برنامه محاسبه فاصله ویرایش – به زبان ساده

دو رشته str1 و str2 داده شده و عملیات بیان شده در زیر، روی رشته str1 قابل انجام است. هدف، پیدا کردن حداقل ویرایش‌های لازم برای تبدیل یک رشته (str1) به رشته دیگر (str2) است. در واقع، در ادامه روش نوشتن برنامه محاسبه فاصله ویرایش (Edit Distance) - برای مثال جهت تبدیل رشته «str1» به «str2» - آموزش داده خواهد شد. همچنین، پیاده‌سازی روش آموزش داده شده در زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «سی» (C)، «جاوا» (Java)، «پایتون ۳» (Python 3) و «پی‌اچ‌پی» (PHP) انجام شده است.

1. درج (Insert)
2. حذف (Remove)
3. جایگزینی (Replace)

همه اعمال بیان شده در بالا دارای هزینه یکسانی هستند. مثال زیر در این رابطه جالب توجه است.

Input:   str1 = "geek", str2 = "gesek"
Output:  1
We can convert str1 into str2 by inserting a 's'.

Input:   str1 = "cat", str2 = "cut"
Output:  1
We can convert str1 into str2 by replacing 'a' with 'u'.

Input:   str1 = "sunday", str2 = "saturday"
Output:  3
Last three and first characters are same.  We basically
need to convert "un" to "atur".  This can be done using
below three operations. 
Replace 'n' with 'r', insert t, insert a

محاسبه فاصله ویرایش به روش بازگشتی

ایده کلی برای حل این مسأله، پردازش همه کاراکترها یکی یکی با شروع از سمت راست یا چپ هر دو رشته است. در اینجا، پیمایش از سمت راست رشته آغاز می‌شود. دو احتمال برای هر جفت از کاراکترهای پیمایش شده وجود دارد.

m: Length of str1 (first string)
n: Length of str2 (second string)

اگر آخرین کاراکتر از دو رشته مشابه باشند، کار دیگری برای انجام دادن وجود ندارد. باید از آخرین کاراکتر صرف‌نظر کرد و محاسبه را برای ادامه رشته (رشته باقی‌مانده) انجام داد. بنابراین، بازگشت برای طول‌های m-1 و n-1 انجام می‌شود. در غیر این صورت (اگر آخرین کاراکتر دو رشته با یکدیگر مشابه نباشند)، همه عملیات روی str1 انجام می‌شود.

در واقع، هر سه عملیات روی آخرین کاراکتر از رشته اول در نظر گرفته می‌شود و حداقل هزینه برای هر سه عملیات به صورت بازگشتی محاسبه و کمینه (Minimum) سه مقدار حاصل شده محاسبه می‌شود.

• درج: بازگشت برای m تا n-1
• حذف: بازگشت برای m-1 و n
• جایگزینی: بازگشت از m-1 و n-1

در ادامه، پیاده‌سازی راهکار بازگشتی ساده بالا در زبان برنامه‌نویسی ++C انجام می‌شود.

برنامه محاسبه فاصله ویرایش در ++C به روش بازگشتی

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

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

برنامه محاسبه فاصله ویرایش در #C به روش بازگشتی

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

خروجی قطعه کدهای بالا به صورت زیر است.

3

پیچیدگی زمانی راهکار بالا به صورت نمایی است. در بدترین حالت، این کار دارای درجه پیچیدگی O(3^m)‎ است. بدترین حالت هنگامی اتفاق می‌افتد که هیچ یک از کاراکترهای بالا از دو رشته تطبیق پیدا نکنند. در زیر، نمودار فراخوانی بازگشتی برای بدترین حالت ارائه شده است.

محاسبه فاصله ویرایش به روش برنامه‌نویسی پویا

می‌توان مشاهده کرد که زیر مسائل دوباره و دوباره حل می‌شوند. برای مثال، eD(2,2)‎ سه آیتم را فراخوانی می‌کند. با توجه به اینکه زیرمسائل مشابهی چندین و چند بار تکرار می‌شوند، این مسائل، دارای زیرمسائل هم‌پوشان هستند.

فیلم آموزش برنامه نویسی C++‎ سی پلاس پلاس در فرادرس

کلیک کنید

بنابراین، مساله ویرایش فاصله، دارای دو مشخصه از مسائل «برنامه‌نویسی پویا» (Dynamic Programming) است. محاسبه مجدد زیر مسائل مشابه با ساخت یک آرایه موقت که نتایج زیر مسائل را ذخیره می‌کند، قابل اجتناب است.

برنامه محاسبه فاصله ویرایش در ++C به روش برنامه‌نویسی پویا

برنامه محاسبه فاصله ویرایش در جاوا به روش برنامه‌نویسی پویا

برنامه محاسبه فاصله ویرایش در پایتون به روش برنامه‌نویسی پویا

برنامه محاسبه فاصله ویرایش در #C به روش برنامه‌نویسی پویا

برنامه محاسبه فاصله ویرایش در PHP به روش برنامه‌نویسی پویا

خروجی قطعه کدهای بالا به صورت زیر است.

3

پیچیدگی زمانی این روش از درجه O(m x n)‎ و فضای کمکی آن از درجه O(m x n)‎ است. کاربردهای عملی زیادی برای الگوریتم بیان شده وجود دارد.

فیلم مجموعه آموزش برنامه نویسی – مقدماتی تا پیشرفته در فرادرس

کلیک کنید

به عنوان مثالی در این رابطه، می‌توان به نمایش همه کلمات در لغت‌نامه‌ای اشاره کرد که تقریب نزدیکی به کلمه نوشته شده به صورت اشتباه دارند.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌های برنامه‌نویسی پایتون
• آموزش تکمیلی برنامه‌نویسی پایتون
• مجموعه آموزش‌های داده‌کاوی و یادگیری ماشین
• زبان برنامه‌نویسی پایتون (Python) — از صفر تا صد
• یادگیری علم داده (Data Science) با پایتون — از صفر تا صد
• آموزش پایتون (Python) — مجموعه مقالات جامع وبلاگ فرادرس

^^