Levenshtein Entfernung für eine Liste

Question

Ich möchte meine Wortliste in einige Cluster unterteilen mit Levenshtein Distance.

Aber als ich Schleife über Liste laufen einige Cluster wiederholt werden. Bitte helfen Sie mir, dieses Problem zu sortieren

Answer 1

Wenn Sie nur Zeichenfolgen haben, warum nicht ein Set verwenden?

Target = set(Target_Column.tolist()) 

---

Sie können auch einen Standardwert eines Satzes für die Zuordnung verwenden:

clusters = defaultdict(set) 

Aber dies erfordert list.append-set.add in der Schleife zu ändern.

---

Es gibt jedoch eine pythischere Alternative zu Ihrem Code.

Ich würde wahrscheinlich eine Zuordnung von Wörtern zum Satz ihrer Verbindungen im laufenden Betrieb generieren.

Hier ist ein Beispiel unter der Annahme, words ein set aller Worte ist:

clusters = {w1: set(w2 for w2 in words if distance(w1, w2) <= threshold) for w1 in words} 

anschauliches Beispiel:

>>> distance = lambda x, y: abs(len(x) - len(y)) 
>>> words = set("abc def abcd abcdefghijk abcdefghijklmnopqrstuv".split()) 
>>> threshold = 3 
>>> for cluster, values in clusters.items(): 
...  print cluster, ": ", ", ".join(values) 
... 
abcd : abcd, abc, def 
abc : abcd, abc, def 
abcdefghijk : abcdefghijk 
abcdefghijklmnopqrstuv : abcdefghijklmnopqrstuv 
def : abcd, abc, def 

Steigende Schwelle bekommen wir einen großen "Cluster" für alle Worte:

>>> threshold = 100 
>>> clusters = {w1: set(w2 for w2 in words if distance(w1, w2) <= threshold) for w1 in words} 
>>> for cluster, values in clusters.items(): 
...  print cluster, ": ", ", ".join(values) 
... 
abcd : abcd, abc, abcdefghijk, abcdefghijklmnopqrstuv, def 
abc : abcd, abc, abcdefghijk, abcdefghijklmnopqrstuv, def 
abcdefghijk : abcd, abc, abcdefghijk, abcdefghijklmnopqrstuv, def 
abcdefghijklmnopqrstuv : abcd, abc, abcdefghijk, abcdefghijklmnopqrstuv, def 
def : abcd, abc, abcdefghijk, abcdefghijklmnopqrstuv, def