Какой алгоритм вы можете использовать, чтобы найти повторяющиеся фразы в строке?

Question

Учитывая произвольную строку, каков эффективный метод поиска повторяющихся фраз? Мы можем сказать, что фразы должны быть длиннее определенной длины, чтобы быть включенными.

В идеале вы должны получить количество вхождений для каждой фразы.

Answer 1

В теории

• A массив суффиксов - это «лучший» ответ, поскольку он может быть реализован для использования линейного пространства и времени для обнаружения любых дублирующих подстрок. Однако наивная реализация на самом деле требует времени O (n ^ 2 log n) для сортировки суффиксов, и не совсем очевидно, как уменьшить это значение до O (n log n), не говоря уже о O (n), хотя вы можете прочитать связанные документы, если вы хотите.
• A дерево суффиксов может занимать немного больше памяти (хотя и по-прежнему линейно), чем массив суффиксов, но его легче реализовать для быстрой сборки, поскольку вы можете использовать что-то вроде radix сортировать идеи по мере добавления вещей в дерево (подробности см. в ссылке на википедию от имени).
• Алгоритм KMP также полезен для ознакомления, который предназначен для очень быстрого поиска определенной подстроки в более длинной строке. Если вам нужен только этот особый случай, просто используйте KMP, и вам не нужно сначала создавать индекс достаточности.

На практике

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

В этом случае вы можете просто выполнить быстрый n-грамм анализ для небольшого n, например, просто n = 2 или 3. Например, вы можете разбить ваш документ на список. слов, убирая знаки препинания, заглавные буквы и слова с запятой (работает, запускает оба -> «запустить»), чтобы увеличить семантические соответствия. Затем просто создайте хэш-карту (например, hash_map в C ++, словарь в python и т. Д.) Каждой смежной пары слов с учетом количества вхождений. В конце вы получаете очень полезные данные, которые очень быстро кодируются и не слишком быстро запускаются.

Answer 2

Как и ранее, люди упоминают, что суффиксное дерево - лучший инструмент для работы. Мой любимый сайт для деревьев суффиксов - http://www.allisons.org/ll/AlgDS/Tree/Suffix/.. Он перечисляет все изящные использования деревьев суффиксов на одной странице и имеет встроенное тестовое приложение js для проверки строк и работы с примерами.

Answer 3

Суффикс-деревья - хороший способ реализовать это. В нижней части этой статьи есть ссылки на реализации на разных языках.

Answer 4

предположим, вам дан отсортированный массив A с n записями (i = 1,2,3, ..., n)

Algo(A(i))
{
  while i<>n
  {
    temp=A[i];
    if A[i]<>A[i+1] then
    {     
      temp=A[i+1];
      i=i+1;
      Algo(A[i])
    }
    else if A[i]==A[i+1] then
      mark A[i] and A[i+1] as duplicates
  }
}

Этот алгоритм работает в O (n) раз.

Answer 5

Как сказал jmah, для этого вы можете использовать деревья суффиксов / массивы суффиксов.

Существует описание алгоритма, который вы можете использовать здесь (см. Раздел 3.1).

Более подробное описание можно найти в цитируемой ими книге (Gusfield, 1997), которая в книгах Google .