「レーベンシュタイン距離がX未満のすべての文字列を取得する」を実行するための効率的なデータ構造があるかどうか疑問に思います。
私が興味を持っていることはほとんどありません：
- アルゴリズムの説明。
- 既存のデータベース/プログラミング言語に既存の実装はありますか？
- 参照できる紙・記事は？
1142 次
2 に答える
3
これは、レーベンシュタイン距離をメトリック (または距離) 関数として使用するメトリック空間での最近傍検索です。
VP ツリーは、その問題を解決する方法の 1 つです。
このPython VP ツリーの実装は、VP ツリーがどのように機能するかを示す実用的なデモです。たとえば、単語リストで実行します。単語を入力すると、そのリスト内の X 距離以内の単語が返されます。入力した単語から
于 2010-12-01T03:17:34.310 に答える
0
単純な幅優先探索のように聞こえます。各世代は前の世代から1つだけ「編集」されており、文字列が1つだけのレベルに表示されることを確認するためのチェックが行われます。
これは、ループのペアでいくつかのハッシュセット/ハッシュテーブルを使用して簡単に実装できます。
于 2010-12-01T03:39:47.340 に答える