مساله تقریب فاصله ویرایش

این نوشته در مورد مقاله زیر است و پیوند آن این است.

Chakraborty, Diptarka, et al. “Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time.” (2018).

مساله فاصله ویرایش یک مساله معروف در علوم کامپیوتر است که معمولا در درس‌های ابتدایی الگوریتم تدریس می‌شوند. مساله بدین صورت است که دو رشته S و T را داریم و می‌خواهیم با کم‌ترین تغییرات شامل حذف، اضافه کردن، و یا تغییر حرف به حرف دیگر دو رشته را به هم تبدیل کنیم. هدف مساله یافتن کم‌ترین تعداد تغییرات برای تبدیل دو رشته به یکدیگر است.

در درس الگوریتم یاد می‌گیریم که الگوریتیمی با زمان اجرای متناسب با mn که m و n طول رشته‌های ورودی هستند برای مساله وجود دارد.

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

مساله تقریب فاصله ویرایش مساله جذابی بوده و نتایج زیادی در موردش مطرح شده. در حقیقت یک الگوریتم دو پارامتر دارد که با آن‌ها سنجیده می‌شود: ضریب تقریب و زمان اجرا. ضریب تقریب توضیح می‌دهد که پاسخ الگوریتم حداکثر چندبرابر جواب بهینه است و با زمان اجرا هم که آشنا هستید.

در سال ۲۰۱۰ الگوریتمی ارائه شد که ضریب تقریب آن یک چندجمله‌ای برحسب لگاریتم n است (اینجا فرض می‌کنید n و m برابر هستند) و زمان اجرای آن تقریبا خطی است، یعنی زمان اجرای آن n ضربدر یک چندجمله‌ای برحسب لگاریتم n است.

در سال ۲۰۱۷ نشان داده شده که اگر فرض‌های معمول پیچیدگی را قبول کنیم، الگوریتمی با ضریب کمتر از [latex]1+o(1)[/latex] برای مساله وجود ندارد.

در کنفرانس FOCS امسال الگوریتمی ارائه شده که با ضریب ثابت و در زمان کمتر از توان دوم n مساله را حل می‌کند. پس از سال‌ها دستاورد خیلی جالبی است. 

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