@inproceedings{2f10288e498f4e9c916b212fcf806da7,
title = "Smaller Representation of Compiled Regular Expressions",
abstract = "We consider the problem of running the regex pattern matching in a space-efficient manner. Given a regex, we suggest a bit-packing scheme for representing a compiled regex in a compressed way, which is its position automaton. Our scheme reduces its representation size further by relying on the homogeneous property of position automata and practical features of regexes. We implement the proposed scheme and evaluate the memory consumption using a practical regex benchmark dataset. Our approach produces a much smaller representation compared to two common FA representations. In addition, experimental results show that our bit-packing regex engine is effective for matching regexes that have large compiled forms, by showing less memory consumption compared to the current state-of-the-art regex engine (RE2).",
keywords = "Bit-packing scheme, Position automata, Regex engine, Regular expressions",
author = "Sicheol Sung and Ko, {Sang Ki} and Han, {Yo Sub}",
note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; Implementation and Application of Automata - 27th International Conference, CIAA 2023, Proceedings ; Conference date: 19-09-2023 Through 22-09-2023",
year = "2023",
doi = "10.1007/978-3-031-40247-0_22",
language = "English",
isbn = "9783031402463",
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 = "290--301",
editor = "Benedek Nagy and Benedek Nagy",
booktitle = "Implementation and Application of Automata - 27th International Conference, CIAA 2023, Proceedings",
address = "Germany",
}