Efficiently Approximating Edit Distance Between Pseudorandom Strings
Efficiently Approximating Edit Distance Between Pseudorandom Strings
复制标题
有效地近似伪随机字符串之间的编辑距离
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
William Kuszmaul
中科院分区：
文献类型：
--
作者：
William Kuszmaul
我们提出了一种算法，用于在两个字符串x和y之间的编辑距离ED（x，y），该算法通过一个字符串x满足天然伪态度属性的程度进行了参数。放置在第二个字符串y上，可以由对X完全了解的对手构建。
我们说x是（p，b）-pseudorandom，如果x的所有对a和b的a和b的x b-letter substrings x满足eD（a，b）≥pb，我们的算法都会在A之间计算A算法。 （p，b）-pseudorandom string x和一个任意字符串y在时间O（1/p）的因子内，如果是随机生成X的，则具有很高的概率。 ω（1），o（logn）） - 伪andom，允许我们要在几乎线性时间内计算恒定因子的ED（X，Y）。
我们的算法是可靠的，因为它可以处理X的一小部分是对抗性的（即，在这种情况下不满足伪界的属性）。
我们的伪随机模型的不对称性在x是源字符串的情况下具有特殊的外观，这意味着ED（x，y）将对许多字符串进行计算。 ed（x，y）计算，b是字符串x为（1/α，b）-pseudorandom的最小块大小。 ]，所以所有人ED形式（x，y）的未来计算可能是O（α） - 时间O（NB）。在时间O（N4/3B2/3）中实现O（α） - 附近。
We present an algorithm for approximating the edit distance ed(x, y) between two strings x and y in time parameterized by the degree to which one of the strings x satisfies a natural pseudorandomness property. The pseudorandomness model is asymmetric in that no requirements are placed on the second string y, which may be constructed by an adversary with full knowledge of x.
We say that x is (p, B)-pseudorandom if all pairs a and b of disjoint B-letter substrings of x satisfy ed(a,b) ≥ pB. Given parameters p and B, our algorithm computes the edit distance between a (p, B)-pseudorandom string x and an arbitrary string y within a factor of O(1/p) in time O(nB), with high probability. If x is generated at random, then with high probability it will be (Ω(1),O(logn))-pseudorandom, allowing us to compute ed(x, y) within a constant factor in near linear time. For strings x of varying degrees of pseudorandomness, our algorithm offers a continuum of runtimes.
Our algorithm is robust in the sense that it can handle a small portion of x being adversarial (i.e., not satisfying the pseudorandomness property). In this case, the algorithm incurs an additive approximation error proportional to the fraction of x which behaves maliciously.
The asymmetry of our pseudorandomness model has particular appeal for the case where x is a source string, meaning that ed(x, y) will be computed for many strings y. Suppose that one wishes to achieve an O(α)-approximation for each ed(x, y) computation, and that B is the smallest block-size for which the string x is (1/α, B)-pseudorandom. We show that without knowing B beforehand, x may be preprocessed in time [MATH HERE], so that all future computations of the form ed(x,y) may be O(α)-approximated in time O(nB). Furthermore, for the special case where only a single ed( x, y) computation will be performed, we show how to achieve an O(α)-approximation in time O(n4/3B2/3).