python - 不切割单词的最长公共(public)子串- python

Question

鉴于以下，我可以找到最长的公共(public)子串:

s1 = "this is a foo bar sentence ."
s2 = "what the foo bar blah blah black sheep is doing ?"

def longest_common_substring(s1, s2):
  m = [[0] * (1 + len(s2)) for i in xrange(1 + len(s1))]
  longest, x_longest = 0, 0
  for x in xrange(1, 1 + len(s1)):
    for y in xrange(1, 1 + len(s2)):
      if s1[x - 1] == s2[y - 1]:
        m[x][y] = m[x - 1][y - 1] + 1
        if m[x][y] > longest:
          longest = m[x][y]
          x_longest = x
      else:
        m[x][y] = 0
  return s1[x_longest - longest: x_longest]

print longest_common_substring(s1, s2)

[输出]:

foo bar

但是如何确保最长公共(public)子串遵守英文单词边界并且不分割单词呢？例如下面的句子:

s1 = "this is a foo bar sentence ."
s2 = "what a kappa foo bar black sheep ?"
print longest_common_substring(s1, s2)

输出不所需的后续内容，因为它打断了 s2 中的单词 kappa:

a foo bar

期望的输出仍然是:

foo bar

我也尝试了一种 ngram 方法来获取关于单词边界的最长公共(public)子串，但是是否有其他方法可以在不计算 ngram 的情况下处理字符串？ (见答案)

Answer 1

这个太简单了，不好理解。我用你的代码完成了 75% 的工作。我先把句子拆分成单词，然后传给你的函数得到最大的公共(public)子串(在这种情况下就是最长的连续单词)，所以你的函数给了我 ['foo', 'bar'], 我加入了该数组的元素以产生所需的结果。

这是在线工作副本，供您测试验证和摆弄。

http://repl.it/RU0/1

def longest_common_substring(s1, s2):
  m = [[0] * (1 + len(s2)) for i in xrange(1 + len(s1))]
  longest, x_longest = 0, 0
  for x in xrange(1, 1 + len(s1)):
    for y in xrange(1, 1 + len(s2)):
      if s1[x - 1] == s2[y - 1]:
        m[x][y] = m[x - 1][y - 1] + 1
        if m[x][y] > longest:
          longest = m[x][y]
          x_longest = x
      else:
        m[x][y] = 0
  return s1[x_longest - longest: x_longest]

def longest_common_sentence(s1, s2):
    s1_words = s1.split(' ')
    s2_words = s2.split(' ')  
    return ' '.join(longest_common_substring(s1_words, s2_words))


s1 = 'this is a foo bar sentence .'
s2 = 'what a kappa foo bar black sheep ?'
common_sentence = longest_common_sentence(s1, s2)
print common_sentence
>> 'foo bar'

边缘情况

1. '.'和 '？'如果最后一个单词和标点符号之间有空格，也将被视为有效单词，就像您的情况一样。如果您不留空格，它们将被计为最后一个词的一部分。那么“绵羊”和“绵羊”呢？不会再是同一个词了。在调用此类函数之前，由您决定如何处理此类字符。那样的话

   导入数据
s1 = re.sub('[.?]','', s1)
s2 = re.sub('[.?]','', s2)

然后像往常一样继续。