UTF-8 et le tri lexicographique

UTF-8 est connu pour encoder tous les caracteres du monde en un format compact et retrocompatible avec ASCII. Mais il cache une propriete remarquable que beaucoup de developpeurs ignorent : l'ordre lexicographique des octets bruts correspond exactement a l'ordre des code points Unicode.

En clair : vous pouvez trier des chaines UTF-8 octet par octet, sans jamais les decoder, et obtenir le bon ordre. C'est une propriete deliberee de la conception d'UTF-8, et elle a des consequences majeures en pratique.

Pourquoi c'est remarquable

Dans la plupart des encodages multi-octets, trier les octets bruts ne donne pas le meme resultat que trier les caracteres. Il faut d'abord decoder chaque caractere, determiner son code point, puis comparer. C'est couteux.

UTF-8 a ete concu pour eviter ce probleme. Ken Thompson et Rob Pike ont choisi une structure d'encodage ou les octets de poids fort determinent a la fois la longueur de la sequence et l'ordre de tri.

Comment ca fonctionne

UTF-8 encode les caracteres sur 1 a 4 octets selon leur code point :

La cle : les prefixes des octets de tete (0, 110, 1110, 11110) sont classes dans l'ordre croissant en valeur binaire. Un caractere ASCII (1 octet) a toujours un premier octet inferieur a celui d'un caractere multi-octets. Et parmi les caracteres multi-octets, ceux avec des code points plus eleves ont des octets de tete plus grands.

Exemple concret

Prenons trois caracteres :

• A = U+0041 = octet 0x41
• e (e accent aigu) = U+00E9 = octets 0xC3 0xA9
• Emoji coeur = U+2764 = octets 0xE2 0x9D 0xA4

Tri par code point Unicode : A (65) < e (233) < coeur (10084). C'est le bon ordre.

Tri par octets bruts : 0x41 < 0xC3... < 0xE2.... Meme resultat, sans decoder.

Les consequences pratiques

Bases de donnees

Les moteurs de bases de donnees comme PostgreSQL, MySQL ou SQLite peuvent utiliser des index B-tree classiques sur des colonnes UTF-8. La comparaison octet par octet suffit pour maintenir l'ordre. Pas besoin d'un comparateur special qui decode chaque caractere.

-- Cet index fonctionne correctement avec UTF-8
-- car l'ordre des octets = l'ordre Unicode
CREATE INDEX idx_name ON users(name);
 
-- Les requetes ORDER BY et les recherches par plage
-- utilisent directement la comparaison binaire
SELECT * FROM users WHERE name > 'Martin' ORDER BY name;

Algorithmes de tri

Un simple memcmp (comparaison memoire octet par octet) suffit pour trier des chaines UTF-8 dans l'ordre Unicode. C'est exactement ce que font les fonctions de tri standard en C, Go, Rust et de nombreux autres langages.

// En Go, la comparaison native des strings
// fonctionne directement sur les octets UTF-8
strings := []string{"cafe", "Zurich", "ecole"}
sort.Strings(strings)
// Resultat correct sans decodage explicite

Recherche binaire

Puisque le tri binaire est coherent avec l'ordre Unicode, la recherche binaire fonctionne directement sur des donnees UTF-8 triees. Les structures comme les tries, les arbres de recherche et les skip lists beneficient toutes de cette propriete.

Systemes de fichiers

Les systemes de fichiers qui trient les entrees de repertoire par nom (comme ext4 avec les htrees) peuvent comparer les noms de fichiers UTF-8 octet par octet. C'est plus rapide qu'un tri qui necessite le decodage complet de chaque caractere.

Une limite importante

Cette propriete garantit l'ordre des code points Unicode, pas l'ordre linguistique. En francais, on s'attend a ce que "e" et "e" (accent aigu) soient proches dans le tri. Mais leurs code points sont eloignes (101 vs 233).

Pour un tri linguistiquement correct (ce qu'on appelle la collation), il faut utiliser des bibliotheques specialisees comme ICU. La propriete de tri d'UTF-8 ne remplace pas la collation — elle garantit simplement que le tri binaire est coherent et deterministe.

Pourquoi c'est un choix de conception brillant

Cette propriete n'est pas un accident. Elle a ete explicitement recherchee par les createurs d'UTF-8. Elle permet :

• Performance : comparer des octets est l'operation la plus rapide qu'un processeur puisse faire.
• Simplicite : pas besoin de bibliotheques de decodage pour le tri de base.
• Interoperabilite : tout systeme qui sait trier des octets sait trier de l'UTF-8.
• Compatibilite : les outils existants qui trient du texte ASCII continuent de fonctionner correctement avec de l'UTF-8.

C'est cette attention aux details pratiques qui a fait d'UTF-8 le standard dominant du web. Pas seulement sa capacite a encoder tous les caracteres du monde, mais aussi sa capacite a s'integrer sans friction dans les systemes existants.

Le tri binaire coherent est l'une de ces proprietes invisibles qui, quand elles sont bien concues, evitent des milliers de bugs et d'optimisations inutiles dans tous les logiciels qui manipulent du texte.