Schnellste Wörterbuch-like

Question

passende

Ich muss eine Rechtschreibprüfung artigen Betrieb in Python wie folgt durchführen:

ich eine große Liste von Wörtern haben (lass es das Lexikon nennen). Ich bekomme jetzt einen Text (nennen wir es das Sample). Ich muss nach jedem Beispielwort im Lexikon suchen. Wenn ich es nicht finden kann, ist dieses Beispielwort ein Fehler.

Kurz gesagt - eine Rechtschreibprüfung mit roher Gewalt. Das lineare Durchsuchen des Lexikons für jedes Abtastwort ist jedoch zwangsläufig langsam. Was ist eine bessere Methode, dies zu tun?

Der komplizierende Faktor ist, dass weder die Probe noch das Lexikon in Englisch ist. Es ist in einer Sprache, die statt 26 Zeichen mehr als 300 - in Unicode gespeichert haben kann.

Ein Vorschlag eines Algorithmus/Datenstruktur/Parallelisierungsmethode wird hilfreich sein. Algorithmen, die eine hohe Geschwindigkeit auf Kosten von weniger als 100% Genauigkeit aufweisen, wären perfekt, da ich keine 100% ige Genauigkeit benötige. Ich kenne Norvigs Algorithmus dafür, aber es scheint spezifisch für Englisch zu sein.

Answer 1

Sie eine Reihe von Unicode-Strings verwenden können:

s = set(u"rabbit", u"lamb", u"calf") 

und verwenden Sie die in Betreiber zu prüfen, ob ein Wort vorkommt:

>>> u"rabbit" in s 
True 
>>> u"wolf" in s 
False 

Dieses Look-up ist im Wesentlichen O (1), also spielt die Größe des Wörterbuchs keine Rolle.

bearbeiten: Hier ist der vollständige Code für eine (case-sensitive) Rechtschreibprüfung (2.6 oder höher):

from io import open 
import re 
with open("dictionary", encoding="utf-8") as f: 
    words = set(line.strip() for line in f) 
with open("document", encoding="utf-8") as f: 
    for w in re.findall(r"\w+", f.read()): 
     if w not in words: 
      print "Misspelled:", w.encode("utf-8") 

(Die print übernimmt das Terminal verwendet UTF-8.)

Answer 2

Dies ist, wo sets an Ort und Stelle kommen. Erstellen Sie einen Satz aller Wörter in Ihrem Wörterbuch und verwenden Sie dann einen Mitgliedschaftsoperator, um zu überprüfen, ob das Wort im Wörterbuch vorhanden ist oder nicht.

Hier ist ein vereinfachtes Beispiel

>>> dictionary = {'Python','check-like', 'will', 'perform','follows:', 'spelling', 'operation'} 
>>> for word in "I will have to perform a spelling check-like operation in Python as follows:".split(): 
    if word in dictionary: 
     print "Found {0} in the dictionary".format(word) 
    else: 
     print "{0} not present in the dictionary".format(word) 


I not present in the dictionary 
Found will in the dictionary 
have not present in the dictionary 
to not present in the dictionary 
Found perform in the dictionary 
a not present in the dictionary 
Found spelling in the dictionary 
Found check-like in the dictionary 
Found operation in the dictionary 
in not present in the dictionary 
Found Python in the dictionary 
as not present in the dictionary 
Found follows: in the dictionary 
>>> 

Answer 3

Die durchschnittliche Zeit Komplexität der Hash-Suche in einem Python-Wörterbuch ist O (1). Sie können daher ein "Wörterbuch ohne Werte" (a.k.a. a set) verwenden

Answer 4

Dafür sind Python-Wörterbücher und -Sets gedacht! :) Speichern Sie Ihr Lexikon in einem Wörterbuch, wenn jedes Wort einen Wert hat (z. B. Häufigkeit), oder ein Satz, wenn Sie nur nach Existenz suchen müssen. Sie zu suchen ist O (1), also wird es verdammt schnell sein.

lex = set(('word1', 'word2', .....)) 

for w in words: 
    if w not in lex: 
     print "Error: %s" % w 

Answer 5

Verwenden Sie eine Baumstruktur, um die Wörter zu speichern, so dass jeder Pfad von Stamm zu Blatt ein einzelnes Wort darstellt. Wenn Ihr Traversal kein Blatt erreichen kann oder ein Blatt vor dem Ende des Wortes erreicht, haben Sie ein Wort, das nicht in Ihrem Lexikon ist.

Abgesehen von den Vorteilen, die Emil in den Kommentaren erwähnt, beachten Sie auch, dass Sie damit Dinge wie Back-Tracking tun können, um alternative Schreibweisen zu finden.

Answer 6

Versuchen Sie es mit einem Satz, wie jeder Ihnen sagt.Set-Lookups wurden von erfahrenen Programmierern im Python-C-Code optimiert, so dass Sie in Ihrer kleinen Anwendung nicht besser werden können.

Unicode ist kein Problem: Set und Dictionary Keys können Unicode oder englischer Text sein, es spielt keine Rolle. Die einzige Überlegung für Sie könnte die Unicode-Normalisierung sein, da verschiedene diakritische Ordnungen nicht gleichwertig sind. Wenn dies ein Problem für Ihre Sprache ist, würde ich zuerst sicherstellen, dass das Lexikon in normalisierter Form gespeichert wird, und dann jedes Wort normalisieren, bevor Sie es überprüfen. Zum Beispiel unicodedata.normalize('NFC', word)

Answer 7

Zuerst müssen Sie den Index Ihres Lexikons erstellen. Zum Beispiel können Sie Ihr eigenes Indizierungssystem erstellen, aber besser ist die Verwendung von Volltext-Suchmaschinen Full text search engine Ich kann Apache Lucene oder Sphinx für Sie empfehlen. Es ist sowohl schnell als auch Open Source. Nachdem Sie eine Suche Abfragen von Python an die Suchmaschine senden und Antworten abfangen können.

Answer 8

Hier ist ein Beitrag schrieb ich über solche Dinge zu prüfen. Es ist ähnlich, wenn der Google Suggestion/Spell Checker funktioniert.

http://blog.mattalcock.com/2012/12/5/python-spell-checker/

Hoffe, es hilft.