3

ここで定義されているバイナリ文字列は、固定サイズのビットの「配列」です。それらには順序がないため（数字としてソート/インデックス付けすることは意味がありません）、各ビットは他のビットから独立しているため、文字列と呼びます。このような文字列はそれぞれ N ビットの長さで、N は数百にのぼります。

これらの文字列を保存し、ハミング距離を距離メトリックとして使用して、最近傍の新しいバイナリ文字列クエリを指定する必要があります。
メトリック ベースの検索 (VP ツリー、カバー ツリー、M ツリー) 用の特殊なデータ構造 (メトリック ツリー) がありますが、通常のデータベース (私の場合は MongoDB) を使用する必要があります。

1 対 1 のハミング距離一致を実行する前に、DB がレコードのサブセットのみにアクセスできるようにするバイナリ文字列に適用できるインデックス作成機能はありますか? あるいは、標準の DB でそのようなハミング ベースの検索を実装するにはどうすればよいでしょうか?

4

2 に答える 2

4

ハミング距離は計量であるため、三角不等式を満たします。データベース内のビット文字列ごとに、事前定義された定数ビット文字列へのハミング距離を格納できます。次に、三角形の不等式を使用して、データベース内のビット文字列を除外できます。

だから言ってみましょう

C <- some constant bitstring
S <- bitstring you're trying to find the best match for
B <- a bitstring in the database
distS <- hamming_dist(S,C)
distB <- hamming_dist(B,C)

したがって、それぞれについてB、対応する を格納しますdistB。

の下限hamming(B,S)は になりますabs(distB-distS)。上限は になりますdistB+distS。

B下限が上限の下限よりも高くなるようなものはすべて破棄できます。

どのC. ビット文字列のメトリック空間の「中心」に近いビット文字列にしたいと思うでしょう。

于 2011-07-06T15:58:25.327 に答える
2

ビット文字列に適用されるlevenshtein automataに似たアプローチを使用できます。

  1. ハミング距離の基準を満たす最初の (辞書編集的に最小の) ビット文字列を計算します。
  2. その値以上の最初の結果をデータベースから取得します
  3. 値が一致した場合、それを出力し、次の結果をフェッチします。それ以外の場合は、それよりも大きい次の一致する値を計算し、2 に進みます。

これは、可能なすべての一致を生成することなく、データベースと可能な一致のリストに対してマージ結合を実行することと同じです。検索スペースは減りますが、それでもかなりの数のクエリが必要になる可能性があります。

于 2011-07-07T00:55:34.753 に答える