Time optimal left to right construction of position trees (Q1092659): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:10, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Time optimal left to right construction of position trees |
scientific article |
Statements
Time optimal left to right construction of position trees (English)
0 references
1987
0 references
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.
0 references
design and analysis of algorithms
0 references
on-line algorithms
0 references
complexity of algorithms
0 references
infix trees
0 references
data struture
0 references
algorithm for the on-line construction of position trees
0 references
multiple pattern matching
0 references
tail node
0 references