Title :
On a two-dimensional antidictionary construction using suffix tries
Author :
Takahiro Ota;Hiroyoshi Morita
Author_Institution :
Dept. of Computer &
fDate :
6/1/2015 12:00:00 AM
Abstract :
Antidictionaries are in particular useful for source coding. In one dimension, for an input string, there are fast construction algorithms of an antidictionary in which a suffix tree that stores all the substrings of the string is utilized. However, in two dimension (2D), for an n×n input square or rectangle, there is no fast construction algorithm of an antidictionary except a straight-forward algorithm in O(n8) time. In this paper, we propose a 2D suffix trie which stores all the subrectangles of an input rectangle and present an algorithm to construct a 2D suffix trie in O(n4 log n) time. A 2D suffix trie consists of two suffix tries with suffix links rowwise and columnwise. Moreover, we propose a fast construction algorithm of a two-dimensional antidictionary using a 2D suffix trie in O(n5 log n) time, and their effectivenesses are demonstrated by simulation results.
Keywords :
"Joining processes","Source coding","Dictionaries","Electronic mail","Computer simulation","Upper bound","Entropy"
Conference_Titel :
Information Theory (ISIT), 2015 IEEE International Symposium on
Electronic_ISBN :
2157-8117
DOI :
10.1109/ISIT.2015.7283002