Tri et recherche dans une liste selon l'alphabet français

Trier des mots ou des phrases 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 l'encodage ISO des caractères. Par exemple, la majuscule “X” se trouve avant la minuscule “a”. Quand aux caractères accentués…

Cela pose des problèmes divers, par exemple pour trier des noms de fichiers sous Windows.

Voilà comment on peut obtenir l'ordre qu'on veut. Il s'agit ici d'un modèle que vous pouvez facilement adapter en fonction de vos besoins.

Pour connaitre l'ordre à utiliser pour les caractères, je me suis inspiré d'articles concernant les règles de tri des dictionnaires français (et merci à nos cousins canadiens ):

• http://www-clips.imag.fr/geta/gilles.serasset/tri-du-francais.html
• http://jacques-andre.fr/faqtypo/unicode/alpha-fr.pdf

J'ai un peu simplifié certaines règles. Par exemple, je n'ai gardé que les règles qui nécessitent un test de gauche à droite.

J'ai aussi ajouté des caractères qui n'ont rien à faire dans un dictionnaire, mais qui peuvent être rencontrés dans d'autres utilisations: ”(”, “|”, ”#”, etc…). J'ai même ajouté un espace ainsi que des caractères de ponctuation, ce qui permettra de trier des phrases, et pas seulement des mots. En fait, vous pouvez ajouter ou pas ces caractères. Je les ai placé dans l'ordre où on les rencontre dans l'encodage UTF-8 (à part le sigle de l'euro “€” qui se trouve loin après les minuscules dans cet encodage: +20AC et que j'ai placé avant).

J'ai aussi considéré que les caractères inconnus en français et qui ne seraient pas dans la liste, seront rangés après les caractères français, selon leur code UTF-8. Cela permettra de traiter ponctuellement, et sans déclenchement d'exception, certains caractères étrangers (allemand, polonais, etc…). Mais selon vos besoins, rien ne vous empêche de les intégrer au bon endroit dans la liste.

La fonction la plus utile quand on parle de tri, c'est une fonction de comparaison qui prend 2 chaînes de caractères comme paramètres, et qui renvoie:

• un nombre négatif si la 1ère chaîne est avant la seconde

• 0 si elles sont égales

• un nombre positif si la 1ère chaîne est après la seconde

Ainsi, cette fonction pourra être utilisée simplement en la passant comme paramètre à la méthode “sort()”!

On verra aussi comment construire une fonction de recherche rapide par dichotomie dans une liste ainsi triée et qui utilisera cette même fonction.

Voilà le code proposé:

#!/usr/bin/python
# -*- coding: utf-8 -*-
 
def comp(v1,v2):
    """comparaison de v1 et v2: renvoie un entier <0 si v1<v2, 0 si v1==v2, un entier >0 si v1>v2"""
    alpha = ur"""!"#$%&'()*+,-./0123456789:;<=>?@""" + \
            ur"""[\]^_`""" + \
            ur"""{|}~ €""" + \
            ur"""aAàÀâÂæÆbBcCçÇdDeEéÉèÈêÊëËfFgGhHiIîÎïÏjJkKlLmMnNoOôÔœŒpPqQrRsStTuUùÙûÛüÜvVwWxXyYÿŸzZ"""
    lgalpha = len(alpha)
    lg1 = len(v1)
    lg2 = len(v2)
    lg = min([lg1,lg2]) # on veut lg=longueur du mot le plus court entre V1 et v2
    for i in range(0,lg):
        i1 = alpha.find(v1[i])
        if i1<0:
            i1 = lgalpha + ord(v1[i])
        i2 = alpha.find(v2[i])
        if i2<0:
            i2 = lgalpha + ord(v2[i])
        if i1<i2:
            return -1
        if i1>i2:
            return 1
    # ici, les lg premiers caractères sont identiques: le mot le plus court est avant l'autre 
    return lg1-lg2

Si dans les tri ou dans les recherches on veut passer de minuscules en majuscules ou le contraire, les fonctions intégrées dans Python (type “str.lower()”) ne conviendront pas pour les caractères accentués. On va donc créer ces fonctions de conversion de telle sorte qu'elles pourront servir en même temps dans les tris et dans les recherches.

def minusc(ch):
    """Convertit les majuscules (y compris accentuées) en minuscules (y compris accentuées)"""
    alphaminusc = u"aàâæbcçdeéèêëfghiîïjklmnoôœpqrstuùûüvwxyÿz"
    alphamajusc = u"AÀÂÆBCÇDEÉÈÊËFGHIÎÏJKLMNOÔŒPQRSTUÙÛÜVWXYŸZ"
    x = ""
    for i in range(0,len(ch)):
        k = alphamajusc.find(ch[i])
        if k>=0:
            x += alphaminusc[k]
        else:
            x += ch[i]
    return x

def minusc2(ch):
    """Convertit les majuscules (y compris accentuées) en minuscules (non accentuées)"""
    alphaminusc = u"aaaæbccdeeeeefghiiijklmnooœpqrstuuuuvwxyyz"
    alphamajusc = u"AÀÂÆBCÇDEÉÈÊËFGHIÎÏJKLMNOÔŒPQRSTUÙÛÜVWXYŸZ"
    x = ""
    for i in range(0,len(ch)):
        k = alphamajusc.find(ch[i])
        if k>=0:
            x += alphaminusc[k]
        else:
            x += ch[i]
    return x

def majusc(ch):
    """Convertit les minuscules (y compris accentuées) en majuscules (y compris accentuées)"""
    alphaminusc = u"aàâæbcçdeéèêëfghiîïjklmnoôœpqrstuùûüvwxyÿz"
    alphamajusc = u"AÀÂÆBCÇDEÉÈÊËFGHIÎÏJKLMNOÔŒPQRSTUÙÛÜVWXYŸZ"
    x = ""
    for i in range(0,len(ch)):
        k = alphaminusc.find(ch[i])
        if k>=0:
            x += alphamajusc[k]
        else:
            x += ch[i]
    return x

def majusc2(ch):
    """Convertit les minuscules (y compris accentuées) en majuscules (non accentuées)"""
    alphaminusc = u"aàâæbcçdeéèêëfghiîïjklmnoôœpqrstuùûüvwxyÿz"
    alphamajusc = u"AAAÆBCCDEEEEEFGHIIIJKLMNOOŒPQRSTUUUUVWXYYZ"
    x = ""
    for i in range(0,len(ch)):
        k = alphaminusc.find(ch[i])
        if k>=0:
            x += alphamajusc[k]
        else:
            x += ch[i]
    return x

Rien ne vous empêche d'en créer d'autres.

Par exemple, vous pouvez vouloir conserver les majuscules, mais convertir celles qui sont accentuées en majuscules non-accentuées:

def majuscnonaccent(ch):
    """Convertit les majuscules accentuées en majuscules non-accentuées"""
    alphamajusc1 = u"ÀÂÇÉÈÊËÎÏÔÙÛÜŸ"
    alphamajusc2 = u"AACEEEEIIOUUUY"
    x = ""
    for i in range(0,len(ch)):
        k = alphamajusc1.find(ch[i])
        if k>=0:
            x += alphamajusc2[k]
        else:
            x += ch[i]
    return x

Une fois cette fonction de comparaison “comp(v1,v2)” faite, pour trier une liste “L” selon l'ordre de tri alphabétique français, il suffit de faire ceci:

L.sort(comp)

Si vous voulez que le tri soit fait sans tenir compte des majuscules, par exemple, il suffit d'ajouter la fonction de conversion qui convient. Cette fonction sera appliquée aux chaînes de caractères de la liste avant les comparaisons nécessaires au tri:

L.sort(comp, minusc)

La fonction sort() trie la liste “sur place, et donc la modifie. Si vous ne voulez pas la modifier, vous pouvez utiliser la fonction sorted() qui utilise les mêmes arguments:

R = sorted(L, comp, minusc)

Simple, non?

Il suffit d'adapter la fonction de recherche par dichotomie pour qu'elle accepte d'utiliser la fonction de comparaison “comp(v1,v2)” définie ci-dessus, ainsi que, si nécessaire, les fonctions de conversion.

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:

• 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

Bien entendu, on peut utiliser cette fonction de recherche par dichotomie sans passer comme paramètre de fonction personnalisée cmp= ni key=. Dans ce cas, ce sont les valeurs par défaut qui seront prises (et qui ne donnent pas de bons résultats pour les caractères accentués).

Cette fonction renvoie une liste de 2 valeurs. La 1ère est le critère de réussite, et 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

En ce qui concerne les fonctions de comparaison et de conversion, elles sont identiques à celle qu'on utilise avec les fonctions sort() et sorted(). Seule différence, la fonction éventuellement affectée à key ne corrige que l'élément de la liste, parce que nous avons pleine maitrise de la présentation de la valeur à chercher x et que ce serait une perte de temps de faire cette correction sur x à chaque comparaison.

Ce code utilise les fonctions dichot() et comp() définies plus haut.

alpha = ur"""!"#$%&'()*+,-./0123456789:;<=>?@""" + \
        ur"""[\]^_`""" + \
        ur"""{|}~ €""" + \
        ur"""aAàÀâÂæÆbBcCçÇdDeEéÉèÈêÊëËfFgGhHiIîÎïÏjJkKlLmMnNoOôÔœŒpPqQrRsStTuUùÙûÛüÜvVwWxXyYÿŸzZ"""
lgalpha = len(alpha)
 
# on fabrique une liste au hasard:
from random import *
L = []
n = 100 # nombre d'éléments de la liste à créer
for i in range(0,n):
    x = randint(1,12) # longueur du mot au hasard entre 1 et 12 caractères
    ch = ""
    for j in range(1,x+1):
        # on ajoute un caractère pris au hasard dans la chaine alpha
        ch += alpha[randint(0,lgalpha-1)]
    L.append(ch)
 
# on fait quelques modifs de cette liste pour appliquer certains tests
L[5] = L[6]
L[8], L[9] = L[8] + L[9], L[8]
 
# on affiche la liste créée:
for i in range(0,len(L)):
    print "%4d  => %s" % (i, L[i])
print
 
# on trie cette liste:
L.sort(comp)
 
# on affiche la liste ainsi triée
for i in range(0,len(L)):
    print "%4d  => %s" % (i, L[i])
print
 
# tests de recherche:
 
# on cherche une valeur qui se trouve déjà dans la liste:
# les 2 valeurs affichées doivent être les mêmes
v = L[7]
r,i = dichot(v,L,comp)
print v, i, L[i]
print
 
# on cherche une valeur qui se trouve entre 2 valeurs:
# la valeur cherchée doit se trouver entre les 2 dernières valeurs affichées
v = L[7] + "xxx"
r,i = dichot(v,L,comp)
print v, i-1, L[i-1], i, L[i]
print
 
# on cherche une valeur qui est avant la toute 1ère valeur:
# et on la trouve, sauf si la 1ère valeur de la liste (index=0) est déjà "!"
v = u"!"
r,i = dichot(v,L,comp)
print v, i, L[i]
print
 
# on cherche une valeur qui est après la toute dernière valeur:
# et on affiche l'index et la valeur précédente trouvée (en principe la dernière valeur de la liste)
v = u"ZZZZZZZZZZZZZZZZ"
r,i = dichot(v,L,comp)
print v, i, L[i]
print

Tant dans le tri que dans la recherche, on teste tout de même caractère par caractère: est-ce que c'est viable en tant que temps d'exécution?

Test avec une liste de 10000 (dix milles) valeurs prises au hasard:

• durée de tri: inférieur à la seconde

• durées de recherche d'une valeur quelconque dans la liste: de l'ordre de 2/1000 de seconde

Test avec une liste de 1000000 (un million) de valeurs prises au hasard:

• durée de tri: environ 2mn et 45 secondes (n'oubliez pas: les comparaisons sont faites caractère par caractère!)

• durées de recherche d'une valeur quelconque dans la liste: de l'ordre de 2/1000 de seconde (comme précédemment)

Qui a dit que le langage Python était lent?

Voilà le code de test utilisé (Ce code utilise les fonctions dichot() et comp() définies plus haut):

alpha = ur"""!"#$%&'()*+,-./0123456789:;<=>?@""" + \
        ur"""[\]^_`""" + \
        ur"""{|}~ €""" + \
        ur"""aAàÀâÂæÆbBcCçÇdDeEéÉèÈêÊëËfFgGhHiIîÎïÏjJkKlLmMnNoOôÔœŒpPqQrRsStTuUùÙûÛüÜvVwWxXyYÿŸzZ"""
lgalpha = len(alpha)
 
from random import *
import time
 
# on fabrique une liste au hasard:
L = []
n = 10000 # nombre d'éléments de la liste à créer
for i in range(0,n):
    x = randint(1,12) # longueur du mot au hasard entre 1 et 12 caractères
    ch = ""
    for j in range(1,x+1):
        # on ajoute un caractère pris au hasard dans la chaine alpha
        ch += alpha[randint(0,lgalpha-1)]
    L.append(ch)
 
# on fait quelques modifs de cette liste pour appliquer certains tests
L[5] = L[6]
L[8], L[9] = L[8] + L[9], L[8]
 
# on trie cette liste:
tps = time.clock()
L.sort(comp)
print u"durée de tri = ", time.clock()-tps
print
 
# tests de recherche:
 
# on cherche une valeur qui se trouve déjà dans la liste:
# les 2 valeurs affichées doivent être les mêmes
v = L[7]
tps = time.clock()
r,i = dichot(v,L,comp)
print  u"durée de recherche = ", time.clock()-tps
print v, i, L[i]
print
 
# on cherche une valeur qui se trouve entre 2 valeurs:
# la valeur cherchée doit se trouver entre les 2 dernières valeurs affichées
v = L[7] + "xxx"
tps = time.clock()
r,i = dichot(v,L,comp)
print   u"durée de recherche = ", time.clock()-tps
print v, i-1, L[i-1], i, L[i]
print
 
# on cherche une valeur qui est avant la toute 1ère valeur:
# et on la trouve, sauf si la 1ère valeur de la liste (index=0) est déjà "!"
v = u"!"
tps = time.clock()
r,i = dichot(v,L,comp)
print   u"durée de recherche = ", time.clock()-tps
print v, i, L[i]
print
 
# on cherche une valeur qui est après la toute dernière valeur:
# et on affiche l'index et la valeur précédente trouvée (en principe la dernière valeur de la liste)
v = u"ZZZZZZZZZZZZZZZZ"
tps = time.clock()
r,i = dichot(v,L,comp)
print   u"durée de recherche = ", time.clock()-tps
print v, i, L[i]

Amusez-vous bien!