文字列とセットA文字列の間の最小ハミング距離の計算

Question

ex： 文字列 "asdf"と文字列のセット（ "qwer"、 "aswr"、 "asdv"）がある場合。セットと文字列との間のハミング距離は、「ASDV」、「ASDF」として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

.

n= len（文字列）とk= len（set）であるO（n * k）があると思います。ただし、最大設定サイズはN ^ 2でスケールスケールです。これは、本質的にO（n ^ 3）を扱っています。前処理が確実にオプションである場合は、かなり静的なセットです。

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

Answer 1

まず、文字列間のハミング距離はメトリックです。したがって、あなたはk最近隣人をメートルメート空間に見つけようとしています（ここで、k= 1）

その結果、Mツリーデータ構造と同様のツリーを検討することができます。（ real="nofollow">を参照してください。 http://en.wikipedia.org/wiki/m-tree と http. //www.vldb.org/conf/1997/p426.pdf ）。このツリーは、「最近傍」を見つけるために実行される必要がある数の距離比較を減らすように設計されています。

個人的には、私が満足していたM-Tree Onlineの実装を見つけることができませんでした（私の熟年のMツリーの実装を探している私の閉じたスレッドを見てください）ので、私は自分のものを転がしました。

私の実装はここにあります： https://github.com/jon1van/mtreemaprepo

私が見つけることができる唯一の他の実装はこれでした： https://github.com/erdavila/m -tree この実装がなくなりました（そして他のいくつかの問題）（しかしそれはそれほど無料でしたが、それは良いこと）なので、この実装が好きではなかった。

Levensthtein距離メトリック（ http://en.wikipedia.org/wiki/levenshtein_distance ）完全に実装されたLevenshteinの距離メトリックを見つけるのは、かなり簡単であるべきです

追加Levenstein距離関数** http://code.google.com/p/google-refine.com/source/browse/trunk/src/main/java/edu/mit/simile/vicino/distances/levensteIndistance.java？= 181