{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T07:54:40Z","timestamp":1773388480213,"version":"3.50.1"},"reference-count":13,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,30]],"date-time":"2006-10-30T00:00:00Z","timestamp":1162166400000},"content-version":"vor","delay-in-days":4595,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Softw Pract Exp"],"published-print":{"date-parts":[[1994,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given a text string, a pattern string, and an integer <jats:italic>k<\/jats:italic>, the problem of approximate string matching with <jats:italic>k<\/jats:italic> differences is to find all substrings of the text string whose edit distance from the pattern string is less than <jats:italic>k.<\/jats:italic> The edit distance between two strings is defined as the minimum number of differences, where a difference can be a substitution, insertion, or deletion of a single character. An implementation of the dynamic programming algorithm for this problem is given that packs several characters and mod\u20104 integers into a computer word. Thus, it is a parallelization of the conventional implementation that runs on ordinary processors. Since a small alphabet means that characters have short binary codes, the degree of parallelism is greatest for small alphabets and for processors with long words. For an alphabet of size 8 or smaller and a 64 bit processor, a 21\u2010fold parallelism over the conventional algorithm can be obtained. Empirical comparisons to the basic dynamic programming algorithm, to a version of Ukkonen's algorithm, to the algorithm of Galil and Park, and to a limited implementation of the Wu\u2010Manber algorithm are given.<\/jats:p>","DOI":"10.1002\/spe.4380240402","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T17:03:21Z","timestamp":1163783001000},"page":"337-362","source":"Crossref","is-referenced-by-count":20,"title":["Approximate string matching using withinword parallelism"],"prefix":"10.1002","volume":"24","author":[{"given":"Alden H.","family":"Wright","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,30]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"e_1_2_1_3_2","volume-title":"Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison","author":"Sankoff D.","year":"1983"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-12689-9_129"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80046-2"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90023-9"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90016-4"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90010-2"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/0219067"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/135239.135244"},{"key":"e_1_2_1_11_2","first-page":"75","article-title":"A new approach to text searching","volume":"35","author":"Baeza\u2010Yates R.","year":"1992","journal-title":"Comm. Assoc. Computing. Mach."},{"key":"e_1_2_1_12_2","unstructured":"B. W.EricksonandP. H.Sellers \u2018Recognition of patterns in genetic sequences\u2019 in Reference 2 pp.55\u201391."},{"key":"e_1_2_1_13_2","unstructured":"R. J.LiptonandD.Lopresti \u2018A systolic array for rapid string comparison\u2019 Proc. 1985 Chapel Hill Conference on VLSI 1985 pp.363\u2013376."},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90045-1"}],"container-title":["Software: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fspe.4380240402","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.4380240402","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T23:38:21Z","timestamp":1698104301000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/spe.4380240402"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,4]]},"references-count":13,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1994,4]]}},"alternative-id":["10.1002\/spe.4380240402"],"URL":"https:\/\/doi.org\/10.1002\/spe.4380240402","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,4]]}}}