Better Filtering with Gapped q-Grams
Better Filtering with Gapped q-Grams
复制标题
使用有间隙的 q-Gram 进行更好的过滤
DOI：
10.1007/3-540-48194-x_6
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Juha Kärkkäinen
中科院分区：
文献类型：
--
作者：
S. Burkhardt;Juha Kärkkäinen
用于近似字符串匹配的一类流行且经过充分研究的过滤器会比较模式和文本中长度为 q 的子字符串（q-gram），以识别包含潜在匹配项的文本区域。使用间隙 q-gram 代替连续子串的方法的推广在文献中多次提到，但从未进行过任何深入的分析。在本文中，我们报告了空位 q-grams 研究的第一个结果。我们表明，有间隙的 q-gram 可以比连续的 q-gram 提供更快和/或更有效的过滤。为了实现这些结果，必须优化 q-gram 中间隙的排列和称为阈值的滤波器参数。这两个任务都是重要的组合优化问题，我们为此提供了有效的解决方案。我们专注于 k 个不匹配问题，即用汉明距离进行近似字符串匹配。
A popular and well-studied class of filters for approximate string matching compares substrings of length q, the q-grams, in the pattern and the text to identify text areas that contain potential matches. A generalization of the method that uses gapped q-grams instead of contiguous substrings is mentioned a few times in literature but has never been analyzed in any depth. In this paper, we report the first results of a study on gapped q-grams. We show that gapped q-grams can provide orders of magnitude faster and/or more efficient filtering than contiguous q-grams. To achieve these results the arrangement of the gaps in the q-gram and a filter parameter called threshold have to be optimized. Both of these tasks are nontrivial combinatorial optimization problems for which we present efficient solutions. We concentrate on the k mismatches problem, i.e, approximate string matching with the Hamming distance.