[ALGORITMO] "Forse cercavi..." di Google. Come funziona?

[longline]

Ciao a tutti!
Vorrei realizzare una funzionalità simile a quella che ha Google: quando si utilizza un termine, il sistema propone una o più alternative simili, o che possono far pensare che l'utente possa aver sbagliato a digitare.

A prescindere da esempi pratici di codice, voi avete un'idea di quale sia l'algoritmo che, confrontando la parola inserita con quelle già presenti nel sistema, valuti quelle simili?

Grazie mille!

[Ned Hanster]

penso che utilizzi un database delle parole piu ricercate, ma non so niente di sicuro

[longline]

Originariamente inviato da Ned Hanster
penso che utilizzi un database delle parole piu ricercate, ma non so niente di sicuro

Non credo, visto che sbagliando ortografia, ti propone la parola corretta.

Non solo, propone anche le ortografie corrette partendo da parole digitate in modo molto diverso:

Ad esempio, propone la grafìa "dostoevskij" anche se l'utente scrive "dostoieski"... potrebbe essere logico pensare che faccia un controllo sull'inizio parola, ma quando vedo che funziona anche con "tostoieski" e pure con "ostoieski" (!!!) mi rendo conto che è un algoritmo fatto molto bene!

Secondo voi come ragiona?

[LeleFT]

Hai anche un linguaggio di riferimento?
E' obbligatorio specificarlo nel titolo, ma non lo hai specificato nemmeno nella discussione.


Ciao.

[doraemon83]

Cerca gli algoritmi di String matching...

sono degli algoritmi che fanno un confronto tra due stringhe, di cui una è quella da te digitata e un'altra contenuta nel database. A ogni confronto associa un indice che rappresenta quanto la tua stringa corrisponde a quella del database.
Alla fine dei confronti ti propone la parola il cui confronto ha generato l'indice massimo...

ciao

[longline]

No, non mi interessa un linguaggio in particolare. Quello che mi interessa è l'algoritmo che sta alla base, non il codice.

Pensa che ho postato qui su suggerimento di un moderatore, perchè siccome la mia richiesta riguarda solo un ragionamento e non un codice per farlo, io avrei postato su OT.

[LeleFT]

Ok, allora modifico il titolo opportunamente.


Ciao.

[damj]

lcs è un algoritmo ( il cui pseudocodice trovi su un qualsiasi libro di algoritmi ) che calcola la lunghezza della sottostringa comune a due stringhe (mi pare sia l'acronimo di longest common string).Viene usato anche per confronti del dna o cose simili..restituisce un numero che è appunto la lunghezza della sottostringa comune alle due stringhe...fatto tra quello che digiti e le parole del database la più alta lcs fa riferimento alla stringa del database che scrive dopo "forse cercavi..."

[ab5000]

in php sono presenti alcune librerie per la verifica dell'ortografia, le aspell, eccole qui: http://it.php.net/manual/it/ref.aspell.php ce sono definite "deprecated", ora ci sono le pspell: http://it.php.net/manual/it/ref.pspell.php

ciao!