文字列のセットとの編集距離が最も短い最短文字列

Question

類似した文字列のリストがあるとします。これらすべての文字列の共通部分または特徴を理解したいと思います。与えられたセット内のすべての文字列に最もよく似た文字列を見つけ出す既知の方法はありますか？そのセットに属していませんか？例えば

、私は次のように設定した場合：

Hello 
Hell 
Help 
Hepl 

を 'ヘル' は2,1,1,1のレーベンシュタイン距離を提供します。現在、私は基底として異なる部分文字列を取って、距離を計算することを考えています（私の集合はかなり小さいので、ブルートフォースは問題にならないでしょう）が、この解決法は文字列の本質的に部分文字列ではない最も最適な解（解が2つの部分文字列の共役のような場合）かもしれません。

この点についてご迷惑をお掛けしたいと思います。

Answer 1

あなたはブルートフォースが許容できると言った:-)。古典的なアプローチは、幅広い最初の検索です。あなたのリストの各文字列に対して、編集距離が1であるすべての文字列を生成します。それらの文字列からは、すべての距離2の文字列などを生成します。与えられた文字列ごとに、突然変異した文字列のツリーが得られます。毎回のラウンド（距離）の後、すべてのツリーに共通の文字列があるかどうかをチェックします。

レーベンシュタイン距離のための擬似コード：

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