Paquet : libagrep-ocaml-dev (1.1-1) [debports]

algorithme Wu-Manber pour la recherche de chaînes avec erreurs

La bibliothèque OCaml met en œuvre l'algorithme de Wu-Manber pour la recherche de chaînes avec erreurs, popularisé par la commande Unix « agrep » et l'outil d'indexation de fichier « glimpse ». Elle a été développée comme une partie d'un moteur de recherche pour une énorme collection de MP3 ; la recherche « avec erreur » est pratique pour tous ceux qui ne savent pas épeler Liszt ou Chostakovitch.

À partir d'une chaîne et d'un motif de recherche donnés, cet algorithme détermine si la chaîne contient une sous-chaîne qui correspond au motif jusqu'à un certain nombre N « d'erreurs » paramétrable. Une « erreur » peut être une substitution (remplacement d'un caractère de la chaîne par un autre caractère), une suppression (suppression d'un caractère) ou une insertion (ajout d'un caractère à la chaîne). En termes plus scientifiques, le nombre d'erreurs est la distance d'édition de Levenshtein entre le motif et la sous-chaîne correspondante.

Les motifs de recherche sont grossièrement ceux du shell Unix, dont le caractère de remplacement unique (?), les classes de caractères ([0-9]) et le caractère de remplacement multiple (*). En plus, la conjonction (&) et l'alternative (|) sont pris en charge. Néanmoins, les expressions rationnelles générales ne sont pas gérées.

Ce paquet fournit tout le matériel de développement nécessaire à l'utilisation de la bibliothèque OCaml agrep dans les programmes.

Cette page est uniquement disponible dans les langues suivantes (Comment configurer la langue par défaut du document) :