計算單詞列表中的反向漢明距離

Question

我想查找單詞列表中每個單詞中同一位置上相同字符的編號。因此，例如，最終的結果將是相比，在列表中的其他詞詞的矩陣顯示了兩個像這樣間反漢明距離：

鑑於hamm_dist(a,b) = hamm_dist(b,a)我才真正需要計算到的權對角線。有沒有更有效的方法來找到這些值，而不僅僅是一堆調用來計算任何兩個值之間的距離？

Answer 1

如果我們談論填充這樣一個矩陣的複雜性，顯然你不能做得比O(n^2)更好，其中n是單詞的數量。至少不是在最壞的情況下。

但是，這裏有另一種解決方案，比您建議的解決方案需要更少的char-to-char比較。

您爲每個單詞指定一個索引，從而創建形式爲(<index>, <word>)的元組。也讓L是您輸入中單詞的最大長度，並且M是您的輸出矩陣。

set all elements in M to 0 
for i = 1 to L do 
    sort the tuples using the ith character of the words as key 
    for every pair w1 w2 of words having the same ith letter do 
     M[w1,w2]++ 
    endfor 
endfor 

換言之，對於每個索引位置時，利用在該位置作爲鍵的字符排序的話，增加計數器對於具有在該位置的相同值的所有字對。因爲我認爲你的字母不是很寬，你可以使用計數排序。事實上，你並不需要排序，而是將每個單詞（實際上是指定給該單詞的索引）放在相應的存儲區（字母表中每個可能字母的一個存儲區）。

複雜明智的，這種解決方案需要O(L*n)字符到字符「比較」和O(S)增加接一個操作，其中S是所有的漢明距離的總和。您的解決方案似乎需要O(L*n^2) char-to-char比較和O(S)逐個操作。我的「比較」並不是實際的比較，而只是對一個詞中第i個位置的詢問。