Un parser StringToken che fornisce lo stile di ricerca di Google "Intendevi dire:" Suggerimenti

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

  •  02-07-2019
  •  | 
  •  

Domanda

Alla ricerca di un metodo per:

Accetta i token separati da spazi bianchi in una stringa; restituisce una parola suggerita


vale a dire:
Ricerca Google può accettare " fonetic wrd nterpreterr " ,
e in cima alla pagina dei risultati mostra " Intendevi forse: interprete di parole fonetiche "

Sarebbe preferibile una soluzione in qualsiasi linguaggio C * o Java.


Esistono librerie aperte esistenti che svolgono tale funzionalità?

O c'è un modo per utilizzare un'API di Google per richiedere una parola suggerita?

È stato utile?

Soluzione

Nel suo articolo Come scrivere un correttore ortografico , Peter Norvig discute come Google- come il controllo ortografico potrebbe essere implementato. L'articolo contiene un'implementazione a 20 righe in Python, nonché collegamenti a diverse reimplementazioni in C, C ++, C # e Java. Ecco un estratto:

  

I dettagli completi di un   correttore ortografico di forza industriale   come quello di Google sarebbe più confuso   che illuminante, ma l'ho immaginato   sull'aereo volo verso casa, in meno di   una pagina di codice, potrei scrivere un giocattolo   correttore ortografico che raggiunge 80 o   Precisione del 90% ad una velocità di elaborazione di   almeno 10 parole al secondo.

Utilizzo del codice di Norvig e questo testo come set di formazione, ottengo i seguenti risultati: 

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

Altri suggerimenti

Puoi utilizzare il servizio web yahoo qui: http://developer.yahoo.com/search/web/V1/spellingSuggestion. html

Tuttavia è solo un servizio web ... (cioè non ci sono API per altre lingue ecc.) ma genera output JSON o XML, quindi ... abbastanza facile adattarsi a qualsiasi lingua ...

Puoi anche utilizzare le API di Google per il controllo ortografico. Esiste un'implementazione ASP qui (non sono responsabile per questo, però).

Prima di tutto:

Usa quello che preferisci. Ho il sospetto che esegua la query su un motore di controllo ortografico con un limite di parole esattamente di uno, quindi non fa nulla se l'intera query è valida, altrimenti sostituisce ogni parola con la migliore corrispondenza di quella parola. In altre parole, il seguente algoritmo (una stringa di ritorno vuota significa che la query non ha avuto problemi): 

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;
}

Dato che nessuno lo ha ancora menzionato, darò un'altra frase per cercare: " modifica distanza " (ad esempio, testo del link ). Può essere usato per trovare le corrispondenze più vicine, supponendo che siano errori di battitura in cui le lettere vengono trasposte, mancanti o aggiunte.

Ma di solito questo è anche abbinato a una sorta di informazione di pertinenza; o per semplice popolarità (supporre che la corrispondenza abbastanza vicina usata più comunemente sia probabilmente la parola corretta), o per probabilità contestuale (parole che seguono la parola corretta precedente o che precedono una). Questo entra nel recupero delle informazioni; un modo per iniziare è guardare bigram e trigrammi (sequenze di parole viste insieme). Google ha set di dati molto ampi e liberamente disponibili per questi.

Per una semplice soluzione iniziale, sebbene una coppia di dizionari con abbinamenti basati su Levenshtein funzioni sorprendentemente bene.

Potresti collegare Lucene, che ha una funzione di dizionario che implementa il metodo della distanza Levenshtein.

Ecco un esempio dal Wiki, dove 2 è la distanza. 

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

Se hai un dizionario memorizzato come trie, esiste un modo abbastanza semplice per trovare le voci con la corrispondenza migliore, in cui i caratteri possono essere inseriti, eliminati o sostituiti. 

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);
}

L'idea è che prima lo chiami con un budget pari a zero e vedi se stampa qualcosa. Quindi prova un budget di 1 e così via, fino a quando non stampa alcune partite. Maggiore è il budget, maggiore è il tempo impiegato. Potresti voler aumentare fino a un budget di 2.

Aggiunto: non è troppo difficile estenderlo per gestire prefissi e suffissi comuni. Ad esempio, prefissi inglesi come " un " ;, " anti " e "dis" può trovarsi nel dizionario e può quindi ricollegarsi all'inizio del dizionario. Per suffissi come "ism", "s", "e" ed "; può esserci un trie separato contenente solo i suffissi e la maggior parte delle parole può collegarsi a quel suffisso. Quindi può gestire strane parole come "quotazionalizzazione antinazionale".

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top