Khoảng cách sửa đổi (Edit distance)

Bài toán quy hoạch động có nhiều loại, trong đó có bài Khoảng cách sửa đổi (Edit distance)

Để hiểu nhưng bài này nó chạy như thế nào khá khó với người học, có nhiều Youtube cũng như các Blog đã trình bày lý thuyết và cách làm.

Trong bài này Tui nói lại phần lý thuyết, giải thuật và viết chương trình tự giải bài Edit distance. Từ đó các bạn sẽ tự học được vì phần mềm này sẽ giải thích chi tiết từng bước.

Định nghĩa: Cho hai xâu kí tứ S[1,2,…,m] và T[1,2,…,n] có chiều dài lần lượt là m và n. Khoảng cách sửa đổi giữa hai xâu, là số nhỏ nhất các thao tác cơ bản: chèn một kí tự, xóa một kí tự, và đổi một kí tự sang kí tự khác, để biến chuỗi này thành chuỗi kia.

• Chèn (insert) một ký tự (ví dụ: ABC → ABCA)
• Xóa (remove) một ký tự (ví dụ: ABC → AC)
• Sửa đổi (modify) một ký tự (ví dụ: ABC → ADC)

Ví dụ: Ta có thể sửa đổi FOOD và MONEY sử dụng 4 thao tác (trong số 3 thao tác cơ bản trong định nghĩa) như sau:

FOOD → MOOD → MOND → MONED → MONEY

Do đó khoảng cách sửa đổi giữa hai xâu này là không quá 4. Thực tế 4 cũng là khoảng cách sửa đổi giữa hai xâu này.

Mã giả:

Input: Chuỗi S có m ký tự, Chuỗi T có n ký tự.
Output: Trả về chi tiết khoảng cách chỉnh sửa tối thiểu khi chuyển S qua T. Với E[m,n] là mảng kết quả trả về.

1. For i=0 to m E[i,0]=i// khởi tạo ban đầu cho các cột =0
2. For j=0 to n E[0,j]=j// Khởi tạo ban đầu cho các dòng 0
3. for i=1 to m
4.     for j=1 to n
5.          E[i,j] = min{E[i,j-1]+1, E[i-1,j]+1, E[i-1,j-1]+α}
6. return E[m,n]

α được tính như thế nào? α =0 khi S[i] = T[j], α =1 khi S[i] != T[j]

Vì cơ sở lý thuyết là giống nhau, cách giải thích giống nhau nên Tui không muốn mất thời gian viết lại.

Các bạn có thể đọc thêm các bài viết về Tiếng Việt tại đây : https://giaithuatlaptrinh.github.io/Quy-ho%E1%BA%A1ch-%C4%91%E1%BB%99ng-2/

hoặc tại đây https://vallicon.com/post/kho%E1%BA%A3ng-c%C3%A1ch-ch%E1%BB%89nh-s%E1%BB%ADa-(edit-distance)-mRX2Y5VEdeo

bài Tiếng Anh tại đây https://en.wikipedia.org/wiki/Levenshtein_distance

Dưới đây Tui sẽ giải thích chi tiết giải thuật Edit Distance nó chạy (dựa vào mã giả gồm 6 dòng lệnh ở trên.

Ví dụ: S= “strong”, T=”stone”. Hãy chạy từng bước quá trình chuyển S qua T

Khở tạo bảng tính khoảng cách ban đầu:

Line 1. For i = 0 to m E[i, 0] = i// khởi tạo cột bằng 0

Line 2. For j = 0 to n E[0, j] = j// khởi tạo dòng bằng 0

E	T	ε	s	t	o	n	e
S		0	1	2	3	4	5
ε	0	0	1	2	3	4	5
s	1	1
t	2	2
r	3	3
o	4	4
n	5	5
g	6	6

Chạy mã lệnh từ dòng 3-> tới dòng 5

3. for i = 1 to m
4.   for j = 1 to n
5.    E[i, j] = min{ E[i, j – 1] + 1, E[i – 1, j] + 1, E[i – 1, j – 1] + α}

Khi i = 1:

E[1, 1]=min{E[1,0] + 1, E[0,1] + 1, E[0, 0]+α}=>min{1 + 1,1 + 1,0+0}=0, α=0 vì S[1]=T[1]=’s’

E[1, 2]=min{E[1,1] + 1, E[0,2] + 1, E[0, 1]+α}=>min{0 + 1,2 + 1,1+1}=1, α=1 vì S[1]=’s’ ≠ T[2]=’t’

E[1, 3]=min{E[1,2] + 1, E[0,3] + 1, E[0, 2]+α}=>min{1 + 1,3 + 1,2+1}=2, α=1 vì S[1]=’s’ ≠ T[3]=’o’

E[1, 4]=min{E[1,3] + 1, E[0,4] + 1, E[0, 3]+α}=>min{2 + 1,4 + 1,3+1}=3, α=1 vì S[1]=’s’ ≠ T[4]=’n’

E[1, 5]=min{E[1,4] + 1, E[0,5] + 1, E[0, 4]+α}=>min{3 + 1,5 + 1,4+1}=4, α=1 vì S[1]=’s’ ≠ T[5]=’e’

Ta cập nhật lại bảng tính khoảng cách:

E	T	ε	s	t	o	n	e
S		0	1	2	3	4	5
ε	0	0	1	2	3	4	5
s	1	1	0	1	2	3	4
t	2	2
r	3	3
o	4	4
n	5	5
g	6	6

Khi i = 2:

E[2, 1]=min{E[2,0] + 1, E[1,1] + 1, E[1, 0]+α}=>min{2 + 1,0 + 1,1+1}=1, α=1 vì S[2]=’t’ ≠ T[1]=’s’

E[2, 2]=min{E[2,1] + 1, E[1,2] + 1, E[1, 1]+α}=>min{1 + 1,1 + 1,0+0}=0, α=0 vì S[2]=T[2]=’t’

E[2, 3]=min{E[2,2] + 1, E[1,3] + 1, E[1, 2]+α}=>min{0 + 1,2 + 1,1+1}=1, α=1 vì S[2]=’t’ ≠ T[3]=’o’

E[2, 4]=min{E[2,3] + 1, E[1,4] + 1, E[1, 3]+α}=>min{1 + 1,3 + 1,2+1}=2, α=1 vì S[2]=’t’ ≠ T[4]=’n’

E[2, 5]=min{E[2,4] + 1, E[1,5] + 1, E[1, 4]+α}=>min{2 + 1,4 + 1,3+1}=3, α=1 vì S[2]=’t’ ≠ T[5]=’e’

Ta cập nhật lại bảng tính khoảng cách:

E	T	ε	s	t	o	n	e
S		0	1	2	3	4	5
ε	0	0	1	2	3	4	5
s	1	1	0	1	2	3	4
t	2	2	1	0	1	2	3
r	3	3
o	4	4
n	5	5
g	6	6

Khi i = 3:

E[3, 1]=min{E[3,0] + 1, E[2,1] + 1, E[2, 0]+α}=>min{3 + 1,1 + 1,2+1}=2, α=1 vì S[3]=’r’ ≠ T[1]=’s’

E[3, 2]=min{E[3,1] + 1, E[2,2] + 1, E[2, 1]+α}=>min{2 + 1,0 + 1,1+1}=1, α=1 vì S[3]=’r’ ≠ T[2]=’t’

E[3, 3]=min{E[3,2] + 1, E[2,3] + 1, E[2, 2]+α}=>min{1 + 1,1 + 1,0+1}=1, α=1 vì S[3]=’r’ ≠ T[3]=’o’

E[3, 4]=min{E[3,3] + 1, E[2,4] + 1, E[2, 3]+α}=>min{1 + 1,2 + 1,1+1}=2, α=1 vì S[3]=’r’ ≠ T[4]=’n’

E[3, 5]=min{E[3,4] + 1, E[2,5] + 1, E[2, 4]+α}=>min{2 + 1,3 + 1,2+1}=3, α=1 vì S[3]=’r’ ≠ T[5]=’e’

Ta cập nhật lại bảng tính khoảng cách:

E	T	ε	s	t	o	n	e
S		0	1	2	3	4	5
ε	0	0	1	2	3	4	5
s	1	1	0	1	2	3	4
t	2	2	1	0	1	2	3
r	3	3	2	1	1	2	3
o	4	4
n	5	5
g	6	6

Khi i = 4:

E[4, 1]=min{E[4,0] + 1, E[3,1] + 1, E[3, 0]+α}=>min{4 + 1,2 + 1,3+1}=3, α=1 vì S[4]=’o’ ≠ T[1]=’s’

E[4, 2]=min{E[4,1] + 1, E[3,2] + 1, E[3, 1]+α}=>min{3 + 1,1 + 1,2+1}=2, α=1 vì S[4]=’o’ ≠ T[2]=’t’

E[4, 3]=min{E[4,2] + 1, E[3,3] + 1, E[3, 2]+α}=>min{2 + 1,1 + 1,1+0}=1, α=0 vì S[4]=T[3]=’o’

E[4, 4]=min{E[4,3] + 1, E[3,4] + 1, E[3, 3]+α}=>min{1 + 1,2 + 1,1+1}=2, α=1 vì S[4]=’o’ ≠ T[4]=’n’

E[4, 5]=min{E[4,4] + 1, E[3,5] + 1, E[3, 4]+α}=>min{2 + 1,3 + 1,2+1}=3, α=1 vì S[4]=’o’ ≠ T[5]=’e’

Ta cập nhật lại bảng tính khoảng cách:

E	T	ε	s	t	o	n	e
S		0	1	2	3	4	5
ε	0	0	1	2	3	4	5
s	1	1	0	1	2	3	4
t	2	2	1	0	1	2	3
r	3	3	2	1	1	2	3
o	4	4	3	2	1	2	3
n	5	5
g	6	6

Khi i = 5:

E[5, 1]=min{E[5,0] + 1, E[4,1] + 1, E[4, 0]+α}=>min{5 + 1,3 + 1,4+1}=4, α=1 vì S[5]=’n’ ≠ T[1]=’s’

E[5, 2]=min{E[5,1] + 1, E[4,2] + 1, E[4, 1]+α}=>min{4 + 1,2 + 1,3+1}=3, α=1 vì S[5]=’n’ ≠ T[2]=’t’

E[5, 3]=min{E[5,2] + 1, E[4,3] + 1, E[4, 2]+α}=>min{3 + 1,1 + 1,2+1}=2, α=1 vì S[5]=’n’ ≠ T[3]=’o’

E[5, 4]=min{E[5,3] + 1, E[4,4] + 1, E[4, 3]+α}=>min{2 + 1,2 + 1,1+0}=1, α=0 vì S[5]=T[4]=’n’

E[5, 5]=min{E[5,4] + 1, E[4,5] + 1, E[4, 4]+α}=>min{1 + 1,3 + 1,2+1}=2, α=1 vì S[5]=’n’ ≠ T[5]=’e’

Ta cập nhật lại bảng tính khoảng cách:

E	T	ε	s	t	o	n	e
S		0	1	2	3	4	5
ε	0	0	1	2	3	4	5
s	1	1	0	1	2	3	4
t	2	2	1	0	1	2	3
r	3	3	2	1	1	2	3
o	4	4	3	2	1	2	3
n	5	5	4	3	2	1	2
g	6	6

Khi i = 6:

E[6, 1]=min{E[6,0] + 1, E[5,1] + 1, E[5, 0]+α}=>min{6 + 1,4 + 1,5+1}=5, α=1 vì S[6]=’g’ ≠ T[1]=’s’

E[6, 2]=min{E[6,1] + 1, E[5,2] + 1, E[5, 1]+α}=>min{5 + 1,3 + 1,4+1}=4, α=1 vì S[6]=’g’ ≠ T[2]=’t’

E[6, 3]=min{E[6,2] + 1, E[5,3] + 1, E[5, 2]+α}=>min{4 + 1,2 + 1,3+1}=3, α=1 vì S[6]=’g’ ≠ T[3]=’o’

E[6, 4]=min{E[6,3] + 1, E[5,4] + 1, E[5, 3]+α}=>min{3 + 1,1 + 1,2+1}=2, α=1 vì S[6]=’g’ ≠ T[4]=’n’

E[6, 5]=min{E[6,4] + 1, E[5,5] + 1, E[5, 4]+α}=>min{2 + 1,2 + 1,1+1}=2, α=1 vì S[6]=’g’ ≠ T[5]=’e’

Ta cập nhật lại bảng tính khoảng cách:

E	T	ε	s	t	o	n	e
S		0	1	2	3	4	5
ε	0	0	1	2	3	4	5
s	1	1	0	1	2	3	4
t	2	2	1	0	1	2	3
r	3	3	2	1	1	2	3
o	4	4	3	2	1	2	3
n	5	5	4	3	2	1	2
g	6	6	5	4	3	2	2

Kết thúc quá trình tính khoảng cách chỉnh sửa! Ta được kết quả cuối cùng khi chuyển từ S (Strong) qua T (Stone):

E	T	ε	s	t	o	n	e
S		0	1	2	3	4	5
ε	0	0	1	2	3	4	5
s	1	1	0	1	2	3	4
t	2	2	1	0	1	2	3
r	3	3	2	1	1	2	3
o	4	4	3	2	1	2	3
n	5	5	4	3	2	1	2
g	6	6	5	4	3	2	2

File exe bấm chạy để ra giảng giải chi tiết đáp án:

https://www.mediafire.com/file/9hhq3zo3rnlk5b8/EditDistance.exe/file

File mã nguồn đọc chơi (chắc là không hiểu):

https://www.mediafire.com/file/un5uiksmns54q4q/EditDistance.rar/file

Nếu cảm thấy hữu ích thì hãy Ủng hộ Tui 1 ly cafe sữa đá lề đường 

STK: 0101146302
Chủ TK: Trần Duy Thanh
Ngân Hàng: Đông Á, chi nhánh Gò Vấp