Solution du problème Dénombrement

Vous trouverez ici la solution pour l'exercice suivant:

Denombrement

Généralités

Ce problème, bien qu'assez simple, va nous permettre d'aborder plusieurs notions capitales en python, notement à propos de dictionaires, et de chaines de caracteres.

Solutions du probleme de base

Approches naives

Tout d'abord il faut savoir comment découper une chaine de characteres (string). Pour cela on utilise la methode split.

>>> "aa     bbbb   cccc".split()
["aa", "bbbb", "cccc"]

split prend en parametre un separateur, mais celui-ci est optionel. Si on ne donne pas ce parametre, alors le texte sera découpé par rapport à tout les "blancs" (espace, tabulations, etc).

Maintenant que nous avons les mots, il va falloir les compter. Pour cela on va utiliser un dictionaire pour associer à chaque mot, son nombre d'occurences.

Il va donc falloir gérer deux cas: * Le mot n'est pas déjà dans le dictionaire, il faut donc le rajouter et lui associer la valeur 1 * Le mot est déjà là, il faut donc incrémenter son nombre d'occurences

NB: pour savoir si une clef est ou non dans un dictionaire on utilise le mot clef in

NB: pour incrémenter de 1 en python on utilise +=

Première version:

def count_words(text):
    result = dict()
    for word in text.split():
        if word in result:
            result[word] += 1
        else:
            result[word] = 1
    return result

On peut aussi faire du duck typing:

def count_words(text):
    result = dict()
    for word in text.split():
        try:
            result[word] += 1
        except KeyError:
            result[word] = 1
    return result

Meilleure utilisation des dictionaires

Les dictionaires ont 2 methodes qui peuvent être utiles ici: setdefault() et get().

En utilisant setdefault(), qui permet d'affecter une valeur dans un dictionaire si la cle n'existe pas encore, et ne touche pas la valeur si elle existe; par exemple:

def count_words(text):
    result = dict()
    for word in text.split():
        result.setdefault(word, 0)
        result[word] += 1
    return result

get(), quant à elle permet d'obtenir une valeur dans un dictionaire, et si la cle n'y est pas enregistrée, alors elle retourne la valeur passée en second parametre:

def count_words(text):
    result = dict()
    for word in text.split():
        result.setdefault(word, 0)
        result[word] = result.get(word, 0) + 1
    return result

defaultdict

Encore plus fort: les defaultdict. Comme leur nom l'indique, ce sont des dictionaires qui permettent d'avoir une valeur par default lors d'une requete de valeur. Un peu comme si il appelait la methode get() tout le temps. Dans le constructeur d'un defaultdict, on passe une fonction qui retourne la valeur par default que l'on veut. Par exemple * bool pour une valeur bouleene (initialisee a False) * int pour un entier (initialise a 0) * ... * une lambda telle que lambda : 123.5 si on veut initialiser les valeurs à cette valeur On peut aussi initialiser un defaultdict avec un autre defaultdict afin de faire des structures imbriquees, plus complexes.

Cela donne pour notre cas:

from collections import defaultdict
def count_words(text):
    result = defaultdict(int)
    for word in text.split():
        result[word] += 1
    return result

Counter

Finalement, il y a un objet dans collections qui peut être utilisé pour faire du dénombrement; il a même été prévu pour ca: Counter.

Son but est de retourner un objet capable de se comporter comme un dictionaire qui continent le nombre d'occurences des elements de l'iterable qui lui est passé en parametre.

On peut par exemple l'utiliser pour connaitre la lettre la plus représentée dans un texte, pour essayer de cracker un code cryptographique simple (codage de Cesar en autre).

En ce qui nous concerne, son usage permet de se passer de la logique du dictionaire, et de se concentrer sur la partie découpe des mots.

Voici une solution utilisant Counter:

from collections import Counter
def count_words(text):
    return Counter(text.split())

Bonus 1

Faire en sorte que les mots soient comptes quelque soit leur casse. Pour cela rien de plus simple, avant de compter les mots on les passe en minuscule. Ainsi, tOtO et ToTo seront tous deux comptés comme le mot toto.

Une manière simple d'arriver à ce resultat est de rendre minuscule tout le texte passé:

def count_words(text):
    return Counter(text.lower().split())

Bien que ceci fonctionne très bien pour des cas de base, il a tout de même un gros inconvégnant. Il duplique l'intégralité du texte qu'on nous donne. Pour palier ce problème, il suffit de n'appeler lower() que sur chaque élément individuel du resultat de split().

generator expression

Nous allons utiliser pour cela une expression de générateur (generator expression) qui ressemble beaucoup à une comprehension de liste (list comprehension) sauf qu'il faut utiliser des parenthèses () en lieu et place des crochets []. Pour rappel, la comprehension de liste permet d'écrire une liste en une lisgne, alors qu'il aurait fallu passer par un bloque for. Par exemple:

titi = list()
for x in range(5):
    titi.append(x**3)

est equivalent à

titi = [x**3 for x in range(5)]

ce qui se lit quasiment naturelement: titi est la liste des x au cube pour x dans les 5 premiers entiers en partant de zero

La comprehension de liste génère la liste en entier, si on ne veut que un iterable, alors il vaut mieux utiliser une expression de générateur qui ne va calculer qu'un élément à la fois. Pour l'exemple précédent, si on se sert de titi que pour une boucle, alors il est plus judicieux d'en faire un générateur comme cela:

titi = (x**3 for x in range(5))

Si on veut prendre la version minuscule des éléments retournés par split(), il suffit de faire:

def count_words(text):
    return Counter((w.lower() for w in text.split()))

Note

dans ce cas les parenthèses autour du générateur sont optionnelles et on trouvera le plus souvent celui-ci écrit:

def count_words(text):
    return Counter(w.lower() for w in text.split())

Bonus 2

Il va falloir se débarrasser de la ponctuation qui est parfois accollée aux mots. Encore une fois plein de choix s'offrent à nous pour faire cela, mais je ne vais en décrire que deux (cette solution commence à être très longue à lire, et à écrire).

solution naive

On va enlever la ponctuation des mots en utilisant strip(). Cette methode de tout string permet d'enlever les characters du string donné en parametre en tête ou en queue du texte. Cette suppression se fait jusqu'au dernier charactère: "aaaBBBBccacc".strip("ac") == "BBBB".

On peut donc faire:

def count_words(text):
    return Counter(w.lower().strip('",;.:/!') for w in text.split())

Ceci peut fonctionner, mais il va falloir faire augmenter la liste des charactères de ponctuation au fur et à mesure, et surtout avec les charactères étrangés comme ¿...

expressions rationnelles

Nous allons donc utiliser le module re pour cela. Celui-ci a une fonction pour trouver toutes les occurences (non collocaliées) qui correspondent à une expression donnée findall()

Ici nous voulons trouver les mots donc nous utiliserons cette expression: "[\w-]+". Elle va chercher les mots composés de charactères présents dans les mots (\w) et du trait d'union.

Voici donc la solution finale:

import re
from collections import Counter

def count_words(text):
    return Counter(x.lower() for x in re.findall("[\w-]+", text))