{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T19:09:16Z","timestamp":1648840156028},"reference-count":9,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p> We present a run-time efficient implementation of compressed pattern matching automata (CPMA) of Kida et al. (2003), where a text is given as a truncation-free collage system [Formula: see text] such that variable sequence [Formula: see text] is encoded by any prefix code. We first build CPMA directly from P and [Formula: see text] in [Formula: see text] time and space, and then convert it into the decoder-embedded CPMA (DECPMA), where |P| is the pattern length and [Formula: see text] is the number of variables defined in [Formula: see text]. The bound [Formula: see text] improves the bound [Formula: see text] achieved by a straightforward application of the method of Kida et al. We experimentally show that a combination of recursive-pairing compression and byte-oriented Huffman coding allows both a high compression ratio and a high speed CPM. <\/jats:p>","DOI":"10.1142\/s0129054109006838","type":"journal-article","created":{"date-parts":[[2009,7,29]],"date-time":"2009-07-29T07:44:22Z","timestamp":1248853462000},"page":"717-733","source":"Crossref","is-referenced-by-count":2,"title":["A RUN-TIME EFFICIENT IMPLEMENTATION OF COMPRESSED PATTERN MATCHING AUTOMATA"],"prefix":"10.1142","volume":"20","author":[{"given":"TETSUYA","family":"MATSUMOTO","sequence":"first","affiliation":[{"name":"Department of Informatics, Kyushu University, 744 Moto-oka, Nishi-ku, Fukuoka 819-0395, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KAZUHITO","family":"HAGIO","sequence":"additional","affiliation":[{"name":"Department of Informatics, Kyushu University, 744 Moto-oka, Nishi-ku, Fukuoka 819-0395, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MASAYUKI","family":"TAKEDA","sequence":"additional","affiliation":[{"name":"Department of Informatics, Kyushu University, 744 Moto-oka, Nishi-ku, Fukuoka 819-0395, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0023"},{"key":"rf3","volume-title":"Text Algorithms","author":"Crochemore M.","year":"1994"},{"key":"rf4","volume":"12","author":"Gage P.","journal-title":"The C Users Journal"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00426-7"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1109\/18.841160"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1145\/248625.248639"},{"key":"rf9","first-page":"2638","volume":"39","author":"Miyazaki M.","journal-title":"Transactions of Information Processing Society of Japan"},{"key":"rf10","first-page":"187","volume":"1","author":"Miyazaki M.","journal-title":"Journal of Discrete Algorithms"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1145\/348751.348754"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054109006838","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:39:04Z","timestamp":1565138344000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054109006838"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":9,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.1142\/S0129054109006838"],"URL":"https:\/\/doi.org\/10.1142\/s0129054109006838","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}