Lexique trié ?

10-02-2023

Objectifs

  • tester si une structure est triée

  • programmer une relation d’ordre sur le chaînes de caractères

  • implanter le tri par insertion

  • comparer la recherche d’un mot à l’aide de l’opérateur in avec la recherche dichotomique.

Matériel fourni

  • le module lexique et le fichier texte lexique.txt permettant d’obtenir 139719 mots de la langue française.

  • le module compare définissant la fonction de comparaison trivaluée compare vue en cours.

  • le fichier incomplet lexique_trie.py que vous complèterez dans ce TP.

Ces quatre fichiers sont contenus dans l’archive lexique_trie.zip à télécharger et décompresser.

Le lexique est-il trié ?

On rappelle que le module lexique définit une variable nommée LEXIQUE dont la valeur est une liste de plus de cent trente mille mots de la langue française. La question à laquelle vous allez répondre est Les mots de cette liste sont ils rangés dans l’ordre alphabétique croissant ?

À faire

Un examen superficiel «à la main» de quelques morceaux de cette liste peut amener à répondre positivement à la question précédente. Mais ce n’est pas une démarche vraiment scientifique.

Réalisez la fonction

def est_trie(l, comp=compare):
    '''
    :param l: (str ou tuple ou list) une structure séquentielle
    :param comp: (function) fonction de comparaison
    :return: (bool)
      - True si l est triée selon l'odre défini par comp
      - False sinon
    :CU: éléments de l comparables avec la fonction comp
    :Exemples:

    >>> est_trie([1, 2, 3, 4])
    True
    >>> est_trie([4, 3, 1, 2])
    False
    '''

(vous pouvez utiliser le prédicat all).

Puis répondez à la question posée en utilisant cette fonction avec la fonction de comparaison compare.

Sauf erreur de votre part, ce que vous avez fait vous révèle que pour Python, la liste n’est pas triée. Peut-être s’est-il glissé dans la liste une ou deux inversions de mots qui font qu’elle n’est pas triée.

À faire

Réalisez la fonction

def causes_erreurs_tri(l, comp=compare):
    '''
    :param l: (str ou tuple ou list) une structure séquentielle
    :param comp: (function) fonction de comparaison
    :return: (list) une liste de triplets de la forme `(i, l[i], l[i+1])`
      tels que `l[i] > l[i+1]`
    :CU: éléments de l comparables avec la fonction comp
    :Exemples:

    >>> causes_erreurs_tri([1, 2, 3, 4])
    []
    >>> causes_erreurs_tri([4, 3, 1, 2]) == [(0, 4, 3), (1, 3, 1)]
    True
    '''

  • Quelles sont les causes des erreurs de tri pour LEXIQUE ?

  • Quelle est la longueur de cette liste ?

  • Pour quelle raison la liste n’est pas triée ?

Une nouvelle relation d’ordre

Ainsi, la liste LEXIQUE n’est pas triée à cause des lettres accentuées qui, pour Python, sont toutes «plus grandes» que toutes les lettres non accentuées.

À faire

Construisez le dictionnaire d’occurences de tous les caractères constituant les mots de LEXIQUE. Vous devez obtenir 42 associations.

Il faut maintenant définir une nouvelle relation d’ordre sur les caractères pour tenir compte des caractères accentués : un a accentué doit être plus grand qu’un a non accentué

On définit une constante nommée ALPHABET dont la valeur est

"aàâbcçdeéèêëfghiîïjklmnoôpqrstuùûüvwxyz".

C’est l’ordre dans lequel sont rangés les caractères dans cette constante qui va définir la relation d’ordre entre caractères.

À faire

Définissez une fonction de comparaison pour les caractères de ALPHABET

def compare_caracteres(c1, c2):
    '''
    :param c1, c2: (str)
    :return: (int)
       - -1 si c1 est situé avant c2 dans ALPHABET
       -  1 si c1 est situé après c2dans ALPHABET
       -  0 si c1 = c2
    :CU: c1 et c2 doivent être dans ALPHABET
    :Exemples:

    >>> compare_caracteres('a', 'à')
    -1
    >>> compare_caracteres('à', 'b')
    -1
    >>> est_trie(ALPHABET, compare_caracteres)
    True
    '''

Il n’y a pas que les caractères accentués qui posent problème. En effet il y a aussi trois symboles de ponctuation -, ' et .. Les deux premiers interviennent dans des mots comme aujourd’hui ou vis-à-vis. Le dernier n’intervient dans aucun mot de la langue française, mais il figure dans quelques mots du lexique.

Pour décider de deux chaînes laquelle doit être rangée avant l’autre, il suffit de commencer par comparer les deux chaînes en supprimant les caractères de ponctuation et en remplaçant les caractères accentués par leur équivalent non accentué.

À faire

Réalisez la fonction

def sans_accent_sans_ponctuation(s):
    """
    :param s: (str) une chaîne de caractères
    :return: (str) une chaîne identique à s sans accent et sans trait d'union
    :CU: aucune
    :Exemples:

    >>> sans_accent_sans_ponctuation('orangé')
    'orange'
    >>> sans_accent_sans_ponctuation('vis-à-vis')
    'visavis'
    """

Pour comparer deux mots \(m_1\) et \(m_2\) :

  1. on calcule les mots sans accents et sans ponctuation correspondant

  2. si cette comparaison révèle que les deux mots transformés ne sont pas égaux on en déduit immédiatement l’ordre des deux mots \(m_1\) et \(m_2\).

  3. si les deux mots sans accents et ponctuation sont égaux, alors il faut examiner plus finement les mots \(m_1\) et \(m_2\) en les parcourant caractère par caractère tout en sautant au dessus des symboles de ponctuation.

À faire

Réalisez la fonction

def compare_mots(s1, s2):
    """
    :param s1, s2: (str)
    :return: (int)
        - -1 si s1 est situé avant s2 dans l'ordre défini dans l'énoncé
        -  1 si si s1 est situé après s2 dans l'ordre défini dans l'énoncé
        -  0 si s1 = s2
    :CU: s1 et s2 ne contiennent que des caractères appartenant à ALPHABET
         ou appartenant à "-'."
    :Exemples:

    >>> compare_mots('êtes', 'étés')
    1
    >>> compare_mots('à', 'abaissa')
    -1
    >>> compare_mots('visas', 'vis-à-vis')
    -1
    """

Vous pouvez utiliser une fonction intermédiaire sans_ponctuation.

À faire

  • Vérifiez si le LEXIQUE est trié selon l’ordre défini par votre fonction compare_mots.

  • Construisez la liste de tous les triplets de la forme (i, LEXIQUE[i], LEXIQUE[i+1]), tels que

    LEXIQUE[i] > LEXIQUE[i+1] selon l’ordre ainsi défini.

  • Quelle est la longueur de cette liste ?

Puisque même avec l’ordre défini par compare_mots le lexique n’est pas trié, vous allez trier ce lexique.

À faire

  • Pourquoi préfère-t-on ici le tri par insertion au tri par sélection ?

  • Réalisez une procédure inserer et une procédure trier_par_insertion pour implanter le tri par insertion.

Cela fait, vérifiez à l’aide de votre prédicat est_trie que le lexique est maintenant bien trié selon l’ordre défini par compare_mots.

Recherche dichotomique dans le lexique

On suppose dans cette partie que le lexique LEXIQUE a été trié selon l’ordre compare_mots.

À faire

Réalisez la fonction spécifiée ci-dessous

def recherche_dicho(x, l, a, b, comp=compare):
    """
    :param x: (any) l'élément à rechercher
    :param l: (list ou tuple) structure dans laquelle on effectue la recherche
    :param a, b: (int) indices délimitant la recherche
    :param comp: (function) fonction de comparaison à utiliser
    :return: (int)
          - i tq  i dans [a, b[ et l[i] = x si un tel indice existe
            (recherche fructueuse)
          - -1 sinon (recherche infructueuse)
    :CU: x comparable avec les éléments de l à l'aide de la fonction comp
                       0 <= a <= b <= len(l)
                       l triée dans l'ordre croissant selon comp
    :Exemples:

    >>> l = [2 * k for k in range(100)]
    >>> recherche_dicho(50, l, 0, 100)
    25
    >>> recherche_dicho(51, l, 0, 100)
    -1
    """

À faire

Testez l’appartenance des mots suivants dans le lexique à l’aide de votre fonction de recherche dichotomique. Dans le cas d’une réponse positive, notez l’indice du mot dans le lexique.

  • étés

  • êtes

  • python

  • pythonesque

Comparaison avec les fonctionnalités de Python

En Python, on peut tester l’appartenance d’un élément dans une liste à l’aide de l’opérateur in et obtenir l’indice de cet élément à l’aide de la méthode index (uniquement pour des éléments appartenant à la liste).

À faire

En utilisant la fonction timeit du module timeit, comparez les temps de calcul pour des recherches de mots dans le lexique avec

  • votre fonction recherche_dicho

  • l’opérateur in

  • la méthode index (uniquement pour des recherches fructueuses).

Vous pourrez fixer à 5000 le nombre d’essais (paramètre number de timeit).

Question

Quelle conclusion tirez-vous de ces mesures ?