String Ähnlichkeit Metriken in Python

StackOverflow https://stackoverflow.com/questions/1471153

Frage

Ich möchte Zeichenfolge Ähnlichkeit zwischen zwei Zeichenketten zu finden. Diese Seite Beispiele für einige von ihnen hat. Python hat eine implemnetation von Levenshtein Algorithmus . Gibt es einen besseren Algorithmus (und hoffentlich eine Python-Bibliothek), unter diesem contraints.

  1. Ich möchte Fuzzy-Matches zwischen Strings zu tun. zB entspricht ( 'Hallo, ihr alle', 'hallo, alles, was Sie peopl') sollte return true
  2. False Negative sind akzeptabel, Falsch positive Ergebnisse, außer in extrem seltenen Fällen sind es nicht.
  3. Dies wird in einer nicht Echtzeit-Einstellung vorgenommen, so Geschwindigkeit ist nicht (viel) zur Sorge.
  4. [Bearbeiten] Ich Mehrwortketten bin im Vergleich.

Würde etwas anderes als Levenshtein Abstand (oder Levenshtein-Verhältnis) einen besseren Algorithmus für meinen Fall sein?

War es hilfreich?

Lösung

Es gibt eine große Ressource für Zeichenfolge Ähnlichkeit Metriken an der University of Sheffield. Es verfügt über eine Liste von verschiedenen Metriken (darüber hinaus nur Levenshtein) und hat Open-Source-Implementierungen von ihnen. Sieht aus wie viele von ihnen leicht fallen sollte in Python anzupassen.

http //web.archive.org/web/20081224234350/http: //www.dcs.shef.ac.uk/~sam/stringmetrics.html

Hier ist ein bisschen der Liste:

  • Hamming-Distanz
  • Levenshtein Abstand
  • Needleman-Wunch Abstand oder Sellers Algorithmus
  • und viele mehr ...

Andere Tipps

Ich weiß, es ist nicht das gleiche, aber das ist nah genug: 

>>> import difflib
>>> a = 'Hello, All you people'
>>> b = 'hello, all You peopl'
>>> seq=difflib.SequenceMatcher(a=a.lower(), b=b.lower())
>>> seq.ratio()
0.97560975609756095

Sie können als Funktion machen dieses 

def similar(seq1, seq2):
    return difflib.SequenceMatcher(a=seq1.lower(), b=seq2.lower()).ratio() > 0.9

>>> similar(a, b)
True
>>> similar('Hello, world', 'Hi, world')
False

Dieser Code-Schnipsel die difflib, Levenshtein, Sørensen und Jaccard Ähnlichkeitswerte für zwei Strings berechnen. Im Snippet unten wurde iterieren ich eine tsv, in dem die Saiten von Interesse besetzten Spalten [3] und [4] des tsv. (pip install python-Levenshtein und pip install distance): 

import codecs, difflib, Levenshtein, distance

with codecs.open("titles.tsv","r","utf-8") as f:
    title_list = f.read().split("\n")[:-1]

    for row in title_list:

        sr      = row.lower().split("\t")

        diffl   = difflib.SequenceMatcher(None, sr[3], sr[4]).ratio()
        lev     = Levenshtein.ratio(sr[3], sr[4]) 
        sor     = 1 - distance.sorensen(sr[3], sr[4])
        jac     = 1 - distance.jaccard(sr[3], sr[4])

        print diffl, lev, sor, jac

würde ich Levenshtein Abstand verwenden, oder die sogenannte Damerau Entfernung statt der difflib Sachen aus zwei Gründen (1) „schnell genug“ (dynamische Programmierung algo) und „whoooosh“ (bit- (die Transpositionen berücksichtigt) bashing) C-Code verfügbar ist, und (2) gut verstandenes Verhalten zB Levenshtein der Ungleichung Dreiecks und kann somit in verwendet werden, z.B. ein Burkhard-Keller Baum.

Threshold: Sie sollten als "positiv" behandeln nur jene Fälle, in denen Entfernung <(1 - X) * max (len (string1), len (string2)) und X (die Ähnlichkeitsfaktor) einstellen, sich anzupassen. Eine Möglichkeit, X die Wahl ist eine Probe der Spiele erhalten, berechnet X für jeden, ignorieren Fälle, in denen X

N. B. Ihr Affe / Apfel Beispiel hat Abstand 2, so X 0.6 ist ... Ich würde nur eine Schwelle so niedrig wie 0,75 verwenden, wenn ich verzweifelt nach etwas gesucht und hatte eine hohe falsch-negative Strafe

Ist das, was Sie? 

>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
['apple', 'ape']
>>> import keyword
>>> get_close_matches('wheel', keyword.kwlist)
['while']
>>> get_close_matches('apple', keyword.kwlist)
[]
>>> get_close_matches('accept', keyword.kwlist)
['except']

Blick auf http://docs.python.org/library/difflib. html # difflib.get_close_matches

Ich weiß, das ist nicht das gleiche, aber man kann das Verhältnis anpassen Strings, um herauszufiltern, die nicht genug ähnlich sind, und gibt die größte Übereinstimmung mit der Zeichenfolge, die Sie suchen.

Vielleicht möchten Sie mehr Interesse an semantischer Ähnlichkeit Metriken.

https: //www.google.com/search?client=ubuntu&channel=fs&q=semantic+similarity+string+match&ie=utf-8&oe=utf-8

Ich weiß, Sie sagte Geschwindigkeit ist kein Problem, aber wenn Sie eine Menge der Saiten für Ihren Algorithmus verarbeiten die unten ist sehr hilfreich. 

def spellcheck(self, sentence):
    #return ' '.join([difflib.get_close_matches(word, wordlist,1 , 0)[0] for word in sentence.split()])
    return ' '.join( [ sorted( { Levenshtein.ratio(x, word):x for x in wordlist }.items(), reverse=True)[0][1] for word in sentence.split() ] )

Die etwa 20-mal schneller als difflib.

https://pypi.python.org/pypi/python-Levenshtein/

Import Levenshtein

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top