Newsgroup: it.comp.programmare
Titolo: Algoritmo sistema T9

Qualcuno sa dove posso trovare l'algoritmo per il sistema di scrittura
intuitiva degli sms denominato T9?
Grazie

 intuitiva degli sms denominato T9?
sinceramente non so di preciso quale sia l'algoritmo, ma lo posso 
immaginare.
Supponi di avere una funzione "decode" che prende come parametro una 
stringa e restituisce un array: la stringa di input corrisponde alla 
sequenza di tasti premuta dall'utente, mentre l'array di output e` 
l'insieme di parole che potrebbero corrispondere alla sequenza digitata.
Ad esempio, alla sequenza di tasti "2426" corrispondo (perlomeno) le 
seguenti parole:
        ciao
        cibo
        aibo (il cane-robot giapponese ;-)
Ad ogni parola corrisponde anche una priorita`, in modo che le parole 
piu` comuni possano essere presentate prima di quelle rare.
A questo punto per il software il compito e` facile: basta chiamare la 
funzione decode e presentare all'utente le scelte presenti nell'array 
restituito, ordinate secondo la priorita`. Ovviamente il software puo` 
anche aggiornare le priorita` per adeguarsi alle abitudini dell'utente 
(se un mangione scrive "cibo" piu` spesso di quanto scriva "ciao" e` 
auspicabile che dopo un po' il telefono presenti "cibo" come prima 
scelta).
In C il tutto potrebbe apparire cosi`:
struct Word {
        char* str;
        int priority;
};
Word* decode(const char*)
{
...
}
per implementare la funzione decode mi vengono in mente almeno due 
possibilita`:
1) tabella hash
2) albero binario di ricerca
ciao Anto
-- 
Antonio Cuni, 19 anni, studente
Brainbench C++ Master: 4.73, higher than 99% of all previous test takers.
C Language: 3.79, higher than 92% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it

 intuitiva degli sms denominato T9?
http://www.t9.com/t9_faqs.html
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 l'insieme di parole che potrebbero corrispondere alla sequenza digitata.
mumble... direi che perň in questo modo fai molti calcoli in piů che 
potresti risparmiarti. Penso che usando una struttura dati come una trie 
sia tutto molto piů semplice e veloce da gestire in tempo reale.
Maurizio

Cosa č una trie ?
Mi potresti dare qualche suggerimento per mettermi sulla strada giusta?
Grazie
"Maurizio Sambati" <gsm...@NOSPAMinwind.it> ha scritto nel messaggio
news:MPG.17433d876...@news.tin.it...


 Mi potresti dare qualche suggerimento per mettermi sulla strada giusta?
http://www.nist.gov/dads/HTML/trie.html
in sostanza poniamo di avere un dizionario: (per comodità lo faccio con 
poche parole)
mela
melo
mare
pera
adesso traduciamo queste parole in codici che vanno digitati con la 
tastiera del cellulare:
6352 - mela
6356 - melo
6273 - mare
7372 - pera
e formiamo la trie... dunque i nodi di una trie saranno più o meno così:
struct nodo 
{
  nodo *figli[9];
  int parola;
}
diamo un valore di -1 a parola per i nodi che non contengono nessuna 
parola, gli altri valori fanno riferimento ad un array contenente tutte 
le parole del nostro dizionario:
const char *parole[] = { "mela", "melo", "mare", "pera" };
quindi vediamo di costruire la trie in questo modo partendo dalla radice 
ovvero prendiamo un codice, creiamo un nodo per ogni suo carattere 
ricorsivamente così:
node *curr = radice_trie;
for( char *s = stringa_codice; *s; ++s )
{
  int cifra = ( int )( *s - '0' );
  if( !curr->figlio[cifra - 1] )
    curr->figlio = crea_nodo();
  curr = curr->figlio[cifra];
}
curr->parola = indice_parola;
(codice non testato, potrei aver scritto cazzate)
spero sia chiaro dato che normalmente non so spiegarmi.
Adesso devi solo gestire la collisione di più parole con lo stesso 
codice ("casa" e "bara", per esempio potresti fare in modo che l'array 
del dizionario sia di liste concatenate che poi contengono le stringe) e 
il riempimento della parola in tempo reale (che immagino avrai già 
capito come fare: basta scorrere la trie, se ti trovi in un nodo senza 
parole allora potresti fare una ricerca in ampiezza e scrivere una parte 
della prima parola trovata; nota che NON ti puoi trovare in un nodo che 
non fa parte di una parola, altrimenti hai sbagliato qualcosa)
Maurizio

 Mi potresti dare qualche suggerimento per mettermi sulla strada giusta?
Probabilmente, la cosa piu' efficiente da fare e' utilizzare
un database (il sistema T9 utilizza un db, anche se supercompattato).


 trie sia tutto molto piů semplice e veloce da gestire in tempo reale.
penso che tu abbia quotato male: mi sembra che il tuo commento sia piu` 
adatto alla mia ultima osservazione (implementare decode tramite un 
albero o una hash table), non al fatto di scrivere una funzione decode 
(che potrebbe essere implementata con un trie). A dire il vero non avevo 
neppure pensato al trie...
Detto questo, se ho capito il senso della tua osservazione, posso dirti 
che potresti avere ragione, ma prima bisogna fare un po' di conti.
[ nota: in ogni caso un trie occupa molto piu` spazio in RAM che non un 
albero o una hash table e quindi potrebbe non essere praticabile in un 
ambiente di risorse limitate come quello di un cellulare ]
chiamiamo N il numero di parole nel vocabolario e L la lunghezza della 
parola cercata. Le complessita` computazionali delle ricerche dovrebbero 
essere (a meno di errori):
        albero: O(L * lgN)
        trie:   O(L)
        hash:   come la complessita` della funzione di hash, tipicamente O(L)
dato che in genere L e` molto piccolo possiamo considerare la prima come 
O(lgN) e le altre due costanti.
A questo punto, guardando le complessita` e la nota precedente mi 
sentirei di consigliare la hash table, dato che sembra avere combinati i 
vantaggi del trie (veloce) e dell'albero (poca RAM occupata). Pero` c'e` 
un ultima considerazione da fare: tipicamente il programma dovra` 
effettuare delle ricerche in serie con queste chiavi:
        "2" (premo c)
        "24" (premo i)
        "242" (premo a)
        "2426" (premo o)
Un albero o un trie permettono di ottimizzare queste situazioni, in 
quanto per trovare "2426" possiamo gia` utilizzare la posizione trovata 
cercando "242", e cosi` via. Viceversa, usando una hash table dovremmo 
ogni volta eseguire la funzione di hash sul nuovo input.
Dal punto di vista pratico immagino che cmq la tabella hash sia ancora 
in vantaggio, dato che le chiavi sono molto brevi, ma dal punto di vista 
teorico mi pare un problema interessante.
Pero` forse c'e` un modo di salvare capra e cavoli: se riusciamo a 
formulare una buona funzione di hash con questo prototipo:
        size_t hash(size_t old_hash, char new_char);
che sia "ricorsiva":
        hash("") == x
        hash(x, "c") == y // calcola hash("c")
        hash(y, "i") == z  // calcola hash("ci")
        // ecc.
potremmo sfruttare il valore hash calcolato in precedenza per calcolare 
quello nuovo (che e` solo un carattere piu` lungo).
A questo dobbiamo anche aggiungere la possibilita` che l'utente cancelli 
un carattere, ma adesso e` tardi e devo andare...


 quello nuovo (che e` solo un carattere piu` lungo).
mumble... però c'è un altro problema, che è quello che mi fa sbilanciare 
sulle trie: la parola incompleta dovrebbe pur essere scritta. Se con 242 
non esistono parole nel vocabolario, con le hash che scrivi? 
Probabilmente "aga" ma non è elegante (perchè noi vogliamo essere 
eleganti, altrimenti possiamo pure fare una brutale query di ricerca in 
un db e lasciare il tutto nelle mani del db...). Con le trie nell'ultimo 
mio post ho suggerito una ricerca in ampiezza finchè non troviamo una 
parola, quindi sostituiamo le 3 lettere digitate con le prime 3 lettere 
della parola.
Maurizio

 prime 3 lettere della parola.
beh, ti potrei rispondere: se non hai 1 mega e mezzo nel quale mettere 
la trie quali alternative hai? :-))
Si, in effetti la soluzione proposta da te ha questo vantaggio, ma non 
credo che per l'utente sia un vantaggio determinante: se ci pensi quando 
scrivi un SMS hai gli occhi sulla tastiera e non sul display: usualmente 
guardi quest'ultimo solo quando hai finito di digitare la parola 
completa, e in questo caso il software avrebbe potuto visualizzare anche 
un'animazione di fuochi d'artificio ma non l'avresti vista ;-) 
(ovviamente era un "tu" impersonale - non so cosa cavolo fai quando 
scrivi SMS...).
Naturalmente e` possibilissimo che io abbia sbagliato i conti e/o le 
stime, quindi i risultati potrebbero anche non essere veritieri (e 
probabilmente non lo sono...)


 probabilmente non lo sono...)
Non sono giusti ma ci si avvicinano molto. (hai sbagliato i conti per il 
calcolo dell'occupazione della tabella di hash, poi non hai considerato 
la proprietà 17.4 del Sedgewick sugli alberi di Patricia, e poi... 
accidenti con puntatori a 16 bit a malapena ce le ficchi 50000 parole! 
:-) )
Ad ogni modo è ragionevole pensare che un cellulare usi la trie proprio 
per il comportamento che ti ho descritto (quando la parola non è 
digitata completamente), poi la memoria di sola lettura per ficcarci il 
vocabolario e la trie ce l'hanno quasi sicuramente. (alla fine il grosso 
è occupato dal vocabolario)
Maurizio
P.S. probabilmente anche l'autocompletamento con TAB che c'è in linux 
usa una trie.

 grosso è occupato dal vocabolario)
uhm... non credo. Se utilizziamo una memoria ROM perdiamo interessanti 
possibilita`:
1) non possiamo aggiornare le priorita` con cui devono comparire le 
parole
2) non possiamo inserire altre parole digitate frequentemente dall'utente
Sinceramente, in quanto utente, preferirei avere la (1) e la (2) 
piuttosto che vedere la parola che "magicamente compare man mano che 
pigio i tasti" ;-)
Concludo con una nota finale: e` incredibile quanto ci sia da scrivere 
su un argomento che probabilmente non interessa a nessuno e sul quale 
abbiamo le idee poco chiare... :-)))


 > grosso č occupato dal vocabolario)


 abbiamo le idee poco chiare... :-)))
Io non credo che non interessi a nessuno, ma sicuramente l'OP ha
bisogno di risposte e probabilmente lo state sballottando tra
complessita' computazionali e filosofie algoritmiche :)
Io credo che la cosa che bisogna riuscire a fare sia la ricerca
su un db di possibili parole, mediante chiave parziale.
Non credo che l'hash vada bene per questo.


 Non credo che l'hash vada bene per questo.
è quello che sostengo anche io, però era interessante vedere cosa le 
hash potessero fare anche in caso di "difficoltà".
Maurizio

 allore la tabelle hash o le Trie?
In tal caso le trie. (dato che non hai problemi di spazio)
Però dipende dalle dimensioni del dizionario: hai 16 bit di 
indirizzamento se non erro... quindi fatti un po' di conti. (il problema 
c'è anche con le hash)
Maurizio

 Cosa mi consigliate allore la tabelle hash o le Trie?
beh, se devi effettuare ricerche con chiavi parziali la tabella hash non 
va bene. Rimangono il trie e gli alberi binari: probabilmente il primo 
e` piu` veloce e il secondo piu` facile da implementare: vedi un po' tu.


 Non credo che l'hash vada bene per questo.
se la ricerca con chiave parziale e` uno dei requisiti del problema 
(come ha puntualizzato Ciobin) sicuramente la tabella hash non va bene 
ed e` meglio guardare altrove.
Personalmente non riterrei il completamento parziale una caratteristica 
*cosi`* utile, ma questo e` un altro discorso...


 caratteristica *cosi`* utile, ma questo e` un altro discorso...
In che senso ?
Se si vuol implementare la stessa logica alla base del T9 bisogna
necessariamente considerare gli sviluppi parziali.


 > Scusate, siete stati gentilissimi, ma il mio quesito è dovuto al fatto


 necessariamente considerare gli sviluppi parziali.
si, mi sono spiegato male; diciamo che se io dovessi progettare da zero 
un sistema per la composizione veloce degli SMS non metterei questa 
caratteristica tra le priorita`.


 caratteristica tra le priorita`.
Non capisco, il riscontro che dai ad un utente dopo la pressione 
di un tasto, quale sarebbe ?  L'utente deve capire se quello che
sta scrivendo e' cio' che vuole realmente scrivere...


 e' cio' che vuole realmente scrivere...
Spesso e volentieri, durante la composizione della parola, la
visualizzazione parziale e` molto diversa dalla parola che si vuole
ottenere, e penso che questo sia inevitabile non essendoci una
corrispondenza biunivoca tra combinazioni di tasti e parole corrette.
-- 
 Ciao, Bianco.
 Reply to luca.bianco (at) 
tiscali.it

 arrivo.
potrei risponderti qui ma verrebbe un post lungo e poco comprensibile; 
cerca "alberi binari di ricerca" su un libro di algoritmi (o su google) 
e immagino che troverai molte info su quel che cerchi.


 ha scritto nel messaggio
news:abp3si$ce1$1...@newsreader.mailgate.org...


 corrispondenza biunivoca tra combinazioni di tasti e parole corrette.
Difatti e' quello che intendo anche io.  
Devi comunque dare riscontro, all'utente, di cio' che stai scrivendo.
La visualizzazione parziale potrebbe corrisponde tanto piu' alla 
parola reale che si vuol scrivere, quanto piu' e' lunga la parola.


 dati nel progetto T9.
Come mai hai scartato le trie? :-)
Maurizio

 sta scrivendo e' cio' che vuole realmente scrivere...
Si, ma in ogni caso spesso e volentieri non riuscirebbe a capirlo prima 
di finire di battere i tasti.
Se dovessi scrivere io il software e l'utente digitasse "2626#" potrebbe 
apparire, in sequenza "a", "am", "amt", "covo", "anto" (tralasciando il 
fatto che "amt" dovrebbe essere "bot")
In effetti l'utente non visualizza la parola sino a che non e` completa, 
ma non credo sia un problema: tanto, per "definizione", l'utente non 
puo` sapere se ha battuto i tasti giusti prima di averli battuti tutti; 
tornando all'esempio di prima, quali sarebbero i vantaggi di vedere 
apparire qualcosa del tipo "a", "am", "cov", "covo", "anto"?
Supponi di sbagliare a premere il terzo tasto e di digitare "2676"; con 
il "mio" metodo vedresti "a", "am", "amp", "coro"; con il "tuo" vedresti 
"a", "am", "cor", "coro".
Ora, come fa uno a capire "a pelle" di aver sbagliato perche` vede 
"cor"? E come farebbe a capire di aver scritto giusto vedendo "cov"?
ciao Anto
-- 
Antonio Cuni, 20 anni, studente


 organizzare i dati nel progetto T9.
potrebbe essere qualcosa del genere (commenti in stile C++):
const N= ....;
type 
        Dictionary = array[1..N] of string; // le parole del dizionario
        PtrNode = ^Node;
        Node = record
                code: string; // il codice tipo "2426"
                word: longint; // l'indice della parola all'interno del dizionario
                left, right: PtrNode; // i figli dell'albero
        end;
Ovviamente devi tenere il tuo albero ordinato secondo la chiave "code".
ciao Anto
-- 
Antonio Cuni, 20 anni, studente


 capirlo prima di finire di battere i tasti.
A parte che non capisco quale sia il tuo criterio per stabilire se
una parola e' terminata e in base a cosa, a quel punto, la fai
vedere... in base alla digitazione dello spazio ? della virgola ?
del punto ?  se e' l'ultima ? A parte il fatto che la parola non 
cambia di molto, quanto piu' si allunga, perche' non e' frequente 
trovare parole molto diverse, con un prefisso uguale .... a parte 
tutto questo, quello che voglio dire e' che man mano che scrivo voglio 
avere un riscontro a video, perche' potrei persino, a un certo punto, 
scegliere la parola da scrivere da una lista che il cellulare mi 
presenta, in base al prefisso che ho gia' digitato (su molti cellulari,
premendo lo zero appare questa lista), il che mi evita di scrivere 
tutte le restanti lettere.


 "cor"? E come farebbe a capire di aver scritto giusto vedendo "cov"?
come fai a sapere con il tuo sistema se un codice anche se incompleto 
non porterà ad alcuna soluzione?
Come fai a dire che per esempio per 1111 non c'è nessuna parola 
associata (così come per ogni codice che abbia come prefisso 1111)?
Maurizio

 parola reale che si vuol scrivere, quanto piu' e' lunga la parola.
Fin qui ok, piu` e` lunga la combinazione e meno parole "buone"
corrispondenti ci sono. 


 "cor"? E come farebbe a capire di aver scritto giusto vedendo "cov"?
mmm... si`, sono d'accordo, ma penso che il vantaggio si avrebbe per errori
di battitura molto evidenti, ossia dove la distanza tra il numero digitato
errato e quello corretto sia abbastanza grande; se vedi una "b" dove
dovrebbe esserci una "t", magari ti accorgi che qualcosa non va`... oltre a
pensare di avere un principio di artrite, viste le dita non proprio dritte
:-). Forse la cosa e` un po' forzata, sono d'accordo, anche perche` penso
che la maggior parte della gente non guardi gran che il display mentre
scrive... controlla ogni tanto il risultato.


 visualizzare "amt".
rispondo a te ma credo che questo post possa chiarire le idee anche ad 
Andrea e Maurizio.
Ovviamente (forse non era tanto ovvio, visto che non l'ha capito nessuno 
:-)) io mi riferivo al caso in cui la ricerca nella struttura dati non 
porta ad alcun risultato.
I casi sono due:
1) la ricerca nella struttura dati porta ad un risultato; viene 
visualizzata la parola con priorita` maggiore. Questo mi pare assodato e 
non era su questo che discutevo.
2) la ricerca non porta ad alcun risultato (stavamo discutendo di questo 
caso); le opzioni sono "visualizzazione parziale di una parola con quel 
prefisso" o "visualizzazione senza un particolare senso".
Nel caso di "262" dicevo che avrebbe dovuto essere "bot" perche` 
quest'ultima e` una parola esistente e quindi cadiamo nel caso 1 
anziche` nel 2; avevo ignorato l'esistenza di "bot" perche` altrimenti 
l'esempio era senza senso :-)
ciao anto


 tutte le restanti lettere.
questa e` una opzione a cui non avevo pensato e potrebbe essere 
interessante.
Anche se IMHO mi da' l'idea che sia piu` il tempo passato a premere 0, 
scorrere la lista e scegliere la parola piuttosto che non scrivere la 
parola tutta intera.


 non porterà ad alcuna soluzione?
non lo sai. Infatti se non trovi nulla di esatto visualizzi 
semplicemente le prime lettere di ogni tasto battuto.


 Nel caso di "262" dicevo che avrebbe dovuto essere "bot" perche` 
               ^^^
Ehm... "268", no?
Ok, cmq tutto chiaro.
