Algorithme de recherche approximative dans un dictionnaire fondé sur une distance d'édition définie par blocs
This work addresses dictionary search challenges in domains like text processing or NLP, but appears incremental as it modifies existing edit distance methods.
The paper tackles the problem of approximative dictionary lookup for altered strings by proposing an algorithm that uses a block-based edit distance, adaptable to specific corpora, to find entries within a threshold distance, achieving unspecified performance improvements.
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. Nous proposons un algorithme de recherche approximative de chaînes dans un dictionnaire à 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).