Chỉnh sửa python
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 đặtCá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 [email protected]: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ừ difflibNgoài các phương thức sm.distance() sm.matches() Ngay cả khi sự liên kết của hai chuỗi giống hệt với git clone [email protected]:belambert/edit_distance.git cd edit_distance python setup.py install0 và git clone [email protected]: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
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 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) |