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

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

Теоретически

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

На практике

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

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

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

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

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

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

предположим, вам дан отсортированный массив 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).