For any T >= 1, there are constants R = R(T) > 1 and zeta = zeta((T) > 0 and a randomized algorithm that takes as input an integer n and two strings x, y of length at most n, and runs in time O(n(1+1/T)) and ...
详细信息
ISBN:
(纸本)9781450369794
For any T >= 1, there are constants R = R(T) > 1 and zeta = zeta((T) > 0 and a randomized algorithm that takes as input an integer n and two strings x, y of length at most n, and runs in time O(n(1+1/T)) and outputs an upper bound U on the edit distance of d(edit)(x, y) that with high probability, satisfies U <= R(d(edit)(x, y) + n(1-zeta)). particular, on any input with d(edit)(x, y) >= n(1-zeta) the algorithm outputs a constant factor approximation with high probability. A similar result has been proven independently by Brakensiek and Rubinstein (this proceedings).
暂无评论