Dec, 2014

编辑距离无法在强次二多项式时间内计算（除非 SETH 为假）

PDF
TL;DR本文提供了证据表明计算编辑距离的时间复杂度可能是近二次的。具体来说，我们展示了如果编辑距离可以在 O（n2−δ）的时间内计算，则可以在时间 M^{O (1)} 2^{(1−ε) N} 内解决带 N 个变量和 M 个子句的命题范式的满足性问题，这将违反强指数时间假设。
edit distancelevenshtein distancecomputational taskdynamic programmingstrong exponential time hypothesis
发现论文，激发创造
  • 字符串问题和动态时间规整的二次条件下界

    研究了字符串相似性度量的经典算法，探究了其在时间复杂度下限方面的限制，并引入了一个证明相似性度量二次时间难度的框架，进而证明了一个字符串问题在其困难时的时间复杂度下限。

    Feb, 2015

  • 学习字符串编辑距离

    本文提出了一种基于概率的字符串编辑距离模型，并通过应用于口语语音中单词发音的学习来证明其实用性

    Oct, 1996

  • 关于 k-Hamming 和 k-Edit 距离

    本文研究了加权 k-Hamming 和 k-Edit 距离级它们分别是经典 Hamming 和 Edit 距离的自然推广。研究的主要结果是，对于任何 k≥2，DECIS-k-Hamming 问题是 P-SPACE 完全的，DECIS-k-Edit 问题是 NEXPTIME 完全的。

    Jun, 2023

  • 使用量子设备算法计算图编辑距离

    本文介绍了 QUBO 形式的 Graph Edit Distance (GED) 问题，它允许我们在量子芯片上实现两种不同的方法，即量子退火和变分量子算法，为机器学习和模式识别提供一种新颖的解决方案。

    Nov, 2021

  • 概率多项式和汉明最近邻

    本文提出了一种利用概率多项式计算对数域上任意对称布尔函数并控制误差的低阶多项式方案，借此算法可在超对数维度中在真正的亚二次时间内求解汉明距离，并且能够对内积最大的向量，有最近的 ell1 对和杰卡德系数最大的向量对进行计算。

    Jul, 2015

  • 神经字符串编辑距离

    本文提出神经字符串编辑距离模型用于字符串对匹配与转录，并在同一框架中平衡精度与可解释性，通过对认知相似性，音译以及字音转换等任务进行评估达到了最先进匹配模型的表现。

    Apr, 2021

  • 如何比穷举更快地解决最接近字符串问题？

    本文研究了最接近字符串问题，讨论了此问题能够比朴素算法更快的算法，并在连续和离散 Closest String 问题以及其自然对偶问题 Remotest String 问题中给出了一些算法和复杂性结果。

    May, 2023

  • 近似最近邻搜索的难度

    采用代数几何编码，利用分布式 PCP 框架，证明了近二次运行时间下的条件下的近似双色最近点问题（包括 Euclidean，Manhattan，Hamming 或编辑距离），提出了新的硬度结果，其特别适用于多项式预处理时间的近似最近邻搜索问题。

    Mar, 2018

  • 时间序列匹配的时间扭曲编辑距离与硬度调整

    介绍了一种测量两个时间序列相似性的新方法 Time Warp Edit Distance (TWED)，该方法在动态规划算法中使用了图形编辑过程范例，并使用一种带有刚性参数的弹性量度来进行 “编辑操作”，可用于提高时间序列检索性能。

    Mar, 2007

  • 文本相似度矩阵的次线性时间近似

    本篇研究文章探讨通过推荐算法，计算相似矩阵的问题，介绍了基于 Nyström 方法的一种新的推荐算法，此算法可以以亚线性时间的复杂度对任何相似矩阵进行求解，在 NLP 的不同应用场景中展示出高精确度的表现。

    Dec, 2021