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.
318
tenstar 30 Juni 2013 im 11:35

7 Antworten

Beste Antwort

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
504
Inbar Rose 30 Juni 2013 im 08:18

Ich denke, vielleicht suchen Sie nach einem Algorithmus, der den Abstand zwischen Zeichenfolgen beschreibt. Hier sind einige, auf die Sie sich beziehen können:

  1. Hamming Distanz
  2. Levenshtein Entfernung
  3. Entfernung Damerau - Levenshtein
  4. Jaro-Winkler-Entfernung
67
hbprotoss 30 Juni 2013 im 08:45

Das Paket Entfernung enthält die Levenshtein-Entfernung:

import distance
distance.levenshtein("lenvestein", "levenshtein")
# 3
9
Enrique Pérez Herrero 10 Apr. 2017 im 22:02

Beachten Sie, dass difflib.SequenceMatcher nur die längste zusammenhängende übereinstimmende Teilsequenz findet. 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, darunter Biopython. In diesem Beispiel wird der Needleman Wunsch-Algorithmus implementiert:

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

Die Verwendung von Biopython oder einem anderen Bioinformatikpaket 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
4
Chris_Rands 4 Dez. 2019 im 10:27

Fuzzy Wuzzy ist ein Paket, das die Levenshtein-Distanz in Python implementiert, wobei einige Hilfsfunktionen in bestimmten Fällen hilfreich sind Situationen, in denen zwei unterschiedliche Zeichenfolgen als identisch angesehen werden sollen. Beispielsweise:

>>> 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
25
BLT 18 Jän. 2017 im 22:26

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))
9
Ilia Kurenkov 11 Sept. 2016 im 10:11

Das eingebaute SequenceMatcher ist bei großen Eingaben sehr langsam. So kann es mit diff gemacht werden -match-patch:

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
6
damio 30 Apr. 2018 im 14:24