Я хочу построить эффективный суффикс для всех подстрок строки; Предположим, что длина строки равна 5000, тогда количество подстрок будет примерно 25 * 10 ^ 6, и для каждого узла я храню массив связанных данных размером 26, поэтому общая память = 26 * 5000 * 5000, что невозможно, поэтому ошибка времени выполнения ожидается. У меня есть решение для эффективного по пространству суффиксного дерева, в котором мы сжимаем путь там, где у нас нет выбора, так что порядок пространства становится приблизительно линейным. Но я не могу понять, может ли кто-нибудь помочь мне в этом.
Как построить суффикс Trie для всех подстрок строки?
Ответы (2)
Я думаю, вы ищете не три, а суффиксное дерево. Сжатие пути - это способ, но я бы просто поискал алгоритм Укконена. Сложность времени и пространства равна n. Если вы хотите что-то, что лучше понять, просто найдите Suffix Arrays. Пространственная сложность также равна n, с более низкой константой (около 6 вместо 32 или около того, я не помню точных цифр) и гораздо лучшим предсказанием кэша через аппаратное обеспечение.
person
Nicolas
schedule
30.07.2015
Не уверен в вашей арифметике... но если у вас есть только одна строка, ваше дерево должно иметь размер 26n.
Технически вы можете заменить Suffix Trie/Tree на Suffix Array + LCP Array, сохраняя ту же скорость базовых операций с графом. Потребление памяти будет 1+4+4=9n. Недостатком является то, что изменить исходную строку непросто.
person
dim
schedule
20.08.2015
