فاصله لون‌اشتاین

فاصله لون‌اشتاین یا فاصله ویرایش در نظریه اطلاعات  و علوم کامپیوتر مقیاسی برای محاسبه‌ی میزان تفاوت میان دو رشته است.

فاصله لون‌اشتاین بین دو رشته به وسیلهٔ کمترین تعداد عملیات مورد نیاز برای تبدیل یک رشته به رشته دیگر معین می‌شود، که یک عملیات می‌تواند یک ضمیمه، یا جایگزینی یک کارکتر باشد. تعمیم فاصله لوناشتاین (فاصله دامرا-لون‌اشتاین) اجازه ترانهش دو کاراکتر را به عنوان یک عملیات می‌دهد.

این معیار به افتخار ولادمیر لون‌اشتاین، که این فاصله را در سال ۱۹۵۶ مطرح کرد، نام گذاری شده‌است.В. И. Левенштейн (1965) Двоичные коды с исправлением выпадений, вставок и замещений символов. Доклады Академий Наук СССР 163.4:845–848. Appeared in Englisصh as: V. I. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady 10 (1966):707–710.

همچنین از این موضوع در برنامه‌هایی که نیاز به یافتن مقدار شباهت، یا تفاوت دو رشته را دارند، مانند مقابله گر املائی، استفاده می‌شود.

به عنوان مثال فاصله لوناشتاین بین "kitten" و "sitting" برابر ۳ است. همان‌طور که می‌بینیم حداقل سه ویرایش برای تبدیل یکی به دیگری وجود دارد و کمتر از آن ممکن نیست:
 kitten → sitten(با جایگزینی 's' به جای 'k')
 sitten → sittin(با جایگزینی 'i' به جای 'e')
 sittin → sitting(با وارد کردن 'g' در انتها)

این موضوع را می‌توان به عنوان تعمیم فاصله‌ی همینگ در نظر گرفت که برای رشته‌های هم اندازه استفاده می‌شود و تنها می‌توان در آن از جایگزینی استفاده کرد.

از این مفهوم برای تصحیح، غلط‌یابی و پیشنهاد دادن در موتورهای جستجو نیز استفاده می‌شود.

 الگوریتم 
یک الگوریتم رایج برنامه‌نویسی پویا برای محاسبه فاصله لوناشتاین شامل استفاده از یک (n + 1) × (m + 1) ماتریس می‌شود، که n و m طول دو رشته هستند. این الگوریتم بر پایه الگوریتم وگنر-فیشر برای ویرایش فاصله‌است. در این قسمت یک شبه کد برای تابع LevensteinDistance بیان شده که دو رشته می‌گیرد، s به طول m و t به طول n، و فاصله لوناشتاین میان آن‌ها را حساب می‌کند:

 int LevenshteinDistance(char s[1..m], char t[1..n])
// d is a table with m+1 rows and n+1 columns
declare int d[0..m, 0..n]

for i from 0 to m
d[i, 0] := i
for j from 0 to n
d[0, j] := j

for i from 1 to m
for j from 1 to n
{
if s[i] = t[j] then cost := 0
else cost := 1
d[i, j] := minimum(
d[i-1, j] + 1, // insertion
d[i, j-1] + 1, // deletion
d[i-1, j-1] + cost // substitution
)
}

return d[m, n]

دو مثال از ماتریس خروجی به صورت زیر است (حداقل مراحل مشخص شده‌است):

رنگها در جدول:
 خاکستری:دو حرف با هم برابر بودند و نیازی به تغییر نیست.
 آبی:نشان دهندهٔ جایگزینی است.
 سبز:نشان دهندهٔ درج حرف است.
 قرمز:نشان دهندهٔ حذف حرف است.

kitten ۰ ۱ ۲ ۳ ۴ ۵ ۶s1 1 ۲ ۳ ۴ ۵ ۶i2 2 1 ۲ ۳ ۴ ۵t3 3 2 1 ۲ ۳ ۴t4 4 3 2 1 ۲ ۳i5 5 4 3 2 2 ۳n6 6 5 4 3 3 2g7 7 6 5 4 4 3Saturday۰ ۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸S1 0 1 2 ۳ ۴ ۵ ۶ ۷u2 1 1 2 2 ۳ ۴ ۵ ۶n3 2 2 2 3 3 ۴ ۵ ۶d4 3 3 3 3 4 3 ۴ ۵a5 4 3 4 4 4 4 3 ۴y6 5 4 4 5 5 5 4 3

ناوردا یی به دست آمده از الگوریتم این است که ما می‌توانیم بخش ابتدایی [s[1..i را به [t[1..j را با حداقل تعداد عملیات [d[i,j، تبدیل کنیم و در انتها، عنصر پایین و راست آرایه جواب ما است.

این الگوریتم ضرورتاً قسمتی از جواب بلندترین مسئله رایج زیردنباله (LCS)، در حالت خاصی که فقط دو لیست ورودی داریم، است.

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

 اثبات درستی 
همان‌طور که اشاره شد، ناوردایی این است که ما بتوانیم قسمت اولیه [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 حامل جواب ما است.

این اثبات نمی‌تواند این موضوع را که عددی که در [d[i,j در حقیقت کوچکترین عدد است را تصدیق کند;نشان دادن این موضوع بسیار مشکل است، و شامل برهان خلف است که در آن ما فرض می‌کنیم [d[i,j کوچکتر از سه فاصله مطرح شده‌است، و از این می‌توان استفاده کرد تا نشان دهیم یکی از سه فاصله مینیمم نیست.

 بهسازی‌های ممکن 
بهسازی‌های ممکن برای این الگوریتم شامل:
 ما می‌توانیم الگوریتم را به گونه‌ای تغییر دهیم که فضای کمتری اشغال کند که (O(s به جای (O(mn زمان ببرد، تا زمانی که قفط نیاز باشد که سطر قبلی و سطر فعلی در هر یک زمان ذخیره شوند.
 می‌توانیم تعداد ضمیمه‌ها، حذف‌ها، و جایگزینی‌ها را به‌طور جدا ذخیره کنیم، یا حتی در همان موقعیتی که رخ می‌دهند، که همیشه j است.
 می‌توان فاصله بازه‌های [۰٬۱] را نرمال سازی کرد.
 اگر تنها فاصله برای ما مهم است اگر آن کوچکتر از یک سرحد k باشد، آنگاه محاسبه خط قطری به پهنای 2k+۱ در ماتریس کفایت می‌کند. در این روش الگوریتم را می‌توان در زمان (O(kl اجرا کرد که l طول کوتاهترین رشته‌است.Dan Gusfield. Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge University Press, New York, NY, USA, 1997.
 با مقدار دهی اولیه سطر اول ماتریس با مقدار ۰ این الگوریتم را می‌توان در جستجوی فازی رشته ی یک رشته در یک متن استفاده کرد.Gonzalo Navarro. A guided tour to approximate string matching. ACM Computing
Surveys, 33(1):31–88, 2001. این بهسازی موقعیت پایانی زیررشتهٔ موردنظر متن را به دست می‌دهد. برای معین کردن نقطه شروع زیررشته منطبق تعداد ضمیمه‌ها، حذف‌ها، و جایگزینی‌ها را به‌طور جدا ذخیره می‌کنیم و از آن‌ها برای محاسبه نقطه شروع با توجه به نقطه پایان استفاده کنیم.Bruno Woltzenlogel Paleo. An approximate gazetteer for GATE based on levenshtein distance . Student Section of the European Summer School in Logic, Language and Information (ESSLLI), 2007.
 این الگوریتم به دلیل تعداد بسیار زیاد وابستگی داده در کارهای موازی ضعیف عمل می‌کند. هرچند، همه مقادیر cost قابل محاسبه به صورت موازی هستند و از این الگوریتم می‌توان برای اجرای تابع minimum در قسمت‌های متفاوت در جهت از بین بردن وابستگی‌ها استفاده کرد.

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

 جستارهای وابسته 
 فاصله همینگ
 ماشین خودکار لوناشتاین
 بلندترین مسئله رایج زیردنباله
 فضای متریک

 منابع 


رده:برنامه‌نویسی پویا
رده:زبان‌شناسی کمی