dc.creator | Barbay, Jeremy | |
dc.creator | Perez-Lantero, Pablo | |
dc.date.accessioned | 2019-05-31T15:21:16Z | |
dc.date.available | 2019-05-31T15:21:16Z | |
dc.date.created | 2019-05-31T15:21:16Z | |
dc.date.issued | 2018 | |
dc.identifier | ACM Transactions on Algorithms, Volumen 14, Issue 4, 2018 | |
dc.identifier | 15496333 | |
dc.identifier | 15496325 | |
dc.identifier | 10.1145/3232057 | |
dc.identifier | https://repositorio.uchile.cl/handle/2250/169555 | |
dc.description.abstract | The Swap-Insert Correction distance from a string S of length n to another string L of length m≥n on the alphabet [1.δ] is the minimum number of insertions, and swaps of pairs of adjacent symbols, converting S into L. Contrarily to other correction distances, computing it is NP-Hard in the size δ of the alphabet. We describe an algorithm computing this distance in time within O(δ2nmtδ.1), where for each [1.δ] there are occurrences of in S,mϵoccurrences of ¿ in L, and where "t = max [1.δ] min is a new parameter of the analysis, measuring one aspect of the difficulty of the instance. The difficulty "t is bounded by above by various terms, such as the length n of the shortest string S, and by the maximum number of occurrences of a single character in S (max[1.δ]). This result illustrates how, in many cases, the correction distance between two strings can be easier to compute than in the worst case scenario. | |
dc.language | en | |
dc.publisher | Association for Computing Machinery | |
dc.rights | http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ | |
dc.rights | Attribution-NonCommercial-NoDerivs 3.0 Chile | |
dc.source | ACM Transactions on Algorithms | |
dc.subject | Adaptive | |
dc.subject | Dynamic programming | |
dc.subject | Edit distance | |
dc.subject | Insert | |
dc.subject | Swap | |
dc.title | Adaptive computation of the swap-insert correction distance | |
dc.type | Artículo de revista | |