Sonntag, Dezember 8, 2019

Algorithmen und Daten-Strukturen am besten geeignet für eine Rechtschreibprüfung, Wörterbuch und thesaurus

Beste Weg zur Umsetzung einer

  • Wörterbuch (gibt es eine DS besser als Trie für Wörterbuch)
  • thesaurus (keine Ahnung, wie übereinstimmung hergestellt wird, die auf die Bedeutungen der Wörter, die ähnliche Bedeutungen)
  • Rechtschreibprüfung (etwas besser als hash-map), wenn möglich mit korrekter Rechtschreibung Empfehlungen.

Wenn Sie gefragt werden, die in einem einstündigen interview werden wir voraussichtlich schreiben Sie eine c/c++ – code für den Algorithmus?

  • speall checker? wirklich nicht?
  • warum nicht? Nachdem alle, die Apache-Rechtschreibprüfung Modul aufgerufen wird mod_speling.
  • …und in den HTTP-Spezifikationen referrer geschrieben wird als referer (und muss daher geschrieben werden, falsch in allen Implementierungen mithilfe dieses header).
  • Sorry für das ruinieren der Witz, wenn es Absicht war.
InformationsquelleAutor Vivek Sharma | 2009-10-06

6 Kommentare

  1. 4

    Für das Wörterbuch, es ist in der Tat eine Datenstruktur überlegen, die trie. Versuchen Sie, ein KUMPEL, oder CDAWG: http://en.wikipedia.org/wiki/Directed_acyclic_word_graph. Nur um die Sache zu verkomplizieren, meine Lieblings-Papier, auf die Struktur, Ciura und Deorowicz „Wie man ein Squeeze-Lexikon“ nennt Sie „minimal ADFAs“. Google und finden Sie viele konkurrierende algorithmen für den Bau dieser Tiere. Viel Glück!

    • Das ist eine sehr interessante DS. Vielen Dank für die Wiederauferstehung der Frage, es zu teilen.
  2. 1

    Für ein Wörterbuch würde ich die std::map (calling Dictionary im .Net framework) Sammlung mit dem Wort als Schlüssel und ein benutzerdefiniertes Objekt (mit allen Informationen über die Wort + definition) als Wert.

    Für einen thesaurus, die beste Struktur ist ein Baum, wo jeder Knoten ist ein Abschnitt und wobei jeder Zweig beendet mit einem Objekt, das alle Informationen enthält, über das, was Sie haben, um anzuzeigen.

  3. 1

    Können, sehe ich keinen besseren Datenstruktur, die als ein trie für das Wörterbuch und der thesaurus. Beides kann montiert werden in einer Struktur falls nötig, mit einem link-Knoten zeigen, auf die Bedeutung des Wortes (Wörterbuch) und einem auf Synonyme (thesaurus). Es kann sogar bieten einige form der Auto-Vervollständigung (wenn es nur eine Verknüpfung in den Knoten).

    Rechtschreib-Korrektor ist ein bisschen schwieriger – da hat man sich anzeigen fals Eingang zu einer Art von richtigen Eingang. Sie können diesen link als Einstieg: http://en.wikipedia.org/wiki/Spell_checker. Am Ende finden Sie links zu den Publikationen über verschiedene algorithmen. Gemäß der wikipedia-Artikel, dieses Papier beschreibt die meisten erfolgreichen Algorithmus: Andrew Golding und Dan Roth „Winnow-basierte Rechtschreibung-Korrektur-Algorithmus“

  4. 1

    In allen drei Fällen, können Sie konstruieren eine BK-Baum aus Ihrem word-set. BK-Bäume lassen finden Sie alle Wörter innerhalb einer bestimmten edit-Distanz des eingegebenen Wortes. Siehe my blog-post auf BK-Bäume, die für eine Erklärung von, wie Sie arbeiten.

    Wörterbuch und die Rechtschreibprüfung sind mehr oder weniger identisch – das Wörterbuch muss nur Definitionen zusammen mit den Worten. Für einen thesaurus, Wörter sind gebündelt in ’synsets‘ – synonym – sets mit allen Elementen eingefügt, in der BK-Baum. Wenn jemand sucht ein Wort in das synset, Sie zeigen alle die anderen alternativen. Ein Wort in mehreren synsets, so dass Sie brauchen, um sicherzustellen, dass Ihre BK-Baum-Knoten verarbeiten kann, mehrere Werte für einen bestimmten Schlüssel.

Kostenlose Online-Tests

Letzte Fragen

Tun ItemView löst Blase?

Ich habe eine CompositeView für eine Tabelle. Ich habe Trigger-set in der Kind-ItemView für jede Zeile... var TableRow = Marionette.ItemView.extend({ tagName:...

Wie kann ich untersuchen, WCF was 400 bad request über GET?

Die folgenden WCF-endpoint funktioniert gut mit dem WCF test client: AssetList ListFlaggedAssets(short processCode, string platform, string endpoint = "null", string portalId = "null", int...

Bei der Verwendung von UUIDs, sollte ich auch mit AUTO_INCREMENT?

Wir bauen eine neue web-app, die eine offline-iPad - /Android-app-version auf einer Reihe von lokalen Geräten, die Einsätze mit neuen Daten. Als solche benötigen...

Actionscript-Objekt, das verschiedene Eigenschaften

Wie kann ich die Anzahl der Eigenschaften in einer generischen Actionscript-Objekt? (Wie die Array-Länge) InformationsquelleAutor Fragsworth | 2011-01-15

Wie plot mehrere Graphen und nutzen Sie die Navigations-Taste im [matplotlib]

Die neueste version von matplotlib erstellt automatisch Navigations-buttons unter den graph. Aber die Beispiele, die ich finden alles im Internet zeigen, wie erstellen Sie...