On a two-dimensional antidictionary construction using suffix tries

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(n⁸) 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(n⁴ 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(n⁵ log n) time, and their effectivenesses are demonstrated by simulation results.