Outils pour utilisateurs

Outils du site


tris_alpha

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

Problématique

Trier des chaines de caractères avec Python, c'est facile avec la méthode sort() ou la fonction sorted(), mais l'ordre que vous obtenez n'est pas en général celui d'un tri alphabétique 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 trier des mots selon le dictionnaire français, et décrite par ailleurs sur ce site (http://python.jpvweb.com/mesrecettespython/doku.php?id=tris_dictionnaire_francais), mais ce n'est pas ça qu'on va faire ici. En effet, ce ne sont pas forcément des mots qu'on va chercher à trier, mais des chaines de caractères pouvant contenir des caractères non-alphabétiques dans les mots, comme des caractères de ponctuation, des espaces et des chiffres: on n'est plus dans un dictionnaire.

Comme exemple d'application pratique, pensez au tri des chemins de fichiers sur disque qui, sous Windows, peuvent comporter des espaces, des caractères accentués et autres caractères non-alphanumériques ('#_$&!\:.;?', etc…).

Codage de la fonction de comparaison

On va donc définir une méthode simplifiée pour la comparaison de 2 chaines de caractères:

  • on définit l'ordre des caractères souhaité dans une chaine de caractères de référence (appelée 'alpha' dans le code)
  • on fait la comparaison de 2 textes, caractère par caractère et de gauche à droite, en s'arrêtant au 1er caractère différent (ou au mot le plus court)

Les caractères qui ne sont pas dans la chaine de référence alpha auront pour rang dans la comparaison, la somme:

longueur de alpha + numéro d'ordre du caractère dans sa police 

Ce qui fait que les éventuels caractères non-français rencontrés seront tout de même traités, mais au delà des caractères français, et dans l'ordre qu'ils ont dans la police de caractère.

Comme le cmp() de Python, La fonction de comparaison prend 2 chaînes de caractères comme argument, et renvoie un nombre entier:

  • négatif si la 1ère chaîne est avant la seconde
  • nul si elles sont égales
  • positif si la 1ère chaîne est après la seconde

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

Voilà le code proposé:

#!/usr/bin/python
# -*- coding: utf-8 -*-
# Python 2.7
 
def compalphafr(v1,v2):
    """comparaison alphanumérique de v1 et v2: 
       renvoie un entier: <0 si v1<v2, 0 si v1==v2, et >0 si v1>v2
       v1 et v2 doivent être des chaines unicode
    """
    # correction de v1 et v2 pour les éventuelles voyelles liées (ligature)
    voylig1 = [u"Æ", u"Œ", u"æ", u"œ"]
    voylig2 = [u"AE", u"OE", u"ae", u"oe"]
    for i,c in enumerate(voylig1):
        v1 = v1.replace(c,voylig2[i])
        v2 = v2.replace(c,voylig2[i])
 
    # évaluation de l'ordre de v1 et v2 selon l'ordre des caractères de alpha
    alpha = ur""" !"#$%&'()*+,-./0123456789:;<=>?@[\]^_`{|}~""" + \
            u"\xA0" + \
            u"€aAàÀâÂäÄåÅæÆbBcCçÇdDeEéÉèÈêÊëËfFgGhHiIîÎïÏjJ" + \
            u"kKlLmMnNoOôÔöÖœŒpPqQrRsStTuUùÙûÛüÜvVwWxXyYÿŸzZ"
    lgalpha = len(alpha)
    lg1, lg2 = len(v1), len(v2)
    lg = min([lg1,lg2]) # 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 1ers car. sont identiques: le mot le plus court est avant
    return lg1-lg2

NB: le caractère u“\xA0” est l'espace insécable qui se trouve quelquefois dans les mots composés(comme vice versa).

Attention: les 2 textes à comparer v1 et v2 sont censés être encodés en unicode. Si ce n'est pas le cas, ou s'il y a mélange entre des 'str' et des 'unicode', il faut intégrer les conversions d'encodage. Pour cela, on va initialiser la méthode de comparaison en donnant l'encodage à utiliser, et donc la présenter sous forme de classe.

Et tant qu'à utiliser une classe, on peut faire mieux: se donner la possibilité de changer si nécessaire la chaine de référence alpha, ou même placer un drapeau pour accepter ou refuser les corrections des ligatures.

Voilà ce que ça donne:

class Compalphafr(object):
    """"Fonction de comparaison pour le tri alphanumérique français"""
 
    def __init__(self, decod='utf-8', alpha=None, ligature=True):
        # initialisation de la fonction de comparaison pour tri alpha
        self.decod = decod
        if alpha==None:
            self.alpha = ur""" !"#$%&'()*+,-./0123456789:;<=>?@[\]^_`{|}~""" + \
                u"\xA0" + \
                u"€aAàÀâÂäÄåÅæÆbBcCçÇdDeEéÉèÈêÊëËfFgGhHiIîÎïÏjJ" + \
                u"kKlLmMnNoOôÔöÖœŒpPqQrRsStTuUùÙûÛüÜvVwWxXyYÿŸzZ"
        else:
            self.alpha = alpha
        self.lgalpha = len(self.alpha)
        self.ligature = ligature
        self.voylig1 = [u"Æ", u"Œ", u"æ", u"œ"]
        self.voylig2 = [u"AE", u"OE", u"ae", u"oe"]
 
    def __call__(self, v1, v2):
        # convertir en unicode si nécessaire 
        if isinstance(v1, str):
            v1 = v1.decode(self.decod)
        if isinstance(v2, str):
            v2 = v2.decode(self.decod)
 
        # corriger les voyelles liées si demandé et si nécessaire
        if self.ligature:
            for i,c in enumerate(self.voylig1):
                v1 = v1.replace(c,self.voylig2[i])
                v2 = v2.replace(c,self.voylig2[i])
 
        # évaluer l'ordre de v1 et v2 selon l'ordre des caractères de alpha
        lg1, lg2 = len(v1), len(v2)
        lg = min([lg1,lg2]) # lg=longueur du mot le plus court entre V1 et v2
        for i in range(0,lg):
            i1 = self.alpha.find(v1[i])
            if i1<0:
                i1 = self.lgalpha + ord(v1[i])
            i2 = self.alpha.find(v2[i])
            if i2<0:
                i2 = self.lgalpha + ord(v2[i])
            if i1<i2:
                return -1
            if i1>i2:
                return 1
        # ici, les lg 1ers car. sont identiques: le mot le plus court est avant
        return lg1-lg2

Utilisation de la fonction de comparaison

Utilisons d'abord la 1ère solution: la fonction de comparaison. L'exemple est un extrait d'un répertoire de Python sous Windows, présenté en unicode:

L = [r"C:\Python27\Lib\SimpleHTTPServer.py".decode('utf-8'),
    r"C:\Python27\Lib\_LWPCookieJar.py".decode('utf-8'),
    r"C:\Python27\Lib\rfc822.py".decode('utf-8'),
    r"C:\Python27\Lib\_MozillaCookieJar.py".decode('utf-8'),
    r"C:\Python27\Lib\asyncore.py".decode('utf-8'),
    r"C:\Python27\Lib\BaseHTTPServer.py".decode('utf-8'),
    r"C:\Python27\Lib\io.py".decode('utf-8'),
    r"C:\Python27\Lib\zipfile.py".decode('utf-8'),
    r"C:\Python27\Lib\Queue.py".decode('utf-8'),
    r"C:\Python27\Lib\__future__.py".decode('utf-8'),
    r"C:\Python27\Lib\urllib2.py".decode('utf-8')]
 
L.sort(cmp=compalphafr)
for elem in L:
    print elem
 
C:\Python27\Lib\__future__.py
C:\Python27\Lib\_LWPCookieJar.py
C:\Python27\Lib\_MozillaCookieJar.py
C:\Python27\Lib\asyncore.py
C:\Python27\Lib\BaseHTTPServer.py
C:\Python27\Lib\io.py
C:\Python27\Lib\Queue.py
C:\Python27\Lib\rfc822.py
C:\Python27\Lib\SimpleHTTPServer.py
C:\Python27\Lib\urllib2.py
C:\Python27\Lib\zipfile.py

Ce qui est le résultat correct.

Les chemins auraient pu contenir des espaces, des caractères accentués, des chiffres et autres caractères non-alphanumériques($,%,#, etc…) pour autant, bien sûr, que ce soit permis par l'OS dans les chemins de fichiers sur disque.

Avec la comparaison sous forme de classe, l'utilisation est très peu différente.

Pour déclencher des conversions d'encodage, on va prendre ici les même chemins, mais écrits en encodage 'utf-8':

L = [r"C:\Python27\Lib\SimpleHTTPServer.py",
    r"C:\Python27\Lib\_LWPCookieJar.py",
    r"C:\Python27\Lib\rfc822.py",
    r"C:\Python27\Lib\_MozillaCookieJar.py",
    r"C:\Python27\Lib\asyncore.py",
    r"C:\Python27\Lib\BaseHTTPServer.py",
    r"C:\Python27\Lib\io.py",
    r"C:\Python27\Lib\zipfile.py",
    r"C:\Python27\Lib\Queue.py",
    r"C:\Python27\Lib\__future__.py",
    r"C:\Python27\Lib\urllib2.py"]
 
compalpha = Compalphafr('utf-8')
L.sort(cmp=compalpha)
 
C:\Python27\Lib\__future__.py
C:\Python27\Lib\_LWPCookieJar.py
C:\Python27\Lib\_MozillaCookieJar.py
C:\Python27\Lib\asyncore.py
C:\Python27\Lib\BaseHTTPServer.py
C:\Python27\Lib\io.py
C:\Python27\Lib\Queue.py
C:\Python27\Lib\rfc822.py
C:\Python27\Lib\SimpleHTTPServer.py
C:\Python27\Lib\urllib2.py
C:\Python27\Lib\zipfile.py

Ce qui donne, bien entendu, le même résultat. les chaines non-unicodes ont été simplement convertis en les supposant encodées en 'utf-8' comme demandé.

Dans des cas plus complexes, on pourrait changer la chaine de comparaison alpha, ou empêcher la correction des voyelles liées.

Avec la fonction sorted au lieu de la méthode sort, on fait, bien entendu la même chose.

Avec Python 3.x, l'argument 'cmp=' n'existe plus. On peut cependant utiliser encore la fonction de comparaison avec l'argument qui reste: 'key=', en utilisant la fonction cmp_to_key du module functools:

from functools import cmp_to_key
...
L.sort(key=cmp_to_key(compalphafr))
...

idem avec la comparaison sous forme de classe:

from functools import cmp_to_key
...
compalpha = Compalphafr()
L.sort(key=cmp_to_key(compalpha))
...

idem, enfin, avec la fonction sorted() au lieu de la méthode sort()

Codage des fonctions de conversion

On va définir ici plusieurs fonctions qui pourront corriger les chaines à comparer dans le tri avant leur comparaison. Par exemple passer de majuscules en minuscules ou vice versa, ou encore de supprimer tous les accents ou seulement les accents des majuscules : on pourra passer ces fonctions avec l'argument key de sort() ou sorted().

On peut passer facilement de minuscules en majuscules et vice versa avec les méthodes chaine.upper() et chaine.lower() car pour les polices de caractères ayant 8 bits (=hors 'ASCII'), elles utilisent la 'locale'. Si donc vous avez la locale française, vous pouvez faire facilement:

chaine = u"aAàÀâÂäÄåÅæÆbBcCçÇdDeEéÉèÈêÊëËfFgGhHiIîÎïÏjJkKlLmMnNoOôÔöÖœŒpPqQrRsStTuUùÙûÛüÜvVwWxXyYÿŸzZ"
 
print chaine
aAàÀâÂäÄåÅæÆbBcCçÇdDeEéÉèÈêÊëËfFgGhHiIîÎïÏjJkKlLmMnNoOôÔöÖœŒpPqQrRsStTuUùÙûÛüÜvVwWxXyYÿŸzZ
 
print chaine.lower()
aaààââääååææbbccççddeeééèèêêëëffgghhiiîîïïjjkkllmmnnooôôööœœppqqrrssttuuùùûûüüvvwwxxyyÿÿzz
 
print chaine.upper()
AAÀÀÂÂÄÄÅÅÆÆBBCCÇÇDDEEÉÉÈÈÊÊËËFFGGHHIIÎÎÏÏJJKKLLMMNNOOÔÔÖÖŒŒPPQQRRSSTTUUÙÙÛÛÜÜVVWWXXYYŸŸZZ

Vous constatez que les accentuations des voyelles sont conservés dans les conversions.

Cependant, la forme 'méthode' ne permet pas de passer directement dans le 'key' de sort(key=): il faut donner une forme de fonction avec lambda ou def.

Conversion des majuscules en minuscules en conservant les accentuations

def minusc(ch):
    """transforme les majuscules en minuscules en conservant l'accentuation"""
    return ch.lower()
 
print minusc(chaine)
aaààââääååææbbccççddeeééèèêêëëffgghhiiîîïïjjkkllmmnnooôôööœœppqqrrssttuuùùûûüüvvwwxxyyÿÿzz

Utilisation dans un tri alphanumérique français (avec le fonction compalphafr décrite plus haut):

...
L.sort(cmp=compalphafr, key=minusc)
...

Vous pourriez aussi faire:

...
L.sort(cmp=compalphafr, key=lambda ch: ch.lower())
...

Dans ce tri, les chaines à comparer par compalphafr seront d'abord converties par minusc avant la comparaison.

Conversion des minuscules en majuscules en conservant les accentuations

def majusc(ch):
    """transforme les minuscules en majuscules en conservant l'accentuation"""
    return ch.upper()
 
print majusc(chaine)
AAÀÀÂÂÄÄÅÅÆÆBBCCÇÇDDEEÉÉÈÈÊÊËËFFGGHHIIÎÎÏÏJJKKLLMMNNOOÔÔÖÖŒŒPPQQRRSSTTUUÙÙÛÛÜÜVVWWXXYYŸŸZZ

Utilisation dans un tri alphanumérique français (avec le fonction compalphafr décrite plus haut):

...
L.sort(cmp=compalphafr, key=majusc)
...

Vous pourriez aussi faire:

...
L.sort(cmp=compalphafr, key=lambda ch: ch.upper())
...

Dans ce tri, les chaines à comparer par compalphafr seront d'abord converties par majusc avant la comparaison.

Suppression des accents

On va utiliser le module unicodedata:

import unicodedata
 
def sansaccent(ch):
    """Supprime les accents sans changer la casse (majuscules et minuscules)"""
    chnorm = unicodedata.normalize('NFKD', unicode(ch))
    return u"".join([c for c in chnorm if not unicodedata.combining(c)])

Ce code est simple et fait très bien le travail, sauf sur un point: il remplace en plus les espaces insécables par des espaces normaux.

Si vous voulez, comme moi, garder les espaces insécables, voilà comment vous pouvez écrire la fonction définitive:

import unicodedata
 
def sansaccent(ch):
    """Supprime les accents sans changer la casse (majuscules et minuscules)"""
    r = u""
    for car in unicode(ch):
        if car==u"\xA0":
            r += car
        else:
            carnorm = unicodedata.normalize('NFKD', car)
            r += carnorm[0]
    return r       

Comment ça marche? C'est très simple:

  • si car est un caractère accentué, par exemple car='ê', unicodedata.normalize('NFKD', car) renvoie les 2 caractères: 'e' et '^'. Le caractère sans accent est le 1er caractère de la liste, d'où le “r += carnorm[0]”.
  • si car n'est pas caractère accentué, unicodedata.normalize('NFKD', car) se contente de le renvoyer et “r += carnorm[0]” marche aussi.

Exemple (avec la même chaine que précédemment):

print chaine
aAàÀâÂäÄåÅæÆbBcCçÇdDeEéÉèÈêÊëËfFgGhHiIîÎïÏjJkKlLmMnNoOôÔöÖœŒpPqQrRsStTuUùÙûÛüÜvVwWxXyYÿŸzZ
print sansaccent(chaine)
aAaAaAaAaAæÆbBcCcCdDeEeEeEeEeEfFgGhHiIiIiIjJkKlLmMnNoOoOoOœŒpPqQrRsStTuUuUuUuUvVwWxXyYyYzZ

Si on veut supprimer les accents seulement sur les majuscules, c'est facile aussi, à condition d'introduire une autre fonction du module unicodedata: une fois obtenu le caractère non accentué comme précédemment, on teste ce caractère avec unicodedata.category(carnorm[0]). S'il renvoie “Lu” (=Letter upercase), c'est une majuscule! Il suffit dans ce cas de renvoyer le caractère non accentué. Dans les autres cas, on renvoie le caractère d'origine.

def sansaccentmaj(ch):
    """Supprime les accents uniquement sur les majuscules"""
    r = u""
    for car in unicode(ch):
        if car==u"\xA0":
            r += car
        else:
            carnorm = unicodedata.normalize('NFKD', car)
            carcat = unicodedata.category(carnorm[0])
            if carcat==u'Lu':
                r += carnorm[0]
            else:
                r += car
    return r       

Exemple (avec la même chaine que précédemment):

print chaine
aAàÀâÂäÄåÅæÆbBcCçÇdDeEéÉèÈêÊëËfFgGhHiIîÎïÏjJkKlLmMnNoOôÔöÖœŒpPqQrRsStTuUùÙûÛüÜvVwWxXyYÿŸzZ
print sansaccentmaj(chaine)
aAàAâAäAåAæÆbBcCçCdDeEéEèEêEëEfFgGhHiIîIïIjJkKlLmMnNoOôOöOœŒpPqQrRsStTuUùUûUüUvVwWxXyYÿYzZ

Et, en ne changeant qu'un seul caractère dans la fonction précédente, on peut ne retirer les accents que dans les minuscules: il suffit de modifier la ligne "if carcat==u'Lu':" comme suit: "if carcat!=u'Lu':". Mais je ne vois pas d'application pratique…


On peut dès lors dans les tri utiliser ces fonctions de correction seules ou combinées avec les précédentes.

Par exemple: convertir en majuscules sans accent avant la comparaison:

...
L.sort(cmp=compalphafr, key=lambda ch: sansaccent(majusc(ch)))
...

Avec Python 3.x, comme l'argument cmp de sort n'existe plus, on va utiliser la fonction cmp_to_key du module functools pour utiliser la fonction de comparaison. Mais comme ici on va avoir en même temps une fonction de comparaison ET une fonction de conversion, ce sera un peu plus compliqué.

Par exemple, tri alphanumérique français avec la conversion majuscule sans accent:

...
L.sort(key=cmp_to_key(lambda v1,v2: compalphafr(sansaccent(majusc(v1)),sansaccent(majusc(v2)))))
...

Tri indexé alphanumérique 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:

L = [r"C:\Python27\Lib\SimpleHTTPServer.py".decode('utf-8'),
    r"C:\Python27\Lib\_LWPCookieJar.py".decode('utf-8'),
    r"C:\Python27\Lib\rfc822.py".decode('utf-8'),
    r"C:\Python27\Lib\_MozillaCookieJar.py".decode('utf-8'),
    r"C:\Python27\Lib\asyncore.py".decode('utf-8'),
    r"C:\Python27\Lib\BaseHTTPServer.py".decode('utf-8'),
    r"C:\Python27\Lib\io.py".decode('utf-8'),
    r"C:\Python27\Lib\zipfile.py".decode('utf-8'),
    r"C:\Python27\Lib\Queue.py".decode('utf-8'),
    r"C:\Python27\Lib\__future__.py".decode('utf-8'),
    r"C:\Python27\Lib\urllib2.py".decode('utf-8')]
 
ind = [i for i in xrange(0,len(L))] # permet d'avoir ind=[0,1,2,3,...]
ind.sort(cmp=compalphafr, 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 9 C:\Python27\Lib\__future__.py
1 1 C:\Python27\Lib\_LWPCookieJar.py
2 3 C:\Python27\Lib\_MozillaCookieJar.py
3 4 C:\Python27\Lib\asyncore.py
4 5 C:\Python27\Lib\BaseHTTPServer.py
5 6 C:\Python27\Lib\io.py
6 8 C:\Python27\Lib\Queue.py
7 2 C:\Python27\Lib\rfc822.py
8 0 C:\Python27\Lib\SimpleHTTPServer.py
9 10 C:\Python27\Lib\urllib2.py
10 7 C:\Python27\Lib\zipfile.py

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
...
ind.sort(key=cmp_to_key(lambda v1,v2: compalphafr(L[v1],L[v2]))) # c'est l'index que l'on trie!
...

Recherche rapide par dichotomie dans une liste triée

Il suffit d'adapter la fonction de recherche par dichotomie pour qu'elle accepte d'utiliser la méthode de comparaison définie ci-dessus. On peut y ajouter, si nécessaire, une fonction affectée à key pour corriger chaque chaine 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:

  • 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
  • =0 si v1==v2

Donc, pour les 2 valeurs de retour:

  • 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é x n'est pas corrigé par key: il faut le corriger vous-même avant l'appel! Par exemple si vous voulez chercher en majuscules sans accent avec la conversion key=lambda ch: sansaccent(majusc(ch)), la chaine à chercher x doit être passée en majuscule sans accent!

Exemple:

L = [r"C:\Python27\Lib\__future__.py".decode('utf-8'),
r"C:\Python27\Lib\_LWPCookieJar.py".decode('utf-8'),
r"C:\Python27\Lib\_MozillaCookieJar.py".decode('utf-8'),
r"C:\Python27\Lib\asyncore.py".decode('utf-8'),
r"C:\Python27\Lib\BaseHTTPServer.py".decode('utf-8'),
r"C:\Python27\Lib\io.py".decode('utf-8'),
r"C:\Python27\Lib\Queue.py".decode('utf-8'),
r"C:\Python27\Lib\rfc822.py".decode('utf-8'),
r"C:\Python27\Lib\SimpleHTTPServer.py".decode('utf-8'),
r"C:\Python27\Lib\urllib2.py".decode('utf-8'),
r"C:\Python27\Lib\zipfile.py".decode('utf-8')]
 
 
x = r"C:\PYTHON27\LIB\IO.PY".decode('utf-8')
print dichot(x, L, comp=compalphafr, key=lambda v: sansaccent(majusc(v)))
[0, 5]

Le résultat est correct: O indique que la chaine a été trouvé, et 5 qu'elle est à l'indice 5 de la liste triée.

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:

L = [r"C:\Python27\Lib\SimpleHTTPServer.py".decode('utf-8'),
    r"C:\Python27\Lib\_LWPCookieJar.py".decode('utf-8'),
    r"C:\Python27\Lib\rfc822.py".decode('utf-8'),
    r"C:\Python27\Lib\_MozillaCookieJar.py".decode('utf-8'),
    r"C:\Python27\Lib\asyncore.py".decode('utf-8'),
    r"C:\Python27\Lib\BaseHTTPServer.py".decode('utf-8'),
    r"C:\Python27\Lib\io.py".decode('utf-8'),
    r"C:\Python27\Lib\zipfile.py".decode('utf-8'),
    r"C:\Python27\Lib\Queue.py".decode('utf-8'),
    r"C:\Python27\Lib\__future__.py".decode('utf-8'),
    r"C:\Python27\Lib\urllib2.py".decode('utf-8')]
ind = [9,1,3,4,5,6,8,2,0,10,7]
 
x = r"C:\PYTHON27\LIB\IO.PY".decode('utf-8')
print dichot(x, ind, comp=compalphafr, key=lambda v: sansaccent(majusc(L[v])))
[0, 5]

Ce qui est le bon résultat: dans la liste triée indexée, avec une recherche en majuscules non accentuées, la chaine x est trouvée à l'indice 5 de l'index ind, c'est à dire à l'indice 6 (=ind[5]) de la liste non triée d'origine!

Avec Python 3.x, on utilise la même formule.

Tests de performances

Même si le tri utilisé (sort ou sorted) est très rapide, les fonctions de comparaison sont écrites en Python et analysent les chaines caractère par caractère: est-ce suffisamment rapide?

Pour le vérifier, on va créer des chaines au hasard, et on va compter les temps de tri.

Le nombre de chaines à créer est un paramètre. La longueur de chaque chaine est tirée au hasard entre 10 et 50 caractères. Et chaque caractère est tiré au hasard dans la chaine de référence alpha. Cela donne des chaines bizarres comme "+n?KMÏuK~fOA+$^-B Aå+ô)îg7mÊïbÇYè27Ÿ{x`Waks#iäïÏèp" mais qui conviennent parfaitement au test.

from time import clock
 
alpha = ur""" !"#$%&'()*+,-./0123456789:;<=>?@[\]^_`{|}~""" + \
        u"\xA0" + \
        u"€aAàÀâÂäÄåÅæÆbBcCçÇdDeEéÉèÈêÊëËfFgGhHiIîÎïÏjJ" + \
        u"kKlLmMnNoOôÔöÖœŒpPqQrRsStTuUùÙûÛüÜvVwWxXyYÿŸzZ"
lgalpha = len(alpha)
 
L = []
n = 1000
for i in xrange(0,n):
    lg = randint(10,50)
    ch = u""
    for j in xrange(0,lg):
        ch += alpha[randint(0, lgalpha-1)]
    L.append(ch)
 
t = clock()
L.sort(cmp=compalphafr)
t = clock()-t
 
print t

Résultats:

  • 1000 chaines à trier: 5/100 seconde
  • 10000 chaines à trier: 7/10 seconde
  • 100000 chaines à trier: 10 secondes
  • 1000000 chaines à trier: 2 minutes

Ce qui n'est pas mal du tout pour du code interprété.

Et pour la recherche dichotomique?

Prenons la dernière liste de 1000000 (un million) de chaines, et voyons le temps nécessaire pour trouver l'une des chaines x dans cette liste:

x = L[4999]
t = clock()
r = dichot(x, L, comp=compalphafr, key=None)
t = clock()-t
print r
print t

Le résultat correct [0,4999] est trouvé en… 2/10000 seconde! Ça vous suffira comme rapidité?


Amusez-vous bien!

tris_alpha.txt · Dernière modification: 2011/09/21 08:45 par tyrtamos

Outils de la page