.png){kind=icon}
返回
Practical compressed string dictionaries
.png){kind=icon}
OA
AI
DOI：10.1016/j.is.2015.08.008.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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.
Keyword:
Compressed string dictionaries
Text processing
Text databases
Compressed data structures
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
3.9
论文数:
2.8K
被引数:
1.8K
机构
引用论文
.png){kind=icon}
Propensity Score Stratification Using Multilevel Models to Examine Charter School Achievement Effects使用多层模型进行倾向得分分层以检验特许学校成就效应
PREAI
分享收藏Putting Politics in the Lab: A Review of Lab Experiments in Political Science将政治带入实验室：政治科学实验室实验综述OAAI
OAAI分享收藏
分享收藏分享收藏分享收藏
查看更多内容