문자열 편집 거리 예시에 대한 자세한 설명
- 零下一度원래의
- 2017-06-30 09:34:252028검색
동적 프로그래밍 알고리즘 문제는 대기업 필기시험에서 자주 출제되는 문제입니다. 많은 알고리즘 WeChat 공개 계정에서는 "동적 프로그래밍"에 대한 기사가 일반적입니다. 그들은 모두 동적 프로그래밍을 설명하기 위해 가장 이해하기 쉬운 단어를 사용하려고 합니다. 심지어 일부는 이를 설명하기 위해 만화를 사용하기도 합니다. 숫자로 푸시된 기사를 읽고 이해할 수 있으며 누구나 동적 프로그래밍에 대한 전반적인 이해를 가질 수 있습니다.
동적 프로그래밍이란 무엇인가요? 평신도의 말로는 문제에 대한 해결책은 한 눈에 알 수 있지만(완전한 목록) 하나씩 셀 수는 없지만 최적의 해결책을 찾아야 한다는 것입니다. 그리고 "최소한"이라는 질문에 "적어도", "전체적으로 몇 종류가 있는가" 등의 공식을 사용하면 이러한 문제는 이론적으로 동적 프로그래밍이라는 아이디어를 사용하여 해결할 수 있습니다. 동적 프로그래밍은 분할 정복 방법과 유사하며 하위 문제의 해를 결합하여 원래 문제를 해결하지만 각 하위 문제를 한 번만 해결하고 이를 다시 계산하지 않고 테이블에 저장하는 것이 일반적입니다. 최적화 문제를 해결하기 위해 ——"알고리즘 소개".
거리 편집(Edit Distance), 이 기사에서는 Levenshtein 거리를 의미합니다. 즉, 문자열 S1은 삽입하는 세 가지 작업을 통해 적어도 S2 문자열로 변환될 수 있습니다. , 수정, 삭제 횟수. 예: S1 = abc, S2 = abf, 편집 거리 d = 1(c을 f로 변경하면 됩니다). 이 기사에서는 동적 프로그래밍이라는 알고리즘 아이디어를 사용하여 문자열의 편집 거리를 해결합니다.
정의: S1과 S2는 두 개의 문자열 을 나타내고, S1(i)은 S1의 첫 번째 문자 을 나타내며, d[i, j]는 S 를 나타냅니다. 일 1의 i 접두어를 S2의 j번째 접두어로(예: :S1 = ”abc”,S2 = ”def”,Solve S1to The S2의 편집 거리 는 d[3, 3])입니다.
S1 = "abc", S2 = "dec"인 경우 편집 거리는 d[3, 3] = 2입니다. 두 문자열의 마지막 문자가 동일한지 확인하세요. 즉, S1(3) = S2(3)에는 변환이 필요하지 않으므로 S1 = ”abc”, S2 = ”dec” <= > S1' = ”ab”, S2' = ”de” 즉, S1[i] = S[j], d[i, j] = d[i-1,j -1]인 경우입니다. 공식을 구하세요: d[i, j] = d[i - 1, j - 1] (S1[i] = S2[j])
위 기사는 S1[i] = S2[j]일 때 계산 공식을 산출합니다. 분명히 S1 = ”abc ", S2인 경우 S1[i] ≠ S2[j]인 또 다른 상황이 있습니다. = "데프". S1을 S2로 변환하는 과정은 "modify"도 가능하지만, "insert", 를 통해 삭제도 가능합니다. " ” 은 S1을 S2로 변신시킵니다.
1) 문자열 S1 끝에 문자 "f" 를 삽입합니다. S1[i] = S2[j]의 인 경우, S1일 때 편집 거리는 는 S2로 변환되어 d[4, 3] = d[3, 2]입니다. 따라서 d[i, j]=d[i, j - 1] + 1이 됩니다. (+1은 S1에 ”f”이 추가되었기 때문입니다.) 2) 이때 S2에 문자열 끝에 "c"
문자를 삽입합니다. S1 = "abc", S2 = "defc", S1[i] = S[j], S1이 S2로 변환되는 경우입니다. 편집 거리는 d[3, 4] = d[2, 3]입니다. 따라서 d[i, j]=d[i - 1, j] + 1이 됩니다. 실제로 이것은 S1의 deletion입니다. (+1은 S2에 ”c”가 추가되었기 때문입니다) 3) S1 문자열의 마지막 문자 를
”f”로 변경합니다. S1 = “abf”, S2 = “def”, S1[i] = S[j], S1이 S2로 변환되는 경우입니다. 의 편집 거리는 d[3, 3] = d[2, 2]입니다. 따라서 d[i, j] = d[i – 1, j - 1] + 1이 됩니다. (+1은 S1이 “c” 수정되었기 때문입니다) 요약하면 다음과 같은 재귀 공식을 얻게 됩니다. => S1="abc", S2="def"에 대한 동적 프로그래밍의 풀이 과정을 표로 표현하는 것이 좋습니다. . 빨간색 사각형이 필요한 최종 편집 거리이고 전체 솔루션 프로세스는 이 테이블을 ——2차원 배열로 채우는 것임을 알 수 있습니다. 다음은 각각 Java 및 Python에서 문자열 편집 거리에 대한 동적 프로그래밍 솔루션입니다. Java Python3
1 package com.algorithm.dynamicprogramming; 2 3
/** 4 * 动态规划——字符串的编辑距离 5 * s1 = "abc", s2 = "def" 6
* 计算公式： 7 * | 0
i = 0, j = 0 8 * | j
i = 0, j > 0 9 * d[i,j] = | i
i > 0, j = 0 10 * | min(d[i,j-1]+1, d[i-1,j]+1, d[i-1,j-1]) s1(i) = s2(j) 11
* | min(d[i,j-1]+1, d[i-1,j]+1, d[i-1,j-1]+1) s1(i) ≠ s2(j) 12 * 定义二维数组[4][4]： 13
* d e f d e f 14 * |x|x|x|x| |0|1|2|3| 15
* a |x|x|x|x| => a |1|1|2|3| => 编辑距离d = [3][3] = 3 16 * b |x|x|x|x|
b |2|2|2|3| 17 * c |x|x|x|x| c |3|3|3|3| 18 * 19 * Created by yulinfeng on 6/29/17. 20
*/ 21 public class Levenshtein { 22 23 public static void main(String[] args) { 24
String s1 = "abc"; 25 String s2 = "def"; 26 int editDistance = levenshtein(s1, s2); 27
System.out.println("s1=" + s1 + "与s2=" + s2 + "的编辑距离为：" + editDistance); 28 } 29 30 /** 31
* 编辑距离求解 32 * @param s1 字符串s1 33 * @param s2 字符串s2 34 * @return 编辑距离 35
*/ 36 private static int levenshtein(String s1, String s2) { 37 int i = 0; //s1字符串中的字符下标 38
int j = 0; //s2字符串中的字符下标 39 char s1i = 0; //s1字符串第i个字符 40
char s2j = 0; //s2字符串第j个字符 41 int m = s1.length(); //s1字符串长度 42
int n = s2.length(); //s2字符串长度 43 if (m == 0) {
//s1字符串长度为0，此时的编辑距离就是s2字符串长度 44 return n; 45 } 46
if (n == 0) { 47 return m; //s2字符串长度为0，此时的编辑距离就是s1字符串长度 48 }
int[][] solutionMatrix = new int[m + 1][n + 1]; //求解矩阵 50
/** 51 *
d e f 52 * |0|x|x|x| 53
* a |1|x|x|x| 54
* b |2|x|x|x| 55
* c |3|x|x|x| 56 */ 57 for (i = 0; i < m + 1; i++) { 58 solutionMatrix[i][0] = i; 59 } 60
/** 61 * d e f 62
* |0|1|2|3| 63
* a |x|x|x|x| 64
* b |x|x|x|x| 65
* c |x|x|x|x| 66 */ 67 for (j = 0; j < n + 1; j++) { 68 solutionMatrix[0][j] = j; 69 } 70
/** 71 * 上面两个操作后，求解矩阵变为 72
* d e f 73
* |0|1|2|3| 74
* a |1|x|x|x| 75
* b |2|x|x|x| 76
* c |3|x|x|x| 77
* 接下来就是填充剩余表格 78
*/ 79 for (i = 1; i < m + 1; i++) { //i = 1,j = 1, 2, 3，以行开始填充 80 s1i = s1.charAt(i - 1); 81
for (j = 1; j < n + 1; j++) { 82 s2j = s2.charAt(j - 1); 83 int flag = (s1i == s2j) ? 0 : 1;
//根据公式，如果s1[i] = s2[j]，则d[i,j]=d[i-1,j-1]，如果s1[i] ≠ s2[j]，则其中一个公式为d[i,j]=d[i-1,j-1]+1 84
solutionMatrix[i][j] = min(solutionMatrix[i][j-1] + 1, solutionMatrix[i-1][j] + 1, solutionMatrix[i-1][j-1] + flag); 85
} 86 } 87 return solutionMatrix[m][n]; 88 } 89 90 /** 91 * 根据公式求解编辑距离 92
* @param insert s1插入操作 93 * @param delete s1删除操作 94 * @param edit s1修改操作 95 * @return 编辑距离 96
*/ 97 private static int min(int insert, int delete, int edit) { 98 int tmp = insert < delete ? insert : delete; 99
return tmp < edit ? tmp : edit;100 }101 } 1 ''' 2 动态规划——字符串的编辑距离 3 s1 = "abc", s2 = "def" 4
计算公式： 5 | 0
i = 0, j = 0 6 | j
i = 0, j > 0 7 d[i,j] = | i
i > 0, j = 0 8 | min(d[i,j-1]+1, d[i-1,j]+1, d[i-1,j-1]) s1(i) = s2(j) 9
| min(d[i,j-1]+1, d[i-1,j]+1, d[i-1,j-1]+1) s1(i) ≠ s2(j)10
定义二维数组[4][4]：11 d e f d e f12 |x|x|x|x|
|0|1|2|3|13 a |x|x|x|x| => a |1|1|2|3| => 编辑距离d = [4][4] = 314 b |x|x|x|x|
b |2|2|2|3|15 c |x|x|x|x| c |3|3|3|3|16 '''17 def levenshtein(s1, s2):18 i = 0
#s1字符串中的字符下标19 j = 0 #s2字符串中的字符下标20 s1i = "" #s1字符串第i个字符21
s2j = "" #s2字符串第j个字符22 m = len(s1) #s1字符串长度23 n = len(s2) #s2字符串长度24
if m == 0:25 return n #s1字符串长度为0，此时的编辑距离就是s2字符串长度26 if n == 0:27
return m #s2字符串长度为0，此时的编辑距离就是s1字符串长度28
solutionMatrix = [[0 for col in range(n + 1)] for row in range(m + 1)] #长为m+1，宽为n+1的矩阵29 '''30
d e f31 |0|x|x|x|32 a |1|x|x|x|33 b |2|x|x|x|34
c |3|x|x|x|35 '''36 for i in range(m + 1):37 solutionMatrix[i][0] = i38 '''39
d e f40 |0|1|2|3|41 a |x|x|x|x|42 b |x|x|x|x|43
c |x|x|x|x|44 45 '''46 for j in range(n + 1):47 solutionMatrix[0][j] = j48 '''49
上面两个操作后，求解矩阵变为50 d e f51 |0|1|2|3|52 a |1|x|x|x|53
b |2|x|x|x|54 c |3|x|x|x|55 接下来就是填充剩余表格56 '''57 for x in range(1, m + 1):58
s1i = s1[x - 1]59 for y in range(1, n + 1):60 s2j = s2[y - 1]61 flag = 0 if s1i == s2j else 162
solutionMatrix[x][y] = min(solutionMatrix[x][y-1] + 1, solutionMatrix[x-1][y] + 1, solutionMatrix[x-1][y-1] + flag)63 64
return solutionMatrix[m][n]65 66 def min(insert, delete, edit):67 tmp = insert if insert < delete else delete68
return tmp if tmp < edit else edit69 70 s1 = "abc"71 s2 = "def"72 distance = levenshtein(s1, s2)73 print(distance)
위 내용은 문자열 편집 거리 예시에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!