(Modification le 28/2/2012: modif du code de la classe Compfr pour éviter des problèmes d'encodage dans le reste du code)
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 ):
on va créer une méthode de comparaison qui pourra être utilisée dans les arguments de la méthode sort:
import locale class Compfr(object): """comparaison de 2 chaines selon le dictionnaire français""" def __init__(self, decod='utf-8'): self.decod = decod self.loc = locale.getlocale() # stocker la locale courante 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'') locale.setlocale(locale.LC_ALL, '') comp = locale.strcoll(v1, v2) locale.setlocale(locale.LC_ALL, self.loc) #retour à la locale courante return comp # retour du résultat de la comparaison
Et voilà comment on va l'utiliser:
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
Ce qui donne à l'exécution (et qui est l'ordre correct):
pèche PÈCHE pêche PÊCHE péché PÉCHÉ pécher pêcher
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:
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
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.
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.
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']
NB: u'\xA0' est l'espace insécable.
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:
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
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:
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
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.
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]
Dans cette fonction, les paramètres en entrée sont les suivants:
Cette fonction renvoie une liste de 2 valeurs:
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
En cas de doublon dans la liste:
Attention, le mot cherché n'est pas corrigé par key: il faut le corriger vous-même avant l'appel!
Dans une liste indexée triée, on va utiliser la même recherche par dichotomie:
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]
Ce qui est le résultat correct donné par [0, 3]:
Avec Python 3.x, on utilise la même formule.
Amusez-vous bien!