- ベストアンサー
編集距離空間探索法
文字列の類似度の指標として、編集距離というものがあります。文字列がリストで並んでいて、そこにある文字列との編集距離が最小になる問題を考えるような場合、シーケンシャルに文字列の編集距離を調べ、編集距離が最小になるアルゴリズムは効率が悪い。そこで、編集距離をノードの値としてもつ二分木というものを考えてみました。そこで質問なのですが、編集距離をノードの値として持つ二分木を用いて、編集距離が最小になるようなアルゴリズムは既に考案されているのでしょうか？
- student_of_kit
- お礼率80% (16/20)
- C・C++・C#
- 回答数2
- ありがとう数11
- みんなの回答 （2）
- 専門家の回答
関連するQ&A
- schemeで二分探索木の問題について
schemeの問題で，「二分探索木であることを判定する関数を定義せよ」という問題があります。二分探索木とは，左の部分木に含まれる値はノードの値より小さく，右は大きい二分木です。 頑張って考えたのですが，まったくわかりません。 どなたかご回答をしていただけると助かります。 よろしくお願いします。
- 締切済み
- その他（プログラミング・開発）
- 探索アルゴリズムの名称について
以下の探索もしくは組み合わせのアルゴリズムに名称があるのかを教えていただければ幸いです． ある変数a1,a2,a3・・・，b1,b2,b3・・・があり（それぞれ小さい順にソートされている）， このaとbにより影響する評価関数が最小となる最適な組を探索するアルゴリズムです． (1)まずa1・b1のペアを用いた時の値を算出する． (2)次にa2・b1のペアとa1・b2のペアでの値をそれぞれ算出し，小さい方を見つける． （今回はa1・b2のペアの方が小さかったとします．） (3)次にa2・b2のペアとa1・b3のペアでの値をそれぞれ算出し，小さい方を見つける． (2)，(3)の様な処理を繰り返し行い，最小となるa・bの組を探索する． 以上の様なアルゴリズムなのですが，名称があるのかをお聞きしたいと思います． 言葉で書くとイメージしづらいですが，小学・中学ぐらいで勉強した最短経路問題のように 格子状の図を書くと分かりやすいと思います． 二方向のみをみて探索していきます． 個人的には，二分木探索に近いと思うのですがどうでしょうか？ ただ，進み方によっては，同じ組み合わせを探索する事も出来るので， 完全な二分木探索ではないような気がします． 皆様のお力をお貸しいただければありがたいです． お願いいたします．
- 締切済み
- 数学・算数
- 4分木の探索プログラミングについて
全零で初期化した二次元配列の要素の値を ある条件を満たすまで再帰的に処理して値を返していくような プログラムを書いています そこで４分木を使わなければならなくなりました。 4分木の参考サイトが少ないのでアルゴリズムがわからないのですが 二分木の拡張版のようなもので複雑な再帰処理が必要になるでしょうか。
- 締切済み
- C・C++・C#
- 二分探索木のheight(高さ?)を見つけるアルゴリズム
Binary Search Tree(=二分探索木)のheight(高さ?)を見つけるメソッドを作りたいのですが、 そのアルゴリズムが頭にうまく浮かびません。 まず思いついたのは一つ一つのNode(=ノード)をそれぞれのLeaf(=リーフ、葉?)まで辿っていって それらのheightを全部記憶させておいて後で比較するという…最も原始的な方法です。 しかし、Treeの大きさも未知なので用意する変数の数も未知になって どう考えても不適当でしょう(当たり前か(^^ゞ)。 Recursion(=再帰)を使えばいいのでしょうか? そうだとしてもどうすればいいのか…。 アルゴリズムがパッと浮かぶ方、どうか教えて下さい。
- ベストアンサー
- Java
- ２点同士の距離の平均が最小となる木
グラフ理論に関してです。 ネットや手持ちのグラフ理論入門書で探しても見つけられなかったので質問させて下さい。 重みつき連結グラフにおいて, 入力が「グラフ上の複数(>=2)の節点」であり、出力が「節点同士の距離平均が最小であるような木」となるようなアルゴリズムはあるでしょうか。 もしくはそれに対する近似的なアルゴリズムでもかまいません。 言い直すと、入力された節点集合を U として ( Σ<iとjの距離> ) / |U| i,j∈U, i≠j が最小となるような木です。
- ベストアンサー
- 数学・算数
- 退化木をバランス木にしたい
二分探索木でアドレス帳を作っています。 二分探索木はノードの削除を繰り返すと退化木になってしまいますが、 これを回避するために二分探索木を再構成して、バランス木に近い形にしたいのです。 この二分探索木を再構成するアルゴリズムが全く思いつかず困っています。 詳しい方、ご教授お願い申し上げます。 ちなみに言語はCです。
- ベストアンサー
- C・C++・C#
- 2分木
実行すると 「トップノードの値を入力してください。20 ノード[20:深さ0]の左の子の値を入れてください。15 ノード[20:深さ0]の右の子の値を入れてください。40 ノード[15:深さ1]の左の子の値を入れてください。11 ノード[15:深さ1]の右の子の値を入れてください。18 ノード[11:深さ2]の左の子の値を入れてください。/ ノード[18:深さ2]の左の子の値を入れてください。17 ノード[18:深さ2]の右の子の値を入れてください。/ ・ が表示されて2分木のデータを作成するプログラムを作りたいのです。絵で表すと、 20 ／ ＼ 15 40 ／ ＼ ／＼ 11 18 30 55 ／ ／＼ ＼ 17 25 33 61 のようになります(なんか絵がずれて表示される）。 一応、自分で考えてみたのですが #include<stdio.h> #include<malloc.h> struct data { int kazu; struct data *left; struct data *right; }; main() { struct data *root,*p; root=(struct data *)malloc(sizeof(struct data)); printf("トップノードの値を入れてください:"); scanf("%d",root->kazu); root->left=root->right=NULL; while(1){ p=(struct data *)malloc(sizeof(struct data)); printf("ノード%d,深さ%dの左の子の値を入れてください",root->kazu, scanf("%d", ); printf("ノード%d,深さ%dの右の子の値を入れてください",root->kazu, scanf("%d", ); if( break; なんか全然良くわからないのです。アルゴリズムの本を見て勉強していて、データ構造は理解できたのですが、２分木(グラフ)で詰まってしまいました。 小さい順に数を表示させるとか、そういうのじゃなくて、単にデータを格納するだけです。どうかよろしくお願いします。
- 締切済み
- C・C++・C#
- アルゴリズム(2分探索木)の問題について
２分探索木のアルゴリズムに関する問題について質問させていただきます。 [問題] 集合Sに対する2文探索木とは、ラベルつきの2分木で、 その頂点vにはSのある要素l(v)がラベルとしてつけられている。 l(v)は次の性質を満たす。 １．vの左部分木の頂点uに対して l(u) < l(v) 2．vの右部分木の頂点uに対して l(u) > l(v) 3．Sの任意の要素aに対して l(v) = a となる頂点vはちょうどひとつある。 図はキーワード集合{begin,else,end,if,then}をあらわす2分探索木の例である。 いま、集合Sを表す2分探索木と要素aが与えられているときa∈Sならば"はい"、 そうでなければ"いいえ"を出力するアルゴリズムを考える。 このアルゴリズムは、木の根rについて一回だけ再帰手続きSEARCH(a,r)を呼び出せばよい。 ただし、SEARCH(a,v)はvを根とする部分木中に要素aが含まれているかを判定する。 含まれているときに値"はい"を、そうでなければ値"いいえ"を返す。 ・アルゴリズム procedure SEARCH(a,v): if a = l(v) then return "はい" else if a < l(v) then if vが左の子wを持つ then return SEARCH( ア ) else return "いいえ" else イ 以下の問題に答えよ。 (1) 上のアルゴリズムのア,イを埋めよ。 (2) 上のアルゴリズムを参考にして、集合Sからのデータの削除DELETE(a,S)を考える。 削除すべき要素aが頂点vのラベルであったとする。そのとき次の3つの場合について、行うべき操作を記述せよ。 (i) 頂点vが葉である (ii) 頂点vの子が1個ある (iii) 頂点vの子が2個ある 以上です。 設問(1)は解けました。 答えは ア: a,w イ: a > l(v) then if vが右の子wを持つ then return SEARCH(a,w) else return "いいえ" になるのではないかと思います。 設問(2)についてなのですが、それぞれの場合について、どのような操作をすればよいのかは、 参考書などを読んで理解したのですが、どのように記述したらよいかがわかりません。 長文になってしまい申し訳ないのですが、回答よろしくお願いいたします。
- ベストアンサー
- その他（プログラミング・開発）
- アルゴリズムの2-3-4木
アルゴリズムの2-3-4木 アルゴリズムの平衡木の一種である2-3-4木を使い、テキストファイルに書かれている文中の英単語1文字1文字を挿入し（同じ単語は1度だけ）、全ての単語の配置（パラグラフ、行数）を表示するというプログラムを考えているのですが、どのように組めばいいのかがわかりません。 例えばテキストファイルの文中に、studyという単語が1つ目のパラグラフの2行目、2つ目のパラグラフの4行目にあれば、 study (1,2) (2,4) と表示するプログラムです。2-3-4木ではどのようにデータを格納していくかはわかったのですが、データの挿入やノードの分割などをプログラムではどのように書けばいいのでしょうか。 どなたかご教授お願いいたします。
- 締切済み
- Java
- Excelで各行の最小値となる列の探索
Excelで，各行ごとに，最小値を探索し，その最小値が どの列のデータかを計算したいのですが，どのようにすればよいのでしょうか？ 例えば 山田 鈴木 田中 データ(1) 10.3 0.42 0.5 データ(2) 1 10.1 4 データ(3) 5 11.8 2 といった感じのデータに対して， 山田 鈴木 田中 データ(1) 10.3 0.42 0.5 鈴木 データ(2) 1 10.1 4 山田 データ(3) 5 11.8 2 田中 という感じで，各列の1行目の値が出力されるように したいのですが。 一応，LookUp関数，Match＆Index関数を使ってみましたが，探索する文字列が小数のためか，探索できる行と N/Aになるものとが存在し，その差がなぜ生じるのかが わかりません。 上記関数にはこだわらないので，何か良い方法がありましたらご教授ください。
- ベストアンサー
- オフィス系ソフト
補足
説明が不足しておりました。ドキュメントファイルのスペルチェックの実装を考えてください。スペルチェッカーは編集距離が最小となる単語を類推しますよね。そこで単語がリストのように一列に並んでいると、編集距離の算出を線形探索で行わなければならず、時間がかかります。そこで単語を編集距離をキーとして二分木にすれば高速化されそうに思えるが、実際に高速化されるのか？というのが質問の趣旨です。