{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:32:26Z","timestamp":1750221146543,"version":"3.41.0"},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,8,9]],"date-time":"2018-08-09T00:00:00Z","timestamp":1533772800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"CONICYT FONDECYT\/Regular","award":["1170366 and 1160543"],"award-info":[{"award-number":["1170366 and 1160543"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,10,31]]},"abstract":"<jats:p>\n            The Swap-Insert Correction distance from a string\n            <jats:italic>S<\/jats:italic>\n            of length\n            <jats:italic>n<\/jats:italic>\n            to another string\n            <jats:italic>L<\/jats:italic>\n            of length\n            <jats:italic>m<\/jats:italic>\n            \u2265\n            <jats:italic>n<\/jats:italic>\n            on the alphabet [1\u2025\u03c3] is the minimum number of insertions, and swaps of pairs of adjacent symbols, converting\n            <jats:italic>S<\/jats:italic>\n            into\n            <jats:italic>L<\/jats:italic>\n            . Contrarily to other correction distances, computing it is NP-Hard in the size \u03c3 of the alphabet. We describe an algorithm computing this distance in time within\n            <jats:italic>O<\/jats:italic>\n            (\u03c3\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>nmg<\/jats:italic>\n            <jats:sup>\u03c3\u22121<\/jats:sup>\n            ), where for each \u03b1 \u2208 [1\u2025\u03c3] there are\n            <jats:italic>n<\/jats:italic>\n            <jats:sub>\u03b1<\/jats:sub>\n            occurrences of \u03b1 in\n            <jats:italic>S<\/jats:italic>\n            ,\n            <jats:italic>m<\/jats:italic>\n            <jats:sub>\u03b1<\/jats:sub>\n            occurrences of \u03b1 in\n            <jats:italic>L<\/jats:italic>\n            , and where\n            <jats:italic>g<\/jats:italic>\n            = max\n            <jats:sub>\u03b1\u2208[1\u2025\u03c3]<\/jats:sub>\n            min{\n            <jats:italic>n<\/jats:italic>\n            <jats:sub>\u03b1<\/jats:sub>\n            ,\n            <jats:italic>m<\/jats:italic>\n            <jats:sub>\u03b1<\/jats:sub>\n            \u2212\n            <jats:italic>n<\/jats:italic>\n            <jats:sub>\u03b1<\/jats:sub>\n            } is a new parameter of the analysis, measuring one aspect of the difficulty of the instance. The difficulty\n            <jats:italic>g<\/jats:italic>\n            is bounded by above by various terms, such as the length\n            <jats:italic>n<\/jats:italic>\n            of the shortest string\n            <jats:italic>S<\/jats:italic>\n            , and by the maximum number of occurrences of a single character in\n            <jats:italic>S<\/jats:italic>\n            (max\n            <jats:sub>\u03b1 \u2208[1\u2025\u03c3]<\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            <jats:sub>\u03b1<\/jats:sub>\n            ). This result illustrates how, in many cases, the correction distance between two strings can be easier to compute than in the worst case scenario.\n          <\/jats:p>","DOI":"10.1145\/3232057","type":"journal-article","created":{"date-parts":[[2018,8,13]],"date-time":"2018-08-13T12:29:41Z","timestamp":1534163381000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Adaptive Computation of the Swap-Insert Correction Distance"],"prefix":"10.1145","volume":"14","author":[{"given":"J\u00e9r\u00e9my","family":"Barbay","sequence":"first","affiliation":[{"name":"Departamento de Ciencias de la Computaci\u00f3n, Universidad de Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pablo","family":"P\u00e9rez-Lantero","sequence":"additional","affiliation":[{"name":"Departamento de Matem\u00e1tica y Ciencia de la Computaci\u00f3n, Universidad de Santiago, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,8,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.10.003"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"J. Barbay. 2018. Adaptive computation of the discrete Fr\u00e9chet Distance. arxiv:cs.CG\/1806.01226","DOI":"10.1007\/978-3-030-00479-8_5"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"J. Barbay and A. Olivares. 2018. Indexed dynamic programming to boost edit distance and LCSS computation. arxiv:cs.IR\/1806.04277","DOI":"10.1007\/978-3-030-00479-8_6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23826-5_3"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/829519.830817"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","unstructured":"T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2009. Introduction to Algorithms (3rd ed.). The MIT Press.","DOI":"10.5555\/1614191"},{"key":"e_1_2_1_7_1","unstructured":"T. Eiter and H. Mannila. 1994. Computing Discrete Fr\u00e9chet Distance. Technical Report. Technical Report CD-TR 94\/64 Christian Doppler Laboratory for Expert Systems TU Vienna Austria."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.11.002"},{"volume-title":"The Binary String-to-String Correction Problem. Master\u2019s thesis","author":"Spreen T. D.","key":"e_1_2_1_9_1","unstructured":"T. D. Spreen. 2013. The Binary String-to-String Correction Problem. Master\u2019s thesis. University of Victoria, Canada."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/800116.803771"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/321796.321811"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321880"},{"volume-title":"String to String Correction Kernelization. Master\u2019s thesis","author":"Watt N.","key":"e_1_2_1_13_1","unstructured":"N. Watt. 2013. String to String Correction Kernelization. Master\u2019s thesis. University of Victoria, Canada."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3232057","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3232057","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:17Z","timestamp":1750208897000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3232057"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,9]]},"references-count":13,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,10,31]]}},"alternative-id":["10.1145\/3232057"],"URL":"https:\/\/doi.org\/10.1145\/3232057","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,8,9]]},"assertion":[{"value":"2015-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}