Python - Collapse文字列グループ

Question

私は文字列のリストを持っています。 ['Apple', 'Appl','Elephnt', 'Elephant']。この文字列のリストを異なるグループ、つまり['Apple', 'Elephnt']に折りたたむ必要があります。

同じグループに属している必要がある文字列の基準は、一致率が80％を超えることに基づいています。 AppleとApplは88％のマッチを共有し、ElephntとElephantは93％のマッチを共有します。

def similar(a, b): 
    return SequenceMatcher(None, a, b).ratio() 

機能similarは、2つの文字列の一致率を計算するために使用されます。 上記の関数を使用してこの折り畳みのグループ分けを計算するにはどうすればよいですか？

Answer 1

あなたは、グループのリストに類似した文字列の各文字列（名前）のあなたの最初のリストを分割したい場合：たとえば

from difflib import SequenceMatcher 
from functools import partial 

def is_similar(a, b): 
    return SequenceMatcher(None, a, b).ratio() > 0.8 

def similar_groups(names): 
    remaining = set(names) 
    groups = [] 
    while remaining: 
     ref = remaining.pop() 
     group = [ref] + filter(partial(is_similar, ref), remaining) 
     groups.append(group) 
     remaining -= set(group) 
    return groups 

を：

>>> similar_groups(['Apple', 'Appl','Elephnt', 'Elephant']) 
[['Elephant', 'Elephnt'], ['Appl', 'Apple']] 

Answer 2

これはあなたが欲しいと思うようです。その主な問題は、類似しない文字列の大きなリストに対して2次の順序があることです。 「類似」は等価に近いが、全く同じではない（例えば、推移的ではない）とすれば、アルゴリズムの順序を減らす方法は見当たらない。たとえば、itertoolのgroupby関数を使用できるように項目を並べ替える方法はわかりません。

主な考え方は、以前の文字列のいずれにも似ていない場合は、結果リストに文字列を追加することです。所望に応じて

from difflib import SequenceMatcher 

def similar(a, b): 
    return SequenceMatcher(None, a, b).ratio() 

def collapse_similar(strlist): 
    """Eliminate "duplicate" strings in a list, where "duplicate" means 
    similar() is more than 80%. 
    """ 
    result = [] 
    for s in strlist: 
     if all(similar(s, v) <= 0.8 for v in result): 
      result.append(s) 
    return result 

collapse_similar(['Apple', 'Appl','Elephnt', 'Elephant'])の結果は、['Apple', 'Elephnt']あります。

Answer 3

はまあがたくさんありますこれを行う方法。ここに例があります

from difflib import SequenceMatcher 
from itertools import combinations 
a_list = ['Apple', 'Appl','Elephnt', 'Elephant'] 

def similar(a, b): 
    return SequenceMatcher(None, a, b).ratio() > 0.8 

print [a for (a, b) in combinations(a_list, 2) if similar(a,b)]