1

私は現在、次の定式化で問題の効率的な解決策を考え出そうとしています。

入力文字列sと固定レキシコンが与えられた場合、sまでのレーベンシュタイン距離が最小の文字列w1 || w2（||は連結を示し、w1とw2はレキシコン内の単語です）を見つけます。

明らかな素朴な解決策は次のとおりです。

for word1 in lexicon:
   for word2 in lexicon:
       if lev_dist(word1 + word2) < lev_dist(lowest):
          lowest = word1 + word2

この問題にはもっと良い解決策があるはずです。誰かが何か洞察を提供できますか？

4

3 に答える 3

1

個々の文字列のコストに下限を設定することで、少し改善できる場合があります。

http://en.wikipedia.org/wiki/Levenshtein_distanceのアルゴリズムを見ると、s[i] とt[j]、ここで s と t は比較される文字列であるため、変更/削除/挿入のコストを 2 つの文字列内の操作の位置に依存させることができます。

これは、XXX とマークされた文字に対する操作が自由なコスト関数を使用して、abcXXX と abcdef の間の距離を計算できることを意味します。これにより、文字列 XXX が実際に可能な限り最も好ましい文字列である場合、abcXXX を abcdef に変換するコストを計算できます。

したがって、レキシコン内の各単語 w1 について、w1XXX とターゲット文字列、および XXXw1 とターゲット文字列の間の距離を計算します。w1XXX 距離と XXXw1 距離の順にソートされた辞書の 2 つのコピーを作成します。次に、ペアのコストの下限である左手と右手のコストの合計の順にすべてのペアを試します。これまでの最良の回答を追跡します。最良の答えが、遭遇する次の下限コストと少なくとも同じくらい良い場合、この最良の答えを改善できるものは何もないことがわかっているので、やめることができます。

于 2012-06-24T05:36:42.200 に答える
0

同じレキシコンで多くのクエリを実行していて、クエリ時間を改善したいが、前処理に時間がかかる場合は、可能なすべての単語を w1 || の形式で含むトライを作成できます。w2. 次に、ここで説明されているアルゴリズムを使用できます:トライを使用した高速で簡単なレーベンシュタイン距離で、必要な単語の答えを見つけることができます。

アルゴリズムが行うことは、基本的にトライのノードをたどり、現在の最小値を追跡することです。次に、あるノードにたどり着き、レーベンシュタイン距離 (ルートから現在のノードおよび入力文字列 s までの単語の距離) が、これまでに達成された最小値よりもすでに大きい場合、このノードをルートとするサブツリー全体を剪定できます。答えを導き出すことができないからです。

英単語とランダムなクエリ単語の辞書を使った私のテストでは、実行するクエリの種類にもよりますが、辞書内のすべての単語をテストする通常のアプローチよりも 30 倍から 300 倍高速です。

于 2012-06-24T14:28:54.480 に答える
0

同じレキシコンに対してこれを何度もやりたいと思います。単語のつづりが間違っていて、単語間にスペースがないことが原因ではないかと疑っています。

最初に必ず必要になるのは、文字列の「近さ」を推定する方法です。私は正規化技術が好きです。たとえば、各文字を同等クラスの代表者に置き換えます。(おそらく、M と N は、音が似ているため、両方とも M になります。おそらく、同様の理由で PH --> F になります。)

ここで、正規化されたレキシコンを前方と後方の両方でトライまたは類似の構造に入力する必要があります。

ここで、前方と後方の両方で針を検索しますが、両方の方向の中間結果を追跡します。つまり、検索文字列の各位置で、その位置で選択された候補トライ ノードのリストを追跡します。

次に、中間結果の前向き配列と後向き配列を比較し、単語間の適切な結合点のように見える場所を探します。また、互いに 1 つずつ離れたジョイン ポイントを確認することもできます。(つまり、最初の単語の終わりと 2 番目の単語の始まりを見つけました。)

もしそうなら、あなたはあなたの単語のペアを見つけました.

于 2012-06-24T08:04:48.583 に答える