問題タブ [edit-distance]

この質問は新しいものではなく、こことここで何らかの説明を見てきました。どちらの方法も、クエリ 1 とクエリ 2 の項に対して N グラム (主にバイグラム) の計算を実行し、コサインの類似性を見つけることを説明していました。

私が理解していることに基づいて明確にすることを望んでいました：

クエリ 1 とクエリ 2 のすべてのバイグラムの TF-IDF スコアを取得し、そのスコアを使用してコサイン類似度スコアを計算する必要があります。もしそうなら、より明確な説明のために誰かが親切に簡単なpythonコードを書くことができますか?

文字列間の距離を見つけるための Wagner-Fischer アルゴリズムを理解しようとしています。次のリンクで疑似コードを調べています: http://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm

実際、私はアルゴリズムの要点を理解し、直感的に理解しています。なぜなら、d[i-1, j] + 1, d[i, j-1] + 1 と d[i-1, j-1 ] + 1は、削除、挿入、置換と見なされます。誰かが実装のニュアンスをより詳細に説明してくれれば幸いです。

2 つのクエリがあります。

PythonライブラリLevenshteinを使用してこのコードを実行すると:

12 という出力が得られます。問題は、値 12 がどのように導き出されるのかということです。

打数差で言えば、間違いなく12以上あるからです。

edit-distance を使用して、R を使用して多数の整数リストを比較したいと考えています。例:list1[231, 3883, 21099, 12, 2]とlist2[433, 3883, 12, 919, 2]

これら2つのリストの間の距離だけを取得したいと思います。元。上記のリストでは、距離は に等しくなり3ます。list2のようlist1にするには、substitute 231for 433、 then add 21099after 3883、 then としdelete 919ます。

list1 を list2 のように見せるために必要な追加と削除の数を見つけたいと思います。Rには組み込み関数があることを知っています: adist(). ただし、文字列を比較する場合にのみ機能するようです（文字列のリストでさえありません）。Google は私にプッシュし続けますがadist()、dist()どちらもこの問題を解決するものではありません。車輪の再発明はしたくないので、すでに存在する機能はありますか? https://searchcode.com/codesearch/view/13555814/にあるように書き直そうとしadist()ました が、現在の R 能力には複雑すぎます。

単語の挿入/削除/編集に関して、2 つの文字列間の距離を確認したい。これはレーベンシュタイン距離に似ていますが、私は文字ではなく言葉だけを気にします。例えば：

「猫はマットの上に座った」＆「犬はマットの上に注意深く座った」

単語距離は 3 になります。

レーベンシュタイン距離の Rosetta Code C++ スクリプトを使用していますが、その方法がわかりません。

私は最近この質問に出くわしました：

この問題を解決する 1 つの方法は、動的計画法を使用して 2 つの文字列間の編集距離を見つけ、それが 1 かどうかを確認することです。これには O(N2) 時間かかります。1編集離れているかどうかを確認するだけなので、線形時間でこれを行う方法はありますか?

以下に書いたコードはほとんどの場合に機能しますが、{"m",""} のような場合には失敗します