Алгоритм поиска наиболее распространенных подстрок в строке

Есть ли какой-либо алгоритм, который можно использовать для поиска наиболее распространенных фраз (или подстрок) в строке? Например, следующая строка будет иметь "привет мир" в качестве наиболее распространенной двухбуквенной фразы:

"hello world this is hello world. hello world repeats three times in this string!"

В приведенной выше строке наиболее распространенная строка (после символа пустой строки, которая повторяется бесконечно много раз) будет символом пробела .

Есть ли способ генерировать список общих подстрок в этой строке, от наиболее распространенных до наименее общих?

Ответ 1

Это задача, аналогичная алгоритму Нуссинова и на самом деле даже более простая, поскольку мы не допускаем разрывов, вставок или несоответствий в выравнивании.

Для строки A, имеющей длину N, определите таблицу F[-1 .. N, -1 .. N] и заполните ее, используя следующие правила:

  for i = 0 to N
    for j = 0 to N
      if i != j
        {
          if A[i] == A[j]
            F[i,j] = F [i-1,j-1] + 1;
          else
            F[i,j] = 0;
        }

Например, для B A O B A B:

Это выполняется в O(n^2) времени. Самые большие значения в таблице теперь указывают на конечные позиции самых длинных самоподписывающихся подпоследовательностей (i - конец одного появления, j - другое). Вначале предполагается, что массив инициализируется нулем. Я добавил условие, чтобы исключить диагональ, которая является самой длинной, но, вероятно, не интересной, совпадением.

Размышляя больше, эта таблица симметрична по диагонали, поэтому достаточно вычислить только ее половину. Кроме того, массив инициализируется нулем, поэтому присвоение нуля является избыточным. Это остается

  for i = 0 to N
    for j = i + 1 to N
      if A[i] == A[j]
         F[i,j] = F [i-1,j-1] + 1;

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

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

Я думаю, что использование hashmap непосредственно на самом деле требует O (n ^ 3), поскольку ключевые строки в конце доступа должны сравниваться как-то для равенства. Это сравнение, вероятно, O (n).

Ответ 2

Python. Это несколько быстро и грязно, а структуры данных делают большую часть подъема.

from collections import Counter
accumulator = Counter()
text = 'hello world this is hello world.'
for length in range(1,len(text)+1):
    for start in range(len(text) - length):
        accumulator[text[start:start+length]] += 1

Структура Counter - это словарь с хэш-поддержкой, предназначенный для подсчета того, сколько раз вы что-то видели. Добавление к несуществующему ключу создаст его, в то время как получение несуществующего ключа даст вам нуль вместо ошибки. Итак, все, что вам нужно сделать, это перебрать все подстроки.

Ответ 3

просто псевдокод, и, возможно, это не самое красивое решение, но я бы решил вот так:

function separateWords(String incomingString) returns StringArray{
  //Code
}

function findMax(Map map) returns String{
  //Code
}

function mainAlgorithm(String incomingString) returns String{
    StringArray sArr = separateWords(incomingString);
    Map<String, Integer> map; //init with no content
    for(word: sArr){
        Integer count = map.get(word);
        if(count == null){
            map.put(word,1);
        } else {
            //remove if neccessary
            map.put(word,count++); 
        }
   }
   return findMax(map);
}

Где карта может содержать пары ключей, таких как Java HashMap.

Ответ 4

Perl, O(n²) solution

my $str = "hello world this is hello world. hello world repeats three times in this string!";

my @words = split(/[^a-z]+/i, $str);
my ($display,$ix,$i,%ocur) = 10;

# calculate

for ($ix=0 ; $ix<=$#words ; $ix++) {
  for ($i=$ix ; $i<=$#words ; $i++) {
    $ocur{ join(':', @words[$ix .. $i]) }++;
  }
}

# display 

foreach (sort { my $c = $ocur{$b} <=> $ocur{$a} ; return $c ? $c : split(/:/,$b)-split(/:/,$a); } keys %ocur) {
  print "$_: $ocur{$_}\n";
  last if !--$display;
}

отображает 10 лучших оценок наиболее распространенных подстрок (в случае галстука сначала показывается самая длинная цепочка слов). Измените $display на 1, чтобы иметь только результат.
Есть n(n+1)/2 итерации.