4

想知道解决这个特定问题的最佳方法以及是否有任何库（最好是 python，但如果需要我可以灵活）。

我有一个文件，每行都有一个字符串。我想在每行中找到最长的常见模式及其位置。我知道我可以使用 SequenceMatcher 来比较第一行和第二行、第一行和第三行，等等，然后关联结果，但是如果有什么已经做到了呢？

理想情况下，这些匹配会出现在每行的任何位置，但对于初学者来说，我可以接受它们存在于每行的相同偏移处并从那里开始。像压缩库这样具有良好 API 来访问其字符串表的东西可能是理想的，但到目前为止我还没有找到任何符合该描述的东西。

例如这些行：

\x00\x00\x8c\x9e\x28\x28\x62\xf2\x97\x47\x81\x40\x3e\x4b\xa6\x0e\xfe\x8b
\x00\x00\xa8\x23\x2d\x28\x28\x0e\xb3\x47\x81\x40\x3e\x9c\xfa\x0b\x78\xed
\x00\x00\xb5\x30\xed\xe9\xac\x28\x28\x4b\x81\x40\x3e\xe7\xb2\x78\x7d\x3e

我希望看到 0-1 和 10-12 在同一位置的所有行中匹配，并且 line1[4,5] 匹配 line2[5,6] 匹配 line3[7,8]。

谢谢，

4

2 回答 2

2

如果您只想在每行中找到相同偏移量的公共子字符串，那么您所需要的就是这样的：

matches = []
zipped_strings = zip(s1,s2,s3)
startpos = -1
for i in len(zipped_strings):
  c1,c2,c3 = zipped_strings[i]
  # if you're not inside a match, 
  #  look for matching characters and save the match start position
  if startpos==-1 and c1==c2==c3:
    startpos = i
  # if you are inside a match, 
  #  look for non-matching characters, save the match to matches, reset startpos
  elif startpos>-1 and not c1==c2==c3:
    matches.append((startpos,i,s1[startpos:i]))
    # matches will contain (startpos,endpos,matchstring) tuples
    startpos = -1
# if you're still inside a match when you run out of string, save that match too!
if startpos>-1:
  endpos = len(zipped_strings)
  matches.append((startpos,endpos,s1[startpos:endpos]))

要找到最长的公共模式，无论位置如何，SequenceMatcher 听起来确实是最好的主意，但不是比较 string1 到 string2，然后比较 string1 到 string3 并尝试合并结果，只需获取 string1 和 string2 的所有公共子串（使用 get_matching_blocks） ，然后将每个结果与 string3 进行比较，以获得所有三个字符串之间的匹配。

于 2011-06-15T21:56:41.300 回答
0

你的问题是表现吗？

你的输入有多大？

匹配 2 的最小字符串长度是多少？

请注意，我认为您的示例不正确，因为您期望的结果与您提供的示例字符串不匹配。

于 2010-04-02T14:33:49.917 回答