如何找到大串的最佳拟合子序列？

Question

假设我有一个大字符串和一个子字符串数组，当它们与大字符串相等时（差别很小）。

例如（注意字符串之间的细微差别）：

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"] 

我怎样才能最好对准串生产从原来large_str一组新的子串？例如：

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

附加信息

的应用案例，这是要找到从PDF文档中提取文本的现有分页符原文的分页符。从PDF中提取的文本是OCR，与原始文本相比具有较小的错误，但原始文本没有分页符。我们的目标是准确地翻页原始文本，避免PDF文本的OCR错误。

Answer 1

1. 串联的子
2. 对准串联与原字符串
3. 跟踪其位置在原始字符串对齐的子
4. 拆分的位置原来的字符串之间的边界对齐使用Python的这些边界

---

的实现：

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) 

输出：

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

Answer 2

（额外的信息使很多下面是不必要的。它是为在子提供可能的顺序任意排列在它们发生的主要字符串的情况下写的）

会有一个动态编程解决方案的问题与此非常接近。在给出编辑距离的动态编程算法中，动态程序的状态是（a，b），其中a是第一个字符串的偏移量，b是第二个字符串的偏移量。对于每对（a，b），计算出与第一个字符串的第一个字符和第二个字符串的前b个字符相匹配的最小编辑距离，从（a-1，b -1），（a-1，b）和（a，b-1）。

现在你可以写出一个类似的算法（a，n，m，b），其中a是到目前为止子字符串消耗的字符总数，n是当前子字符串的索引，m是内部位置当前子字符串，b是第二个字符串中匹配的字符数。这解决了将b与通过粘贴任何可用子字符串的任意数量副本组成的字符串进行匹配的问题。

这是一个不同的问题，因为如果你试图从片段中重构一个长字符串，你可能会得到一个不止一次使用同一片段的解决方案，但是如果你这样做，你可能希望答案是它显然足以证明它产生的子串的集合恰好是给予它的集合的排列。

由于此方法返回的编辑距离总是至少与强制排列时的最佳编辑距离一样好，您还可以使用它来计算排列的最佳可能编辑距离的下限，并运行分支定界算法以找到最佳置换。

Answer 3

你正在试图解决序列比对的问题。在你的情况下，它是一个“本地”序列比对。它可以用Smith-Waterman的方法解决。一种可能的实现是here。 如果你运行它，您将收到：

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 

中间行表示匹配字符。如果您需要这些头寸，请查找max_i值，以得到结尾在原始字符串中的位置。 起始位置的值将为i在water()函数的末尾。