Sous-chaînes et tranches

Table des matières

1. Sous-chaînes d'un mot

On considère $c = c_0c_1\dots c_n$ une chaîne de caractères de longueur $n+1$, dont les caractères sont $c_0,c_1,\dots,c_n$.

  1. On appelle préfixe de la chaîne $c$, toute chaîne de la forme $c_0c_1\dots c_i$, pour $i\in \db{0,n}$.
  2. On appelle suffixe de la chaîne $c$, toute chaîne de la forme $c_ic_{i+1}\dots c_n$, pour $i\in\db{0,n}$.

  3. On appelle sous-chaîne, ou facteur, de $c$ toute chaîne de la forme $c_ic_{i+1}\dots c_j$, pour $0\leq i\leq j\leq n$.

    On dit que cette sous-chaîne se trouve à la position ou l'indice $i$.

On convient que la chaîne vide "" est un préfixe, un suffixe et une sous-chaîne de toutes les chaînes de caractères.

Pour la chaîne "abracadabra"

  • "abr" est un préfixe.
  • "bra" est un suffixe.
  • "cada" est une sous-chaîne, à la position $4$.
  • "abra" est une sous-chaîne, aux positions $0$ et $7$.

Soit $\om$ une chaîne de longueur $n$.

  1. Pour $k\geq 1$, combien $\om$ peut-elle admettre de facteurs de longueur $k$ ?
  2. Combien $\om$ peut-elle admettre de facteurs de longueur $\geq 1$ ?

2. Tranches d'une chaîne de caractères ou d'une liste

Python dispose d'une syntaxe pour pouvoir copier une sous-chaîne d'une chaîne de caractère : si c est une chaîne de caractères, l'expression c[i:j] crée une nouvelle chaîne de caractères, contenant les caractères de c d'indices i (inclus) à j (exclus).

La longueur de la tranche c[i:j] est $j-i$.

Cette notion de tranches s'applique également à des listes. 

In [1]: c = "Essai"
In [2]: c[1:4]
Out[2]: "ssa"

In [1]: l = [0,1,2,3,4]
In [2]: l[2:len(l)]
Out[2]: [2,3,4]

La syntaxe l[i:j] admet les extensions suivantes :

  • Si i est omis, c'est qu'il vaut 0.
  • Si j est omis, c'est qu'il vaut len(l).

En particulier, la syntaxe l[:] renvoie une copie de la liste l. 

In [1]: l = [3,5,7,11]
In [2]: l[:2]
Out[2]: [3,5]

In [3]: l[2:]
Out[3]: [7,11]

Écrire une fonction change_format qui prend en argument une chaîne de caractère représentant une date au format jj-mm-aaaa, comme "14-03-2001" et renvoie une chaîne de caractère représentant cette même date au format aaaa-mm-jj.

La complexité de l'instruction l[i:j] est en $O(j-i)$.

Écrire une fonction liste_préfixes qui prend en argument une chaîne de caractère et renvoie la liste des préfixes de l. Quelle est la complexité de cette implémentation ?

Il est également possible d'utiliser des indices négatifs dans la syntaxe de tranche. En particulier l[:-1] correspond à tous les éléments de l, sauf le dernier.

3. ♥ Recherche d'une sous-chaîne dans un texte

On veut écrire une fonction est_facteur qui prend en argument deux chaînes de caractères : un motif m et un texte t et qui renvoie True ssi le motif est un facteur du texet.

Écrire la fonction est_facteur, en utilisant la syntaxe de tranches pour comparer les tranches de t avec le motif.

  1. Réécrire la fonction est_facteur sans utiliser la syntaxe de tranches.
  2. Si $n$ est la longueur du texte, et $m$ celle de du motif, quel est, dans le pire des cas, le nombre de comparaisons effectuées ?

L'opérateur de comparaison == entre chaînes de caractères réalise autant de comparaisons élémentaires que l'implémentation naïve, qui compare caractère par caractère. Comme il cache une complexité algorithmique, il est à éviter, sauf invitation de l'énoncé.

Il existe des algorithmes de recherche d'un motif plus compliqués (Boyer-Moore, recherche par automate, Knuth–Morris–Pratt) qui garantissent une complexité en $O(n+m)$ opérations dans le pire des cas. Par contre, ces algorithmes nécessitent d'allouer $O(m)$ de mémoire supplémentaire (utilisation d'une liste de taille $m$ par exemple, pré-calculée à partir de m).

Écrire une fonction pseudo_concat qui prend en argument deux chaînes c1 et c2 et renvoie la plus petite chaîne de caractères qui admet c1 comme préfixe, et c2 comme suffixe. Par exemple, pseudo_concat("abc", "bcd") renverra "abcd".

4. Exercices

4.1. Recherche de sous-chaînes

Écrire des fonctions est_prefixe et est_suffixe qui prennent en argument deux chaînes de caractères c1 et c2 et qui renvoie True si c1 est un préfixe/suffixe de c2.

Écrire une fonction nb_occurrences qui prend en argument deux chaînes c1 et c2 et renvoie le nombre de fois où la chaîne c1 est présente dans la chaîne c2. Si c1 est une chaîne vide, la fonction nb_occurrences renverra len(c2) + 1.

On veut compter le nombre d'apparitions d'un facteur simple, en minimisant le nombre de comparaisons entre caractères.

  1. Écrire une fonction nb_de_aaa qui prend en argument une chaîne c et renvoie le nombre d'occurrences du facteur "aaa" dans c. Si la chaîne c est de longueur $n$, votre fonction effectuera seulement $n$ comparaisons entre caractères dans le pire des cas.
  2. ★ Même chose, avec la chaîne "abc".

  1. Écrire une fonction qui prend en argument une chaîne c et renvoie la plus grande valeur possible de $n$ pour laquelle c contient une sous-chaîne de la forme $a^n = \underbrace{a\dots a}_{n}$.
  2. Écrire une fonction qui prend en argument une chaîne c et renvoie la plus grande valeur possible de $n$ pour laquelle c contient une sous-chaîne de la forme $a^n b^n = \underbrace{a\dots a}_{n} \underbrace{b\dots b}_{n}$. On pourra proposer une version qui ne lit la chaîne qu'une seule fois.

4.2. Utilisation de tranches

Écrire une fonction cycle qui prend en argument une chaîne de caractères c et renvoie la chaîne obtenue en mettant le premier caractère de c à la fin. Si c est la chaîne vide, on renverra la chaîne vide.

assert(cycle("abcd") == "bcda")

Écrire une fonction coupe qui prend en argument une chaîne de caractères c et renvoie un couple (c1,c2) de chaînes de caractères telles que c soit la concaténation de c1 et c2 et que len(c1) == len(c2) ou len(c1) == len(c2) + 1.

On écrira un jeu de deux tests.

Écrire une fonction split_space qui prend en argument une chaîne de caractères c et renvoie une liste de chaînes de caractères, obtenues en découpant la chaîne c à chaque caractère espace " ".

assert(split_space("ceci est un essai") == ["ceci", "est", "un", "essai"])

  1. Écrire une fonction facteurs qui prend en argument une chaîne de caractères c et renvoie la liste de toutes les facteurs de c.
  2. Écrire une version facteurs_uniques pour laquelle la liste renvoyée ne contient pas de doublons.
  3. Quelle est la complexité de l'implémentation précédente ? Justifier. Peut-on l'améliorer ?

4.3. Algorithme de Knuth-Moris-Pratt ★

La recherche naïve d'un motif m dans un texte t consiste à comparer le motif m à des tranches t[i:…] successives. Si lors d'une telle comparaison les $k$ premiers caractères de m coïncident avec le texte, on peut utiliser cette information pour éviter d'avoir besoin de comparer m à t[i+1:…], et sauter à t[i+j:m], pour une certaine valeur de j qui dépend de $k$. C'est le principe de l'algorithme KMP, qui commence par calculer une table de sauts (à partir de m), qui associe à $k$ la valeur $j$ du saut possible.

Par exemple, pour $\texttt{m} = \underset{0\,1\,2\,3\,4\,5}{\texttt{"ABUABD"}}$ de longueur $m=6$ dans le texte $\texttt{t} = \underset{0\,1\,2\,3\,4\,5\,6\,7\,8\,9}{\texttt{"ABCABUABUABD"}}$.

  • La comparaison de m avec t[0:6] échoue à l'indice 2 (caractère C).

    On sait à ce stade que la lettre à l'indice $1$ correspond (donc est un B). Comme B n'est pas un préfixe de m, la comparaison de m avec t[1:6] échouera forcément. On peut passer à la comparaison de m avec t[2:8] qui échoue alors au premier caractère.

  • La comparaison de m avec t[3:9] échoue à l'indice $8$ (lettre U au lieu de D).

    On sait à ce stade que la partie m[:5] = ABUAB correspond bien à t[3:8]

    La prochaine comparaison qui peut réussir est celle de m avec t[6:12], parce que AB est à la fois un préfixe de m, et un suffixe de m[:5].

En général, lors d'une comparaison de m avec t[i:…] qui échoue à l'indice k, avec $k\geq i+2$, la prochaine fenêtre à comparer sera t[i+j+1:…], où $j = k - i - \l$, où $\l$ est la longueur du plus long préfixe de m qui soit également un suffixe propre de m[:k-i] (c'est-à-dire un suffixe différent de tout m[:k-i]).

  1. Écrire une fonction plsp_naive qui prend en argument m et renvoie une liste l telle que, pour $2\leq i\leq m$, l[i] soit la longueur du plus long suffixe propre de m[:i] qui soit un préfixe de m.

  2. ★ Notons $c = \texttt{l[i]}$, $c' = \texttt{l[i+1]}$, p = m[:c], et p' = m[:c']. En remarquant entre autres que $c' \leq c+1$ et que p'[:-1] sera un préfixe et un suffixe de p, proposer une implémentation plus efficace. En particulier, une fois l[0], …, l[i] calculés, pour trouver l[i+1] on aura seulement besoin de comparer m[i+1] à certains autres caractères.

    Indication : À quelle condition est-ce que p'[:-1] est égal à p ? Si ce n'est pas le cas, considérer l[l[i]].

  3. ★ Justifier que la complexité est en $O(m)$.

    Indication : À chaque étape $i\ra i+1$, la longueur du préfixe augmente au plus de $1$.

  4. Implémenter l'algorithme KMP de recherche d'un motif dans un texte. Quelle est la complexité dans le pire des cas ?