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

Question

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

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

Answer 1

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

Answer 2

В теории

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

На практике

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

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

Answer 3

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

Answer 4

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

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

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

Answer 5

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