Riconoscimento di nomi in una stringa

[ZioLuffio]

Sto cercando l'algoritmo migliore per il seguente problema:


In un forum, c'è una sezione dedicata alle partite tra gli utenti: significa che, dopo aver giocato una partita, un utente che ha giocato può aprire un thread riguardante la partita, dove può descrivere la partita, chi ha vinto et cetera.

I titoli dei thread, solitamente, sono qualcosa del tipo "Caio vs Sempronio", "SFIDA: Lc gino vs Ic luca - 3 partite", "dario imperator augustus ken sijhro vs dark warrior yaoming PaulMcartey".

I titolo dei thread sono ovviamente scelti dagli utenti, e non dagli amministratori del forum.

Dagli esempi che ho riportato prima, si possono leggere chi sono gli utenti che si sono scontrati: Caio contro Sempronio, LC_Gino contro IC_Luca (LC e IC sono dei tag che indicano il clan di appartenenza).
Nell'ultimo esempio i nickname sono Dario, Imperator_Augustus, KenShiro, Darkwarrior, Yao_ming, Paul_Mc_Cartney. Ho fatto apposta a scriverne alcuni sbagliati, facendo finta che sia un vero thread scritto da un vero utente, che può accidentalmente scambiare o dimenticare qualche lettera.

Ecco, ora vorrei realizzare un programma che, leggendo il titolo del thread, CAPISCA CHI SONO gli utenti che hanno giocato. Deve riuscire a capirlo anche nel caso che i nomi siano scritti sbagliati o abbreviati (es. DW = Darkwarrior, augusto, ken, paul mc). Ovviamente possono esserci utenti con nomi simili (es. Darkwarrior e DarkKnight).

Inoltre il programma non deve trovare i nomi esatti al 100%, perché i nomi trovati dal programma saranno verificati da un moderatore del forum, il quale potrà cambiare correggere i nomi non corrispondenti. L'esattezza ricercata è dell'80-90%. Il programma deve anche capire se alcune parole non corrispondono, negli esempi prima "Sfida", "3 partite", e anche "vs".

[bigdada]

io creerei un autocompilatore in modo che l'utente inizi a scrivere il nome e la pagina confronta quelli presenti in un database e suggerisce il finale della parola.
altrimenti potresti scompattare il nome inserito e salvarlo in un array, poi fai scorrere l'array e lo confronti con i nomi di un database.
in questo modo dovresti risolvere il problema per l'80%, in più potresti creare un controllo che legge il nome inserito e se non trova una corrispondenza chiede un reinserimento
spero di essere stato utile

[ZioLuffio]

Originariamente inviato da bigdada
io creerei un autocompilatore in modo che l'utente inizi a scrivere il nome e la pagina confronta quelli presenti in un database e suggerisce il finale della parola.
altrimenti potresti scompattare il nome inserito e salvarlo in un array, poi fai scorrere l'array e lo confronti con i nomi di un database.
in questo modo dovresti risolvere il problema per l'80%, in più potresti creare un controllo che legge il nome inserito e se non trova una corrispondenza chiede un reinserimento
spero di essere stato utile

Vagliando le tue proposte:
- Autocompilatore: no. Deve essere completamente trasparente all'utente, e poi troppo complicato perché dovrei usare Javascript.
- Reinserimento: no. La correzione viene fatta manualmente dai moderatori in seguito all'invio del post.
- Controllo in array: sì. L'algoritmo base va migliorato, per renderlo compatibile con scambi o dimenticanze di lettere, e per riconoscere le abbreviazioni. Inoltre va migliorato per nomi simili per scegliere che si avvicina di più a quello giusto.

[ZioLuffio]

Originariamente inviato da raven74
Il fatto è che tu hai anche un altro problema

Se hai un utente che si chiama Tizio, un altro che si chiama Caio e un terzo che si chiama Tizio Caio come fai a sapere con quali stringhe fare il paragone?

A parte il caso estremo, se hai letto quello che ho scritto, questo non è un problema, perché gli sbagli e le ambiguità sono ammessi, vanno solo limitati il più possibile.

Cmq grazie per la dritta, adesso proverò la funzione che mi hai indicato

[satifal]

Non si tratta solo di percentuali. Anche in caso di fallimento il codice di riconoscimento va comunque implementato.
Nell'esempio che hai fatto (es. DW = Darkwarrior) tanto per prenderne uno, individuare l'attinenza tra DW e Darkwarrior non è affatto facile. Un essere umano comprende facilmente che Darkwarrior, anche se scritto tutto attaccato, è in realtà l'unione delle parole Dark e warrior. Per implementare a codice questa cosa, però, occorrerebbe indiciduare tutte le parole che iniziano con le iniziali fornite e cercare di capire se sono perole di senso compiuto alle quali le iniziali possono far riferimento (e poi non è detto che in un nicknamen tutte le parole siano di senso compiuto).
In pratica la vedo davvero dura

[ZioLuffio]

Originariamente inviato da satifal
Non si tratta solo di percentuali. Anche in caso di fallimento il codice di riconoscimento va comunque implementato.
Nell'esempio che hai fatto (es. DW = Darkwarrior) tanto per prenderne uno, individuare l'attinenza tra DW e Darkwarrior non è affatto facile. Un essere umano comprende facilmente che Darkwarrior, anche se scritto tutto attaccato, è in realtà l'unione delle parole Dark e warrior. Per implementare a codice questa cosa, però, occorrerebbe indiciduare tutte le parole che iniziano con le iniziali fornite e cercare di capire se sono perole di senso compiuto alle quali le iniziali possono far riferimento (e poi non è detto che in un nicknamen tutte le parole siano di senso compiuto).
In pratica la vedo davvero dura

hai ragionissima su quel DW, infatti per le abbreviazioni credo sia meglio farlo almeno nel caso che le iniziali siano maiuscole tipo DW = DarkWarrior, o anche DW = dARKwARRIOR che cmq si capisce che sono diverse.


EDIT: CMQ ho provato la levenshtein() e fa abbastanza "schifo", o forse sono io che non ho capito come funziona invece fa molto meglio la funzione similar_text(), che forse riesco a usare insieme a un algoritmo che ho già creato

[ZioLuffio]

Ho deciso di prendere spunto dalle due funzioni levenshtein() e similar_text() e scrivere una funzione che calcoli il numero di modifiche che servirebbero per trasformare la stringa di ricerca nella stringa cercata, tenendo conto se la stringa cercata è inclusa all'interno della stringa analizzata: le possibilità diminuiscono se alcune lettere non sono trovate, se la stringa analizzata contiene un anagramma della stringa cercata, se le lettere trovate sono separate l'una dall'altra da caratteri che non c'entrano o se la stringa cercata è più lunga della stringa analizzata.

Suggerimenti?

[Emulman]

ma sei sicuro che non ci voglia HAL 9000? mi sembra terribilmente complicato....

[ZioLuffio]

Originariamente inviato da Emulman
ma sei sicuro che non ci voglia HAL 9000? mi sembra terribilmente complicato....

ahaha ma guarda che l'ho praticamente già fatto, solo che stavo usando un altro algoritmo che calcolava la probabilità in maniera sbagliata e inefficiente, devo solo risistemare quello

[Santino83_02]

Originariamente inviato da ZioLuffio
Suggerimenti?

di cambiare spacciatore

se l'utente ti scrive nel titolo "DW vs Strapippe" dove DW sta per "Dream Warrriors", mi spieghi te come fai a fare un algoritmo che dato Dw capisce Dream Warriors, piuttosto che DreamPippe, piuttosto che Dreamwarriors, piuttosto che Dayworld etc etc?

l'unica è avere una percentuale di attinenza tra DW e il valore nel db, da 100 a 0 %, che ottieni banalmente con le funzioni di match del database, e decidere se, in caso di match non uguale al 100%, scegliere il match a valore maggiore piuttosto che quello a valore inferiore... insomma, fare una cosa con una buona percentuale di errore. Altrimenti dire alla gente "mettete @nome_squadra" davanti al nome della squadra. levenshtein è presente anche come funzione in mysql se non erro