|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Nozhenko 2:5020/175.1 05 Jan 2002 17:04:58
To : Andrew Simontsev
Subject : Строки...
--------------------------------------------------------------------------------
AS>>> Интересно, есть ли какой-нибудь алгоритм для решения следущей
AS>>> задачи: есть длинная-длинная строка X, надо найти минимальную строку
AS>>> Y, которая гарантированно не является подстрокой X? Может кто-нибудь
AS>>> знает?..
SN>> Если долго не думать :) и памяти не жалеть, то можно построить
SN>> суффиксное дерево этой строки (O(n)), потом, просматривая его от корня
SN>> уровень за уровнем, найти узел, у которого число потомков меньше
SN>> мощности алфавита, и дописать любой из отсутствующий среди его
SN>> потомков символ в конец подстроки, соответствующей этому узлу.
AS> А что есть суффиксное дерево?
Это сама по себе очень большая тема. Лучше посмотреть книжки по алгоритмам и
статьи в Интернете. Вкратце, если есть алфавит мощности k, и n строк из символов
этого алфавита, то представь себе k-арное дерево, построенное из строк так, что
каждый узел (кроме корня) i-го уровня содержит i-й символ одной или более строк,
ветвление в узле происходит по (i+1)-му символу этих строк, и все потомки узла
содержат разные символы. В общем, строки вставляются в дерево так, что
одинаковые префиксы представлены одними и теми же узлами. Листья дерева
соответствуют исходным строкам. Это называется trie (of strings).
Пусть есть строка длины n. Trie, построенное из всех n различных суффиксов
этой строки, называется suffix trie. Если ужать его так, чтобы все внутренние
узлы имели не менее двух потомков (что легко реализуется с помощью хранения в
дереве не символов алфавита, а указателей на подстроки и их длины), то такое
compressed trie как раз и называется suffix tree. Существует метод его
построения за линейное время. После чего искомая несуществующая подстрока будет
гарантированно найдена путем просмотра не более чем k^(l-1) узлов, где l - длина
этой подстроки.
AS> И сколько уйдет памяти, если строка, например, мегов 5 будет?
Дофига. :( ;) Правда, при нынешних объемах... В общем случае все сильно
зависит от исходной строки и способа представления дерева. Приблизительно можно
дать оценку в 16*n. То же дерево, преобразованное в бинарное (т.н. Patricia
tree), займет меньше места, но по нему в данном случае ходить не очень удобно.
Serge
--- Golded 2.41+
* Origin: Moccoletto (2:5020/175.1)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
