Time optimal left to right construction of position trees
type: Item
instance of: scholarly article
title: Time optimal left to right construction of position trees
zbMATH Open document ID: 0627.68039
DOI: 10.1007/BF00292114
author: B. George
published in: Acta Informatica
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4020476
zbMATH Keywords: design and analysis of algorithms
zbMATH Keywords: on-line algorithms
zbMATH Keywords: complexity of algorithms
zbMATH Keywords: infix trees
zbMATH Keywords: data struture
zbMATH Keywords: algorithm for the on-line construction of position trees
zbMATH Keywords: multiple pattern matching
zbMATH Keywords: tail node
MaRDI profile type: Publication
cites work: Q4091421
cites work: Efficient On-Line Construction and Correction of Position Trees
cites work: A Space-Economical Suffix Tree Construction Algorithm
full work available at URL: https://doi.org/10.1007/bf00292114
OpenAlex ID: W2085735795
description: scientific article; zbMATH DE number 4020476