Массив суффиксов, обозначающий внутренние узлы

Знание внутренних узлов полезно в дереве суффиксов, поскольку они могут помочь вам решить такие проблемы, как поиск самой длинной повторяющейся подстроки.

Их трудно построить на месте (вспомните интервью на доске). Поэтому люди посоветовали мне изучить массивы суффиксов.

У меня вопрос из двух частей:

1. Можно ли создать массив суффиксов без предварительного построения дерева суффиксов? Из того, что я видел, большинство реализаций строят trie, а затем обходят его, чтобы создать массив суффиксов.

2. Как определить внутренние узлы при наличии массива суффиксов?


algorithm suffix suffix-tree suffix-array
person ApathyBear    schedule 30.11.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

Чтобы ответить на часть 1, да, возможно (и обычно) построить массив суффиксов напрямую.

Эта ссылка на stanford.edu дает короткую O(nlog^2n) простой в реализации алгоритм:

#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
#define MAXN 65536
#define MAXLG 17
char A[MAXN];
struct entry { int nr[2], p;
} L[MAXN];
int P[MAXLG][MAXN], N, i, stp, cnt;
int cmp(struct entry a, struct entry b)
{
  return a.nr[0] == b.nr[0] ? (a.nr[1] < b.nr[1] ? 1 : 0) : (a.nr[0] < b.nr[0] ? 1 : 0);
}
int main(void)
{
  gets(A); for (N = strlen(A), i = 0; i < N; i ++)
  P[0][i] = A[i] - 'a';
  for (stp = 1, cnt = 1; cnt >> 1 < N; stp ++, cnt <<= 1) {
    for (i = 0; i < N; i ++)
      { L[i].nr[0] = P[stp - 1][i];
        L[i].nr[1] = i + cnt < N ? P[stp - 1][i + cnt] : -1;
        L[i].p = i; }
    sort(L, L + N, cmp);
    for (i = 0; i < N; i ++) P[stp][L[i].p] = i > 0 && L[i].nr[0] == L[i - 1].nr[0] && L[i].nr[1] == L[i - 1].nr[1] ?
    P[stp][L[i - 1].p] : i;
  } return 0;
}

В этом PDF-файле также обсуждается, как использовать массивы суффиксов в практических примерах.

В качестве альтернативы, эта статья 2005 г. "Построение массива суффиксов линейной работы" дает O (n) подход к построению массивов суффиксов с 50 строками кода.

В своих экспериментах со строкой длиной 100k я обнаружил, что дерево суффиксов (используя алгоритм Укконена O(n)) занимает 16 секунд, массив суффиксов O(nlog^2n) занимает 2,4 секунды, а суффикс O(n) массив занимает 0,5 секунды.

person Peter de Rivaz    schedule 30.11.2015
comment
Отлично, отличные ссылки. Я с удовольствием прочитаю это (это было именно то, что я искал). Я согласен, это было бы немного нелепо ожидать от интервью на белой доске. Как вы нашли это? Вы учились в Стэнфорде? - person ApathyBear; 01.12.2015
comment
Нет, я никогда не был в Стэнфорде. У меня просто была проблема, для решения которой мне нужно было использовать деревья суффиксов, и я использовал Google, насколько я помню. (Боюсь, я вел записи об используемых мной алгоритмах и их скорости, но не о том, как я их нашел.) - person Peter de Rivaz; 01.12.2015