Fuzzy String Vergleich

70

Was ich vervollständigen möchte, ist ein Programm, das eine Datei einliest und jeden Satz gemäß dem ursprünglichen Satz vergleicht. Der Satz, der perfekt zum Original passt, erhält eine Punktzahl von 1 und ein Satz, der das Gegenteil ist, erhält eine 0. Alle anderen Fuzzy-Sätze erhalten eine Note zwischen 1 und 0.

Ich bin mir nicht sicher, welchen Vorgang ich verwenden soll, damit ich dies in Python 3 ausführen kann.

Ich habe den Beispieltext eingefügt, in dem der Text 1 das Original ist, und die anderen vorhergehenden Zeichenfolgen sind die Vergleiche.

Text: Beispiel

Text 1: Es war eine dunkle und stürmische Nacht. Ich saß ganz alleine auf einem roten Stuhl. Ich war nicht ganz alleine, da ich drei Katzen hatte.

Text 20: Es war eine trübe und stürmische Nacht. Ich saß ganz alleine auf einem purpurroten Stuhl. Ich war nicht ganz alleine, da ich drei Katzen hatte // Sollte einen hohen Punkt erzielen, aber nicht 1

Text 21: Es war eine trübe und stürmische Nacht. Ich saß ganz alleine auf einer purpurroten Kathedra. Ich war nicht ganz alleine, da ich drei Katzen hatte // Sollte weniger als Text 20 punkten

Text 22: Ich saß ganz alleine auf einer purpurroten Kathedra. Ich war nicht ganz alleine, da ich drei Katzen hatte. Es war eine trübe und stürmische Nacht. // Sollte niedriger als Text 21 sein, aber NICHT 0

Text 24: Es war eine dunkle und stürmische Nacht. Ich war nicht allein Ich saß nicht auf einem roten Stuhl. Ich hatte drei Katzen. // Sollte eine 0 erzielen!

jacksonstephenc
quelle
4
Anscheinend möchten Sie die Levenshtein-Entfernung (oder eine andere Bearbeitungsentfernungsmetrik ) berechnen . Wenn Sie jetzt die maximale Entfernung haben, müssen Sie nur die Punktzahlen auf den Bereich skalieren [0,1].
Felix Kling
Vielen Dank für Ihre Hilfe @Felix Kling the difflib könnte der richtige Weg sein.
Jacksonstephenc
@ FelixKling Schade, dass es gelöscht wurde ....
Franck Dernoncourt
Warum sollten String 1 und 24 Null bekommen? Sie haben genau den gleichen ersten Satz. Der 2. Satz in 1 ist fast der gleiche wie Satz 2 + 3 in 24 (der einzige Unterschied ist "nicht" und ein zusätzliches "Ich war nicht"). Numerisch sind sie SEHR ähnlich. Semantisch sind sie unterschiedlich, aber wenn Sie nach einem Computer fragen, um die Bedeutung eines Satzes zu verstehen, fragen Sie möglicherweise zu viel.
naught101

Antworten:

107

Es gibt ein Paket namens fuzzywuzzy. Installation über Pip:

pip install fuzzywuzzy

Einfache Verwendung:

>>> from fuzzywuzzy import fuzz
>>> fuzz.ratio("this is a test", "this is a test!")
    96

Das Paket basiert auf difflib. Warum nicht einfach das benutzen, fragst du? Abgesehen davon, dass es ein bisschen einfacher ist, gibt es eine Reihe verschiedener Matching-Methoden (wie Unempfindlichkeit gegenüber Token-Reihenfolge, partielle String-Matching), die es in der Praxis leistungsfähiger machen. Die process.extractFunktionen sind besonders nützlich: Finden Sie die am besten passenden Zeichenfolgen und Verhältnisse aus einem Satz. Aus ihrer Readme:

Teilverhältnis

>>> fuzz.partial_ratio("this is a test", "this is a test!")
    100

Token-Sortierverhältnis

>>> fuzz.ratio("fuzzy wuzzy was a bear", "wuzzy fuzzy was a bear")
    90
>>> fuzz.token_sort_ratio("fuzzy wuzzy was a bear", "wuzzy fuzzy was a bear")
    100

Token Set Ratio

>>> fuzz.token_sort_ratio("fuzzy was a bear", "fuzzy fuzzy was a bear")
    84
>>> fuzz.token_set_ratio("fuzzy was a bear", "fuzzy fuzzy was a bear")
    100

Prozess

>>> choices = ["Atlanta Falcons", "New York Jets", "New York Giants", "Dallas Cowboys"]
>>> process.extract("new york jets", choices, limit=2)
    [('New York Jets', 100), ('New York Giants', 78)]
>>> process.extractOne("cowboys", choices)
    ("Dallas Cowboys", 90)
Congusbongus
quelle
Fuzzywuzzy ausprobieren. Haben gefunden, wenn "New York Giants" in "New York Giants Dallas Cowboys" geändert wird, erzeugt process.extract ("New York Jets", Auswahlmöglichkeiten, Limit = 2) [('New York Jets', 100), ( "New York Giants Dallas Cowboys", 86)]. Wissen Sie, warum die Übereinstimmungsrate für das zweite Fuzzy-Spiel steigt? Es macht nicht viel Sinn.
ToonZ
Die Warnung "lib / python2.7 / site-packages / fuzzywuzzy / fuzz.py: 35: UserWarning: Verwenden von Slow Pure-Python SequenceMatcher. Installieren Sie Python-Levenshtein, um diese Warnung zu entfernen. warnings.warn ('Verwenden von Slow Pure-Python SequenceMatcher Installieren Sie Python-Levenshtein, um diese Warnung zu entfernen. ') "
@ user2738183 pip install python-Levenshtein FuzzyWuzzy verwendet Difflib, das Teil der Standardbibliothek ist. Um eine bessere Leistung zu erzielen, können Sie jedoch das Python-Levenshtein-Modul für den Sequenzabgleich wie oben beschrieben installieren. pypi.org/project/python-Levenshtein
Alexander
85

In der Standardbibliothek (aufgerufen difflib) gibt es ein Modul , mit dem Zeichenfolgen verglichen und anhand ihrer Ähnlichkeit eine Punktzahl zurückgegeben werden können. Die SequenceMatcherKlasse sollte das tun, wonach Sie suchen.

EDIT: Kleines Beispiel aus der Python-Eingabeaufforderung:

>>> from difflib import SequenceMatcher as SM
>>> s1 = ' It was a dark and stormy night. I was all alone sitting on a red chair. I was not completely alone as I had three cats.'
>>> s2 = ' It was a murky and stormy night. I was all alone sitting on a crimson chair. I was not completely alone as I had three felines.'
>>> SM(None, s1, s2).ratio()
0.9112903225806451

HTH!

Mac
quelle
1
Vielen Dank, dass Sie @mac. Genau das suche ich. Ich habe nur Probleme herauszufinden, wie ich das Programm dazu bringen kann, festzustellen, ob ein Satz das Gegenteil des Originals ist. Verfügt Python über eine Bibliothek, in der ich in grammatikalischen Situationen dieses Problem lösen kann?
Jacksonstephenc
@ user1365664 - Das klingt nach einem wirklich schwierigen Problem, aber die kanonische Antwort auf alles, was natürliche Sprachen in Python betrifft, lautet NLTK, nltk.org .
AKX
@ user1365664: Ich bezweifle, dass so etwas existiert, es sei denn, Sie geben an, was "Gegenteil" in diesem Fall bedeutet. Ist abdas Gegenteil von zy? Oder ist abdas Gegenteil von ba? usw.
Felix Kling
1
@ user1365664: In diesem Fall möchten Sie vielleicht einen Blick auf die NLP- und Stimmungsanalyse werfen .
Felix Kling
5
@ user1365664 Vergessen Sie nicht, diese Antwort zu akzeptieren, wenn Sie zufrieden sind.
Driftcatcher
16

fuzzysetist sowohl für die Indizierung als auch für die Suche viel schneller als fuzzywuzzy( difflib).

from fuzzyset import FuzzySet
corpus = """It was a murky and stormy night. I was all alone sitting on a crimson chair. I was not completely alone as I had three felines
    It was a murky and tempestuous night. I was all alone sitting on a crimson cathedra. I was not completely alone as I had three felines
    I was all alone sitting on a crimson cathedra. I was not completely alone as I had three felines. It was a murky and tempestuous night.
    It was a dark and stormy night. I was not alone. I was not sitting on a red chair. I had three cats."""
corpus = [line.lstrip() for line in corpus.split("\n")]
fs = FuzzySet(corpus)
query = "It was a dark and stormy night. I was all alone sitting on a red chair. I was not completely alone as I had three cats."
fs.get(query)
# [(0.873015873015873, 'It was a murky and stormy night. I was all alone sitting on a crimson chair. I was not completely alone as I had three felines')]

Warnung: Achten Sie darauf, nicht zu mischen unicodeund bytesin Ihrem Fuzzyset.

Kochfelder
quelle
1
Wie man nur den Text extrahiert
Jaffer Wilson
@JafferWilson auf die gleiche Weise, wie Sie die erste Zeile, letzte "Spalte" aus einer Python-Liste von Tupeln extrahieren würden:fs.get(query)[0][-1]
Kochfelder
1
Danke .. :) Ich werde das auf jeden Fall nutzen.
Jaffer Wilson
5

Die Aufgabe heißt Paraphrase Identification und ist ein aktives Forschungsgebiet in der Verarbeitung natürlicher Sprache. Ich habe mehrere hochmoderne Artikel verlinkt, von denen viele Open Source Code auf GitHub finden.

Beachten Sie, dass alle beantworteten Fragen davon ausgehen, dass zwischen den beiden Sätzen eine gewisse Ähnlichkeit zwischen Zeichenfolge und Oberfläche besteht, während in Wirklichkeit zwei Sätze mit geringer Ähnlichkeit zwischen Zeichenfolgen semantisch ähnlich sein können.

Wenn Sie an dieser Art von Ähnlichkeit interessiert sind, können Sie Skip-Thoughts verwenden . Installieren Sie die Software gemäß den GitHub-Anleitungen und gehen Sie zum Abschnitt zur Erkennung von Paraphrasen in der Readme-Datei:

import skipthoughts
model = skipthoughts.load_model()
vectors = skipthoughts.encode(model, X_sentences)

Dadurch werden Ihre Sätze (X_sentences) in Vektoren konvertiert. Später können Sie die Ähnlichkeit zweier Vektoren finden durch:

similarity = 1 - scipy.spatial.distance.cosine(vectors[0], vectors[1])

wobei wir annehmen, dass Vektor [0] und Vektor 1 der entsprechende Vektor zu X_sentences [0] sind, X_sentences 1, für den Sie ihre Punktzahlen ermitteln wollten.

Es gibt andere Modelle, um einen Satz in einen Vektor umzuwandeln, den Sie hier finden .

Sobald Sie Ihre Sätze in Vektoren konvertiert haben, ist die Ähnlichkeit nur eine Frage der Cosinus-Ähnlichkeit zwischen diesen Vektoren.

Update im Jahr 2020 Es gibt dieses neue Modell namens BERT, das von Google basierend auf einem Deep-Learning-Framework namens Tensorflow veröffentlicht wurde. Es gibt auch eine Implementierung, die für viele Benutzer einfacher zu verwenden ist und Transformatoren heißt. Was diese Programme tun, ist, dass sie zwei Phrasen oder Sätze akzeptieren und sie können trainiert werden, um zu sagen, ob diese beiden Phrasen / Sätze gleich sind oder nicht. Um sie zu trainieren, benötigen Sie eine Reihe von Sätzen mit den Bezeichnungen 1 oder 0 (ob sie dieselbe Bedeutung haben oder nicht). Sie trainieren diese Modelle anhand Ihrer Trainingsdaten (bereits gekennzeichnete Daten) und können dann das trainierte Modell verwenden, um Vorhersagen für ein neues Paar von Phrasen / Sätzen zu treffen. Wie Sie diese Modelle trainieren (sie nennen es Feinabstimmung), finden Sie auf den entsprechenden Github-Seiten oder an vielen anderen Orten wie diesem .

Es gibt auch bereits gekennzeichnete Trainingsdaten in englischer Sprache, die als MRPC (Microsoft Paraphrase Identification Corpus) bezeichnet werden. Beachten Sie, dass es auch mehrsprachige oder sprachspezifische Versionen von BERT gibt, sodass dieses Modell auch in anderen Sprachen erweitert (z. B. geschult) werden kann.

Asche
quelle