Embed Size (px)
Citation preview
La correction automatique d’orthographe dans la
langue arabe
Nejja Mohammed1, Yousfi Abdellah
2
1 Équipe Telecom et systèmes embarqués,
ENSIAS, Mohammed V University In Rabat- Morroco
2Équipe ERADIASS
FSJES, Mohammed V UniversityIn Rabat- Morroco
Résumé
Ce papier porte sur la correction automatique des erreurs orthographiques dans la langue arabe. La présente étude présente
unmécanisme à utiliser pour résoudre le problème proposé par le
correcteur d’orthographe qui réside dans l’insuffisance de lexique utilisé.
Dans ce contexte, nous avons traité deux axes : La correction automatique
d’orthographe en utilisant le schème de surface et la gestion de vocabulaire.
1. Introduction
Le système de correction automatique des textes est l’un des plus anciennes
applications des techniques de traitement automatique des langues [mitton
2010]. La correction orthographique consiste à trouver le mot le plus proche
au celui erroné en se basant généralement sur un dictionnaire contenant
l’ensemble des mots de la langue donnée.
Les premières techniques de la correction automatique d’orthographe
consistent à chercher le mot dans le dictionnaire, elles prospectent
simplement si la chaîne en entrée apparaît ou non dans la liste des mots
valides. Si la chaîne est absente du dictionnaire alors elle est dite erronée et
le système propose à l’utilisateur des candidats les plus proches au celui
erroné.
Aujourd’hui, plusieurs techniques sont disponible pour détecter et corriger
les fautes d’orthographe, notamment les systèmes s’appuyant sur des
automates à états finis (pondérés) (Ringlstetter et al. , 2006), Les méthodes
adoptant le modèle du canal bruité (Kernighan et al. , 1990; Brillet Moore,
2000; KolaketResnik, 2002), des systèmes basés sur le principe d’utilisation
LA CORRECTION AUTOMATIQUE D’ORTHOGRAPHE DANS LA LANGUE ARABE
des HMM [2], Les techniques basées sur le modèle n-gramme
(Ukkonen,1992), la distance d’Edition…
Dans cet article, nous nous somme intéressé à la correction automatique
d’orthographe dans la langue arabe via la technique de la distance d’édition
en exploitant les informations morphologique des mots. Ces techniques dont
nous citons visent à réduire la taille du dictionnaire utilisé ainsi que le
nombre des mots à comparer afin d’assurer la performance de système de
correction automatique d’orthographe.
2. La distance de levenshtien
La distance de Levenshtein (Levenshtein, 1966) est une distance
mathématique donnant une mesure de la similarité entre deux chaînes de
caractères. Elle est égale au nombre minimal de caractères qu'il faut
supprimer, insérer ou remplacer pour passer d’une chaîne à l’autre.
L'algorithme de levenshtein utilise une matrice de (N + 1) * (P + 1) « avec N
et P les longueurs des chaines de caractères à comparer T, S». la distance
entre les chaines T et S est définie par :
M 𝑖, 𝑗 = Min
M 𝑖 − 1, 𝑗 + 1
M 𝑖, 𝑗 − 1 + 1
M i − 1, j − 1 + Cout i − 1, j − 1
(1)
Avec
Cout i, j = 0 si T 𝑖 = S 𝑗
1 si T i ≠ S 𝑗 (2)
3. Les schèmes de surface
Le Schème arabe permet essentiellement de déterminer la structure de la
plupart des mots (les noms, les verbes conjugués, etc.). Les schèmes sont des
déclinaisons du mot «فعل » qui sont obtenus en utilisant des diacritiques ou
en y ajoutant des affixes.
Le schème de يكتبو ’ est يفعلو . Les lettres "ف،ع،ل " remplacent les lettres de
la racine de يكتبو , et le schème de " ل نا " est فعل" ".
LA CORRECTION AUTOMATIQUE D’ORTHOGRAPHE DANS LA LANGUE ARABE
Ce type de schème ne peut pas présenter les variations morphologiques du
mot (par exemple le nom االل du verbe (ال ). C'est pour cela que M. Yousfi a
proposé un schème adapté appelé schème de surface (Yousfi, 2010).
Exemple:
La conjugaison du mot " au participe actif à la 1ére personne du " رعى
singulier, est " راع ", alors le schème de surface de la racine "رعى " est "فعى "
et " فاع " est le schème de surface de " راع ".
Le schème de surface de " آزل " est " ف ل " et de " آزاال " est " فعاال ".
4. La correction morphologique par des schèmes de surface dans l‘algorithme de levenshtein
4.1. Objectif
Notre objectif consiste à remédier aux problèmes proposés par les systèmes
de la correction automatique d’orthographe, et donc fournir un correcteur
pertinent.Parmi les problèmes étudiés, je cite l’insuffisance de lexique
utilisé, en fait le principe de détection de l’erreur consiste à se servir d’un
dictionnaire de taille très large contenant tous les mots de langue dans leurs
différentes formes, ce qui est généralement difficile à construire. Pour
remédier à ce problème nous avons proposé une solution en exploitant la
propriété de la dérivation des mots arabe. En fait, la plupart des mots arabe
sont des déclinaisons (mot dérivé) de mot فعل en ajoutant des affixes et/ou
diacritique.
Exemple
racine Schème Mot dirivé
مكتوب مفعول كتب
ستلعبو ستفعلو لعب
شارب فاعل شزب
4.2. La solution proposée
La méthode que nous avons proposé (Nejja et Yousfi, 2014 ; Nejja et Yousfi,
2015) est basée sur deux dictionnaires, un contient l’ensemble des racines,
l’autre contient l’ensemble des schèmes. Donc à partir d’une base de
données contient 10000 racines et 10000 schèmes, nous pouvons traiter
(vérifier et corriger) jusqu’à 100000000 mots.
LA CORRECTION AUTOMATIQUE D’ORTHOGRAPHE DANS LA LANGUE ARABE
Figure. 1. Extrait des mots traités
Pour mettre en œuvre cette idée, nous avons élaboré des approches basées
dans un premier temps sur l‘identification du schème de surface le plus
proche au mot erroné. Pour ce faire nous avons adapté la distance de
levenshtein à la langue arabe pour extraire les schèmes de surface les plus
correct.
La distance de levenshtein adaptée à la sélection du schème de surface (noté
A) et le mot en entrée (noté w) est définie par :
LA CORRECTION AUTOMATIQUE D’ORTHOGRAPHE DANS LA LANGUE ARABE
M 𝑘, 𝑝 = Min
M 𝑘 − 1, 𝑝 + 1
M 𝑘, 𝑝 − 1 + 1
M 𝑘 − 1, 𝑝 − 1 + Cout k − 1, t − 1
(1)
avec
Cout k, p = 1 𝑠𝑖𝐴 𝑘 ≠ 𝑤 𝑝 𝑒𝑡𝐴 𝑘 ∉ ,‘ف} ,‘ع‘ {‘ل‘
0 𝑠𝑖𝐴 𝑘 = 𝑤 𝑝 𝑜𝑢𝐴 𝑘 ∊ 𝛽{ف‘, ,‘ع‘ {‘ل‘ (3)
Exemple
Soit : le mot ستلعبو et le schème de surface ستفعلو donc la distance de
levenshtein adapté est 0 :
ن و ب ع ل ت س
0 1 2 3 4 5 6 7
6 5 4 3 2 1 0 1 س
5 4 3 2 1 0 1 2 ت
4 3 2 1 0 1 2 3 ف
3 2 1 0 1 2 3 4 ع
2 1 0 1 2 3 4 5 ل
1 0 1 2 3 4 5 6 و
0 1 2 3 4 5 6 7 ن
Figure. 2. La matrice de calcul de la distance de levenshtein adaptée
LA CORRECTION AUTOMATIQUE D’ORTHOGRAPHE DANS LA LANGUE ARABE
Cependant, cette approche présente aussi un inconvénient qui réside dans le
fait que le schème de surface désiré peut être parfois situé en dernière
position. Cela est due au grand nombre des solutions proposées ayant la
même distance.
Exemple :
Pour le mot erroné ستتبو nous avons obtenu le résultat suivant :
Figure. 3. Extrait des schèmes de surface proposés pour le mot ستتبون par la
formule 3
Pour remédier à cette lacune, nous avons amélioré la formule utilisée pour la
sélection de schème de surface en partant de l’hypothèse que chaque
caractère peut être un caractère de la racine ou bien un caractère de schème
de surface :
M 𝑘, 𝑝 = Min
M 𝑘 − 1, 𝑝 + 1
M 𝑘, 𝑝 − 1 + 1
M 𝑘 − 1, 𝑝 − 1 + Cout k − 1, t − 1
(1)
avec
Edit
Distance
Surface
Patterns
ستفعلون 1
سيفعلون 1
نفاعلوا 3
… …
ستتبون
LA CORRECTION AUTOMATIQUE D’ORTHOGRAPHE DANS LA LANGUE ARABE
cosu k, p =
1 𝑠𝑖 𝐴 𝑘 ≠ 𝐵 𝑝 𝑒𝑡 𝐴 𝑘 ∉ ل ع ف
0 𝑠𝑖 𝐴 𝑘 ∊ ل ع ف
0,2 𝑠𝑖 𝐴 𝑘 = 𝐵 𝑝 𝑒𝑡 𝐴 𝑘 ∉ 𝑒𝑡 𝑝 ل فع = 𝑘
0 ,5 𝑖𝑠 𝐴 𝑘 = 𝐵 𝑝 𝑒𝑡 𝐴 𝑘 ∉ 𝑒𝑡 𝑝 ل ع ف ≠ 𝑘
(4)
La modification que nous avons introduit dans la formule nous a permet
d’augmenter la précision de la sélection de schème de surface. Pour le même
exemple nous avons obtenu le résultat suivant :
Figure. 4. Extrait des schèmes de surface proposés pour le mot ستتبون par la
formule4
Une fois le schème de surface est identifié, nous créons un ensemble des
candidats potentiels par la dérivation de toutes les racines en utilisant le
schème de surface identifié. Enfin nous comparons le mot en entré avec ces
candidats potentiels en utilisant la distance de levenshtein.
Exemple :
soit
Le mot erroné ستتبو
Le schème de surface le plus proche : ستفعلو
Liste des racines [خزج ,كتب,ذهب…]
Edit
Distance
Surface
Patterns
ستفعلون 1.9
سيفعلون 2.2
نفاعلوا 2.5
… …
ستتبون
LA CORRECTION AUTOMATIQUE D’ORTHOGRAPHE DANS LA LANGUE ARABE
Donc les candidats potentiels sont [ ستذهبو ,ستكتبو ,ستخزآو …]
En comparant ces candidats potentiels avec le mot erroné, nous proposons le
mot ستكتبو comme une solution, car il s’agit de la solution la plus proche
lexicalement au mot erroné.
5. La gestion du corpus et la morphologie dans la correction automatique d’orthographe
La réduction du temps de correction nécessaire pour détecter et corriger les
fautes d’orthographe dans un texte est vue sous 1'angle de l'optimisation du
nombre d'accès au vocabulaire, cette optimisation est restée, depuis
longtemps, un défi.
La solution que nous avons proposé (Nejja et Yousfi,2016) est fondée sur
l’utilisation d’un corpus noté C constitué par un ensemble de dictionnaires
noté DictRiau lieu d’un seul. Chacun d’eux est se compose par des mots
dérivés uniques et non redondants d’un dictionnaire à l’autre étant donné que
le vocabulaire de la langue arabe est essentiellement construit à partir des
racines.
𝑪 = 𝑫𝒊𝒄𝒕𝑹𝟏 ∪ 𝑫𝒊𝒄𝒕𝑹𝟐 ∪ …∪ 𝑫𝒊𝒄𝒕𝑹𝒏(5)
La segmentation du corpus vise à réduire le nombre des mots à comparer en
limitant l'accès uniquement au dictionnaire avec la plus grande probabilité de
contenir le mot désiré et respectant la règle ci-dessous :
𝑆𝑖 𝑅𝑖 ∩ 𝑤𝑒𝑟𝑟 𝑒𝑠𝑡 𝑛𝑜𝑛 𝑣𝑖𝑑𝑒 𝑎𝑙𝑜𝑟𝑠 𝑛𝑜𝑢𝑠 𝑝𝑟𝑒𝑛𝑑𝑒𝑟𝑜𝑛𝑠 𝑒𝑛 𝑐𝑜𝑛𝑠𝑖𝑑é𝑟𝑎𝑡𝑖𝑜𝑛 𝑐𝑒 𝑑𝑖𝑐𝑡𝑖𝑜𝑛𝑛𝑎𝑖𝑟𝑒
𝑆𝑖 𝑅𝑖 ∩ 𝑤𝑒𝑟𝑟 𝑒𝑠𝑡 𝑣𝑖𝑑𝑒 𝑎𝑙𝑜𝑟𝑠 𝑛𝑜𝑢𝑠 é𝑙𝑖𝑚𝑖𝑛𝑜𝑛𝑠 𝑐𝑒 𝑑𝑖𝑐𝑡𝑖𝑜𝑛𝑛𝑎𝑖𝑟𝑒
(6)
avecRi la racine des mots qui font partie du dictionnaire i.
La précédente règle nous évitera de faire des calculs inutiles et d'accéder à
l'ensemble des données. Seuls les dictionnaires répondant à la règle seront
consultés ce qui résulte en un gain en temps de correction.
Pour une bonne illustration, considérons l'exemple suivant:
Soit le corpus rétrécit C contenant les 5 dictionnaires qui suivent:
LA CORRECTION AUTOMATIQUE D’ORTHOGRAPHE DANS LA LANGUE ARABE
dict 1 contenant les mots dérivés de la racine شزب
dict 2 contenant les mots dérivés de la racine حذف
dict 3 contenant les mots dérivés de la racine لعب
dict 4 contenant les mots dérivés de la racine كنز
dict 5 contenant les mots dérivés de la racine كزه
Supposons que chaque dictionnaire contient 10000 mots dérivés, sachant que
le nombre des mots dérivés d'une racine dans la langue arabe est largement
supérieur à celui de l'exemple (10000).
Pour le mot erroné "ملغب " et en appliquant la règle au-dessus, nous avons
accès uniquement aux dictionnaires 1 et 3, car pour les autres
dictionnaires Ri ∩ Werr est vide. Ainsi, le temps d'exécution se voit réduit vu
que nous gagnons le temps d'accès, de parcours et de comparaison avec les
(3 * 10000) mots des dictionnaires restants.
Le corpus implémenté est organisé selon l’architecture suivante:
Partition 1 regroupe tous les mots non assimilés par le système
morphologique dérivationnel de l'arabe. Cette partition contient les mots
outils à savoir les prépositions et les pronoms, etc..ainsi que les mots vides
et les mots propres tels que les noms des villes, les noms des objets, etc....
Partition 2 Cette partition est construite par tous les mots arabes assimilés
par le système morphologique dérivationnel de l’arabe, elle contient une
centaine de sous dictionnaires possédant chacun son propre vocabulaire à
base de mots dérivés [à partir d’une racine] uniques et non redondants d’un
dictionnaire à l’autre.
Pour vérifier et corriger un mot en entrée, nous procédons comme suite :
Nous avons commencé la vérification et correction par la partition 1 en
utilisant l’algorithme de levenshtein. Si le mot en entrée apparaît dans la liste
des mots outils ou bien les mots vides (distance de levenshtein égale à 0)
nous mettons fin à la vérification (le mot fait partie de la langue). Si la
chaîne est absente du dictionnaire (aucune distance de levenshtein n’est
égale à 0) alors nous gardons les solutions les plus proche au mot en entrée
puis nous sélectionnons les sous dictionnaires appartenant à la partition 2 et
respectant la règle 5. En utilisant l’algorithme de levenshtein, nous
comparons le mot en entrée avec tous les mots dérivés appartenant aux sous
dictionnaires sélectionnés. Si le mot existe dans un sous dictionnaire
LA CORRECTION AUTOMATIQUE D’ORTHOGRAPHE DANS LA LANGUE ARABE
(distance de levensthein égale à 0), nous mettons fin à la vérification. Sinon,
nous rassemblons les mots proposés comme solutions au mot en entrée avec
les solutions que nous avons déjà gardé pour les organiser selon la distance
de lenvenshtein et enfin nous proposons un ensemble des mots les plus
proches au mot en entrée.
6. Conclusion
Dans ce travail, nous avons proposé deux techniques utilisées de vérification
et éventuellement la correction des mots de la langue arabes sur le plan
lexical. La première se base sur l’identification des schèmes de surface les
plus proche au mot en entrée. Dans ce contexte, nous avons adapté
l’algorithme de levenshtein à la langue arabe puis corriger le mot en entré
selon le schème de surface identifié. Pour la deuxième technique, nous avons
proposé une gestion de dictionnaire qui nous a permis de limiter l’accès à
toutes les données du dictionnaire pour réduire le nombre des mots à
comparer en évitant les comparaisons inutiles.
Références
Ringlstetter C. Schulz K. U. Mihov S. and Louka K. (2006). The same is not the
same—postcorrection of alphabet confusion errors in mixed-alphabet ocr recognition. Proceedings of the 8th International Conference on Document Analysis and Recognition (ICDAR’05), pp. 406–410.
Kernighan M., Church K. and W.A. G. (1990).A spelling correction program based on a noisy channel model.Proceedings of the 13th conference on Computational linguistics, p. 205–210.
Brill E. andMoore R. C. (2000).An Improved Error Model for Noisy Channel Spelling Correction.Proceedings of the 38th Annual Meeting on Association for Computational Linguistics (ACL’00), pp. 286–293.
KolakO. andResnikP. (2002).OCR error correction using a noisy channel model.Proceedings of the Second International Conference on Human Language Technology Research (HLT’02). pp. 257–262.
Brucq.D. and EI Youbi. A. (1996). Representation de chaines de caracteres par des chaines induites de Markov.Actes RFIA. pp. 651-658.
Ukkonen,E. (1992). Approximate string matching with q-grams and maximal matches.Theoretical Computer Science. pp. 191-211.
Levenshtein.V. (1965).Binary codes capable of correcting deletions, insertions, and reversals.Cybernetics and Control Theory, pp. 707–710.
Yousfi, A. (2010). The morphological analysis of Arabic verbs by using the surface patterns.International Journal of Computer Science Issues, Vol. 7.
Nejja M. and Yousfi A. (2014).Correction of the Arabic derived words using surface patterns.Workshop on Codes, Cryptography and Communication Systems.
LA CORRECTION AUTOMATIQUE D’ORTHOGRAPHE DANS LA LANGUE ARABE Nejja M. and Yousfi A. (2015).A lightweight system for correction of Arabic
derived words.MediterraneanConference on Information & Communication Technologies.
