問題タブ [edit-distance]

ユースケースは、固定文字列のように他の文字列の大規模なセットをランク付けするオートコンプリート オプションです。

各オプションソリューションを最初からやり直すよりも優れた仕事をすることができる、DFA RegEx のような何かのろくでなし化はありますか?

この質問をした人は解決策を知っているようですが、情報源を挙げていません。

（ps「このリンクを読む」タイプの回答歓迎。）

文字列編集距離 (レーベンシュタイン距離) を使用して、アイ トラッキング実験のスキャンパスを比較しています。（現在stringdist、Rでパッケージを使用しています）

基本的に文字列の文字は、6x4 マトリックスの (注視) 位置を表します。マトリックスは次のように構成されています。

基本的なレーベンシュタイン距離を使用して文字列を比較するaと、文字列内の と の比較は との比較gと同じ推定値にaなりxます。

例えば：

これは、文字列が等しく (異なる) 類似していることを意味します。

マトリックスに隣接性を組み込む方法で、文字列比較に重みを付けたいと思います。たとえば、 と の間の距離は、 と の間の距離aよりxも大きく重み付けする必要がaありgます。

One way could be to calculate the "walk" (horizontal and vertial steps) from one letter to the other in the matrix and divide by the max "walk"-distance (i.e. from a to x). E.g. the "walk"-distance from a to g would be 1 and from a to x it would be 8 resulting in a weight of 1/8 and 1 respectively.

Is there a way to implement this (in either R or python)?

2 つのコミットのコンテンツ間の適切な編集距離を計算する方法を探しています。

私が見つけた最良の方法は、の出力から何かを導き出すことです

...しかし、この方法を使用して思いつくものは、編集距離の非常に大まかなプロキシになります。

もっと良いものはありますか？

グラフ編集距離 (GED) やその他のグラフ類似度 ( http://goo.gl/gmDMgAなど) の計算に関する多くの理論を読みましたが、そのような計算を実行するためのツールを見つけることができませんでした。

グラフの編集距離を計算するプログラミング ライブラリまたはソフトウェアはありますか? また、2 つのグラフ間のグラフの類似度を測定するその他の方法はありますか?

これは ScalaでのKendall タウ距離の正しい実装ですか?

問題は、アルゴリズムをテストするのに十分なデータがなく、ウィキペディアの例がほんの少ししかないことです。また、アルゴリズムを十分に理解していないため、独自のテスト データを生成できません。ほとんどの情報源は、関連はあるが別の動物であるケンダル タウの順位相関係数に関するものです。たぶん、どうにかして一方を他方から派生させることができますか？

今のところ、パフォーマンスは重要ではないとしましょう。

アップデート

これで、Kendall タウ距離アルゴリズムの 3 つの実装ができました。そのうちの 2 つ (distance1とdistance3) は同じ結果になります (以下を参照)。それで、どれが正しいですか？

そして、ここにいくつかの結果があります：

典型的な動的レーベンシュタイン距離アルゴリズムでは、 cell の値を計算するために、d[i][j]とiはjそれぞれ行番号と列番号でありd[i-1][j-1]+0/1、d[i-1][j]+1との最小値を取りd[i][j-1]+1ます。ただし、 と の最小値d[i-1][j-1]+0/1はd[i-1][j]+1常に になるように思われます。この場合、計算にd[i-1][j-1]+0/1含めるのは冗長に思えます。レーベンシュタイン距離アルゴリズムで>d[i-1][j]+1の場合はありますか?そうでない場合は、この比較を省略した方が効率的ではないでしょうか?d[i-1][j-1]+0/1d[i-1][j]+1

編集:調査不足の質問で申し訳ありません。アルゴリズムの標準的な実行では、d[i-1][j-1]+0/1>のインスタンスが表示されd[i-1][j]+1ます。

（2行目を考えてください）。

Scalding では、次のことを行う必要があります。

1. 文字列フィールドを最初の 3 文字でグループ化する
2. edit-distanceメトリックを使用して、すべてのグループのすべてのペアの文字列を比較します ( http://en.wikipedia.org/wiki/Edit_distance )
3. レコードがある CSV ファイルに結果を書き込みますstring; string; distance

文字列をグループ化するには、次の例のように mapandを使用します。groupBy

その結果、次のようになります。

aaaさて、この例では、このリストのキーを持つ文字列の編集距離を計算する必要があります。

このリストの「bbb」キーを持つすべての文字列の次:

等

独自の関数に置き換える必要があるすべてのグループのすべての文字列間の編集距離を計算するにはtoList、どうすればよいですか? また、関数の結果を CSV ファイルに書き込むにはどうすればよいですか?

ありがとう！

アップデート

Listスカルディングからの入手方法はPipe？

toList別のものを返すだけPipeなので、すべてを使用することはできません: