Time optimal left to right construction of position trees
The authors present a new algorithm for the on-line construction of position trees. The position tree for a given text is a trie index spelling out for every position the shortest substring starting at that position and occurring nowhere else in the text. This auxiliary text representation structure yields an efficient solution for multiple pattern matching. Hence efficient construction (and correction) algorithms of position trees have become an interesting subject of research. The new position tree construction method is developed starting from a general construction scheme by stepwise refinements. Infix trees are a useful theoretical concept to describe the progress of the construction and to prove the correctness of the algorithm. An additional threading within the trees connecting every node with its ``tail node is the key idea which enables us to read an input string from left to right and thereby to generate its position tree within the best possible time (proportional to the number of tree nodes). Changes in the text obviously require the correction of its position tree. Efficient updating methods also including the strength of tail nodes will be the subject of a forthcoming study by the first author.
- Linear bidirectional on-line construction of affix trees
- On-line construction of suffix trees
- Near real-time suffix tree construction via the fringe marked ancestor problem
- scientific article; zbMATH DE number 1615290 (Why is no real title available?)
- On-line construction of position heaps
- Forty Years of Text Indexing
- New algorithms for position heaps
- Approximate string matching with suffix automata
- Execution time analysis of a top-down R-tree construction algorithm
This page was built for publication: Time optimal left to right construction of position trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1092659)
