Edit Distance क्या है

Edit distance एक word को दूसरे में बदलने के लिए चाहे कम से कम letter changes, adds या deletes count करने जैसा है।

In this page:

Edit Distance Idea
DP State
Transition
Insert and Delete
Practice

Syntax

markup

for i in range(m + 1):
    for j in range(n + 1):
        if i == 0:
            dp[i][j] = j
        elif j == 0:
            dp[i][j] = i
        elif a[i - 1] == b[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])

Edit Distance Idea

Edit distance यह measure करता है कि दो strings कितनी अलग हैं एक string को दूसरी में बदलने के लिए चाहिए सबसे कम single-character insertions, deletions, और substitutions count करके — वही idea जो spell-checkers corrections suggest करने के लिए उपयोग करते हैं।

उदाहरण: Edit Distance Idea

#include <iostream>
using namespace std;
int main() {
	cout << "Fewest inserts/deletes/substitutions to turn 'kitten' into 'sitting' -- what spell-checkers use";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Fewest inserts/deletes/substitutions to turn 'kitten' into 'sitting' -- what spell-checkers use");
	}
}

print("Fewest inserts/deletes/substitutions to turn 'kitten' into 'sitting' -- what spell-checkers use")

#include <stdio.h>
int main() {
	printf("Fewest inserts/deletes/substitutions to turn 'kitten' into 'sitting' -- what spell-checkers use");
	return 0;
}

DP State

dp[i][j] एक string के पहले i characters और दूसरी के पहले j characters के बीच edit distance store करता है, इसलिए हर prefix pair भरने के बाद final answer table के bottom-right corner में बैठता है।

उदाहरण: DP State

#include <iostream>
using namespace std;
int main() {
	int dp[7][8] = {0};
	cout << "dp[i][j] = edit distance between first i chars of s1, first j chars of s2; answer is dp[6][7]";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[][] dp = new int[7][8];
		System.out.println("dp[i][j] = edit distance between first i chars of s1, first j chars of s2; answer is dp[6][7]");
	}
}

dp = [[0]*8 for _ in range(7)]
print("dp[i][j] = edit distance between first i chars of s1, first j chars of s2; answer is dp[6][7]")

#include <stdio.h>
int main() {
	int dp[7][8] = {0};
	printf("dp[i][j] = edit distance between first i chars of s1, first j chars of s2; answer is dp[6][7]");
	return 0;
}

Transition

जब current characters match करें, कोई edit की ज़रूरत नहीं और value diagonal से unchanged carry होती है; जब वे अलग हों, आप तीन possible edits में से सबसे सस्ता लेते हैं — insert, delete, या substitute — और जिस भी neighboring value से वह edit मेल खाता है उसमें एक जोड़ते हैं।

उदाहरण: Transition

#include <iostream>
using namespace std;
int main() {
	string s1 = "kitten", s2 = "sitting";
	int n = s1.size(), m = s2.size();
	int dp[7][8];
	for (int i = 0; i <= n; i++) dp[i][0] = i;
	for (int j = 0; j <= m; j++) dp[0][j] = j;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			dp[i][j] = s1[i-1]==s2[j-1] ? dp[i-1][j-1] : 1 + min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]});
	cout << "Edit distance: " << dp[n][m];
	return 0;
}

public class Main {
	public static void main(String[] args) {
		String s1 = "kitten", s2 = "sitting";
		int n = s1.length(), m = s2.length();
		int[][] dp = new int[n+1][m+1];
		for (int i = 0; i <= n; i++) dp[i][0] = i;
		for (int j = 0; j <= m; j++) dp[0][j] = j;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				dp[i][j] = s1.charAt(i-1)==s2.charAt(j-1) ? dp[i-1][j-1] : 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
		System.out.println("Edit distance: " + dp[n][m]);
	}
}

s1, s2 = "kitten", "sitting"
n, m = len(s1), len(s2)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(n+1): dp[i][0] = i
for j in range(m+1): dp[0][j] = j
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = dp[i-1][j-1] if s1[i-1]==s2[j-1] else 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
print("Edit distance:", dp[n][m])

#include <stdio.h>
#include <string.h>
int min3(int a, int b, int c) { int m = a<b?a:b; return m<c?m:c; }
int main() {
	char s1[] = "kitten", s2[] = "sitting";
	int n = strlen(s1), m = strlen(s2);
	int dp[7][8];
	for (int i = 0; i <= n; i++) dp[i][0] = i;
	for (int j = 0; j <= m; j++) dp[0][j] = j;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			dp[i][j] = s1[i-1]==s2[j-1] ? dp[i-1][j-1] : 1 + min3(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]);
	printf("Edit distance: %d", dp[n][m]);
	return 0;
}

Insert and Delete

एक string में एक insertion ऊपर की cell में move करने से मेल खाता है (source से एक उपयोग किए बिना target का एक और character उपयोग करते हुए), जबकि एक deletion बाईं cell में move करने से मेल खाता है — दोनों बस एक थोड़े छोटे subproblem में एक edit जोड़ते हैं।

उदाहरण: Insert and Delete

#include <iostream>
using namespace std;
int main() {
	cout << "Insert = move up one cell (dp[i][j-1]); delete = move left one cell (dp[i-1][j])";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Insert = move up one cell (dp[i][j-1]); delete = move left one cell (dp[i-1][j])");
	}
}

print("Insert = move up one cell (dp[i][j-1]); delete = move left one cell (dp[i-1][j])")

#include <stdio.h>
int main() {
	printf("Insert = move up one cell (dp[i][j-1]); delete = move left one cell (dp[i-1][j])");
	return 0;
}

Practice

Spell-checkers से आगे, edit distance DNA sequence alignment, plagiarism detection, और search engines द्वारा दिखाए जाने वाले 'did you mean' suggestions के पीछे है जब कोई query exactly किसी चीज़ से match न हो।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Edit distance underlies DNA alignment, plagiarism detection, and search 'did you mean' suggestions";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Edit distance underlies DNA alignment, plagiarism detection, and search 'did you mean' suggestions");
	}
}

print("Edit distance underlies DNA alignment, plagiarism detection, and search 'did you mean' suggestions")

#include <stdio.h>
int main() {
	printf("Edit distance underlies DNA alignment, plagiarism detection, and search 'did you mean' suggestions");
	return 0;
}

Chapter Quiz — Complete all 12 topics to unlock

0/12 topics done

Complete these topics first:

← Previous Lesson Longest Increasing Subsequence Next Lesson → Coin Change Problem