Constructing LZ78 tries and position heaps in linear time for large alphabets
We propose the first linear time algorithm to compute LZ78 trie over an integer alphabet. We propose a linear time algorithm to construct the position heap of a trie. LZ78 tries and position heaps can be superimposed on the corresponding suffix trees. Both of them can be computed by nearest marked ancestor queries on suffix trees.
position heaps algorithms suffix trees nearest marked ancestor queries data structures lempelziv 78 factorization