問題タブ [levenshtein-distance]

Postgres バックエンドを備えた Rails アプリがあります。

レーベンシュタイン距離または他の同様のメトリックに基づくあいまい検索を可能にする全文検索を追加する必要があります。lexer/stemmer は英語以外の単語を処理する必要があるという事実を追加します (英語のエンジンによって無関係と見なされる意味のある単語を含む可能性のあるターゲット言語を台無しにしないために、字句解析時に言語依存の機能をオフにするだけで問題ありません)。 ）。

Postgres の tsearch にはあいまい検索がないため、ここでは適用されないと思います。間違っている場合は修正してください。

バックエンドとプラグインの可能な組み合わせは何ですか? インフラストラクチャへの追加が少ないソリューションを優先したいと考えています (たとえば、Postgres がファジー ft を持つことができる場合、外部の Lucene を使用する理由)。OTOH、関連する Rails プラグインの品質も重要です。

あなたは何をお勧めします？

更新:レーベンシュタインよりもむしろn-gramベースのメトリックが必要なようです。

配列には 5000 個、場合によってはそれ以上の番地の文字列があります。それらすべてをレーベンシュタインと比較して、同様の一致を見つけたいと思います。すべての 5000 をループして、他のすべての 4999 と直接比較せずに、どうすればこれを行うことができますか?

編集:誰かに提案があれば、別の方法にも興味があります。全体的な目標は、ユーザーが送信した住所に基づいて類似のエントリを見つける (および重複を排除する) ことです。

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

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

または、例えば

または：

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

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

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

レーベンシュタイン距離アルゴリズムでは、この行は何をしますか?:

これらすべての値の最小値を取得しますが、なぜコストが最後に追加され、各配列インデクサー (最初の 2 つのパラメーター) の最後に + 1 があるのはなぜですか?

私は、レーベンシュタイン距離関数を変更して、2つの線の間の距離、またはxy座標のセット（つまり、線の幾何学的距離ではなく、線の類似性または相違性）を検出できるようにしようとしています。しかし、私はいくつかの問題に直面しています。削除コストを取得するために上記の値を取得し、追加を取得するために左側の値を取得する方法を取得しますが、置換中にユークリディアン距離を使用しようとしていますが、機能しません。

私が間違っていることを指摘できれば、それは素晴らしいことです。

javascriptの関連コードは次のとおりです。

サンプル出力：

2 つの文字列を比較して、どれだけ似ているかスコアを取得したいと考えています。例えば「文章がほぼ似ている」「文章が似ている」など。

Java の既存のメソッドには詳しくありませんが、PHP の場合はレーベンシュタイン関数を知っています。

Javaにはより良い方法がありますか?

私は、2つの類似したソースコードファイルを比較するための差分テキストツールを作成中です。

そのような「差分」ツールはたくさんありますが、私のものは少し改善されるでしょう：

一連の行が両側で（つまり、両方のファイルで）不一致であることがわかった場合、それらの行を強調表示するだけでなく、これらの行の個々の変更も強調表示します（ここではこの行間比較と呼びます）。

私のやや機能するソリューションの例：

代替テキストhttp://files.tempel.org/tmp/diff_example.png

現在行われていることは、不一致の行のセットを取得し、それらの単一の文字をもう一度差分アルゴに通して、ピンクのハイライトを生成することです。

ただし、「元の2」を含む2番目の不一致のセットにはさらに作業が必要です。ここでは、最初の2つの右側の行（「追加された行a / b」）が追加され、3番目の行は左側の変更されたバージョンです。私のソフトウェアが、可能性のある変更と可能性のある改行の間のこの違いを検出することを望みます。

この単純な例を見ると、このケースをかなり簡単に検出できます。

レーベンシュタインのようなアルゴリズムでは、3から5のセットのすべての右の行の中で、5行目が左の3行目に最もよく一致することがわかりました。したがって、右側の3行目と4行目が追加されたことを差し引いて、インターを実行できます。 -左の行3と右の行5の行の比較。

ここまでは順調ですね。しかし、私はまだこれをこの目的のためのより一般的なアルゴリズムに変える方法に固執しています。

より複雑な状況では、一連の異なる線が両側に線を追加し、その間にいくつかの密接に一致する線がある可能性があります。これは非常に複雑になります。

左側の最初の行を右側の最良の行に一致させるだけでなく、その逆も同様に、他のすべての行と一致させる必要があります。基本的に、左側のすべての行を右側のすべての行と一致させる必要があります。最悪の場合、これにより交差が均等になる可能性があるため、新しく挿入された行と変更された行が簡単に明確になりません（注：実際に単純化されない限り、このようなブロックで移動された可能性のある行を処理したくありませんアルゴリズム）。

確かに、これが完璧になることは決してありませんが、私は今よりも良くしようとしています。あまり理論的ではないが実用的である（抽象的なアルゴリズムをよく理解していない）提案はありがたいです。

アップデート

私はLCSアルゴがどのように機能するかさえ理解していないことを認めなければなりません。文字列の2つの配列をフィードするだけで、一致しないシーケンスのリストが表示されます。私は基本的にここからのコードを使用しています：http：//www.incava.org/projects/java/java-diff

コードを見ると、2行が一致するかどうかをアルゴリズムに伝える役割を担う1つの関数equal（）が見つかります。Pavelが提案したことに基づいて、それが私が変更を加える場所であるかどうか疑問に思います。しかし、どのように？この関数はブール値のみを返します。一致の品質を識別できる相対値は返しません。そして、同様の線がまだ等しいと見なされるかどうかを決定する固定のレーベンシュタイン配給を単純に使用することはできません-問題の線のセット全体に自己採用するものが必要になります。

つまり、基本的に言っているのは、（完全に）一致しない線の相対的な類似性に関連するファジー値をどこに適用するかがまだわからないということです。

単語の候補を伴うスペル チェッカーを実装する場合、通常どのアルゴリズムが使用されますか?

最初は、入力された新しい単語 (辞書にない場合) を、辞書内の他のすべての単語からのレーベンシュタイン距離と照合し、上位の結果を返すことが理にかなっているかもしれないと考えました。ただし、これは辞書全体を繰り返し評価する必要があり、非常に非効率的です。

これは通常どのように行われますか?

2 つの字幕ファイルがあります。それらが同じテキストを表しているか、類似のテキストを表しているかを示す関数が必要です

「風が吹いている...音楽が流れている」のようなコメントが1つのファイルだけにある場合があります。ただし、内容の 80% パーセントは同じになります。関数は TRUE を返す必要があります (ファイルは同じテキストを表します)。また、次のように l (one - L) の代わりに 1 のようなスペルミスがある場合もあります: She 1eft the bug . もちろん、関数が TRUE を返さなければならないことを意味します。

私のコメント:
関数は、テキストの類似性のパーセンテージを返す必要があります - AGREE

「all the people was happy」と「all the people were not happy」 - ここではスペルミスと見なされるため、同じテキストと見なされます。正確には、関数が返すパーセンテージは低くなりますが、フレーズが類似していると言えるほど高くなります

レーベンシュタインをファイル全体に適用するか、検索文字列だけに適用するかを検討してください。レーベンシュタインについてはわかりませんが、アルゴリズムはファイル全体に適用する必要があります。ただし、非常に長い文字列になります。