Implémentation d'un lexique avec Objective Caml

Edouard Evangelisti

Cet article propose une implémentation efficace des lexiques avec Objective Caml. Deux exemples d'application sont proposés : autocomplétion des mots au cours de la frappe, application aux jeux de lettres (Boggle, anagrammes). Commentez

- Titre : Implémentation d'un lexique avec Objective Caml

- Auteur : Edouard Evangelisti

- Parution : 26 octobre 2009

- Mise à jour : 11 juillet 2020

- Licence : Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2009 Edouard Evangelisti. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Quelques définitions

- I-A. Mot

- I-B. Lexique et dictionnaire

- II. Représentation d'un lexique

- III. Implémentation d'un lexique

- III-A. Fonctions de manipulation des mots

- III-B. Choix d'implémentation

- III-C. Le code OCaml

- III-C-1. Type d'un lexique et lexique vide

- III-C-2. Ajout d'un mot dans un lexique

- III-C-3. Appartenance d'un mot à un lexique

- III-C-4. Supprimer un mot d'un lexique

- III-C-5. Taille d'un lexique

- III-C-6. Parcours des mots du lexique

- III-C-7. Fonction fold

- III-C-8. Conversion en liste

- IV. Du lexique au dictionnaire

- V. Exemples d'application

- V-A. Jeux de lettres

- V-B. Applications bureautiques

- VI. Code complet

- VII. Pour aller plus loin

- VIII. Remerciements

I - Quelques définitions

Avant de parler d'algorithmes et d'implémentation, précisions la définition de quelques mots que nous allons utiliser fréquemment tout au long de cet article. Il s'agit des termes mot, lexique et dictionnaire.

I-A - Mot

Dans cet article, un mot est défini comme une séquence de caractères de longueur non nulle. Par caractère on entend les lettres minuscules et capitales d'imprimerie (portant ou non des signes diacritiques), les chiffres et tous les caractères spéciaux, à l'exclusion des espaces. Il est possible de retenir une définition plus restrictive, où seraient exclus les caractères qui ne sont pas des lettres, mais cela n'est pas nécessaire dans cet article.

I-B - Lexique et dictionnaire

Dans cet article, un lexique est défini comme un ensemble de mots. Il existe un lexique vide ne comportant aucun mot. Un dictionnaire est un lexique qui associe une donnée à chacun de ses mots. Il existe également un dictionnaire vide.

II - Représentation d'un lexique

Il existe plusieurs manières de représenter un lexique. Celle que je vais présenter ici est particulièrement adaptée à une grande variété de problèmes. Pour justifier son utilisation, je vous propose de commencer par la mise en évidence des principales contraintes liées à la manipulation d'un lexique.

Contrainte de taille - Les lexiques que nous allons manipuler sont très volumineux : ils comportent entre 300 et 600 000 entrées. Lorsqu'on travaille avec autant de données, il faut s'assurer que les fonctions que l'on utilise ne déclenchent pas d'erreur de débordement de pile (Stack_overflow). Pour cela, il faut que leur complexité temporelle soit indépendante de la taille n du lexique. Elle pourra, en revanche, dépendre de la longueur du mot à insérer. Cette remarque nous permet d'exclure d'emblée l'implémentation naïve d'un lexique à base de liste ordonnée, dans laquelle l'insertion est précisément en O(n).

Implémentation naïve - Insertion d'un mot

let add ?(compare = String.compare) word dic =
let rec loop = function
| [] -> [word]
| x :: t as y ->
match compare word x with
| 0 -> y
| 1 -> x :: loop t
| _ -> word :: y
in loop dic

Contrainte de stockage - Lorsqu'un lexique est utilisé pour stocker les mots d'une langue, le stockage séparé des mots est généralement très redondant. Il existe en effet de nombreux préfixes communs à des familles entières de mots. On voudrait donc, si possible, trouver un moyen de réduire cette redondance sans affecter pour autant les performances.

Contrainte de style - Nous allons essayer de représenter notre arbre de façon purement fonctionnelle, c'est-à-dire sans effectuer aucun effet de bord. En d'autres termes, l'insertion d'un mot dans un lexique doit être une fonction qui crée un nouveau lexique, et non une fonction qui ajoute un mot à un lexique existant, et ne renvoie aucune valeur.

III - Implémentation d'un lexique

Les différentes contraintes que nous avons présentées ci-dessus ne sont pas incompatibles. Il est en effet possible de les satisfaire toutes en utilisant un arbre des préfixes ou prefix tree, encore appelé trie. Cet arbre présente la structure suivante :

- chaque nœud correspond à un caractère. Les caractères sont stockés sous forme de valeurs de type int, char, string, etc. Nous en reparlerons ultérieurement ;

- un drapeau (généralement un booléen) indique, à chaque niveau de l'arbre, si les nœuds parcourus depuis la racine forment un mot ;

- les nœuds supérieurs de l'arbre sont stockés sous forme de couples (clef, valeur). Plusieurs implémentations de ces couples peuvent être utilisées. Nous les présenterons plus tard.

Structure d'un arbre des préfixes. Les nœuds auxquels est associée la valeur 1 (équivalent de true) correspondent aux mots présents dans le lexique.

Notons d'emblée que cette structure permet d'obtenir rapidement l'ensemble des mots qui possèdent un préfixe donné ; cela revient en effet à extraire le sous-arbre correspondant. Nous allons voir qu'il est également possible de satisfaire toutes les contraintes que nous avons énoncées plus haut.

III-A - Fonctions de manipulation des mots

Avant toute chose, on suppose disponibles les fonctions suivantes :

- fonction explode, qui scinde un mot en liste de caractères ;

- fonction compare, qui compare des caractères deux à deux ;

- fonction rev_implode, qui inverse et fusionne une liste de caractères pour former un mot.

La fonction compare est déjà disponible dans la bibliothèque standard d'OCaml : c'est Pervasives.compare. Il existe également des versions spécialisées (String.compare, Char.compare), mais je préfère rester le plus général possible pour le moment. explode n'est quant à elle pas disponible. Si l'on travaille exclusivement avec des caractères non accentués, on peut utiliser la fonction suivante :

Fonction explode

let explode str =
let rec loop acc = function
| 0 -> acc
| i -> let j = i - 1 in loop (str.[j] :: acc) j
in loop [] (String.length str)

L'écriture de cette fonction est donnée seulement à titre d'exemple ; en effet, son écriture varie selon le codage des caractères que l'on utilise. Ainsi, si les chaînes de caractères sont codées en UTF-8, la fonction précédente, qui construit en quelque sorte une liste d'octets à partir d'une chaîne, ne sera pas valable (l'hypothèse selon laquelle un octet correspond à un caractère n'étant alors pas toujours vérifiée).

III-B - Choix d'implémentation

Implémentation des couples (caractère, nœud) - L'implémentation des couples (caractère, nœud fils) peut se faire à l'aide d'un tableau de 26 cases. Chaque case correspond alors à une lettre (la première case correspond au caractère 'a', la seconde à 'b', et ainsi de suite). Cette représentation garantit un accès en temps constant (O(1)) au nœud fils. Elle présente cependant plusieurs défauts : tout d'abord, il n'est pas possible d'utiliser des caractères pour lesquels aucune case n'a été prévue. Ensuite, lorsque le lexique comporte peu de mots, beaucoup de mémoire est utilisée pour rien, puisque les cases ne pointent vers aucun nœud fils ! L'implémentation peut aussi faire appel à une liste d'association. Cette méthode évite de gaspiller trop de mémoire et n'est pas limitée en nombre de caractères. Hélas, la recherche d'un nœud fils possède une complexité en temps linéaire O(s) où s désigne la longueur de la liste. Les inconvénients liés à ces deux méthodes m'ont poussé à utiliser une implémentation à base d'arbres binaires équilibrés (module Map de la bibliothèque standard), qui permet une recherche du nœud fils en O(log s) tout en conservant les avantages des listes par rapport aux tableaux. Enfin, notons au passage qu'une table de hachage est aussi envisageable, mais qu'elle exclut tout tri des mots selon l'ordre lexicographique.

Représentation des caractères - La représentation des caractères est libre et correspond à un type t quelconque. Ceci nous permet de conserver une grande généricité. Cela ouvre également la voie à l'écriture d'un foncteur qui accepterait le module suivant en entrée :

Signature du module passé en argument au foncteur

module type CHAR =
sig
type t
val compare : t -> t -> int
val explode : string -> t list
val rev_implode : t list -> string
end

III-C - Le code OCaml

III-C-1 - Type d'un lexique et lexique vide

Parmi les différentes solutions possibles, j'ai choisi d'utiliser un type enregistrement (record) non mutable. Il présente l'avantage d'alléger les notations par rapport à un couple (en particulier dans les arguments des fonctions auxiliaires internes). Ce record comporte deux éléments : un élément flag, qui indique si le nœud actuel correspond à un mot complet, et un élément cmap par lequel on accède aux nœuds supérieurs (autrement dit aux suffixes des mots de même préfixe, mais plus longs).

Type d'un lexique

type t = { flag : bool; cmap : t CharMap.t }

Si Char désigne le module de type CHAR donné en argument au foncteur, alors le module CharMap est défini de la façon suivante :

Module CharMap

module CharMap = Map.Make(Char)

Le foncteur Map.Make crée le module CharMap qui contient les fonctions de manipulation adaptées au type Char que nous venons de définir.

Signature du module CharMap

module CharMap :
sig
type key = Char.t
type 'a t = 'a Map.Make(Char).t
val empty : 'a t
val is_empty : 'a t -> bool
val add : key -> 'a -> 'a t -> 'a t
val find : key -> 'a t -> 'a
val remove : key -> 'a t -> 'a t
val mem : key -> 'a t -> bool
val iter : (key -> 'a -> unit) -> 'a t -> unit
val map : ('a -> 'b) -> 'a t -> 'b t
val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
end

Ceci étant, la définition et la manipulation d'un lexique vide sont alors très faciles :

Lexique vide

let empty = { flag = false; cmap = CharMap.empty }
let is_empty lex = not lex.flag && CharMap.is_empty lex.cmap

III-C-2 - Ajout d'un mot dans un lexique

L'ajout d'un mot dans un lexique consiste à progresser caractère par caractère dans le lexique jusqu'à épuiser tous les caractères du mot ; à ce niveau, le drapeau flag doit être redéfini comme étant égal à true. Si le mot à insérer n'est le préfixe d'aucun autre mot déjà présent dans le lexique, la fonction CharMap.find lèvera tôt ou tard l'exception Not_found. Dans ce cas, de nouveaux nœuds, initialement vides, devront être insérés dans le lexique pour achever l'insertion.

Ajout d'un mot

let add str lex =
let rec loop lex = function
| [] -> { lex with flag = true }
| chr :: t ->
let res = loop (try CharMap.find chr lex.cmap with _ -> empty) t in
{ lex with cmap = CharMap.add chr res lex.cmap }
in loop lex (Char.explode str)

Complexité en temps de la fonction add - La fonction add présentée ci-dessus insère un mot en autant d'étapes qu'il y a de caractères dans ce mot. Par ailleurs, le passage d'un nœud au nœud suivant s'effectue à l'aide de la fonction CharMap.find dont la complexité temporelle est O(log s) où s désigne la taille de la structure. Si l'on note S la plus grande des structures rencontrées lors de l'insertion d'un mot de longueur m, alors la complexité en temps de la fonction est O(m log S). Notons aussi que la fonction add n'est pas récursive terminale, ce qui exclut l'insertion de longs mots (mais pas l'utilisation d'un très grand lexique !). La valeur de m est par conséquent inférieure de plusieurs ordres de grandeur à la taille n du lexique.

III-C-3 - Appartenance d'un mot à un lexique

Pour tester l'appartenance d'un mot à un lexique, il suffit de progresser caractère par caractère dans l'arbre afin de récupérer la valeur du drapeau associé au dernier caractère du mot. Lorsque la fonction CharMap.find échoue prématurément, le mot est absent du lexique.

Test d'appartenance d'un mot

let mem str lex =
let rec loop lex = function
| [] -> lex.flag
| chr :: t when CharMap.mem chr lex.cmap ->
loop (CharMap.find chr lex.cmap) t
| _ -> false
in loop lex (Char.explode str)

Complexité en temps de la fonction mem - Cette fonction est très proche de la fonction add et possède une complexité temporelle identique, en O(m log S). Elle est récursive terminale.

On peut également écrire une version légèrement différente qui teste l'existence d'un préfixe dans le lexique :

Test d'appartenance d'un préfixe

let mem_prefix str lex =
let rec loop lex = function
| [] -> true
| chr :: t when CharMap.mem chr lex.cmap ->
loop (CharMap.find chr lex.cmap) t
| _ -> false
in loop lex (Char.explode str)

Complexité en temps de la fonction mem_prefix - Cette fonction est très proche de la fonction mem et possède une complexité temporelle identique, en O(m log S). Elle est récursive terminale.

III-C-4 - Supprimer un mot d'un lexique

Supprimer un mot d'un lexique consiste à redéfinir le drapeau associé au dernier caractère du mot en lui assignant la valeur false. Mais attention, ce n'est pas si simple ! Il faut aussi veiller à ne pas conserver les nœuds qui ne portent plus aucun mot. Ce point est très important, sinon l'ajout d'un mot au lexique vide, suivi de sa suppression, ne redonnera pas un lexique vide !

Suppression d'un mot

let remove str lex =
let rec loop lex = function
| [] -> { lex with flag = false }
| chr :: t when CharMap.mem chr lex.cmap ->
let res = loop (CharMap.find chr lex.cmap) t in
{ lex with cmap =
if is_empty res then CharMap.remove chr lex.cmap
else CharMap.add chr res lex.cmap }
| _ -> lex
in loop lex (Char.explode str)

Complexité en temps de la fonction remove - Cette fonction est très proche de la fonction add et possède une complexité temporelle identique, en O(m log S). Elle n'est pas récursive terminale.

III-C-5 - Taille d'un lexique

La taille d'un lexique est définie comme le nombre de mots qui le composent. Elle peut être obtenue de différentes manières plus ou moins lisibles et performantes. Celle qui semble la plus intuitive utilise CharMap.fold ; c'est celle que je vous présente ici (sachez qu'il en existe une autre plus efficace qui utilise des références et CharMap.iter; elle n'est utile que si vous devez calculer très souvent la taille de très gros lexiques).

Taille d'un lexique

let length lex =
let rec loop lex n =
CharMap.fold (fun _ -> loop) lex.cmap (n + if lex.flag then 1 else 0)
in loop lex 0

Complexité en temps de la fonction length - Cette fonction détermine la taille du lexique en comptant un à un les mots qui le composent. Sa complexité temporelle est donc en O(n) où n désigne la taille du lexique.

III-C-6 - Parcours des mots du lexique

La fonction compare définie dans le module Char permet d'écrire un itérateur iter qui applique une fonction f aux mots du lexique pris dans l'ordre lexicographique. La reconstruction des mots à partir des nœuds successifs de l'arbre fait appel à une fonction rev_implode qui, étant donnée une liste d'éléments de type Char.t, inverse l'ordre des éléments et renvoie une chaîne de caractères.

Taille d'un lexique

let iter f =
let rec loop seq lex =
if lex.flag then f (Char.rev_implode seq);
CharMap.iter (fun chr -> loop (chr :: seq)) lex.cmap
in loop []

III-C-7 - Fonction fold

Parmi les fonctions d'ordre supérieur, on trouve également les fonctions de type fold, qui permettent d'effectuer un calcul à l'aide d'une fonction qui reçoit en entrée les données d'une structure. Ici, la fonction reçoit les mots du lexique dans l'ordre lexicographique.

Taille d'un lexique

let fold f =
let rec loop seq lex acc =
CharMap.fold (fun chr -> loop (chr :: seq)) lex.cmap
(if lex.flag then f (Char.rev_implode seq) acc else acc)
in loop []

III-C-8 - Conversion en liste

Il arrive souvent que les données brutes soient disponibles sous forme de listes de mots. Dans ce cas, on peut écrire des fonctions de conversion of_list et to_list. Cette dernière renvoie une liste triée dans l'ordre lexicographique. Remarque : il existe une implémentation plus efficace de la fonction of_list (voir la section « Pour aller plus loin »).

Taille d'un lexique

let of_list = List.fold_left (fun lex str -> add str lex) empty

let to_list lex =
let rec loop seq lex acc =
CharMap.fold (fun chr -> loop (chr :: seq)) lex.cmap
(if lex.flag then seq :: acc else acc)
in List.rev_map Char.rev_implode (loop [] lex [])

Remarque - La fonction List.rev_map est récursive terminale, de sorte que la conversion en liste reste possible pour de très grands lexiques (ce qui ne présage en rien de la pertinence de cette conversion).

IV - Du lexique au dictionnaire

Jusqu'à présent, nous nous sommes intéressés à l'implémentation d'un lexique. Or il suffit de modifier légèrement l'implémentation pour obtenir un dictionnaire. Les mots deviennent alors des clefs auxquelles sont associées des données de type arbitraire. Pour y parvenir, nous allons adopter la convention suivante : la valeur None correspond au booléen false, et la valeur Some au booléen true, quelle que soit la valeur associée. Nous obtenons ainsi :

Des lexiques aux dictionnaires

type 'a t = { flag : 'a option; cmap = 'a t CharMap.t }

Le module DICTIONARY, qui remplace désormais LEXICON, possède la signature suivante :

Signature du module DICTIONARY

module type DICTIONARY =
sig
type 'a t
val empty : 'a t
val is_empty : 'a t -> bool
val add : string -> 'a -> 'a t -> 'a t
val mem : string -> 'a t -> bool
val mem_prefix : string -> 'a t -> bool
val remove : string -> 'a t -> 'a t
val length : 'a t -> int
val sub : string -> 'a t -> 'a t
val iter : (string -> 'a -> unit) -> 'a t -> unit
val fold : (string -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
val of_list : (string * 'a) list -> 'a t
val to_list : 'a t -> (string * 'a) list
end

V - Exemples d'application

V-A - Jeux de lettres

L'une des applications ludiques des lexiques concerne les jeux de lettres tels que le Boggle ou la recherche d'anagrammes. Leur structure est en effet très adaptée à la recherche de mots. En particulier, elle permet d'éviter de nombreuses comparaisons inutiles en décidant très rapidement d'interrompre une recherche lorsqu'un préfixe est absent. C'est particulièrement vrai au Boggle, où essayer toutes les combinaisons qui satisfont les contraintes du jeu dans une grille standard de 16 cases nécessite plusieurs dizaines de secondes (il y a plus de 12 millions de combinaisons valides selon les règles du jeu). Je vous invite à consulter les sources du logiciel OCamlBoggle pour voir comment les lexiques peuvent être mis à profit dans ces situations.

Remarque : Ce petit logiciel est un bon exemple d'utilisation grandeur nature des lexiques puisqu'il utilise une base de données de presque 610 000 mots. Il s'agit en fait d'un dictionnaire dans lequel les clefs sont les mots en majuscules et sans accents (ce qui correspond donc aux lettres piochées dans une grille de Boggle); la valeur associée à une clef n'est autre que la liste des mots accentués correspondants (par exemple, la clef PRATIQUE est associée à la liste [« pratique »; « pratiqué »]).

OCamlBoggle 1.1 - Jeu du Boggle

V-B - Applications bureautiques

Les logiciels de traitement de texte présentent souvent une fonctionnalité d'autocomplétion des mots au cours de la frappe. Certains éditeurs de texte l'étendent aux commandes d'un langage de programmation et/ou de balisage (par exemple les commandes LaTeX). Dans tous les cas, l'autocomplétion est grandement facilitée par la représentation des mots sous forme de trie : il suffit en effet d'extraire le sous-arbre correspondant à un préfixe donné pour connaître toutes les suggestions en rapport avec le texte saisi !

VI - Code complet

Fichier d'implémentation

module type CHAR =
sig
type t
val compare : t -> t -> int
val explode : string -> t list
val rev_implode : t list -> string
end

module type LEXICON =
sig
type t
val empty : t
val is_empty : t -> bool
val add : string -> t -> t
val mem : string -> t -> bool
val mem_prefix : string -> t -> bool
val remove : string -> t -> t
val length : t -> int
val sub : string -> t -> t
val iter : (string -> unit) -> t -> unit
val fold : (string -> 'a -> 'a) -> t -> 'a -> 'a
val of_list : string list -> t
val to_list : t -> string list
end

module Make (Char : CHAR) : LEXICON =
struct
module CharMap = Map.Make (Char)

type t = { flag : bool; cmap : t CharMap.t }

let empty = { flag = false; cmap = CharMap.empty }
let is_empty lex = not lex.flag && CharMap.is_empty lex.cmap

(* Ajout d'un mot dans un lexique. *)
let add str lex =
let rec loop lex = function
| [] -> { lex with flag = true }
| chr :: t ->
let res = loop (try CharMap.find chr lex.cmap with _ -> empty) t in
{ lex with cmap = CharMap.add chr res lex.cmap }
in loop lex (Char.explode str)

(* Teste l'appartenance d'un mot à un lexique. *)
let mem str lex =
let rec loop lex = function
| [] -> lex.flag
| chr :: t when CharMap.mem chr lex.cmap ->
loop (CharMap.find chr lex.cmap) t
| _ -> false
in loop lex (Char.explode str)

(* Teste l'existence d'un préfixe (et non d'un mot !) dans un lexique. *)
let mem_prefix str lex =
let rec loop lex = function
| [] -> true
| chr :: t when CharMap.mem chr lex.cmap ->
loop (CharMap.find chr lex.cmap) t
| _ -> false
in loop lex (Char.explode str)

(* Retire un mot d'un lexique. *)
let remove str lex =
let rec loop lex = function
| [] -> { lex with flag = false }
| chr :: t when CharMap.mem chr lex.cmap ->
let res = loop (CharMap.find chr lex.cmap) t in
{ lex with cmap =
if is_empty res then CharMap.remove chr lex.cmap
else CharMap.add chr res lex.cmap }
| _ -> lex
in loop lex (Char.explode str)

(* Compte le nombre de mots d'un lexique. *)
let length lex =
let rec loop lex n =
CharMap.fold (fun _ -> loop) lex.cmap (n + if lex.flag then 1 else 0)
in loop lex 0

(* Extrait tous les mots d'un lexique qui possèdent un préfixe donné. *)
let sub str lex =
let rec loop lex = function
| [] -> lex
| chr :: t when CharMap.mem chr lex.cmap ->
let res = loop (CharMap.find chr lex.cmap) t in
{ flag = false; cmap = CharMap.add chr res CharMap.empty}
| _ -> raise Not_found
in loop lex (Char.explode str)

(* Parcours ordonné des mots du lexique. *)
let iter f =
let rec loop seq lex =
if lex.flag then f (Char.rev_implode seq);
CharMap.iter (fun chr -> loop (chr :: seq)) lex.cmap
in loop []

(** Calcul à partir des mots du lexique. *)
let fold f =
let rec loop seq lex acc =
CharMap.fold (fun chr -> loop (chr :: seq)) lex.cmap
(if lex.flag then f (Char.rev_implode seq) acc else acc)
in loop []

(* Création d'un lexique à partir d'une liste de mots. *)
let of_list = List.fold_left (fun lex str -> add str lex) empty

(* Récupération des mots sous forme de liste ordonnée. *)
let to_list lex =
let rec loop seq lex acc =
CharMap.fold (fun chr -> loop (chr :: seq)) lex.cmap
(if lex.flag then seq :: acc else acc)
in List.rev_map Char.rev_implode (loop [] lex [])
end

(* Exemple d'application du foncteur. *)
module Latin1 : LEXICON = Make (
struct
type t = char
let compare = Char.compare
let explode str =
let rec loop acc = function
| 0 -> acc
| i -> let j = i - 1 in loop (str.[j] :: acc) j
in loop [] (String.length str)
let rev_implode = List.fold_left (fun str chr -> Printf.sprintf "%c%s" chr str) ""
end )

(* Autre exemple pour UTF-8 avec Glib. *)
module UTF_8 : LEXICON = Make (
struct
type t = Glib.unichar
let compare = compare
let explode str = Array.to_list (Glib.Utf8.to_unistring str)
let rev_implode l = Glib.Utf8.from_unistring (Array.of_list (List.rev l))
end )

VII - Pour aller plus loin

Vous trouverez ci-dessous quelques liens qui vous permettront d'approfondir le sujet abordé dans cet article :

- Wikipédia, l'encyclopédie libre (voir en particulier les articles trie et radix sort) ;

- Le blog de Matias Giovannini ;

- Okasaki, C., and Gill, A (1998). Fast Mergeable Integer Maps ;

- Recherche d'anagrammes par Jean-Christophe Filliâtre ;

- GraphViz, outil de visualisation de graphes ;

- Construction efficace d'un lexique ;

- Tries à tableaux d'enfants (langage Pascal).

VIII - Remerciements

Je tiens à remercier SpiceGuid et Gorgonite pour leur relecture critique. Merci également à LLB pour ses remarques constructives.

Je tiens également à saluer le travail de l'équipe de developpez.com sans laquelle ce tutoriel n'aurait pas vu le jour.