Trier des strings UTF8

Version imprimable

20/03/2011, 18h42
devroot

Trier des strings UTF8

Bonjour,

J'ai des paires (mot, nombre) rangées dans un dictionnaire que j'essaie de trier
par ordre alphabétique.

Or, ces morts comportent des accents (à, é, ô, etc.) qui ne sont pas du tout pris en compte.

J'ai adapté mon locale en "fr.FR", j'ai aussi tenté de sortir d'abord les données dans une liste pour voir si c'était plus facile avec un sort().

Mais je n'arrive pas à trier mes données.
Quelqu'un a une idée???
20/03/2011, 20h03
tyrtamos

Bonjour,

Précise un peu plus ce que tu veux trier: donne un exemple simplifié 'avant' et 'après'.

A noter qu'un dictionnaire 'normal' (dict) ne peut être trié. Dans les dernières versions de Python, il existe cependant un tel dictionnaire

Précise aussi quel version de Python: 2.x ou 3.x?

Tyrtamos
21/03/2011, 01h04
dividee
C'est à ça que sert strcoll dans le module locale:
Code:

1 2 3 4 5 6 7 8 l = ['bec','bébé','bijou'] l.sort() print l # pas bon import locale locale.setlocale(locale.LC_ALL, '') l.sort(cmp=locale.strcoll) print l # bon
On peut aussi utiliser strxfrm:

Code:

l.sort(key=locale.strxfrm)

Mais ça bug en unicode en Python 2.x (http://bugs.python.org/issue2481).
21/03/2011, 13h23
devroot
Bonjour !

Précision : mon dictionnaire contient des paires MOT / NOMBRE

Pour ce qui concerne le tri d'un dictionnaire, je crois que la fonction suivante fait ça plutôt bien à condition que l'on trie sur le nombre (d'oú l'inversion de la paire en ligne 2 de la fonction):
Code:

1 2 3 4 5 6 7 8 def SortNombre(Dico): Dico2 = Dico.items() Dico2 = [(v, k) for (k, v) in Dico2] Dico2.sort() Dico2.reverse() return Dico2
Mais, l'adaptation de cette fonction pour un tri sur le mot - comme suit - provoque une erreur de type "unhandled TypeError coercing to Unicode: need string or buffer, tuple found"
Code:

1 2 3 Dico2 = Dico.items() Dico2.sort(cmp=locale.strcoll)
Si je simplifie le sort, y'a plus de plantage mais évidemment ça ne trie pas correctement les lettres accentuées :
Code:

1 2 3 Dico2 = Dico.items() Dico2.sort()
21/03/2011, 14h46
tyrtamos

Désolé, mais je ne connais pas le type de dictionnaire 'Dico'.

Et le type normal 'dict' n'a pas de méthode sort().

???

Tyrtamos
21/03/2011, 15h00
devroot

Pardon, il manque une information :

Au preálable je déclare :
W ={}

puis j'appelle ma fonction comme suit :
Z = SortNombre(W):

Et là, ça me permet de récuperer le contenu du dictionnaire trié sur la valeur numérique
du plus grand au plus petit

ça y est, j'ai compris: tu ne cherches pas à trier le dictionnaire, mais la liste de listes [(clé, valeur), (clé, valeur), ...] obtenue avec sa méthode items().

Dans ce cas, c'est facile. Voilà un exemple:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 d = {'toto':4, 'titi':2, 'tata':7} print d {'titi': 2, 'toto': 4, 'tata': 7} L = d.items() print L [('titi', 2), ('toto', 4), ('tata', 7)] L.sort(key=lambda v: v[0]) print L [('tata', 7), ('titi', 2), ('toto', 4)]
La solution qui te manquait est l'argument: key=lambda v: v[0] qui veut dire "dans les comparaisons du tri, prendre v[0] au lieu de v". Par exemple, si v=('toto', 4), la comparaison se fera avec v[0]='toto'.

De la même façon, le tri avec les nombres se ferait avec key=lambda v: v[1]

Ok?

Tyrtamos

21/03/2011, 16h46
devroot
Top!
Merci tyrtamos !

En ajoutant l'information locale pour le tri des accents, ça marche au poil :
Code:

1 2 L.sort(key=lambda k: k[0], cmp=locale.strcoll)
MERCI BEAUCOUP !
21/03/2011, 17h27
tyrtamos

Ce problème étant résolu, il faut bien reconnaître que ce sont des tris qui ne font que respecter l'ordre des caractères dans les polices de caractères: les majuscules non accentuées (A..X), puis les minuscules non accentuées (a..x) puis les caractères accentués. Quant aux autres caractères non alphabétiques, ils sont situés avant ou après.

C'est à dire, par exemple: 'a' est après 'X', et 'à' est après 'x'

Bref, on est assez loin des tris français, même simplifiés comme on pourrait le souhaiter pour trier des noms de fichiers sous Windows. Et on est encore plus loin des tris de type 'dictionnaire français'. Il existe, bien sûr, des solutions, mais c'est un peu plus compliqué. Ce sont les besoins de l'application qui disent ce qui est supportable ou pas.

Tyrtamos
21/03/2011, 18h06
wiztricks

Salut,
Normalement, çà peut faire mieux que suivre l'ordre des caractères en fonction de leur valeur dans la police, sinon çà ne servirait pas à grand chose.
Mais c'est sujet à la définition du LC_COLLATE et aux éventuelles soucis dans l'interface Python/C.
note: Je n'ai toujours pas réussi ou pris le temps de à faire fonctionner Python comme C sur ces tris.
- W
21/03/2011, 19h37
tyrtamos

Bonjour wiztricks,

Citation:

Envoyé par wiztricks

Normalement, çà peut faire mieux que suivre l'ordre des caractères en fonction de leur valeur dans la police, sinon çà ne servirait pas à grand chose.
Mais c'est sujet à la définition du LC_COLLATE et aux éventuelles soucis dans l'interface Python/C.

Si tu as une solution avec LC_COLLATE pour redéfinir l'ordre des caractères pour le tri français, ça m'intéresse!

Actuellement, j'ai fait mes propres codes, qui me permettent de faire à peu près tout ce que je veux, mais ce n'est pas simple, et je préfèrerais une solution toute faite.

Je viens en particulier de terminer un code qui fait le vrai tri selon le dictionnaire français (algorithme ici: http://www-clips.imag.fr/geta/gilles...-francais.html), et qui se caractérise par certaines comparaisons entre les mots faites de droite à gauche.

Et je n'ai pas encore eu le courage de m'attaquer à la norme ISO 14651 (52 pages).

Tyrtamos
21/03/2011, 19h43
dividee
Citation:

Envoyé par tyrtamos

Ce problème étant résolu, il faut bien reconnaître que ce sont des tris qui ne font que respecter l'ordre des caractères dans les polices de caractères: les majuscules non accentuées (A..X), puis les minuscules non accentuées (a..x) puis les caractères accentués. Quant aux autres caractères non alphabétiques, ils sont situés avant ou après.

C'est à dire, par exemple: 'a' est après 'X', et 'à' est après 'x'

Bref, on est assez loin des tris français, même simplifiés comme on pourrait le souhaiter pour trier des noms de fichiers sous Windows. Et on est encore plus loin des tris de type 'dictionnaire français'. Il existe, bien sûr, des solutions, mais c'est un peu plus compliqué. Ce sont les besoins de l'application qui disent ce qui est supportable ou pas.

Tyrtamos

Je n'ai pas trop de problèmes avec strcoll (du moins en unicode):
Code:

1 2 3 4 5 >>> d = [u'êtr',u'ess',u'étu',u'd',u'f',u'Êta',u'Èl',u'ets'] >>> d.sort(cmp=strcoll) >>> for e in d: print e, ... d Èl ess Êta êtr ets étu f
(mon locale est fr-BE)

EDIT:
J'ai testé quelques exemples du lien que tu donnes; la plupart fonctionnent; seule la règle 4 semble poser problème.
Exemples testés:

Citation:

aA àÀ âà cC çÇ eE éÉ èÈ êÊ ëË
surélévation sûrement suréminent sûreté
cote côte Côte coté Coté côté Côté coter
cadurcien cæcum caennais cæsium cafard coercitif cœur
Problème:
vice-consul vice-président vice-roi vice-versa vice versa vicennal vicésimal

Bonjour dividee,

Prenons l'exemple:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 x = [X, e, a, x, à, E, A, é, è, â, ê, ë] x.sort() print x [A, E, X, a, e, x, à, â, è, é, ê, ë] import locale locale.setlocale(locale.LC_ALL, '') x.sort(key=locale.strxfrm) print x [a, A, à, è, â, ë, é, ê, e, E, x, X] # et la solution 'tri français' devrait être: [a, A, à, â, e, E, é, è, ê, ë, x, X]
On voit que la solution sort() n'est pas bonne. Et, finalement, la solution locale n'est pas mal, mais avec encore quelques bugs.

Et, bien que ce soit moins courant, quand on passe au tri selon le "dictionnaire français", ça se gâte un peu sur les exemples piégeux (ma référence pour l'algorithme = http://www-clips.imag.fr/geta/gilles...-francais.html):
Code:

1 2 3 4 5 6 7 8 9 10 11 x = [pèche, PÈCHE, pêche, PÊCHE, péché, PÉCHÉ, pécher, pêcher] la solution sort donne: [PÈCHE, PÉCHÉ, PÊCHE, pèche, pécher, péché, pêche, pêcher] la solution locale donne: [PÈCHE, pèche, péché, pécher, PÉCHÉ, pêche, pêcher, PÊCHE] et le résultat devrait être: [pèche, PÈCHE, pêche, PÊCHE, péché, PÉCHÉ, pécher, pêcher]
Tyrtamos

Bonsoir tyrtamos,

Je peux reproduire tes résultats, mais en passant en unicode j'obtiens le bon résultat (avec strcoll, pas strxfrm qui bugge)
Code:

1 2 3 4 5 >>> x = [u'pèche', u'PÈCHE', u'pêche', u'PÊCHE', u'péché', u'PÉCHÉ', u'pécher', u'pêcher'] >>> x.sort(cmp=strcoll) >>> for e in x: print e, ... pèche PÈCHE pêche PÊCHE péché PÉCHÉ pécher pêcher
On dirait que c'est un (autre) bug au niveau de strcoll/strxfrm...

[EDIT:] Non, il semblerait que ce soit simplement un problème d'encodage; locale pense que j'utilise la page de code 1252 alors que ce n'est pas le cas:
Code:

1 2 3 4 5 6 7 8 >>> locale.getlocale() ('French_Belgium', '1252') >>> x = [u'pèche', u'PÈCHE', u'pêche', u'PÊCHE', u'péché', u'PÉCHÉ', u'pécher', u'pêcher'] >>> x = [e.encode('1252') for e in x] >>> x.sort(cmp=strcoll) >>> for e in x: print e.decode('1252'), ... pèche PÈCHE pêche PÊCHE péché PÉCHÉ pécher pêcher

Waou, bravo dividee!

Effectivement, unicode + locale.strcoll donne le bon résultat!

Quand je pense que j'ai écrit un code de 125 lignes pour faire ça...

J'ai essayé d'autres jeux de test qui fonctionnent aussi:
Code:

1 2 3 4 5 6 7 x = [u'surélévation', u'sûrement', u'suréminent', u'sûreté'] x = [u'cote', u'côte', u'Côte', u'coté', u'Coté', u'côté', u'Côté', u'coter'] x = [u'élève', u'élevé'] x = [u'gène', u'gêne'] x = [u'MÂCON', u'maçon'] x = [u'relève', u'relevé', u'révèle', u'révélé']
Par contre, la prise en compte des caractères liés ('æ', 'œ') ainsi que celle des tirets et des espaces insécables sont encore faillibles:
Code:

1 2 3 4 5 6 7 8 x = [u'cadurcien', u'cæcum', u'caennais', u'cæsium', u'cafard', u'coercitif', u'cœur'] la solution 'locale' donne: [cadurcien, cæcum, caennais, cæsium, cafard, coercitif, cœur] et devrait donner: [cadurcien, caennais, cafard, coercitif, cæsium, cæcum, cœur]
Code:

1 2 3 4 5 6 7 8 x = [u'vice-consul', u'vicennal', u'vice-président', u'vice-roi', u'vicésimal', u'vice' + espinsec + u'versa', u'vice-versa'] la solution 'locale' donne: [vice-consul, vice-président, vice-roi, vice-versa, vice*versa, vicennal, vicésimal] et devrait donner: [vice-consul, vicennal, vice-président, vice-roi, vicésimal, vice versa, vice-versa]
Mais bon. Ne chipotons pas: le principal marche, et je sais ce qu'il faut ajouter pour faire fonctionner ces 2 derniers points!

Merci!

Tyrtamos

Edit: effectivement, mes 1ères anomalies devaient provenir de ce que mes chaines étaient en utf-8, alors que ma locale 'fr_FR' était en cp1252.

21/03/2011, 20h58
dividee

Pour les caractères liés, il me semble que c'est la solution 'locale' qui est juste...
21/03/2011, 21h10
tyrtamos

Citation:

Envoyé par dividee

Pour les caractères liés, il me semble que c'est la solution 'locale' qui est juste...

Je confirme, et c'est ce que mon programme avait trouvé aussi: il s'agit d'une simple erreur de copier-coller de ma part.

Donc: ça marche aussi pour les caractères liés.

Tyrtamos

Et voilà le code qui résout tous mes tests, y compris ceux concernant les tirets et les espaces insécables:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
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)

Utilisation:

Code:

1
2
3
4
5
6
7
 
x= [u'vice-consul', u'vicennal', u'vice-président', u'vice-roi', u'vicésimal', u'vice' +  u'\xA0' + u'versa', u'vice-versa']
 
compfr = Compfr()
x.sort(cmp=compfr)
print x
[u'vice-consul', u'vicennal', u'vice-président', u'vice-roi', u'vicésimal', u'vice versa', u'vice-versa']

Merci encore à dividee!

Tyrtamos