Implémentation d'un lexique avec Objective Caml

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.

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.

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 :

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).

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 :

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-1. Type d'un lexique et lexique vide▲

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

module CharMap = Map.Make(Char)

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

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▲

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)

III-C-3. 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)

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)

III-C-4. Supprimer 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)

III-C-5. 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

III-C-6. Parcours 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 []

III-C-7. Fonction fold▲

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▲

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 [])

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é »]).

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 !