{"entities":{"Q2224111":{"pageid":2234854,"ns":120,"title":"Item:Q2224111","lastrevid":71604546,"modified":"2026-04-13T23:21:14Z","type":"item","id":"Q2224111","labels":{"en":{"language":"en","value":"Efficient dictionary matching by Aho-Corasick automata of truncated patterns"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7305389"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2224111$2BF78ECC-2073-4047-981E-DCACC0402C8C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6b4b6b6892f07dec3151f5a73aa606ba7a160b27","datavalue":{"value":{"text":"Efficient dictionary matching by Aho-Corasick automata of truncated patterns","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2224111$F9976485-9EC6-483D-A686-A633D27B58B8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a115349ea3696a556ec868b43ad7a3b54ebc2f1f","datavalue":{"value":"1453.68066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2224111$44CA4D7D-5182-41D9-AA5C-12EB0E400C60","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e51704c4a8bbb99a04f2bb577bc33a4bdfc9709a","datavalue":{"value":"10.1504/IJCSM.2016.078738","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2224111$E6CCE224-92ED-42CA-A48E-192026FEFB21","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1fae73a1077067b50ca05195688338575b0f2987","datavalue":{"value":{"entity-type":"item","numeric-id":639295,"id":"Q639295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2224111$724B785E-743B-4E09-A1C9-0020A956074C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"689a72ea8b5f6edb69093e2da71bca6f80a82761","datavalue":{"value":{"entity-type":"item","numeric-id":2224110,"id":"Q2224110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2224111$8E43ED8B-FCFF-4469-8568-6444559C9690","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c9337011c4414308503dac14e105a83a6240fbc4","datavalue":{"value":{"entity-type":"item","numeric-id":595106,"id":"Q595106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2224111$6A94A92F-20D4-4912-B22B-A0EA323F8182","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f306f7a0701f0c426c5681c314795b1e314a5dc6","datavalue":{"value":{"entity-type":"item","numeric-id":391694,"id":"Q391694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2224111$54FE5F7D-893E-4FF0-BC47-954CD2374EAA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a4fdcf569a0845156edf00801a6025e0e3cf1d2e","datavalue":{"value":{"time":"+2021-02-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2224111$7FC9C44A-5F89-4E80-9F41-C8493692852A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"70c5fb89aa0311d16b9bde05b1fa69f2bb5bf394","datavalue":{"value":"Summary: We present a space-efficient data structure for dictionary matching. We truncate patterns to truncated patterns where symbols are \\(\\ell\\)-length substrings of the pattern. By employing the AC automaton of truncated patterns and that of \\(\\ell\\)-length substrings, we simulate the AC automaton of the original pattern set. The new structure is space economical as we apply the prefix merging to substrings of patterns. Using this structure, the dictionary matching runs in \\(O(n \\log k + \\mathrm{tocc} \\log k + \\mathrm{occ})\\) time where \\(n\\) is the length of the text, \\(k\\) the number of patterns, occ the number of occurrences of patterns in the text, and tocc the number of occurrences of strings that are longest prefix of each pattern with length of a multiple of \\(\\ell\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2224111$556DC027-DB2B-4612-B3D4-AC90B0373AAB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2224111$91D93474-FEF3-4169-BAB5-B30286A086D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2224111$EBA9904D-E46D-4CCD-9CE9-3DB98DBE0E3B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"76aae028f770f447984c157f0a37416a68e2c67b","datavalue":{"value":"7305389","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2224111$69C9C191-6B16-42DA-BB18-2AFBE2F7B38A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3c0bb52add66026c22aa460ea7c41cd49218b6d","datavalue":{"value":"dictionary matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2224111$D4A90629-6EFB-4822-9EA4-ECC48903C62E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"704f77a389167a622b29fd6a31b9f413c489eabe","datavalue":{"value":"Aho-Corasick automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q2224111$F95F8D7E-0234-4D62-A367-1CE697F73EEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c8d5c33376f59c07e5aff463b6f62e008ff50972","datavalue":{"value":"truncated patterns","type":"string"},"datatype":"string"},"type":"statement","id":"Q2224111$951ED558-0F97-4D3E-B36E-0555916E9EA5","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2224111$EDD2015E-92DF-4ADB-A1ED-8520040359FE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4fa9535e874cd536015a35c7d86d605808e64a93","datavalue":{"value":{"entity-type":"item","numeric-id":3575239,"id":"Q3575239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22790f6872509810fc0322a4dc97844d3859d928","datavalue":{"value":{"amount":"+0.8793876767158508","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2224111$E3D3F002-4BAA-4695-8A07-6461B1933831","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9c4b1e7e29010738626b906099c15265fea658c","datavalue":{"value":{"entity-type":"item","numeric-id":2326393,"id":"Q2326393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c612053eaf90109839f08110b5ed1d8e22a482d","datavalue":{"value":{"amount":"+0.850633442401886","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2224111$5B4FB2AD-19AA-48A9-B4D4-D74A82D008E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84f7944579bd7dee90d427a9b411270e948c2b4e","datavalue":{"value":{"entity-type":"item","numeric-id":2344744,"id":"Q2344744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f044ca765c1c72b02881081c3db0ed005dfdb4a1","datavalue":{"value":{"amount":"+0.8472830653190613","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2224111$D0641EDC-3CDA-4D4B-B371-C4D188FC290E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99e8467e46b830333c216920bafe721dfb1bfd9f","datavalue":{"value":{"entity-type":"item","numeric-id":5327505,"id":"Q5327505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37f319176a5f219c66d6fec00b158788d9ff8e66","datavalue":{"value":{"amount":"+0.8416257500648499","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2224111$68072F70-25E6-4D51-9DC3-4C504CC74F36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"832a63b21cf53ddd4509f4a2563deed8e5800456","datavalue":{"value":{"entity-type":"item","numeric-id":1796836,"id":"Q1796836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36cdbc2fe1d4852a42d321aa46ac720ca5b421fb","datavalue":{"value":{"amount":"+0.8187289237976074","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2224111$A4B1B7CE-3862-4125-A703-6F63EAEC7594","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Efficient dictionary matching by Aho-Corasick automata of truncated patterns","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Efficient_dictionary_matching_by_Aho-Corasick_automata_of_truncated_patterns"}}}}}