@inproceedings{c50ad76ceb5344c794d28f38482b329c,
title = "Packed Acyclic Deterministic Finite Automata",
abstract = "An acyclic deterministic finite automaton (ADFA) is a data structure that represents a set of strings (i.e., a dictionary) and facilitates a pattern-searching problem of determining whether a given pattern string is present in the dictionary. We introduce the packed ADFA (PADFA), a compact variant of ADFA designed to achieve more efficient pattern searching by encoding specific paths as packed strings stored in contiguous memory. We theoretically demonstrate that pattern searching in PADFA is near time-optimal with a small additional overhead and becomes fully time-optimal for sufficiently long patterns. Moreover, we prove that a PADFA requires fewer bits than a trie when the dictionary size is relatively smaller than the number of states in the PADFA. Lastly, we empirically show that PADFAs improve both the space and time efficiency of pattern searching on real-world datasets.",
keywords = "acyclic DFA, packed string, pattern searching",
author = "Hiroki Shibata and Masakazu Ishihata and Shunsuke Inenaga",
note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.; 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025 ; Conference date: 20-01-2025 Through 23-01-2025",
year = "2025",
doi = "10.1007/978-3-031-82697-9_21",
language = "English",
isbn = "9783031826962",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "284--297",
editor = "Rastislav Kr{\'a}lovi{\v c} and V{\v e}ra Kůrkov{\'a}",
booktitle = "SOFSEM 2025",
address = "Germany",
}