Discussion :

[lalystar]

Bonjour,

A propos de la distance de Levenshtein (Cf. http://www.developpez.net/forums/viewtopic.php?t=301478), j'aurais voulu savoir si c'est cet algorithme qui est utilisé pour l'envoi de SMS en mode T9 ?

Le mode T9 : chaque touche numérique du clavier du portable est "mappée" avec un ensemble de caractère (1 -> A, B, C, 2 -> D, E, F).

Quand on entre 1 1, le portable propose CA et ainsi de suite...

Quelqu'un connait-il un algorithme performant pour faire ce genre de matching ?


Laly.

[yann2]

bonjour,

C'est cool ça ! Mon projet d'algo était de simuler (un p'tit peu) le mode T9.
Par contre je ne connais pas la distance de Levenshtein.

Tous les mots sont stockés dans un arbre.

exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
                        #
                     /    \  
                    A      B
                   / \       \
                  N M        O
                 /    \        \
                E     E        N
               /      \        / \
              #       #       #  J
                                  \
                                   O
                                    \
                                     U
                                      \
                                       R
                                         \
                                         #

Dans cette exemple, chaque mot est terminé par un #
Tu peux également prendre la fréquence en compte en ajoutant un attribut à chaque noeud.

Ce n'est qu'une mini représentation. J'essaierai de retrouver le sujet de mon projet.

En espérant avoir à peu près répondu à la question, salut.

[lalystar]

Merci pour ta réponse.

Tu stockes vraiment les lettres dans l'arbre ou bien le numéro de la touche ?


Laly.

[Admin]

Il vaut mieux stocké le nom de la touche plutot que la lettre, car en T9 il faut appuyer 1 seule fois pour 1 lettre et donc avant que le mot soit fini on ne connais pas la lettre voulu par l'utilisateur.

D'autre part je ne pense pas que ce soit l'algo Levenshtein car il permet de comparer 2 mots finis, c'est utile dans le cas ou tu as un mot que tu ne connais pas à comparer avec ta référence de 20 mots pour trouver lequel convient le mieux (dico word par exemple ;-) )

Je pense qu'une modélisation arbraire est effectivement la solution, mais en stockant le numéro de la touche en associant evidemment la lettre en face.

Par exemple :

Imaginons que je veux taper "coût" (touche 2688) ces touches correspondent aussi à "bout" et "aout".

tu tape la touche 2, le système te propose "par défaut" la première lettre possible "A".

Ensuite tu tape 6, le système te propose la touche "N" car cela correspond à un mot fini. (AN)

ensuite tu tape 8 le système te propose "U" car cela correspond aussi à un mot fini. (COU) car 2 c'est également "C".

ensuite tu tape de nouveau 8 et le système te propose "B".
Là je bloque un peu sur la raison du B.

en tout cas on se rend bien compte que le sytème switch la première lettre et donc ce serait une erreur de la considérer comme acquise.

[yann2]

re,

en tout cas on se rend bien compte que le sytème switch la première lettre et donc ce serait une erreur de la considérer comme acquise.

exact.

Mais je pense quand même qu'il faut stocker les lettres dans l'arbre.

Appuie de la première touche
---> Liste chainée de toutes les lettres possibles.
Appuie sur la seconde touche
---> Chaque élément de la liste précédente possède un pointeur vers une liste chainée de toutes les lettres possibles.

et ainsi de suite.

Enfin, c'est un peu dur à expliquer comme ça. Il faudrait que je récupère mon rapport...

Pour info, j'ai réussi à récupérer le sujet du TP qui contient des éléments de réponse :
http://www.sciences.univ-nantes.fr/i...hing/sujet.pdf



bye.

[lalystar]

Merci beaucoup à vous deux pour vos explications, yann2 je vais regarder le sujet.


J'ai résolu le pb de l'arbre à ma facon (index sur une table Oracle ) mais je retiens le principe.

Je pensais que le T9 incluait une correction de frappe, c'est pour ca que lorsque j'ai entendu parler de la distance de Levenhstein j'avais pensé au T9 mais apparemment ce n'est pas le cas.


Laly.

[Admin]

non le T9 restreint juste les lettres affichées à des mots existants.