Python-сообщество

vanvanov
Я уже пробовал (и вчера, и год назад)

Может, ты просто задачу пытаешься решить неправильно. По крайней мере описания задачи мы тут не увидели.

py.user.next
По крайней мере описания задачи мы тут не увидели.

Берётся 2 текста, в которых присутствуют общие фрагменты (от отдельных слов до целых абзацев). Необходимо создать список общих фрагментов, при этом фрагменты должны быть не менее целого слова и равны максимально крупному совпадению (т.е., там, где совпадает подряд, например, 5 слов - должно возвращаться 5 слов, 1 слово - 1 слово). Порядок слов внутри фрагментов должен быть такой же, как и в обоих текстах. Однако, порядок самих фрагментов в текстах может быть разным. Порядок фрагментов в результате не имеет значения.
Например:
текст 1: мой первый воздушный шар девочка гладит весёлого котёнка
текст 2: весёлого котёнка гладит девочка мой первый шар
результат: ‘весёлого котёнка’,'гладит','девочка','мой первый','шар'
Есть хороший метод difflib.SequenceMatcher.get_grouped_opcodes, однако, для него важен порядок слов в сравниваемых текстах.

P.S. Не принципиально, но форум не отображает текст в квадратных скобках (если не код и не цитата), да и из кода зачем-то удаляет пустые строки. Не разобрался, куда писать баг-репорт.

Отредактировано vanvanov (Ноя. 19, 2018 02:46:45)

vanvanov
Берётся 2 текста, в которых присутствуют общие фрагменты (от отдельных слов до целых абзацев). Необходимо создать список общих фрагментов, при этом фрагменты должны быть не менее целого слова и равны максимально крупному совпадению (т.е., там, где совпадает подряд, например, 5 слов - должно возвращаться 5 слов, 1 слово - 1 слово). Порядок слов внутри фрагментов должен быть такой же, как и в обоих текстах. Однако, порядок самих фрагментов в текстах может быть разным. Порядок фрагментов в результате не имеет значения.
Например:
текст 1: мой первый воздушный шар девочка гладит весёлого котёнка
текст 2: весёлого котёнка гладит девочка мой первый шар
результат: ‘весёлого котёнка’,'гладит','девочка','мой первый','шар'

Чтобы искать подстроки из второго текста в первом тексте:
Тут надо разложить первый текст на массив слов. Второй текст надо превратить в набор цепочек слов. Цепочки идут от самых длинных к самым коротким. И дальше ты примеряешь самую длинную цепочку, беря её первое слово и отыскивая это слово в списке слов первого текста. Если слово найдено, ты берёшь последее слово цепочки и проверяешь, находится ли оно в списке слов первого текста на таком же расстоянии от первого слова, которое совпало. Если нет, то ты отбрасываешь цепочку и переходишь к следующей цепочке. Если оно там находится, то эта цепочка начинает рассматриваться. При рассмотрении цепочки ты сдвигаешься на второе слово и предпоследнее слово цепочки и сверяешь их со словами в списке слов первого текста. И так ты сдвигаешься к центру цепочки, пока она не проверится вся, либо пока не будет различия в словах. Так у тебя цепочка либо совпадёт, либо будет отброшена.

То есть пример (слова обозначены буквами)
Текст1: A B C D A B C D
Текст2: B C D

Вот ты сразу найдёшь B C D и тебе не нужно перебирать сначала B, потом C, потом D, чтобы понять, что ты нашёл B C D.

Ещё пример
Текст1: A B C D A B C D
Текст2: B C E

Здесь тоже ты сразу отбросишь цепочку B C E и тебе не нужно будет перебирать сначала B, потом C, потом E, чтобы понять, что цепочка B C E не подходит.

Представь, что эта цепочка B C E имеет длину миллион слов (где-нибудь там в середине). Прикинь, сколько ты будешь перебирать слов, чтобы понять, что она неподходящая? Поэтому мы и проверяем сначала первое и последнее слово. И только если они совпали, тогда мы проверяем дальше.