Triển khai một công cụ để so sánh các văn bản song song với Python cho phép có cái nhìn tổng quan hơn về sự khác biệt
Ảnh của Vanessa Giaconi [nguồn. bỏ đi]
Hiện tại tôi đang làm việc trên bộ lọc bảo mật cho văn bản bằng Python. Trong quá trình phát triển, tôi thường xuyên gặp phải một vấn đề; . Lần này, đã đến lúc giải quyết vấn đề này
thư viện difflib
Một số nghiên cứu trên internet đã nhanh chóng tiết lộ sự tồn tại của mô-đun difflib. Mô-đun mặc định này chứa một số trình trợ giúp để so sánh các chuỗi, như mảng và chuỗi. Tất cả các thuật toán để so sánh trình tự có sẵn với một vài dòng mã. Trong một khoảnh khắc ngắn ngủi, ý tưởng thực hiện thuật toán của riêng tôi thoáng qua tâm trí tôi, nhưng nhanh chóng biến mất
Cơ sở của mô-đun difflib là lớp SequenceMatcher. Lớp này thực hiện thuật toán so sánh trình tự. Nó bắt đầu bằng cách tìm các chuỗi chung lớn nhất trong cả hai chuỗi đầu vào và tiếp tục thực hiện nhiệm vụ này một cách đệ quy trên các phần khác cho đến khi không còn chuỗi nào. Do tính chất đệ quy của nó, thời gian thực hiện có thể trở thành bậc hai, tùy thuộc vào mức độ khác biệt trong chuỗi. Đối với mục tiêu của chúng tôi, hiệu suất này là chấp nhận được. Sẽ không dùng để so sách kinh văn, mỗi lần chỉ vài dòng thôi.
Tìm trình tự phù hợp
Để khớp các chuỗi, trước tiên chúng ta phải tạo một thể hiện của lớp SequenceMatcher. Hàm tạo lấy hai chuỗi để khớp làm tham số a và b. Các tham số để phát hiện rác không được sử dụng. Khi truyền chuỗi dưới dạng đối số, chuỗi được xem là một chuỗi ký tự. Trình so khớp sẽ tìm kiếm các chuỗi ký tự phù hợp
Lớp SequenceMatcher có một số cách trả về kết quả phù hợp, chẳng hạn như tìm kết quả khớp dài nhất, trả về các thao tác để chuyển đổi a thành b và trả về tất cả các kết quả tìm thấy. Chúng tôi sẽ sử dụng cái sau
Phương thức get_matching_blocks[] trả về một danh sách có thể lặp lại của tất cả các kết quả khớp, được sắp xếp theo sự xuất hiện của chúng từ đầu chuỗi. Mỗi trận đấu bao gồm vị trí của trận đấu trong chuỗi a, vị trí của trận đấu trong chuỗi b và độ dài của trận đấu. Trong ví dụ này, ba trận đấu được tìm thấy; . Nó là ”,” ờ. ”. Trận đấu được trả lại thứ tư là kết thúc của chuỗi
Vì vậy, chúng tôi đã tìm thấy tất cả các chuỗi phù hợp trong chuỗi. Nhưng để so sánh các văn bản, trận đấu cuối cùng “er. ” chỉ phù hợp với một phần của một từ. Tôi thích chỉ khớp với toàn bộ từ. Vì trình so khớp lấy các chuỗi [chuỗi là chuỗi ký tự trong Python], chúng ta nên thêm các từ vào trình so khớp. Vì vậy, hãy xem điều gì sẽ xảy ra nếu chúng ta mã hóa chuỗi trước khi thực hiện trình so khớp
Phương thức tokenize là một cách thực hiện thô sơ, rất đơn giản bằng cách tách chuỗi tại các khoảng trắng [‘ ’]. Kết quả đầy hứa hẹn, chỉ có chuỗi “It is” và “warm. Nó là” được trả lại. Từ khớp một phần không còn được tìm thấy. Kiểm tra một vài dòng văn bản đã nhanh chóng chỉ ra mã thông báo hạn chế do chỉ phân tách tại các khoảng trắng. Nó không thành công ở các dòng mới và các tab, vì vậy để đẩy mạnh trò chơi một chút, phần tách [] được thay thế bằng một biểu thức chính quy phân tách văn bản ở tất cả các khoảng trắng
Điều này mang lại kết quả tương tự như cách triển khai trước đó nhưng mạnh mẽ hơn với các khoảng trắng khác so với chính không gian đó
Cân bằng các chuỗi
Trình so khớp đang cho chúng tôi biết trình tự nào khớp và do đó cũng không khớp. Với thông tin này, có thể làm cho cả hai chuỗi bằng nhau, thêm các phần còn thiếu từ chuỗi thứ nhất sang chuỗi thứ hai và ngược lại
Nhìn vào ví dụ trên ta thấy dãy khớp đầu tiên bắt đầu từ vị trí 0 và có độ dài al là 2. Dãy khớp thứ hai bắt đầu ở vị trí 2 đối với dãy a và ở vị trí 3 đối với dãy b. Vậy dãy b chứa một phần không thuộc dãy a. Ta cần thêm vào dãy a một phần tử có cùng độ dài với phần tử của dãy b
Để xác định xem một phần tử có bị thiếu trong các chuỗi đã khớp hay không, chúng tôi xem xét vị trí bắt đầu của một chuỗi khớp, thêm độ dài của chuỗi đã khớp và xác định xem chuỗi tiếp theo có bắt đầu bằng tổng của cả hai không. Trong ví dụ dưới đây, trận đấu thứ hai bắt đầu ở vị trí 0 + 3 cho cả hai chuỗi, trận đấu thứ hai bắt đầu ở vị trí 4 cho chuỗi thứ nhất và ở vị trí 3 cho chuỗi thứ hai. Vì 0 + 3 bằng 3 nên dãy khớp 'chạm' nhau ở dãy thứ hai và dãy thứ nhất chứa một phần tử bổ sung giữa cả hai dãy đã khớp. Điều này có nghĩa là, một phần tử bổ sung sẽ được thêm vào chuỗi thứ hai
Hình ảnh của tác giả
Có ba khả năng. Chuỗi đầu tiên chứa một hoặc nhiều phần tử bổ sung, chuỗi thứ hai chứa các phần tử bổ sung hoặc cả hai chuỗi chứa các phần tử bổ sung. Trong trường hợp sau, có sự không phù hợp trong trình tự, e. g. các từ 'mùa hè' và 'mùa đông' trong ví dụ đầu tiên của chúng tôi
Chúng ta sẽ cân bằng dãy bằng cách thêm các phần tử bổ sung vào những nơi mà dãy khác có các phần tử không khớp với nhau. Các phần tử bổ sung này sẽ có cùng độ dài với phần tử chưa khớp và sẽ bao gồm các dấu gạch dưới
Phương thức lặp lại các kết quả tìm thấy [dòng 15] và đối với mỗi kết quả khớp sẽ kiểm tra xem nó có liền kề với kết quả khớp trước đó không. Nếu không đúng như vậy, các phần tử sẽ được thêm vào chuỗi khác để tạo đối sánh [dòng 16–23]. Sau khi thêm các phần tử còn thiếu, cả hai chuỗi được mở rộng với chuỗi phù hợp. Trước khi trả về các giá trị, chúng không được mã hóa
Từ 'không' không có trong chuỗi đầu tiên, được thêm dưới dạng dấu gạch dưới vào chuỗi đầu tiên. Các từ khác nhau 'mùa hè. ' và 'mùa đông. ' đều được thêm vào chuỗi khác. Nhìn thấy kết quả trên nhau đã cung cấp một cái nhìn tổng quan về sự khác biệt giữa cả hai chuỗi
Trực quan hóa sự khác biệt
Vì vậy, bây giờ chúng tôi có các chuỗi cân bằng và chúng tôi cần một cách thuận tiện để hình dung sự so sánh. Đối với các câu đơn, in chúng lên nhau là một giải pháp tuyệt vời. Đối với các văn bản dài hơn, so sánh song song sẽ thuận tiện hơn
Để so sánh song song, chúng ta cần ngắt các chuỗi thành từng đoạn có giới hạn bằng, e. g. 40 ký tự. Chúng tôi muốn ngắt giữa các từ, vì vậy một cửa sổ có thể chấp nhận được thêm vào e. g. 10 ký tự, nghĩa là chúng tôi sẽ bắt đầu tìm kiếm khoảng trắng sau 40 ký tự [dòng 5] và quay lại tối đa 10 ký tự để tìm khoảng trắng đầu tiên nhỏ hơn và gần nhất với 40 ký tự [dòng 7–8]
Hàm trả về một danh sách các chuỗi, không dài hơn 40. Vì việc cân bằng các chuỗi đã làm cho chúng có độ dài bằng nhau, chúng ta có thể sử dụng phương pháp này để ngắt cả hai chuỗi thành các chuỗi rác và các chuỗi này sẽ luôn chứa các từ giống nhau trên cùng một dòng. Chúng rất dễ so sánh. Chúng tôi có thể in các chuỗi bao gồm cả dấu gạch dưới với dấu gạch dưới bị xóa. Bằng cách loại bỏ dấu gạch dưới sau khi ngắt rồi nhập văn bản, chúng tôi đảm bảo rằng các từ giống nhau trong cả hai văn bản sẽ nằm trên cùng một dòng
Hàm so sánh [] lấy hai văn bản để so sánh làm tham số, theo sau là chiều rộng tùy chọn để hiển thị cạnh nhau, cửa sổ tìm khoảng trắng từ chiều rộng này và thời tiết để hiển thị văn bản cạnh nhau hoặc cao hơn
mã hoàn chỉnh
Chạy một ví dụ với tất cả các trực quan hóa có thể
Tôi hy vọng phương pháp so sánh song song này có thể giúp bạn nhiều như nó giúp tôi. Tìm sự khác biệt trong các văn bản dễ dàng hơn nhiều với phép so sánh này, nơi thực sự hữu ích khi cùng một văn bản bên trái và bên phải xuất hiện trên cùng một dòng. Đối với bộ lọc quyền riêng tư của tôi, sự khác biệt về độ dài trở nên khá lớn khiến việc so sánh trở nên khó xử khi các phần văn bản bằng nhau được hiển thị với nhiều dòng ở giữa