如何比穷举更快地解决最接近字符串问题?
使用紧凑的二进制编码表示图像数据和特征描述符的研究表明,多个哈希表可用于在 Hamming 空间中进行精确的 k 近邻搜索,并且在 64、128 或 256 位的十亿级数据集上,其运行时间呈子线性表现,从而实现了极大的速度提升。
Jul, 2013
该论文提出了一种基于Astar搜索的算法,使用确定性自动机的后向最短距离作为启发式来找到非确定性有权自动机上的最短字符串,从而解决了在非幂等半环中单一最短路径算法未定义的问题。
Apr, 2022
本文提出了一种新的超启发式算法,使用一个创新的标准来将字符串集合分类,进而解决最长公共子序列问题。这种算法利用了$S^2D$和集合的一个内部属性来选择最佳匹配启发式算法,比其他算法具有更高的解决质量和运行时间。
Dec, 2022
本文主要针对线性存在规则和半盲chase问题,通过理论研究、算法实现及实验数据评估Chase算法的性能限制,以期理解影响加速Chase算法终止的参数,探索其在实际中的适用性,并揭示其性能限制。
Mar, 2023
string2string是一个开源库,提供了一系列高效的算法用于解决字符串问题,包括字符串对齐、距离测量、词汇和语义搜索以及相似性分析等,并且可以应用于自然语言处理、生物信息学和计算社会科学等多个领域。该库是用Python编写的,易于安装和使用。
Apr, 2023
在这篇文章中,我们使用具有访问分离预言机的内存受限算法提供了解决给定集合中的点的Oracle复杂性下界,其中集合包含单位d维球体并且含有已知半径ε的球体。我们证明了对于准确度ε≥e^(-d^(o(1)))的可行性问题,任何确定性算法要么使用d^(1+δ) bits的内存,要么至少需要进行1/(d^(0.01δ)ε^(2((1-δ)/(1+1.01δ))-o(1)))次预言机查询,其中δ∈[0,1]。此外,我们还证明了对于随机算法,要么使用d^(1+δ)的内存,要么至少需要进行1/(d^(2δ)ε^(2(1-4δ)-o(1)))次查询,其中δ∈[0,1/4]。由于梯度下降算法仅使用线性的内存O(dln(1/ε)),但进行Ω(1/ε^2)次查询,我们的结果表明它在Oracle复杂性/内存权衡中是帕累托最优的。此外,我们的结果表明,如果算法在d维中具有小于二次的内存,则确定性算法的Oracle复杂性总是多项式级别的1/ε。这揭示了一个明显的相变,因为对于二次的O(d^2ln(1/ε))内存,割平面方法仅需要O(dln(1/ε))的查询次数。
Apr, 2024
FAR FROM MOST STRING PROBLEM (FFMSP)的MEMETIC算法在计算生物学中的字符串选择问题上表现优异且与其他先进技术有统计显著性的性能比较。
May, 2024
最近字符串问题是一个NP难问题,目的是找到一个字符串,该字符串与给定字符串集合中的所有序列之间的距离最小。本文介绍了一个包括三个阶段的算法,并利用字母修剪方法、光束搜索和局部搜索来提高解的质量。实验结果表明,所提出的方法优于之前的方法。
Jul, 2024