問題タブ [hamming-distance]

とても簡単な質問があります。

私は 8 パズル (8 つの数字 (1 から 8) + 空白 (=0) ) に取り組んでいます。

ハミング距離 (間違った位置にある数字) とマンハッタン距離 (開始位置と最終位置の間の水平方向と垂直方向の距離) を計算するとき、結果を計算するために「空白」スペースを考慮する必要がありますか?

例えば..

ゴール状態で

何が正しいですか？

• ハミング距離 = 8 (配置されていないすべての数字) または 9 (0 = 空白も考慮される)
• マンハッタン距離 (距離(7)、距離(2)、距離(4)、...) = 3 (=1+2) + 1 (=1+0) + 2 (1+1) + 2 (2+ 0) + 0 (空白) + 3 (1+2) + 2 (2+0) + 3 (1+2) + 3 (2+1) --> 空白を考慮しない場合は 18 、空白あり (+2)は 20 です。何が正しいですか。

ありがとうございました

v と w のハミング距離は 2 ですが、パリティ ビットがないと 1 になります。

Visual Studio 2010C++に実装しています

2つのバイナリ配列があります。例えば、

との間のハミング距離を計算するには、との結果を格納 します。array1array2array3[100]xorarray1array2

1次に、のビット数を数える必要がありますarray3。これを行うために、私は__popcnt命令を使用できることを知っています。

今のところ、私は以下のようなことをしています：

良い結果を示していますが、遅いです。どうすれば速くできますか？

質問があります: 次のコードのハミング距離を見つけてください:

答えは 2 です。これはどのように機能しますか? ハミング距離は2本の弦の間だけだと思っていましたか？

次のパズルのハミング距離を計算する方法：

私が理解している限り、次の2つのシーケンスを比較する必要があります。

それとも簡単ではありませんか？

MySQL データベース (phpMyAdmin で使用) でハミング距離を使用したいのですが、ここで指定されたコードで関数を作成できませんでした。

私はこのコードを参照しています：

問題は、私が「超特権」を持っていないことです。また、このコードを間に入れてみDELIMITER //ました（レーベンシュタイン距離関数で機能しました。以下を参照）が、それでも問題は解決しませんでした-タイムアウトが発生します：

/usr/share/phpmyadmin/libraries/import/sql.php132行目で最大実行時間の300秒を超えました

とにかく、私はMySQLにまったく慣れていないので、誰かがMySQLでハミング関数を作成するのを手伝ってくれるかどうか疑問に思っています。

ところで、私はレーベンシュタイン距離関数も使用しており、この関数の作成はうまくいきました。しかし、2 つの文字列間の距離と数値データのハミング距離の計算には、むしろレーベンシュタイン距離を使用する必要があることがわかりました。

ありがとう。

MySQLデータベースでpHashされた類似画像の検索を改善しようとしています。今、私はこのようにハミング距離を数える pHash を比較します:

選択結果(エンジン MyISAM)

• 20000行; クエリ時間 < 20ms
• 100000行; クエリ時間 ~ 60ms # 150000 行に達するまではこれで問題ありませんでした
• 300000行; クエリ時間 ~ 150ms

したがって、クエリ時間の増加は、テーブルの行数に依存します。

また、SQL のバイナリ文字列に対するスタックオーバーフロー ハミング距離で見つかったソリューションを試し ます

行 300000 ; クエリ時間 ~ 240ms

データベースエンジンをPostgreSQLに変更しました。この MySQL クエリを PyGreSQL に変換して も成功しません。行 300000 ; クエリ時間 ~ 18 秒

上記のクエリを最適化するソリューションはありますか? 行数に依存しない最適化を意味します。

この問題を解決する方法 (ツール) は限られています。これまでのところ、MySQL が最も単純なソリューションのように見えましたが、専用マシン上の Ruby で動作するすべてのオープン ソース データベース エンジンにコードをデプロイできます。MsSQL https://stackoverflow.com/a/5930944/766217 (テストされていません) の準備ができているソリューションがいくつかあります。誰かが MySQL または PostgreSQL 用に翻訳する方法を知っているかもしれません。

いくつかのコードまたは観察に基づいて回答を投稿してください。stackoverflow.com には、ハミング距離に関する多くの理論的な問題があります。

ありがとう！

ハミング距離を使用してバイナリデータをクラスター化する方法をテストしたかったので、上記のコードでは、Xにバイナリ値の行列をランダムに割り当てました。ただし、問題は、重心が10進値であるということです。以下に示すように。

なぜ答えに0.5があるのですか？図心もバイナリにしたいです。また、バイナリデータのためにオーバーラップなしでクラスターをプロットすることは可能ですか？

同じ長さの 2 つの文字列が何文字異なるかを調べたいと思います。xoring アルゴリズムが最も高速であると考えられていることがわかりましたが、それらはビットで表された距離を返します。結果を文字で表現したい。"pet" と "pit" の距離は 1 文字で表現されているが、'e' と 'i' は 2 つの異なるビットを持つ可能性があるため、xoring は 2 を返すとします。

私が書いた関数は次のとおりです。

それはもっと速くなるでしょうか？低レベルのコマンドを使用したり、別のアルゴリズムを実装したりするのでしょうか?

システム: Intel Xeon X5650 上の Gcc 4.7.2

ありがとうございました

私はプロジェクトとして私たちから要求された 8 パズル ソルバー -ベスト ファースト サーチ + ハミング距離(タイルの位置ずれ) ヒューリスティックを使用する - に取り組んでいます。

最初に、ヘッダー ファイルで次のように分離された cpp ファイルでStat Struct を定義しました。

次は main.cpp ファイルです:

次のようなサンプル入力を使用してプログラムを実行すると、次のようになります。

それはパズルを解決し、すべてが良いです.しかし、他のすべての入力を試してみると、それらのパズルの解決策があるという事実にもかかわらず、目標に到達する前にオープンセットが空になりました.

編集: オープン セットに入った統計を確認しようとしましたが、そうではなかったので、以下の入力をサンプルとして使用し、得たもの:

オープンに入力された統計:

パズルを解くために必要な手順はどれですか。

クローズドで見つからず、オープンにならなかった統計:

したがって、Open セットは、上記の統計が Open に存在し、それらの入力を拒否すると述べていますが、Open にはそのような統計はなく、それらの状態のヒューリスティック値は Open(4,4,5,5,5,5) で異なります。その他(6,6,5,7)。

オープンがそれらの統計を既に存在するかのように入力することを拒否する理由を誰か教えてください. 前もって感謝します。