زیاد پیش آمده که وقتی نوشته‌ای را تایپ می‌کنیم، حرفی را از قلم بیاندازیم و یا اضافه قرار دهیم. یا بدتر اینکه املایش را درست ندانیم و «ض» را «ظ» بنوسیم. در این پروژه شما باید خطاهای نوشته را پیدا و اصلاح کنید. [این راهنما](http://norvig.com/spell-correct.html) برای شروع خوب است. # مقدمه  **چکیده** در این پروژه ابتدا به بیان شرح مسئله و کارهای مرتبط با خطایابی املایی می پردازیم و تکنیک ها و چالش های پیشرو را مورد بررسی قرار می دهیم. انواع الگوریتم ها و مدل سازی ها را بیان می کنیم و سپس توسط زبان برنامه نویسی پایتون به پیاده سازی می پردازیم. این خطایاب پس از خطایابی واژگان،سعی می کند پیشنهادهای صحیح را به کاربران ارائه دهد. مشکلات و چالش های پیشرو در زمینه ی پیشنهاددهی به کاربران مورد بررسی قرار خواهد گرفت و روش های مختلف پیاده سازی خواهد شد. سپس به ارزیابی سیستم خواهیم پرداخت و روش های موجود را با هم مقایسه خواهیم کرد.  **مقدمه** مسئله ی پیدا کردن خطا های املایی توسط ماشین از جمله مسائل مورد بحث در پردازش زبان های طبیعی است. پس از به وجود آمدن علوم رایانه ای و مسائل هوش مصنوعی ، پردازش زبان های طبیعی مورد توجه بسیار قرار گرفت. به طور کلی **پردازش زبان‌های طبیعی** یکی از زیرشاخه‌های بااهمیت در حوزه گسترده هوش مصنوعی ، و نیز در دانش زبان شناسی است. تلاش عمده در این زمینه ماشینی کردن فرایند درک و برداشت مفاهیم بیان گردیده با یک زبان طبیعی انسانی توسط ماشین است. با فراگیر شدن پدیده اینترنت و گسترش متون الکترونیکی این علم اهمّیت ویژه ای پیدا کرده است که از جمله نتایج آن می توان به استخراج اطلاعاتی خاص از یک متن، ترجمه یک متن به زبانی دیگر، یافتن مستنداتی خاص در یک پایگاه داده نوشتاری ، سیستم های پرسش و پاسخ انسان با کامپیوتر، سرویس های اتوماتیک ارتباط با مشتری از طریق تلفن و سیستم های کنترلی توسط صدا اشاره کرد. همچنین پیاده سازی انواع خطایاب های املایی ، مترجمین هوشمند ماشینی، نرم افزارهای پردازش و تشخیص گفتار و نرم افزارهای تبدیل متن به صدا از جمله تلاش ها در این زمینه بوده است. در رابطه با خطایابی املایی ، مسئله ی تشخیص خودکار و تصحیح خطاهای املایی موجود در انواع متن از دهه ی ۶۰ میلادی مطرح بوده است و تا به امروز نیز پیدا کردن الگوریتم ها ی بهینه برای این کار مورد توجه بوده است چراکه طبق آخرین بررسی ها در مجموع حدود ۲۶٪ از پرس و جو های وب شامل انواع غلط املایی می شوند. خطایاب های املایی در تصحیح و کمک به جستجوی سریعتر و دقیقتر در اینترنت، تصحیح خطاهای ناشی از تبدیل تصویر به متن،صرفه جویی در وقت و هزینه ، ابزارهای جانبی برای ویرایشگرهای متنی، ابزار پیش پردازنده در پردازش زبان های طبیعی ، واسط های بازیابی اطلاعات، تبدیل گفتار به متن و کامپیوترهای مبتنی بر قلم و … کاربرد های بسیاری دارند. همچنین امروزه حجم بسیار زیادی از اطلاعات و متون فارسـی توسـط رایانـه ها تولید میشوند. فرایند تولید و ورود اطلاعات، به ویژه متن، هیچ گاه عـاری از خطـا نبـوده و هزینه های بسیاری برای یافتن و برطرف ساختن این خطاها صرف میشود که این امر نیاز به خطایاب را بیشتر نمایان می کند.  # کارهای مرتبط **خطایاب املایی** به طور کلی خطایابی املایی شامل بررسی یک متن ، مشخص کردن کلمه یا کلمات اشتباه و تصحیح آن ها می شود. بعضی از خطایاب های امروزی به جای ارائه یک تصحیح، لیستی از پیشنهادات را برای کاربر نمایش می دهند. بعضی از خطایاب های قدیمی تر فقط کلمه ی شامل غلط املایی را مشخص می کنند و پیشنهادی برای املای صحیح ارائه نمی کنند چراکه عمل تصحیح، به مراتب پیچیده تر و نیازمند پردازش بیشتری است. خطایاب ها برای پیدا کردن خطاها از الگو های مشخصی استفاده میکنند به طوریکه دسته بندی های مختلفی برای انواع خطاها وجود دارد و می توان توسط مدل سازی های مختلف زبان ها آنها را شناسایی کرد، که جلوتر به آنها می پردازیم. **انواع خطاهای املایی** خطاهای املایی را می توان به دسته های مختلفی تقسیم بندی کرد. به طور کلی دو دسته ی : ۱) خطاهای غیر لغت ( Non-word Errors ) ۲) خطاهای لغات واقعی ( Real-word Errors ) غیر لغات ها همانطور که از نام آنها پیداست کلماتی هستند که معنایی ندارند و در فرهنگ لغات وجود ندارند. معمولا عمل تصحیح آنها با اضافه یا کم کردن و یا با تغییر یک یا چند حرف انجام می شود. برای مثال اگر کاربر کلمه ی (فقث) را وارد کرده باشد می توان حدس زد که کلمه ی درست (فقط) می باشد. خطاهای لغات واقعی خود شامل خطاهای چاپی(Typographical errors) ، خطاهای شناختی (Cognitive errors) و خطاهای آوایی (Phonetic) می شوند. در خطاهای لغات واقعی ممکن است کلمه ی نوشته شده از نظر املایی درست باشد و در فرهنگ لغات هم موجود باشد اما کاربرد آن در متن نوشته شده اشتباه باشد. در خطاهای چاپی فرض بر این است که کاربر املای درست را می داند اما به دلایلی خطا انجام می دهد (برای مثال دیو به جای دیر و یا اسلام به جای سلام). خطاهای چاپی شامل خطاهای ناشی ازعادات کاربر و یا نزدیکی نوشتاری حروف است. در خطاهای شناختی کاربر تسلط کافی به زبان را ندارد و معنای کلمه ی درست با کلمه ی وارد شده متفاوت است (برای مثال غصه به جای قصه و یا توجیح به جای توجیه ). خطاهای آوایی همانند خطاهای شناختی هستند با این تفاوت که کلمه ی خطا از لحاظ آوایی مشابه کلمه ی صحیح مورد نظر است (برای مثال اصلاح به جای اسلاح ) مورد **الگوی خطاهای اصلی :** در تحقیقاتی که در این زمینه انجام شده است مشخص شده که حدود ۸۰٪ از کل خطاهای املایی موجود در یک نوشتار شامل یکی از موارد زیر هستند : ۱)خطای درج اضافی حرف : اضافه شدن یک یا چند حرف به کلمه ی درست. ۲)خطای حذف حرف : پاک شدن یک یا چند حرف از کلمه ی درست. ۳)خطای جانشینی : استفاده از یک حرف به جای حرفی دیگر . ۴)خطای جابجایی : جابجایی دو حرف با هم. ۵)خطای فاصله : چسبیدن دو کلمه درست بدون فاصله به هم. خطایاب ها با کمک این الگو های خطا و مدل سازی زبان ها ، می توانند به خطایابی بپردازند. **تشخیص خطا** **۱) تشخیص خطاهای غیر لغت :** **استفاده از لغت نامه** ساده ترین و پراستفاده ترین روش برای تشخیص خطاهای غیر لغت ، استفاده از لغت نامه ها (Dictionaries) است. در این روش کلمات درست در یک لغت نامه ذخیره می شوند. سپس خطایاب تک تک کلمات وارد شده را در داخل لغت نامه جست و جو می کند و اگر همانند آن کلمه پیدا نشود ، خطایاب یک خطا را تشخیص داده است. بدین ترتیب هرچه لغت نامه بزرگتر باشد ، بهتر است. اما در این روش مسئله ی زمان پاسخگویی و همچنین فضای ذخیره شده نکات مهمی هستند. معمولا تعداد کلمات لغت نامه ها حدود ۲۵۰ هزار لغات یا بیشتر می باشد. با بزرگتر شدن لغت نامه زمان پاسخگویی سیستم بسیار بالا می رود. همچنین به فضای ذخیره سازی زیادی نیاز خواهیم داشت. برای حل این مشکل روش های مختلفی مثل مراجعه به لغت نامه های کارا، تقسیم لغت نامه ها و روش های مبتنی بر پردازش ریخت شناسی وجود دارند. **بهینه سازی روش لغت نامه** برای مثال یک روش این است که فقط ریشه ی کلمات را ذخیره کنیم (ریشه یابی). در این روش توسط الگوریتم ها و مجموعه قوانین خاص هر زبان پیشوند ها و پسوند های کلمات را حذف می کنیم. به هنگام جست و جوی خطا نیز همین کار را بر روی کلماتی که کاربر وارد کرده انجام می دهیم وریشه های ایجاد شده را با ریشه های ذخیره شده در لغت نامه مقایسه می کنیم. بدین ترتیب فضای اشغال شده توسط لغت نامه کمتر شده و زمان پاسخ گویی نیز بسیار سریعتر می شود. مشکل این روش این است که ممکن است بعضی خطاها نادیده گرفته شوند چراکه امکان دارد کلمه ی وارد شده توسط کاربر ریشه ی درستی داشته باشد ولی به همراه پسوند یا پیشوند وارد شده ، حاوی غلط املایی باشد. روش دیگر استفاده از تابع درهم (Hash Function) در ذخیره سازی است. در این روش برای هر کلمه ی لغت نامه یک آدرس درهم در نظر می گیریم. این آدرس با اعمال تابع درهم بر روی هر یک از حروف الفبا به دست می آید. برای مثال به حرف الف عدد ۱، ب عدد ۲ پ عدد ۳ و به همین ترتیب به تمام حروف یک عدد را نسبت می دهیم. سپس با استفاده از تابع درهم یعنی اعمال محاسبات ریاضی بر روی اعداد حروف هر کلمه ، به یک عدد برای هر کلمه می رسیم. بدین ترتیب به جای ذخیره ی هر کلمه ، این عدد را در حافظه ذخیره می کنیم. هنگامی که کاربر یک رشته ی ورودی را وارد می کند، آدرس درهم آن محاسبه می شود و با مراجعه به جدول درهم از پیش ساخته شده و دریافت کلمه ی ذخیره شده در آن مکان اگر کلمات یکی نبودند یا کلمه ای وجود نداشت، غلط املایی تشخیص داده می شود. این روش در واقع نگاشت بیت به بیت (BitMap) می باشد. بدین ترتیب سرعت دسترسی به اطلاعات و زمان پاسخگویی بسیار سریعتر می شود. به دلیل خاصیت دسترسی مستقیم نیازی به مقایسه های زیادی نیست. همچنین فضای ذخیره سازی نیز کاهش می یابد. مهمترین چالش در این روش داشتن تابع درهم مناسب است چراکه هر کلمه لازم است که آدرس منحصر به فردی داشته باشد. پیدا کردن تابع درهمی مناسب برای تولید این جدول درهم به گونه ای که کلمات تکراری تولید نکند و همچنین سریع بودن تابع مشکل اصلی این روش است. البته روش های مختلفی برای تولید چنین توابعی وجود دارد. **استفاده از تحلیل چند نگاشت (N-grams)** **** روش دیگر برای تشخیص خطاهای غیر لغت استفاده از تحلیل چند نگاشت است. چندنگاشت ها زیر دنباله های چند حرفی از رشته های کاراکتری هستند. برای مثال یک، دو، و یا سه حرفی. برای مثال، زیر نگاشت ۳ حرفی کلمه ی “آفتاب” شامل ‘آفت’ ، ‘فتا’ و ‘تاب’ ، می شود. دو روش کلی برای تحلیل چند نگاشت وجود دارد. در یکی از این روش ها به طور غیر مستقیم از لغت نامه استفاده می کنیم بدین ترتیب که برای مثال ابتدا سه نگاشت های تمام کلمات لغت نامه را ذخیره می کنیم. حال هنگامی که کاربر رشته ای را وارد می کند چند نگاشت های آن نیز به همان روش قبلی ساخته می شوند و با چند نگاشت های لغت نامه مقایسه می شوند. عدم وجود آن ها در چند نگاشت های لغت نامه، مشخص کننده ی خطاهای احتمالی است.در این روش معمولاً به یک لغت نامه برای نگه داری از پیش جدول چندنگاشت ها نیازاست. در روش های مبتنی بر تحلیل چندنگاشت ممکن است تعداد قابل توجهی از خطاها تشخیص داده نشوند چراکه بسیاری از کلمات حاوی خطا، شامل چند نگاشت های غیرمعمول نمی شوند اما در تشخیص خطاهایی که توسط دستگاههای تشخیص نوری حروف (Optical Character Recognition) خطایابی می شوند ، خوب عمل می کنند. در روش دیگر برای تحلیل چند نگاشت ها از لغت نامه استفاده نمی شود. همانند روش قبل ابتدا چند نگاشت های متن ورودی توسط کاربر مشخص می شوند اما این بار تعداد تکرار آن ها در متن اهمیت دارد. برای مثال سه نگاشت “پخز” که فقط یکبار در متن تکرار شده باشد،احتمال خطا بودن آن زیاد است. اما “هست” که بسیار بیشتر استفاده شده است احتمال خطا بودن آن ناچیز است. همانند روش قبل احتمال تشخیص ندادن خطا های عادی وجود دارد اما این روش در تشخیص خطاهای تایپی بسیار کارا عمل می کند.همچنین مزیت دیگر آن این است که برای هر زبانی می توان از این روش استفاده کرد. جدول های چند نگاشت می توانند با روش های مختلفی ساخته شوند. ساده ترین روش استفاده از دونگاشت دودویی است که یک آرایه ی دو بعدی است که تمام ترکیبهای دوتایی حروف را در بر می گیرد. هر خانه ی آن شامل ۱ اگر آن دونگاشت در متن ما حداقل یکبار تکرار شده باشد یا ۰ است. یک سه نگاشت دودویی به همین شکل ولی یک آرایه ی سه بعدی است. این آرایه ها را چند نگاشت های دودویی غیر وابسته به موقعیت می نامند. بدین معنا که محل چندنگاشت را در کلمه مشخص نمی کنند. با اختصاص فضای بیشتر به جدول چند نگاشت می توان موقعیت چندنگاشت را هم ذخیره کرد. این کار باعث بهبود کارایی روش های چند نگاشت ها می شود چراکه می توان محل آن ها در کلمه را نیز مقایسه کرد. به طور کلی تحلیل چند نگاشتی در بعضی زمینه ها مثل تشخیص نوری حروف و خطاهای تایپی مفید است، ولی برای خطاهای تولید شده توسط انسان دقت کمتری دارد. به همین خاطر بیشتر روش های تصحیح خطای املایی بر اساس مراجعه به لغتنامه می باشند. **خطای حرف اول** عموما خطا در حرف اول کلمات رخ نمی دهد. بدین ترتیب می توانیم لغتنامه ها را بر اساس حرف اول تقسیم بندی کنیم تا زمان مراجعه به لغت نامه و زمان پاسخ گویی کاهش یابند.مشکل این دسته بندی این است که در این صورت دسته ای از خطاها(خطاهای حرف اول) توسط سیستم ما تشخیص داده نمی شود. **طول کلمه** طبق تحقیقات انجام شده، در بسیاری از مواقع طول کلمه ی خطا در فاصله ی دوتایی از طول کلمه ی صحیح است. این موضوع باعث می شد محققان لغتنامه ها را بر اساس طول کلمات به چند دسته تقسیم کنند تا زمان جستجو کاهش یابد. با توجه به قانون زیپف در یک نوشته کلمات کوتاه تر تعداد تکرارهای بیشتری دارند. همچنین کلمات با تکرار بیشتر همسایه های تک خطایی بیشتری دارند. ولی معمولاً کلمات کوتاه کمتر اشتباه نوشته می شوند. در ضمن هرچه کلمه کوتاه تر باشد متن درون کلمه ای کمتری در اختیار ما قرار می دهد و کار تصحیح سخت تر می شود. **۲) تشخیص خطای لغات واقعی :** از جمله ایرادات خطایاب ها می توان به تشخیص دادن کلمه ی درست به عنوان خطا و یا تشخیص ندادن بعضی خطاها اشاره کرد. دلیل ایراد نوع اول ، وجود کلمات مبهم و اسم های خاص در متن وارد شده می باشد. می توان با فراهم کردن لغت نامه ی بزرگتر برای خطایاب و یا استفاده از لغت نامه ی تخصصی برای انواع مختلف متن (برای مثال پزشکی) درصد این ایراد را کاهش داد. اما برای ایراد دوم راه حل خاصی وجود ندارد چراکه تعداد اسم های خاص بسیار زیاد است. بسیاری از خطایاب ها امکانی را فراهم می کنند که کاربر اسم خاص را برای خطایاب مشخص کند تا بعد از اولین باری که خطا در نظر گرفته می شود خطایاب دوباره آن را خطا اعلام نکند. ایراد نوع دوم در مقابل ایراد اول یعنی تشخیص اشتباه بسیار مهم تر است چراکه کاربر همواره می تواند خطا را نادیده بگیرد ، اما تشخیص ندادن کلمه ی خطا نگران کننده است چراکه کاربر انتظار متنی بدون خطا را دارد. این مشکل با افزایش سایز لغت نامه برای کاهش ریسک ایراد نوع اول ، بیشتر نیز می شود چراکه با افزایش لغات مبهم لغت نامه امکان تشخیص ندادن خطاهای لغات واقعی بیشتر می شود. خطایاب های کمی هستند که می توانند خطای لغات واقعی را تشخیص دهند. ۳ پروژه در این زمینه قابل ذکر هستند. اولی سیستمی با نام CRITIQUE است که توسط IBM ساخته شده است. در این برنامه متن از لحاظ نوشتاری ، دستور زبان و قالب نوشتاری ، بررسی می شود.سیستم توسط گرامری که برای آن طراحی شده است ، متن را بررسی می کند و نقش کلمات شامل اسم ، قید ، افعال اصلی و کمکی و غیره را مشخص می کند. اگر جمله ای با قواعد گرامر تعریف شده همخوانی نداشته باشد ، آن قاعده کنار گذاشته می شود و دوباره جمله بررسی می شود. این کار تا زمانی ادامه پیدا می کند که جمله مورد قبول واقع شود. حال سیستم با دانستن قواعد کنار گذاشته شده ، می تواند تشخیص دهد چه قسمتی از دستور زبان مشکل داشته است. پروژه ی دوم نیز همانند سیستم اولی بر پایه قواعد نحوی است. در ابتدا این پروژه در دانشگاه لنکستر فقط برای مشخص کردن نقش کلمات در جمله بود اما بعدها به خطایاب املایی تبدیل شد. سیستم ابتدا با مراجعه به یک لغت نامه نقش کلمات را مشخص می کند. لغت نامه بر اساس نقش کلمات مرتب شده است (برای مثال لغت نامه ای برای افعال). همچنین سیستم حاوی جدولی است که جایگاه و ترتیب قرار گرفتن نقش های مختلف در جمله را مشخص می کند. وقتی کاربر متنی را وارد می کند سیستم ترتیب قرار گرفتن کلمات با نقش های دستوری مختلف را بررسی می کند و دنباله ای که احتمال درست بودن آن کم است را ، مشخص می کند. بدین ترتیب سیستم حدس هایی رو برای پیشنهاد کلمه ی درست ارایه می دهد. پروژه ی بعدی مدل پیشرفته تر سیستم قبلی بود که باز هم توسط IMB انجام شد. در این سیستم احتمال قرار گرفتن ۲ کلمه در کنار هم (و یا احتمال های دنباله ی ۳ تایی کلمات) محاسبه می شوند. سپس عمل تشخیص و تصحیح با توجه به این احتمالات انجام می شوند. **تصحیح خطا** برای تصحیح ، خطایاب باید کلمه ی مورد نظر کاربر را حدس بزند و همچنین قادر به نوشتن املا صحیح آن باشد. تولید املا درست سخت نیست چراکه همانطور که توضیح داده شد روش ها ی مختلفی برای ذخیره ی املا ی درست (از جمله ذخیره به صورت لغت نامه) وجود دارد. اما قسمت سخت تر ارایه ی پیشنهاد مناسب است. به طور کلی کامپیوتر در تصحیح کلمات کوتاه تر کار سخت تری دارد تا کلمات بلند چراکه انتخاب ها برای کلمات کوتاه تر بسیار بیشتر است. به دلیل حجیم بودن لغت نامه ها خطایاب برای عمل تصحیح باید قادر باشد فقط بخشی از لغت نامه که احتمال وجود کلمه ی درست در آن بیشتر است را ، ابتدا بررسی کند. این کار با توجه به توضیحی که در قسمت خطای حرف اول دادیم و در نظر گرفتن اینکه اکثر خطاها یکی از انواع الگوی خطاهای اصلی هستند ، انجام می شود. یعنی بیشتر خطاها از نوع خطای درج اضافی حرف ، خطای حذف حرف ، خطای جانشینی و یا خطای جابجایی هستند که معمولا با تغییر فقط یک حرف ، می توانیم به کلمه ی درست برسیم . همچنین حرف اول عموما صحیح است و بدین ترتیب لغت نامه بر اساس آن می تواند محدوده ی جست و جوی خود را مشخص کند و کلماتی که به فاصله ی یک یا چند حرف از کلمه ی ورودی هستند را بررسی کند. طبق تحقیقات انجام شده ۸۰٪ از خطاها به فاصله ی یک حرف از کلمه ی درست هستند. فاصله در این مبحث به تعداد عملیات های تصحیح مورد نیاز گفته میشود. برای تصحیح این خطاها می توان از الگوریتم ‘کمترین فاصله ی تصحیح’ استفاده کرد. در این الگوریتم برای رسیدن به کلمه ی درست می توان از درج یک حرف ، حذف حرف و جا به جایی استفاده کرد . هر کدام از این اعمال را می توان چند بار انجام داد تا کلمه ی درست تولید شود. **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# در مثال بالا ۶ شباهت را مشاهده می کنیم که می تواند حدس بسیار مناسبی برای تصحیح باشد. # آزمایش‌ها# کارهای آینده # مراجع English Spelling and the Computer published by Longman, 1996 K. Kukich, “Techniques for automatically correcting words in text,” ACM Computing Surveys, vol. 24, pp. 378-439, 1992. 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. D. E. Knuth, “The Art of Programming Vol. 3, Sorting and Searching,” Addison-Wesley, Reading 1973. 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. 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. A. V. Aho, “Algorithms for finding patterns in strings,” in Handbook of Theroretical Computer Science, J. Van Leeuwen, Ed. Elsevier Science Publishers, 1990. M. K. Odell, and R. C. Russell, U.S Patent Number 1261167, 1918. K. Atkinson, “Gnu aspell,” In Available at http://aspell.net, 2009.در این بخش به توضیح روش های استفاده شده در فاز دوم و اریزیابی های انجام شده می پردازیم. **استفاده از مدل های چند نگاشت برای خطایابی املایی** **استفاده از مدل زبان** در اولین روش برای پیاده سازی, از مجموعه کد و داده های 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)  # کارهای آینده # مراجع 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/) # پیوندهای مفید + [تمرین خطایابی املایی درس پردازش زبان طبیعی به همراه داده‌های یادگیری](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/)