Suchen Sie die Ähnlichkeitsmetrik zwischen zwei Zeichenfolgen

283

Wie erhalte ich die Wahrscheinlichkeit, dass eine Zeichenfolge einer anderen Zeichenfolge in Python ähnelt?

Ich möchte einen Dezimalwert wie 0,9 (dh 90%) usw. erhalten. Am besten mit Standard-Python und -Bibliothek.

z.B

similar("Apple","Appel") #would have a high prob.

similar("Apple","Mango") #would have a lower prob.
python probability similarity metric Tenstar
quelle
6
Ich denke nicht, dass "Wahrscheinlichkeit" hier der richtige Begriff ist. In jedem Fall siehe stackoverflow.com/questions/682367/…
NPE
1
Das Wort, das Sie suchen, ist Verhältnis, nicht Wahrscheinlichkeit.
Inbar Rose
1
Schauen Sie sich die Hamming-Distanz an .
Diana
2
Der Ausdruck lautet "Ähnlichkeitsmetrik" , es gibt jedoch mehrere Ähnlichkeitsmetriken (Jaccard, Cosine, Hamming, Levenshein usw.), sodass Sie angeben müssen, welche. Insbesondere möchten Sie eine Ähnlichkeitsmetrik zwischen Zeichenfolgen. @hbprotoss listete mehrere auf.
smci

Antworten:

541

Es ist ein eingebauter.

from difflib import SequenceMatcher

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

Es benutzen:

>>> similar("Apple","Appel")
0.8
>>> similar("Apple","Mango")
0.0
Inbar Rose
quelle
42
Sehen Sie diese große Antwort zu vergleichen SequenceMatchervs python-LevenshteinModul. stackoverflow.com/questions/6690739/…
ssoler
1
Interessanter Artikel und Tool: Chairnerd.seatgeek.com/…
Anthony Perot
7
Ich würde wärmstens empfehlen, das gesamte Difflib-Dokument docs.python.org/2/library/difflib.html zu lesen. Es gibt ein get_close_matcheseingebautes, obwohl ich es sorted(... key=lambda x: difflib.SequenceMatcher(None, x, search).ratio(), ...)zuverlässiger fand, mit benutzerdefinierten sorted(... .get_matching_blocks())[-1] > min_matchÜberprüfungen
ThorSummoner
2
@ThorSummoner macht auf eine sehr nützliche Funktion aufmerksam ( get_closest_matches). Es ist eine praktische Funktion, nach der Sie vielleicht suchen. AKA, lesen Sie die Dokumente! In meiner speziellen Anwendung habe ich einige grundlegende Fehlerprüfungen / Berichte an den Benutzer durchgeführt, die schlechte Eingaben lieferten, und diese Antwort ermöglicht es mir, ihnen die möglichen Übereinstimmungen und die "Ähnlichkeit" zu melden . Wenn Sie die Ähnlichkeit jedoch nicht anzeigen müssen, get_closest_matches
schauen Sie auf
Das hat perfekt funktioniert. Einfach und effektiv.
Vielen Dank
45

Lösung 1: Python eingebaut

Verwenden Sie SequenceMatcher von difflib

Profis : native Python-Bibliothek, kein zusätzliches Paket erforderlich.
Nachteile : Zu begrenzt, es gibt so viele andere gute Algorithmen für die Ähnlichkeit von Zeichenfolgen.

Beispiel : 
>>> from difflib import SequenceMatcher
>>> s = SequenceMatcher(None, "abcd", "bcde")
>>> s.ratio()
0.75

Lösung 2: Quallen - Bibliothek

Es ist eine sehr gute Bibliothek mit guter Abdeckung und wenigen Ausgaben. Es unterstützt:
- Levenshtein-Distanz
- Damerau-Levenshtein-Distanz
- Jaro-Distanz
- Jaro-Winkler-Distanz
- Match-Rating-Ansatz-Vergleich
- Hamming-Distanz

Profis : einfach zu bedienen, Umfang der unterstützten Algorithmen, getestet.
Nachteile : keine native Bibliothek.

Beispiel : 

>>> import jellyfish
>>> jellyfish.levenshtein_distance(u'jellyfish', u'smellyfish')
2
>>> jellyfish.jaro_distance(u'jellyfish', u'smellyfish')
0.89629629629629637
>>> jellyfish.damerau_levenshtein_distance(u'jellyfish', u'jellyfihs')
1
Iman Mirzadeh
quelle
26

Fuzzy Wuzzyist ein Paket , das die Levenshtein-Distanz in Python implementiert, mit einigen Hilfsfunktionen, die in bestimmten Situationen helfen, in denen zwei unterschiedliche Zeichenfolgen als identisch angesehen werden sollen. Zum Beispiel:

>>> fuzz.ratio("fuzzy wuzzy was a bear", "wuzzy fuzzy was a bear")
    91
>>> fuzz.token_sort_ratio("fuzzy wuzzy was a bear", "wuzzy fuzzy was a bear")
    100
BLT
quelle
9

Sie können eine Funktion erstellen wie:

def similar(w1, w2):
    w1 = w1 + ' ' * (len(w2) - len(w1))
    w2 = w2 + ' ' * (len(w1) - len(w2))
    return sum(1 if i == j else 0 for i, j in zip(w1, w2)) / float(len(w1))
Saullo GP Castro
quelle
aber ähnlich ('appel', 'apple') ist höher als ähnlich ('appel', 'ape')
tenstar
1
Ihre Funktion vergleicht eine bestimmte Zeichenfolge mit anderen Stichen. Ich möchte eine Möglichkeit, die Zeichenfolge mit dem höchsten Ähnlichkeitsverhältnis zurückzugeben
answerSeeker
1
@ SaulloCastro, if self.similar(search_string, item.text()) > 0.80:funktioniert vorerst . Danke,
answerSeeker
9

Paket Abstand umfasst Levenshtein Abstand:

import distance
distance.levenshtein("lenvestein", "levenshtein")
# 3
Enrique Pérez Herrero
quelle
6

Das eingebaute Gerät SequenceMatcherist bei großen Eingaben sehr langsam. So kann es mit Diff-Match-Patch gemacht werden :

from diff_match_patch import diff_match_patch

def compute_similarity_and_diff(text1, text2):
    dmp = diff_match_patch()
    dmp.Diff_Timeout = 0.0
    diff = dmp.diff_main(text1, text2, False)

    # similarity
    common_text = sum([len(txt) for op, txt in diff if op == 0])
    text_length = max(len(text1), len(text2))
    sim = common_text / text_length

    return sim, diff
damio
quelle
5

Beachten Sie, dass difflib.SequenceMatcher nur die längste zusammenhängende übereinstimmende Teilsequenz gefunden wird. Dies ist häufig nicht erwünscht, zum Beispiel:

>>> a1 = "Apple"
>>> a2 = "Appel"
>>> a1 *= 50
>>> a2 *= 50
>>> SequenceMatcher(None, a1, a2).ratio()
0.012  # very low
>>> SequenceMatcher(None, a1, a2).get_matching_blocks()
[Match(a=0, b=0, size=3), Match(a=250, b=250, size=0)]  # only the first block is recorded

Das Finden der Ähnlichkeit zwischen zwei Strings hängt eng mit dem Konzept der paarweisen Sequenzausrichtung in der Bioinformatik zusammen. Hierfür gibt es viele dedizierte Bibliotheken, einschließlich Biopython . Dieses Beispiel implementiert den Needleman Wunsch-Algorithmus :

>>> from Bio.Align import PairwiseAligner
>>> aligner = PairwiseAligner()
>>> aligner.score(a1, a2)
200.0
>>> aligner.algorithm
'Needleman-Wunsch'

Die Verwendung von Biopython oder einem anderen Bioinformatik-Paket ist flexibler als jeder Teil der Python-Standardbibliothek, da viele verschiedene Bewertungsschemata und -algorithmen verfügbar sind. Außerdem können Sie die passenden Sequenzen abrufen, um zu visualisieren, was passiert:

>>> alignment = next(aligner.align(a1, a2))
>>> alignment.score
200.0
>>> print(alignment)
Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-Apple-
|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-
App-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-elApp-el
Chris_Rands
quelle
0

Unter diesem Link finden Sie die meisten Methoden zur Textähnlichkeit und deren Berechnung: https://github.com/luozhouyang/python-string-similarity#python-string-similarity Hier einige Beispiele;

  • Normalisiert, metrisch, Ähnlichkeit und Entfernung

  • (Normalisierte) Ähnlichkeit und Entfernung

  • Metrische Abstände

  • Ähnlichkeit und Abstand basierend auf Schindeln (n-Gramm)
  • Levenshtein
  • Normalisiertes Levenshtein
  • Gewichteter Levenshtein
  • Damerau-Levenshtein
  • Optimale Stringausrichtung
  • Jaro-Winkler
  • Längste gemeinsame Folge
  • Metrisch längste gemeinsame Folge
  • N-Gramm
  • Shingle (n-Gramm) -basierte Algorithmen
  • Q-Gramm
  • Kosinusähnlichkeit
  • Jaccard-Index
  • Sorensen-Würfel-Koeffizient
  • Überlappungskoeffizient (dh Szymkiewicz-Simpson)
Mike
quelle