A Grouping Approach for Succinct Dynamic Dictionary Matching

详细信息    查看全文

• 作者：Guy Feigenblat ; Ely Porat ; Ariel Shiftan
• 关键词：Dictionary matching ; Patterns matching ; Online algorithms ; Succinct ; Algorithms ; Compression ; Aho Corasick
• 刊名：Algorithmica
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：77
• 期：1
• 页码：134-150
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity; Theory of Computation; Mathematics of Computing; Algorithms; Computer Systems Organization and Communication Networks; Data Structures, Cryptology and Inform
• 出版者：Springer US
• ISSN：1432-0541
• 卷排序：77

文摘

In this work, we focus on building an efficient succinct dynamic dictionary that significantly improves the query time of the current best known results. The algorithm that we propose suffers from only a \( O((\log \log n)^2 )\) multiplicative slowdown in its query time and a \(O(\frac{1}{\epsilon } \log n)\) slowdown for insertion and deletion operations, where n is the sum of all of the patterns’ lengths, the size of the alphabet is \(\textit{polylog}(n)\) and \(\epsilon \in (0,1)\). For general alphabet the query time is \( O((\log \log n) \log \sigma )\), where \(\sigma \) is the size of the alphabet. A byproduct of this paper is an Aho-Corasick automaton that can be constructed with only a compact working space, which is the first of its type to the best of our knowledge.