Résumé

Nous proposons un algorithme de recherche approximative de chaînes dans un dic- tionnaire à partir de formes altérées. Cet algorithme est fondé sur une fonction de divergence entre chaînes– une sorte de distance d’édition: il recherche des entrées pour lesquelles la distance à la chaîne cherchée est inférieure à un certain seuil. La fonction utilisée n’est pas la distance d’édition classique (distance DL); elle est adaptée à un corpus, et se fonde sur la prise en compte de coûts d’altération élémentaires définis non pas sur des caractères, mais sur des sous-chaînes (des blocs de caractères).

Abstract

We propose an algorithm for approximative dictionary lookup, where altered strings are matched against reference forms. The algorithm makes use of a divergence function between strings– broadly belonging to the family of edit distances; it finds dictionary entries whose distance to the search string is below a certain threshold. The divergence function is not the classical edit distance (DL distance); it is adaptable to a particular corpus, and is based on elementary alteration costs defined on character blocks, rather than on individual characters.