問題タブ [hamming-distance]

同じポイントの 2 つのデータセット間のハミング距離を計算する方法は?両方のデータセットはまったく同じに見えます。
http://postimg.org/image/u11qnsolh/

同じ数のポイントの 2 つのデータセットがあります。
合計点数 -19

最初のデータセットには 3 つのクラスターがあります。
クラスタ A には 4 つのポイントがあります
クラスタ B には 2 つのポイントがあります
クラスタ C には 4 つのポイントがあります

残りのポイントはクラスターの外側にあります

2 番目のデータ セットには 3 つのクラスターがあります。
クラスタ A には 8 つのポイントがあります
クラスタ B には 5 つのポイントがあります
クラスタ C には 6 つのポイントがあります

n ノードのグラフで各ノード間のハミング距離を計算しようとしています。このグラフの各ノードには同じ長さ (k) のラベルがあり、ラベルに使用されるアルファベットは {0, 1, *} です。「*」はドントケア記号として機能します。たとえば、ラベル 101*01 と 1001*1 の間のハミング距離は 1 です (これらは 3 番目のインデックスでのみ異なると言います)。

私がしなければならないことは、各ノードのハミング距離が 1 のすべての隣接ノードを見つけて、これら 2 つのラベルがどのインデックスで異なるかを正確に報告することです。

次のように、各ノードのラベルを他のすべてのラベルと文字ごとに比較しています。

数百万のノードがあるかもしれません。k は通常 50 前後です。私は Java を使用しています。この比較には n*n*k 時間がかかり、動作も遅くなります。試行と VP ツリーを使用することを検討しましたが、この場合にどのデータ構造が機能するかわかりませんでした。Simmetrics ライブラリも調べましたが、何も頭に浮かびませんでした。提案があれば本当に感謝します。

私はここで読んだ：

検索エンジンは逆索引からの結果をどのようにマージしますか?

「クエリ実行アルゴリズムは実際にはかなり馬鹿げています」

また、検索エンジンで使用されることになっている、ハミング距離を使用する洗練されたアルゴリズムが多数あります。

これらのアルゴリズムは論文で見つけることができます:

MapReduce を介したハミング距離ベースの類似性検索クエリの効率的な処理。HmSearch: 効率的なハミング距離クエリ処理アルゴリズム。マルチインデックス ハッシング: ハミング空間での正確な最近傍検索を高速に行うためのデータ構造。

ハミング空間のアルゴリズムが本当に役に立つかどうか知っている人はいますか?

ハミング距離で比較して取得するハッシュをmysqlに保存しています。

保存されるハッシュは次のとおりです。

私は通常、次のように取得します。

しかし、mysqlのハミング距離は、文字列が数値のみの場合に実行できるビット単位の演算子です。

整数（数値）でのみ機能しますが、私の要件は数字とアルファベットを使用することです。たとえば、次のようになります。

私のちょっとした調査から、最初にフィールドを変換してから、次のようにbinary使用bitcountするCAST必要があることがわかりましたCONVERT。

また

これは、データを に変換しbinaryて使用するので問題ありませんbitcount。varbinaryここで、すでに格納されている文字/ハッシュmysqlが英数字であり、フィールドを変換するvarbinaryとbitcount、格納されたハッシュがバイナリ文字列ではないため機能しないという疑問が生じます。

私は何をすべきか？

私はphpハミング距離マッチングの例として言及していました：

しかし、mysqlで実装できないため、mysqlとfetchとの照合方法がわかりません。

groupごとに不一致のケースをどのように計算できるか疑問に思っていました。

これが私のデータであると想像してみましょう:

データはこんな感じ

のようなものを得るために

stringdistライブラリを使用してこれを計算することは素晴らしいことです。

何かのようなもの

しかし、それは機能していません。

何か案は ？

クイック更新: 重みの問題をどのように解決しますか? たとえば、2 つの文字の不一致を設定するときに、引数 (値 (1,2,3, ...)) を渡すにはどうすればよいでしょうか。同様に、b と cの間のミスマッチは2のコストがかかり、a とcの間のミスマッチは1などのコストがかかります。