faire des manipulations sur un texte

**debutante en galere** · 19/11/2009, 12h13

OK bon alors, j'ai tout repris depuis le début et finalement j'avais effectivement pas vu la réponse de valAa. J'ai bien compris!!! et ça marche!!!
159 mots n'apparaissent qu'une fois. Merci à tous!!!! je me penche sur la prochaine étape... Et à bientôt pour de futurs problèmes....

**eyquem** · 19/11/2009, 17h40

En écrivant hier «Le problème est posé mais pas circonscrit», je voulais dire qu'on n'avait pas fait le tour du problème de la définition de ce qui doit être considéré comme un mot dans un texte.
J'ai pensé que ce n'était pas le plus urgent à examiner parce que ça dépend de ce qu'on veut obtenir et que ce point pourrait être traité après avoir mis en place le squelette algorithmique.

**nardo47** · 19/11/2009, 18h29

Si je relis les messages, son entrée est une liste de mots, pas un texte entier...

La définition d'un mot dans un texte est intéressante, mais c'est de la surqualité par rapport à ce qu'elle cherche à faire... ou peut-être une réflexion en avance de phase.

**eyquem** · 19/11/2009, 19h16

Tout à fait, nardo47.

En fait mon message précédent est ce qui reste d'un plus long message que j'avais écrit en m'enferrant dans l'idée que l'algorithme qui a été proposé dans cette file était non seulement déficient au point de vue vitesse, mais même faux.

J'ai préféré éliminer les sottises que j'avais écrites dans ce long message parce que ce qui était faux c'était surtout mon mien code à moi que je m'avais écrit.

Il comportait
if texte.count(mot)==1:
au lieu de
if liste_de_mots.count(mot)==1:

Alors évidemment, une chaîne comme 'barque' qui apparaissait en tant que mot dans un texte et en tant que chaîne au sein d'autres mots comme 'embarquement' ou 'barquette' était comptabilisée plusieurs fois.

Donc il ne reste plus de ce long message précédent que son début que je voulais compléter par ce qui suit.

En écrivant « l'objectif est perdu de vue », je pensais aussi que la question initiale était de trouver un nombre de mots à occurence unique, et non pas d'en faire la liste, et qu'on pouvait faire un code déterminant ce nombre sans construire cette liste ni même un dictionnaire recensant le nombre d'occurences de chaque mot avant d'y compter ceux d'occurence 1.

Le principe de ce code est le suivant: reproduire la façon de procéder d'une personne ayant à traiter ce problème, à savoir:
- examiner les mots les uns après les autres
- pour chaque mot, déterminer s'il se trouve dans la suite de la chaîne qui lui succède; cette suite est de plus en plus courte à mesure qu'on avance dans le texte
- si on ne trouve pas le mot dans la suite du texte après lui, il est d'occurence unique

Mais ce n'est pas aussi facile à mettre ceci en code que je le croyais, parce qu'on ne peut pas en réalité calquer exactement le fonctionnement d'un programme sur celui d'une personne.

Cependant, bien que le code donné plus haut soit juste dans son principe, aux problèmes de ponctuation près, il reste tout à fait insuffisant en terme de performance. Or on ne peut pas envisager se contenter d'un code insuffisant s'il s'agit d'étudier les mots à occurence unique dans "Guerre et Paix"

Je veux donc écrire les quelques codes dont j'ai l'idée et comparer leurs vitesses. Je pense qu'un code avec count() peut être 50 ou 100 fois plus lent qu'un code avec un dictionnaire.

J'ai aussi pensé à l'utilisation d'une fonction génératrice avec yield, comme fred1599, je suis curieux de voir si elle sera plus rapide qu'un algorithme avec dictionnaire.

**fred1599** · 19/11/2009, 19h48

Mais ce n'est pas aussi facile à mettre ceci en code que je le croyais, parce qu'on ne peut pas en réalité calquer exactement le fonctionnement d'un programme sur celui d'une personne.

La dessus je suis d'accord avec toi, et c'est pourquoi même si c'est très lent, le module re est bien.

J'ai aussi pensé à l'utilisation d'une fonction génératrice avec yield, comme fred1599, je suis curieux de voir si elle sera plus rapide qu'un algorithme avec dictionnaire.

Sans nul doute je pense que yield est le plus optimisé des codes.

Cependant, bien que le code donné plus haut soit juste dans son principe, aux problèmes de ponctuation près

Faut pas oublier que l'input est une liste.

**eyquem** · 19/11/2009, 20h05

Faut pas oublier que l'input est une liste.

Ah mais tout à fait. J'ai du mal à m'y faire, moi. J'ai un neurone qui a laché ou quoi ?

**eyquem** · 22/11/2009, 14h40

Voici plusieurs algorithmes qui répondent tous à la demande énoncée:
déterminer le nombre de mots à occurences uniques et leur pourcentage dans un texte,
à partir de la liste des mots dans le texte

J'ai isolé chaque algorithme dans une fenêtre-code pour que ce soit bien clair

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
def par_count(limots):
    return sum(limots.count(mot)==1 for mot in limots)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
def par_human_like(limots):
    compteur = 0
    vus = set([])
    for i,mot in enumerate(limots):
        if mot not in vus:
            if mot not in limots[i+1:]:
                compteur += 1
            vus.add(mot)
    return compteur

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
def par_dico_update(limots):
    d = {}
    [ d.update(((mot,mot not in d),)) for mot in limots ]
    return sum(d.itervalues())

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
def par_sorting_et_groupby(limots):
    limots.sort()
    return sum( 1 for k,g in groupby(limots) if sum(1 for u in g)==1)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
def par_sorting_et_yielding(limots):
    def avance(li,k=1):
        a = li[0]
        for u in li[1:-1]:
            if u==a:  k = 0
            else:
                yield k
                a,k = u,1     
    limots.sort()
    return sum( avance(limots) ) + (limots[-1]!=limots[-2])

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
def par_defaultdict(limots):
    d = defaultdict(int)
    for mot in limots:
        d[mot] += 1
    return sum(1 for u in d.itervalues() if u==1)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
def par_dictionnaire(limots):
    d = {}
    for mot in limots:
        if mot in d:
            d[mot] += 1
        else:
            d[mot] = 1
    return sum(1 for u in d.itervalues() if u==1)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
def par_dico_if(limots):
    d = {}
    for mot in limots:
        if mot in d:
            d[mot] = 0
        else:
            d[mot] = 1
    return sum(d.itervalues())

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
def par_dico_if_court(limots):
    d = {}
    for mot in limots:
        d[mot] = (mot not in d)
    return sum(d.itervalues())

Voici le code d'un seul tenant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
from collections import defaultdict
from time import clock
from itertools import groupby
 
 
def par_count(limots):
    return sum(limots.count(mot)==1 for mot in limots)
 
def par_human_like(limots):
    compteur = 0
    vus = set([])
    for i,mot in enumerate(limots):
        if mot not in vus:
            if mot not in limots[i+1:]:
                compteur += 1
            vus.add(mot)
    return compteur    
 
def par_dico_update(limots):
    d = {}
    [ d.update(((mot,mot not in d),)) for mot in limots ]
    return sum(d.itervalues())
 
def par_sorting_et_groupby(limots):
    limots.sort()
    return sum( 1 for k,g in groupby(limots) if sum(1 for u in g)==1)
 
def par_sorting_et_yielding(limots):
    def avance(li,k=1):
        a = li[0]
        for u in li[1:-1]:
            if u==a:  k = 0
            else:
                yield k
                a,k = u,1     
    limots.sort()
    return sum( avance(limots) ) + (limots[-1]!=limots[-2])
 
def par_defaultdict(limots):
    d = defaultdict(int)
    for mot in limots:
        d[mot] += 1
    return sum(1 for u in d.itervalues() if u==1)
 
def par_dictionnaire(limots):
    d = {}
    for mot in limots:
        if mot in d:
            d[mot] += 1
        else:
            d[mot] = 1
    return sum(1 for u in d.itervalues() if u==1)
 
def par_dico_if(limots):
    d = {}
    for mot in limots:
        if mot in d:
            d[mot] = 0
        else:
            d[mot] = 1
    return sum(d.itervalues())
 
def par_dico_if_court(limots):
    d = {}
    for mot in limots:
        d[mot] = (mot not in d)
    return sum(d.itervalues())
 
texte = open('akkamchi.txt').read()
fin_akkad = texte.find('FIN_AKKAD')
choisir = "\nPour choisir le texte entier (articles Akkad+Amerique+Chine, Wikipedia),\n    entrer  e"\
          +"\nsinon pour choisir l'extrait (Akkad),\n    presser ENTREE (sans aucun caractère)\n            "
while True:
    quoi = raw_input(choisir)
    if quoi=='':
        texte = texte[0:fin_akkad]
        break
    elif quoi=='e':
        texte = texte[0:fin_akkad] + texte[fin_akkad+9:]
        break
 
 
nb_essais = 10
print '\n\nNombre de mots uniques dans chaîne de '+str(len(texte))+' caractères'\
      +"\n(chaque temps = le plus petit à l'issue de " + str(nb_essais) + ' exécutions) :'
 
for f in (par_count,  par_human_like,  par_dico_update,  par_sorting_et_groupby, par_sorting_et_yielding,
          par_defaultdict,  par_dictionnaire,  par_dico_if,  par_dico_if_court):
    cumul = []
    for i in xrange(nb_essais):
        li_texte = texte.split()
        te = clock()
        n = f(li_texte)
        tf = clock()
        cumul.append(tf-te)
        if f==par_count and i==1:
            break
    print '\n' +  str(f)[10:].partition(' ')[0]\
          + '\n' + str(n) + '   ' + str(n/float(len(li_texte))*100)[:5] + ' %   ' + str(min(cumul)) + ' secondes'

J'ai créé un texte en aggrégeant les articles de Wikipedia consacrés à Akkad, Amérique et Chine, pour tester.
---> pièce jointe akkamchi archive.zip , à dézipper.

Le code ci-dessus traite
soit le texte en entier qui fait 103 303 caractères.
soit un extrait du texte qui fait 29 339 caractères (le premier tiers, consacré à Akkad), pour prendre moins de temps (j'ai un ordi lent).

Voici les résultats pour l'extrait
Les temps sont les plus bas que j'aie obtenus sur un grand nombre d'essais

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
par_count
1179   25.35 %   4.34423006276 secondes

par_human_like
1179   25.35 %   0.793907605577 secondes

par_dico_update
1179   25.35 %   0.0592832329239 secondes

par_sorting_et_groupby
1179   25.35 %   0.0315327786084 secondes

par_sorting_et_yielding
1179   25.35 %   0.021630682113 secondes

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
par_defaultdict
1179   25.35 %   0.0140034557444 secondes

par_dictionnaire
1179   25.35 %   0.0116674046549 secondes

par_dico_if
1179   25.35 %   0.00830105502246 secondes

par_dico_if_court
1179   25.35 %   0.00821109945537 secondes

Ces résultats sont éloquents:
en prenant pour base 1 le temps du code avec dictionnaire, les temps s'étagent de la façon suivant

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
par_count                   372.34
par_human_like               68.04
par_dico_update               5.08
par_sorting_et_groupby        2.70
par_sorting_et_yielding       1.85
par_defaultdict               1.20
par_dictionnaire              1.00 = base
par_dico_if                   0.71
par_dico_if _court            0.70

Avec l'extrait de 29 339 caractères, la méthode avec dictionnaire est quand même 372 fois plus rapide que celle avec count() !

J'avais donc effectivement raison:
l'algorithme avec count() n'est pas bon
l'algorithme avec dictionnaire est bien « à la fois le plus simple à mettre en place, à comprendre et de rapidité acceptable. »

Préférer l'algorithme avec dictionnaire n'est pas une question d'optimisation, mais de bonne pratique minimale.

L'optimisation a lieu entre le code avec dictionnaire et le code avec chargement particulier des valeurs du dictionnaire par dico_if: on gagne 29 % de temps.
Ainsi donc, on a

code avec dictionnaire : 372 fois plus rapide
code avec dico_if : 523 fois plus rapide
code avec dico_if_court : 529 fois plus rapide

que le code avec count()

Quant au code avec defaultdict, il apporte la concision et la facilité d'utiliser un dictionnaire qui s'auto-initialise pour une clé inexistante, mais il demande 20 % de temps en plus que l'utilisation d'un dictionnaire simple.

Voici les résultats pour le texte en entier

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
par_count
3748   22.93 %   91.6541635878 secondes

par_human_like
3748   22.93 %   19.2975788822 secondes

par_dico_update
3748   22.93 %   0.204769879971 secondes

par_sorting_et_groupby
3748   22.93 %   0.122503558413 secondes

par_sorting_et_yielding
3748   22.93 %   0.0929498022788 secondes

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
par_defaultdict
3748   22.93 %   0.0466564884646 secondes

par_dictionnaire
3748   22.93 %   0.0398592558549 secondes

par_dico_if
3748   22.93 %   0.028528206798 secondes

par_dico_if_court
3748   22.93 %   0.0278876225893 secondes

le code avec dictionnaire est 2300 fois plus rapide !!
le code avec dico_if_court est 3286 fois plus rapide !!

que le code avec count()

On peut imaginer ce que ça peut donner si on cherche à analyser "Guerre et Paix" de Tolstoï avec l'algorithme utilisant count().....

Si quelqu'un pouvait importer le texte et le code sur son ordinateur et faire deux exécutions, pour l'extrait et le texte entier, avec nb_essais = 100, je serais bien content de pouvoir connaître les résultats absolus et relatifs sur une machine rapide.

Merci

EDIT
Le code mis en premier n'était pas le plus actualisé. C'est maintenant le bon.
.

**fred1599** · 22/11/2009, 17h24

Bravo pour tout le travail,

La plupart des techniques dico je ne les connaissais pas. pour yield je ne suis pas surpris, par contre pour les méthodes dico, je suis sur les fesses.

Si j'ai un peu de temps dans la semaine, j'essaierais de tester sur mon PC, mais bon il est pas très puissant non plus.

groupby je ne connaissais pas non plus.

Merci pour la démonstration

faire des manipulations sur un texte

Python

Discussions similaires

Partager

Partager