লেভেনস্টাইন দূরত্ব
লেভেনস্টাইন দূরত্ব হলো দুটি সিকোয়েন্সের পার্থক্য মাপার একটি স্ট্রিং মেট্রিক। এটি এক শব্দকে অন্য শব্দে রূপান্তর করতে необходими ন্যূনতম একক-ক্যারেক্টার এডিটের সংখ্যা।
উদাহরণস্বরূপ:
বिचার করুন, আমাদের কাছে দুটি স্ট্রিং আছে:
const str1 = 'hitting'; const str2 = 'kitten';
এই দুটি স্ট্রিংয়ের মাঝপথের লেভেনস্টাইন দূরত্ব ৩ কারণ আমাদের তিনটি এডিট করতে হবে:
kitten → hitten (k-এর বদলে h সাবস্টিটিউশন)
hitten → hittin (e-এর বদলে i সাবস্টিটিউশন)
hittin → hitting (শেষে g ইনসার্শন)
আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা দুটি স্ট্রিং নিয়ে তাদের মাঝপথের লেভেনস্টাইন দূরত্ব হিসাব করবে।
উদাহরণ
নিচে কোডটি দেওয়া হলো:
const str1 = 'hitting'; const str2 = 'kitten'; const levenshteinDistance = (str1 = '', str2 = '') => { const track = Array(str2.length + 1).fill(null).map(() => Array(str1.length + 1).fill(null)); for (let i = 0; i <= str1.length; i += 1) { track[0][i] = i; } for (let j = 0; j <= str2.length; j += 1) { track[j][0] = j; } for (let j = 1; j <= str2.length; j += 1) { for (let i = 1; i <= str1.length; i += 1) { const indicator = str1[i - 1] === str2[j - 1] ? 0 : 1; track[j][i] = Math.min( track[j][i - 1] + 1, // deletion track[j - 1][i] + 1, // insertion track[j - 1][i - 1] + indicator, // substitution ); } } return track[str2.length][str1.length]; }; console.log(levenshteinDistance(str1, str2));আউটপুট
কনসোলে নিচের আউটপুট পাওয়া যাবে:
3
