ffgrep：可扩展的近似字符串匹配-研究论文

【文件属性】：
文件名称：ffgrep：可扩展的近似字符串匹配-研究论文
文件大小：465KB
文件格式：PDF
更新时间：2021-06-10 14:17:25
论文研究 近似子串搜索是生物信息学和文本分析中一项常见但计算量大的任务。 我们提出了一种将字符串搜索重铸为多重卷积问题的新方法，然后利用高效的快速傅立叶卷积技术。 这种我们称为 ffgrep 的方法计算并缓存目标语料库的频谱，大大降低了后续搜索的成本。 与其他方法一样，该算法具有令人尴尬的可并行性； 与其他方法不同，它不仅能够对原始字符串进行操作，还能够对词嵌入进行操作。 ffgrep 应用于 2012 年美国总统大选竞选演讲的不完美自动转录的原始语料库。 我们将我们的方法与 agrep 进行对比，agrep 是一种行业标准元算法，可从许多高度优化的近似字符串匹配算法中选择最佳成员。 搜索手动策划的候选标语集的近似重复，我们表明 ffgrep 在典型设置中将计算速度提高了 60 倍，随着对齐变得更长或更复杂，增益会增加。 此外，这些计算收益的性能成本很低。 将 agrep 搜索结果作为基本事实，在广泛的 agrep 参数上，我们表明 ffgrep 能够以超过 0.94 的准确度和 0.84-0.9 的 F1 恢复高度相似的结果。 最后，我们展示了有效的子串匹配如何通过在没有人工监督的情况下识别候选标语来实现新的实质性研究。 通过快速计算和组织 900 亿个成对字符串比较，我们提出的方法会自动学习短语“将孩子踢出领先地位或取消穷人的健康保险”和“踢学生是 [原文如此] 经济援助或摆脱资助计划生育或取消数百万人的医疗补助”——连同其他 32 项竞选呼吁——都映射到一个反复出现的主题，即巴拉克奥巴马总统对拟议的医疗保险改革的批评。