জাভাস্ক্রিপ্টে Levenshtein দূরত্ব

Levenshtein দূরত্ব

Levenshtein দূরত্ব দুটি অনুক্রমের মধ্যে পার্থক্য পরিমাপের জন্য একটি স্ট্রিং মেট্রিক। এটি একটি শব্দকে অন্য শব্দে পরিবর্তন করার জন্য প্রয়োজনীয় একক-অক্ষরের সম্পাদনার ন্যূনতম সংখ্যা৷

উদাহরণস্বরূপ -

বিবেচনা করুন, আমাদের এই দুটি স্ট্রিং আছে -

const str1 = 'hitting';
const str2 = 'kitten';

এই দুটি স্ট্রিংয়ের মধ্যে Levenshtein দূরত্ব 3 কারণ আমাদের এই তিনটি সম্পাদনা করতে হবে -

• kitten → hitten ("k" এর জন্য "h" এর প্রতিস্থাপন)

• hitten → hittin ("e" এর জন্য "i" এর প্রতিস্থাপন)

• hittin → হিটিং (শেষে "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