問題タブ [hamming-distance]

2 つの 2 桁の符号なし整数を比較する新しいプログラムを作成します。ハミング距離で比較します。しかし、私のアルゴリズムは完全には機能しません。このコードの何が問題なのか教えてもらえますか :( どうもありがとうございました!!

これが私の数え方です。

a および b 8 ビット バイナリ。

出力をお見せしましょう。

例: 文字列 "asdf" と一連の文字列 ("qwer"、"aswr"、"asdv") があるとします。「asdv」と「asdf」のハミング距離は 1 であるため、セットと文字列の間のハミング距離は 1 になります。

このようなものでブルートフォースするのは簡単です

これには O(n*k) があり、n = len(string) および k = len(set) であると思います。ただし、最大セット サイズは n^2 に比例します。これは、基本的に O(n^3) を扱っていることを意味します。セットはかなり静的なので、前処理が役立つ場合は間違いなくオプションです。

最後に、ここでのアプリケーションは、問題の文字列に最も近いセットを特定することですが、文字列の長さはセットの数よりもはるかに制限的な要因であるため、問題を軽減しました. 個々のサブセットではなく空間全体を見ることによってこれにアプローチする別の方法がある場合、私はすべての耳になります. 私が最初にそのアプローチを採用したときは、スペースの複雑さが完全にばかげているように見えました.

「template_phash」列を持つテーブル A があります。400K の画像から生成された phash を保存します。

次に、ランダムな画像を取得し、その画像から phash を生成します。

テーブル A から、ハミング距離の差がしきい値 (たとえば 20) 未満のレコードを取得できるようにクエリを実行するにはどうすればよいでしょうか。

SQL のバイナリ文字列のハミング距離を見たことがありますが、理解できませんでした。

これを達成するには関数を作成する必要があることがわかったと思いますが、どうすればよいですか?

私のphashは両方ともBigIntにあります。例：7641692061273169067

次のようにクエリできるように関数を作成するのを手伝ってください

2 つのバイナリ文字列のハミング距離が異なるビットの数であることは誰もが知っています。一方、1110 と 1101 の 2 つのバイナリ文字列の場合、それらの類似性を最上位ビットから同じビットの数で説明したい場合。(この例では、左から右に、2 つのビットが異なるまでビットをカウントし、結果は 2 になります。) この種の類似性は定義されているか、正式な名前がありますか?

この C# 関数を T-SQL UDF に変換する必要があります

ハミング距離が x より小さいデータベースからすべての行を取得する必要があります。この関数はソリューションの一部にすぎません。

csharp 関数はこれら 2 つのハッシュに対して 40 を返し、t-sql 関数は 52 を返します。

14714557628763197901

15383788748848265778

サンプルはありますが、同じ結果が得られません。

どんな助けでも大歓迎です

バイナリ コードの文字列と数値を受け取り、元の文字列のハミング距離内にあるすべての文字列を出力するプログラムを作成することになっています。私はすべてを行う関数を持っていますが、出力にはリスト内のリストがあります。これがなぜなのか理解しています - 関数は再帰的であり、可能な値のリストを返すことがあります。

問題は、完全な文字列を出力するように変更する方法がわからないことです。たとえば、文字列が "0000" でハミング距離が "2" の場合、["1['100', '010', '001']", "01['10', '01']" となります。 , "001['1']"]

しかし、私が欲しいのは:

コードは以下のとおりです。

ハミング距離:

たとえば、2 つの 2 進数: 1011 と 1000 の HD (ハミング距離) は 2 です。

10000 と 01111 の HD は 5 です。

コードは次のとおりです。

誰かが私にそれを説明できますか？

ありがとう！

さまざまなアルゴリズムを調査してきましたが、探しているものを正確に見つけられませんでした。

ハミング距離 (同じ長さの文字列にのみ有効) レーベンスタイン距離 (kitten や sitten などの類似語を検索)

私が探しているのは、同じ考えに関する文章を見つけるものです。

例えば：

私が探しているのは

sentence 1 and 2トピックについてですが、そうではありません sentence 3 or 4。

文中の各単語を比較してみることができると思いますか?

私を正しい方向に向けることができる人なら誰でも大歓迎です。