問題タブ [levenshtein-distance]

私はここに座って、メイン プログラムのいくつかのアルゴリズムを Java でプログラミングしています (これまでのところ最初のアルゴリズムです)。初心者向けの疑似コードと素敵なチュートリアルを備えた wiki のおかげで、レーベンシュタイン アルゴリズムをうまくプログラムできました :D

次に、Damerau にアップグレードして余分な行を追加することにしましたが、それは DL アルゴではなく OptimalStringAlignmentDistance であると読みました。actionscript コードを読んで、DL にするにはさらに何を追加する必要があるかを理解しようとしましたが、混乱してしまいました。私はJavaに似たコードでさまざまな場所に行ったことがありますが、それらはすべて間違った擬似コードも使用しています。

半日過ごして諦めてこちらにお願いすることにしました。このコードを Java の Damerau-Levenshtein にアップグレードするのを手伝ってくれる人はいますか?

ダメラウ・レーベンシュタイン距離アルゴリズムのウィキペディアのページは次のとおりです。

辞書を使用して光学式文字認識システムを作成しようとしています。

実際、私はまだ実装された辞書を持っていません=)

異なるシンボル間の異なる距離を考慮した、レーベンスタイン距離に基づく単純なメトリックがあると聞いたことがあります。たとえば、'N' と 'H' は互いに非常に近く、d("THEATRE", "TNEATRE") は d("THEATRE", "TOEATRE") より小さくなければなりませんが、これは基本的なレーベンシュタイン距離では不可能です。

そのような指標を見つけるのを手伝ってくれませんか。

私は Java でレーベンシュタイン アルゴリズムを実装し、アルゴリズムによって行われた修正、つまりコストを取得しています。結果をパーセンテージで表示したいので、これは少しは役に立ちますが、あまり役に立ちません。

だから私はそれらの類似点を計算する方法を知りたいです。

また、皆さんがどのようにそれを行うのか、またその理由を知りたいです。

レーベンシュタインを実行したいのですが、作成しているのはリアルタイムアプリケーションなので、はるかに高速です。距離が10を超えると、終了できます。

だれかが Jarowinkler 関数を SQLite のロード可能な拡張機能として実装したかどうか疑問に思っていました。

「SQLite-Levenshtein」に相当するものを探しています。Mateusz Adamowski による SQLite ロード可能な拡張機能としてのレーベンステハイン距離の優れた実装

https://github.com/mateusza/SQLite-Levenshtein

前もって感謝します

Commons Lang apiを使用すると、 LevensteinDistanceを介して2つの文字列間の類似性を計算できます。結果は、ある文字列を別の文字列に変更するために必要な変更の数です。結果が0から1の範囲内にあるといいのですが、文字列間の類似性を識別しやすくなります。結果は0に近い大きな類似性になります。出来ますか？

私が使用している例の下に：

ありがとう！

レーベンシュタイン距離式のCoffeeScript実装、別名EditDistanceを作成または検索しようとしています。これが私がこれまでに持っているものです、どんな助けでも大いに感謝されるでしょう。

ところで：私はこのコードが多くのレベルで間違っていることを知っています、私はありとあらゆる建設的な批判を受けてうれしいです。改善を目指して、この公式を理解してください！

CodeEdit1：Trevorが指摘したエラーを修正しました。上記の現在のコードには、これらの変更が含まれています

更新：私が尋ねている質問は、CoffeeScriptでLevenshteinをどのように実行するかです。

これが、私が達成しようとしていることを理解するのに役立つレーベンシュタイン距離アルゴリズムの「ステップ」です。

手順
1nをsの長さに設定します。mをtの長さに設定します。n = 0の場合、mを返して終了します。m = 0の場合、nを返し、終了します。0..m行と0..n列を含む行列を作成します。

2
最初の行を0..nに初期化します。最初の列を0..mに初期化します。

3 sの各文字を調べます（iは1からnまで）。

4 tの各文字を調べます（jは1からmまで）​​。

5 s[i]がt[j]と等しい場合、コストは0です。s[i]がt [j]と等しくない場合、コストは1です。

6行列のセルd[i、j]を次の最小値に等しく設定します。プラス1のすぐ上のセル：d [i-1、j]+1。b. すぐ左のセルに1を加えたもの：d [i、j-1]+1。c. 対角線上と左のセルにコストを加えたもの：d [i-1、j-1]+コスト。

7反復ステップ（3、4、5、6）が完了すると、セルd [n、m]に距離が表示されます。

出典：http：//www.merriampark.com/ld.htm

私は臨床メッセージの正規化 (スペル チェック) を行っており、与えられた各単語を 900,000 語の医学辞書と照らし合わせてチェックしています。時間の複雑さ/パフォーマンスについてもっと心配しています。

あいまい文字列比較を行いたいのですが、どのライブラリを使用すればよいかわかりません。

オプション1：

オプション 2:

この例では、どちらも同じ答えを返します。この場合、どちらも同じように機能すると思いますか?

約 1000 店舗の情報を含む MySQL データベース テーブルがあります。現在、Excel スプレッドシートをアップロードして、より多くのショップをインポートする予定であり、重複を避けようとしています。

• ショップの名前は同じかもしれませんが、住所が同じになることはありません。
• 店は同じ住所を持っているかもしれませんが、決して同じ名前ではありません

しかし、ここに私の問題があります。

• ストアのスペルが間違っている可能性があります
• アドレスのスペルが間違っている可能性があります

現在、データを一時テーブルにインポートしています。今、輸入店と既存店を比較するにはどうするのがベストなのだろうかと考えています。

私の計画は、各行を見て、お店を比較することです.

• まず、a.name = b.name AND a.street = b.street を比較します。マッチすると、ショップが削除されます。
• 次に、名前と通りについてレーベンシュタイン比較を行います。ここでは、結果が重複しているかどうかを判断するために、結果を手動で確認する必要があるでしょう。

この種のデータ比較の経験がある人はいますか?

更新
良い回答をありがとう。

比較に使用されるフィールドは次のとおりです。

• 名前
• 住所
• 郵便番号
• 街
• 国

私はこれらの線に沿って何かを考えています:

name = Lavenshtein および country = country の行を選択します。
そうすれば、小さなリストを操作するだけで済みます。

次に、名前と住所をより徹底的に比較し始めます。

Edit/Levenstein 距離を使用して、単語間の類似性を測定しています。最も単純な実装とは異なり、私の手紙にはタイム スタンプがあり、サンプル番号 N=0,1,2,... としましょう。

私が直面している問題は、コスト マトリックスに沿って、同じ (最小) コストで終わるさまざまなパスを取得できることです。これらのさまざまなパスは、さまざまなターゲット文字列に関連付けられています。たとえば、ソース文字列aaとターゲット文字列の間の距離を測定しbab、ソース文字列がタイム スタンプ N=0 で始まると仮定すると、同じコスト 2 (1 つの追加と 1 つの置換) を持つ 2 つのパスがあります。

1. bN=-1 で加算し、1 番目はそのままにして、2 番目を にa置き換えます。ab
2. 1 番目aをbに置き換え、2 番目はそのままにして、N=2 でa追加します。b

時系列で並べると、次の 2 つの結果は異なります。

それがいつ起こるかを知る必要があるので、いくつかの基準に基づいて 2 つの可能なターゲットから選択できます。途中でパスをトレースし、最小コストにつながるすべての可能なパスを追跡する以外に他の方法はありますか?

そもそもタイムラインはモデルの一部であるため、代わりにダイナミック タイム ワープを使用することを検討しましたが、コスト マトリックスが無限に初期化されているため ([0,0] エントリを除く)、最初のステップは、常にターゲットの最初のフレームをソースの最初のフレームに一致させ、その結果、ターゲットはソースと同じタイムスタンプで開始されます。とにかく、DTW を使用して、同じ最小コストにつながるすべてのパスをトレースする必要があります。

どんな助けや洞察も歓迎します。