এডিট ডিস্ট্যান্স ও অপটিমাল সাবস্ট্রাকচার

১ · সমস্যার সংজ্ঞা

দুটি স্ট্রিং $X$ (দৈর্ঘ্য $m$) ও $Y$ (দৈর্ঘ্য $n$) দেওয়া থাকলে, $X$-কে $Y$-তে রূপান্তর করতে ন্যূনতম কতগুলো নিচের অপারেশন লাগবে তা বের করতে হবে — প্রতিটির খরচ $1$:

এটি বানান-সংশোধক (spell checker), DNA সিকোয়েন্স অ্যালাইনমেন্ট, এবং diff-জাতীয় টুলের একটি মৌলিক উপাদান। L26-এর LCS-এর সাথে গঠনগত মিল আছে (দুটি স্ট্রিং-এর প্রিফিক্স জোড়া দিয়ে রাজ্য), কিন্তু এখানে "মেলে কি না" ছাড়াও তিনটি ভিন্ন অপারেশনের খরচ বিবেচনা করতে হয়।

২ · DP রিকারেন্স

$dp[i][j]$ সংজ্ঞায়িত করি $X$-এর প্রথম $i$ ক্যারেক্টার-কে $Y$-এর প্রথম $j$ ক্যারেক্টারে রূপান্তর করার ন্যূনতম খরচ হিসেবে। বেস কেস: $dp[i][0] = i$ (পুরো $X$-এর প্রিফিক্স মুছে ফেলতে হবে) এবং $dp[0][j] = j$ (পুরো $Y$-এর প্রিফিক্স ইনসার্ট করতে হবে)।

$$ dp[i][j] = \begin{cases} dp[i-1][j-1] & x_i = y_j \\[4pt] 1 + \min\big(\, dp[i-1][j],\;\; dp[i][j-1],\;\; dp[i-1][j-1] \,\big) & x_i \ne y_j \end{cases} $$

যখন $x_i = y_j$, কোনো অপারেশনেরই দরকার নেই এই অবস্থানে — সমস্যাটি সরাসরি $dp[i-1][j-1]$-এ নেমে আসে। যখন $x_i \ne y_j$, তিনটি বিকল্প থেকে সবচেয়ে সস্তাটি বেছে নেওয়া হয় (প্রতিটির নিজস্ব খরচ $1$ যোগ করে):

অপটিমাল সাবস্ট্রাকচার প্রমাণ: $X[1..i]$-কে $Y[1..j]$-এ রূপান্তরকারী যেকোনো অপটিমাল অপারেশন-ক্রম বিবেচনা করুন এবং এর শেষ অপারেশনটি দেখুন (যেটি শেষ পর্যন্ত $x_i$ বা $y_j$-এর সাথে সংশ্লিষ্ট অবস্থানকে প্রভাবিত করে)। এটি অবশ্যই তিনটির একটি — ডিলিট, ইনসার্ট, সাবস্টিটিউট, অথবা (মিলে গেলে) কোনো অপারেশনই না। প্রতিটি ক্ষেত্রে, শেষ অপারেশনটি বাদ দিলে যা থাকে তা অবশ্যই সংশ্লিষ্ট ছোট সাবপ্রবলেমের (যথাক্রমে $dp[i-1][j]$, $dp[i][j-1]$, বা $dp[i-1][j-1]$) জন্য একটি অপটিমাল রূপান্তর-ক্রম হতে হবে — কারণ যদি সেই সাবপ্রবলেমের জন্য এর চেয়ে সস্তা কোনো ক্রম থাকত, সেটি ব্যবহার করে (একই শেষ অপারেশন যোগ করে) মূল সমস্যার জন্য একটি সস্তা সমাধান পাওয়া যেত — যা মূল সমাধানের অপটিমাল হওয়ার সাথে সাংঘর্ষিক। যেহেতু আমরা জানি না প্রকৃতপক্ষে কোন অপারেশনটি অপটিমাল সমাধানে ব্যবহৃত হয়েছিল, তাই সবগুলো বিবেচনা করে সবচেয়ে সস্তাটি বেছে নিই — এটাই $\min$ টার্মটির উৎস।

৩ · যাচাই — নেইভ এক্সপোনেনশিয়াল রিকার্সন বনাম DP

import random

def edit_brute(X, Y, i, j):
    # নেইভ এক্সপোনেনশিয়াল রিকার্সন -- কোনো cache নেই
    if i == 0:
        return j
    if j == 0:
        return i
    if X[i - 1] == Y[j - 1]:
        return edit_brute(X, Y, i - 1, j - 1)
    return 1 + min(
        edit_brute(X, Y, i - 1, j),      # ডিলিট
        edit_brute(X, Y, i, j - 1),      # ইনসার্ট
        edit_brute(X, Y, i - 1, j - 1),  # সাবস্টিটিউট
    )

def edit_dp(X, Y):
    # ট্যাবুলেটেড DP -- ঠিক একই রিকারেন্স, ইটারেটিভভাবে
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[m][n]

rng = random.Random(5)
alphabet = "abc"
print(f"{'X':>10} | {'Y':>10} | {'brute':>5} | {'dp':>3}")
for trial in range(10):
    lx = rng.randint(1, 8)
    ly = rng.randint(1, 8)
    X = "".join(rng.choice(alphabet) for _ in range(lx))
    Y = "".join(rng.choice(alphabet) for _ in range(ly))
    b = edit_brute(X, Y, len(X), len(Y))
    d = edit_dp(X, Y)
    assert b == d, "মিসম্যাচ!"
    print(f"{X:>10} | {Y:>10} | {b:>5} | {d:>3}")

print("\nক্লাসিক উদাহরণ:")
print("kitten -> sitting:", edit_dp("kitten", "sitting"),
      "(brute:", edit_brute("kitten", "sitting", 6, 7), ")")