Come faccio a confrontare le frasi per la somiglianza?

Question

Quando inserisci una domanda, StackOverflow ti presenta un elenco di domande che ritiene possano coprire lo stesso argomento.Ho visto funzionalità simili su altri siti o anche in altri programmi (file system della Guida, ad esempio), ma non ho mai programmato qualcosa di simile personalmente.Ora sono curioso di sapere che tipo di algoritmo si utilizzerebbe per questo.

Il primo approccio che mi viene in mente è dividere la frase in parole e cercare frasi che contengono queste parole.Prima di farlo, probabilmente vorrai eliminare parole insignificanti (come "il", "a", "fa" ecc.) e poi classificare i risultati.

Ehi, aspetta, facciamolo per le pagine web e poi possiamo avere un...guardaamachiamala...- un "motore di ricerca", e poi possiamo vendere annunci, e poi...

No, sul serio, quali sono i modi comuni per risolvere questo problema?

Answer 1

Un approccio è il cosiddetto modello del sacco di parole.

Come hai indovinato, per prima cosa conti quante volte le parole compaiono nel testo (di solito chiamato documento nel gergo della PNL).Quindi butti via le cosiddette stopword, come "il", "a", "o" e così via.

Ti rimangono le parole e il conteggio delle parole.Fatelo per un po' e otterrete un insieme completo di parole che appariranno nei vostri documenti.È quindi possibile creare un indice per queste parole:"aardvark" è 1, "apple" è 2, ..., "z-index" è 70092.

Ora puoi prendere i tuoi sacchetti di parole e trasformarli in vettori.Ad esempio, se il tuo documento contiene due riferimenti per aardvarks e nient'altro, sarebbe simile a questo:

[2 0 0 ... 70k zeroes ... 0].

Dopodiché puoi contare l '"angolo" tra i due vettori con un prodotto scalare.Quanto più piccolo è l'angolo, tanto più vicini saranno i documenti.

Questa è una versione semplice e ci sono altre tecniche più avanzate.Possa il Wikipedia sia con te.

Answer 2

@Hanno dovresti provare l'algoritmo della distanza di Levenshtein.Data una stringa di input S e un elenco di stringhe T ripetere per ogni stringa tu In T e restituire quello con la distanza minima di Levenshtein.

http://en.wikipedia.org/wiki/Levenshtein_distance

Vedi un esempio di implementazione Java in http://www.javalobby.org/java/forums/t15908.html

Answer 3

Per aumentare l'idea del sacco di parole:

Ci sono alcuni modi in cui puoi prestare attenzione agli n-grammi, stringhe di due o più parole tenute in ordine.Potresti voler farlo perché la ricerca di "complessità spaziale" è molto più che una ricerca di cose che contengono "spazio" E "complessità", poiché il significato di questa frase è più della somma delle sue parti;cioè, se ottieni un risultato che parla della complessità dello spazio esterno e dell'universo, probabilmente non è questo ciò che realmente significava la ricerca della "complessità spaziale".

Un'idea chiave dell'elaborazione del linguaggio naturale qui è quella di informazioni reciproche, che ti consente (algoritmicamente) di giudicare se una frase è davvero una frase specifica (come "complessità spaziale") o solo parole che sono casualmente adiacenti.Matematicamente, l’idea principale è chiedersi, probabilisticamente, se queste parole appaiono una accanto all’altra più spesso di quanto si indovinerebbe solo dalla loro frequenza.Se vedi una frase con un punteggio elevato di informazione reciproca nella tua query di ricerca (o durante l'indicizzazione), puoi ottenere risultati migliori cercando di mantenere queste parole in sequenza.

Answer 4

Dalla mia (piuttosto piccola) esperienza nello sviluppo di motori di ricerca full-text:Cercherei le domande che contengono alcune parole della query (nel tuo caso, query è la tua domanda).Certo, le parole non significative dovrebbero essere ignorate e potremmo voler controllare la query per parole "forti" come "ASP.Net" per restringere l'ambito della ricerca.http://en.wikipedia.org/wiki/Index_(search_engine)#Inverted_indices'>Gli indici invertiti sono comunemente usati per trovare domande con parole che ci interessano.

Dopo aver trovato le domande con le parole della query, potremmo voler calcolare la distanza tra le parole che ci interessano nelle domande, quindi la domanda con il testo "somiglianza di frasi" si classifica più in alto della domanda con il testo "discussione di somiglianza, senti le seguenti frasi...".