編集距離空間探索法

文字列の類似度の指標として、編集距離というものがあります。文字列がリストで並んでいて、そこにある文字列との編集距離が最小になる問題を考えるような場合、シーケンシャルに文字列の編集距離を調べ、編集距離が最小になるアルゴリズムは効率が悪い。そこで、編集距離をノードの値としてもつ二分木というものを考えてみました。そこで質問なのですが、編集距離をノードの値として持つ二分木を用いて、編集距離が最小になるようなアルゴリズムは既に考案されているのでしょうか？

No.2 ベストアンサー 回答者： Tacosan 回答日時： 2009/08/29 23:44

問題の説明が変.

「文字列がリストで並んでいて, そこにある文字列との編集距離が最小になる問題を考える」っのはどんな問題を考えるんでしょうか? 「1つの文字列 s と 1つの文字列のリスト L があり, L の中から s との編集距離が最小となるものを見付ける」問題でいい?
で, そのあとで「編集距離をノードの値としてもつ二分木というものを考えてみました」と書いていますが, この「編集距離」はどのように得られたのですが? リストL 中の文字列を 1つずつ調べる? それとも編集距離はあらかじめ与えられていることを仮定する?
いずれにしても「編集距離が最小になるようなアルゴリズム」ってのは意味不明ですが.
「ソート」は余計かも＞#1.

この回答への補足

説明が不足しておりました。ドキュメントファイルのスペルチェックの実装を考えてください。スペルチェッカーは編集距離が最小となる単語を類推しますよね。そこで単語がリストのように一列に並んでいると、編集距離の算出を線形探索で行わなければならず、時間がかかります。そこで単語を編集距離をキーとして二分木にすれば高速化されそうに思えるが、実際に高速化されるのか？というのが質問の趣旨です。

補足日時：2009/09/03 11:17

No.1 回答者： f272 回答日時： 2009/08/29 19:38

ヒープソートといっておけば十分かな。