12

N 個の固定長文字列を持つデータベースがあります。同じ長さのクエリ文字列があります。問題は、q までのハミング距離が最も小さい最初の k 個の文字列をデータベースから取得することです。

N は小さく (約 400)、文字列は長く、長さは固定されています。データベースは変更されないため、インデックスを事前に計算できます。クエリは大きく異なります。キャッシングや事前計算はオプションではありません。毎秒たくさんあります。k-1 の結果が 0 に一致する場合でも、常に k の結果が必要です (ハミング距離でソートし、最初の k を取得するため、局所性に依存するハッシュや同様のアプローチでは実行できません)。kd-tree および同様のスペース分割は、おそらく線形検索よりもパフォーマンスが低下します (文字列は非常に長くなる可能性があります)。BK-tree が現時点では最良の選択ですが、必要以上に遅く複雑です。

実際のハミング距離を計算するために k <= t << N エントリを残して、ほとんどのエントリを非常に少ないステップで破棄するインデックスを構築するアルゴリズムがあるように感じます。

レーベンスタイン距離に基づくファジー文字列マッチングを提案する人々 - ありがとう、しかし問題ははるかに単純です。一般化された距離メトリック ベースのアプローチ (BK ツリーなど) は優れていますが、上記の事実を利用するものがあるかもしれません (小さな DB/長い固定サイズの文字列、単純なハミング距離)

リンク、キーワード、論文、アイデア？=)

4

4 に答える 4

11

これは、 Vantage Point (VP ツリー)が機能するタスクのように思えます...ハミング距離は三角形の不等式定理を満たす必要があるため、それを適用できるはずです... k-closest を特定するのにも適しています。画像索引データベースのセットアップで見たことがあります...この論文のセクション 5 を、私が話していることの例として確認してください (別の分野ではありますが)。

于 2010-06-23T01:01:13.703 に答える
4

すべてのハミング距離は、以下の Python コードを使用して O(K^2/D) で生成できます。
これは、場合によっては、O(N*K) である簡単なコードよりも高速です。

ここで、N は固定長文字列の数、
K は各文字列の長さ
、D は辞書のサイズです。 

# DATABASE is a tuple of the strings
# eg. ('asdfjjajwi...', 'hsjsiei...', ...)

# SINGLE is the string you are matching
# eg. 'jfjdkaks...'

SIZE_OF_STRING = 5000
NUMBER_OF_STRINGS = 400
FIRST_K_REQUIRED = 100

def setup_index():
  index = []
  for x in xrange(SIZE_OF_STRING):
    index_dict = {}
    for y in xrange(NUMBER_OF_STRINGS):
      temp = index_dict.get(DATABASE[y][x], [])
      temp.append(y)
      index_dict[DATABASE[y][x]] = temp
    index.append(index_dict)
  return index

index = setup_index()

output = []
for x in xrange(NUMBER_OF_STRINGS):
  output.append([SIZE_OF_STRING, x])

for key, c in enumerate(SINGLE):
  for x in index[key][c]:
    output[x][0] -= 1

output.sort()
print output[:FIRST_K_REQUIRED]

これは、SIZE_OF_STRING / DICTIONARY_SIZE < NUMBER_OF_STRINGS の場合にのみ高速な方法です。

お役に立てれば。

編集: 上記のコードの複雑さは正しくありません。

ハミング距離は、平均で O(N*K/D) で生成できます。これは、O(N*K) である単純なコードよりもすべてのケースで
高速です。

ここで、N は固定長文字列の数、
K は各文字列の長さ
、D は辞書のサイズです。

于 2010-12-30T13:41:51.153 に答える
1

私の理解では、BK ツリーは、クエリ文字列から最大で K 個の「差」のすべての文字列を見つけるのに最適です。これは、X 個の最も近い要素を見つけることとは別の問題です。これがおそらくパフォーマンスの問題の原因です。

私の最初の傾向は、速度が本当に重要である場合、最終的な目標は、この問題を処理する決定論的有限オートマトン(DFA) を構築することであるべきだということです。Donald Knuth は関連する問題に取り組み、DFA をシミュレートするTrieと呼ばれる方法を開発しました。この方法は、最初の辞書に検索対象となる可能性のある単語が多数ある場合に特に便利です。あなたの問題は、この作品の興味深い拡張になると思います。彼の最初の仕事では、DFA の目標は、入力文字列を辞書内の単語と一致させようとすることでした。この問題についても同じことができると思いますが、代わりに、クエリに最も近い K 個のアイテムを返します。本質的に、私たちは受容状態の定義を拡張しています。

これが実用的かどうかは、含める必要がある受け入れ状態の数によって異なります。重要なアイデアは、互換性のあるセットのアイデアだと思います。たとえば、数直線上に要素 1、2、3、4、5 があり、任意のクエリで最も近い 2 つの要素が必要であると想像してください。要素 2 は 2 つの可能なセット (1,2) または (2,3) に含まれる可能性がありますが、2 が 4 または 5 のセットになることは決してありません。一瞬。答えにはまともな論文があるようです。

于 2010-12-31T08:35:40.773 に答える
0

この問題は、非常に最適な特別なソリューションがいくつかある Knuth の「トライ」アルゴリズムに強く関連しているように見えます。これには、主にキャッシュ コヒーレンスと CPU 命令による高速化 (ビット単位のトライ) が関係しています。

トライは、関連する問題 (文字列の開始点の類似性) に対する優れたソリューションです。これはもちろん、文字列の原点から始まる任意の点から最小の一意の文字列ソリューションのセットを見つけるための完璧なソリューションになります。この場合のビット単位のトライは、実際には O(1) の平均パフォーマンスを持ち、最悪の場合は O(m) (M はキーの長さ) です。検索、挿入、および削除の全体的なパフォーマンスは、純粋なハッシュ配列の衝突の問題がないことを除いて、ハッシュと同じです。

ビットごとの試行に関する情報を検索していて、特定のハミング アルゴリズムとの類似性に気付いたので、この質問に出くわしました。おそらく、このクラスのアルゴリズムは、あなたにとって有益な研究分野になるでしょう。幸運を。

于 2012-02-08T16:28:44.267 に答える