Существует ли структура данных «стек строк», которая поддерживает эти строковые операции?

28

Я ищу структуру данных , которая хранит множество строк над набором символов , способных выполнять следующие операции. Обозначим через D ( S ) в качестве структуры данных , хранящей множество строк S .ΣD(S)S

  • Add-Prefix-Setна : для некоторого множества T (возможно, пустых) строк, размер которых ограничен константой, а длины строк ограничены константой, вернуть D ( { t s | t T , s S } ) , Оба эти константы являются глобальными Ограничивающими: они одинаковы для всех входов Т .D(S)TD({ts | tT,sS})T
  • Get-Prefixesна : возврат { a | a s S , a Σ } . Обратите внимание, что я действительно не против того, какая структура используется для этого набора, поскольку я могу перечислить его содержимое за O ( | Σ | ) время.D(S){a | asS,aΣ}O(|Σ|)
  • Remove-Prefixesна : вернуть D ( { s | a s S , a Σ } ) .D(S)D({s | asS,aΣ})
  • Merge: даны и D ( T ) , вернуть D ( S T ) .D(S)D(T)D(ST)

Теперь я действительно хотел бы выполнить все эти операции за время , но я в порядке со структурой, которая выполняет все эти операции за время o ( n ) , где n - длина самой длинной строки в состав. В случае слияния, я хотел бы, чтобы o ( n 1 + n 2 ) выполнялось, где n 1 - это n для первой, а n 2 - для n для второй структуры.O(1)o(n)no(n1+n2)n1nn2n

Дополнительным требованием является то, что структура является неизменной или, по крайней мере, вышеуказанные операции возвращают «новые» структуры, так что указатели на старые по-прежнему функционируют, как и прежде.

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

Я хотел бы использовать такую ​​структуру в алгоритме синтаксического анализа, над которым я работаю; Приведенная выше структура будет содержать запрос, необходимый мне для алгоритма.

Add-Prefix-SetO(1)

|Σ|

Алекс тен Бринк
источник
Строки строятся только с помощью операции, Add-Prefix-Setили вы начинаете с произвольного набора строк?
Джо
2
n1=n2STo(n1+n2)
Вы начинаете с набора с одной строкой из одного символа в нем, но с пустой строкой тоже все в порядке (вы можете просто вставить Add-Prefix-Setее)
Алекс тен Бринк
@Joe: это хороший вопрос - я начинаю убеждаться, что операция слияния в значительной степени разрушает любой шанс получить такую ​​структуру ...
Алекс тен Бринк
(n1,n2)

Ответы:

5

Я думал довольно долго, но не нашел проблемы с выполнением всех ваших операций самым глупым из возможных способов в структуре структуры DAG, похожей на три:

Надстройка Приставка-Set

T

O(|T|)

Объединить

Объедините корни двух структур: сделайте все дочерние узлы второго корневого потомка первого узла. Теперь у вас может быть несколько ребер, помеченных одним и тем же символом, идущим от одного и того же узла.

O(1)

Ленивое обновление рута

  1. O(|Σ|)O(1)
  2. O(1)

Get-префиксы

Ленивое обновление рута. Теперь найдите всех потомков корня и сообщите множество букв по краям, идущим к ним.

O(|Σ|)

Remove-префиксы

Ленивое обновление рута. Объедините всех дочерних элементов корня и установите корневой указатель на результат этого объединения. Ленивое обновление нового рута.

O(|Σ|)

Упорство

O(1)O(|Σ|)O(logN)N

maksay
источник