編輯字符串距編輯距離最短的字符串

Question

假設我有一個字符串列表，它們是相似的。我想弄清楚所有這些字符串的共同部分或特徵。是否有一種已知的方法可以找出與給定集合中所有字符串最相似的字符串，並且不屬於該集合？

例如，如果我有以下組：

Hello 
Hell 
Help 
Hepl 

'赫爾' 給出的一個2,1,1,1 Levenshtein距離。目前我正在考慮以不同的子字符串爲基礎，並計算距離（我的集合相當小，所以粗暴的強制不會成爲問題），但是這種解決方案並沒有發現字符串，它本質上不是任何給定字符串的子字符串集合，但可能是最優的解決方案（例如解決方案是兩個子串共軛的情況）。

任何與此有關的線索將不勝感激。

Answer 1

你說蠻力是可以接受的:-)。經典的方法是廣度優先搜索。對於列表中的每個字符串，您都會生成編輯距離爲1的所有字符串，從那些距離爲2的字符串等等。對於每個給定的字符串，你會得到一個變異字符串樹。在每一輪（距離）之後，檢查每棵樹是否有一個共同的字符串。

僞代碼爲Levenshtein距離：

alphabet = "abcd..." 
starters = "Hello", "Hell", "Help", "Hepl" 
relatives = set() 
distance = 0 
for word in starters 
    trees[word][distance] = word 

while len(relatives) == 0 
    distance++ 
    for tree in trees 
     for word in tree[distance-1] 
      for pos in range(len(word)) 
       new_word = word.erase(pos) 
       if new_word not in tree 
        tree[distance].insert(new_word) 
        dict[new_word] += 1 
        if dict[new_word] == len(starters) 
         relatives.insert(new_word) 
      for pos in range(len(word)) 
       for letter in alphabet 
        new_word = word.replace(pos, letter) 
        if new_word not in tree: 
         tree[distance].insert(new_word) 
         dict[new_word] += 1 
         if dict[new_word] == len(starters) 
          relatives.insert(new_word) 
      for pos in range(len(word) + 1): 
       for letter in alphabet 
        new_word = word.insert(pos, letter) 
        if new_word not in tree 
         tree[distance].insert(new_word) 
         dict[new_word] += 1 
         if dict[new_word] == len(starters) 
          relatives.insert(new_word) 
print relatives