واژگان: خطایابی، اصلاح خطای کلمه ای، اصلاح خطای مفهوم گرا.
مقدمه
اصلاح خطا(3) در دو سطح «کلمهمحور»(4) و «مفهوممحور»(5) صورت میگیرد.
الف ـ اصلاح خطای کلمه ای
در قدیم، بیشتر خطاها قانونمند بودند. قالب های خطا برای اصلاح خطا استفاده میشد. از این دست کارها را دیمراو (1964)، آنجل (1983) و زوبل (1994) انجام دادند. اخیراً مدل های احتمالی برای اصلاح خطا استفاده میشوند. مجموعه دادهای خطادار برای یادگیری قالب های خطای موجود در مجموعه داده استفاده میشود[1]، [2]، [3].
به طور کلی، روشهای اصلاح کلمه ای به زیردسته های زیر تقسیم میشوند:
- • شگردهای فاصله ویرایشی (Edit Distance)؛
- • شگردهای مبتنی بر آواشناسی (Phonetics Based)؛
- • شگردهای کلید مشابهت (Similarity Key)؛
- • شگردهای چند وزنی (N-Gram Based)؛
- • شگردهای احتمال.
دسته های فوق، کاملاً مجزا نیستند؛ بلکه ممکن است اشتراک هایی با هم نیز داشته باشند.
1. شگردهای فاصله ویرایشی (EditDistance)
کلمه «Edit Distance» ابتدا توسط ونگر (1971) ابداع شد. منظور از این عبارت حداقل تغییرات مورد نیاز برای تبدیل یک رشته به رشته دیگر بود. مفهومی مشابه با این مفهوم توسط دیمراو (1964) تعریف شدهبود [4].
1-1. شگرد تکخطای دیمراو
دیمراو نشان داد که 80% تکخطاها متعلق به یکی از چهار دسته زیر میباشند:
- • درج یک حرف؛
- • حذف یک حرف؛
- • جایگزینی یک حرف؛
- • جابه جایی یک حرف با حرف همسایه.
این شگرد، 84% دقت بر روی 964 خطا از خود نشان داد.
گورین (1971) این روش را به صورت معکوس استفاده کرد تا با استفاده از چهار عمل فوق، برای کلمه های خطا مجموعه کلمات جایگزین را پیدا کند. این به آن معنا است که اگر طول کلمه خطا n و تعداد حروف الفبا 32 باشد، n کلمه جایگزین برای عمل حذف، n-1 کلمه جایگزین برای عمل جابهجایی، 32(n+1) کلمه جایگزین برای عمل درج و 31(n) کلمه جایگزین برای عمل جایگزینی و جمعا 65n+31 کلمه تولید میشود. معتبر بودن کلمات احتمالی پس از تولید، در واژه نامه بررسی میشود تا بتوان مجموعه کلمات جایگزین را به دست آورد. برای بهبود این آزمون، اصلاحیهای ارائه شد که توسط تولیدکنندگان نرمافزار STAVA استفاده شد[5]. آنها پیش از جستجو در واژه نامه، کلمات را با جداول N-Grams آزمودند. اگر کلمه ای دارای یک دنباله رشته غیرمجاز بود، آن کلمه از مجموعه جایگزین حذف میشد.
1-2. فاصلهLevenshtein
فاصلهی Levenshtein فاصله بین دو حرف را با عملگرهای درج، حذف و جایگزینی محاسبه میکند. اما در مقابل Damerau جامعتر است؛ چون به چندین خطا در یک کلمه اجازه وقوع میدهد[6].
1-3. Edit Distance وزندهی شده
در روشهایDamerau و Levenshtein، همه حروف با احتمال یکسانی قابل حذف و درج و با همه حروف قابل جایگزینی و جابهجایی هستند؛ در صورتی که حقیقتاً این حرکت اشتباهی است.
در تحقیقی که توسط کوکیچ (1992) انجام شد، نشان داده شد که 58% جایگزینیها ناشی از فشردن کلیدهای همسایه هستند.
برای استفاده از این روش، ماتریسی n در n ساخته میشود که n تعداد حروف الفبا است. و هر عنصر ijام ماتریس نشانه احتمال جایگزینی حرف i به حرف j است[6].
1-4. مخروطی کردن(6)
مخروطی کردن نیز یک شگرد برای اصلاح Edit Distance است؛ به این صورت که کلمه ای که در آخر با کلمه صحیح، متفاوت باشد، شبیه تر است نسبت به کلمه ای که در ابتدا متفاوت است[7].
2. شگردهای مبتنی بر آواشناسی(7)
این روشها بر روی آوای حروف جاافتاده در کلمات خطادار متمرکز میشوند. هدف این است که کلمه ای در واژه نامه یافت شود که از نظر آواشناختی به کلمات خطادار نزدیکتر باشد.
2-1. الگوریتم Soundex
اولین الگوریتم مقایسه رشته مبتنی بر آوا توسط اودل و راسل در سال 1918 ارائه شد. ایده اصلی این بود که به نامهای همآوا(8) کد مشترکی اختصاص بدهد.
1 = B, P, F, V
2 = C, S, G, J, K, Q, X, Z
3 = D, T
4 = L
5 = M, N
6 = R
تحقیق استینر (1990) نشان داد در جستجوی اسم، یک چهارم کلمات مرتبط پیدا نمیشوند و فقط یک سوم کلمات پیداشده کاملاً مرتبط هستند.
Soundex با رویکرد استفاده در خطایابی اصلاح شد. اصلیترین تغییر، شکستن گروه دوم به گروه های کوچکتر بود[9].
1 = B, P
2 = F, V
3 = C, S, K
4 = G, J
5 = Q, X, Z
6 = D, T
7 = L
8 = M, N
9 = R
تحقیقات نشان میدهد که احتمال خطا در ابتدای کلمه بسیار کم است[10].
کارهای زیادی برای بهبود این الگوریتم انجام شد که باعث افزایش دقت آن شد.
2-2. الگوریتم Blair'sAbbreviations
در این روش، هر کلمه از واژه نامه به 4 حرف مختصر میشود. در این تکنیک، کلماتی شبیه به هم میباشند که اختصار آنها با هم کاملاً منطبق باشند[11].
دیمراو در یک مقایسه نشان داد که این روش در خطاهای انسانی(9) یکسان و خیلی خوب عمل میکنند؛ اما در مقابل خطاهایی که مربوط به سیستم(10) هستند، خیلی ضعیف عمل میکند[12].
2-3. الگوریتم Phonix
این الگوریتم با روش Soundex متفاوت است. در بعضی پیادهسازیها قوانین تبدیل متفاوتی برای حروف در موقعیتها نوشته شده است[6]، [9]، [13]، [14]، [15].
1 = B, P
2 = C, G, J, K, Q
3 = D, T
4 = L
5 = M, N
6 = R
7 = F, V
8 = S, X, Z
فایفر در سال (1996) دو روش Soundex و برخی از انواع Phonix را در ترکیب با Edit Distance و شباهت Bigram اندازه گرفت و 80% دقت(11) و 80% بازخوانی(12) را گزارش داد.
2-4. الگوریتم Editex
این روش، ترکیبی از شگرد Edit Distance، دستهبندی حروف در شگردهای Soundex و Phonix است. در این روش، برای محاسبه Edit Distance، اگر دو حرف مربوطه برابر باشند، 0 اضافه میشود، اگر همگروه بودند، 1 اضافه میشود و در غیر این صورت، 2 اضافه میشود. این روش، در جایگزینی های هم گروه مقدار کمتری اضافه میکند و در جایگزینی های غیر هم گروه مقدار بیشتری اضافه میکند[9].
1 = B, P
2 = C, K, Q
3 = D, T
4 = L, R
5 = M, N
6 = G, J
7 = F, P, V
8 = S, X, Z
9 = C, S, Z
3. شگردهای کلیدمشابهت(13)
این شگرد مانند Soundex و Phonix، به حروف، کدهایی را اختصاص میدهد. این شگرد را میتوان با شگرد Edit Distance ترکیب نمود.
3-1. کلید شالوده(14)
کلید شالودهی یک کلمه، از اتصال حرف اوّل کلمه با حروف صامتی (تکراری حذف میشود) که پس از حروف صدادار در کلمه آمده اند، تشکیل شده است. این شگرد مانند Soundex فرض میکند که خطا در حرف اول به طور نادر اتفاق میافتد. بنابراین، نمیتواند خطای حرف اوّل را اصلاح کند[6].
3-2. کلید جاافتادگی(15)
آمار نشان میدهد که تناوب جاافتادگی حروف متفاوت است. در زبان انگلیسی این تناوب به صورت کاهشی، به ترتیب زیر است[16]:
R S T N L C H D P G M F B Y W V Z X Q K J
شگرد کلید جاافتادگی، حروف یک کلمه را به صورت معکوس ترتیب بالا مرتب میکند و سپس حروف صدادار را به ترتیب جای خود در کلمه به آن اضافه میکند[6]، [15].
3-3. کلید افلاطون(Plato Key)
این شگرد، یک کلید عددی است که شامل اطلاعاتی در مورد طول کلمه، حروف مورد استفاده، ترتیب حروف و تلفّظ هجایی است. کلید شگرد، انعطاف پذیر است؛ چون ویژگیهای جدید را میتوان به راحتی به آن افزود[4][6].
4.شگردهای احتمال
همه تکنیکهای بررسی شده، یافتن گزینه مناسب برای جایگزینی را مبتنی بر اندازهگیری شباهت و محاسبه انواع فاصله ها میدانند. اشکال این روشها آن است که عوامل مهمّی را که بر الگوی خطا اثر میگذارد، نادیده میگیرند. با شناخت چنین عواملی باید روشی جدید طراحی کرد. روش جامع و مناسب برای این کار، ساخت مدل خطای احتمالی است.
4-1. مدل Noisy Channel
مدل خطای احتمالی را که برای زبانها و زمینه های مختلف آموزش دیده باشد و بتواند پارامترهای خود را تنظیم کند، مدل Noisy Channel نامیدهاند. اگر Noisy Channel، درست مدل بشود، حدس صحیحی میتواند در مورد کلمه مورد نظر بزند[2]، [4]، [17].
این روش در بسیاری از برنامه های پردازش گفتار و پردازش متن که دارای انواع شناسایی و طبقه بندی داده های ناقص و مبهوم بوده، موفق عمل کرده است[17].
از آنجایی که این احتمالها رفتار منشأ خطا را نشان میدهند، آنها را Channel Probabilities می نامند[4].
روش Noisy Channel برای اوّلین بار برای بررسی خطا در سال 1990 انجام شد[18]. روش احتمالات، فقط برای رتبه بندی گزینه ها استفاده شد.
این شگرد یادگیری مدل، یک نمونه از الگوریتم EM است که در آن پارامترهای مدل، مکرّراً تا رسیدن به وضعیت ایستا، تخمین زده میشوند[17].
یک شگرد بسیار جامعتر و به مراتب پیچیدهتر با به کارگیری Noisy Channel، توسط بریل و مور (2000) ارائه شده است. به جای استفاده از عملهای اصلاحی حرف به حرف که توسط چرچ و گیل (1990) انجام شده بود، عملهای اصلاحی، رشته به رشته عمل میکنند. یک رشته، دنباله ای از حرف به تعداد صفر یا بیشتر است. استفاده از عملهای جامعتر کمک میکند که مدل چندین خطا را به خوبی یک خطا، پشتیبانی کند.
برای محاسبه احتمال تبدیل واژه صحیح به واژه خطا، باید احتمال تبدیل حروف واژه صحیح به حروف واژه خطا را سنجید و در هم ضرب نمود.
همانطور که دیده شد، محاسبه احتمال تبدیل واژه صحیح به واژه خطا، از طریق داده های یادگیری محاسبه میشود؛ اما محاسبه تعداد واژه خطا در متن کمی مشکل است. اگر ما مدل را با استفاده از یک مجموعه نوشته یادگیری میکنیم، بهراحتی میتوان تعداد رویدادهای رشته در مجموعه را معادل تعداد واژه خطا قرار داد. اما اگر تعداد تبدیلها با استفاده از یک مجموعه یادگیری محاسبه شده، آنگاه باید مجموعه ای مستقل را برای تخمین تعداد واژه خطا به کار برد؛ به صورتی که تعداد رویداد جایگزینی در آن مجموعه را محاسبه کرده و سپس آن را به وسیله یک ضریب خطای انسانی هنجار کنیم.
در شگرد اولیّه که توسط بریل و مور ارائه شد، یک واژه نامه در یک Trie گنجانده شد.
یک Trie نوع ویژهای درخت مرتب شده است که برای ذخیره سازی آرایه های انجمنی(16) که معمولا کلید آنها رشته حروف الفبا میباشد، استفاده میشود[19].
چرچ و گیل با استفاده از پارامترهای اغتشاش مکان(17) و یک پنجره(18) سهتایی، دقتی برابر 98.8% گزارش کردند[18].
4-2. مدل Noisy Channel اصلاحشده
در مدل Noisy Channel اصلاحشده که توسط توتانوا و مور در سال 2002 ارائه شد، α و β دنباله ای از آواها است. در این شگرد، همه کلمات واژه نامه و عبارتهای خطا باید از دنباله ای از حروف تبدیل به دنباله آوا شوند. این کار برای کلمات واژه نامه آسان است؛ چون تلفظ مشخصی دارند؛ اما در عبارتهای خطا، مدل انتقال حرف به آوا نیاز است. متداولترین مدل برای این کار، مدل N-Grams متعلق به فیشر است[3].
توتانوا و مور نشان دادند که ترکیب مدل Noisy Channel برمبنای آوا و مدل Noisy Channel بر مبنای حرف، بازدهی بیشتری نسبت به هرکدام از آنها بهتنهایی را میدهد. روش ترکیبی، تصحیح را با دقت 95.58% و سه گزینه بهتر با دقت 99.50% جواب را پیدا میکند.
ب ـ اصلاح خطای مفهومگرا
بسیاری از ابزارها هستند که نیاز به اصلاح خودکار دارند. در این ابزارها مداخله انسان ممکن نیست. بنابراین، خطایابی نباید بیش از یک پیشنهاد داشته باشد. چرچ و گیل (1990) کشف کردند که واژهی پیشنهادی سیستم بدون توجه به مفهوم لزوماً گزینه مناسب نیست.
طبق تحقیق کوکیچ (1992)، بعضی تحلیلها ادعا دارند که 15 تا 40% کل خطاها در خطایابی، مربوط به خطای لغت هستند[4].
در مقایسه با خطای غیر لغت، خطای لغت بسیار مشکلتر است؛ چون خطای لغت فقط مربوط به واژه نگاری یا خطایابی نیست. ممکن است که مربوط به خطای نحوی(19)، معنایی(20)، کلامی (ادا کردن) و یا خطای مصطلح(21) باشد.
از آنجا که بیشتر خطاهای لغوی مفهوم گرا، ریشه در خطای نحوی دارند و به علت ساده بودن مدیریت این خطاها، پردازش زبان بر روی قوانین آن تمرکز دارد. ضمن اینکه ترکیب اطلاعات نحوی و مفاهیم معنایی، دسترسی به جواب را آسانتر میکند[4].
شگردهای آماری نیز برای حل این مشکل استفاده شدهاند که احتمال باهم آیی لغات از این جمله است.
تمام شگردهای اصلاح خطای واژه، نیاز به دانستن نحو زبان و مجموعه داده وسیع متوازن(22) دارند.
ج-خطایاب نور
خطایاب نور هم اکنون با استفاده از از مدل Noisy Channel پیادهسازی شدهاست. خطایاب نور با دریافت کلمه خطا، تمام کلمات صحیح جایگزین را به همراه درصد صحتشان نمایش میدهد. در شکل(1)، نمونه خروجی برنامه مشاهده میشود.
شکل(1): نمونه خروجی خطایاب نور
1. ارائه پیشنهادهای صحیح
مرحله اول اجرای این برنامه، یافتن کلماتی است که با استفاده از شگرد تکخطای دیمراو، فاصلهای به اندازه یک داشته باشند؛ یعنی کلماتی را که با کلمه خطا یک تفاوت درج، حذف، جایگزینی و یا جابجایی دارند، پیدا میکند. در مرحله بعدی، کلماتی را که در واژه نامه موجود نیستند، حذف میکند.
برای مثال، اگر واژه «پادشا» را به عنوان واژه خطا به ورودی بدهیم، برنامه جانشینهای صحیحی را که در جدول (1) آمده است، پیشنهاد میدهد. با توجه به این جدول، واژه خطای «پادشا» میتواند با استفاده از Noisy Channel به واژه صحیح «پادشاه» تبدیل شود. این تبدیل با درج «ه» پس از حرف پنجم کلمه، یعنی «ا» صورت میگیرد.
جدول(1) : نحوه انتقال از واژه خطا به واژه صحیح
2. امتیازدهی
برای امتیازدهی به هر واژه پیشنهادشده، ابتدا احتمال اولیّه آن بر حسب تکرار آن واژه در متن محاسبه میشود.
در این مثال، تعداد تکرار واژه مورد نظر در 400 جلد کتاب تایپشده توسط مرکز تحقیقات کامپیوتری علوم اسلامی نور میباشد. تعداد کلمات این 400 جلد کتاب برابر 34 میلیون و 337 هزار و 299 کلمه است.
با توجه به روش باکس و تیائو میتوان با استفاده از یک احتمال اولیّه ناآموخته به یک توزیع پسین(23) برای یک واژه رسید. میزان در نظر گرفته شده برای این مقدار تعداد تکرار به علاوه 0.5 میباشد. این احتمال را تخمین شباهت مورد انتظار(24) مینامند[20].
نقاط ضعف این روش، در تحقیقات چرچ و گیل بررسی شده است[1].
پس از محاسبه (P(c، احتمالهای شرطی (P(t|c ، بر حسب تغییر انجامشده در واژه خطا محاسبه میشود.
هر واژه پیشنهادشده براساس ضرب احتمال واژه در احتمال شرطی، امتیازدهی میشود.
سپس به وسیله جمع امتیاز همه واژه های پیشنهادی با توجه به جدول (2)، احتمالهای خام و نرمالشده برای گزینه های پیشنهادشده برای واژه «پادشا» محاسبه شده است.
این پروژه، هماکنون در مرحله ارزیابی قرار دارد.
جدول(2): نمونه محاسبه (Score(c
پی نوشت ها:
1. Spell Checking.2. Lexicon.
3. Spelling Error Correction.
4. Isolated Word.
5. Context Based.
6. Tapering.
7. Phonetics Based.
8. Similar Sounding Names.
9. Orthographical.
10. Equipment Malfunction.
11. Precision.
12. Recall.
13. Similarity Key.
14. Skeleton Key.
15. Omission Key.
16. Associative Arrays.
17. Position Confusion.
18. Context Window.
19. Syntactic.
20. Semantic.
21. Pragmatic.
22. Balanced corpus of the language.
23. Posterior Distribution.
24. Expected Likelihood Estimate (ELE).
منابع:
[1]Church, K., Gale, W.,"Probability Scoring for Spelling Correction", Statistics and Computing, Vol. 1, pp. 93-103, 1991.[2]Brill, E., Moore, R. C.,"An Improved Error Model for Noisy Channel Spelling Correction. In proceedings of 38th Annual meeting of Association for Computational Linguistics, pp. 286-293, 2000.
[3]Toutanova, K., Moore, R. C., "Pronunciation Modeling for Improved Spelling Correction"In proceedings of 40th Annual meeting of Association for Computational Linguistics, pp. 144-151, 2002.
[4]Kukich, K.,"Techniques for Automatically Correcting Words in Text", ACM Computing Survey, Vol. 14, No. 4, pp 377-439, 1992.
[5]Kann, V.,Domeij, R., Hollman, J., Tillenius, M., "Implementation Aspects and Applications of A Spelling CorrectionAlgorithm", 1998.
[6]Erikson, K.,"Approximate Swedish Name Matching - Survey and Test ofDifferentAlgorithms", 1997.
[7]Zobel, J., Dart, P. "Phonetic String Matching: Lessons from Information Retrieval", 1996.
[8]Pollock, J.,Zamora, A. "Automaticspelling correction inscientific and scholarly text",CACM, pp. 27, 358-368, 1984.
[9]Zobel, J., Dart, P. "Finding Approximate Matches in Large Lexicons", Software-Practiceand Experience, Vol. 25, No. 3,pp. 331-345, 1995.
[10]Christian,P., "Soundex - can it be improved?",Computers in Genealogy, Vol. 6, No. 5, 1998.
[11]Alberga, C.N.,"String Similarity and Misspelling", In Communications of ACM, Vol. 10,No. 5, pp. 302-313,1967.
[12]Damerau, F.J.,"A Technique for Computer Detection and Correction of Spelling Errors",In Communications of ACM, Vol. 7, No. 3, pp. 171-177, 1964.
[13]Holmes, D., McCabe, C. M., "Improving precision andrecall for soundexretrieval",In Proceedings of the IEEE International Conference on Information Technology -Codingand Computing (ITCC), Las Vegas, 2002.
[14]Pfeifer, U., Poersch, T., Fuhr, N., "Searching Proper Names in Databases", Proceedings of the Conference on Hyper-text-Information Retrieval-Multimedia,Germany, pp. 259-275, 1995.
[15]Pfeifer, U., Poersch, T., Fuhr, N., "Retrieval Effectiveness of Name Search Methods", Information Processing and Management, Vol. 32, No. 6, pp. 667-679, 1996.
[16]Pollock, J.J., Zamora, A.,"Automaticspelling correction in scientific and scholarly text", CACM, Vol. 27, pp. 358-368, 1984.
[17]Jurafsky, D., Martin, J. H., "Speech and Language Processing.: An Introduction to Natural Language Processing", Computational Linguistics and Speech Recognition Prentice Hall, 1st edition, 2000.
[18]Kernighan, M. D., Church, K. W., Gale, W. A., "A Spelling Correction Program Based on a Noisy Channel Model", In Proceedings of COLING-90, The 13th International Conference On Computational Linguistics, Vol. 2, 1990.
[19]http://en.wikipedia.org/wiki/Trie
[20]Box, G. E. P., Tiao, G. C., "Bayesian Inference in Statistical Analysis", Addison-Wesley, Reading, Massachussets, 1973