Warning: Undefined array key "DOKU_PREFS" in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/common.php on line 2082
tris_alpha [Les recettes Python de Tyrtamos]

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Piste:
tris_alpha

Warning: Undefined array key -1 in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/html.php on line 1458

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
Prochaine révision 		Révision précédente
tris_alpha [2011/09/18 10:06]
tyrtamos 		tris_alpha [2011/09/21 08:45]
tyrtamos
Ligne 5: Ligne 5:
 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'… 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 textes, et ceux-ci pourront contenir des caractères non-alphabétiques dans les mots, comme des caractères de ponctuation et des chiffres.+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...). 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...).
Ligne 12: Ligne 12:
  
 On va donc définir une méthode simplifiée pour la comparaison de 2 chaines de caractères:  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 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)   * 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)
  
Ligne 23: Ligne 21:
 </code> </code>
  
-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.+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.
  
-La fonction de comparaison prend 2 chaînes de caractères comme argument, et renvoie un nombre entier:+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   * négatif si la 1ère chaîne est avant la seconde
   * nul si elles sont égales   * nul si elles sont égales
Ligne 170: Ligne 168:
 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. 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 classe de comparaison, l'utilisation est très peu différente. On va prendre ici les même chemins, mais présentés en encodage 'utf-8':+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':
  
 <code python> <code python>
Ligne 201: Ligne 201:
 </code> </code>
  
-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'.+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. Dans des cas plus complexes, on pourrait changer la chaine de comparaison alpha, ou empêcher la correction des voyelles liées.
Ligne 311: Ligne 311:
 ==== Suppression des accents ==== ==== Suppression des accents ====
  
-On va créer une fonction de conversion:+On va utiliser le module unicodedata:
  
 <code python> <code python>
 +import unicodedata
 +
 def sansaccent(ch): def sansaccent(ch):
     """Supprime les accents sans changer la casse (majuscules et minuscules)"""     """Supprime les accents sans changer la casse (majuscules et minuscules)"""
-    alpha1 = u"àÀâÂäÄåÅçÇéÉèÈêÊëËîÎïÏôÔöÖùÙûÛüÜÿŸ" +    chnorm = unicodedata.normalize('NFKD', unicode(ch)) 
-    alpha2 = u"aAaAaAaAcCeEeEeEeEiIiIoOoOuUuUuUyY" +    return u"".join([c for c in chnorm if not unicodedata.combining(c)])
-    x = u"" +
-    for i,c in enumerate(ch): +
-        k = alpha1.find(c) +
-        if k>=0: +
-            x += alpha2[k] +
-        else: +
-            x += c +
-    return x    +
 </code> </code>
 +
 +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:
 +
 +<code python>
 +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       
 +</code> 
 +
 +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): Exemple (avec la même chaine que précédemment):
  
 <code python> <code python>
 +print chaine
 +aAàÀâÂäÄåÅæÆbBcCçÇdDeEéÉèÈêÊëËfFgGhHiIîÎïÏjJkKlLmMnNoOôÔöÖœŒpPqQrRsStTuUùÙûÛüÜvVwWxXyYÿŸzZ
 print sansaccent(chaine) print sansaccent(chaine)
 aAaAaAaAaAæÆbBcCcCdDeEeEeEeEeEfFgGhHiIiIiIjJkKlLmMnNoOoOoOœŒpPqQrRsStTuUuUuUuUvVwWxXyYyYzZ aAaAaAaAaAæÆbBcCcCdDeEeEeEeEeEfFgGhHiIiIiIjJkKlLmMnNoOoOoOœŒpPqQrRsStTuUuUuUuUvVwWxXyYyYzZ
 </code> </code>
  
-Si on veut supprimer les accents seulement sur les majuscules, c'est facile aussi:+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.
  
 <code python> <code python>
 def sansaccentmaj(ch): def sansaccentmaj(ch):
-    """Supprime les accents des majuscules uniquement""" +    """Supprime les accents uniquement sur les majuscules""" 
-    alpha1 = u"ÀÂÄÅÇÉÈÊËÎÏÔÖÙÛÜŸ" +    r = u"" 
-    alpha2 = u"AAAACEEEEIIOOUUUY" +    for car in unicode(ch): 
-    x = u"" +        if car==u"\xA0": 
-    for i,c in enumerate(ch): +            r += car
-        k = alpha1.find(c) +
-        if k>=0: +
-            x += alpha2[k]+
         else:         else:
-            x += c +            carnorm = unicodedata.normalize('NFKD', car) 
-    return x    +            carcat = unicodedata.category(carnorm[0]) 
 +            if carcat==u'Lu': 
 +                r += carnorm[0] 
 +            else: 
 +                r += car 
 +    return r       
 </code> </code>
  
Ligne 355: Ligne 376:
  
 <code python> <code python>
 +print chaine
 +aAàÀâÂäÄåÅæÆbBcCçÇdDeEéÉèÈêÊëËfFgGhHiIîÎïÏjJkKlLmMnNoOôÔöÖœŒpPqQrRsStTuUùÙûÛüÜvVwWxXyYÿŸzZ
 print sansaccentmaj(chaine) print sansaccentmaj(chaine)
 aAàAâAäAåAæÆbBcCçCdDeEéEèEêEëEfFgGhHiIîIïIjJkKlLmMnNoOôOöOœŒpPqQrRsStTuUùUûUüUvVwWxXyYÿYzZ aAàAâAäAåAæÆbBcCçCdDeEéEèEêEëEfFgGhHiIîIïIjJkKlLmMnNoOôOöOœŒpPqQrRsStTuUùUûUüUvVwWxXyYÿYzZ
 </code> </code>
  
 +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. 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:+Par exemple: convertir en majuscules sans accent avant la comparaison:
  
 <code python> <code python>
Ligne 454: Ligne 480:
   * x = chaîne à rechercher   * x = chaîne à rechercher
   * L = liste triée   * L = liste triée
-  * cmp = fonction de comparaison à utiliser (qui doit être la même que celle qui a servi au tri!)+  * 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   * key = fonction de conversion utile à ce qu'on recherche
  
Ligne 528: Ligne 554:
  
 Avec Python 3.x, on utilise la même formule. 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.
 +
 +<code python>
 +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
 +</code>
 +
 +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:
 +
 +<code python>
 +x = L[4999]
 +t = clock()
 +r = dichot(x, L, comp=compalphafr, key=None)
 +t = clock()-t
 +print r
 +print t
 +</code>
 + Le résultat correct [0,4999] est trouvé en... 2/10000 seconde! Ça vous suffira comme rapidité?
  
  
tris_alpha.txt · Dernière modification: 2011/09/21 08:45 de tyrtamos

Outils de la page

Sauf mention contraire, le contenu de ce wiki est placé sous les termes de la licence suivante : CC Attribution-Noncommercial-Share Alike 4.0 International
CC Attribution-Noncommercial-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki