موضوع مقاله: فاصله لون‌اشتاین | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # فاصله لون‌اشتاین | مقدمه: فاصله لون‌اشتاین یا فاصله ویرایش در نظریه اطلاعات و علوم کامپیوتر مقیاسی برای محاسبه‌ی میزان تفاوت میان دو رشته است. | ## بخش 1: فاصله لون‌اشتاین | فاصله لون‌اشتاین بین دو رشته به وسیلهٔ کمترین تعداد عملیات مورد نیاز برای تبدیل یک رشته به رشته دیگر معین می‌شود، که یک عملیات می‌تواند یک ضمیمه، یا جایگزینی یک کارکتر باشد. تعمیم فاصله لوناشتاین (فاصله دامرا-لون‌اشتاین) اجازه ترانهش دو کاراکتر را به عنوان یک عملیات می‌دهد. این معیار به افتخار ولادمیر لون‌اشتاین، که این فاصله را در سال ۱۹۵۶ مطرح کرد، نام گذاری شده‌است.В. همچنین از این موضوع در برنامه‌هایی که نیاز به یافتن مقدار شباهت، یا تفاوت دو رشته را دارند، مانند مقابله گر املائی، استفاده می‌شود. از این مفهوم برای تصحیح، غلط‌یابی و پیشنهاد دادن در موتورهای جستجو نیز استفاده می‌شود. الگوریتم یک الگوریتم رایج برنامه‌نویسی پویا برای محاسبه فاصله لوناشتاین شامل استفاده از یک (n + 1) × (m + 1) ماتریس می‌شود، که n و m طول دو رشته هستند. این الگوریتم ضرورتاً قسمتی از جواب بلندترین مسئله رایج زیردنباله (LCS)، در حالت خاصی که فقط دو لیست ورودی داریم، است. | ## بخش 2: فاصله لون‌اشتاین | با کمی تغییر، الگوریتم مشابهی را می‌توان در تطبیق تقریبی رشته استفاده کرد که برای یافتن یک زیررشته از یک متن که به بهترین صورت منطبق با الگوی داده شده‌است، استفاده می‌شود. اثبات درستی همان‌طور که اشاره شد، ناوردایی این است که ما بتوانیم قسمت اولیه [s[1..i را به [t[1..j با حداقل تعداد عملیاتهای [d[i,j، تبدیل کنیم. این ناوردایی تا زمانی برقرار است که: در ابتدا این موضوع در سطر و ستون ۰ درست است چون که [s[1..i می‌تواند به یک رشته تهی [t[1..0، با به سادگی بیرون انداختن همه کاراکترهای i، تبدیل شود. سه فاصله مینیمم به دست می‌آید، که هر کدام محتمل هستند: اگر می‌توانستیم [s[1..i را به [t[1..j-1 در k عملیات تبدیل کنیم، آنگاه به سادگی [t[j را بعد از آن برای رسیدن به [t[1..j در k+1 عمل، اضافه می‌کردیم. اگر می‌توانستیم [s[1..i-1 را به [t[1..j در k عملیات تبدیل کنیم، آنگاه همین عملیات را روی [s[1..i انجام می‌دادیم و سپس در انتها [s[i اصلی را در k+1 حذف می‌کردیم. اگر می‌توانستیم [s[1..i-1 را به [t[1..j-1 در k عملیات تبدیل کنیم، آنگاه همین عملیات را روی [s[1..i انجام دهیم و سپس جایگزینی [t[j به جای [s[i اصلی در انتها در صورت نیاز، که نیاز به k+cost عملیات دارد. تعداد عملیاتی که مورد نیاز است برای تبدیل [s[1..n به [t[1..m به‌طور قطع همان تعداد عملیاتی است که برای همهٔ s به همهٔ t است، و [d[n,m حامل جواب ما است. | ## بخش 3: فاصله لون‌اشتاین | این اثبات نمی‌تواند این موضوع را که عددی که در [d[i,j در حقیقت کوچکترین عدد است را تصدیق کند;نشان دادن این موضوع بسیار مشکل است، و شامل برهان خلف است که در آن ما فرض می‌کنیم [d[i,j کوچکتر از سه فاصله مطرح شده‌است، و از این می‌توان استفاده کرد تا نشان دهیم یکی از سه فاصله مینیمم نیست. بهسازی‌های ممکن بهسازی‌های ممکن برای این الگوریتم شامل: ما می‌توانیم الگوریتم را به گونه‌ای تغییر دهیم که فضای کمتری اشغال کند که (O(s به جای (O(mn زمان ببرد، تا زمانی که قفط نیاز باشد که سطر قبلی و سطر فعلی در هر یک زمان ذخیره شوند. می‌توانیم تعداد ضمیمه‌ها، حذف‌ها، و جایگزینی‌ها را به‌طور جدا ذخیره کنیم، یا حتی در همان موقعیتی که رخ می‌دهند، که همیشه j است. اگر تنها فاصله برای ما مهم است اگر آن کوچکتر از یک سرحد k باشد، آنگاه محاسبه خط قطری به پهنای 2k+۱ در ماتریس کفایت می‌کند. این الگوریتم به دلیل تعداد بسیار زیاد وابستگی داده در کارهای موازی ضعیف عمل می‌کند. هرچند، همه مقادیر cost قابل محاسبه به صورت موازی هستند و از این الگوریتم می‌توان برای اجرای تابع minimum در قسمت‌های متفاوت در جهت از بین بردن وابستگی‌ها استفاده کرد. | ## جمع‌بندی | کران‌های بالا و پایین فاصله لوناشتاین تعداد زیادی کران بالا و پایین دارد که در بسیاری از برنامه‌ها که بعضی از آن‌ها را محاسبه و مقایسه می‌کند کاربرد دارد که شامل: همیشه حداقل تفاوت اندازه‌های دو رشته‌است.