Ein StringToken Parser, die Google Search Stil gibt „Meinten Sie:“ Vorschläge

StackOverflow https://stackoverflow.com/questions/135777

  •  02-07-2019
  •  | 
  •  

Frage

Ich suche eine Methode:

Nehmen Sie Leerzeichen getrennt Token in einem String; Rückkehr ein vorgeschlagenes Wort


ie:
Google-Suche kann nehmen "fonetic wrd nterpreterr" ,
und oben auf der Ergebnisseite zeigt es „Meinen Sie: Laut Wort Interpreter“

Eine Lösung in einem der C * Sprachen oder Java wäre vorzuziehen.


Gibt es irgendwelche bestehenden Offene Bibliotheken, die eine solche Funktionalität durchführen?

Oder gibt es eine Möglichkeit, einen Google-API zu verwenden, ein vorgeschlagenes Wort zu beantragen?

War es hilfreich?

Lösung

In seinem Artikel Wie eine Rechtschreibung Korrektor zu schreiben, bespricht Peter Norvig wie ein Google- wie Rechtschreibprüfung umgesetzt werden könnten. Der Artikel enthält eine 20-Zeilen-Implementierung in Python, sowie Links zu verschiedenen Neuimplementierungen in C, C ++, C # und Java. Hier ein Auszug:

  

Die vollständigen Einzelheiten über eine   Industrie-Stärke Zauber Korrektor   wie Google wäre verwirrend   als aufschlussreich, aber ich dachte, dass   auf der Ebene Flug, in weniger als   eine Seite von Code, kann ich ein Spielzeug schreiben   Schreibkorrektur, die 80 erreicht oder   90% Genauigkeit bei einer Verarbeitungsgeschwindigkeit von   mindestens 10 Wörter pro Sekunde.

Mit Norvig Code und dieser Text als Trainingssatz, erhalte ich folgende Ergebnisse: 

>>> import spellch
>>> [spellch.correct(w) for w in 'fonetic wrd nterpreterr'.split()]
['phonetic', 'word', 'interpreters']

Andere Tipps

Sie können die Yahoo-Web-Service verwenden hier: http://developer.yahoo.com/search/web/V1/spellingSuggestion. html

Allerdings ist es nur ein Web-Service ... (das heißt es gibt keine APIs für andere Sprache etc ..), aber es gibt JSON oder XML, so ... ziemlich einfach in jede Sprache anpassen ...

Sie können auch die Google-API verwenden Kontrolle zu buchstabieren. Es ist eine ASP-Implementierung hier (Ich bin nicht für zu dies, obwohl).

Zunächst einmal:

Mit der eines Ihrer Wahl. Ich vermute, es läuft die Abfrage für eine Rechtschreibprüfung Motor mit einem Wort Grenze von genau einem, es dann nichts tut, wenn die gesamte Abfrage gültig ist, sonst ersetzt er jedes Wort mit dem besten Treffer Wort. Mit anderen Worten, (bedeutet eine leere Rückgabestring, dass die Abfrage keine Probleme hatte) der folgenden Algorithmus: 

startup()
{
   set the spelling engines word suggestion limit to 1
}

option 1()
{
   int currentPosition = engine.NextWord(start the search at word 0, querystring);

   if(currentPosition == -1)
      return empty string; // Query is a-ok.

   while(currentPosition != -1)
   {
       queryString = engine.ReplaceWord(engine.CurrentWord, queryString, the suggestion with index 0);
       currentPosition = engine.NextWord(currentPosition, querystring);
   }

   return queryString;
}

Da niemand es noch erwähnt hat, werde ich noch einen Satz geben zu suchen: „Edit-Distanz“ (zum Beispiel link text ). Das kann dazu verwendet werden, die am nächsten Spielen zu finden, vorausgesetzt, es ist Typos wo Buchstaben vertauscht, fehlen oder hinzugefügt werden.

Aber in der Regel ist dies auch mit irgendeiner Art von Relevanz Informationen gekoppelt ist; entweder durch einfache Popularität (davon ausgehen, am häufigsten verwendete der Nähe genug Spiel am wahrscheinlichsten richtige Wort) oder durch kontextuelle Wahrscheinlichkeit (Worte, die vorhergehenden richtige Wort folgen, oder kommen vor eins). Dies wird in Information Retrieval; ein Weg zu beginnen ist bei Bigramm und Trigramme (Sequenzen von Wörtern zusammen gesehen) zu suchen. Google hat eine sehr umfangreiche frei verfügbare Datensätze für diese.

Für einfache Ausgangslösung obwohl ein Wörterbuch Paar mit Levenshtein-basierten Matcher funktioniert überraschend gut.

Sie könnten Lucene-Stecker, der eine Wörterbuch Anlage hat die Levenshtein-Distanz-Methode implementiert.

Hier ist ein Beispiel aus dem Wiki, wo 2 der Abstand. 

String[] l=spellChecker.suggestSimilar("sevanty", 2);
//l[0] = "seventy"

Wenn Sie ein Wörterbuch als Trie gespeichert haben, gibt es eine ziemlich einfache Art und Weise am besten passende Einträge zu finden, in Zeichen können eingefügt, gelöscht oder ersetzt werden. 

void match(trie t, char* w, string s, int budget){
  if (budget < 0) return;
  if (*w=='\0') print s;
  foreach (char c, subtrie t1 in t){
    /* try matching or replacing c */
    match(t1, w+1, s+c, (*w==c ? budget : budget-1));
    /* try deleting c */
    match(t1, w, s, budget-1);
  }
  /* try inserting *w */
  match(t, w+1, s + *w, budget-1);
}

Die Idee ist, dass zuerst Sie es mit einem Budget von Null nennen, und sehen, ob es etwas aus druckt. Dann versuchen Sie ein Budget von 1, und so weiter, bis er einige Spiele ausdruckt. Je größer das Budget desto länger dauert es. Vielleicht haben Sie nur wollen zu einem Budget von 2 steigen.

hinzugefügt: Es ist nicht allzu schwer zu verlängern diese gemeinsamen Präfixe und Suffixe zu handhaben. Zum Beispiel Englisch Präfixe wie „un“, „anti“ und „dis“ können im Wörterbuch sein und können dann an die Spitze der Wörterbuch-Links zurück. Für Suffixe wie „ism“, „'s“ und ‚ed‘ es kann eine separate trie nur die Suffixe enthalten sein, und die meisten Worte zu diesem Suffixbaum verknüpfen. Dann kann es seltsame Worte wie „antinationalizationalization“ behandeln.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top