خطایابی املائی

شرح مساله وکارهای مرتبط

وقتی نوشته‌ای را تایپ می‌کنیم،ممکن است حرفی را از قلم بیاندازیم و یا حرفی را اضافه تر قراردهیم ویا املایش را درست ندانیم مثلا ندانیم که کلمه ی قسطنطنیه با کدام ت در زبان فارسی نوشته می شود وبین دو حرف «ت» و «ط» شک داشته باشیم.این دسته از خطاهای انسانی اجتناب ناپذیر است وتشخیص و تصحیح دستی آن‌ها سخت و زمان‌بر خواهد بود علی الخصوص اگر متن نوشته شده طولانی باشد.لذا نیاز به یک سامانه تشخیص هوشمند خطاهای املائی در متن احساس شده است.

مقدمه

مسئله ی پیدا کردن خطاهای املایی توسط ماشین از جمله مسائل مورد بحث در پردازش زبان های طبیعی است. پس از به وجود آمدن علوم رایانه ای و مسائل هوش مصنوعی ، پردازش زبان های طبیعی مورد توجه بسیار قرار گرفت. به طور کلی پردازش زبان‌های طبیعی،یکی از زیرشاخه‌های بااهمیت در حوزه گسترده هوش مصنوعی است. تلاش عمده در این زمینه ماشینی کردن فرایند درک و برداشت مفاهیم بیان گردیده با یک زبان طبیعی انسانی توسط ماشین است. با فراگیر شدن پدیده اینترنت و گسترش متون الکترونیکی این علم اهمّیت ویژه ای پیدا کرده است که از جمله نتایج آن می توان به استخراج اطلاعاتی خاص از یک متن، ترجمه یک متن به زبانی دیگر، یافتن مستنداتی خاص در یک پایگاه داده نوشتاری ، سیستم های پرسش و پاسخ انسان با کامپیوتر، سرویس های اتوماتیک ارتباط با مشتری از طریق تلفن و سیستم های کنترلی توسط صدا اشاره کرد. همچنین پیاده سازی انواع خطایاب های املایی ، مترجمین هوشمند ماشینی، نرم افزارهای پردازش و تشخیص گفتار و نرم افزارهای تبدیل متن به صدا از جمله تلاش ها در این زمینه بوده است.
در رابطه با خطایابی املایی ،مسئله ی تشخیص خودکار و تصحیح خطاهای املایی موجود در انواع متن از دهه ی ۶۰ میلادی مطرح بوده است و تا به امروز نیز پیدا کردن الگوریتم ها ی بهینه برای این کار مورد توجه بوده است و ﻣﺴﺌﻠﻪ ی اﺧﺘﺮاع اﻟﮕﻮرﻳﺘﻢ ﻫﺎ و روش ﻫﺎی تصحیح ﺧﻮدﻛﺎر ﻛﻠﻤﺎت در ﻣﺘﻦ ﺑﻪ ﻳﻚ ﭼﺎﻟﺶ ﺑﺎﻟﻘﻮه تحقیقاتی ﺗﺒﺪﻳﻞ ﺷﺪه اﺳﺖ چنانچه استفاده از سامانه‌های تشخیص لغات و تصحیح خودکار و هوشمند خطاهای املائی در دنیای امروز در بسیاری از کاربردها نظیر نرم‌افزارهای تولید اسناد متنی و همچنین کیبوردهای مجازی گوشی‌های هوشمند متداول شده است.برای مثال حدود 10 تا 12 ‏درصد پرس و جوهای وارد شده در موتورهای جستجو و بیش از 14% تمام پرس و جوهای ارسال شده برای بازیابی اطلاعات، ‏شامل عبارت هایی با غلط املایی است.پس امروزه با فراگیر شدن پدیده اینترنت ، گسترش متون الکترونیکی و استفاده از واسط های مبتنی بر پرس و جو، وجود ابزارهایی ‏کمکی جهت تسریع و تسهیل در غلط یابی و ارائه کلمه پیشنهادی مناسب، اجتناب ناپذیر گشته است.[1]
خطایاب های املایی در تصحیح و کمک به جستجوی سریع تر و دقیق تر در اینترنت، تصحیح خطاهای ناشی از تبدیل تصویر به متن،صرفه جویی در وقت و هزینه ، ابزارهای جانبی برای ویرایشگرهای متنی، ابزار پیش پردازنده در پردازش زبان های طبیعی ، واسط های بازیابی اطلاعات، تبدیل گفتار به متن و کامپیوترهای مبتنی بر قلم و … کاربرد های بسیاری دارند. همچنین امروزه حجم بسیار زیادی از اطلاعات و متون فارسـی توسـط رایانـه ها تولید میشوند. فرایند تولید و ورود اطلاعات، به ویژه متن، هیچ گاه عـاری از خطـا نبـوده و هزینه های بسیاری برای یافتن و برطرف ساختن این خطاها صرف میشود که این امر نیاز به خطایاب را بیشتر نمایان می کند.
ﺗﻔﺎوﺗﻲ ﺑﺎﻳﺪ بین ﻛﺎر تشخیص ﺧﻄﺎی اﻣﻼﻳﻲ و تصحیح آن ﻗﺎﺋﻞ ﺷﺪ .روش ﻫﺎی ﻛﺎراﻳﻲ ﺑﺮای تشخیص رﺷﺘﻪ ﻫﺎﻳﻲ ﻛﻪ در ﻳﻚ ﻟﻐﺖ ﻧﺎﻣﻪ وﺟﻮد ﻧﺪارﻧﺪ اﻳﺠﺎد ﺷﺪه اﺳﺖ .وﻟﻲ تصحیح رﺷﺘﻪ ی ﺷﺎﻣﻞ ﻏﻠﻂ اﻣﻼﻳﻲ ﻣﺴﺌﻠﻪ ی ﺑﻪ ﻣﺮاﺗﺐ ﺳﺨﺖ ﺗﺮی اﺳﺖ.[1]
کارهای زیادی جهت مدل کردن الگوی خطا و مشخص نمودن پارامترهای آن صورت گرفته است. تقسیم بندی های متفاوتی از ‏الگوی خطا، با توجه به منبع خطا وجود دارد. دسته بندیهای ارائه شده برای خطا ، به ساختار آوائی و نگارشی هر زبان بستگی ‏دارد.‏مثلا یک دسته بندی می تواند مبتنی بر شباهت در تلفظ، خطای تایپوگرافی و خطای فتونیکی باشد. خطای تایپوگرافی شامل ‏خطاهای ناشی از عادات کاربر و یا نزدیکی نوشتاری حروف است. خطاهای فتونیکی، از شباهت تلفظی حروف با نوشتار ‏متفاوت، ناشی می شود. الگوهای خطای بدست آمده صرفنظر از دسته بندی های اعمال شده، به عنوان یک راهنما جهت تشخیص ‏محل وقوع خطا و رفع آن عمل می نمایند. مشکل اساسی در این رابطه، وابستگی الگوی خطا به زبان و رسانه ای است که ‏سیستم در آن کار می کند.‏

بخش کارهای مرتبط
به طور کلی خطایابی املایی شامل بررسی یک متن ، مشخص کردن کلمه یا کلمات اشتباه و تصحیح آن ها می شود. بعضی از خطایاب های امروزی به جای ارائه یک تصحیح، لیستی از پیشنهادات را برای کاربر نمایش می دهند. بعضی از خطایاب های قدیمی تر فقط کلمه ی شامل غلط املایی را مشخص می کنند و پیشنهادی برای املای صحیح ارائه نمی کنند چراکه عمل تصحیح، به مراتب پیچیده تر و نیازمند پردازش بیشتری است.
خطایاب ها برای پیدا کردن خطاها از الگو های مشخصی استفاده میکنند به طوریکه دسته بندی های مختلفی برای انواع خطاها وجود دارد و می توان توسط مدل سازی های مختلف زبان ها آنها را شناسایی کرد، که جلوتر به آنها می پردازیم.

خطاهای املایی را می توان به دسته های مختلفی تقسیم بندی کرد.

به طور کلی دو دسته ی :

۱) خطاهای غیر لغت ( Non-word Errors )

۲) خطاهای لغات واقعی ( Real-word Errors )

غیر لغات ها همانطور که از نام آنها پیداست کلماتی هستند که معنایی ندارند و در فرهنگ لغات وجود ندارند. معمولا عمل تصحیح آنها با اضافه یا کم کردن و یا با تغییر یک یا چند حرف انجام می شود. برای مثال اگر کاربر کلمه ی (فقث) را وارد کرده باشد می توان حدس زد که کلمه ی درست (فقط) می باشد.

خطاهای لغات واقعی خود شامل خطاهای چاپی(Typographical errors) ، خطاهای شناختی (Cognitive errors) و خطاهای آوایی (Phonetic) می شوند. در خطاهای لغات واقعی ممکن است کلمه ی نوشته شده از نظر املایی درست باشد و در فرهنگ لغات هم موجود باشد اما کاربرد آن در متن نوشته شده اشتباه باشد.

در خطاهای چاپی فرض بر این است که کاربر املای درست را می داند اما به دلایلی خطا انجام می دهد (برای مثال دیو به جای دیر و یا اسلام به جای سلام). خطاهای چاپی شامل خطاهای ناشی ازعادات کاربر و یا نزدیکی نوشتاری حروف است.

در خطاهای شناختی کاربر تسلط کافی به زبان را ندارد و معنای کلمه ی درست با کلمه ی وارد شده متفاوت است (برای مثال غصه به جای قصه و یا توجیح به جای توجیه ).

خطاهای آوایی همانند خطاهای شناختی هستند با این تفاوت که کلمه ی خطا از لحاظ آوایی مشابه کلمه ی صحیح مورد نظر است (برای مثال اصلاح به جای اسلاح )
بیش ﺗﺮ روش ﻫﺎی ﺧﻄﺎﻳﺎﺑﻲ اﻣﻼﻳﻲ ﻣﻮﺟﻮد ﺑﺮ روی ﻛﻠﻤﺎت ﻣﻨﺰوی ﺗﻤﺮﻛﺰ دارﻧﺪ و اﻃﻼﻋﺎﺗﻲ را ﻛﻪ از ﻣﺘﻨﻲ ﻛﻪ رﺷﺘﻪ در آن ﻇﺎﻫﺮ ﺷﺪه اﺳﺖ ﻣﻲ ﺗﻮاﻧﺪ ﺑﻪ دﺳﺖ آورد را در ﻧﻈﺮ نمی گیرند. روش ﻫﺎﻳﻲ ﻗﺎدر ﺑﻪ تشخیص ﻗﺴﻤﺖ ﺑﺰرﮔﻲ از ﺧﻄﺎﻫﺎ از ﺟﻤﻠﻪ ﺧﻄﺎﻫﺎی ﭼﺎﭘﻲ، آواﻳﻲ و ﻧﺤﻮی ﻛﻪ ﻣﻨﺠﺮ ﺑﻪ تولید دﻳﮕﺮ ﻛﻠﻤﺎت ﻣﻮرد ﻗﺒﻮل ﻫﺴﺘﻨﺪ،نیستند.[1]
الگوی خطاهای اصلی :

در تحقیقاتی که در این زمینه انجام شده است مشخص شده که حدود ۸۰٪ از کل خطاهای املایی موجود در یک نوشتار شامل یکی از موارد زیر هستند :

۱)خطای درج اضافی حرف : اضافه شدن یک یا چند حرف به کلمه ی درست.

۲)خطای حذف حرف : پاک شدن یک یا چند حرف از کلمه ی درست.

۳)خطای جانشینی : استفاده از یک حرف به جای حرفی دیگر .

۴)خطای جابجایی : جابجایی دو حرف با هم.

۵)خطای فاصله : چسبیدن دو کلمه درست بدون فاصله به هم.

خطایاب ها با کمک این الگو های خطا و مدل سازی زبان ها ، می توانند به خطایابی بپردازند.

۱) تشخیص خطاهای غیر لغت :
دو روش اﺻﻠﻲ ﻛﻪ ﺑﺮای تشخیص ﺧﻄﺎی اﻣﻼﻳﻲ غیر لغت ﺑﻪ ﻛﺎر رﻓﺘﻪ اﻧﺪ، تحلیل ﭼﻨﺪ نگاشت و ﻣﺮاﺟﻌﻪ ﺑﻪ ﻟﻐت ﻧﺎﻣﻪ اﺳﺖ . ﭼﻨﺪﻧﮕﺎﺷﺖ ﻫﺎ زﻳﺮ دﻧﺒﺎﻟﻪ ﻫﺎی ﭼﻨﺪ ﺣﺮﻓﻲ از ﻛﻠﻤﺎت و رﺷﺘﻪ ﻫﺎ ﻫﺴﺘﻨﺪ ﻛﻪ ﭼﻨﺪ ﻣﻌﻤﻮﻻً ﻳﻚ، دو و ﻳﺎ ﺳﻪ اﺳﺖ .ﺑﻪ ﻃﻮر ﻛﻠﻲ تشخیص روش ﻫﺎی ﺧﻄﺎی ﻣﺒﺘﻨﻲ ﺑﺮ ﭼﻨﺪﻧﮕﺎﺷﺘﻲ ﺑﺎ اﻣﺘﺤﺎن در ﻣﺘﻦ ورودی و ﺑﻪ دﻧﺒﺎل آن در ﻳﻚ ﺟﺪول از پیش تولیدﻛﺮدن ﻫﺮ ﭼﻨﺪﻧﮕﺎﺷﺖ ﺷﺪه ﮔﺸﺘﻦ ﺑﺮای ﻣﺸﺨﺺ ﺷﺪن وﺟﻮد ﻳﺎ ﺗﻌﺪاد ﺗﻜﺮار آن، ﻛﺎر ﻣﻲ ﻛﻨﺪ .رﺷﺘﻪ ﻫﺎﻳﻲ ﻛﻪ دارای ﭼﻨﺪﻧﮕﺎﺷﺖ ﻫﺎی ﺑﺪون ﺗﻜﺮار ﻳﺎ ﺗﻜﺮار بسیار ﻛﻢ ﺑﺎﺷﻨﺪ ﻣﺜﻞ ﺳﻪ ﻧﮕﺎﺷﺖ ﭘﺨﺰ ﻳﺎ ﻓﻘﺚ (ﺑﻪ ﻋﻨﻮان ﺧﻄﺎﻫﺎی اﺣﺘﻤﺎﻟﻲ در ﻧﻈﺮ ﮔﺮﻓﺘﻪ ﻣﻲ ﺷﻮﻧﺪ .اﻳﻦ روش ﻫﺎ ﻣﻌﻤﻮﻻً ﺑﻪ ﻳﻚ ﻟﻐﺖ ﻧﺎﻣﻪ ﻳﺎ ﻳﻚ ﻣﺠﻤﻮﻋﻪ ی ﺑﺰرگ از ﻧﻮﺷﺘﺠﺎت ﺑﺮای تولید از پیش ﺟﺪول ﭼﻨﺪﻧﮕﺎﺷﺖ ﻫﺎ نیاز دارﻧﺪ .روش ﻫﺎی ﻣﺒﺘﻨﻲ ﺑﺮ ﻟﻐﺖ ﻧﺎﻣﻪ ﺑﻪ ﺳﺎدﮔﻲ ﻛﻠﻤﺎت ورودی را در ﻳﻚ ﻟﻐﺖ ﻧﺎﻣﻪ ﺟﺴﺘﺠﻮ ﻣﻲ ﻛﻨﻨﺪ .اﮔﺮ ﻛﻠﻤﻪ ی ورودی در ﻟﻐﺖ ﻧﺎﻣﻪ وﺟﻮد ﻧﺪاﺷﺖ ﺑﻪ ﻋﻨﻮان ﺧﻄﺎ ﻋﻼﻣﺖ ﮔﺬاری ﻣﻲ ﺷﻮد.
در ﻛﻞ ﺑﺎ اﻳﻨﻜﻪ تحلیل ﭼﻨد نگاشتی ممکن از برای خطاهای تولید شده ﺗﻮﺳﻂ ماشین، ﺑﺮای ﻣﺜﺎل تشخیص ﻧﻮری ﺣﺮوف مفید ﺑﺎﺷﺪ، وﻟﻲ ﺛﺎﺑﺖ ﺷﺪه اﺳﺖ ﺑﺮای ﺧﻄﺎﻫﺎی تولید ﺷﺪه ﺗﻮﺳﻂ اﻧﺴﺎن دﻗﺖ ﻛﻢ ﺗﺮی دارد .ﺑﻪ همین ﺧﺎﻃﺮ بیش ﺗﺮ روش ﻫﺎی تصحیح ﺧﻄﺎی اﻣﻼﻳﻲ ﺑﺮ اﺳﺎس ﻣﺮاﺟﻌﻪ ﺑﻪ ﻟﻐﺖ ﻧﺎﻣﻪ ﻫﺴﺘﻨﺪ .از آﻧﺠﺎﻳﻲ ﻛﻪ وﻗﺘﻲ ﻟﻐﺖ ﻧﺎﻣﻪ ﺑﺰرگ ﻣﻲ ﺷﻮد، ﺳﺮﻋﺖ ﭘﺎﺳﺦ ﮔﻮﻳﻲ ﻣﺴﺌﻠﻪ ی ﻣﻬﻤﻲ ﻣﻲ ﺷﻮد، روش ﻫﺎﻳﻲ ﻛﻪ از ﺟﺪول ﻫﺎی درﻫﻢ، درﺧﺖ ﻫﺎ و...اﺳﺘﻔﺎده ﻣﻲ ﻛﻨﻨﺪ ﺑﻪ وﺟﻮد آﻣﺪه اﻧﺪ.

استفاده از لغت نامه

ساده ترین و پراستفاده ترین روش برای تشخیص خطاهای غیر لغت ، استفاده از لغت نامه ها (Dictionaries) است. در این روش کلمات درست در یک لغت نامه ذخیره می شوند. سپس خطایاب تک تک کلمات وارد شده را در داخل لغت نامه جست و جو می کند و اگر همانند آن کلمه پیدا نشود ، خطایاب یک خطا را تشخیص داده است. بدین ترتیب هرچه لغت نامه بزرگتر باشد ، بهتر است. اما در این روش مسئله ی زمان پاسخگویی و همچنین فضای ذخیره شده نکات مهمی هستند. معمولا تعداد کلمات لغت نامه ها حدود ۲۵۰ هزار لغات یا بیشتر می باشد. با بزرگتر شدن لغت نامه زمان پاسخگویی سیستم بسیار بالا می رود. همچنین به فضای ذخیره سازی زیادی نیاز خواهیم داشت. برای حل این مشکل روش های مختلفی مثل مراجعه به لغت نامه های کارا، تقسیم لغت نامه ها و روش های مبتنی بر پردازش ریخت شناسی وجود دارند.
در ﻣﺮاﺟﻌﻪ ﺑﻪ ﻟﻐﺖ ﻧﺎﻣﻪ ﻣﺴﺌﻠﻪ زﻣﺎن ﭘﺎﺳﺦ ﮔﻮﻳﻲ اﺳﺖ .ﻣﻌﻤﻮﻻً اﻧﺪازه ی ﻟﻐﺖ نامه ها بین 25 هزار تا 250 هزار لغت است وبرای این اندازه لغت نامه ها زﻣﺎن ﭘﺎﺳﺦ ﮔﻮﻳﻲ بسیار ﺑﺎﻻ ﻣﻲ رود .اﻳﻦ ﻣﺸﻜﻞ از ﺳﻪ روش ﻣﺮاﺟﻌﻪ ﺑﻪ ﻟﻐﺖ ﻧﺎﻣﻪ ی ﻛﺎرا، تقسیم ﻟﻐﺖ ﻧﺎﻣﻪ و روش های ﻣﺒﺘﻨﻲ ﺑﺮ ﭘﺮدازش رﻳﺨﺖ ﺷﻨﺎﺳﻲ ﺳﻌﻲ ﺷﺪه اﺳﺖ ﻛﻪ ﺣﻞ ﺷﻮد.
ﭘﺮ اﺳﺘﻔﺎده ﺗﺮﻳﻦ روش ﺑﺮای دﺳﺘﺮﺳﻲ ﺳﺮﻳﻊ ﺑﻪ ﻟﻐﺖ ﻧﺎﻣﻪ ﻫﺎ اﺳﺘﻔﺎده از ﺟﺪول های درهم است .برای امتحان کردن یک رشته ی ورودی، آدرس درﻫﻢ آن ﻣﺤﺎﺳﺒﻪ ﻣﻲ ﺷﻮد و ﺑﺎ ﻣﺮاﺟﻌﻪ ﺑﻪ ﺟﺪول درﻫﻢ از پیش ﺳﺎﺧﺘﻪ ﺷﺪه و درﻳﺎﻓﺖ ﻛﻠﻤﻪ ی ذﺧﻴﺮه ﺷﺪه در آن ﻣﻜﺎن اﮔﺮ ﻛﻠﻤﺎت ﻳﻜﻲ ﻧﺒﻮدﻧﺪ ﻳﺎ ﻛﻠﻤﻪ ای وﺟﻮد ﻧﺪاﺷﺖ، ﻏﻠﻂ اﻣﻼﻳﻲ تشخیص داده ﻣﻲ ﺷﻮد.[4]
ﺣﺴﻦ اﺻﻠﻲ اﺳﺘﻔﺎده از ﺟﺪول ﻫﺎی درﻫﻢ ﻋﺪم نیاز ﺑﻪ ﻣﻘﺎﻳﺴﻪ زﻳﺎد ﺑﻪ ﺧﺎﻃﺮ خاصیت دﺳﺘﺮﺳﻲ مستقیم اﺳﺖ و ﻣﺸﻜﻞ ﺑﺰرگ آن پیدا ﻛﺮدن ﺗﺎﺑﻊ درﻫﻤﻲ ﻣﻨﺎﺳﺐ ﺑﺮای تولید ﺟﺪول درﻫﻢ ﺑﻪ ﮔﻮﻧﻪ ای ﻛﻪ ﺗﻜﺮاری تولید ﻧﻜﻨﺪ و ﺳﺮﻳﻊ ﺑﺎﺷﺪ اﺳﺖ .اﻟﺒﺘﻪ روش ﻫﺎﻳﻲ ﺑﺮای تولید چنین ﺗﻮاﺑﻌﻲ توضیح داده ﺷﺪه اﺳﺖ.[5]
ﺑﺮﻧﺎﻣﻪ spellمربوط به سیستم عامل Unix از جمله برنامه هایی است ﻛﻪ از ﻳﻚ ﺟﺪول درﻫﻢ ﺑﺮای ﻣﺮاﺟﻌﻪ ی ﺳﺮﻳﻊ ﺑﻪ ﻟﻐﺖ ﻧﺎﻣﻪ اﺳﺘﻔﺎده ﻣﻲ کند.[6]

بهینه سازی روش لغت نامه

برای مثال یک روش این است که فقط ریشه ی کلمات را ذخیره کنیم (ریشه یابی). در این روش توسط الگوریتم ها و مجموعه قوانین خاص هر زبان پیشوند ها و پسوند های کلمات را حذف می کنیم. به هنگام جست و جوی خطا نیز همین کار را بر روی کلماتی که کاربر وارد کرده انجام می دهیم وریشه های ایجاد شده را با ریشه های ذخیره شده در لغت نامه مقایسه می کنیم. بدین ترتیب فضای اشغال شده توسط لغت نامه کمتر شده و زمان پاسخ گویی نیز بسیار سریعتر می شود. مشکل این روش این است که ممکن است بعضی خطاها نادیده گرفته شوند چراکه امکان دارد کلمه ی وارد شده توسط کاربر ریشه ی درستی داشته باشد ولی به همراه پسوند یا پیشوند وارد شده ، حاوی غلط املایی باشد.

روش دیگر استفاده از تابع درهم (Hash Function) در ذخیره سازی است. در این روش برای هر کلمه ی لغت نامه یک آدرس درهم در نظر می گیریم. این آدرس با اعمال تابع درهم بر روی هر یک از حروف الفبا به دست می آید. برای مثال به حرف الف عدد ۱، ب عدد ۲ پ عدد ۳ و به همین ترتیب به تمام حروف یک عدد را نسبت می دهیم. سپس با استفاده از تابع درهم یعنی اعمال محاسبات ریاضی بر روی اعداد حروف هر کلمه ، به یک عدد برای هر کلمه می رسیم. بدین ترتیب به جای ذخیره ی هر کلمه ، این عدد را در حافظه ذخیره می کنیم. هنگامی که کاربر یک رشته ی ورودی را وارد می کند، آدرس درهم آن محاسبه می شود و با مراجعه به جدول درهم از پیش ساخته شده و دریافت کلمه ی ذخیره شده در آن مکان اگر کلمات یکی نبودند یا کلمه ای وجود نداشت، غلط املایی تشخیص داده می شود. این روش در واقع نگاشت بیت به بیت (BitMap) می باشد.
بدین ترتیب سرعت دسترسی به اطلاعات و زمان پاسخگویی بسیار سریعتر می شود. به دلیل خاصیت دسترسی مستقیم نیازی به مقایسه های زیادی نیست. همچنین فضای ذخیره سازی نیز کاهش می یابد. مهمترین چالش در این روش داشتن تابع درهم مناسب است چراکه هر کلمه لازم است که آدرس منحصر به فردی داشته باشد. پیدا کردن تابع درهمی مناسب برای تولید این جدول درهم به گونه ای که کلمات تکراری تولید نکند و همچنین سریع بودن تابع مشکل اصلی این روش است. البته روش های مختلفی برای تولید چنین توابعی وجود دارد.

استفاده از تحلیل چند نگاشت (N-grams)

ﺧﻄﺎﻫﺎﻳﻲ ﻛﻪ ﺗﻮﺳﻂ دﺳتگاه ﻫﺎی ﻧﻮری ﺣﺮوف معمولا انهایی هستند که ﺣﺮوف شبیه ﺑﻪ ﻫﻢ را ﺑﺎ ﻫﻢ اﺷﺘﺒﺎه ﻣﻲ ﻛﻨﻨﺪ، ﻣﺜﻞ اﻟﻒ و ﻻم ﻳﺎ 1والف.روش های مبتنی برتحلیل ﭼﻨﺪﻧﮕﺎﺷﺖ ﺑﺮای تشخیص اﻳﻦ ﺧﻄﺎﻫﺎ ﺧﻮب ﻋﻤﻞ میﻛﻨﻨﺪ.
ﺟﺪولﻫﺎی ﭼﻨﺪﻧﮕﺎﺷﺖ ﻣﻲ ﺗﻮاﻧﻨﺪ ﺑﻪ ﺷﻜﻞ ﻫﺎی ﻣﺘﻔﺎوﺗﻲ تولید ﺷﻮﻧﺪ .ﺳﺎده ﺗﺮﻳﻦ آن ﻫﺎ ﻳﻚ دوﻧﮕﺎﺷﺖ دودوﻳﻲ اﺳﺖ ﻛﻪ ﻳﻚ آراﻳﻪ ی دو بعدی 32 ×32است که تمام ترکیب های دوﺗﺎﻳﻲ ﺣﺮوف را در ﺑﺮ میگیرد .ﻫﺮ ﺧﺎﻧﻪ آن شامل 1 اﮔﺮ آن دوﻧﮕﺎﺷﺖ در ﻣﺘﻦ ﻣﺎ ﺣﺪاﻗﻞ یکبارتکرارشده باشد یا 0است.ﻳﻚ ﺳﻪ ﻧﮕﺎﺷﺖ دودوﻳﻲ ﺑﻪ ﻫﻤﻴﻦ ﺷﻜﻞ و ﻳﻚ آراﻳﻪ سه بعدی است.ﻫﺮ دو آراﻳﻪ ﻫﺎی ﺑﺎﻻ را ﭼﻨﺪﻧﮕﺎﺷﺖ ﻫﺎی دودوﻳﻲ غیر واﺑﺴﺘﻪ ﺑﻪ موقعیت ﻣﻲﻧﺎﻣﻨﺪ .ﺑﺪﻳﻦ ﻣﻌﻨﺎ ﻛﻪ ﻣﺤﻞ ﭼﻨﺪﻧﮕﺎﺷﺖ را در ﻛﻠﻤﻪ ﻣﺸﺨﺺ ﻧﻤﻲ ﻛﻨﻨﺪ.
در اختصاص ﻓﻀﺎی بیش ﺗﺮ ﺑﻪ ﺟﺪول ﭼﻨﺪ ﻧﮕﺎﺷﺖ ﻣﻲ ﺗﻮان موقعیت ﭼﻨﺪ ﻧﮕﺎﺷﺖ را ﻫﻢ ذخیره ﻛﺮد.در آزﻣﺎﻳﺸﺎت ﻣﺸﺨﺺ ﺷﺪه اﺳﺖ ﻛﻪ ﭼﻨﺪﻧﮕﺎﺷﺖ ﻫﺎی واﺑﺴﺘﻪ ﺑﻪ ﻣﻮﻗﻌﻴﺖ ﺑﻬﺘﺮ ﻋﻤﻞ ﻣﻲ کنند.[2-3]

روش دیگر برای تشخیص خطاهای غیر لغت استفاده از تحلیل چند نگاشت است. چندنگاشت ها زیر دنباله های چند حرفی از رشته های کاراکتری هستند. برای مثال یک، دو، و یا سه حرفی. برای مثال، زیر نگاشت ۳ حرفی کلمه ی “آفتاب” شامل ‘آفت’ ، ‘فتا’ و ‘تاب’ ، می شود. دو روش کلی برای تحلیل چند نگاشت وجود دارد.

در یکی از این روش ها به طور غیر مستقیم از لغت نامه استفاده می کنیم بدین ترتیب که برای مثال ابتدا سه نگاشت های تمام کلمات لغت نامه را ذخیره می کنیم. حال هنگامی که کاربر رشته ای را وارد می کند چند نگاشت های آن نیز به همان روش قبلی ساخته می شوند و با چند نگاشت های لغت نامه مقایسه می شوند. عدم وجود آن ها در چند نگاشت های لغت نامه، مشخص کننده ی خطاهای احتمالی است.در این روش معمولاً به یک لغت نامه برای نگه داری از پیش جدول چندنگاشت ها نیازاست. در روش های مبتنی بر تحلیل چندنگاشت ممکن است تعداد قابل توجهی از خطاها تشخیص داده نشوند چراکه بسیاری از کلمات حاوی خطا، شامل چند نگاشت های غیرمعمول نمی شوند اما در تشخیص خطاهایی که توسط دستگاههای تشخیص نوری حروف (Optical Character Recognition) خطایابی می شوند ، خوب عمل می کنند.

در روش دیگر برای تحلیل چند نگاشت ها از لغت نامه استفاده نمی شود. همانند روش قبل ابتدا چند نگاشت های متن ورودی توسط کاربر مشخص می شوند اما این بار تعداد تکرار آن ها در متن اهمیت دارد. برای مثال سه نگاشت “پخز” که فقط یکبار در متن تکرار شده باشد،احتمال خطا بودن آن زیاد است. اما “هست” که بسیار بیشتر استفاده شده است احتمال خطا بودن آن ناچیز است. همانند روش قبل احتمال تشخیص ندادن خطا های عادی وجود دارد اما این روش در تشخیص خطاهای تایپی بسیار کارا عمل می کند.همچنین مزیت دیگر آن این است که برای هر زبانی می توان از این روش استفاده کرد.

جدول های چند نگاشت می توانند با روش های مختلفی ساخته شوند. ساده ترین روش استفاده از دونگاشت دودویی است که یک آرایه ی دو بعدی است که تمام ترکیبهای دوتایی حروف را در بر می گیرد. هر خانه ی آن شامل ۱ اگر آن دونگاشت در متن ما حداقل یکبار تکرار شده باشد یا ۰ است. یک سه نگاشت دودویی به همین شکل ولی یک آرایه ی سه بعدی است.

این آرایه ها را چند نگاشت های دودویی غیر وابسته به موقعیت می نامند. بدین معنا که محل چندنگاشت را در کلمه مشخص نمی کنند.

با اختصاص فضای بیشتر به جدول چند نگاشت می توان موقعیت چندنگاشت را هم ذخیره کرد. این کار باعث بهبود کارایی روش های چند نگاشت ها می شود چراکه می توان محل آن ها در کلمه را نیز مقایسه کرد.

به طور کلی تحلیل چند نگاشتی در بعضی زمینه ها مثل تشخیص نوری حروف و خطاهای تایپی مفید است، ولی برای خطاهای تولید شده توسط انسان دقت کمتری دارد. به همین خاطر بیشتر روش های تصحیح خطای املایی بر اساس مراجعه به لغتنامه می باشند.

خطای حرف اول

عموما خطا در حرف اول کلمات رخ نمی دهد. بدین ترتیب می توانیم لغتنامه ها را بر اساس حرف اول تقسیم بندی کنیم تا زمان مراجعه به لغت نامه و زمان پاسخ گویی کاهش یابند.مشکل این دسته بندی این است که در این صورت دسته ای از خطاها(خطاهای حرف اول) توسط سیستم ما تشخیص داده نمی شود.

طول کلمه

طبق تحقیقات انجام شده، در بسیاری از مواقع طول کلمه ی خطا در فاصله ی دوتایی از طول کلمه ی صحیح است. این موضوع باعث می شد محققان لغتنامه ها را بر اساس طول کلمات به چند دسته تقسیم کنند تا زمان جستجو کاهش یابد.
با توجه به قانون زیپف در یک نوشته کلمات کوتاه تر تعداد تکرارهای بیشتری دارند. همچنین کلمات با تکرار بیشتر همسایه های تک خطایی بیشتری دارند. ولی معمولاً کلمات کوتاه کمتر اشتباه نوشته می شوند. در ضمن هرچه کلمه کوتاه تر باشد متن درون کلمه ای کمتری در اختیار ما قرار می دهد و کار تصحیح سخت تر می شود.

۲) تشخیص خطای لغات واقعی :

از جمله ایرادات خطایاب ها می توان به تشخیص دادن کلمه ی درست به عنوان خطا و یا تشخیص ندادن بعضی خطاها اشاره کرد. دلیل ایراد نوع اول ، وجود کلمات مبهم و اسم های خاص در متن وارد شده می باشد. می توان با فراهم کردن لغت نامه ی بزرگتر برای خطایاب و یا استفاده از لغت نامه ی تخصصی برای انواع مختلف متن (برای مثال پزشکی) درصد این ایراد را کاهش داد. اما برای ایراد دوم راه حل خاصی وجود ندارد چراکه تعداد اسم های خاص بسیار زیاد است. بسیاری از خطایاب ها امکانی را فراهم می کنند که کاربر اسم خاص را برای خطایاب مشخص کند تا بعد از اولین باری که خطا در نظر گرفته می شود خطایاب دوباره آن را خطا اعلام نکند.

ایراد نوع دوم در مقابل ایراد اول یعنی تشخیص اشتباه بسیار مهم تر است چراکه کاربر همواره می تواند خطا را نادیده بگیرد ، اما تشخیص ندادن کلمه ی خطا نگران کننده است چراکه کاربر انتظار متنی بدون خطا را دارد.

این مشکل با افزایش سایز لغت نامه برای کاهش ریسک ایراد نوع اول ، بیشتر نیز می شود چراکه با افزایش لغات مبهم لغت نامه امکان تشخیص ندادن خطاهای لغات واقعی بیشترمی شود.

خطایاب های کمی هستند که می توانند خطای لغات واقعی را تشخیص دهند. ۳ پروژه در این زمینه قابل ذکر هستند.

اولی سیستمی با نام CRITIQUE است که توسط IBM ساخته شده است. در این برنامه متن از لحاظ نوشتاری ، دستور زبان و قالب نوشتاری ، بررسی می شود.سیستم توسط گرامری که برای آن طراحی شده است ، متن را بررسی می کند و نقش کلمات شامل اسم ، قید ، افعال اصلی و کمکی و غیره را مشخص می کند. اگر جمله ای با قواعد گرامر تعریف شده همخوانی نداشته باشد ، آن قاعده کنار گذاشته می شود و دوباره جمله بررسی می شود. این کار تا زمانی ادامه پیدا می کند که جمله مورد قبول واقع شود. حال سیستم با دانستن قواعد کنار گذاشته شده ، می تواند تشخیص دهد چه قسمتی از دستور زبان مشکل داشته است.

پروژه ی دوم نیز همانند سیستم اولی بر پایه قواعد نحوی است. در ابتدا این پروژه در دانشگاه لنکستر فقط برای مشخص کردن نقش کلمات در جمله بود اما بعدها به خطایاب املایی تبدیل شد. سیستم ابتدا با مراجعه به یک لغت نامه نقش کلمات را مشخص می کند. لغت نامه بر اساس نقش کلمات مرتب شده است (برای مثال لغت نامه ای برای افعال). همچنین سیستم حاوی جدولی است که جایگاه و ترتیب قرار گرفتن نقش های مختلف در جمله را مشخص می کند. وقتی کاربر متنی را وارد می کند سیستم ترتیب قرار گرفتن کلمات با نقش های دستوری مختلف را بررسی می کند و دنباله ای که احتمال درست بودن آن کم است را ، مشخص می کند. بدین ترتیب سیستم حدس هایی رو برای پیشنهاد کلمه ی درست ارایه می دهد.

پروژه ی بعدی مدل پیشرفته تر سیستم قبلی بود که باز هم توسط IMB انجام شد. در این سیستم احتمال قرار گرفتن ۲ کلمه در کنار هم (و یا احتمال های دنباله ی ۳ تایی کلمات) محاسبه می شوند. سپس عمل تشخیص و تصحیح با توجه به این احتمالات انجام می شوند.

تصحیح خطا

برای تصحیح ، خطایاب باید کلمه ی مورد نظر کاربر را حدس بزند و همچنین قادر به نوشتن املا صحیح آن باشد. تولید املا درست سخت نیست چراکه همانطور که توضیح داده شد روش ها ی مختلفی برای ذخیره ی املا ی درست (از جمله ذخیره به صورت لغت نامه) وجود دارد. اما قسمت سخت تر ارایه ی پیشنهاد مناسب است.
به طور کلی کامپیوتر در تصحیح کلمات کوتاه تر کار سخت تری دارد تا کلمات بلند چراکه انتخاب ها برای کلمات کوتاه تر بسیار بیشتر است.
به دلیل حجیم بودن لغت نامه ها خطایاب برای عمل تصحیح باید قادر باشد فقط بخشی از لغت نامه که احتمال وجود کلمه ی درست در آن بیشتر است را ، ابتدا بررسی کند. این کار با توجه به توضیحی که در قسمت خطای حرف اول دادیم و در نظر گرفتن اینکه اکثر خطاها یکی از انواع الگوی خطاهای اصلی هستند ، انجام می شود. یعنی بیشتر خطاها از نوع خطای درج اضافی حرف ، خطای حذف حرف ، خطای جانشینی و یا خطای جابجایی هستند که معمولا با تغییر فقط یک حرف ، می توانیم به کلمه ی درست برسیم . همچنین حرف اول عموما صحیح است و بدین ترتیب لغت نامه بر اساس آن می تواند محدوده ی جست و جوی خود را مشخص کند و کلماتی که به فاصله ی یک یا چند حرف از کلمه ی ورودی هستند را بررسی کند. طبق تحقیقات انجام شده ۸۰٪ از خطاها به فاصله ی یک حرف از کلمه ی درست هستند. فاصله در این مبحث به تعداد عملیات های تصحیح مورد نیاز گفته میشود.
برای تصحیح این خطاها می توان از الگوریتم ‘کمترین فاصله ی تصحیح’ استفاده کرد. در این الگوریتم برای رسیدن به کلمه ی درست می توان از درج یک حرف ، حذف حرف و جا به جایی استفاده کرد . هر کدام از این اعمال را می توان چند بار انجام داد تا کلمه ی درست تولید شود.

Soundex

ساخت کد soundex :

۱) حرف اول به صورت بزرگ نگه داشته می شود

۲) حروف a,e,i,o,u,y,h,w با خط فاصله جایگزین می شوند

۳) دسته بندی حروف دیگر:

b,f,p,v : 1
c,g,j,k,q,s,x,z :2
d,t : 3
l :4
m,n :5
r :6

۴) اعداد کنار هم مشابه حذف می شوند

۵) خط فاصله ها حذف می شوند

۶) حرف اول به صورت بزرگ به همراه ۳ عدد اول نگه داشته می شوند.( اگر کمتر از ۳ عدد ساخته شده بود ، ۰ اضافه می کنیم )
برای مثال : (car(C600) ، toy(T00) ، bicycle(B224

SPEEDCOP

سیستم speedcop برای خطایابی سریع و خصوصا خطاهای تایپوگرافی به صورت خودکار ساخته شد. یک کلید برای هر کلمه ی لغت نامه ساخته می شود. حرف اول نگه داشته می شود ، سپس حروف بی صدای کلمه به ترتیب بعد از آن قرار می گیرند. حروف یکسان فقط یکبار نوشته می شوند. سپس حروف صدادار به ترتیب بعد از آنها قرار می گیرند. برای مثال کلمه ی xenon به XNEO تبدیل می شود. وقتی سیستم خطایی را تشخیص می دهد ، کد آن را می سازد و درلغت نامه جست و جو می کند تا آن را پیدا کند. سپس برای عمل تصحیح کلمات مشابه با این کد را بررسی می کند.

روش های Soundex و SPEEDCOP برای مشخص کردن قسمت خاصی از لغت نامه و بررسی کاندید ها در آن قسمت ، به کار می روند چون همانطور که گفتیم جست و جوی کل لغت نامه هزینه ی بسیاری دارد.

چالش پیش رو در این روش این است که اگر کلمه ی درست در محدوده ی مشخص شده ی لغت نامه نباشد ، خطایاب قادر به پیدا کردن آن نخواهد بود.

انتخاب کاندیدهای پیشنهادی

مرحله ی بعدی برای خطایاب انتخاب لیستی از کلمات درست ( لیست کاندید ها ) و سپس ارایه ی بهترین انتخاب است.
برای خطاهای تایپی این کار سخت نیست چراکه بسیاری از آن ها از نوع ۴ نوع اصلی هستند. خطایاب کلمات مشابه را بررسی می کند و اگر در یکی از این ۴ نوع با کلمه ی ورودی تفاوت داشته باشند به لیست کاندید ها اضافه می شوند.
روش دیگر محاسبه ی ارزش شباهت برای هر کلمه ی نزدیک به کلمه ی خطا است. سپس کلمات با ارزش بیشتر به لیست اضافه می شوند. به این عمل ‘تطبیق رشته (String-Matching)’ می گویند. روش های مختلفی برای این کار وجود دارد. برای مثال در نظر گرفتن تعداد حروف در زیردنباله های مشابه از حروف در دو کلمه. مثلا کلمهات medsin و medicine در زیردنباله های med و in ، ۵ حرف مشابه دارند یعنی ۶۳٪ تشابه .
همچنین می توانیم چند نگاشت های کلمات را مقایسه کنیم. هر دو کلمه ای که چند نگاشت های مشابه بیشتری داشته باشند ، بیشتر به هم شباهت دارند ( برای مثال می توان سه نگاشت ها را در نظر گرفت ).
در بعضی روش ها به بعضی حروف ارزش بیشتری داده می شود. برای مثال حروف نزدیک به ابتدا و یه حروف بی صدا ارزش بیشتری می گیرند.

روش آماری

دیگر روش هایی که خطایاب ها برای امتیازدهی و تصحیح استفاده می کنند ، روش های آماری هستند که بر اساس احتمال کار می کنند. در این روش ها جدولی وجود دارد که احتمال خطا های مختلف را ذخیره می کند. سپس پس از تولید لیست کاندید ها توسط خطایاب برای امتیازدهی و رتبه بندی از فرمول زیر استفاده می کنیم:

P(X|Y)\quad =\quad \frac { P(Y|X)\quad *\quad P(X) }{ P(Y) }

در این فرمول X یکی از نامزدها و Y کلمه ی خطای مشاهده شده است. (P(X|Y احتمال مناسب بودن کاندید X است. (P(Y|X احتمال خطا بودن Y برای کلمه ی درست X است. (P(X احتمال وقوع X است.
برای تمام کلمات کاندید احتمال را محاسبه می کنیم و سپس بر اساس آن ها رتبه بندی را انجام می دهیم.

شباهت آوایی :

بعضی خطایاب ها بر اساس شباهت تلفظ ، کلمات مشابه را ارزشگذاری می کنند به این معنی که عمل مقایسه بر روی تلفظ انجام می شه نه املای کلمات. برای مثال کلمه ی خطای indissceat به صورت /IndIski:t/ تلفظ می شود. خطایاب این تلفظ را به صورت سه تایی جدا می کند. برای کلمات لغت نامه نیز همین کار انجام شده. بدین ترتیب با مقایسه ی این حروف سه تایی عمل ارزشگذاری انجام می شود. هرچه تعداد شباهت ها بیشتر باشد ، کلمه ارزش بیشتری پیدا می کند.

indissceat #In Ind ndI dIs Isk ski: ki:t i:t#

indiscreet #In Ind ndI dIs Isk skr kri: ri:t i:t#

در مثال بالا ۶ شباهت را مشاهده می کنیم که می تواند حدس بسیار مناسبی برای تصحیح باشد.

آزمایش ها

مدل هایn-gram برای خطایابی املایی[8]

برای استفاده از مدل زبان برای خطایابی املایی از مجموعه کد و داده های Dan Jurafsky و Chris Manning استفاده میکنیم. Dan Jurafsky و Chris Manning کد وداده هایی را در دوره‌ی آنلاین خود برای NLP ارائه داده‌اند.کد های ارایه شده برپایه ی Peter Norvig در مورد خطایابی املایی می‌باشد که این یک روش مفید وسازنده در استفاده از مدل های زبان می باشد.در این روش اشاره شده به مدل زبان تا یک خطایاب املایی بتوان درست کرد پس برای ساخت خطایاب املایی مدل‌های زبانی مختلفی را از نظر دقت و کارایی بررسی خواهیم کرد.به ویژه اینکه پیاده سازی بخشی از مدل noisy channel برای خطایاب املایی را در نظر خواهیم گرفت.در زمان تست کردن میتوان یک جمله با دقیقا یک خطای تایپی را در نظر بگیرید.سپس خواهیم توانست ان را select کرده وسپس انرا با توجه به بیشترین احتمال اصلاح کرده.این به وسیله ی مدل noisy channel امکان پذیر است.در اخر مدل زبان سنجیده خواهد شد به وسیله ی درستی وصحت تعدادی از درستی یابی های صحیح وvalid که تقسیم شده به وسیله ی تعدادجملات تست شده.یعنی به هر یک از مجموعه ا‌ی از حروف ،احتمالی خاص را اختصاص می‌دهیم. مدل زبان این کار را انجام می دهد. میزان دقت برابر است با تعداد تصحیح های درست به تعداد کل جملات.ابتدا کلمات غلط را یافته سپس این احتمالات را که احتمالات درستی یک لغت به جای کلمه ی غلط است بررسی میکنیم واحتمال هر کلمه را به جای کلمه ی غلط در نظر می گیریم.در نهایت آن کلمه ای که احتمال درستی آن از همه ی کلمات دیگر بیشتر باشد را انتخاب کرده وجایگزین کلمه ی غلط میکنیم.حساب کردن این مدل از احتمالات به روش های مختلفی وابسته است که مدل های مختلف زبان به وجود می آورد.در این روش های مختلف زبان میزان دقت های متفاوتی مورد بحث است.
نوشته های دانش آموزان دوره ی راهنمایی به عنوان داده مورد استفاده قرار می گیرند که به وسیله ی David Holbrook جمع شده است.داده های ما درdata/directory قرار دارند.به آن جا مراجعه شود.خلاصه ای از داده مورد استفاده شامل موارد زیر است.
۱) holbrook-tagged-train.dat :‌ مجموعه ای از نوشته جات تا ساخت مدل زبان را بتوان انجام داد.
۲) holbrook-tagged-dev.dat : مجموعه ای از نوشته ها شامل خطاهای املایی برای توسعه دهندگان.
۳) count_1edit.txt : یک جدول که تعداد تغییرات و ویرایش لغات وادیت را بر عهده دارد.پیاده سازی سه مدل زبانی را انجام میدهیم.
۱) Laplace Unigram Language Model :‌ مدل نگاشت تکی ( یک نگاشت) همراه با یک هموارسازی.(one smooth)
منظور از هموارسازی این است که به کلماتی که در داخل متن مورد استفاده برای مدل‌کردن نیستند .(zero items in training)احتمال کمی بدهیم.
۲) Laplace Bigram Language Model : مدل نگاشت دوتایی ( دو نگاشت) همراه با یک هموارسازی. (one smooth)

۳) Stupid Backoff Language Model : ترکیبی از مدل اول بدون هموارسازی و مدل دوم همراه با هموارسازی.
برای پیاده سازی یک مدل زبانی دو تابع وجود دارد.
۱) train(HolbrookCorpus corpus) : با توجه به مجموعه‌ای از نوشته جات مدل زبانی را تشکیل می دهد. محاسبه‌ی تعداد کلمات ، جملات و احتمالات در این تابع انجام می شود.مثال UniformLanguageModel برای اینکه چگونه به یک جمله در نوشتجات وکلمات داخل آن جملات دسترسی میتوان یافت است.
۲) (score(List words :یک لیستی ازstring ها به عنوان argument ها را میگیردونتیجه ی شمارشی را برمیگرداند که log احتمال جمله ای را که از زبان مدل استفاده میکند را نشان می دهد.در واقع تابعی است برای اینکه میزان موفقیت ومیزان ددقت مدل زبانی خود را متوجه شویم تا بتوان به درستی ان را ارزیابی کرد.ارزیابی عملکرد هرکدام از مدل های زبان،به رابطه ونسبت عملکردی از راه حل پیاده سازی ما برمیگردد.موارد زیر انتظارات ما از عملکرد هر مدل زبانی را نشان می دهد.برای مثال=
Laplace Unigram Language Model: 0.11
Laplace Bigram Language Model: 0.13
Stupid Backoff Language Model: 0.18
کلاس SpellCorrect.py :‌ بهترین تصحیح را با درنظر گرفتن مدل زبانی داده شده محاسبه واصلاح میکند دو واقع تشخیص می دهد که بهترین انتخاب چیست وکلمه ای که دچار خطا شده است را درست میکند.فانکشن main() تمام مدل های زبانی خود را در خود لود میکند وعملکرد را در پیاده سازی داده ها print میکند و بسیار این مفید است برای debugging.
کلاس EditModel.py :‌ فایل count_1edit.txt رامیخواندومحاسبه ی احتمال درستی را میکند که کاندیدای درست کردن همگی در edit distance یک در نظر گرفته میشوند واحتمال درست نکردن 0.9 است.(p(x|x)=0.9) پس بعد از محاسبه ی احتمال نتیجه ی خود را به کلاس SpellCorrect.py میدهد تا از ان استفاده کند وغلط را تشخیص داده و درست کند.
کلاس HolbrookCorpus.py:مجموعه ای از نوشتجات را میخواند وtest case ای از غلط املایی را تولید میکند.
Sentence.py :داده ها را اعم از درست وغلط برای جمله داده شده نگه داری میکند که برای تولید جمله درست وجمله ای که خطای املایی دارد،توابع کمکی دارد.
Datum.py : لیستی شامل دو رشته ی word و error می‌باشد.word کلمه‌ی تصحیح شده و error خطای املایی است. برای کلمات درست رشته‌ی error تهی است.
پیوند

برای ساخت غلط گیراملایی،میتوان از spellchecker استفاده کرد که این کتابخانه توانایی افزودن یک واژه به واژه نامه درمواردی که واژه‌ی مورد پردازش با این که واژه‌ای صحیح است، در واژه‌نامه‌ی خطایاب وجود ندارد و از این رو یک خطای املایی تشخیص داده می‌شود،را دارا است.که در این موارد راه حل پیشنهادی این است که میتوان واژه ی مورد نظر را به واژه نامه ی خطایاب افزود وپس از یک واژه ی درست در نظر گرفته خواهد شد وهم چنین این کتابخانه توانایی خطایابی املایی در صورت نیاز را دارد که در آن کلمات و ریشه‌ها و مقادیر فاصله ویرایشی و تعداد پیشنهادها برای خطای املایی مشخص می‌شود. وهم چنین این کتابخانه توانایی پیش پردازش برای خطاهای رایج املایی را دارد که این اشکالات شامل فاصله‌گذاری ناصحیح در «می» (مانند «میروم» و «می روم» که باید به «می‌روم» اصلاح شوند)، فاصله‌گذاری ناصحیح در نشانه‌ی جمع ها (مانند «کتابها» و «کتاب ها» که باید به «کتاب‌ها» اصلاح شوند)، اتصال «بـ» (مانند «بعنوان» که صحیح آن «به عنوان» است) و اصلاح «یای بدل از کسره» (مانند «خانهٔ» که می‌تواند به «خانه‌ی» اصلاح شود) در ترکیب‌های اضافی است.برای پیاده سازی اضافه کردن یک واژه به دیکشنری از کلاس PersianSpellChecker استفاده میشود که با استفاده از متد AddToDictionary واژه‌ی مورد نظر را به دیکشنری میتوان اضافه کرد. از متد ContainWord نیز می‌توان برای کنترل موجود بودن یک واژه در دیکشنری استفاده کرد.برای خطایابی املایی هم از کلاس PersianSpellChecker استفاده شده است. این کلاس نیاز به مقدار دهی اولیه از طریق شیء از کلاس SpellCheckerConfig دارد. عمل خطا یابی توسط تابع CheckSpelling انجام می‌شود که کلمه‌ی مورد خطایابی را به همراه کلمات قبل و بعد آن به عنوان پارامتر دریافت می‌کند.قوانین پیش پردازش املایی در OnePassConvertingRules آمده‌اند. از تابع SetOnePassConvertingRules از کلاس PersianSpellChecker مشخص کرد که چه زیرمجموعه‌ای از این قوانین برای پیش‌پردازش املایی مورد استفاده قرار گیرد. تابع OnePassCorrection می‌تواند برای اعمال این دسته از قوانین مورد استفاده قرار گیرد.

استفاده از الگوریتم ارائه شده توسط Peter Norvig
[9]

فانکشن correction(word) مناسب ترین وشبیه ترین کلمه به جای کلمه ی خطا را شامل می شود.

این الگوریتم بر مبنای نظریه احتمال کار می کند.این روش قبلا توضیح داده شده است.فراخوانی تابع correction(w) منجر میشود به اینکه مناسب ترین کلمه به جای کلمه ی خطا انتخاب شود.با توجه به کلمه‌ی خطا می خواهیم کلمه با بیشترین احتمال درست بودن را به جای کلمه‌ی غلط قرار دهیم. یعنی P(w|c) ،احتمال درست بودن کلمه‌ی c به جای کلمه‌ی خطای w ، بیشترین مقدار باشد.
argmaxc ∈ candidates P(c|w)
که به وسیله ی Bayes'_theorem،معادل میشود با:
argmaxc ∈ candidates P(c) P(w|c) / P(w)
وتا زمانی که p(w) یکسان باشد برای هر کاندیدای c،میتوان نتیجه گرفت که:
argmaxc ∈ candidates P(c) P(w|c)
پس
4قسمت از این نظریه شامل:
Selection Mechanism: argmax
کاندیدایی را انتخاب میکنیم با بیشترین احتمال.
Candidate Model: c ∈ candidates
این میگوید کدام کاندیدای درست است
Language Model: P(c)
احتمال اینکه c پیدا شود به عنوان یک کلمه از متن ما.به عنوان مثال کلمه ی the در 7درصد از مواقع ممکن است در متن ما ظاهر شود.پس P(the) = 0.07
Error Model: P(w|c)
احتمال درست بودن کلمه‌ی c به جای کلمه‌ی خطای w.
در قسمت Selection Mechanism:
max(WORDS, key=P) و max(candidates(word), key=P)،همان argmax که توضیح داده شد هستند.(max با ارگیومنت key)
در قسمت Candidate Model:
عمل تصحیح با توجه به یکی از الگوهای خطای اصلی مانند خطای درج اضافی حرف ، حذف حرف، جانشینی، جابجایی و خطای فاصله ، انجام می‌شود.
یک simple edit،یرای یک کلمه شامل
deletion() برای حذف یک کلمه است.
Transposition() برای عوض کردن دو کلمه نزدیک هم است.
Replacement()تغییر یک کلمه به کلمه ای دیگر است.
Insertion()برای اضافه کردن یک کلمه است.
. بدین ترتیب تابع edits1 لیستی از تمام کلمات درستی که به فاصله‌ی یک از کلمه‌ی خطا هستند را بر می‌گرداند و تابع edits2 لیست کلمات درست به فاصله‌ی ۲ از کلمه ی غلط را بر می‌گرداند وتابع edits3،
لیستی از تمام کلمات درستی که به فاصله‌ی چهار از کلمه‌ی خطا هستند را بر می‌گرداند
Edit distance یعنی تعداد اعمال لازمه برای تبدیل کلمه ی خطا به کلمه ی صحیح و شکل درست کلمه.
بااین حال اگر ما بخواهیم خودمان را محدود به کلمات کنیم که شناخته شده هستند و در دیکشنری موجود هستند پس مجموعه ما تاحدی کوچک می شود و در این صورت باknown(word) شناخته می شوند.
known_edits2 فقط کلماتی از لیست بازگشتی edits2 را بر می‌گرداند که در لیست کلمات مدل شده بوده‌اند.
در نهایت،تابع correct با در نظر گرفتن بیشترین احتمال، کلمه‌ای درست را به جای کلمه‌ی غلط قرار می دهد.
پس،
P،احتمال 'word'است.
Correction(word)،نشان دهنده ی بیشترین احتمالی است که برای غلط یاب املایی از یک word در نظر گرفته می شود.
Candidate(word)،برای word،خطایاب املایی شدنی را تولید میکند.
Known(word)،زیر مجموعه ای ازwords هایی که پدیدار می شوند در دیکشنری از خود word است.
Vowels(char)،تمام vowel های ممکنه را تولید میکند اگر که char ما vowel باشد.در بقیه موارد هم یک لیست empty برمیگرداند.
Similar_to(char)،تعدادی از کاراکترهای مشابه را تولید می کند.
Double_back_edit2(word)،حذف کردن یکی از دو کاراکتری که به صورت متوالی در یک کلمه ای وجود دارد.
Double_edit(word)،دقیقا کار double_back_edit(word) را انجام میدهد، با این تفاوت که برعکس ان است یعنی مثلا در مثال adress،اگر address را به صورت adres تایپ کنیم این فانکشن کمک میکند تا ان را اصلاح کرده و به صورت address بنویسیم.
Double_edit2(word)، دقیقا کار double_back_edit(word) را انجام میدهد، با این تفاوت که برعکس ان است.
Vowel_edit(word)،یک زیر مجموعه ای از words هایی که vowel ها جایگزین می شوند را میگیرد.
Similar_edits(word)،یک زیر مجموعه ای از words هایی که chars ها جایگزین میشوند به وسیله ی همسان و شبیه بودن،را میگیرند.(اگر وجود داشته باشد)
Spelltest()،correction(wrong) را اجرا میکند روی هر دوجفت right,wrong))ونتیجه را نشان میدهد.
spelltest با توجه به تعداد کل کلمات، کلمه ی صحیح داخل لغت‌نامه‌ی مجموعه‌ی تست و کلمه‌ای که به جای کلمه‌ی خطا در نظر گرفته شده ، درصد دقت روش را باز می‌گرداند.

در قسمت Language Model:
برای پیاده‌سازی ابتدا از فایل big.txt برای ساخت مدل زبان استفاده می‌کنیم. تابع اصلی در این قسمت train است که برای محاسبه‌ی تعداد دفعات تکرار هر کلمه در متن استفاده می‌شود.بدین ترتیب مدل احتمال ساخته می‌شود.

در نهایت برای ارزیابی سیستم از مجموعه داده یBirkbeck استفاده می‌کنیم. دو مجموعه ی تست که شامل کلمه ی درست و کلمه‌ی خطا هستند را توسط لغت‌نامه، تشکیل می‌دهیم.
پیوند

بهبود نتایج وتکمیل گزارش

در این مرحله پیاده سازی یک خطایاب املایی صورت گرفته است.
پیوند

برنامه تنها از re استفاده می کند پس نیازی به هیچ کتابخانه ای نیست. می توان با دستور phyton Main.py برنامه را فراخوانی کرد( فقط مسیر terminal, CMD باید پوشه اصلی پروژه که حاوی کد است باشد) پس از بارگزای لیست لغات در رم. می توانید بین گرفتن متن از ورودی و یا خواندن یک فایل متنی انتخاب کنید در صورت انتخاب فایل نام آن پرسیده می شود که پس از وارد کردن برنامه نتیجه را در *.out.txt در مسیر اصلی ذخیره می کند. در صورت انتخاب ورودی برنامه منتظر ورودی می شود سپس نتیجه را در خروجی استاندارد نمایش می دهد. خروجی شامل کلمه خطا دار به همراه پیشنهاد های محتمل تر است. برای راحتی کار با پروژه استفاده از PyCharm توصیه می شود.
نحوه کار برنامه:
روش تشخیص اشتباه املایی استفاده از جست و جوی Brute force روی فایل ورودی و استفاده از جدول Hash می باشد. برای اضافه کردن زبان جدید باید یک فایل مشابه dictionary.json برای آن زبان درست کنید (متاسفانه برای زبان فارسی حتی لیست واژه ها هم به شکل صحیح در دست رس نیست و برنامه موجود فقط در انگلیسی Aplha کار می کند) این فایل توسط متد read در کلاس HT خوانده می شود. خواندن واژه ها آنها به کد هش تبدیل می شوند. برای این کار از روش djb2 استفاده می شود که ساختار آن به شکل زیر است.

از این به بعد برای افزایش سرعت جست و جوی خطا روی این اعداد انجام می شود.
پس از دریافت وردی اگر فایل بود تمامی خطوط و اگر متن بود روی همان تقسیم انجام می شود در مورد زبان های بر پایه لاتین می توان به راحتی از موتور Regex به شکل زیر استفاده کرد:

همان گونه که مشخص در نتیجه تمامی کلمات بدون علائم تولید می شوند. حال عدد هش این کلمات بررسی می شود. برای این کار ابتدا جدول hash مرتب سازی صعودی می شود و برای این کار از روش Quick Sort (https://en.wikipedia.org/wiki/Quicksort) استفاده می شود در لحظات اول که بخش ها بزرگ هستند این روش بسیار سریع است ولی در انتها کند می شود بنابراین در قبل از پایان از TimSort (https://en.wikipedia.org/wiki/Timsort) برای مرتب کردن مابقی استفاده می شود که در خود Phyton پیاده سازی شده کد زیر متد اصلی Quick Sort در کلاس HT می باشد:

با استفاده از این روش با سرعت بسیار بالا جدول مرتب سازی می شود. سپس بررسی می شود که عدد هش کلمه در کدام ناحیه جدول می باشد و همان ناحیه بررسی می شود. در بدترین حالت این روش دو برابر از جست و جوی المانی سریع تر است کد زیر مربوط به متد سرچ BFS می باشد:

حال کلمه و کلمات همسایه آن بررسی می شوند اگر همه آنها کلمات بزرگی (بزرگتر از 5( بودند که در جدول نبودند احتمالا یک اصتلاح غیر معمول است. اگر خود کلمه در جدول نبود ولی یکی از همسایه ها بود حتما مشکل املایی است. اگر کلمه مشکل املایی بود کلماتی در جدول که یکی از دو حروف اولشان با خطا یکسان است از نظر فاصله کاراکتری( کاراکتر های مشابه) بررسی می شوند کلمه هایی با کمترین فاصله برای رفع خطا املایی توصیه می شوند. کد های زیر به ترتیب متد تشخیص خطا در کلاس Core و پیداکردن توصیه در کلاس HT هستند:

در نهایت بسته به انتخاب اولیه نتیجه در خروجی نمایش داده می شود یا در فایل ذخیره می شود.
فایل Main.py اسکریپت اصلی برنامه است که باید اجرا شود.
فایل Core.py اسکریپت تشخیص است.
فایل HT.py اسکریپت پیاده سازی متد های جدول Hash می باشد.
یک خروجی فایل به نام test.txt.out.txt در مسیر اصلی موجود است که حاوی خروجی تولید شده توسط test.txt می باشد.

در ادامه مراحل اجرای کد را مشاهده خواهید کرد.

مراجع

1- K. Kukich, “Techniques for automatically correcting words in text,” ACM Computing Surveys, vol. 24, pp. 378-439, 1992.1

2-Hanson, Riseman, and Fisher, “Context in word recognition,” Patt. Recog. 8 35-45

3-J. J. Hull, and S. N. Srihari, “Experiments in text recognition with binary n-gram and Viterbi algorithms,” IEEE Trans. Patt. Anal. Machine Intell. PAMI-4, 5 (Sept.), 1982 520-530.
4-D. E. Knuth, “The Art of Programming Vol. 3, Sorting and Searching,” Addison-Wesley, Reading 1973.
5-E. A. Fox, Q. F. Chen, and L. S. Heath, “A faster algorithm for constructing minimal perfect hash functions,” In Proceedings of the 15th annual International SIGIR Meeting. ACM, New York, 1992, 266-273.
6-K. Atkinson, “Gnu aspell,” In Available at http://aspell.net, 2009.
7-F. J. Damerau, “A technique for computer detection and correction of spelling errors,” Commun ACM 7, 3 (Mar.), 1964, pp. 171-176.
8-https://www.cs.indiana.edu/~alexr/nlpclass_2012/hw3.html
9-http://norvig.com/spell-correct.html