زیاد پیش آمده که وقتی نوشته‌ای را تایپ می‌کنیم، حرفی را از قلم بیاندازیم و یا اضافه قرار دهیم. یا بدتر اینکه املایش را درست ندانیم و «ض» را «ظ» بنوسیم. در این پروژه شما باید خطاهای نوشته را پیدا و اصلاح کنید. [این راهنما](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 حروف صدادار حذف می
# مقدمه
**چکیده**
در این پروژه ابتدا به بیان شرح مسئله و کارهای مرتبط با خطایابی املایی می‌پردازیم و تکنیک‌ها و چالش‌های پیشرو را مورد بررسی قرار می‌دهیم. انواع الگوریتم‌ها و مدل‌سازی‌ها را بیان می‌کنیم و سپس توسط زبان برنامه‌نویسی پایتون به پیاده‌سازی می‌پردازیم. این خطایاب پس از خطایابی واژگان،سعی می‌کند پیشنهادهای صحیح را به کاربران ارائه دهد. مشکلات و چالش‌های پیشرو در زمینه‌ی پیشنهاددهی به کاربران مورد بررسی قرار خواهد گرفت و روش‌های مختلف پیاده‌سازی خواهد شد. سپس به ارزیابی سیستم خواهیم پرداخت و روش‌های موجود را با هم مقایسه خواهیم کرد.
**مقدمه**
مسئله‌ی پیدا کردن خطاهای املایی توسط ماشین از جمله مسائل مورد بحث در پردازش زبان‌های طبیعی است. پس از به وجود آمدن علوم رایانه‌ای و مسائل هوش مصنوعی ، پردازش زبان‌های طبیعی مورد توجه بسیار قرار گرفت. به طور کلی **پردازش زبان‌های طبیعی** یکی از زیرشاخه‌های بااهمیت در حوزه گسترده هوش مصنوعی ، و نیز در دانش زبان‌شناسی است. تلاش عمده در این زمینه ماشینی کردن فرایند درک و برداشت مفاهیم بیان گردیده با یک زبان طبیعی انسانی توسط ماشین است. با فراگیر شدن پدیده اینترنت و گسترش متون الکترونیکی این علم اهمّیت ویژه‌ای پیدا کرده است که از جمله نتایج آن می‌توان به استخراج اطلاعاتی خاص از یک متن، ترجمه یک متن به زبانی دیگر، یافتن مستنداتی خاص در یک پایگاه داده نوشتاری ، سیستم های پرسش و پاسخ انسان با کامپیوتر، سرویس های اتوماتیک ارتباط با مشتری از طریق تلفن و سیستم های کنترلی توسط صدا اشاره کرد. همچنین پیاده‌سازی انواع خطایاب‌های املایی ، مترجمین هوشمند ماشینی، نرم افزارهای پردازش و تشخیص گفتار و نرم افزارهای تبدیل متن به صدا از جمله تلاش‌ها در این زمینه بوده است.
در رابطه با خطایابی املایی ، مسئله‌ی تشخیص خودکار و تصحیح خطاهای املایی موجود در انواع متن از دهه ی ۶۰ میلادی مطرح بوده است و تا به امروز نیز پیدا کردن الگوریتم ها ی بهینه برای این کار مورد توجه بوده است چراکه طبق آخرین بررسی‌ها در مجموع حدود ۲۶٪ از پرس و جو‌های وب شامل انواع غلط املایی می شوند. خطایاب‌های املایی در تصحیح و کمک به جستجوی سریعتر و دقیقتر در اینترنت، تصحیح خطاهای ناشی از تبدیل تصویر به متن،صرفه جویی در وقت و هزینه ، ابزارهای جانبی برای ویرایشگرهای متنی، ابزار پیش پردازنده در پردازش زبان‌های طبیعی ، واسط‌های بازیابی اطلاعات، تبدیل گفتار به متن و کامپیوترهای مبتنی بر قلم و … کاربرد‌های بسیاری دارند. همچنین امروزه حجم بسیار زیادی از اطلاعات و متون فارسـی توسـط رایانـه‌ها تولید میشوند. فرایند تولید و ورود اطلاعات، به ویژه متن، هیچ گاه عـاری از خطـا نبـوده و هزینه های بسیاری برای یافتن و برطرف ساختن این خطاها صرف میشود که این امر نیاز به خطایاب را بیشتر نمایان می کند.
# کارهای مرتبط
**خطایاب املایی**
به طور کلی خطایابی املایی شامل بررسی یک متن ، مشخص کردن کلمه یا کلمات اشتباه و تصحیح آن ها می شود. بعضی از خطایاب‌های امروزی به جای ارائه یک تصحیح، لیستی از پیشنهادات را برای کاربر نمایش می‌دهند. بعضی از خطایاب‌های قدیمی‌تر فقط کلمه‌ی شامل غلط املایی را مشخص میکنند و پیشنهادی برای املای صحیح ارائه نمی‌کنند چراکه عمل تصحیح، به مراتب پیچیده‌تر و نیازمند پردازش بیشتری است.
خطایاب‌ها برای پیدا کردن خطاها از الگوهای مشخصی استفاده میکنند به طوریکه دسته بندی‌های مختلفی برای انواع خطاها وجود دارد و می‌توان توسط مدل سازی‌های مختلف زبان‌ها آنها را شناسایی کرد، که جلوتر به آنها می‌پردازیم.
**انواع خطاهای املایی**
خطاهای املایی را می توان به دسته‌های مختلفی تقسیم‌بندی کرد.
به طور کلی دو دسته‌ی :
۱) خطاهای غیر لغت ( 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 جمع‌آوری شده است.
پوشه شوند
۵) خط فاصله‌ها حذف میشوند
۶) حرف اول به صورت بزرگ به همراه ۳ عدد اول نگه داشته میشوند.( اگر کمتر از ۳ عدد ساخته شده بود ، ۰ اضافه می‌کنیم )
برای مثال : (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)
# کارهای آینده‌ای از نوشته (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/)