String Sanitization Under Edit Distance: Improved and Generalized-猫眼课题宝

DOI：

10.4230/lipics.cpm.2021.19

发表时间：

2020-07

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Takuya Mieno;S. Pissis;L. Stougie;Michelle Sweering

设$W$是字母表$\Sigma$上长度为$n$的字符串，$k$是正整数，$\mathcal{S}$是$W$的一组长度为$k$的子串。 ETFS 问题要求我们构造一个字符串 $X_{\mathrm{ED}}$，使得： (i) $X_{\mathrm{ED}}$ 中不出现 $\mathcal{S}$ 字符串； (ii) $\Sigma$ 上所有其他长度为 $k$ 的子串的顺序在 $W$ 和 $X_{\mathrm{ED}}$ 中是相同的； (iii) $X_{\mathrm{ED}}$ 到 $W$ 的编辑距离最小。当 $W$ 代表个人数据且 $\mathcal{S}$ 代表一组机密模式时，ETFS 问题要求对 $W$ 进行转换以保护其隐私及其实用性 [Bernardini et al., ECML PKDD 2019]。 ETFS 可以在 $\mathcal{O}(n^2k)$ 时间内解决[Bernardini et al., CPM 2020]。同一篇论文表明，对于任何 $\delta>0$，ETFS 无法在 $\mathcal{O}(n^{2-\delta})$ 时间内求解，除非强指数时间假设 (SETH) 为假。我们的主要结果可以概括如下：(i) 一种求解 ETFS 的 $\mathcal{O}(n^2\log^2k)$-time 算法； (ii) 求解 AETFS 的 $\mathcal{O}(n^2\log^2n)$ 时间算法，AETFS 是 ETFS 的推广，其中 $\mathcal{S}$ 的元素可以具有任意长度。因此，除非 SETH 失败，否则我们的算法在多对数因子下都是最优的。我们还强调，我们的算法可以在任意权重的编辑距离下工作，无需额外成本。作为奖励，我们展示了如何修改一些已知的技术，从而加快标准编辑距离计算的速度，以应用于我们的问题。除了字符串清理之外，我们的技术还可以启发解决与正则表达式或上下文无关语法相关的其他问题。

Let $W$ be a string of length $n$ over an alphabet $\Sigma$, $k$ be a positive integer, and $\mathcal{S}$ be a set of length-$k$ substrings of $W$. The ETFS problem asks us to construct a string $X_{\mathrm{ED}}$ such that: (i) no string of $\mathcal{S}$ occurs in $X_{\mathrm{ED}}$; (ii) the order of all other length-$k$ substrings over $\Sigma$ is the same in $W$ and in $X_{\mathrm{ED}}$; and (iii) $X_{\mathrm{ED}}$ has minimal edit distance to $W$. When $W$ represents an individual's data and $\mathcal{S}$ represents a set of confidential patterns, the ETFS problem asks for transforming $W$ to preserve its privacy and its utility [Bernardini et al., ECML PKDD 2019]. ETFS can be solved in $\mathcal{O}(n^2k)$ time [Bernardini et al., CPM 2020]. The same paper shows that ETFS cannot be solved in $\mathcal{O}(n^{2-\delta})$ time, for any $\delta>0$, unless the Strong Exponential Time Hypothesis (SETH) is false. Our main results can be summarized as follows: (i) an $\mathcal{O}(n^2\log^2k)$-time algorithm to solve ETFS; and (ii) an $\mathcal{O}(n^2\log^2n)$-time algorithm to solve AETFS, a generalization of ETFS in which the elements of $\mathcal{S}$ can have arbitrary lengths. Our algorithms are thus optimal up to polylogarithmic factors, unless SETH fails. Let us also stress that our algorithms work under edit distance with arbitrary weights at no extra cost. As a bonus, we show how to modify some known techniques, which speed up the standard edit distance computation, to be applied to our problems. Beyond string sanitization, our techniques may inspire solutions to other problems related to regular expressions or context-free grammars.

String Sanitization Under Edit Distance: Improved and Generalized

文献摘要

相似文献