Title :
A T-decomposition algorithm with O(n log n) time and space complexity
Author :
Yang, Jia ; Speidel, Ulrich
Author_Institution :
Dept. of Comput. Sci., Auckland Univ.
Abstract :
T-decomposition maps a finite string into a series of parameters for a recursive string construction algorithm. Initially developed for the communication of coding trees (M. R. Titchener, June 1996), (U. Guenther, Feb. 2001), T-decomposition has since been studied within the context of information measures. This involves the parsing of potentially very large strings, which in turn requires algorithms with good time complexity. This paper presents a T-decomposition algorithm with O(n log n) time and space complexity
Keywords :
computational complexity; tree codes; T-decomposition algorithm; coding trees; recursive string construction algorithm; space complexity; time complexity; Approximation algorithms; Computer science; Context; Decoding; Entropy; Event detection; Logistics; Production;
Conference_Titel :
Information Theory, 2005. ISIT 2005. Proceedings. International Symposium on
Conference_Location :
Adelaide, SA
Print_ISBN :
0-7803-9151-9
DOI :
10.1109/ISIT.2005.1523285
