計算字符串和字符串之間的最小漢明距離

Question

例如： 如果我有字符串「asdf」和字符串集（「qwer」，「aswr」，「asdv」）。集合和字符串之間的漢明距離爲1，因爲「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 

我覺得這爲O（n * K），其中n = LEN（字符串）和k = LEN（套）。然而，最大集大小與n^2成比例，這意味着我們基本上處理O（n^3）。該集相當靜態，所以如果預處理將有助於這絕對是一種選擇。

最後，我應該提及的是，這裏的應用程序是要確定哪個集合最接近問題的字符串，但我減少了這個問題，因爲字符串長度是一個更多的限制因素集。如果還有另外一種方法來看待整個空間而不是單個子集，我會全神貫注。當我第一次採取這種方法時，似乎空間複雜性將會變得完全荒謬。

Answer 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我不喜歡這個實現，因爲它沒有刪除功能（以及其他一些問題），（但它是免費的，所以...那很好）。

您可能想要考慮使用我的代碼（它解決了通用度量空間中的kNN搜索）和Levensthtein距離度量（http://en.wikipedia.org/wiki/Levenshtein_distance）。找到一個完全實現Levenshtein距離度量在線應該是很容易

添加編輯距離函數** http://code.google.com/p/google-refine/source/browse/trunk/src/main/java/edu/mit/simile/vicino/distances/LevensteinDistance.java?r=181