4

私は、人々が学校で学ぶ必要のある単語を翻訳しようとする Web アプリを PHP で作成しています。

たとえば、誰かがオランダ語の 'weer' を英語の 'weather' に翻訳する必要がありますが、残念ながら 'whether' と入力します。彼はほぼ正しい単語を入力したので、もう一度試してもらいたいと思います.。間違いを犯した場所にドット ' ' を付けます。

Language A:   weer
Language B:   weather
Input:        whether
Output:       w..ther

または、例えば

Language A:   fout
Language B:   mistake
Input:        mitake
Output:       mi.take

または：

Language A:   echt
Language B:   genuine
Input:        genuinely
Output:       genuinely (almost good, shorten the word a little bit)

しかし、入力が目的の翻訳と大きく異なる場合、次のような出力を得たくありません........

レーベンシュタイン距離について聞いたので、それによく似たアルゴリズムが必要だと思いますが、実行する操作の数をエコーする代わりに、適切な場所にドットを配置する方法がわかりません。

では、誰かが間違えた場所にドットを付けて、スペルミスのある単語を返すにはどうすればよいでしょうか?

4

3 に答える 3

4

まず、ウィキペディアでレーベンシュタイン アルゴリズムを見てみましょう。d次に、記事ページの例と結果のマトリックスを見てください。

                *k*     *i*     *t*     *t*     *e*     *n*
        >0       1       2       3       4       5       6 
*s*      1      >1       2       3       4       5       6 
*i*      2       2      >1       2       3       4       5 
*t*      3       3       2      >1       2       3       4 
*t*      4       4       3       2      >1       2       3 
*i*      5       5       4       3       2      >2       3 
*n*      6       6       5       4       3       3      >2 
*g*      7       7       6       5       4       4      >3

距離は、マトリックス d[m, n] の右下隅にあります。しかし、そこから、行列 d[1, 1] の左上への最小ステップをバックトラックすることが可能になりました。パスを最小化する各ステップで、左、左上、または上に移動するだけです。上記の例では、「>」記号でマークされたパスが見つかります。

  s i t t i n g      k i t t e n
0 1 1 1 1 2 2 3    0 1 1 1 1 2 2 3
  ^       ^   ^      ^       ^   ^
  changes in the distance, replace by dots

これで、距離が変化する位置 d[i,j] の最小パス (上記の例では ^ でマーク) を見つけることができます。これらの文字については、最初 (または 2 番目) の単語の位置 i (または j それぞれ）。

結果：

  s i t t i n g      k i t t e n
  ^       ^   ^      ^       ^   ^
  . i t t . n .      . i t t . n .
于 2009-12-31T16:06:33.693 に答える
3

あなたが探している用語は「編集距離」と呼ばれます。レーベンシュタイン距離のようなものを使用すると、1 つの文字列を別の文字列に変換するために必要な操作 (挿入、削除、置換など) の数がわかります。

他の「編集距離」アルゴリズムのリストは次のとおりです。

単語が「十分に近い」(つまり、必要な編集のしきい値を超えていない) と判断したら、編集が必要な場所を示すことができます (ドットを表示することによって)。

では、ドットをどこに置くべきかをどうやって知るのでしょうか?

「レーベンシュタイン距離」の興味深い点は、各軸に 1 つの単語を含む M x N 行列を使用することです (レーベンシュタインの記事のサンプル行列を参照してください)。マトリックスを作成したら、どの文字を正しく編集する必要があるかを判断できます。そこにドットを配置します。レターに「追加の編集が必要ない」場合は、レターを印刷するだけです。かなりクール。

于 2009-12-31T16:02:03.103 に答える
0

レーベンシュタインだけでなく、多段階のプロセスを実行する必要があると思います。まず、入力単語がターゲット単語の形式であるかどうかを確認します。それはあなたの3番目の例をキャッチし、ドットを追加する心配もありません. このステップを使用して同義語をキャッチすることもできます。次のステップは、2 つの文字列の長さの違いを確認することです。

差が 0 の場合は、文字の比較を行ってドットを配置できます。すべてのドットを表示したくない場合は、配置されたドットの数を保持し、制限を超えるとエラー メッセージを表示する必要があります。（すみません、間違っていました）

違いが入力が長いことを示している場合は、削除する文字を確認して問題を解決する必要があります。ここで、レーベンシュタインを使用して、それらが遠すぎる場合にどれだけ近いかを確認できます。範囲内にある場合はエラーメッセージを表示します。レーベンシュタインの手順を逆に実行し、何らかの方法で変更をマークする必要があります。手紙を削除する必要があることをどのように示したいかわかりません。

違いが入力が短いことを示している場合は、レーベンシュタイン距離を使用して、2 つの単語が十分に近いかどうかを確認するか、エラーを表示できます。次に、逆の手順を実行して、挿入用のドットと置換用のドットを追加します。

実際には、最後の 2 つのステップを 1 つの関数に組み合わせることができます。この関数はアルゴリズムを実行し、挿入削除または置換を記憶し、それに応じて出力を変更します。

于 2009-12-31T16:01:35.897 に答える