Tôi cần một cách để tính khoảng cách chỉnh sửa giữa các chuỗi trong Python. Tôi không thể tìm thấy bất kỳ thư viện thích hợp nào làm việc này nên tôi đã viết thư viện của riêng mình. Dường như có rất nhiều thư viện khoảng cách chỉnh sửa có sẵn để tính toán khoảng cách chỉnh sửa giữa hai chuỗi, nhưng không phải giữa hai chuỗi
Điều này được viết hoàn toàn bằng Python. Việc triển khai này có thể được tối ưu hóa để nhanh hơn trong Python. Và có lẽ có thể nhanh hơn nhiều nếu được thực hiện trong C
API thư viện được mô hình hóa sau difflib. trình so khớp trình tự. Điều này rất giống với difflib, ngoại trừ mô-đun này tính toán khoảng cách chỉnh sửa [khoảng cách Levenshtein] thay vì phương pháp Ratcliff và Oberhelp mà difflib của Python sử dụng. difflib "không tạo ra các trình tự chỉnh sửa tối thiểu, nhưng có xu hướng tạo ra các kết quả khớp 'có vẻ phù hợp' với mọi người. "
Nếu bạn thấy thư viện này hữu ích hoặc có bất kỳ đề xuất nào, vui lòng gửi tin nhắn cho tôi
Cài đặt và gỡ cài đặt
Cách dễ nhất để cài đặt là sử dụng pip
pip install edit_distance
Ngoài ra, bạn có thể sao chép git repo này và cài đặt bằng distutils
git clone git@github.com:belambert/edit_distance.git cd edit_distance python setup.py install
Để gỡ cài đặt bằng pip
pip uninstall edit_distance
sử dụng API
Để xem các ví dụ về cách sử dụng, hãy xem tài liệu difflib. Tài liệu cấp API bổ sung có sẵn trên ReadTheDocs
Điều này yêu cầu Python 2. 7+ vì nó sử dụng argparse cho giao diện dòng lệnh. Phần còn lại của mã sẽ ổn với các phiên bản Python trước đó
Ví dụ sử dụng API
import edit_distance ref = [1, 2, 3, 4] hyp = [1, 2, 4, 5, 6] sm = edit_distance.SequenceMatcher[a=ref, b=hyp] sm.get_opcodes[] sm.ratio[] sm.get_matching_blocks[]
Sự khác biệt từ difflib
Ngoài các phương thức SequenceMatcher, các phương thức distance[] và matches[] được cung cấp để tính toán khoảng cách chỉnh sửa và số lượng khớp
sm.distance[] sm.matches[]
Ngay cả khi sự liên kết của hai chuỗi giống hệt với difflib, thì
git clone git@github.com:belambert/edit_distance.git cd edit_distance python setup.py install0 và
git clone git@github.com:belambert/edit_distance.git cd edit_distance python setup.py install1 có thể trả về các chuỗi hơi khác nhau. Các mã lệnh do thư viện này trả về đại diện cho các hoạt động của từng ký tự riêng lẻ và do đó không bao giờ được trải dài trên hai ký tự trở lên
Cũng có thể tính toán số trận đấu tối đa thay vì số lần chỉnh sửa tối thiểu
sm = edit_distance.SequenceMatcher[a=ref, b=hyp,
action_function=edit_distance.highest_match_action]
ghi chú
Điều này không triển khai các tính năng khớp 'rác' trong difflib
Đóng góp và quy tắc ứng xử
Đối với đóng góp, tốt nhất là Github phát hành và kéo yêu cầu. Thử nghiệm thích hợp và tài liệu được đề xuất
Để hiểu nhưng bài này nó chạy như thế nào thì hơi 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 viết 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 Chỉnh sửa khoảng cách. 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ủa các thao tác cơ bản. thêm 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 [chèn] một ký tự [ví dụ. ABC → ABCA]
- Delete [loại bỏ] một ký tự [ví dụ. ABC → AC]
- Sửa đổi [sửa đổi] một ký tự [ví dụ. ABC → ADC]
Ví dụ. Ta có thể sửa đổi THỰC PHẨM VÀ TIỀN bằng cách sử dụng 4 thao tác [trong số 3 thao tác cơ bản trong định nghĩa] như sau
THỰC PHẨM → TÂM TRẠNG → TÂM → TIỀN → TIỀN
Khoảng cách sửa đổi giữa hai xâu này không quá 4. Thực tế 4 cũng là khoảng cách giữa hai xâu này
Mã giả
________số 8_______α được tính như thế nào? . = T[j]
Vì cơ sở lý thuyết 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. // vi. wikipedia. org/wiki/Levenshtein_ distance
Dưới đây Tui sẽ giải thích chi tiết giải thuật Edit Khoảng cách nó chạy [dựa vào mã giả bao gồm 6 dòng lệnh ở trên
Ví dụ. S= “mạnh”, T=”đá”. Please run each step too process Squa T
Khởi tạo bảng tính cách ban đầu
Dòng 1. For i = 0 to m E[i, 0] = i//khởi tạo cột bằng 0
Dòng 2. For j = 0 to n E[0, j] = j//khởi tạo dòng bằng 0
ETεstoneS 012345ε0012345s11 t22 r33 o44 n55 g66Run code from line 3-> to line 5
3. cho tôi = 1 đến m
4. cho j = 1 đến 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+
E[1, 2]=min{E[1,1] + 1, E[0,2] + 1, E[0, 1]+α}=>min{0 + 1,2 + 1,1+
E[1, 3]=min{E[1,2] + 1, E[0,3] + 1, E[0, 2]+α}=>min{1 + 1,3 + 1,2+
E[1, 4]=min{E[1,3] + 1, E[0,4] + 1, E[0, 3]+α}=>min{2 + 1,4 + 1,3+
E[1, 5]=min{E[1,4] + 1, E[0,5] + 1, E[0, 4]+α}=>min{3 + 1,5 + 1,4+
Ta cập nhật lại khoảng cách bảng tính
ETεstoneS 012345ε0012345s1101234t22 r33 o44 n55 g66Khi tôi = 2
E[2, 1]=min{E[2,0] + 1, E[1,1] + 1, E[1, 0]+α}=>min{2 + 1,0 + 1,1+
E[2, 2]=min{E[2,1] + 1, E[1,2] + 1, E[1, 1]+α}=>min{1 + 1,1 + 1,0+
E[2, 3]=min{E[2,2] + 1, E[1,3] + 1, E[1, 2]+α}=>min{0 + 1,2 + 1,1+
E[2, 4]=min{E[2,3] + 1, E[1,4] + 1, E[1, 3]+α}=>min{1 + 1,3 + 1,2+
E[2, 5]=min{E[2,4] + 1, E[1,5] + 1, E[1, 4]+α}=>min{2 + 1,4 + 1,3+
Ta cập nhật lại khoảng cách bảng tính
ETεstoneS 012345ε0012345s1101234t2210123r33 o44 n55 g66Khi tôi = 3
E[3, 1]=min{E[3,0] + 1, E[2,1] + 1, E[2, 0]+α}=>min{3 + 1,1 + 1,2+
E[3, 2]=min{E[3,1] + 1, E[2,2] + 1, E[2, 1]+α}=>min{2 + 1,0 + 1,1+
E[3, 3]=min{E[3,2] + 1, E[2,3] + 1, E[2, 2]+α}=>min{1 + 1,1 + 1,0+
E[3, 4]=min{E[3,3] + 1, E[2,4] + 1, E[2, 3]+α}=>min{1 + 1,2 + 1,1+
E[3, 5]=min{E[3,4] + 1, E[2,5] + 1, E[2, 4]+α}=>min{2 + 1,3 + 1,2+
Ta cập nhật lại khoảng cách bảng tính
ETεstoneS 012345ε0012345s1101234t2210123r3321123o44 n55 g66Khi tôi = 4
E[4, 1]=min{E[4,0] + 1, E[3,1] + 1, E[3, 0]+α}=>min{4 + 1,2 + 1,3+
E[4, 2]=min{E[4,1] + 1, E[3,2] + 1, E[3, 1]+α}=>min{3 + 1,1 + 1,2+
E[4, 3]=min{E[4,2] + 1, E[3,3] + 1, E[3, 2]+α}=>min{2 + 1,1 + 1,1+
E[4, 4]=min{E[4,3] + 1, E[3,4] + 1, E[3, 3]+α}=>min{1 + 1,2 + 1,1+
E[4, 5]=min{E[4,4] + 1, E[3,5] + 1, E[3, 4]+α}=>min{2 + 1,3 + 1,2+
Ta cập nhật lại khoảng cách bảng tính
ETεstoneS 012345ε0012345s1101234t2210123r3321123o4432123n55 g66Khi tôi = 5
E[5, 1]=min{E[5,0] + 1, E[4,1] + 1, E[4, 0]+α}=>min{5 + 1,3 + 1,4+
E[5, 2]=min{E[5,1] + 1, E[4,2] + 1, E[4, 1]+α}=>min{4 + 1,2 + 1,3+
E[5, 3]=min{E[5,2] + 1, E[4,3] + 1, E[4, 2]+α}=>min{3 + 1,1 + 1,2+
E[5, 4]=min{E[5,3] + 1, E[4,4] + 1, E[4, 3]+α}=>min{2 + 1,2 + 1,1+
E[5, 5]=min{E[5,4] + 1, E[4,5] + 1, E[4, 4]+α}=>min{1 + 1,3 + 1,2+
Ta cập nhật lại khoảng cách bảng tính
ETεstoneS 012345ε0012345s1101234t2210123r3321123o4432123n5543212g66Khi tôi = 6
E[6, 1]=min{E[6,0] + 1, E[5,1] + 1, E[5, 0]+α}=>min{6 + 1,4 + 1,5+
E[6, 2]=min{E[6,1] + 1, E[5,2] + 1, E[5, 1]+α}=>min{5 + 1,3 + 1,4+
E[6, 3]=min{E[6,2] + 1, E[5,3] + 1, E[5, 2]+α}=>min{4 + 1,2 + 1,3+
E[6, 4]=min{E[6,3] + 1, E[5,4] + 1, E[5, 3]+α}=>min{3 + 1,1 + 1,2+
E[6, 5]=min{E[6,4] + 1, E[5,5] + 1, E[5, 4]+α}=>min{2 + 1,2 + 1,1+
Ta cập nhật lại khoảng cách bảng tính
ETεstoneS 012345ε0012345s1101234t2210123r3321123o4432123n5543212g6654322Kết thúc quá trình chỉnh sửa khoảng cách tính toán. Ta được kết quả cuối cùng khi chuyển từ S [Strong] qua T [Stone]