{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T13:41:37Z","timestamp":1770990097301,"version":"3.50.1"},"reference-count":30,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,30]],"date-time":"2006-10-30T00:00:00Z","timestamp":1162166400000},"content-version":"vor","delay-in-days":4626,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Softw Pract Exp"],"published-print":{"date-parts":[[1994,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A trie structure can immediately determine whether a desired key is in a given key set or not, and can find its longest match easily. Thanks to these attractive properties, a trie structure is frequently used for various fields, such as natural language dictionaries, database systems and compilers. However, the total number of states of a trie becomes large, so space requirements are not good for a huge key set. To resolve this disadvantage a new structure which reduces the total number of states in a traditional trie, called a double\u2010trie, is introduced in this paper. Insertion and deletion operations, as well as key retrieval for this double\u2010trie, are presented. The efficiency of this method is shown by the results of simulations for various key sets.<\/jats:p>","DOI":"10.1002\/spe.4380240303","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T16:56:38Z","timestamp":1163782598000},"page":"265-288","source":"Crossref","is-referenced-by-count":9,"title":["A method of compressing trie structures"],"prefix":"10.1002","volume":"24","author":[{"given":"Katsushi","family":"Morimoto","sequence":"first","affiliation":[]},{"given":"Hirokazu","family":"Iriguchi","sequence":"additional","affiliation":[]},{"given":"Jun\u2010Ichi","family":"Aoe","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,30]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/367390.367400"},{"issue":"9","key":"e_1_2_1_3_2","first-page":"1592","article-title":"A fast digital search algorithm using a double\u2010array structure\u2019 (in Japanese)","volume":"71","author":"Aoe J.","year":"1988","journal-title":"Trans. IEICE"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.31365"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380220902"},{"key":"e_1_2_1_6_2","first-page":"163","volume-title":"Data Structures and Algorithms","author":"Aho A. V.","year":"1983"},{"key":"e_1_2_1_7_2","unstructured":"D. E.Knuth The Art of Computer Programming vol. 3 Sorting and Searching 1973 pp.481\u2013505."},{"key":"e_1_2_1_8_2","volume-title":"Computer Programs for Spelling Correction","author":"Peterson J. L.","year":"1980"},{"key":"e_1_2_1_9_2","volume-title":"Data Structure Techniques","author":"Standish T. A.","year":"1980"},{"key":"e_1_2_1_10_2","unstructured":"J.AoeandM.Fujikawa \u2018An efficient representation of hierarchical semantic primitives\u2014an aid to machine translation systems\u2019 Proc. Second Int. Conf. on Supercomputing 1987 pp.361\u2013370."},{"key":"e_1_2_1_11_2","volume-title":"Compilers Principles, Techniques, and Tools","author":"Aho A. V.","year":"1986"},{"issue":"21","key":"e_1_2_1_12_2","first-page":"85","article-title":"Dynamic hashing schemes","volume":"20","author":"Enbody R. J.","year":"1988","journal-title":"ACM Computing Surveys"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.83904"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28873"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/360248.360258"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/329.295"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380211004"},{"issue":"11","key":"e_1_2_1_19_2","first-page":"841","article-title":"Median split trees: a fast lookup technique for frequency occurring keys","volume":"20","author":"Sheil B. A.","year":"1977","journal-title":"Commun. ACM"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1984.5010205"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1080\/00207169008803920"},{"issue":"4","key":"e_1_2_1_22_2","article-title":"An algorithm of compressing common suffixes for trie structures\u2019, (in Japanese)","volume":"75","author":"Aoe J.","year":"1992","journal-title":"Trans. IEICE"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/42411.42420"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/320083.320092"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1987.233491"},{"key":"e_1_2_1_27_2","unstructured":"T.Matsukawa J.NakamuraandM.Nagao \u2018An algorithm of word clustering from co\u2010occurrence data using DM decomposition and statical estimation\u2019 (in Japanese) Research Report 89\u2010NL\u201072\u20138 Information Processing Society of Japan 1989."},{"key":"e_1_2_1_28_2","unstructured":"K.MorimotoandJ.Aoe \u2018A method for building morphological and co\u2010occurrence dictionaries by trie structures\u2019 (in Japanese) Research Report 91\u2010NL\u201085\u20133 Information Processing Society of Japan 1991."},{"issue":"6","key":"e_1_2_1_29_2","first-page":"514","article-title":"Data\u2010structure of a large Japanese dictionary and morphological analysis by using it\u2019 (in Japanese)","volume":"19","author":"Nagao M.","year":"1978","journal-title":"Journal of Information Processing Society of Japan."},{"key":"e_1_2_1_30_2","unstructured":"A.NakajimaandR.Sugimura \u2018Japanese morphological analyzer with TRIE structure dictionary and graph stack for local ambiguity packing\u2019 (in Japanese) 39th Natl. Conf. on Information Processing Society of Japan 1F\u20104 1989."},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359175"}],"container-title":["Software: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fspe.4380240303","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.4380240303","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T13:28:40Z","timestamp":1698154120000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/spe.4380240303"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,3]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,3]]}},"alternative-id":["10.1002\/spe.4380240303"],"URL":"https:\/\/doi.org\/10.1002\/spe.4380240303","archive":["Portico"],"relation":{},"ISSN":["0038-0644","1097-024X"],"issn-type":[{"value":"0038-0644","type":"print"},{"value":"1097-024X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,3]]}}}