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

از آنجا که علی فرد تنبلیست تصمیم می گیرد تا یک مدل احتمالاتی برای تصحیح نوشتار (Auto correct) ایجاد کند. به این ترتیب دیگر نیاز به تمرین ندارد. او برای ساختن مدل خود از متن‌های شکسپیر کمک می گیرد!! متنی که در اختیار شما قرار گرفته حدودا شامل ۶۱۱۶ کلمه‌ی متفاوت از شکسپیر کبیر است.

مدل احتمالاتی تصحیح خودکار کلمات

علی ابتدا همه‌ی کلمات را lower case کرده و کلمات یکتا را جدا می کند. سپس سه تابع زیر را برای ویرایش کلمات پیاده می‌کند.این سه تابع سه روش برای تصحیح یک کلمه هستند: ‍‍‍

• delete_letter: همه‌ی جایگشت کلماتی (با معنی و بی معنی) که با حذف یک حرف از کلمه تشکیل می‌شود را باز میگرداند.
• replace_letter: همه‌ی جایگشت کلماتی (با معنی و بی معنی) که با جایگزین کردن یک حرف از کلمه تشکیل می‌شود را باز میگرداند.
• insert_letter:همه‌ی کلماتی (با معنی و بی معنی) که با اضافه کردن یک حرف به کلمه تشکیل می‌شود را باز میگرداند.

مثلا به ازای ورودی ate به تابع delete_letter خروجی همه‌ی جایگشت‌های حذف یک حرف از کلمه یعنی te,ae,at خواهد بود.

>>> delete_letter('ate')
['at','ae','te']

به ازای ورودی at به تابع replace_letter خروجی همه‌ی جایگشت‌های جایگزینی یکی از حروف هستند. bt,ct,dt,...,zt,aa,ab,ac,...,az

>>> replace_letter('at')
['bt','ct','dt',...,'zt','aa','ab','ac',...,'az']

به ازای ورودی at به تابع insert_letter خروجی همه‌ی جایگشت‌های اضافه شدن یک حرف به این کلمه است. در واقع کلمات جدید به یکی از فرمت‌های xat,axt,atx هستند که x می‌تواند هر یک از حروف الفبا انگلیسی باشد.

دقت کنید خروجی این توابع همه‌ی جایگشت‌ها به جز خود کلمه هستند .با در اختیار داشتن این سه تابع علی می‌تواند به ازای هر کلمه‌ی ورودی همه‌ی کلماتی (با معنی و بی‌معنی) که از طریق اعمال یکی از سه روش بالا به وجود می‌آیند را تولید کند. مثلا در تابع زیر همه‌ی جایگشت‌های یک کلمه که از طریق روش‌های بالا ممکن است تولید شوند، به عنوان خروجی به دست می‌آید.

def edit_one_letter(word):
 """
    Input:
        word: the string/word for which we will generate all possible words that are one edit away.
    Output:
        edit_one_set: a set of words with one possible edit. Please return a set. and not a list.
    """
    edit_one_set = set()
    edit_one_set.update(delete_letter(word))
    edit_one_set.update(replace_letter(word))
    edit_one_set.update(insert_letter(word))
    return edit_one_set

تابع edit_two_letters نیز همه‌ی جایگشت‌های ممکن با استفاده از دقیقا دو مورد از توابع ویرایش متن را خروجی می‌دهد. یعنی خروجی حاصل اعمال دو تا از توابع ویرایش بر کلمه است.

برای تصحیح خودکار یک کلمه، ابتدا همه‌ی کلماتی که می‌توان آن‌ها را با یک ویرایش و یا دو ویرایش از کلمه‌ی ورودی ساخت را مشخص می‌کنیم. سپس کلماتی که در متن شکسپیر وجود ندارند را به عنوان کلمات بی معنی حذف می‌کنیم. در این فرایند استفاده از توابع insert و delete هر یک هزینه برابر ۱ واحد دارد. استفاده از replace اما هزینه برابر ۲ واحد دارد. بنابراین کلمات ساخته شده از کلمه‌ی اصلی هر یک هزینه‌ای دارند(این هزینه عددی بین ۱ تا ۴ خواهد بود!). بعد کلمه‌ای که با کمترین هزینه ویرایش از روی کلمه‌ی اصلی ساخته شده را به عنوان پاسخ صحیح انتخاب می‌کنیم. اگر خروجی چند کلمه با هزینه ویرایش مینیمم خروجی داد، کلمه‌ای را انتخاب می‌کنیم که احتمال حضورش در متن بیشتر است. احتمال حضور یک کلمه یعنی تعداد دفعات حضور کلمه در متن تقسیم بر تعداد کل کلمات. به این روش ایجاد شباهت بین کلمات minimum edit distance می‌گویند.

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

فایل پروژه را از این لینک دانلود کنید. در پروژه یک فایل submit.py وجود دارد. ما تابع autoCorrect از این فایل را در داوری صدا می زنیم. این تابع یک کلمه را به عنوان ورودی گرفته و کلمه‌ی با املای درست با شرایط ذکر شده را پس می‌دهد.

>>> autoCorrect('flw')
'flow'

در نهایت فقط فایل submit.py را آپلود کنید.