Riconoscimento di nomi in una stringa

[Luffio]

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".

[tdef]

Per prima cosa devi decidere una discriminante tra i due nomi, ad esempio vs (versus) può essere la discriminante, cioè l'identificatore che permette di dividere i nomi dei due contendenti e fino a qui è facile, lo decidi tu :) poi ovviamente puoi inserire più discriminanti ma non permettere agli utenti di poter scrivere questo valore se no non lo capirai più.
Poi immagino che i nomi degli utenti nascano da un database di iscritti al gioco e quindi è facile conoscere se "Ken Shiro" è diverso da KenShiro, il problema è che all'inizio puoi anche riuscire a gestire una funzione di "soundex" sui due nomi e trovare il "suono" in modo da decidere che i due nomi sono uguali, ma se in futuro permetti di iscriversi due o più Ken Shiro ti sarà impossibile discriminarli, infatti se permetti di iscriversi a: KenShiro, Ken Shiro, Ken-Shiro, Ken Shiro 1 non ci sarà funzione in grado di disstinguerli ma anzi con una soundex ti ritroverai con un caos di falsi positivi.
Secondo me la cosa migliore è modificare il gioco in modo che chi sceglie un nome lo fa per sempre e non lo cambia più e quando si iscrive ad una competizione sarà il sistema a gestirlo, come questo forum, mi iscrivo come TDef mi loggo come TDef e quando scrivo sul forum non è che cambio nome quando mi pare, rimango comunque TDef.
Ovviamente è possibile dare la possibilità di cambiarsi nome a volontà ad esempio mi iscrivo come TDef, mi loggo come TDef ma poi ho a disposizione un campo nome in cui posso scrivere che so Marco.
A quel punto il programma associa a TDef Marco, se domani lo cambio sempre TDef rimango. Mi segui?

[dreadnaut]

Fai il titolo a pezzi, elimini parole troppo corte o comuni, e per ogni parola restante usi levenshtein() per calcolare la distanza dai nomi degli utenti registrati.

Un po' costosa in termini di elaborazione, ma puoi probabilmente ottimizzare qua e la.

[tdef]

Si ma non risolve nulla se permette di scrivere nomi molto simili tra loro, rischia di far lavorare i moderatori come pazzi a correggere.

[dreadnaut]

Avere un limite "niente nomi troppo simili" all'iscrizione non è fattibile. Obbligheresti l'utente ad sbattersi prima ancora di essersi iscritto. Altre limitazioni sono ancora peggio.

Via distanza puoi ottenere una lista dei nomi più vicini possibili a quelli nella stringa in questione. Nella maggior parte dei casi, ci saranno uno o due nomi, quindi al massimo faciliti il lavoro dei moderatori mostrandogli solo validi candidati, anche se ci sono nomi molto simili.

Qualiasi algoritmo che legga del linguaggio naturale deve essere pronto a gestire imperfezioni e similitudini. Se vuoi evitare quel problema, devi evitare il linguaggio naturale, ad esempio creando un thread relativo ad ogni partita in automatico, appena conclusa.

[tdef]

A parte che lo sbattimento lo hai sempre, cioè voglio dire che fa parte della vita; se voglio crearmi un indirizzo email su un servizio pubblico ad esempio difficilmente lo troverò come lo voglio io perché sarà già stato preso da qualcun altro, è la norma.
Per questo ti avevo consigliato di inserire un campo libero nel database di login, tu ti iscrivi come dreadnaut ti logghi con lo stesso nome ma poi scrivi "Ivan il terribile" nel campo nome, solo che la macchina (il server) quando compila la statistica non fa affidamento sul campo libero ma sul login e il campo libero lo usa per mostrare il nome, così come l'hai scritto, quale che sia.
Cercare di creare un sistema di lettura del linguaggio naturale è molto complesso, non bastano metaphone o levenstein o soundex. Oddio puoi provarli e forse raggiungi il tuo scopo ma credo sia dura identificare la differenza tra ivano e ivan0 e soprattutto difficilmente comprenderà l'importanza di tale differenza, ma tu prova magari ti basta.

[dreadnaut]

Mi sembra che tu stia andando un po' agli estremi, senza sapere quale caso Luffio abbia davanti. E' facile che sia un forum con un migliaio di utenti, dove il problema dei nomi simili è minimo se non inesistente. E non ci vuole molto ad usare sia username che nome utente, è un falso problema.

Soundex e metaphone sono secondo me inadatti allo scopo: metaphone aspetta in parte una pronuncia inglese, soundex ha una bassa granularità, ed entrambi avrebbero grossi problemi con lo zero di ivan0. La distanza fra stringhe che ti restituisce levenshtein è più adatta per identificatori alfanumerici come questi.

Se poi vuoi andare all'assoluto hai perfettamente ragione, la vita è piena di problemi e ci sono solo soluzioni parziali. Solo che è un po' OT qua

[tdef]

Ma veramente le funzioni soundex eccetera le ho citate solo per dire che secondo me sono inutili.
Poi non è un problema di numeri di utenti ma di contesto, se crei un forum su Dragon ball con dieci utenti, ne sono sicuro che si iscriveranno almeno nove Dragonball in tutte le varianti del caso.