Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
434434 | Theoretical Computer Science | 2014 | 12 Pages |
Abstract
An antidictionary is in particular useful for data compression. Static construction algorithms of antidictionaries with linear complexity have been proposed. However, the construction algorithms do not work in a dynamic manner with linear complexity. In this paper, we propose a dynamic construction algorithm of an antidictionary with linear complexity. The proposed algorithm uses two linear construction algorithms of suffix trees proposed by Weiner and Ukkonen, individually. It is proved that the proposed algorithm works with linear complexity. Moreover, its effectiveness is demonstrated by simulation results.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Takahiro Ota, Hirotada Fukae, Hiroyoshi Morita,