Самая длинная общая подстрока без вырезания слова-питона
Учитывая следующее, я могу найти самую длинную общую подстроку:
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
Но как я могу гарантировать, что самая длинная общая подстрока уважает границу английского слова и не разрезает слово? Например, следующие предложения:
s1 = "this is a foo bar sentence ."
s2 = "what a kappa foo bar black sheep ?"
print longest_common_substring(s1, s2)
выводит следующее, что НЕ желательно, так как это разбивает слово kappa из с2:
a foo bar
Желаемый результат по-прежнему:
foo bar
Я пробовал также ngram способ получить самую длинную общую подстроку, относящуюся к границе слова, но есть ли другой способ, который имеет дело со строками без вычисления ngram? (см. ответ)
8 ответов
Это слишком просто для понимания. Я использовал твой код для выполнения 75% работы. Сначала я делю предложение на слова, затем передаю его вашей функции, чтобы получить наибольшую общую подстроку (в этом случае это будут самые длинные слова подряд), поэтому ваша функция дает мне ['foo', 'bar'], я присоединяюсь к элементы этого массива для получения желаемого результата.
Вот онлайн рабочая копия, которую вы можете протестировать, проверить и поиграть с ней.
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'
Краевые случаи
'' а также '?' также рассматриваются как допустимые слова, как в вашем случае, если между последним словом и знаком препинания есть пробел. Если вы не оставите пробел, они будут засчитаны как часть последнего слова. В этом случае "овцы" и "овцы?" не будет больше одних и тех же слов. Вам решать, что делать с такими символами, прежде чем вызывать такую функцию. В таком случае
import res1 = 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 '
Как вы думаете, это направление стоит изучить?
Это более интересная проблема, чем я изначально считал. Когда вы думаете об этом, есть 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 = 's a foo bar'
>>>
>>> longest_whole_substring(a,b)
'a foo bar '
Слово ограничено в конце:
>>> b = 'foo bar f'
>>>
>>> longest_whole_substring(a,b)
'foo bar'
И Слово ограничено на обоих концах:
>>> b = 's a foo bar f'
>>>
>>> longest_whole_substring(a,b)
'a foo bar'
Выглядит хорошо!
Все, что вам нужно сделать, это добавить проверки начала и конца слова.
Затем вы обновите 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]
Я сделал это рекурсивно:
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
Просто добавьте условие принятия в ваш код:
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)
Одним из эффективных методов поиска самых длинных общих подстрок является дерево суффиксов (см. http://en.wikipedia.org/wiki/Suffix_tree и http://en.wikipedia.org/wiki/Longest_common_substring_problem). Я не вижу причин, по которым вы не могли бы создать дерево суффиксов, используя слова вместо символов, и в этом случае самая длинная общая подпоследовательность, извлеченная из дерева, будет соответствовать границам токенов. Этот подход будет особенно эффективен, если вы хотите найти общие подстроки между одной фиксированной строкой и большим количеством других строк.
Смотрите принятый ответ для python: library для обобщенных деревьев суффиксов для списка реализаций дерева суффиксов Python.
from difflib import SequenceMatcher
def longest_substring(str1, str2):
# initialize SequenceMatcher object with
# input string
# below logic is to make sure word does not get cut
str1 = " " + str1.strip() + " "
str2 = " " + str2.strip() + " "
seq_match = SequenceMatcher(None, str1, str2)
# find match of longest sub-string
# output will be like Match(a=0, b=0, size=5)
match = seq_match.find_longest_match(0, len(str1), 0, len(str2))
# return longest substring
if match.size != 0:
lm = str1[match.a: match.a + match.size]
# below logic is to make sure word does not get cut
if not lm.startswith(" "):
while not (lm.startswith(" ") or len(lm) == 0):
lm = lm[1:]
if not lm.endswith(" "):
while not (lm.endswith(" ") or len(lm) == 0):
lm = lm[:-1]
return lm.strip()
else:
return ""
Вот способ 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))