{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,18]],"date-time":"2025-01-18T16:10:24Z","timestamp":1737216624617,"version":"3.33.0"},"reference-count":32,"publisher":"Wiley","issue":"7","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"vor","delay-in-days":6653,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp;amp; Computers in Japan"],"published-print":{"date-parts":[[1989,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper presents an efficient digital search algorithm by introducing a new internal array structure called a double\u2010array that combines the fast access of a matrix form with the compactness of a list form. Each arc of a digital search tree called a DS\u2010tree can be computed from the double\u2010array in<jats:italic>O<\/jats:italic>(1) time; that is, the worst\u2010case time complexity for retrieving a key becomes<jats:italic>O(k)<\/jats:italic>for the length<jats:italic>k<\/jats:italic>of that key. The double\u2010array is modified to make the size compact while maintaining fast access and algorithms for retrieval, insertion and deletion are presented. Suppose that the size of the double\u2010array is<jats:italic>n<\/jats:italic>+<jats:italic>cm<\/jats:italic>, where<jats:italic>n<\/jats:italic>is the number of nodes of the DS\u2010tree,<jats:italic>m<\/jats:italic>is the number of input symbols, and<jats:italic>c<\/jats:italic>is a constant depending on each double\u2010array. Then it is proved theoretically that the worst\u2010case times of deletion and insertion are proportional to<jats:italic>cm<\/jats:italic>and<jats:italic>cm<\/jats:italic><jats:sup>2<\/jats:sup>, respectively, independent of<jats:italic>n<\/jats:italic>. From the experimental results of building the double\u2010array incrementally for various sets of keys, it is shown that the constant<jats:italic>c<\/jats:italic>has an extremely small value, ranging from 0.17 to 1.13.<\/jats:p>","DOI":"10.1002\/scj.4690200710","type":"journal-article","created":{"date-parts":[[2007,7,7]],"date-time":"2007-07-07T18:08:56Z","timestamp":1183831736000},"page":"92-103","source":"Crossref","is-referenced-by-count":1,"title":["A fast digital search algorithm using a double\u2010array structure"],"prefix":"10.1002","volume":"20","author":[{"given":"Jun\u2010Ichi","family":"Aoe","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_2_2","DOI":"10.1145\/360825.360855"},{"volume-title":"Data Structures and Algorithms","year":"1983","author":"Aho A. V.","key":"e_1_2_1_3_2"},{"volume-title":"Compilers Principles, Techniques, and Tools","year":"1986","author":"Aho A. V.","key":"e_1_2_1_4_2"},{"key":"e_1_2_1_5_2","first-page":"1235","article-title":"An efficient method for storing and retrieving finite state machines","volume":"65","author":"Aoe J.","year":"1982","journal-title":"I.E.C.E. Trans."},{"unstructured":"Electronica Japonica 13","key":"e_1_2_1_5_3"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_2","DOI":"10.1080\/00207168208803329"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_2","DOI":"10.1109\/TSE.1983.236167"},{"key":"e_1_2_1_8_2","first-page":"414","article-title":"An efficient method for storing and retrieving pattern matching machines","volume":"24","author":"Aoe J.","year":"1983","journal-title":"Trans. IPS Japan"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_2","DOI":"10.1109\/TSE.1984.5010205"},{"key":"e_1_2_1_10_2","first-page":"211","article-title":"An efficient algorithm of reducing sparse matrices by row displacements","volume":"26","author":"Aoe J.","year":"1985","journal-title":"Trans. IPS Japan"},{"unstructured":"J.Aoe Y.YamamotoandR.Shimada.An efficient implementation of static string pattern matching machines. Proc. of the First Int. Conf. on Supercomputing pp.491\u2013498(Dec.1985).","key":"e_1_2_1_11_2"},{"key":"e_1_2_1_12_2","first-page":"653","article-title":"An efficient implementation of finite state machines using a double\u2010array structure","volume":"70","author":"Aoe J.","year":"1987","journal-title":"I.E.C.E. Trans."},{"unstructured":"J.AoeandM.Fujikawa.An efficient representation of hierarchical semantic primitives\u2013An aid to machine translation systems. Proc. of the Second Int. Conf. on Supercomputing pp.361\u2013370(May1987).","key":"e_1_2_1_13_2"},{"doi-asserted-by":"crossref","unstructured":"J.Aoe S.YasutomeandT.Sato.An efficient digital search algorithm by using a double\u2010array structure. In: Proc. of the Twelfth Int. Comput. Softw. & Appli. Conf. pp.472\u2013479(Oct.1988). [To appear in IEEE Trans. Software Engineering.]","key":"e_1_2_1_14_2","DOI":"10.1109\/CMPSAC.1988.17222"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_2","DOI":"10.1137\/0215044"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_2","DOI":"10.1145\/358808.358813"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_2","DOI":"10.1093\/comjnl\/28.1.54"},{"unstructured":"S. C.Johnson.YACC\u2013yet another compiler\u2010compiler. CSTR 32 Bell Lab. NJ pp.1\u201334(1975).","key":"e_1_2_1_18_2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_2","DOI":"10.1145\/358800.358806"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_2","DOI":"10.1109\/TSE.1987.233491"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_2","DOI":"10.1145\/320083.320092"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_2","DOI":"10.1145\/367390.367400"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_2","DOI":"10.1145\/828.1884"},{"volume-title":"The Art of Computer Programming. I, Fundamental Algorithm","author":"Knuth D. E.","first-page":"295","key":"e_1_2_1_24_2"},{"unstructured":"III Sorting and Searching pp.481\u2013505(1973).","key":"e_1_2_1_24_3"},{"unstructured":"M. E.Lesk.Lex\u2013A lexical analyzer generator. CSTR 39 Bell Lab. NJ pp.1\u201313(Oct.1975).","key":"e_1_2_1_25_2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_2","DOI":"10.1145\/360248.360258"},{"key":"e_1_2_1_27_2","series-title":"Lecture Notes in Comput. Sci.","volume-title":"Computer Programs for Spelling Correction","author":"Peterson J. L.","year":"1980"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_2","DOI":"10.1145\/359642.359653"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_2","DOI":"10.1145\/359863.359887"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_2","DOI":"10.1145\/359168.359175"},{"volume-title":"Data Structure Techniques","year":"1980","author":"Standish T. A.","key":"e_1_2_1_31_2"}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690200710","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690200710","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,18]],"date-time":"2025-01-18T15:47:55Z","timestamp":1737215275000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690200710"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,1]]},"references-count":32,"journal-issue":{"issue":"7","published-print":{"date-parts":[[1989,1]]}},"alternative-id":["10.1002\/scj.4690200710"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690200710","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"type":"print","value":"0882-1666"},{"type":"electronic","value":"1520-684X"}],"subject":[],"published":{"date-parts":[[1989,1]]}}}