1

たとえば、OST やネットワーク エラー修正アプリケーションを作成しているとします。つまり、"*leph*nt" のように、いくつかの文字が欠落している単語を扱っています。英語の辞書が配列に格納されています。それがどの単語であるかをどのように判断しますか？

4

2 に答える 2

5

一般的なアプローチは、レーベンシュタイン距離で測定された最も近い単語を使用することです。同点は任意に解決でき、通常は最大許容距離が使用されます。

于 2013-03-03T08:10:54.810 に答える
3

クエリとすべての辞書の単語の間のレーベンシュタイン距離の計算は、確かに遅くなります。

生物学的配列のBLASTプログラムでは、より優れた戦略が使用されます。BLAST では、インデックスは最初に、短い固定長 K の部分文字列を、それらを含むすべての単語のリストに関連付けるシーケンスのデータベースで構築されます。

クエリでは、BLAST はクエリ文字列から長さ K のすべての部分文字列のインデックスを検索します。次に、クエリ文字列とインデックス文字列全体で一致する部分文字列を拡張して、おおよそのレーベンシュタイン距離をすばやく計算し、距離がしきい値を下回るインデックス文字列を返します。

于 2013-03-06T01:56:29.833 に答える