たとえば、英語の単語から始めて、 "light"や "tight"などの文字列を1回高速に検索できる構造体/アルゴリズムがあります。単語 "right"をクエリとして使用しますか?つまり、クエリ文字列にLevenshteinの距離が小さい文字列を取得したいとします。Levenshtein距離で近い文字列を検索するためのデータ構造
答えて
私は、O(1)時間にインデックスを作成してアクセスできる類似性のキャッシュを事前に構築するのが最速の方法だと考えています。このトリックは、一般的なスペルミスがキャッシュに追加されるのを発見することです。かなり大きくなる可能性があります。
私は、Googleが幅広い統計クエリ検索データを使って同様のことをすると思います。
長さnとmの文字列の場合、Levenshtein距離を計算するとO(nm)
なので、すべてのLevenshtein距離を計算する単純なアプローチは非常に高価です。
しかし、Levenshteinアルゴリズムを視覚化すると、基本的に編集距離でn * mの表が塗りつぶされます。しかし、同じ数文字(接頭辞)で始まる単語の場合、Levenshteinテーブルの最初の数行は同じになります。 (もちろんクエリ文字列を修正してください)
trie (also called prefix tree)を使用することをお勧めします。クエリ文字列を読み取り、Levenshtein行のトライを作成します。その後、簡単にトラバースしてクエリ文字列に近い文字列を見つけることができます。
(これはは、新しいクエリ文字列のための新しいトライを構築する必要があることを意味します。私はすべてのペア距離に対しても同様に魅力的な構造があるとは思わない。)私は思っ
私は最近、素晴らしいpythonの実装でこれについての記事を見ました。見つけたらリンクを追加します。 編集:Here it is, on Steve Hanov's blog.
BK-treeデータ構造がここで適切かもしれません。これは、「クエリーワードから編集距離k以内のすべての単語は何ですか?」という形式のクエリーを効率的にサポートするように設計されています。その性能保証は合理的に優れており、実装するのが難しくありません。
希望すると便利です。
- 1. Levenshteinフレーズの距離/文字列マッチングアルゴリズム
- 2. 文字列を検索するためのより速いデータ構造
- 3. ランダムワード検索のためのデータ構造
- 4. 検索距離
- 5. Android&ファジーマッチング、nグラム、Levenshtein距離
- 6. 言語特有のためのDamerau-Levenshtein距離
- 7. 方法 "Xより小さいLevenshtein距離ですべての文字列を取得する"
- 8. 正規表現のLevenshtein距離
- 9. セットから最も近い要素を効率的に検索するためのデータ構造
- 10. 最近の回文との距離
- 11. シフト文字列のデータ構造
- 12. 検索情報のための最速データ構造体C++
- 13. 検索エンジンのようなjava文字列検索の構文
- 14. 交換可能な文字列を保持するためのデータ構造
- 15. 最も最近のファイルの文字列を検索するバッチファイル
- 16. SQL関数と距離の間の距離が最も近い
- 17. おそらくLevenshteinの距離を使って検索語の精度を一致させる
- 18. 等距離文字の特定の正規表現検索の最適化
- 19. 情報検索システムのデータ構造/アルゴリズム
- 20. 範囲検索のデータ構造(再訪)
- 21. Android NFC(近距離通信)
- 22. Google maps距離近似
- 23. 配列内の文字列を文字列で検索する
- 24. JSON文字列の構造
- 25. 英語以外の言語でのLevenshtein距離
- 26. 文字列の文字列の検索
- 27. Pythonの:(リストから)最も近い文字列を検索する別の文字列に
- 28. 自然言語文構造の検索
- 29. 文字列のdjango検索文字列
- 30. 別の文字列で文字列を検索するには?
実際にはスペルミスの場合は良いアプローチですが、Levenshtein距離の理論的応用の場合はそれほど有用ではありません。 – us2012
正確にはどういう意味ですか?それが私が想像しているものであれば、メモリの使用は実用的ではないでしょう。 – MaiaVictor
@ us2012が目的です。 – MaiaVictor