Finden Sie die Ähnlichkeitsmetrik zwischen zwei Zeichenfolgen

Question

Wie bekomme ich die Wahrscheinlichkeit, dass ein String in Python einem anderen String ähnlich ist?

Ich möchte einen Dezimalwert wie 0.9 (was 90% bedeutet usw.) erhalten. Bevorzugt mit Standard-Python und Bibliothek.

zum Beispiel.

ähnlich("Apfel", "Apel") # hätte eine hohe Wahrscheinlichkeit.

ähnlich("Apfel", "Mango") # hätte eine niedrigere Wahrscheinlichkeit.

Answer 1

Hinweis, difflib.SequenceMatcher findet nur die längste zusammenhängende übereinstimmende Teilsequenz, dies ist oft nicht das Gewünschte, zum Beispiel:

>>> a1 = "Apfel"
>>> a2 = "Appel"
>>> a1 *= 50
>>> a2 *= 50
>>> SequenceMatcher(None, a1, a2).ratio()
0,012  # sehr niedrig
>>> SequenceMatcher(None, a1, a2).get_matching_blocks()
[Match(a=0, b=0, size=3), Match(a=250, b=250, size=0)]  # nur der erste Block wird aufgezeichnet

Die Ähnlichkeit zwischen zwei Zeichenfolgen zu finden, ist eng mit dem Konzept der paarweisen Sequenzalignierung in der Bioinformatik verbunden. Es gibt viele dedizierte Bibliotheken dafür, 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 Bioinformatikpaket ist flexibler als jedes Teil der Python-Standardbibliothek, da viele verschiedene Bewertungsschemata und Algorithmen verfügbar sind. Außerdem können Sie tatsächlich die übereinstimmenden Sequenzen erhalten, um zu visualisieren, was passiert:

>>> alignment = next(aligner.align(a1, a2))
>>> alignment.score
200,0
>>> print(alignment)
Apfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-Äpfel-
|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-|||-|-
Äpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-elÄpf-el

Answer 2

Paket distance enthält die Levenshtein-Distanz:

import distance
distance.levenshtein("lenvestein", "levenshtein")
# 3

Answer 3

Sie finden die meisten Textähnlichkeitsmethoden und wie sie berechnet werden unter diesem Link: https://github.com/luozhouyang/python-string-similarity#python-string-similarity Hier einige Beispiele;

• Normalisierte, metrische, Ähnlichkeits- und Distanzwerte

• (Normalisiert) Ähnlichkeits- und Distanzwerte

• Metrische Distanzen

• Ähnlichkeits- und Distanzwerte basierend auf Shingles (n-Grammen)

• Levenshtein

• Normalisierter Levenshtein

• Gewichteter Levenshtein

• Damerau-Levenshtein

• Optimale Zeichenkettenausrichtung

• Jaro-Winkler

• Längste gemeinsame Teilfolge

• Metrische längste gemeinsame Teilfolge

• N-Gramm

• Shingle(n-Gramm) basierte Algorithmen

• Q-Gramm

• Kosinus-Ähnlichkeit

• Jaccard-Index

• Sorensen-Dice-Koeffizient

• Überlappungskoeffizient (d.h. Szymkiewicz-Simpson)

Answer 4

BLEUscore

BLEU, oder der Bilingual Evaluation Understudy, ist ein Score zur Vergleichung einer Kandidatenübersetzung von Text mit einer oder mehreren Referenzübersetzungen.

Ein perfekter Treffer ergibt einen Score von 1.0, während ein perfektes Missmatch einen Score von 0.0 ergibt.

Obwohl für Übersetzungen entwickelt, kann es verwendet werden, um Texte zu bewerten, die für eine Reihe von natürlichsprachlichen Aufgaben generiert wurden.

Code:

import nltk
from nltk.translate import bleu
from nltk.translate.bleu_score import SmoothingFunction
smoothie = SmoothingFunction().method4

C1='Text'
C2='Best'

print('BLEUscore:',bleu([C1], C2, smoothing_function=smoothie))

Beispiele: Durch Aktualisierung von C1 und C2.

C1='Test' C2='Test'

BLEUscore: 1.0

C1='Test' C2='Best'

BLEUscore: 0.2326589746035907

C1='Test' C2='Text'

BLEUscore: 0.2866227639866161

Sie können auch die Ähnlichkeit von Sätzen vergleichen:

C1='Es ist hart.' C2='Es ist rau.'

BLEUscore: 0.7348889200874658

C1='Es ist hart.' C2='Es ist hart.'

BLEUscore: 1.0

Answer 5

Der eingebaute SequenceMatcher ist sehr langsam bei großen Eingaben, 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)

    # Ähnlichkeit
    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