Làm thế nào tôi có thể tìm thấy các chuỗi phù hợp nhất của một chuỗi lớn?

Question

Giả sử tôi có một chuỗi lớn và một mảng các đoạn mà khi nối bằng chuỗi lớn (với sự khác biệt nhỏ).

Ví dụ (lưu ý sự khác biệt tinh tế giữa dây):

large_str = "hello, this is a long string, that may be made up of multiple 
substrings that approximately match the original string" 

sub_strs = ["hello, ths is a lng strin", ", that ay be mad up of multiple", 
"subsrings tat aproimately ", "match the orginal strng"] 

Làm thế nào tôi có thể sắp xếp tốt nhất các dây để tạo ra một bộ mới của tiểu chuỗi từ bản gốc large_str? Ví dụ:

["hello, this is a long string", ", that may be made up of multiple", 
"substrings that approximately ", "match the original string"] 

Thông tin cá

Các trường hợp sử dụng cho điều này là để tìm thấy những ngắt trang của văn bản gốc từ ngắt trang hiện có của văn bản được chiết xuất từ ​​một tài liệu PDF. Văn bản được trích xuất từ ​​PDF là OCR'd và có lỗi nhỏ so với văn bản gốc, nhưng văn bản gốc không có ngắt trang. Mục đích là để trang chính xác phá vỡ văn bản gốc tránh các lỗi OCR của văn bản PDF.

Answer 1

1. CONCATENATE các chuỗi con
2. Căn nối với chuỗi gốc
3. Theo dõi trong đó vị trí trong chuỗi ban đầu được liên kết với các ranh giới giữa các chuỗi con
4. Chia chuỗi gốc trên các vị trí thẳng hàng với những ranh giới đó

---

Thực hiện sử dụng Python difflib:

from difflib import SequenceMatcher 
from itertools import accumulate 

large_str = "hello, this is a long string, that may be made up of multiple substrings that approximately match the original string" 

sub_strs = [ 
    "hello, ths is a lng strin", 
    ", that ay be mad up of multiple", 
    "subsrings tat aproimately ", 
    "match the orginal strng"] 

sub_str_boundaries = list(accumulate(len(s) for s in sub_strs)) 

sequence_matcher = SequenceMatcher(None, large_str, ''.join(sub_strs), autojunk = False) 

match_index = 0 
matches = [''] * len(sub_strs) 

for tag, i1, i2, j1, j2 in sequence_matcher.get_opcodes(): 
    if tag == 'delete' or tag == 'insert' or tag == 'replace': 
    matches[match_index] += large_str[i1:i2] 
    while j1 < j2: 
     submatch_len = min(sub_str_boundaries[match_index], j2) - j1 
     while submatch_len == 0: 
     match_index += 1 
     submatch_len = min(sub_str_boundaries[match_index], j2) - j1 
     j1 += submatch_len 
    else: 
    while j1 < j2: 
     submatch_len = min(sub_str_boundaries[match_index], j2) - j1 
     while submatch_len == 0: 
     match_index += 1 
     submatch_len = min(sub_str_boundaries[match_index], j2) - j1 
     matches[match_index] += large_str[i1:i1+submatch_len] 
     j1 += submatch_len 
     i1 += submatch_len 

print(matches) 

Output:

['hello, this is a long string', 
', that may be made up of multiple ', 
'substrings that approximately ', 
'match the original string'] 

Answer 2

(Các thông tin bổ sung tạo ra rất nhiều những điều sau đây không cần thiết. Nó được viết cho một tình huống mà các chuỗi con được cung cấp có thể là bất kỳ hoán vị của thứ tự mà chúng xuất hiện trong chuỗi chính)

Sẽ có một giải pháp lập trình động cho một vấn đề rất gần với điều này. Trong thuật toán lập trình động cung cấp cho bạn khoảng cách chỉnh sửa, trạng thái của chương trình động là (a, b) trong đó a là giá trị bù vào chuỗi đầu tiên và b là giá trị bù vào chuỗi thứ hai. Đối với mỗi cặp (a, b) bạn tính khoảng cách chỉnh sửa nhỏ nhất có thể khớp với ký tự đầu tiên của chuỗi đầu tiên với ký tự b đầu tiên của chuỗi thứ hai, làm việc (a, b) từ (a-1, b -1), (a-1, b) và (a, b-1). Bây giờ bạn có thể viết một thuật toán tương tự với trạng thái (a, n, m, b) trong đó a là tổng số ký tự được tiêu thụ bởi các phần tử cho đến nay, n là chỉ mục của chuỗi con hiện tại, m là vị trí bên trong chuỗi con hiện tại và b là số ký tự được đối sánh trong chuỗi thứ hai. Điều này giải quyết vấn đề kết hợp b với một chuỗi được tạo thành bằng cách dán cùng nhau bất kỳ số lượng bản sao nào của bất kỳ phần nền nào có sẵn. Đây là một vấn đề khác, bởi vì nếu bạn đang cố gắng tạo một chuỗi dài từ các đoạn, bạn có thể nhận được một giải pháp sử dụng cùng một phân đoạn nhiều lần, nhưng nếu bạn làm điều này, bạn có thể hy vọng câu trả lời là đủ rõ ràng rằng việc thu thập các chất nền mà nó tạo ra xảy ra là một hoán vị của bộ sưu tập cho nó.

Vì khoảng cách chỉnh sửa được trả về bằng phương pháp này sẽ luôn tốt nhất là khoảng cách chỉnh sửa tốt nhất khi bạn hoán vị, bạn cũng có thể sử dụng tính này để tính giới hạn thấp hơn trên khoảng cách chỉnh sửa tốt nhất có thể cho một hoán vị, và chạy một thuật toán nhánh và liên kết để tìm ra hoán vị tốt nhất.

Answer 3

Bạn đang cố gắng giải quyết vấn đề bắt cặp trình tự. Trong trường hợp của bạn, đó là liên kết chuỗi "cục bộ". Nó có thể được giải quyết với cách tiếp cận Smith-Waterman. Một triển khai có thể là here. Nếu bạn chạy, bạn nhận được:

large_str = "hello, this is a long string, that may be made up of multiple substrings that approximately match the original string" 
sub_strs = ["hello, ths is a lng sin", ", that ay be md up of mulple", "susrings tat aproimately ", "manbvch the orhjgnal strng"] 

for sbs in sub_strs: 
    water(large_str, sbs) 


>>> 

Identity = 85.185 percent 
Score = 210 
hello, this is a long strin 
hello, th s is a l ng s in 
hello, th-s is a l-ng s--in 

Identity = 84.848 percent 
Score = 255 
, that may be made up of multiple 
, that ay be m d up of mul ple 
, that -ay be m-d- up of mul--ple 

Identity = 83.333 percent 
Score = 225 
substrings that approximately 
su s rings t at a pro imately 
su-s-rings t-at a-pro-imately 

Identity = 75.000 percent 
Score = 175 
ma--tch the or-iginal string 
ma ch the or g nal str ng 
manbvch the orhjg-nal str-ng 

Dòng giữa hiển thị các ký tự trùng khớp. Nếu bạn cần vị trí, hãy tìm giá trị max_i để có được kết thúc vị trí trong chuỗi gốc. Các bắt đầu từ vị trí sẽ là giá trị của i vào cuối của water() chức năng.