A New Algebraic Approach for String Reconstruction from Substring Compositions
A New Algebraic Approach for String Reconstruction from Substring Compositions
复制标题
DOI：
10.1109/isit50566.2022.9834531
复制
发表时间：
2022-01
期刊：
影响因子：
--
通讯作者：
Utkarsh Gupta;Hessam Mahdavifar
中科院分区：
文献类型：
--
作者：
Utkarsh Gupta;Hessam Mahdavifar
我们考虑了Acharya等人首先引入和研究了二元字符串重建的问题，即其子弦组合物的多键（即称为子弦组合物多动物）的问题。我们引入了一种新算法，该算法是从其子弦组成的多序中引入弦的重建问题，该算法依赖于该问题的等效双变量多项式公式的代数属性。然后，我们表征要重建二进制字符串的特定代数条件，以确保算法不需要通过重建进行任何回溯，因此，时间复杂性在多个角度上是界定的。更具体地说，与Acharya等人的算法相比，在没有回溯的情况下，我们的算法在实践中具有O（N2）的时间复杂性，该算法具有O（n2 logn）的时间复杂性，其中N是二进制字符串的长度。此外，已经表明，较大的二进制字符串是由新算法可以独特地重构的，而无需回溯导致较大的重建代码的代码簿，与Pattabiraman et ew al。，同时具有O（n2）实际重建复杂性。
We consider the problem of binary string reconstruction from the multiset of its substring compositions, i.e., referred to as the substring composition multiset, first introduced and studied by Acharya et al. We introduce a new algorithm for the problem of string reconstruction from its substring composition multiset which relies on the algebraic properties of the equivalent bivariate polynomial formulation of the problem. We then characterize specific algebraic conditions for the binary string to be reconstructed that guarantee the algorithm does not require any backtracking through the reconstruction, and, consequently, the time complexity is bounded polynomially. More specifically, in the case of no backtracking, our algorithm has a time complexity of O(n2) in practice, compared to the algorithm by Acharya et al., which has a time complexity of O(n2 logn), where n is the length of the binary string. Furthermore, it is shown that larger sets of binary strings are uniquely reconstructable by the new algorithm and without the need for backtracking leading to codebooks of reconstruction codes that are larger, by a linear factor in size, compared to the previously known construction by Pattabiraman et al., while having O(n2) practical reconstruction complexity.