Couper, mémoriser, sauter : tri fusion, programmation dynamique et Boyer-Moore

Ctrl + F dans un PDF de 300 pages, tri d'une playlist de 2 000 titres : réponse immédiate. Derrière ces prouesses, trois idées d'algorithmique : couper le problème, mémoriser ce qui est déjà calculé, sauter ce qui ne peut pas réussir.

1. Diviser pour régner : le tri fusion

Diviser pour régner, c'est diviser le problème en sous-problèmes plus petits de même nature, les résoudre (souvent récursivement), puis combiner leurs solutions. Le tri fusion coupe la liste en deux moitiés, trie chacune récursivement, puis fusionne les deux moitiés triées.

def fusion(g, d):
 res = []
 i, j = 0, 0
 while i < len(g) and j < len(d):
 if g[i] <= d[j]:
 res.append(g[i])
 i += 1
 else:
 res.append(d[j])
 j += 1
 return res + g[i:] + d[j:]


def tri_fusion(t):
 if len(t) <= 1:
 return t
 m = len(t) // 2
 return fusion(tri_fusion(t[:m]), tri_fusion(t[m:]))

À la main avec [5, 2, 4, 1] : on coupe en [5, 2] et [4, 1], puis en listes d'un élément, déjà triées (le cas de base). On fusionne : [2, 5] et [1, 4]. Dernière fusion : 2 contre 1, on prend 1 ; 2 contre 4, on prend 2 ; 5 contre 4, on prend 4 ; il reste 5. Résultat : [1, 2, 4, 5].

Environ log₂ n niveaux de découpage, chacun parcourant les n éléments : le coût est de l'ordre de n × log₂ n. Pour un million d'éléments, environ 20 millions d'opérations, contre jusqu'à 500 milliards (n² ÷ 2) pour le tri par insertion.

2. La programmation dynamique : ne jamais recalculer

La fonction récursive directe fib(n) = fib(n − 1) + fib(n − 2) fait 331 160 281 appels pour fib(40) : fib(38) est calculé 2 fois, fib(37) 3 fois… Les sous-problèmes se chevauchent. Remède : mémoïser, ranger chaque résultat dans un dictionnaire.

memo = {}


def fib(n):
 if n <= 1:
 return n
 if n not in memo:
 memo[n] = fib(n - 1) + fib(n - 2)
 return memo[n]

Plus que 79 appels pour fib(40) !

On peut aussi remplir un tableau du plus petit sous-problème au plus grand. Rendons 6 € avec des pièces de 1, 3 et 4 € : le glouton prend la plus grosse pièce d'abord, 4 + 1 + 1, soit 3 pièces ; or 3 + 3 suffit. Si nb[s] est le nombre minimal de pièces pour s, la dernière pièce vaut 1, 3 ou 4, donc nb[s] = 1 + min(nb[s − 1], nb[s − 3], nb[s − 4]).

s	0	1	2	3	4	5	6
nb[s]	0	1	2	1	1	2	2

Ainsi nb[6] = 1 + min(2, 1, 2) = 2.

def rendu(pieces, somme):
 nb = [0] + [somme + 1] * somme
 for s in range(1, somme + 1):
 for p in pieces:
 if p <= s and nb[s - p] + 1 < nb[s]:
 nb[s] = nb[s - p] + 1
 return nb[somme]

rendu([1, 3, 4], 6) renvoie 2 (somme + 1 joue l'infini). En diviser pour régner, les sous-problèmes sont indépendants ; en programmation dynamique, ils se chevauchent.

3. Recherche textuelle : Boyer-Moore

L'algorithme naïf essaie le motif (de longueur m) à chaque position du texte. Boyer-Moore, dans la version simplifiée de Horspool, compare depuis la fin du motif, puis saute selon la lettre du texte située sous la dernière lettre du motif : si cette lettre figure dans le motif avant la dernière case, le saut est la distance entre sa dernière apparition avant cette case et la fin ; sinon, il vaut m.

Motif CHIEN : C → 4, H → 3, I → 2, E → 1, autre → 5. Dans « UN CHAT CHASSE LE CHIEN » :

• position 0, « UN CH » : H ≠ N, saut de 3 ;
• positions 3, 8 et 13 : un échec, puis un saut de 5 (espace ou S) ;
• position 18 : 5 comparaisons réussies, trouvé !

Bilan : 9 comparaisons, contre 27 pour l'algorithme naïf.

def horspool(texte, motif):
 m, n = len(motif), len(texte)
 saut = {}
 for k in range(m - 1):
 saut[motif[k]] = m - 1 - k
 positions = []
 i = 0
 while i <= n - m:
 j = m - 1
 while j >= 0 and texte[i + j] == motif[j]:
 j -= 1
 if j < 0:
 positions.append(i)
 i += saut.get(texte[i + m - 1], m)
 return positions

horspool("UN CHAT CHASSE LE CHIEN", "CHIEN") renvoie [18].

À retenir

• Diviser pour régner : diviser, résoudre récursivement, combiner ; le tri fusion coûte de l'ordre de n × log₂ n.
• La programmation dynamique ne recalcule jamais un sous-problème : mémoïsation, ou tableau rempli du plus petit au plus grand.
• Le glouton n'est pas toujours optimal : 6 = 4 + 1 + 1 au lieu de 3 + 3.
• Boyer-Moore compare depuis la fin du motif et saute grâce à une table calculée sur le motif.

★ Pour aller plus loin

Le tri fusion est attribué à John von Neumann (1945) ; Python trie avec Timsort (Tim Peters, 2002), hybride du tri fusion et du tri par insertion.

« Programmation dynamique » vient de Richard Bellman, dans les années 1950 : « programmation » y veut dire planification. En biologie, l'algorithme de Needleman et Wunsch (1970) aligne ainsi des séquences d'ADN.

Boyer et Moore ont publié leur algorithme en 1977, Horspool sa simplification en 1980.

Sources pour creuser

• Spécialité Numérique et sciences informatiques : 24 leçons avec exercices corrigés – Terminale, Balabonski, Conchon, Filliâtre et Nguyen (Ellipses).
• visualgo.net : le tri fusion animé pas à pas.
• Sur lumni.fr ou YouTube, cherche « tri fusion NSI » et « Boyer-Moore NSI ».
• Le programme de NSI sur eduscol.education.fr.