Deprecated: Array and string offset access syntax with curly braces is deprecated in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/init.php on line 563
tris_dictionnaire_francais [Les recettes Python de Tyrtamos]

Outils pour utilisateurs

Outils du site


tris_dictionnaire_francais

Ceci est une ancienne révision du document !



Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/parser/handler.php on line 1458

Warning: preg_match(): Compilation failed: invalid range in character class at offset 3565 in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/parser/lexer.php on line 118
A PCRE internal error occured. This might be caused by a faulty plugin

====== Tri et recherche rapide selon le dictionnaire français ====== ===== Problématique ===== Trier des mots avec Python, c'est facile, mais l'ordre que vous obtenez n'est pas en général celui d'un dictionnaire français, mais celui de la police de caractères utilisée. Par exemple, la majuscule “X” se trouve **avant** la minuscule “a”. Quand aux caractères accentués, ils se trouvent derrière les minuscules non accentuées: 'à' est donc **après** 'x'… Il existe une méthode de base intégrée à Python pour faire ça. Je propose ici une adaptation un peu complétée qui répond à tous les cas que j'ai pu tester. Pour ces cas, j'ai pris comme référence l'excellent article suivant, qui traite des règles de tri des dictionnaires français (et un grand merci à nos cousins canadiens :-D ): * [[http://www-clips.imag.fr/geta/gilles.serasset/tri-du-francais.html]] ===== Code proposé pour le tri ===== on va créer une méthode de comparaison qui pourra être utilisée dans les arguments de la méthode sort: <code python> import locale class Compfr(object): def __init__(self, decod='utf-8'): self.decod = decod locale.setlocale(locale.LC_ALL, '') self.espinsec = u'\xA0' # espace insécable def __call__(self, v1, v2): # on convertit en unicode si nécessaire if isinstance(v1, str): v1 = v1.decode(self.decod) if isinstance(v2, str): v2 = v2.decode(self.decod) # on retire les tirets et les blancs insécables v1 = v1.replace(u'-', u'') v1 = v1.replace(self.espinsec, u'') v2 = v2.replace(u'-', '') v2 = v2.replace(self.espinsec, u'') # on retourne le résultat de la comparaison return locale.strcoll(v1, v2) </code> Et voilà comment on va l'utiliser: <code python> L = ['pèche', 'PÈCHE', 'pêche', 'PÊCHE', 'péché', 'PÉCHÉ', 'pécher', 'pêcher'] compfr = Compfr() L.sort(cmp=compfr) for mot in L: print mot </code> Ce qui donne à l'exécution (et qui est l'ordre correct): <code> pèche PÈCHE pêche PÊCHE péché PÉCHÉ pécher pêcher </code> Si on est dans Python 3.x, l'argument cmp de sort() n'existe plus, mais grâce à cmp_to_key du module functools, on peut encore utiliser la même méthode de comparaison avec l'argument 'key'. Il suffira d'écrire: <code python> from functools import cmp_to_key L = ['pèche', 'PÈCHE', 'pêche', 'PÊCHE', 'péché', 'PÉCHÉ', 'pécher', 'pêcher'] compfr = Compfr() L.sort(key=cmp_to_key(compfr)) for mot in L: print mot pèche PÈCHE pêche PÊCHE péché PÉCHÉ pécher pêcher </code> Tel que la classe Compfr() est définie, la liste est supposée être composée de mots encodés soit en unicode, soit en 'utf-8'. Si les mots non-unicode sont dans un autre encodage, on le donne à l'initialisation. Par exemple, si c'est 'cp1252' (=Windows), on écrit: compfr = Compfr('cp1252'). Dans tous les cas, les comparaisons sont faites en unicode. ===== Listes de test ===== Volà les listes utilisées pour les tests, issues de l'article de référence cité plus haut. Les mots se présentent déjà dans l'ordre correct, et le tri doit donc les renvoyer à l'identique. Mais rien ne vous empêche de changer l'ordre pour vérifier. <code python> L = [u'surélévation', u'sûrement', u'suréminent', u'sûreté'] L = [u'cote', u'côte', u'Côte', u'coté', u'Coté', u'côté', u'Côté', u'coter'] L = [u'élève', u'élevé'] L = [u'gène', u'gêne'] L = [u'MÂCON', u'maçon'] L = [u'pèche', u'PÈCHE', u'pêche', u'PÊCHE', u'péché', u'PÉCHÉ', u'pécher', u'pêcher'] L = [u'relève', u'relevé', u'révèle', u'révélé'] L = [u'cadurcien', u'cæcum', u'caennais', u'cæsium', u'cafard', u'coercitif', u'cœur'] L = [u'vice-consul', u'vicennal', u'vice-président', u'vice-roi', u'vicésimal', u'vice' + u'\xA0' + u'versa', u'vice-versa'] </code> NB: u'\xA0' est l'espace insécable. ===== Tri indexé selon le dictionnaire français ===== Dans ce cas, la liste initiale ne change pas, et on veut obtenir l'ordre du tri par l'intermédiaire d'un fichier d'index. Par exemple, le 3ème mot de la liste L sera trouvé grâce au fichier index ind, par L[ind[2]] et non L[2]. Voilà comment on trouve ce fichier d'index: <code python> L = [u'cæcum', u'cadurcien', u'cæsium', u'caennais', u'coercitif', u'cafard', u'cœur'] ind = [i for i in xrange(0,len(L))] # permet d'avoir ind=[0,1,2,3,...] compfr = Compfr() ind.sort(cmp=compfr, key=lambda v: L[v]) # c'est l'index que l'on trie! for i in xrange(0,len(L)): print i, ind[i], L[ind[i]] print 0 1 cadurcien 1 0 cæcum 2 3 caennais 3 2 cæsium 4 5 cafard 5 4 coercitif 6 6 cœur </code> Et le résultat affiché est bien l'ordre correct. Si on est avec Python 3.x, l'argument cmp n'existe plus et on utilise encore cmp_to_key du module functools: <code python> from functools import cmp_to_key L = [u'cæcum', u'cadurcien', u'cæsium', u'caennais', u'coercitif', u'cafard', u'cœur'] ind = [i for i in xrange(0,len(L))] # permet d'avoir ind=[0,1,2,3,...] compfr = Compfr() ind.sort(key=cmp_to_key(lambda v1,v2: compfr(L[v1],L[v2]))) # c'est l'index que l'on trie! for i in xrange(0,len(L)): print i, ind[i], L[ind[i]] print 0 1 cadurcien 1 0 cæcum 2 3 caennais 3 2 cæsium 4 5 cafard 5 4 coercitif 6 6 cœur </code> ===== Recherche rapide par dichotomie dans une liste triée selon le dictionnaire français ===== Il suffit d'adapter la fonction de recherche par dichotomie pour qu'elle accepte d'utiliser la méthode de comparaison “compfr(v1,v2)” définie ci-dessus. On peut y ajouter, si nécessaire, une fonction affectée à key pour corriger chaque donnée avant la comparaison. <code python> def dichot(x, L, comp=cmp, key=None): i, j = 0, len(L)-1 if key == None: key = lambda c: c if comp(x,key(L[j]))>0: return [1,j] while i!=j: k=(i+j)//2 if comp(x,key(L[k]))<1: j = k else: i = k+1 if comp(x,key(L[i]))==0: return [0, i] return [-1, i] </code> Dans cette fonction, les paramètres en entrée sont les suivants: * x = chaîne à rechercher * L = liste triée * cmp = fonction de comparaison à utiliser (**//qui doit être la même que celle qui a servi au tri!//**) * key = fonction de conversion utile à ce qu'on recherche Cette fonction renvoie une liste de 2 valeurs: * la 1ère est le critère de réussite * la 2ème est l'indice dans la liste. Le critère de réussite est analogue au résultat de la fonction intégrée cmp(v1,v2): <0 si v1<v2; >0 si v1>v2; et =0 si v1==v2 * Si la valeur x est trouvée dans la liste L, la fonction renvoie [0,i], i étant l'indice de la valeur trouvée dans L. * Si la valeur x ne se trouve pas dans la liste L: * si [-1,0] ⇒ la valeur cherchée x est inférieure à la valeur la plus petite de la liste * si [-1,i] avec i>0 ⇒ la valeur cherchée x se trouve entre la valeur d'indice i-1 et celle d'indice i * si [1,i] avec i==len(L)-1 ⇒ la valeur cherchée x est supérieure à la valeur la plus grande de la liste En cas de doublon dans la liste: * si on cherche le doublon et qu'on le trouve, on trouve celui d'indice le plus faible * si on cherche une valeur juste inférieure au doublon, on trouve aussi le doublon d'indice le plus faible Attention, le mot cherché n'est pas corrigé par key: il faut le corriger vous-même avant l'appel! ===== Recherche rapide par dichotomie dans une liste indexée triée ===== Dans une liste indexée triée, on va utiliser la même recherche par dichotomie: <code python> L = [u'cæcum', u'cadurcien', u'cæsium', u'caennais', u'coercitif', u'cafard', u'cœur'] ind = [1,0,3,2,5,4,6] print dichot(u"cæsium", ind, comp=compfr, key=lambda v: L[v]) [0, 3] </code> Ce qui est le résultat correct donné par [0, 3]: * 0 => le mot a été trouvé * 3 => il est là: L[ind[3]]=u'cæsium' Avec Python 3.x, on utilise la même formule. \\ Amusez-vous bien! <html> <head> <style type="text/css"> <!-- body {background-image:url(fondcorps.jpg);} --> </style> </head> <body> </body> </html>

tris_dictionnaire_francais.1316148625.txt.gz · Dernière modification: 2011/09/16 06:50 par tyrtamos

Outils de la page