Practical compressed string dictionaries

作     者：Martinez-Prieto, Miguel A. Brisaboa, Nieves Canovas, Rodrigo Claude, Francisco Navarro, Gonzalo 

作者机构：Univ Valladolid Dept Comp Sci DataWeb Res E-47002 Valladolid Spain Univ A Coruna Database Lab La Coruna Spain Univ Melbourne Dept Comp & Informat Syst CIS NICTA Victoria Res Lab Melbourne Vic 3010 Australia Univ Diego Portales Escuela Informat & Telecomunicac Santiago Chile Univ Chile Dept Comp Sci CeBiB Ctr Biotechnol & Bioengn Santiago Chile 

出 版 物：《INFORMATION SYSTEMS》 (信息系统)

年 卷 期：2016年第56卷第Mar.期

页      面：73-108页

核心收录：

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

基　　金：Spanish Ministry of Economy and Competitiveness [TIN2013-46238-C4-3-R] ICT COST Action KEYSTONE [IC1302] Conicyt, Chile [FB0001] Fondecyt Iniciacion 

主　　题：Compressed string dictionaries Text processing Text databases Compressed data structures 

摘      要：The need to store and query a set of strings - a string dictionary - arises in many kinds of applications. While classically these string dictionaries have accounted for a small share of the total space budget (e.g., in Natural Language Processing or when indexing text collections), recent applications in Web engines, Semantic Web (RDF) graphs, Bioinformatics, and many others handle very large string dictionaries, whose size is a significant fraction of the whole data. In these cases, string dictionary management is a scalability issue by itself. This paper focuses on the problem of managing large static string dictionaries in compressed main memory space. We revisit classical solutions for string dictionaries like hashing, tries, and front-coding, and improve them by using compression techniques. We also introduce some novel string dictionary representations built on top of recent advances in succinct data structures and full-text indexes. All these structures are empirically compared on a heterogeneous testbed formed by real-world string dictionaries. We show that the compressed representations may use as little as 5% of the original dictionary size, while supporting lookup operations within a few microseconds. These numbers outperform the state-of-the-art space/time tradeoffs in many cases. Furthermore, we enhance some representations to provide prefix- and substring-based searches, which also perform competitively. The results show that compressed string dictionaries are a useful building block for various data-intensive applications in different domains. (C) 2015 Elsevier Ltd. All rights reserved.