سورس مسئله فاصله لون اشتاین با جاوا Java

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

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

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

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

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

kitten → sitten(با جایگزینی ‘s’ به جای ‘k’)
sitten → sittin(با جایگزینی ‘i’ به جای ‘e’)
sittin → sitting(با وارد کردن ‘g’ در انتها)
این موضوع را می‌توان به عنوان تعمیم فاصله همینگ در نظر گرفت، که برای رشته‌های هم اندازه استفاده می‌شد و فقط می‌توانستیم در آن از جایگزینی استفاده کنیم.

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

سورس مسئله فاصله لون اشتاین با جاوا Java

اولین نفری باشید که نظر می دهد.

دیدگاهی بنویسید

آدرس ایمیل شما محفوظ می ماند


*