Самая длинная общая подстрока без резки слова-питона

Это слишком просто понять. Я использовал ваш код для выполнения 75% работы. Сначала я разделил предложение на слова, а затем передал его в вашу функцию, чтобы получить самую большую общую подстроку (в этом случае это будут самые длинные последовательные слова), поэтому ваша функция дает мне ['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. '' а также '?' также рассматриваются как допустимые слова, как в вашем случае, если между последним словом и знаком препинания есть пробел. Если вы не оставите пространство, они будут считаться частью последнего слова. В таком случае «овцы» и «овцы»? больше не будут такими же словами. Вы можете решить, что делать с такими персонажами, прежде чем называть такую ​​функцию. В таком случае

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

а затем продолжить, как обычно.

Мой ответ не опирается ни на какие официальные источники, а на простое наблюдение: по крайней мере, в моей установке есть разница между выходом вашей функции LCS, как на пару (s1, s2) и (s1, s3) :

 In [1]: s1 = "this is a foo bar sentence ." In [3]: s2 = "what the foo bar blah blah black sheep is doing ?" In [4]: s3 = "what a kappa foo bar black sheep ?" In [12]: longest_common_substring(s1, s3) Out[12]: 'a foo bar ' In [13]: longest_common_substring(s1, s2) Out[13]: ' foo bar ' 

Как вы можете заметить, если совпадают полные слова, то также сопоставляются окружающие пробелы .

Затем вы можете изменить функцию перед ее выходом, например:

 answer = s1[x_longest - longest: x_longest] if not (answer.startswith(" ") and answer.endswith(" ")): return longest_common_substring(s1, answer[1:]) else: return answer 

Я уверен, что есть другие случаи кросс, такие как подстрока, появляющаяся в конце строки, рекурсивно вызывающая функцию либо с s1 либо s2 , будь то обрезка переднего или заднего answer , а другие – но, по крайней мере, в случаях, когда вы показать, эта простая модификация делает то, что вы хотите:

 In [20]: longest_common_substring(s1, s3) Out[20]: ' foo bar ' 

Считаете ли вы, что это направление стоит изучить?

Просто добавьте условие подтверждения в свой код:

 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 and word_aligned(x, y, m[x][y]): # acceptance condition longest = m[x][y] x_longest = x else: m[x][y] = 0 return s1[x_longest - longest: x_longest] def word_aligned(x, y, length): """check that a match starting at s1[x - 1] and s2[y - 1] is aligned on a word boundary""" # check start of match in s1 if s1[x - 1].isspace(): # match doesn't start with a character, reject return False if x - 2 > 0 and not s1[x - 2].isspace(): # char before match is not start of line or space, reject return False # check start of match in s2 ... same as above ... # check end of match in s1 ... your code is a bit hard for me follow, what is end of match? ... # check end of match in s2 ... same as above ... return True print longest_common_substring(s1, s2) 

Все, что вам нужно сделать, это добавить проверки для начала и конца слова.

Затем вы обновляете m только для действительных концов конца.

Вот так:

 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)): # current character in s1 x_char = s1[x - 1] # we are at the beginning of a word in s1 if # (we are at the beginning of s1) or # (previous character is a space) x_word_begin = (x == 1) or (s1[x - 2] == " ") # we are at the end of a word in s1 if # (we are at the end of s1) or # (next character is a space) x_word_end = (x == len(s1)) or (s1[x] == " ") for y in xrange(1, 1 + len(s2)): # current character in s2 y_char = s2[y - 1] # we are at the beginning of a word in s2 if # (we are at the beginning of s2) or # (previous character is a space) y_word_begin = (y == 1) or (s2[y - 2] == " ") # we are at the end of a word in s2 if # (we are at the end of s2) or # (next character is a space) y_word_end = (y == len(s2)) or (s2[y] == " ") if x_char == y_char: # no match starting with x_char if m[x - 1][y - 1] == 0: # a match can start only with a space # or at the beginning of a word if x_char == " " or (x_word_begin and y_word_begin): m[x][y] = m[x - 1][y - 1] + 1 else: m[x][y] = m[x - 1][y - 1] + 1 if m[x][y] > longest: # the match can end only with a space # or at the end of a word if x_char == " " or (x_word_end and y_word_end): longest = m[x][y] x_longest = x else: m[x][y] = 0 return s1[x_longest - longest: x_longest] 

Это более интересная проблема, после чего я изначально дал ей кредит. Когда вы думаете об этом, есть 4 возможных результата.

1. Тривиальный случай, вся строка не соответствует границам (ваш первый пример)
2. Пересеките границу слова в начале (ваш второй пример)
3. Пересечь границу слова в конце
4. Имейте границу слова на каждом конце

Теперь ваш код заботится о тривиальном случае, чтобы мы могли использовать это; все, что осталось – это обернуть ваши результаты несколькими проверками на другие случаи. Итак, какими должны быть эти проверки? Давайте рассмотрим ваш случай сбоя:

 string 1 = "this is a foo bar sentence ." string 2 = "what a kappa foo bar black sheep ?" output string = "a foo bar" 

Таким образом, из перспективы find строк мы можем найти все эти буквы в этом порядке как в string1 и в string2 , но если мы отделим все вокруг пробелов в списках и будем искать списки, чтобы только string1 соответствовала.

Теперь я в первую очередь парень C, поэтому я хочу написать это в функции:

 def full_string(str1, str2, chkstr): l1 = str1.split() l2 = str2.split() chkl = chkstr.split() return (any(l1[i:i+len(chkl)]==chkl for i in xrange(len(l1)-len(chkl)+1)) and any(l2[i:i+len(chkl)]==chkl for i in xrange(len(l2)-len(chkl)+1))) 

С помощью этой функции мы можем проверить, не содержит ли каждая из двух строк все слова нашего результата из longest_common_substring(s1, s2) по порядку. Отлично. Таким образом, последний шаг состоит в том, чтобы объединить эти две функции и проверить каждый из 4 случаев, перечисленных выше:

 def longest_whole_substring(s1, s2): subs = longest_common_substring(s1, s2) if not full_string(s1, s2, subs): if full_string(s1, s2, ' '.join(subs.split()[1:])): subs = ' '.join(subs.split()[1:]) elif full_string(s1, s2, ' '.join(subs.split()[:-1])): subs = ' '.join(subs.split()[:-1]) else: subs = ' '.join(subs.split()[1:-1]) return subs 

Теперь функция longest_whole_substring(s1, s2) предоставит самую длинную целую подстроку, не прерывая никаких слов. Давайте просто проверим это в каждом из случаев:

Trivial:

 >>> a = 'this is a foo bar bar foo string' >>> b = 'foo bar' >>> >>> longest_whole_substring(a,b) 'foo bar' 

Граница слова в начале:

 >>> b = 'sa foo bar' >>> >>> longest_whole_substring(a,b) 'a foo bar ' 

Словарная грань в конце:

 >>> b = 'foo bar f' >>> >>> longest_whole_substring(a,b) 'foo bar' 

И граница слов на обоих концах:

 >>> b = 'sa foo bar f' >>> >>> longest_whole_substring(a,b) 'a foo bar' 

Смотри, хорошо!

Я сделал это рекурсивно:

 def common_phrase(self, longer, shorter): """ recursively find longest common substring, consists of whole words only and in the same order """ if shorter in longer: return shorter elif len(shorter.split()) > 1: common_phrase_without_last_word = common_phrase(shorter.rsplit(' ', 1)[0], longer) common_phrase_without_first_word = common_phrase(shorter.split(' ', 1)[1], longer) without_first_is_longer = len(common_phrase_without_last_word) < len(common_phrase_without_first_word) return ((not without_first_is_longer) * common_phrase_without_last_word + without_first_is_longer * common_phrase_without_first_word) else: return '' 

Просто классифицируйте две строки до «короче» и «дольше» перед применением:

 if len(str1) > len(str2): longer, shorter = str1, str2 else: longer, shorter = str2, str1 

Вот путь ngram:

 def ngrams(text, n): return [text[i:i+n] for i in xrange(len(text)-n)] def longest_common_ngram(s1, s2): s1ngrams = list(chain(*[[" ".join(j) for j in ngrams(s1.split(), i)] for i in range(1, len(s1.split()))])) s2ngrams = list(chain(*[[" ".join(j) for j in ngrams(s2.split(), i)] for i in range(1, len(s2.split()))])) return set(s1ngrams).intersection(set(s2ngrams)) 

Одним из эффективных методов поиска наиболее длинных общих подстрок является дерево суффикса (см. http://en.wikipedia.org/wiki/Suffix_tree и http://en.wikipedia.org/wiki/Longest_common_substring_problem ). Я не вижу причин, по которым вы не могли бы создать дерево суффикса, используя слова вместо символов, и в этом случае самая длинная общая подпоследовательность, извлеченная из дерева, будет уважать границы токена. Такой подход был бы особенно эффективен, если вы хотите найти общие подстроки между одной фиксированной строкой и большим количеством других строк.

См. Принятый ответ на библиотеку python: для обобщенных деревьев суффиксов для списка реализаций дерева суффикса Python.