Skip to content

Commit fdf6ac2

Browse files
oldherdoldherd
committed
add algo6.1~algo6.5
1 parent fe0a3a9 commit fdf6ac2

File tree

1 file changed

+315
-0
lines changed

1 file changed

+315
-0
lines changed

‎第六章代码.ipynb

Lines changed: 315 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,315 @@
1+
{
2+
"cells": [
3+
{
4+
"cell_type": "markdown",
5+
"metadata": {},
6+
"source": [
7+
"# 第六章代码"
8+
]
9+
},
10+
{
11+
"cell_type": "markdown",
12+
"metadata": {},
13+
"source": [
14+
"## 算法 6.1"
15+
]
16+
},
17+
{
18+
"cell_type": "code",
19+
"execution_count": 14,
20+
"metadata": {},
21+
"outputs": [
22+
{
23+
"name": "stdout",
24+
"output_type": "stream",
25+
"text": [
26+
"[[0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 2], [0, 1, 2, 2, 2, 2], [0, 1, 2, 2, 3, 3], [0, 1, 2, 2, 3, 4], [0, 1, 2, 2, 3, 4]]\n",
27+
"[['', '', '', '', '', ''], ['', 'LU', 'L', 'L', 'L', 'LU'], ['', 'LU', 'L', 'L', 'L', 'LU'], ['', 'U', 'LU', 'L', 'L', 'L'], ['', 'U', 'U', 'L', 'LU', 'L'], ['', 'LU', 'U', 'L', 'U', 'LU'], ['', 'U', 'LU', 'L', 'U', 'U']]\n"
28+
]
29+
}
30+
],
31+
"source": [
32+
"def longest_common_subsequence(sa : list, sb : list):\n",
33+
" n = len(sa)\n",
34+
" m = len(sb)\n",
35+
" C = [[0 for i in range(m + 1)] for _ in range(n + 1)]\n",
36+
" rec = [[\"\" for i in range(m + 1)] for _ in range(n + 1)]\n",
37+
" for i in range(1, n + 1):\n",
38+
" for j in range(1, m + 1):\n",
39+
" if sa[i - 1] == sb[j - 1]:\n",
40+
" C[i][j] = C[i - 1][j - 1] + 1\n",
41+
" rec[i][j] = \"LU\"\n",
42+
" elif C[i - 1][j] > C[i][j - 1]:\n",
43+
" C[i][j] = C[i - 1][j]\n",
44+
" rec[i][j] = \"U\"\n",
45+
" else:\n",
46+
" C[i][j] = C[i][j - 1]\n",
47+
" rec[i][j] = \"L\"\n",
48+
" return C, rec\n",
49+
"\n",
50+
"if __name__ == '__main__':\n",
51+
" seqa = [1, 1, 4, 5, 1, 4]\n",
52+
" seqb = [1, 4, 3, 5, 1]\n",
53+
" C, rec = longest_common_subsequence(seqa, seqb)\n",
54+
" print(C)\n",
55+
" print(rec)"
56+
]
57+
},
58+
{
59+
"cell_type": "markdown",
60+
"metadata": {},
61+
"source": [
62+
"## 算法 6.2"
63+
]
64+
},
65+
{
66+
"cell_type": "code",
67+
"execution_count": 17,
68+
"metadata": {},
69+
"outputs": [
70+
{
71+
"name": "stdout",
72+
"output_type": "stream",
73+
"text": [
74+
"[1, 4, 5, 1]\n"
75+
]
76+
}
77+
],
78+
"source": [
79+
"def print_LCS(sa : list, rec, i, j):\n",
80+
" if i == 0 or j == 0:\n",
81+
" return []\n",
82+
" if rec[i][j].__eq__(\"LU\"):\n",
83+
" cur = print_LCS(sa, rec, i - 1, j - 1)\n",
84+
" cur.append(sa[i - 1])\n",
85+
" return cur\n",
86+
" elif rec[i][j].__eq__(\"U\"):\n",
87+
" return print_LCS(sa, rec, i - 1, j)\n",
88+
" else:\n",
89+
" return print_LCS(sa, rec, i, j - 1)\n",
90+
"\n",
91+
"### algo6.1 for generation of test data \n",
92+
"def longest_common_subsequence(sa : list, sb : list):\n",
93+
" n = len(sa)\n",
94+
" m = len(sb)\n",
95+
" C = [[0 for i in range(m + 1)] for _ in range(n + 1)]\n",
96+
" rec = [[\"\" for i in range(m + 1)] for _ in range(n + 1)]\n",
97+
" for i in range(1, n + 1):\n",
98+
" for j in range(1, m + 1):\n",
99+
" if sa[i - 1] == sb[j - 1]:\n",
100+
" C[i][j] = C[i - 1][j - 1] + 1\n",
101+
" rec[i][j] = \"LU\"\n",
102+
" elif C[i - 1][j] > C[i][j - 1]:\n",
103+
" C[i][j] = C[i - 1][j]\n",
104+
" rec[i][j] = \"U\"\n",
105+
" else:\n",
106+
" C[i][j] = C[i][j - 1]\n",
107+
" rec[i][j] = \"L\"\n",
108+
" return C, rec\n",
109+
"\n",
110+
"if __name__ == '__main__':\n",
111+
" seqa = [1, 1, 4, 5, 1, 4]\n",
112+
" seqb = [1, 4, 3, 5, 1]\n",
113+
" C, rec = longest_common_subsequence(seqa, seqb)\n",
114+
" print(print_LCS(seqa, rec, len(seqa), len(seqb)))"
115+
]
116+
},
117+
{
118+
"cell_type": "markdown",
119+
"metadata": {},
120+
"source": [
121+
"## 算法 6.3"
122+
]
123+
},
124+
{
125+
"cell_type": "code",
126+
"execution_count": 18,
127+
"metadata": {},
128+
"outputs": [
129+
{
130+
"name": "stdout",
131+
"output_type": "stream",
132+
"text": [
133+
"[[0, 1, 2, 2, 3, 4], [0, 1, 2, 2, 3, 4]]\n",
134+
"[['', '', '', '', '', ''], ['', 'LU', 'L', 'L', 'L', 'LU'], ['', 'LU', 'L', 'L', 'L', 'LU'], ['', 'U', 'LU', 'L', 'L', 'L'], ['', 'U', 'U', 'L', 'LU', 'L'], ['', 'LU', 'U', 'L', 'U', 'LU'], ['', 'U', 'LU', 'L', 'U', 'U']]\n"
135+
]
136+
}
137+
],
138+
"source": [
139+
"def LCS_scrolling_array(sa : list, sb : list):\n",
140+
" n = len(sa)\n",
141+
" m = len(sb)\n",
142+
" C = [[0 for i in range(m + 1)] for _ in range(2)]\n",
143+
" rec = [[\"\" for i in range(m + 1)] for _ in range(n + 1)]\n",
144+
" for i in range(1, n + 1):\n",
145+
" for j in range(1, m + 1):\n",
146+
" id = i & 1\n",
147+
" if sa[i - 1] == sb[j - 1]:\n",
148+
" C[id][j] = C[id ^ 1][j - 1] + 1\n",
149+
" rec[i][j] = \"LU\"\n",
150+
" elif C[id ^ 1][j] > C[id][j - 1]:\n",
151+
" C[id][j] = C[id ^ 1][j]\n",
152+
" rec[i][j] = \"U\"\n",
153+
" else:\n",
154+
" C[id][j] = C[id][j - 1]\n",
155+
" rec[i][j] = \"L\"\n",
156+
" return C, rec\n",
157+
"\n",
158+
"if __name__ == '__main__':\n",
159+
" seqa = [1, 1, 4, 5, 1, 4]\n",
160+
" seqb = [1, 4, 3, 5, 1]\n",
161+
" C, rec = LCS_scrolling_array(seqa, seqb)\n",
162+
" print(C)\n",
163+
" print(rec)"
164+
]
165+
},
166+
{
167+
"cell_type": "markdown",
168+
"metadata": {},
169+
"source": [
170+
"## 算法 6.4"
171+
]
172+
},
173+
{
174+
"cell_type": "code",
175+
"execution_count": 22,
176+
"metadata": {},
177+
"outputs": [
178+
{
179+
"name": "stdout",
180+
"output_type": "stream",
181+
"text": [
182+
"2\n",
183+
"[['L', 'L', 'L', 'L', 'L', 'L', 'L', 'L'], ['U', 'LU', 'L', 'L', 'L', 'L', 'L', 'L'], ['U', 'U', 'LU', 'L', 'L', 'L', 'L', 'L'], ['U', 'U', 'U', 'LU', 'L', 'L', 'L', 'L'], ['U', 'U', 'U', 'U', 'LU', 'L', 'L', 'L'], ['U', 'U', 'U', 'U', 'LU', 'L', 'L', 'L'], ['U', 'U', 'U', 'U', 'U', 'LU', 'L', 'L'], ['U', 'U', 'U', 'U', 'U', 'U', 'LU', 'L'], ['U', 'U', 'U', 'U', 'U', 'U', 'U', 'LU']]\n"
184+
]
185+
}
186+
],
187+
"source": [
188+
"def minimal_edit_distance(s : str, t : str):\n",
189+
" n = len(s)\n",
190+
" m = len(t)\n",
191+
" D = [[0 for _ in range(m + 1)] for __ in range(n + 1)]\n",
192+
" rec = [[0 for _ in range(m + 1)] for __ in range(n + 1)]\n",
193+
" for i in range(n + 1):\n",
194+
" D[i][0] = i\n",
195+
" rec[i][0] = \"U\"\n",
196+
" for j in range(m + 1):\n",
197+
" D[0][j] = j\n",
198+
" rec[0][j] = \"L\"\n",
199+
" \n",
200+
" for i in range(1, n + 1):\n",
201+
" for j in range(1, m + 1):\n",
202+
" ansDel = D[i - 1][j] + 1\n",
203+
" ansIns = D[i][j - 1] + 1\n",
204+
" ansRep = D[i - 1][j - 1] + (0 if s[i - 1] == t[j - 1] else 1)\n",
205+
" D[i][j] = min(ansDel, ansIns, ansRep)\n",
206+
" if D[i][j] == ansDel:\n",
207+
" rec[i][j] = \"U\"\n",
208+
" elif D[i][j] == ansIns:\n",
209+
" rec[i][j] = \"L\"\n",
210+
" else:\n",
211+
" rec[i][j] = \"LU\"\n",
212+
" return D[n][m], rec\n",
213+
"\n",
214+
"if __name__ == '__main__':\n",
215+
" s1 = \"kittcjen\"\n",
216+
" s2 = \"kitchen\"\n",
217+
" ans, rec = minimal_edit_distance(s1, s2)\n",
218+
" print(ans)\n",
219+
" print(rec)"
220+
]
221+
},
222+
{
223+
"cell_type": "markdown",
224+
"metadata": {},
225+
"source": [
226+
"## 算法 6.5"
227+
]
228+
},
229+
{
230+
"cell_type": "code",
231+
"execution_count": 25,
232+
"metadata": {},
233+
"outputs": [
234+
{
235+
"name": "stdout",
236+
"output_type": "stream",
237+
"text": [
238+
"delete t.\n",
239+
"replace j with h.\n"
240+
]
241+
}
242+
],
243+
"source": [
244+
"def print_MED(rec, s, t, i, j):\n",
245+
" if i == 0 or j == 0:\n",
246+
" return None\n",
247+
" if rec[i][j] == \"LU\":\n",
248+
" print_MED(rec, s, t, i - 1, j - 1)\n",
249+
" if s[i - 1] != t[j - 1]:\n",
250+
" print(\"replace {} with {}.\".format(s[i - 1], t[j - 1])) \n",
251+
" elif rec[i][j] == \"U\":\n",
252+
" print_MED(rec, s, t, i - 1, j)\n",
253+
" print(\"delete {}.\".format(s[i - 1]))\n",
254+
" else:\n",
255+
" print_MED(rec, s, t, i, j - 1)\n",
256+
" print(\"insert {}.\".format(t[j - 1]))\n",
257+
"\n",
258+
"# algo6.4 for generation of the test data\n",
259+
"def minimal_edit_distance(s : str, t : str):\n",
260+
" n = len(s)\n",
261+
" m = len(t)\n",
262+
" D = [[0 for _ in range(m + 1)] for __ in range(n + 1)]\n",
263+
" rec = [[0 for _ in range(m + 1)] for __ in range(n + 1)]\n",
264+
" for i in range(n + 1):\n",
265+
" D[i][0] = i\n",
266+
" rec[i][0] = \"U\"\n",
267+
" for j in range(m + 1):\n",
268+
" D[0][j] = j\n",
269+
" rec[0][j] = \"L\"\n",
270+
" \n",
271+
" for i in range(1, n + 1):\n",
272+
" for j in range(1, m + 1):\n",
273+
" ansDel = D[i - 1][j] + 1\n",
274+
" ansIns = D[i][j - 1] + 1\n",
275+
" ansRep = D[i - 1][j - 1] + (0 if s[i - 1] == t[j - 1] else 1)\n",
276+
" D[i][j] = min(ansDel, ansIns, ansRep)\n",
277+
" if D[i][j] == ansDel:\n",
278+
" rec[i][j] = \"U\"\n",
279+
" elif D[i][j] == ansIns:\n",
280+
" rec[i][j] = \"L\"\n",
281+
" else:\n",
282+
" rec[i][j] = \"LU\"\n",
283+
" return D[n][m], rec\n",
284+
"\n",
285+
"\n",
286+
"if __name__ == '__main__':\n",
287+
" s1 = \"kittcjen\"\n",
288+
" s2 = \"kitchen\"\n",
289+
" ans, rec = minimal_edit_distance(s1, s2)\n",
290+
" print_MED(rec, s1, s2, len(s1), len(s2))"
291+
]
292+
}
293+
],
294+
"metadata": {
295+
"kernelspec": {
296+
"display_name": "Python 3",
297+
"language": "python",
298+
"name": "python3"
299+
},
300+
"language_info": {
301+
"codemirror_mode": {
302+
"name": "ipython",
303+
"version": 3
304+
},
305+
"file_extension": ".py",
306+
"mimetype": "text/x-python",
307+
"name": "python",
308+
"nbconvert_exporter": "python",
309+
"pygments_lexer": "ipython3",
310+
"version": "3.11.8"
311+
}
312+
},
313+
"nbformat": 4,
314+
"nbformat_minor": 2
315+
}

0 commit comments

Comments
 (0)