DocumentCode
2948834
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.
fYear
2006
fDate
9-14 July 2006
Firstpage
2343
Lastpage
2347
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;
fLanguage
English
Publisher
ieee
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
Type
conf
DOI
10.1109/ISIT.2006.262007
Filename
4036389
Link To Document