Найти похожие слова или фразы из двух текстов

Question

Я знаю, как сравнить два текста и получить все отдельные слова, которые появляются в обоих.Но как я могу сопоставить выражения / фразы?

Например: 1. «Это производитель компьютеров Apple» 2. «Apple - великий производитель компьютеров в Калифорнии»

Now :)

1. Apple явно присутствует в обоих.

2. компьютер и производитель присутствуют в обоих.Я мог бы проверить в этот момент, являются ли они группой слов (одно следует за другим).

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

Имейте в виду, что приведенный пример является тривиальным и только для целей иллюстрации, на практике могут быть представлены более сложные предложения / тексты.

Answer 1

Вы можете проанализировать обе строки и разбить их на пустое пространство, чтобы получить массивы токенов A1 и A2. Затем просто проверьте каждую смежную подпоследовательность в A1 на предмет соответствия в A2. Для меня это выглядит как O (n ^ 4), что лучше, чем получать все одинарные совпадения и искать комбинации ... что не является полиномом.

  1. the cat is on the roof
  2. a man is on the stage

  A1 = [the, cat, is, on, the, roof]
  A2 = [a, man, is, on, the, stage]

  [the]: no match
  [cat]: no match
  [is]: match
  [is, on]: match
  [is, on, the]: match
  [is, on, the, roof]: no match
  [on]: match
  [on, the]: match
  [on, the, roof]: no match
  [the]: match
  [the, roof]: no match
  [roof]: no match
  -end-

Рекурсия кажется элегантным способом реализации чего-то подобного. Если вам нужно что-то более эффективное, я уверен, что есть более разумный способ сделать это, чем этот.

Answer 2

РЕДАКТИРОВАТЬ : Возможно, вы ищете решение для самой длинной общей проблемы с подстрокой , или, в более общем случае самой длинной общей проблемы с подпоследовательностями . Если это так, то вам, по сути, нужен вариант утилиты «diff», и детали реализации, конечно же, очень сильно зависят от деталей ваших требований.