Des algorithmes appliqués en C++

1. Approche directe

L’approche naïve consiste à comparer caractère par caractère le motif recherché avec le texte d’entrée. Si toutes les comparaisons réussissent du premier au dernier caractère du motif, on dit que le motif est épuisé et la recherche est terminée. 

Si la comparaison diffère avant d’arriver à la fin du motif, il est inutile de poursuivre les comparaisons pour les caractères suivants. On décale le motif d’un caractère et on recommence la comparaison.

L’implémentation C++ de cet algorithme ne présente aucune difficulté. On doit vérifier les caractères un par un sans dépasser la taille du motif ni celle du texte à analyser :

int recherche_motif_simple(string s, string m)  
{ 
   int pos = 0; 
   int p = 0; 
   while (pos < s.length()) 
   {        
       if (s.at(pos) == m.at(0)) 
       { 
           // premier caractère identique 
           p = 1; 
 
           // compare un par un les prochains caractères du motif
           while ( 
                   p + pos < s.length() && 
                   p < m.length() &&  
       ...

1. Présentation des graphes

Nous avons étudié au chapitre La bibliothèque Standard Template Library une structure dynamique appelée liste. Une liste est constituée d’un élément de tête (une valeur) rattaché à une liste appelée suite. Pour parcourir la liste, on utilise volontiers une fonction récursive qui se rappelle jusqu’à atteindre la liste vide.

En considérant qu’un élément peut avoir plusieurs successeurs on obtient un arbre constitué de nœuds. Les nœuds ont un seul ancêtre appelé père et un nombre multiple de descendants appelés fils. Les nœuds terminaux qui n’ont pas de fils sont des feuilles, tandis que l’élément au sommet de l’arbre s’appelle racine. Il existe des cas particuliers d’arbres, par exemple ceux qui ont au plus deux fils appelés B-arbres ou B-trees, le B signifiant en anglais binary pour le nombre 2.

Un graphe généralise encore la construction de l’arbre en admettant qu’un nœud (appelé sommet) compte plusieurs ancêtres.

Les graphes sont formés de deux types d’éléments : des sommets et des arcs. Les sommets représentent les objets, et les arcs établissent les relations entre ceux-ci. Les arcs peuvent être porteurs de valeurs (ou poids) mais cette caractéristique n’est pas déterminante pour l’étude d’un graphe à proprement parler. 

Les graphes peuvent être orientés ou non-orientés. Dans le premier cas, les arcs sont orientés et sont représentés par des flèches. Au besoin, un arc peut être bidirectionnel en étant dédoublé pour représenter...

1. Approche par statistique : l’algorithme d’Huffman

On parle aussi de codage d’Huffman, du nom de son inventeur. Le principe de cet algorithme consiste à réduire le nombre de bits pour coder des caractères fréquents (octets) dans le fichier à comprimer, et rallonger les autres.

En langue française, la lettre E est la plus fréquente, tandis que les lettres K ou Z le sont beaucoup moins. D’une façon empirique, un codage du E sur 7 bits au lieu de 8 fera gagner 1 bit à chaque occurrence.

Comme il faut toujours 256 codes différents pour représenter chaque caractère ASCII (1 octet), on admettra que les lettres les moins fréquentes aient des codages plus longs, par exemple sur 9 bits.

L’algorithme d’Huffman construit un codage binaire (un arbre à deux branches ou B-tree) à partir des statistiques des caractères. Selon les implémentations, les statistiques sont prédéfinies en fonction du type de fichier ou dynamiquement calculées à partir du fichier à compresser. Des implémentations encore plus élaborées modifient le codage en actualisant les statistiques au fur et à mesure du traitement du fichier.

class Noeud 
{ 
public: 
   int code, lcode; 
   int freq, sauve; ...