Dynamic construction of an antidictionary with linear complexity

作     者：Ota, Takahiro Fukae, Hirotada Morita, Hiroyoshi 

作者机构：Nagano Prefectural Inst Technol Dept Comp & Syst Engn Ueda Nagano 3861211 Japan Shikoku Polytech Coll Elect Informat Technol Dept Kochi 7815232 Japan Univ Electrocommun Grad Sch Informat Syst Chofu Tokyo 1828585 Japan 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2014年第526卷

页      面：108-119页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Antidictionary Incremental construction Linear computational complexity Suffix tree Data compression 

摘      要：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. (C) 2014 Elsevier B.V. All rights reserved.