H2PTM (1999) Hallab

PROXILEX

Un outil d'approximation orthographique à partir des fréquences des N-grammes

---

 
 

Titre PROXILEX : Un outil d'approximation orthographique à partir des fréquences des N-grammes Auteurs Mohamed Hallab, Alain Lelu Affiliations université Paris 8, Département Hypermédia Dans actes du colloque H2PTM 1999 Paris publié dans H²PTM99 : Hypertextes hypermédias et internet; Réalisations, outils et méthodes

Résumé

On présente ici une méthode d'approximation orthographique rapide d'une chaîne de caractères tapée par l'utilisateur par rapport aux termes les plus proches issus d'une liste de grande taille : chaque mot de la liste, simple ou composé, est caractérisé par le profil de ses N-grammes, c'est à dire de toutes les chaînes de longueur fixe de n caractères qui s'y trouvent (ici chaque vecteur mot est caractérisé par les fréquences de ses bigrammes concaténées à celles de ses trigrammes). La mesure de proximité entre les chaînes utilise d'abord une distance vectorielle, puis un indicateur d'ordre des N-grammes communs. On compare cette procédure à la distance d'édition obtenue par programmation dynamique.

Mots-clés

Approximation orthographique, N-grammes, distance vectorielle, distance d'édition, programmation dynamique, comparaison de chaînes.

English description

Abstract

A fast lexical maching method is presented, for comparing a requested character string to the most similar terms in the system's vocabulary: each term, eithera single word or a phrase, is described by its N-grams frequency profiles. Our method first uses a vector distance, then a similarity index embedding the relative order between N-grams. we compare our procedure with the calculation of edit distance through dynamic programming.

Key words

Lexical matching, N-grams, vector distance, edit distance, dynamic programming, string matching.