2021/09/01 by Pascal Vaillant, Vaillant, Pascal
Computer Science · #Algorithms and Data Compression #Computation and Language (cs.CL) #FOS: Computer and information sciences #H.3.3 #I.2.7 #Information Retrieval (cs.IR) #Rough Sets and Fuzzy Logic #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2109.00624
openalex created_date 2016/06/24 · openalex publication_date 2021/09/01 · openalex updated_date 2026/07/28
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).