Come si implementa un "Intendevi dire"?[duplicare]

https://stackoverflow.com/questions/41424

09-06-2019
|

Domanda

Possibile duplicato:
In che modo il Google "intendevi?" Algoritmo lavoro?

Supponiamo che tu abbia già un sistema di ricerca nel tuo sito web.Come puoi implementare la frase "Intendevi dire:<spell_checked_word>"come fa Google in alcuni query di ricerca?

Soluzione

In realtà ciò che fa Google non è banale e anche a prima vista controintuitivo.Non fanno nulla come controllare un dizionario, ma piuttosto utilizzano le statistiche per identificare query "simili" che hanno restituito più risultati della tua query, l'algoritmo esatto ovviamente non è noto.

Ci sono diversi sottoproblemi da risolvere qui, come base fondamentale per tutte le statistiche relative all'elaborazione del linguaggio naturale è necessario avere un libro: Fondamenti dell'elaborazione statistica del linguaggio naturale.

Concretamente per risolvere il problema della somiglianza di parole/query ho ottenuto buoni risultati con l'utilizzo Modifica distanza, una misura matematica della somiglianza delle stringhe che funziona sorprendentemente bene.Usavo Levenshtein ma potrebbe valere la pena esaminarli.

Soundex, secondo la mia esperienza, è una schifezza.

In realtà, archiviare e cercare in modo efficiente un ampio dizionario di parole con errori di ortografia e avere il recupero in meno di un secondo non è banale, la soluzione migliore è utilizzare i motori di indicizzazione e recupero del testo completo esistenti (ad es.non quello del tuo database), di cui Lucene è attualmente uno dei migliori e, guarda caso, portato su molte piattaforme.

Altri suggerimenti

Il dottor Norvig di Google ha illustrato come funziona;fornisce anche un'implementazione Python di circa 20 righe:

http://googlesystem.blogspot.com/2007/04/simplified-version-of-googles-spell.html

http://www.norvig.com/spell-correct.html

Il dottor Norvig discute anche del "volevi dire" in questo eccellente discorso.Il dottor Norvig lo è capo della ricerca presso Google: alla domanda su come viene implementato "volevi dire?", la sua risposta è autorevole.

Quindi si tratta del controllo ortografico, presumibilmente con un dizionario dinamico creato da altre ricerche o anche da frasi Internet reali e simili.Ma questo è ancora controllo ortografico.

SOUNDEX e altre ipotesi non danno un'occhiata, gente!

Controllo Questo articolo su Wikipedia sulla distanza di Levenshtein.Assicurati di dare un'occhiata ai possibili miglioramenti.

Sono rimasto piacevolmente sorpreso che qualcuno abbia chiesto come creare un sistema di suggerimenti ortografici all'avanguardia per i motori di ricerca.Lavoro su questo argomento da più di un anno per una società di motori di ricerca e posso indicare informazioni di pubblico dominio sull'argomento.

Come accennato in un post precedente, Google (e Microsoft e Yahoo!) non utilizzano alcun dizionario predefinito né impiegano orde di linguisti che riflettono sui possibili errori di ortografia delle query.Ciò sarebbe impossibile a causa della portata del problema ma anche perché non è chiaro se le persone possano effettivamente identificare correttamente quando e se una query è scritta in modo errato.

Esiste invece un principio semplice e piuttosto efficace che vale anche per tutte le lingue europee.Ottieni tutte le query univoche nei tuoi log di ricerca, calcola la distanza di modifica tra tutte le coppie di query, presupponendo che la query di riferimento sia quella con il conteggio più alto.

Questo semplice algoritmo funzionerà perfettamente per molti tipi di query.Se vuoi passare al livello successivo, ti suggerisco di leggere il documento di Microsoft Research su questo argomento.Puoi trovarlo Qui

Il documento ha un'ottima introduzione, ma dopo dovrai essere a conoscenza di concetti come il modello di Markov nascosto.

Suggerirei di guardare SOUNDEX per trovare parole simili nel tuo database.

Puoi anche accedere al dizionario di Google utilizzando il file Richiesta di suggerimento ortografico dell'API di Google.

Potresti dare un'occhiata a Peter Norvig "Come scrivere un correttore ortografico"articolo.

Credo che Google registri tutte le query e identifichi quando qualcuno apporta una correzione ortografica.Questa correzione può quindi essere suggerita quando altri forniscono la stessa prima query.Funzionerà per qualsiasi lingua, in effetti qualsiasi stringa di qualsiasi carattere.

http://en.wikipedia.org/wiki/N-gram#Google_use_of_N-gram

Penso che questo dipenda da quanto è grande il tuo sito web.Sulla nostra Intranet locale, utilizzata da circa 500 membri del personale, guardo semplicemente le frasi di ricerca che hanno restituito zero risultati e inserisco quella frase di ricerca con la nuova frase di ricerca suggerita in una tabella SQL.

Chiamo quella tabella se non vengono restituiti risultati di ricerca, tuttavia, funziona solo se il sito è relativamente piccolo e lo faccio solo per le frasi di ricerca più comuni.

Potresti anche voler dare un'occhiata alla mia risposta a una domanda simile:

Funzionalità simili a "Post simili" che utilizzano MS SQL Server?

Se disponi di traduzioni specifiche del settore, probabilmente avrai bisogno di un dizionario dei sinonimi.Ad esempio, ho lavorato nel settore della gioielleria e nelle nostre descrizioni c'erano abbreviazioni come kt - carati, rd - rotondo, cwt - peso in carati...Endeca (il motore di ricerca per quel lavoro) ha un dizionario dei sinonimi che traduce gli errori di ortografia più comuni, ma richiede un intervento manuale.

Lo faccio con Lucene'S Correttore ortografico.

Soundex è utile per le corrispondenze fonetiche, ma funziona meglio con i nomi delle persone (è stato originariamente sviluppato per i dati del censimento)

Controlla anche l'indicizzazione del testo completo, la sintassi è diversa dalla logica di Google, ma è molto veloce e può gestire elementi linguistici simili.

Soundex e "Porter stemming" (soundex è banale, non sono sicuro dello stemming di porter).

C'è qualcosa chiamato aspell che potrebbe aiutare:http://blog.evanweaver.com/files/doc/fauna/raspell/classes/Aspell.html

C'è una gemma di rubino per questo, ma non so come parlarci da Pythonhttp://blog.evanweaver.com/files/doc/fauna/raspell/files/README.html

Ecco una citazione dall'implementazione di Ruby

Utilizzo

Aspell ti consente di controllare le parole e suggerire correzioni.Per esempio:

  string = "my haert wil go on"

  string.gsub(/[\w\']+/) do |word|
    if !speller.check(word)
      # word is wrong
      puts "Possible correction for #{word}:"
      puts speller.suggest(word).first
    end
  end

Questo produce:

Possibile correzione per haert:Cuore possibile correzione per Wil:Volere

Implementare la correzione ortografica per i motori di ricerca in modo efficace non è banale (non puoi semplicemente calcolare la distanza di modifica/levenshtein per ogni parola possibile).Una soluzione basata sugli indici k-gram è descritta in Introduzione al recupero delle informazioni (testo completo disponibile online).

Potresti usare ngram per il confronto: http://en.wikipedia.org/wiki/N-gram

Utilizzando il modulo Python Ngram: http://packages.python.org/ngram/index.html

import ngram

G2 = ngram.NGram([  "iis7 configure ftp 7.5",
                    "ubunto configre 8.5",
                    "mac configure ftp"])

print "String", "\t", "Similarity"
for i in G2.search("iis7 configurftp 7.5", threshold=0.1):
    print i[1], "\t", i[0]

Ottieni:

>>> 
String  Similarity
0.76    "iis7 configure ftp 7.5"    
0.24    "mac configure ftp"
0.19    "ubunto configre 8.5"

Perché non usare Google, intendevi nel tuo codice. Per come vedi quihttp://narenonit.blogspot.com/2012/08/trick-for-using-googles-did-you-mean.html

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow