# مقدمه
**چکیده**
در این پروژه ابتدا به بیان شرح مسئله و کارهای مرتبط با خطایابی املایی می‌پردازیم و تکنیک‌ها و چالش‌های پیشرو را مورد بررسی قرار می‌دهیم. انواع الگوریتم‌ها و مدل‌سازی‌ها را بیان می‌کنیم و سپس توسط زبان برنامه‌نویسی پایتون به پیاده‌سازی می‌پردازیم. این خطایاب پس از خطایابی واژگان،سعی می‌کند پیشنهادهای صحیح را به کاربران ارائه دهد. مشکلات و چالش‌های پیشرو در زمینه‌ی پیشنهاددهی به کاربران مورد بررسی قرار خواهد گرفت و روش‌های مختلف پیاده‌سازی خواهد شد. سپس به ارزیابی سیستم خواهیم پرداخت و روش‌های موجود را با هم مقایسه خواهیم کرد.
**مقدمه**
مسئله‌ی پیدا کردن خطاهای املایی توسط ماشین از جمله مسائل مورد بحث در پردازش زبان‌های طبیعی است. پس از به وجود آمدن علوم رایانه‌ای و مسائل هوش مصنوعی ، پردازش زبان‌های طبیعی مورد توجه بسیار قرار گرفت. به طور کلی **پردازش زبان‌های طبیعی** یکی از زیرشاخه‌های بااهمیت در حوزه گسترده هوش مصنوعی ، و نیز در دانش زبان‌شناسی است. تلاش عمده در این زمینه ماشینی کردن فرایند درک و برداشت مفاهیم بیان گردیده با یک زبان طبیعی انسانی توسط ماشین است. با فراگیر شدن پدیده اینترنت و گسترش متون الکترونیکی این علم اهمّیت ویژه‌ای پیدا کرده است که از جمله نتایج آن می‌توان به استخراج اطلاعاتی خاص از یک متن، ترجمه یک متن به زبانی دیگر، یافتن مستنداتی خاص در یک پایگاه داده نوشتاری ، سیستم های پرسش و پاسخ انسان با کامپیوتر، سرویس های اتوماتیک ارتباط با مشتری از طریق تلفن و سیستم های کنترلی توسط صدا اشاره کرد. همچنین پیاده‌سازی انواع خطایاب‌های املایی ، مترجمین هوشمند ماشینی، نرم افزارهای پردازش و تشخیص گفتار و نرم افزارهای تبدیل متن به صدا از جمله تلاش‌ها در این زمینه بوده است.
در رابطه با خطایابی املایی ، مسئله‌ی تشخیص خودکار و تصحیح خطاهای املایی موجود در انواع متن از دهه ی ۶۰ میلادی مطرح بوده است و تا به امروز نیز پیدا کردن الگوریتم ها ی بهینه برای این کار مورد توجه بوده است چراکه طبق آخرین بررسی‌ها در مجموع حدود ۲۶٪ از پرس و جو‌های وب شامل انواع غلط املایی می شوند. خطایاب‌های املایی در تصحیح و کمک به جستجوی سریعتر و دقیق‌تر در اینترنت، تصحیح خطاهای ناشی از تبدیل تصویر به متن،صرفه جویی در وقت و هزینه ، ابزارهای جانبی برای ویرایشگرهای متنی، ابزار پیش پردازنده در پردازش زبان‌های طبیعی ، واسط‌های بازیابی اطلاعات، تبدیل گفتار به متن و کامپیوترهای مبتنی بر قلم و … کاربرد‌های بسیاری دارند. همچنین امروزه حجم بسیار زیادی از اطلاعات و متون فارسـی توسـط رایانـه‌ها تولید میشوند. فرایند تولید و ورود اطلاعات، به ویژه متن، هیچ گاه عـاری از خطـا نبـوده و هزینه های بسیاری برای یافتن و برطرف ساختن این خطاها صرف میشود که این امر نیاز به خطایاب را بیشتر نمایان می کند.
# کارهای مرتبط
**خطایاب املایی**
به طور کلی خطایابی املایی شامل بررسی یک متن ، مشخص کردن کلمه یا کلمات اشتباه و تصحیح آن ها می شود. بعضی از خطایاب‌های امروزی به جای ارائه یک تصحیح، لیستی از پیشنهادات را برای کاربر نمایش می‌دهند. بعضی از خطایاب‌های قدیمی‌تر فقط کلمه‌ی شامل غلط املایی را مشخص می‌کنند و پیشنهادی برای املای صحیح ارائه نمی‌کنند چراکه عمل تصحیح، به مراتب پیچیده‌تر و نیازمند پردازش بیشتری است.
خطایاب‌ها برای پیدا کردن خطاها از الگوهای مشخصی استفاده می‌کنند به طوریکه دسته بندی‌های مختلفی برای انواع خطاها وجود دارد و می‌توان توسط مدل سازی‌های مختلف زبان‌ها آنها را شناسایی کرد، که جلوتر به آنها می‌پردازیم.
**انواع خطاهای املایی**
خطاهای املایی را می توان به دسته‌های مختلفی تقسیم‌بندی کرد.
به طور کلی دو دسته‌ی :
۱) خطاهای غیر لغت ( Non-word Errors )
۲) خطاهای لغات واقعی ( Real-word Errors )
غیر لغات‌ها همانطور که از نام آنها پیداست کلماتی هستند که معنایی ندارند و در فرهنگ لغات وجود ندارند. معمولا عمل تصحیح آنها با اضافه یا کم کردن و یا با تغییر یک یا چند حرف انجام می شود. برای مثال اگر کاربر کلمه‌ی (فقث) را وارد کرده باشد می توان حدس زد که کلمه‌ی درست (فقط) می‌باشد.
خطاهای لغات واقعی خود شامل خطاهای تایپی(Typographical errors) ، خطاهای شناختی (Cognitive errors) و خطاهای آوایی (Phonetic) میشوند. در خطاهای لغات واقعی ممکن است کلمه‌ی نوشته شده از نظر املایی درست باشد و در فرهنگ لغات هم موجود باشد اما کاربرد آن در متن نوشته شده اشتباه باشد.
در خطاهای تایپی فرض بر این است که کاربر املای درست را می‌داند اما به دلایلی خطا انجام می‌دهد (برای مثال دیو به جای دیر و یا اسلام به جای سلام). خطاهای تایپی شامل خطاهای ناشی از‌عادات کاربر و یا نزدیکی نوشتاری حروف است.
در خطاهای شناختی کاربر تسلط کافی به زبان را ندارد و معنای کلمه‌ی درست با کلمه ی وارد شده متفاوت است (برای مثال غصه به جای قصه و یا توجیح به جای توجیه ).
خطاهای آوایی همانند خطاهای شناختی هستند با این تفاوت که کلمه‌ی خطا از لحاظ آوایی مشابه کلمه‌ی صحیح مورد نظر است (برای مثال اصلاح به جای اسلاح )
مورد
**الگوی خطاهای اصلی :**
در تحقیقاتی که در این زمینه انجام شده است مشخص شده که حدود ۸۰٪ از کل خطاهای املایی موجود در یک نوشتار شامل یکی از موارد زیر هستند [6] :
۱)خطای درج اضافی حرف : اضافه شدن یک یا چند حرف به کلمه‌ی درست.
۲)خطای حذف حرف : پاک شدن یک یا چند حرف از کلمه‌ی درست.
۳)خطای جانشینی : استفاده از یک حرف به جای حرفی دیگر .
۴)خطای جابجایی : جابجایی دو حرف با هم.
۵)خطای فاصله : چسبیدن دو کلمه درست بدون فاصله به هم.
خطایاب ها با کمک این الگو های خطا و مدل سازی زبان‌ها ، می توانند به خطایابی بپردازند.
**تشخیص خطا**
**۱) تشخیص خطاهای غیر لغت :**
**استفاده از لغت نامه**
ساده‌ترین و پراستفاده‌ترین روش برای تشخیص خطاهای غیر لغت ، استفاده از لغت نامه‌ها (Dictionaries) است. در این روش کلمات درست در یک لغت نامه ذخیره می شوند. سپس خطایاب تک تک کلمات وارد شده را در داخل لغت نامه جستوجو می کند و اگر همانند آن کلمه پیدا نشود ، خطایاب یک خطا را تشخیص داده است. بدین ترتیب هرچه لغت نامه بزرگتر باشد ، بهتر است. اما در این روش مسئله‌ی زمان پاسخگویی و همچنین فضای ذخیره شده نکات مهمی هستند. معمولا تعداد کلمات لغت نامه ها حدود ۲۵۰ هزار لغات یا بیشتر می باشد. با بزرگتر شدن لغت نامه زمان پاسخگویی سیستم بسیار بالا می رود. همچنین به فضای ذخیره سازی زیادی نیاز خواهیم داشت. برای حل این مشکل روش‌های مختلفی مثل مراجعه به لغت نامه‌های کارا، تقسیم لغت نامه‌ها و روش‌های مبتنی بر پردازش ریخت‌شناسی وجود دارند.
**بهینه سازی روش لغت نامه**
برای مثال یک روش این است که فقط ریشه‌ی کلمات را ذخیره کنیم (ریشه‌یابی). در این روش توسط الگوریتم‌ها و مجموعه قوانین خاص هر زبان پیشوند‌ها و پسوند‌های کلمات را حذف می‌کنیم. به هنگام جست و جوی خطا نیز همین کار را بر روی کلماتی که کاربر وارد کرده انجام می‌دهیم وریشه‌های ایجاد شده را با ریشه های ذخیره شده در لغت نامه مقایسه می‌کنیم. بدین ترتیب فضای اشغال شده توسط لغت‌نامه کمتر شده و زمان پاسخ گویی نیز بسیار سریع تر میشود. مشکل این روش این است که ممکن است بعضی خطاها نادیده گرفته شوند چراکه امکان دارد کلمه‌ی وارد شده توسط کاربر ریشه‌ی درستی داشته باشد ولی به همراه پسوند یا پیشوند وارد شده ، حاوی غلط املایی باشد.
روش دیگر استفاده از تابع درهم (Hash Function) در ذخیره‌سازی است. در این روش برای هر کلمه‌ی لغت نامه یک آدرس درهم در نظر می‌گیریم. این آدرس با اعمال تابع درهم بر روی هر یک از حروف الفبا به دست می آید. برای مثال به حرف الف عدد ۱، ب عدد ۲ پ عدد ۳ و به همین ترتیب به تمام حروف یک عدد را نسبت می دهیم. سپس با استفاده از تابع درهم یعنی اعمال محاسبات ریاضی بر روی اعداد حروف هر کلمه ، به یک عدد برای هر کلمه می‌رسیم. بدین ترتیب به جای ذخیره‌ی هر کلمه ، این عدد را در حافظه ذخیره می‌کنیم. هنگامی که کاربر یک رشته‌ی ورودی را وارد می‌کند، آدرس درهم آن محاسبه میشود و با مراجعه به جدول درهم از پیش ساخته‌شده و دریافت کلمه‌ی ذخیره شده در آن مکان اگر کلمات یکی نبودند یا کلمه‌ای وجود نداشت، غلط املایی تشخیص داده میشود. این روش در واقع نگاشت بیت به بیت (BitMap) می باشد.
بدین ترتیب سرعت دسترسی به اطلاعات و زمان پاسخگویی بسیار سریعتر میشود. به دلیل خاصیت دسترسی مستقیم نیازی به مقایسه‌های زیادی نیست. همچنین فضای ذخیره‌سازی نیز کاهش می‌یابد. مهم‌ترین چالش در این روش داشتن تابع درهم مناسب است چراکه هر کلمه لازم است که آدرس منحصر به فردی داشته‌باشد. پیدا کردن تابع درهمی مناسب برای تولید این جدول درهم به گونه‌ای که کلمات تکراری تولید نکند و همچنین سریع بودن تابع مشکل اصلی این روش است. البته روش‌های مختلفی برای تولید چنین توابعی وجود دارد.
**استفاده از تحلیل چند نگاشت (N-grams)**
****
روش دیگر برای تشخیص خطاهای غیر لغت استفاده از تحلیل چند نگاشت است. چندنگاشت‌ها زیر دنباله‌های چند حرفی از رشته‌های کاراکتری هستند. برای مثال یک، دو، و یا سه حرفی. برای مثال، زیر نگاشت ۳ حرفی کلمه‌ی “آفتاب” شامل ‘آفت’ ، ‘فتا’ و ‘تاب’ ، میشود. دو روش کلی برای تحلیل چند نگاشت وجود دارد.
**۱.**
در یکی از این روش ها به طور غیر مستقیم از لغت نامه استفاده می‌کنیم بدین ترتیب که برای مثال ابتدا سه نگاشت‌های تمام کلمات لغت نامه را ذخیره می‌کنیم. حال هنگامی که کاربر رشته‌ای را وارد می‌کند چند نگاشت‌های آن نیز به همان روش قبلی ساخته میشوند و با چند نگاشت های لغت نامه مقایسه می شوند. عدم وجود آن ها در چند نگاشت‌های لغت نامه، مشخص کننده‌ی خطاهای احتمالی است.در این روش معمولاً به یک لغت نامه برای نگه داری از پیش جدول چندنگاشت‌ها نیاز است. در روش‌های مبتنی بر تحلیل چندنگاشت ممکن است تعداد قابل توجهی از خطاها تشخیص داده نشوند چراکه بسیاری از کلمات حاوی خطا، شامل چند نگاشت‌های غیرمعمول نمی‌شوند اما در تشخیص خطاهایی که توسط دستگاه‌های تشخیص نوری حروف (Optical Character Recognition) خطایابی میشوند ، خوب عمل می‌کنند.
**۲.**
در روش دیگر برای تحلیل چند نگاشت‌ها از لغت نامه استفاده نمی‌شود. همانند روش قبل ابتدا چند نگاشت‌های متن ورودی توسط کاربر مشخص میشوند اما این بار تعداد تکرار آن ها در متن اهمیت دارد. برای مثال سه نگاشت “پخز” که فقط یکبار در متن تکرار شده باشد،احتمال خطا بودن آن زیاد است. اما “هست” که بسیار بیشتر استفاده شده است احتمال خطا بودن آن ناچیز است. همانند روش قبل احتمال تشخیص ندادن خطاهای عادی وجود دارد اما این روش در تشخیص خطاهای تایپی بسیار کارا عمل می‌کند.همچنین مزیت دیگر آن این است که برای هر زبانی می‌توان از این روش استفاده کرد.
جدول‌های چند نگاشت می توانند با روش‌های مختلفی ساخته شوند. ساده‌ترین روش استفاده از دونگاشت دودویی است که یک آرایه‌ی دو بعدی است که تمام ترکیب‌های دوتایی حروف را در بر می گیرد. هر خانه‌ی آن شامل ۱ (اگر آن دونگاشت در متن ما حداقل یکبار تکرار شده باشد) یا ۰ است. یک سه نگاشت دودویی به همین شکل ،ولی یک آرایه‌ی سه بعدی است.
این آرایه ها را چند نگاشت‌های دودویی غیر وابسته به موقعیت می‌نامند. بدین معنا که محل چندنگاشت را در کلمه مشخص نمی‌کنند.
با اختصاص فضای بیشتر به جدول چند نگاشت می‌توان موقعیت چندنگاشت را هم ذخیره کرد. این کار باعث بهبود کارایی روش‌های چند نگاشت‌ها می شود چراکه می توان محل آنها در کلمه را نیز مقایسه کرد.
به طور کلی تحلیل چند نگاشتی در بعضی زمینه‌ها مثل تشخیص نوری حروف و خطاهای تایپی مفید است، ولی برای خطاهای تولید شده توسط انسان دقت کمتری دارد. به همین خاطر بیشتر روش‌های تصحیح خطای املایی بر اساس مراجعه به لغت‌نامه می باشند.
**خطای حرف اول**
عموما خطا در حرف اول کلمات رخ نمی‌دهد. بدین ترتیب می‌توانیم لغت‌نامه ها را بر اساس حرف اول تقسیم بندی کنیم تا زمان مراجعه به لغت نامه و زمان پاسخ گویی کاهش یابند.مشکل این دسته بندی این است که در این صورت دسته‌ای از خطاها(خطاهای حرف اول) توسط سیستم ما تشخیص داده نمی شود.
**طول کلمه**
طبق تحقیقات انجام شده، در بسیاری از مواقع طول کلمه‌ی خطا در فاصله ی دوتایی از طول کلمه‌ی صحیح است. این موضوع باعث می شد محققان لغت‌نامه ها را بر اساس طول کلمات به چند دسته تقسیم کنند تا زمان جستجو کاهش یابد.
با توجه به قانون زیپف در یک نوشته کلمات کوتاه‌تر تعداد تکرارهای بیشتری دارند. همچنین کلمات با تکرار بیشتر همسایه‌های تک خطایی بیشتری دارند. ولی معمولاً کلمات کوتاه کمتر اشتباه نوشته میشوند. در ضمن هرچه کلمه کوتاه‌تر باشد متن درون کلمه‌ای کمتری در اختیار ما قرار می‌دهد و کار تصحیح سخت‌تر میشود.
**۲) تشخیص خطای لغات واقعی :**
از جمله ایرادات خطایاب‌ها می توان به تشخیص دادن کلمه‌ی درست به عنوان خطا و یا تشخیص ندادن بعضی خطاها اشاره کرد. دلیل ایراد نوع اول ، وجود کلمات مبهم و اسم‌های خاص در متن وارد شده می باشد. می توان با فراهم کردن لغت نامه‌ی بزرگتر برای خطایاب و یا استفاده از لغت نامه‌ی تخصصی برای انواع مختلف متن (برای مثال پزشکی) درصد این ایراد را کاهش داد. اما برای ایراد دوم راه حل خاصی وجود ندارد چراکه تعداد اسم های خاص بسیار زیاد است. بسیاری از خطایاب‌ها امکانی را فراهم می‌کنند که کاربر اسم خاص را برای خطایاب مشخص کند تا بعد از اولین باری که خطا در نظر گرفته میشود خطایاب دوباره آن را خطا اعلام نکند.
ایراد نوع دوم در مقابل ایراد اول یعنی تشخیص اشتباه بسیار مهم‌تر است چراکه کاربر همواره می تواند خطا را نادیده بگیرد ، اما تشخیص ندادن کلمه‌ی خطا نگران کننده است چراکه کاربر انتظار متنی بدون خطا را دارد.
این مشکل با افزایش سایز لغت‌نامه برای کاهش ریسک ایراد نوع اول ، بیشتر نیز می شود چراکه با افزایش لغات مبهم لغت‌نامه امکان تشخیص ندادن خطاهای لغات واقعی بیشتر میشود.
خطایاب های کمی هستند که می‌توانند خطای لغات واقعی را تشخیص دهند. ۳ پروژه در این زمینه قابل ذکر هستند.
# پروژه‌ی اول : CRITIQUE
اولی سیستمی با نام CRITIQUE است که توسط IBM ساخته شده است. در این برنامه متن از لحاظ نوشتاری ، دستور زبان و قالب نوشتاری، بررسی میشود.سیستم توسط گرامری که برای آن طراحی شده است ، متن را بررسی می‌کند و نقش کلمات شامل اسم ، قید ، افعال اصلی و کمکی و غیره را مشخص می کند. اگر جمله‌ای با قواعد گرامر تعریف شده هم‌خوانی نداشته باشد ، آن قاعده کنار گذاشته می شود و دوباره جمله بررسی میشود. این کار تا زمانی ادامه پیدا می کند که جمله مورد قبول واقع شود. حال سیستم با دانستن قواعد کنار گذاشته شده ، می‌تواند تشخیص دهد چه قسمتی از دستور زبان مشکل داشته است.
# پروژه‌ی دوم : خطایاب دانشگاه لنکستر
پروژه ی دوم نیز همانند سیستم اولی بر پایه قواعد نحوی است. در ابتدا این پروژه در دانشگاه لنکستر فقط برای مشخص کردن نقش کلمات در جمله بود اما بعدها به خطایاب املایی تبدیل شد. سیستم ابتدا با مراجعه به یک لغت‌نامه نقش کلمات را مشخص می‌کند. لغت‌نامه بر اساس نقش کلمات مرتب شده است (برای مثال لغت‌نامه‌ای برای افعال). همچنین سیستم حاوی جدولی است که جایگاه و ترتیب قرار گرفتن نقش های مختلف در جمله را مشخص می‌کند. وقتی کاربر متنی را وارد می‌کند سیستم ترتیب قرار گرفتن کلمات با نقش‌های دستوری مختلف را بررسی می‌کند و دنباله ای که احتمال درست بودن آن کم است را ، مشخص می‌کند. بدین ترتیب سیستم حدس‌هایی را برای پیشنهاد کلمه‌ی درست ارایه می دهد.
# پروژه‌ی سوم : مدل پیشرفته تر CRITIQUE
پروژه ی بعدی مدل پیشرفته تر سیستم قبلی بود که باز هم توسط IBM انجام شد. در این سیستم احتمال قرار گرفتن ۲ کلمه در کنار هم (و یا احتمال های دنباله‌ی ۳ تایی کلمات) محاسبه میشوند. سپس عمل تشخیص و تصحیح با توجه به این احتمالات انجام می شوند.
**تصحیح خطا**
برای تصحیح ، خطایاب باید کلمه‌ی مورد نظر کاربر را حدس بزند و همچنین قادر به نوشتن املا صحیح آن باشد. تولید املا درست سخت نیست چراکه همانطور که توضیح داده شد روش‌های مختلفی برای ذخیره‌ی املای درست (از جمله ذخیره به صورت لغت نامه) وجود دارد. اما قسمت سخت‌تر ارایه ی پیشنهاد مناسب است.
به طور کلی کامپیوتر در تصحیح کلمات کوتاه تر کار سخت تری دارد تا کلمات بلند چراکه انتخاب‌ها برای کلمات کوتاه‌تر بسیار بیشتر است.
به دلیل حجیم بودن لغت‌نامه‌ها خطایاب برای عمل تصحیح باید قادر باشد فقط بخشی از لغت‌نامه که احتمال وجود کلمه ی درست در آن بیشتر است را ، ابتدا بررسی کند. این کار با توجه به توضیحی که در قسمت خطای حرف اول دادیم و در نظر گرفتن اینکه اکثر خطاها یکی از انواع الگوی خطاهای اصلی هستند ، انجام می شود. یعنی بیشتر خطاها از نوع خطای درج اضافی حرف ، خطای حذف حرف ، خطای جانشینی و یا خطای جابجایی هستند که معمولا با تغییر فقط یک حرف ، می توانیم به کلمه ی درست برسیم . همچنین حرف اول عموما صحیح است و بدین ترتیب لغت‌نامه بر اساس آن می تواند محدوده‌ی جست و جوی خود را مشخص کند و کلماتی که به فاصله‌ی یک یا چند حرف از کلمه ی ورودی هستند را بررسی کند. طبق تحقیقات انجام شده ۸۰٪ از خطاها به فاصله‌ی یک حرف از کلمه ی درست هستند [11]. فاصله در این مبحث به تعداد عملیات های تصحیح مورد نیاز گفته میشود.
برای تصحیح این خطاها می توان از الگوریتم ‘کم ترین فاصله‌ی تصحیح’ استفاده کرد. در این الگوریتم برای رسیدن به کلمه‌ی درست می توان از درج یک حرف ، حذف حرف و جا به‌جایی استفاده کرد . هر کدام از این اعمال را می توان چند بار انجام داد تا کلمه ی درست تولید شود.
\**Soundex**
در این سیستم با توجه به آوا و تلفظ ، کلمات در دسته‌های مختلفی دسته بندی میشوند. کلمات با تلفظ مشابه در گروهای یکسان قرار می گیرند. برای هر کلمه یک کد soundex ساخته می شود. این روش بر اساس مشابهت حروف صفحه کلید می باشد. حال با ساخته‌شدن کد برای هر کلمه و دسته بندی آنها ، خطایاب می تواند با مراجعه به گروه کلمه‌ی خطا ، کاندید‌های تصحیح را انتخاب کند.در کد soundex حروف صدادار حذف میشوند و حروف بی صدا دسته بندی می شوند.
ساخت کد soundex :
۱) حرف اول به صورت بزرگ نگه داشته می شود
۲) حروف a,e,i,o,u,y,h,w با خط فاصله جایگزین میشوند
۳) دسته بندی حروف دیگر:
b,f,p,v : ۱
c,g,j,k,q,s,x,z : ۲
d,t : ۳
l : ۴
m,n : ۵
r : ۶
۴) اعداد کنار هم مشابه حذف میشوند
۵) خط فاصله‌ها حذف میشوند
۶) حرف اول به صورت بزرگ به همراه ۳ عدد اول نگه داشته میشوند.( اگر کمتر از ۳ عدد ساخته شده بود ، ۰ اضافه می‌کنیم )
برای مثال : (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#
در مثال بالا ۶ شباهت را مشاهده می‌کنیم که می تواند حدس بسیار مناسبی برای تصحیح باشد.
# آزمایش‌ها
در این بخش به توضیح روش‌های استفاده شده در فاز دوم و ارزیابی‌های انجام شده می پردازیم.
**استفاده از مدل‌های چند نگاشت برای خطایابی املایی**
**استفاده از مدل زبان**
در اولین روش برای پیاده سازی, از مجموعه کد و داده های Dan Jurafsky و Chris Manning که در دوره‌ی آنلاین خود برای NLP ارائه داده‌اند ، استفاده می‌کنیم. لینک این داده‌های اولیه‌ی مسئله در قسمت پیوندهای مفید ارائه شده است.
اساس کار این روش کد توضیح داده شده توسط Peter Norvig در رابطه با خطایابی املایی می‌باشد. در این روش برای ساخت خطایاب املایی مدل‌های زبانی مختلفی را از نظر دقت و کارایی بررسی می‌کنیم. در مدل زبان ، به هر مجموعه ی از حروف ، احتمالی را اختصاص می‌دهیم. سپس می‌توان با توجه به این احتمالات به عمل خطایابی پرداخت. برای مثال احتمالات درست بودن کلمات مختلف به جای کلمه‌ی غلط را بررسی می‌کنیم و هر کلمه‌ی که احتمال درست بودن آن بیشتر باشد را با آن جایگزین می کنیم. با توجه به روشی که برای محاسبه‌ی این احتمالات انتخاب می کنیم ، مدل های مختلفی برای زبان ساخته میشود. برای ارزیابی سیستم از مجموعه داده‌ای شامل جملاتی با فقط یک خطای املایی، استفاده می‌کنیم. سپس میزان دقت مدل های مختلف زبانی را بررسی می کنیم. بدین ترتیب که میزان دقت برابر است با تعداد تصحیح های درست به تعداد کل جملات.
**داده ی مورد استفاده**
داده‌ی ما مجموعه‌ای از نوشته های دانش آموزان متوسطه است که توسط David Holbrook جمع‌آوری شده است.
پوشه‌ی داده شامل سه فایل است :
۱) holbrook-tagged-train.dat : مجموعه نوشته برای ساخت مدل زبان
۲) holbrook-tagged-dev.dat : مجموعه نوشته شامل خطاهای املایی
۳) count_1edit.txt : جدولی شامل تعداد تغییرات و ویرایش های لغات
**پیاده سازی**
در این روش سه مدل زبانی را پیاده سازی می‌کنیم:
۱) Laplace Unigram Language Model : مدل نگاشت تکی ( یک نگاشت) همراه با یک هموارسازی.
منظور از هموارسازی این است که به کلماتی که در داخل متن مورد استفاده برای مدل‌کردن نیستند هم یک احتمال
کمی بدهیم.
۲) Laplace Bigram Language Model : مدل نگاشت دوتایی ( دو نگاشت) همراه با یک هموارسازی.
۳) Stupid Backoff Language Model : ترکیبی از مدل اول بدون هموارسازی و مدل دوم همراه با هموارسازی.
توضیح چند تابع اصلی :
۱) train(HolbrookCorpus corpus) : با توجه به مجموعه‌ای از نوشته (corpus) مدل زبانی را تشکیل می دهد. محاسبه‌ی تعداد کلمات ، جملات و احتمالات در این تابع انجام می شود.
۲) (score(List words : تابع ارزیابی مدل زبانی
توضیح کلاس‌ها:
۱) SpellCorrect.py : این کلاس بهترین انتخاب را با توجه به مدل زبانی داده شده، انجام می‌دهد و کلمه‌ی‌غلط را تصحیح می‌کند.
۲) EditModel.py : این تابع احتمال درست بودن هر تصحیح را محاسبه می‌کند تا SpellCorrect.py از آن استفاده کرده و عمل تصحیح را انجام دهد.
۳) Sentence.py : شامل داده‌ها و توابع کمکی برای تولید جمله ی درست است. همچنین اطلاعات هر جمله را مثل کلمات درست و غلط آن را نگهداری می‌کند.
۴) Datum.py : لیستی شامل دو رشته می‌باشد. word و error. اولی کلمه‌ی تصحیح شده و دومی خطای املایی است. برای کلمات درست رشته‌ی error تهی است.
لینک github:
[پیوند](https://github.com/shahiiin/NLPSpellCorrector)
**روش دیگر: استفاده از الگوریتم ارائه شده توسط Peter Norvig**
در این روش نیز از تئوری احتمال که قبل‌تر توضیح داده شد، استفاده میشود. با توجه به کلمه‌ی خطا می خواهیم کلمه با بیشترین احتمال درست بودن را به جای کلمه‌ی غلط قرار دهیم. یعنی P(w|c) ،احتمال درست بودن کلمه‌ی c به جای کلمه‌ی خطای w ، بیشترین مقدار باشد.
برای پیاده‌سازی ابتدا از فایل big.txt برای ساخت مدل زبان استفاده می‌کنیم. تابع اصلی در این قسمت train است که برای محاسبه‌ی تعداد دفعات تکرار هر کلمه در متن استفاده میشود.بدین ترتیب مدل احتمال ساخته میشود.
همانطور که قبل‌تر توضیح داده شد، در اینجا هم از هموارسازی (smoothing) استفاده می‌کنیم و به کلماتی که در متن مرود استفاده برای مدل‌سازی نبودند هم احتمال کمی می‌دهیم. برای این کار از کلاس collections.defaultdict استفاده می‌کنیم. مقدار پیش‌فرض هر کلید را ۱ در نظر می‌گیریم.
همچنین عمل تصحیح با توجه به یکی از الگوهای خطای اصلی که یعنی خطای درج اضافی حرف ، حذف حرف، جانشینی، جابجایی و خطای فاصله ، انجام میشود.به تعداد اعمال مورد نیاز برای تبدیل کلمه‌ی خطا به کلمه‌ی درست edit distance گفته میشود. بدین ترتیب تابع edits1 لیستی از تمام کلمات درستی که به فاصله‌ی یک از کلمه‌ی خطا هستند را بر می‌گرداند.به همین شکل تابع edits2 لیست کلمات درست به فاصله‌ی ۲ از کلمه ی غلط را بر می‌گرداند.
همچنین known_edits2 فقط کلماتی از لیست بازگشتی edits2 را بر می‌گرداند که در لیست کلمات مدل شده بوده‌اند.
حال تابع correct با در نظر گرفتن بیشترین احتمال، کلمه‌ای درست را به جای کلمه‌ی غلط قرار می دهد.
ارزیابی :
برای ارزیابی سیستم از مجموعه داده یBirkbeck spelling error corpus [پیوند](http://ota.ahds.ac.uk/texts/0643.html) استفاده می‌کنیم. دو مجموعه ی تست که شامل کلمه ی درست و کلمه‌ی خطا هستند را توسط لغت‌نامه، تشکیل می‌دهیم. تابع spelltest با توجه به تعداد کل کلمات، کلمه ی صحیح داخل لغت‌نامه‌ی مجموعه‌ی تست و کلمه‌ای که به جای کلمه‌ی خطا در نظر گرفته شده ، درصد دقت روش را باز می‌گرداند.
لینک github:
[پیوند](https://github.com/shahiiin/NorvigSpellingCorrector)
**با استفاده از کتابخانه ی PyEnchant**
روش دیگر استفاده از کتابخانه‌ی PyEnchant است. این کتابخانه جهت خطایابی املایی توسط زبان برنامه‌نویسی پایتون ، مورد استفاده قرار می‌گیرد. تعداد زیادی کد باز متن دیگر جهت خطایابی وجود دارند اما این کتابخانه از لحاظ کارایی و دقت بسیار خوب عمل می‌کند. برای استفاده از آن باید PyEnchant و Encant را نصب کنید. تابع check() صحیح بودن کلمه را بررسی می‌کند و تابع suggest() لیستی از کلمات درست پیشنهادی را باز می‌گرداند.
برای ارزیابی از مجموعه داده‌ای که در روش قبل توسط Peter Norvig جمع آوری شده بود، استفاده می‌کنیم.
لینک github:
[پیوند](https://github.com/shahiiin/SpellCorrectorPyEnchant)
# بهبود نتایج و تکمیل گزارش
در این فاز به بهبود نتایج و تکملیل گزارش می‌پردازیم.
برای بهینه‌سازی می‌توانیم از الگوریتم بهتر و سریعتر “تصحیح خطا توسط حذف متقارن(FAROO)” که توسط Wolf Garbe ارایه شده است بپرازیم[14]. این روش نیز همانند روش های قبلی، بر پایه‌ی کمترین فاصله‌ی تصحیح (Damerau-Levenshtein distance) بنا شده است. به هنگام بررسی یک کلمه اگر کمترین فاصله‌ی تصحیح برای آن صفر باشد، املای آن کلمه درست است. در غیر این صورت از بین کلمات موجود در لغت‌نامه‌ی ذخیره شده،پیشنهادهایی ارایه میشود. تفاوت الگوریتم فوق با الگوریتم‌های قبلی در نحوه‌ی جستوجوی کلمات لغت‌نامه، برای پیدا کردن کلمه با کمترین فاصله‌ی تصحیح از کلمه‌ی خطا می‌باشد.
سه روش برای این کار وجود دارد:
# روش ساده ( Naive approach )
در این روش فاصله‌ی تصحیح کلمه‌ی ورودی کاربر از تمام کلمات لغت‌نامه محاسبه میشود و کلمه با کمترین فاصله‌ی تصحیح پیشنهاد داده میشود. این روش جستوجو بسیار کند و هزینه‌بر است. [13]
# روش Peter Norvig
روش استفاده شده توسط Peter Norvig بدین شکل بود که تمام کلمات به فاصله‌ی تصحیح کمتر از ۲، از روی کلمه‌ی ورودی ساخته می‌شد و سپس این کلمات با کلمات لغت‌نامه مقایسه می‌شدند. برای کلمه‌ای به طول n، الفبایی به اندازه‌ی a و فاصله‌ی تصحیح ۱، در مجموع 2n+2an+a-1 کلمه ساخته میشود(توسط جابجایی،حذف حرف اضافه،جانشینی و درج حرف اضافی).[11]
# روش تصحیح خطا توسط حذف متقارن(FAROO)
و اما روش خذف متقارن بدین شکل عمل می‌کند که ابتدا در مرحله‌ی به اصطلاح 'قبل از محاسبه(pre-calculation step)'، برای هر کلمه‌ی لغت‌نامه، کلمات به فاصله‌ی تصحیح کمتر از ۲(فقط توسط حذف حرف اضافه) را محاسبه کرده و به همراه کلمه، در لغت‌نامه ذخیره می‌کند. حال برای انجام عمل تصحیح و ارایه‌ی پیشنهاد، از روی کلمه‌ی وارد شده توسط کاربر به همین شکل کلمات به فاصله‌ی تصحیح کمتر از ۲ از آن ساخته شده و در لغت‌نامه جستوجو میشوند. برای کلمه‌ای به طول n، الفبایی به اندازه‌ی a و فاصله‌ی تصحیح ۱، فقط n کلمه که توسط حذف به دست آمده‌اند، خواهیم داشت. هزینه‌ی این روش ذخیره سازی تعداد بیشتری کلمه در لغت‌نامه است.
در عمل ۴ نوع مقایسه وجود دارد:
۱) کلمه‌ی لغت‌نامه با کلمه‌ی ورودی
۲) کلمه‌ی لغت‌نامه بعد از عمل خذف با کلمه‌ی ورودی
۳) کلمه‌ی لغت‌نامه با کلمه‌ی ورودی بعد از عمل حذف
۴) کلمه‌ی لغت‌نامه بعد از عمل خذف با کلمه‌ی ورودی بعد از عمل حذف
بدین ترتیب در این روش فقط از حذف حروف اضافه, استفاده می شود. در واقع کلماتی که با جایگزینی، جانشینی و یا درج در کلمه‌ی ورودی به دست می‌آیند, توسط حذف حروف اضافه در کلمات لغت‌نامه به دست می‌آیند.
پیاده‌سازی روش فوق به صورت متن‌باز در لینک مقابل وجود دارد. [پیوند](https://github.com/wolfgarbe/symspell)
مقایسه بین روش FAROO و روش Peter Norvig:
# کارهای آینده
بررسی روش‌های وابسته به متن و پیاده سازی آنها.
# مراجع
1) English Spelling and the Computer published by Longman, 1996
2) K. Kukich, “Techniques for automatically correcting words in text,” ACM Computing Surveys, vol. 24, pp. 378-439, 1992.
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.
5) D. E. Knuth, “The Art of Programming Vol. 3, Sorting and Searching,” Addison-Wesley, Reading 1973.
6) F. J. Damerau, “A technique for computer detection and correction of spelling errors,” Commun ACM 7, 3 (Mar.), 1964, pp. 171-176.
G. K. Zipf, “The Psycho-Biology of Language,” Houghton Mifflin, Boston, 1935.
7) E. M. Riseman, and A. R. Hanson, “A contextual postprocessing system for error correction using binary n-grams,” IEEE Trans. Comput. C-23, (May), 480-493, 1974.
8) A. V. Aho, “Algorithms for finding patterns in strings,” in Handbook of Theroretical Computer Science, J. Van Leeuwen, Ed. Elsevier Science Publishers, 1990.
9) M. K. Odell, and R. C. Russell, U.S Patent Number 1261167, 1918.
10) K. Atkinson, “Gnu aspell,” In Available at http://aspell.net, 2009.
11) How to Write a Spelling Corrector by Peter Norvig [پیوند](http://norvig.com/spell-correct.html)
12) PyEnchant Library [پیوند](http://pythonhosted.org/pyenchant/)
13) [Christopher D. Manning, Prabhakar Raghavan & Hinrich Schütze: Introduction to Information Retrieval.](http://nlp.stanford.edu/IR-book/html/htmledition/edit-distance-1.html)
14) [Improved Edit Distance Based Spelling Correction](http://blog.faroo.com/2012/06/07/improved-edit-distance-based-spelling-correction/)
# پیوندهای مفید
+ [تمرین خطایابی املایی درس پردازش زبان طبیعی به همراه داده‌های یادگیری](http://www.cs.indiana.edu/~alexr/nlpclass_2012/hw3.html)
+ [روشی جدید در خطایابی املایی در زبان فارسی](http://www.cs.columbia.edu/~rasooli/papers/AnewapproachforPersianspellchecking.pdf)
+ [خطایابی املایی در پروژه ویراستیار](http://www.virastyar.ir/content/%D8%AE%D8%B7%D8%A7%DB%8C%D8%A7%D8%A8%DB%8C-%D8%A7%D9%85%D9%84%D8%A7%DB%8C%DB%8C)
+ [اصول و مبانی خطایابی املایی، پروژه درس هوش مصنوعی، دانشگاه علم و صنعت، ۱۳۸۸](http://bayanbox.ir/id/4167494434444049956?download)
+ [Natual Language Processing Course - Spelling Correction](https://class.coursera.org/nlp/lecture/preview)
+ [Improved Edit Distance Based Spelling Correction](http://blog.faroo.com/2012/06/07/improved-edit-distance-based-spelling-correction/)