ره آورد نور

 واژگان: خطایابی، اصلاح خطای کلمه‏ ای، اصلاح خطای مفهوم‏ گرا.

مقدمه

اصلاح خطا(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

پی نوشت ها:

منابع: