Title :
On the Construction of an Antidictionary of a Binary String with Linear Complexity
Author :
Ota, Takahiro ; Morita, Hiroyoshi
Author_Institution :
Dept. of Electron. Eng., Nagano Prefectural Inst. of Technol.
Abstract :
An antidictionary of a binary string is a set of words of minimal length that never appear in this string. Antidictionaries are in particular useful for source coding. We present a fast and memory-efficient algorithm to construct an antidictionary for a binary string using a suffix tree. It is proved that the complexity of this algorithm is linear in space and time, and its effectiveness is demonstrated by simulation results
Keywords :
binary codes; computational complexity; linear codes; source coding; antidictionary construction; binary string; linear complexity; memory-efficient algorithm; source coding; Compression algorithms; Computational complexity; Data compression; Electrocardiography; Entropy; Information systems; Pattern matching; Source coding; Tree data structures; Virtual manufacturing;
Conference_Titel :
Information Theory, 2006 IEEE International Symposium on
Conference_Location :
Seattle, WA
Print_ISBN :
1-4244-0505-X
Electronic_ISBN :
1-4244-0504-1
DOI :
10.1109/ISIT.2006.262007
