最长的公共子串，无需砍字-python [英] Longest Common Substring without cutting a word- python

问题描述

给出以下信息，我可以找到最长的公共子字符串:

Given the following, i can find the longest common substring:

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

但是我如何确保最长的公共子字符串遵守英语单词的边界并且不切掉单词呢?例如，以下句子:

But how do i ensure that the longest common substring respect English word boundary and don't cut up a word? For example, the following sentences:

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

输出不希望出现的跟随 ，因为它会将单词kappa从s2中分解出来:

outputs the follow which is NOT desired since it breaks up the word kappa from s2:

a foo bar

所需的输出仍然是:

foo bar

我还尝试了一种ngram方法来获得最长的符合单词边界的公共子字符串，但是还有其他方法可以处理不计算ngrams的字符串吗? (请参阅答案)

I've tried also an ngram way of getting the longest common substring respecting word boundary but is there other way that deals with strings without calculating ngrams? (see answer)

推荐答案

这太容易理解了.我用您的代码完成了75％的工作. 我首先将句子拆分成单词，然后将其传递给您的函数以获取最大的公共子字符串(在这种情况下，它将是最长的连续单词)，因此您的函数给了我['foo'，'bar']，我加入了数组中的元素以产生所需的结果.

This is too simple to understand. I used your code to do 75% of the job. I first split the sentence into words, then pass it to your function to get the largest common substring(in this case it will be longest consecutive words), so your function gives me ['foo', 'bar'], I join the elements of that array to produce the desired result.

这里是在线工作副本，您可以对其进行测试和验证，并加以摆弄.

Here is the online working copy for you to test and verify and fiddle with it.

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. '.和 '?'如果最后一个单词和标点符号之间有空格，则也将被视为有效单词.如果您不留空格，它们将被算作最后一句话.在那种情况下，绵羊"和绵羊"?不再是相同的词了.在调用此类函数之前，由您决定如何处理此类字符.在这种情况下

1. '.' and '?' are also treated as valid words as in your case if there is a space between last word and the punctuation mark. If you don't leave a space they will be counted as part of last word. In that case 'sheep' and 'sheep?' would not be same words anymore. Its up to you decide what to do with such characters, before calling such function. In that case

import re
s1 = re.sub('[.?]','', s1)
s2 = re.sub('[.?]','', s2)

import re
s1 = re.sub('[.?]','', s1)
s2 = re.sub('[.?]','', s2)

然后照常继续.

这篇关于最长的公共子串，无需砍字-python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！