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

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

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

این معیار به افتخار ولادمیر لون‌اشتاین، که این فاصله را در سال ۱۹۵۶ مطرح کرد، نام گذاری شده‌است.

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

به عنوان مثال فاصله لوناشتاین بین "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]

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

رنگها در جدول:

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

		k	i	t	t	e	n
	۰	۱	۲	۳	۴	۵	۶
s	1	1	۲	۳	۴	۵	۶
i	2	2	1	۲	۳	۴	۵
t	3	3	2	1	۲	۳	۴
t	4	4	3	2	1	۲	۳
i	5	5	4	3	2	2	۳
n	6	6	5	4	3	3	2
g	7	7	6	5	4	4	3

		S	a	t	u	r	d	a	y
	۰	۱	۲	۳	۴	۵	۶	۷	۸
S	1	0	1	2	۳	۴	۵	۶	۷
u	2	1	1	2	2	۳	۴	۵	۶
n	3	2	2	2	3	3	۴	۵	۶
d	4	3	3	3	3	4	3	۴	۵
a	5	4	3	4	4	4	4	3	۴
y	6	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 طول کوتاهترین رشته‌است.
با مقدار دهی اولیه سطر اول ماتریس با مقدار ۰ این الگوریتم را می‌توان در جستجوی فازی رشته ی یک رشته در یک متن استفاده کرد. این بهسازی موقعیت پایانی زیررشتهٔ موردنظر متن را به دست می‌دهد. برای معین کردن نقطه شروع زیررشته منطبق تعداد ضمیمه‌ها، حذف‌ها، و جایگزینی‌ها را به‌طور جدا ذخیره می‌کنیم و از آن‌ها برای محاسبه نقطه شروع با توجه به نقطه پایان استفاده کنیم.
این الگوریتم به دلیل تعداد بسیار زیاد وابستگی داده در کارهای موازی ضعیف عمل می‌کند. هرچند، همه مقادیر cost قابل محاسبه به صورت موازی هستند و از این الگوریتم می‌توان برای اجرای تابع minimum در قسمت‌های متفاوت در جهت از بین بردن وابستگی‌ها استفاده کرد.

کران‌های بالا و پایین

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

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

جستارهای وابسته

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

منابع

↑ В. И. Левенштейн (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.
↑ 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 بایگانی‌شده در ۸ مه ۲۰۱۳ توسط Wayback Machine. Student Section of the European Summer School in Logic, Language and Information (ESSLLI), 2007.

[1] В. И. Левенштейн (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.

[2] Dan Gusfield. Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge University Press, New York, NY, USA, 1997.

[3] Gonzalo Navarro. A guided tour to approximate string matching. ACM Computing Surveys, 33(1):31–88, 2001.

[4] Bruno Woltzenlogel Paleo. An approximate gazetteer for GATE based on levenshtein distance بایگانی‌شده در ۸ مه ۲۰۱۳ توسط Wayback Machine. Student Section of the European Summer School in Logic, Language and Information (ESSLLI), 2007.