এডিট ডিসট্যান্স (Edit Distance)

আপনি হয়তো "kitten" টাইপ করেছেন এবং অটো-কারেক্ট সাজেস্ট করছে "sitting"। এটি কীভাবে বোঝে যে শব্দ দুটি কাছাকাছি? এটি মূলত একটি শব্দকে অন্যটিতে রূপান্তর করতে প্রয়োজনীয় ন্যূনতম একক-অক্ষর পরিবর্তনের সংখ্যা গণনা করে। একটি অক্ষর যোগ করা (insert), একটি অক্ষর মুছে ফেলা (delete), অথবা একটি অক্ষর অন্য অক্ষর দিয়ে পরিবর্তন করা (replace) — প্রতিটির খরচ বা কস্ট ১। এই ন্যূনতম সংখ্যাটিই হলো এডিট ডিসট্যান্স (Edit Distance) (একে লেভেনস্টেইন ডিসট্যান্সও বলা হয়)।

kitten → sitten (k-কে s দিয়ে পরিবর্তন) → sittin (e-কে i দিয়ে পরিবর্তন) → sitting (শেষে g যোগ করা)। এখানে মোট তিনটি অপারেশন লেগেছে। সুতরাং, এডিট ডিসট্যান্স = ৩।

তিনটি অপারেশন

ইনসার্ট (Insert): যেকোনো জায়গায় একটি অক্ষর যোগ করা। "cat" → "coat" = ১টি ইনসার্শন।

ডিলিট (Delete): একটি অক্ষর মুছে ফেলা। "cats" → "cat" = ১টি ডিলিশন।

রিপ্লেস (Replace): একটি অক্ষরের বদলে অন্য একটি অক্ষর বসানো। "cat" → "bat" = ১টি রিপ্লেসমেন্ট।

2D ডিপি (DP) টেবিল

ধরি dp[i][j] = s-এর প্রথম \(i\) সংখ্যক অক্ষরকে t-এর প্রথম \(j\) সংখ্যক অক্ষরে রূপান্তর করতে ন্যূনতম কতবার এডিট করতে হবে। টেবিলটি হবে (m+1) × (n+1) সাইজের।

বেস কেস (Base cases): dp[i][0] = i (s-এর সব \(i\) সংখ্যক অক্ষর মুছে ফেলা) এবং dp[0][j] = j (কিছুই না থাকা অবস্থা থেকে t তৈরি করতে \(j\) সংখ্যক অক্ষর ইনসার্ট করা)।

রিকারেন্স বা পুনরাবৃত্তি

যদি s[i-1] == t[j-1] হয়: dp[i][j] = dp[i-1][j-1]। অক্ষরগুলো মিলে গেছে — তাই কোনো অপারেশনের প্রয়োজন নেই, শুধু কোণাকুণি বা ডায়াগোনাল মানটি নিলেই হবে।

যদি s[i-1] != t[j-1] হয়: dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])। এটি একটি অপারেশন, সাথে এই তিনটির মধ্যে ন্যূনতমটি: রিপ্লেসিং (কোণাকুণি), s[i-1] ডিলিট করা (ওপরে), অথবা t[j-1] ইনসার্ট করা (বামে)।

স্পেস অপ্টিমাইজেশন (Space Optimization)

dp[i][j] মানটি শুধুমাত্র কোণাকুণি ওপর-বামে, সরাসরি ওপরে এবং সরাসরি বামে থাকা সেলের ওপর নির্ভর করে — তাই শুধুমাত্র একটি রRow বা সারি এবং একটি অতিরিক্ত ভেরিয়েবলই যথেষ্ট। এর ফলে স্পেস \(O(m·n)\) থেকে কমে \(O(\min(m,n))\) হয়ে যায়। এতে আপনি রূপান্তরের ধাপগুলো (reconstruction) ট্র্যাক করার ক্ষমতা হারাবেন, তবে ডিসট্যান্স ভ্যালুটি সঠিকভাবে পাবেন।