1

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

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

def hamming_distance(string, set):
    min = len(string)
    for element in set:
        element_distance = sum(ch1 != ch2 for ch1, ch2 in zip(string, element))
        if min > element_distance:
            min = element_distance
        if min == 0:
            break
    return min

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

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

4

1 に答える 1

1

まず、文字列間のハミング距離がメトリックです。したがって、距離空間 (k = 1) で k 最近傍を見つけようとしています。

したがって、M-Tree データ構造に似たツリーを検討することをお勧めします ( http://en.wikipedia.org/wiki/M-treeおよびhttp://www.vldb.org/conf/1997/を参照)。 P426.PDF）。このツリーは、「最近傍」を見つけるために実行する必要がある距離比較の数を減らすように設計されています。

個人的には、私が満足できる M-Tree の実装をオンラインで見つけることができなかったので (成熟した M-Tree の実装を探している私の閉じたスレッドを参照してください)、自分で作成しました。

私の実装はこちらです: https://github.com/jon1van/MTreeMapRepo

私が見つけることができた唯一の他の実装はこれでした: https://github.com/erdavila/M-Tree 私はこの実装が好きではありませんでした. 。それは良い）。

レーベンシュタイン距離メトリック ( http://en.wikipedia.org/wiki/Levenshtein_distance )で私のコード (一般的なメトリック空間で kNN 検索を解決する) を使用することを検討してください。完全に実装されたレーベンシュタイン距離メトリックをオンラインで見つけるのは非常に簡単です

レーベンスタイン距離関数を追加 ** http://code.google.com/p/google-refine/source/browse/trunk/src/main/java/edu/mit/simile/vicino/distances/LevensteinDistance.java?r= 181

于 2014-01-09T17:35:47.567 に答える