Algorithme Re-Pair

Définition

Il s’agit d’un algorithme de compression de graphes sans perte de données qui utilise une grammaire. L’algorithme remplace les paires d’éléments consécutifs dans les listes d’adjacence par un seul symbole et stocke ce dernier dans un dictionnaire (qui correspond à la hiérarchie de la phrase), jusqu’à ce qu’aucune paire de symbole adjacents n’apparaisse deux fois.

Français

algorithme Re-Pair

pairage récursif

Anglais

Re-Pair algorithm

recursive pairing

This is a lossless graph compression algorithm that uses a grammar. The algorithm replaces pairs of consecutive elements in adjacency lists with a single symbol and stores the latter in a dictionary (corresponding to the sentence hierarchy), until no pair of adjacent symbols appears twice.

Source

Source : HAL Science

Source : Wikipedia