GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — Python/dynamic_programming/edit_distance.py at python3.15t · TheAlgorithms/Python Expand file tree/ Copy pathedit_distance.pyMore file actions 103 lines (87 loc) · 3.35 KB / Copy pathedit_distance.pyFile metadata and controls103 lines (87 loc) · 3.35 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 """ Author : Turfa Auliarachman Date : October 12, 2016 This is a pure Python implementation of Dynamic Programming solution to the edit distance problem. The problem is : Given two strings A and B. Find the minimum number of operations to string B such that A = B. The permitted operations are removal, insertion, and substitution. """ class EditDistance: """ Use : solver = EditDistance() editDistanceResult = solver.solve(firstString, secondString) """ def __init__(self): self.word1 = "" self.word2 = "" self.dp = [] def __min_dist_top_down_dp(self, m: int, n: int) -> int: if m == -1: return n + 1 elif n == -1: return m + 1 elif self.dp[m][n] > -1: return self.dp[m][n] else: if self.word1[m] == self.word2[n]: self.dp[m][n] = self.__min_dist_top_down_dp(m - 1, n - 1) else: insert = self.__min_dist_top_down_dp(m, n - 1) delete = self.__min_dist_top_down_dp(m - 1, n) replace = self.__min_dist_top_down_dp(m - 1, n - 1) self.dp[m][n] = 1 + min(insert, delete, replace) return self.dp[m][n] def min_dist_top_down(self, word1: str, word2: str) -> int: """ >>> EditDistance().min_dist_top_down("intention", "execution") 5 >>> EditDistance().min_dist_top_down("intention", "") 9 >>> EditDistance().min_dist_top_down("", "") 0 """ self.word1 = word1 self.word2 = word2 self.dp = [[-1 for _ in range(len(word2))] for _ in range(len(word1))] return self.__min_dist_top_down_dp(len(word1) - 1, len(word2) - 1) def min_dist_bottom_up(self, word1: str, word2: str) -> int: """ >>> EditDistance().min_dist_bottom_up("intention", "execution") 5 >>> EditDistance().min_dist_bottom_up("intention", "") 9 >>> EditDistance().min_dist_bottom_up("", "") 0 """ self.word1 = word1 self.word2 = word2 m = len(word1) n = len(word2) self.dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)] for i in range(m + 1): for j in range(n + 1): if i == 0: # first string is empty self.dp[i][j] = j elif j == 0: # second string is empty self.dp[i][j] = i elif word1[i - 1] == word2[j - 1]: # last characters are equal self.dp[i][j] = self.dp[i - 1][j - 1] else: insert = self.dp[i][j - 1] delete = self.dp[i - 1][j] replace = self.dp[i - 1][j - 1] self.dp[i][j] = 1 + min(insert, delete, replace) return self.dp[m][n] if __name__ == "__main__": solver = EditDistance() print("****************** Testing Edit Distance DP Algorithm ******************") print() S1 = input("Enter the first string: ").strip() S2 = input("Enter the second string: ").strip() print() print(f"The minimum edit distance is: {solver.min_dist_top_down(S1, S2)}") print(f"The minimum edit distance is: {solver.min_dist_bottom_up(S1, S2)}") print() print("*************** End of Testing Edit Distance DP Algorithm ***************") |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |