{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T15:53:44Z","timestamp":1772726024173,"version":"3.50.1"},"publisher-location":"Cham","reference-count":51,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031826696","type":"print"},{"value":"9783031826702","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-82670-2_11","type":"book-chapter","created":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T04:39:45Z","timestamp":1738816785000},"page":"136-150","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Fast Practical Compression of\u00a0Deterministic Finite Automata"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1120-5154","authenticated-orcid":false,"given":"Philip","family":"Bille","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8322-4952","authenticated-orcid":false,"given":"Inge Li","family":"G\u00f8rtz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8850-6422","authenticated-orcid":false,"given":"Max Rish\u00f8j","family":"Pedersen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,7]]},"reference":[{"key":"11_CR1","unstructured":"https:\/\/www.suricata.io\/"},{"key":"11_CR2","doi-asserted-by":"publisher","unstructured":"Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. Commun. ACM 18(6), 333\u2013340 (1975). https:\/\/doi.org\/10.1145\/360825.360855","DOI":"10.1145\/360825.360855"},{"key":"11_CR3","doi-asserted-by":"publisher","unstructured":"Antonello, R., Fernandes, S.F.L., Sadok, D., Kelner, J., Szab\u00f3, G.: Deterministic finite automaton for scalable traffic identification: the power of compressing by range. In: NOMS 2012, pp. 155\u2013162 (2012). https:\/\/doi.org\/10.1109\/NOMS.2012.6211894","DOI":"10.1109\/NOMS.2012.6211894"},{"key":"11_CR4","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.comcom.2014.12.011","volume":"61","author":"R Antonello","year":"2015","unstructured":"Antonello, R., Fernandes, S.F.L., Sadok, D.F.H., Kelner, J., Szab\u00f3, G.: Design and optimizations for efficient regular expression matching in DPI systems. Comput. Commun. 61, 103\u2013120 (2015). https:\/\/doi.org\/10.1016\/j.comcom.2014.12.011","journal-title":"Comput. Commun."},{"key":"11_CR5","doi-asserted-by":"publisher","unstructured":"Becchi, M., Cadambi, S.: Memory-efficient regular expression search using state merging. In: Proceedings of 26th INFOCOM, pp. 1064\u20131072 (2007). https:\/\/doi.org\/10.1109\/INFCOM.2007.128","DOI":"10.1109\/INFCOM.2007.128"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Becchi, M., Crowley, P.: A hybrid finite automaton for practical deep packet inspection. In: Proceedings of 3rd CoNEXT Conference, pp. 1\u201312 (2007)","DOI":"10.1145\/1364654.1364656"},{"key":"11_CR7","doi-asserted-by":"publisher","unstructured":"Becchi, M., Crowley, P.: An improved algorithm to accelerate regular expression evaluation. In: Proceedings of ANCS 2007, pp. 145\u2013154 (2007). https:\/\/doi.org\/10.1145\/1323548.1323573","DOI":"10.1145\/1323548.1323573"},{"key":"11_CR8","doi-asserted-by":"publisher","unstructured":"Becchi, M., Crowley, P.: Efficient regular expression evaluation: theory to practice. In: Proceedings of ANCS 2008, pp. 50\u201359 (2008). https:\/\/doi.org\/10.1145\/1477942.1477950","DOI":"10.1145\/1477942.1477950"},{"key":"11_CR9","doi-asserted-by":"publisher","unstructured":"Becchi, M., Crowley, P.: A-DFA: A time- and space-efficient DFA compression algorithm for fast regular expression evaluation. ACM Trans. Archit. Code Optim. 10(1), 4:1\u20134:26 (2013). https:\/\/doi.org\/10.1145\/2445572.2445576","DOI":"10.1145\/2445572.2445576"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Bille, P., G\u00f8rtz, I.L., Pedersen, M.R.: Fast practical compression of deterministic finite automata. arXiv:2306.12771 (2024)","DOI":"10.1007\/978-3-031-82670-2_11"},{"key":"11_CR11","unstructured":"Bille, P., G\u00f8rtz, I.L., Puglisi, S.J., Tarnow, S.R.: Hierarchical relative lempel-ziv compression. In: Proceedings of 21st SEA (2023)"},{"key":"11_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/3-540-48405-1_14","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 99","author":"J Black","year":"1999","unstructured":"Black, J., Halevi, S., Krawczyk, H., Krovetz, T., Rogaway, P.: UMAC: fast and secure message authentication. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 216\u2013233. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-48405-1_14"},{"key":"11_CR13","unstructured":"Broder, A.Z.: On the resemblance and containment of documents. In: Proceedings of SEQUENCES, pp. 21\u201329 (1997)"},{"issue":"3","key":"11_CR14","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1006\/jcss.1999.1690","volume":"60","author":"AZ Broder","year":"2000","unstructured":"Broder, A.Z., Charikar, M., Frieze, A.M., Mitzenmacher, M.: Min-wise independent permutations. J. Comput. Syst. Sci. 60(3), 630\u2013659 (2000). https:\/\/doi.org\/10.1006\/jcss.1999.1690","journal-title":"J. Comput. Syst. Sci."},{"key":"11_CR15","doi-asserted-by":"publisher","unstructured":"Brodie, B.C., Taylor, D.E., Cytron, R.K.: A scalable architecture for high-throughput regular-expression pattern matching. In: Proceedings of 33rd ISCA, pp. 191\u2013202 (2006). https:\/\/doi.org\/10.1109\/ISCA.2006.7","DOI":"10.1109\/ISCA.2006.7"},{"key":"11_CR16","doi-asserted-by":"publisher","unstructured":"Charikar, M.: Similarity estimation techniques from rounding algorithms. In: Proceedings of 34th STOC, pp. 380\u2013388 (2002). https:\/\/doi.org\/10.1145\/509907.509965","DOI":"10.1145\/509907.509965"},{"key":"11_CR17","doi-asserted-by":"crossref","unstructured":"Ding, S., Attenberg, J., Suel, T.: Scalable techniques for document identifier assignment in inverted indexes. In: Proceedings of 19th WWW, pp. 311\u2013320 (2010)","DOI":"10.1145\/1772690.1772723"},{"key":"11_CR18","unstructured":"Douglis, F., Iyengar, A.: Application-specific delta-encoding via resemblance detection. In: Proceedings of USENIX ATC, General Track 2003, pp. 113\u2013126 (2003). http:\/\/www.usenix.org\/events\/usenix03\/tech\/douglis.html"},{"issue":"1","key":"11_CR19","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF00978378","volume":"10","author":"AM Farley","year":"1981","unstructured":"Farley, A.M., Hedetniemi, S.T., Proskurowski, A.: Partitioning trees: matching, domination, and maximum diameter. Int. J. Parallel Program. 10(1), 55\u201361 (1981). https:\/\/doi.org\/10.1007\/BF00978378","journal-title":"Int. J. Parallel Program."},{"issue":"5","key":"11_CR20","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1145\/1452335.1452339","volume":"38","author":"D Ficara","year":"2008","unstructured":"Ficara, D., Giordano, S., Procissi, G., Vitucci, F., Antichi, G., Pietro, A.D.: An improved DFA for fast regular expression matching. Comput. Commun. Rev. 38(5), 29\u201340 (2008). https:\/\/doi.org\/10.1145\/1452335.1452339","journal-title":"Comput. Commun. Rev."},{"issue":"3","key":"11_CR21","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1109\/TNET.2010.2089639","volume":"19","author":"D Ficara","year":"2011","unstructured":"Ficara, D., Pietro, A.D., Giordano, S., Procissi, G., Vitucci, F., Antichi, G.: Differential encoding of dfas for fast regular expression matching. IEEE\/ACM Trans. Netw. 19(3), 683\u2013694 (2011). https:\/\/doi.org\/10.1109\/TNET.2010.2089639","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"4","key":"11_CR22","doi-asserted-by":"publisher","first-page":"1011","DOI":"10.1109\/TC.2022.3187338","volume":"72","author":"L Gong","year":"2023","unstructured":"Gong, L., Wang, C., Xia, H., Chen, X., Li, X., Zhou, X.: Enabling fast and memory-efficient acceleration for pattern matching workloads: the lightweight automata processing engine. IEEE Trans. Comput. 72(4), 1011\u20131025 (2023). https:\/\/doi.org\/10.1109\/TC.2022.3187338","journal-title":"IEEE Trans. Comput."},{"issue":"1","key":"11_CR23","doi-asserted-by":"publisher","first-page":"321","DOI":"10.4086\/toc.2012.v008a014","volume":"8","author":"S Har-Peled","year":"2012","unstructured":"Har-Peled, S., Indyk, P., Motwani, R.: Approximate nearest neighbor: towards removing the curse of dimensionality. Theory Comput. 8(1), 321\u2013350 (2012). https:\/\/doi.org\/10.4086\/toc.2012.v008a014","journal-title":"Theory Comput."},{"key":"11_CR24","unstructured":"Hemmingsen, M., Lam, B.W.: Fast Compression of DFAs for Intrusion Detection Systems. Master\u2019s thesis, Tech. Uni. Denmark. (2021)"},{"key":"11_CR25","doi-asserted-by":"publisher","unstructured":"Kong, S., Smith, R., Estan, C.: Efficient signature matching with multiple alphabet compression tables. In: Proceedings of 4th SECURECOMM, p.\u00a01 (2008). https:\/\/doi.org\/10.1145\/1460877.1460879","DOI":"10.1145\/1460877.1460879"},{"key":"11_CR26","doi-asserted-by":"publisher","unstructured":"Krc\u00e1l, L., Holub, J.: Incremental locality and clustering-based compression. In: DCC 2015, pp. 203\u2013212 (2015). https:\/\/doi.org\/10.1109\/DCC.2015.23","DOI":"10.1109\/DCC.2015.23"},{"issue":"1","key":"11_CR27","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"JB Kruskal","year":"1956","unstructured":"Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7(1), 48\u201350 (1956)","journal-title":"Proc. Am. Math. Soc."},{"key":"11_CR28","unstructured":"Kulkarni, P., Douglis, F., LaVoie, J.D., Tracey, J.M.: Redundancy elimination within large collections of files. In: Proceedings of USENIX ATC, General Track 2004, pp. 59\u201372 (2004)"},{"key":"11_CR29","doi-asserted-by":"publisher","unstructured":"Kumar, S., Dharmapurikar, S., Yu, F., Crowley, P., Turner, J.S.: Algorithms to accelerate multiple regular expressions matching for deep packet inspection. In: Proceedings of SIGCOMM 2006, pp. 339\u2013350 (2006). https:\/\/doi.org\/10.1145\/1159913.1159952","DOI":"10.1145\/1159913.1159952"},{"key":"11_CR30","doi-asserted-by":"publisher","unstructured":"Kumar, S., Turner, J.S., Williams, J.: Advanced algorithms for fast and scalable deep packet inspection. In: Proceedings of ANCS 2006, pp. 81\u201392 (2006). https:\/\/doi.org\/10.1145\/1185347.1185359","DOI":"10.1145\/1185347.1185359"},{"key":"11_CR31","doi-asserted-by":"publisher","unstructured":"Liu, A.X., Torng, E.: An overlay automata approach to regular expression matching. In: Proceedings of 33rd INFOCOM, pp. 952\u2013960 (2014). https:\/\/doi.org\/10.1109\/INFOCOM.2014.6848024","DOI":"10.1109\/INFOCOM.2014.6848024"},{"issue":"3","key":"11_CR32","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1049\/el.2016.2613","volume":"53","author":"S Liu","year":"2017","unstructured":"Liu, S., Su, S., Liu, D., Huang, Z., Xiao, M.: Efficient compression algorithm for ternary content addressable memory-based regular expression matching. Electron. Lett. 53(3), 152\u2013154 (2017)","journal-title":"Electron. Lett."},{"key":"11_CR33","doi-asserted-by":"publisher","unstructured":"Matousek, D., Kubis, J., Matousek, J., Korenek, J.: Regular expression matching with pipelined delayed input dfas for high-speed networks. In: Proceedings of ANCS 2018, pp. 104\u2013110 (2018). https:\/\/doi.org\/10.1145\/3230718.3230730","DOI":"10.1145\/3230718.3230730"},{"key":"11_CR34","doi-asserted-by":"publisher","unstructured":"Matousek, D., Matousek, J., Korenek, J.: High-speed regular expression matching with pipelined memory-based automata. In: Proceedings of 26th FCCM, p.\u00a0214 (2018). https:\/\/doi.org\/10.1109\/FCCM.2018.00048","DOI":"10.1109\/FCCM.2018.00048"},{"key":"11_CR35","unstructured":"Meiners, C.R., Patel, J., Norige, E., Torng, E., Liu, A.X.: Fast regular expression matching using small tcams for network intrusion detection and prevention systems. In: 19th USENIX Security, pp. 111\u2013126 (2010)"},{"key":"11_CR36","doi-asserted-by":"publisher","unstructured":"Ouyang, Z., Memon, N.D., Suel, T., Trendafilov, D.: Cluster-based delta compression of a collection of files. In: Proceedings of 3rd WISE, pp. 257\u2013268 (2002). https:\/\/doi.org\/10.1109\/WISE.2002.1181662","DOI":"10.1109\/WISE.2002.1181662"},{"issue":"6","key":"11_CR37","doi-asserted-by":"publisher","first-page":"1701","DOI":"10.1109\/TNET.2014.2309014","volume":"22","author":"J Patel","year":"2014","unstructured":"Patel, J., Liu, A.X., Torng, E.: Bypassing space explosion in high-speed regular expression matching. IEEE\/ACM Trans. Netw. 22(6), 1701\u20131714 (2014). https:\/\/doi.org\/10.1109\/TNET.2014.2309014","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"23\u201324","key":"11_CR38","doi-asserted-by":"publisher","first-page":"2435","DOI":"10.1016\/S1389-1286(99)00112-7","volume":"31","author":"V Paxson","year":"1999","unstructured":"Paxson, V.: Bro: a system for detecting network intruders in real-time. Comput. Netw. 31(23\u201324), 2435\u20132463 (1999)","journal-title":"Comput. Netw."},{"key":"11_CR39","doi-asserted-by":"publisher","unstructured":"Peel, A., Wirth, A., Zobel, J.: Collection-based compression using discovered long matching strings. In: Proceedings of 20th CIKM, pp. 2361\u20132364 (2011). https:\/\/doi.org\/10.1145\/2063576.2063967","DOI":"10.1145\/2063576.2063967"},{"issue":"6","key":"11_CR40","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"RC Prim","year":"1957","unstructured":"Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36(6), 1389\u20131401 (1957)","journal-title":"Bell Syst. Tech. J."},{"issue":"3","key":"11_CR41","first-page":"14","volume":"17","author":"S Prithi","year":"2017","unstructured":"Prithi, S., Sumathi, S.: A survey on recent dfa compression techniques for deep packet inspection in network intrusion detection system. J. Electr. Eng. 17(3), 14\u201314 (2017)","journal-title":"J. Electr. Eng."},{"key":"11_CR42","doi-asserted-by":"publisher","unstructured":"Qi, Y., et al.: FEACAN: front-end acceleration for content-aware network processing. In: Proceedings of 30th INFOCOM, pp. 2114\u20132122 (2011). https:\/\/doi.org\/10.1109\/INFCOM.2011.5935021","DOI":"10.1109\/INFCOM.2011.5935021"},{"key":"11_CR43","unstructured":"Roesch, M.: Snort: lightweight intrusion detection for networks. In: Proceedings of 13th LISA, pp. 229\u2013238 (1999)"},{"key":"11_CR44","doi-asserted-by":"publisher","unstructured":"Roussev, V.: Data fingerprinting with similarity digests. In: IFIP International Conference Digital Forensics 2010, vol.\u00a0337, pp. 207\u2013226 (2010). https:\/\/doi.org\/10.1007\/978-3-642-15506-2_15","DOI":"10.1007\/978-3-642-15506-2_15"},{"key":"11_CR45","doi-asserted-by":"publisher","unstructured":"Shankar, S.S., Lin, P., Herkersdorf, A., Wild, T.: A divide and conquer state grouping method for bitmap based transition compression. In: Proceedings of 18th PDCAT, pp. 400\u2013406 (2017). https:\/\/doi.org\/10.1109\/PDCAT.2017.00071","DOI":"10.1109\/PDCAT.2017.00071"},{"key":"11_CR46","doi-asserted-by":"publisher","unstructured":"Shilane, P., Huang, M., Wallace, G., Hsu, W.: Wan-optimized replication of backup datasets using stream-informed delta compression. ACM Trans. Storage 8(4), 13:1\u201313:26 (2012). https:\/\/doi.org\/10.1145\/2385603.2385606","DOI":"10.1145\/2385603.2385606"},{"key":"11_CR47","doi-asserted-by":"publisher","unstructured":"Tang, Q., Jiang, L., Dai, Q., Su, M., Xie, H., Fang, B.: RICS-DFA: a space and time-efficient signature matching algorithm with reduced input character set. Concurr. Comput. Pract. Exp. 29(20) (2017). https:\/\/doi.org\/10.1002\/cpe.3940","DOI":"10.1002\/cpe.3940"},{"key":"11_CR48","doi-asserted-by":"publisher","unstructured":"Tuck, N., Sherwood, T., Calder, B., Varghese, G.: Deterministic memory-efficient string matching algorithms for intrusion detection. In: Proceedings of 23rd INFOCOM, pp. 2628\u20132639 (2004). https:\/\/doi.org\/10.1109\/INFCOM.2004.1354682","DOI":"10.1109\/INFCOM.2004.1354682"},{"key":"11_CR49","unstructured":"Xia, W., Jiang, H., Feng, D., Hua, Y.: Silo: a similarity-locality based near-exact deduplication scheme with low RAM overhead and high throughput. In: USENIX ATC 2011 (2011)"},{"issue":"4","key":"11_CR50","doi-asserted-by":"publisher","first-page":"2991","DOI":"10.1109\/COMST.2016.2566669","volume":"18","author":"C Xu","year":"2016","unstructured":"Xu, C., Chen, S., Su, J., Yiu, S., Hui, L.C.K.: A survey on regular expression matching for deep packet inspection: applications, algorithms, and hardware platforms. IEEE Commun. Surv. Tutorials 18(4), 2991\u20133029 (2016). https:\/\/doi.org\/10.1109\/COMST.2016.2566669","journal-title":"IEEE Commun. Surv. Tutorials"},{"key":"11_CR51","doi-asserted-by":"publisher","unstructured":"Yu, F., Chen, Z., Diao, Y., Lakshman, T.V., Katz, R.H.: Fast and memory-efficient regular expression matching for deep packet inspection. In: Proceedings of ANCS 2006, pp. 93\u2013102 (2006). https:\/\/doi.org\/10.1145\/1185347.1185360","DOI":"10.1145\/1185347.1185360"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2025: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-82670-2_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T05:02:55Z","timestamp":1757134975000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-82670-2_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031826696","9783031826702"],"references-count":51,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-82670-2_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"7 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bratislava","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovakia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 January 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 January 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"50","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.sofsem.sk","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}