0

私はそのようなアルゴリズムを探していますが、文字間ではなく単語間で置換を行うアルゴリズムです。そのようなアルゴリズムはありますか？

SQL Server での実装を探していますが、アルゴリズムの名前で十分です。

4

2 に答える 2

0
  1. 両方の文字列をスペースで分割
  2. 両方の文字列の単語を調べて単語ハッシュテーブルを作成します（必要に応じて、分割操作から取得した配列を1つに連結します）、新しい単語ごとに増分的に新しい番号が取得されます
  3. 結果として得られる 2 つの数値配列に対してレーベンシュタイン アルゴリズムを使用します (ただし、11,12 -> "1112" -> 1,1,1,2 であるため、それらを文字列に戻すことはありません)

単語の並べ替え中にスペルミスを見つける必要がある場合は、スペースが最も少ない単語を取得し、その分割配列を並べ替えて、同じ単語を異なる順序で並べ替えた文字列に戻し、新しい単語と 2 番目のフレーズでレーベンシュタインを実行すると、うまく機能することがわかりました。 !

Harward Medical School (2 スペース、6 順列) Harward School of Medicine (3 スペース、24 順列) レーベンシュタイン距離 - 17 たとえば、「スタンフォード大学医学部」 (レーベンシュタイン距離 5) と比較してください。

Harward School Medical 対 Harward School of Medicine の LD は 6 です。それでもスタンフォード大学との間違いは許容されますが、ランクがはるかに近いため、単語を削除するようなものを組み込むことができます (この場合、"of" を削除すると、LD は のみ取得されます)。 3)

スペースによる単語の並べ替えのパフォーマンスは O(n!) であり、単語の削除は O(n+m) です。ここで、n,m は各フレーズの単語の数です。複数の単語を削除する場合、またはその逆の場合を除きます。 4文字未満の単語、または前置詞/形容詞リストからの単語などのみをドロップすることを選択します.

レーベンシュタインの性能は、ウィキペディアのページで説明されています。

于 2011-09-27T16:34:05.217 に答える