+1 امتیاز
قبل در علم و دانش توسط (1.1هزار امتیاز)

فاصله لون اشتاین در علوم کامپیوتر چیست و برای چه مواردی کاربرد دارد؟

1 پاسخ

+2 امتیاز
قبل توسط (2.2هزار امتیاز)

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

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

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

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

به عنوان مثال فاصله لوناشتاین بین "kitten" و "sitting" برابر 3 است. همانطور که می‌بینیم حداقل سه ویرایش برای تبدیل یکی به دیگری وجود دارد و کمتر از آن ممکن نیست:

kitten → sitten(با جایگزینی 's' به جای 'k')
sitten → sittin(با جایگزینی 'i' به جای 'e')
sittin → sitting(با وارد کردن 'g' در انتها)


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

سوالات مشابه

+1 امتیاز
2 پاسخ 585 بازدید
0 امتیاز
0 پاسخ 339 بازدید
0 امتیاز
0 پاسخ 573 بازدید
0 امتیاز
0 پاسخ 822 بازدید
0 امتیاز
0 پاسخ 186 بازدید
...