Linear-Time Computation of Similarity Measures for Sequential Data
Linear-Time Computation of Similarity Measures for Sequential Data
复制标题
DOI：
10.5555/1390681.1390683
复制
发表时间：
2008-06
期刊：
影响因子：
--
通讯作者：
Konrad Rieck;P. Laskov
中科院分区：
文献类型：
--
作者：
Konrad Rieck;P. Laskov
序列的高效和表达性比较是序列数据学习的基本过程。在这篇文章中，我们提出了一个通用的框架，用于计算序列的相似性度量，涵盖各种内核，距离和非度量相似性函数。比较的基础是使用形式语言嵌入序列，例如一组自然词，k-gram或所有连续的序列。作为框架的实现，我们提供了不同的复杂性和能力的线性时间算法，使用排序数组，尝试和后缀树作为底层数据结构。生物信息学，文本处理和计算机安全数据集上的实验说明了所提出的算法的效率-使峰值性能高达每秒106个成对比较。序列的距离和非度量相似性度量作为字符串内核的替代品的效用被证明在文本分类，网络入侵检测和DNA转录位点识别的应用中。
Efficient and expressive comparison of sequences is an essential procedure for learning with sequential data. In this article we propose a generic framework for computation of similarity measures for sequences, covering various kernel, distance and non-metric similarity functions. The basis for comparison is embedding of sequences using a formal language, such as a set of natural words, k-grams or all contiguous subsequences. As realizations of the framework we provide linear-time algorithms of different complexity and capabilities using sorted arrays, tries and suffix trees as underlying data structures. Experiments on data sets from bioinformatics, text processing and computer security illustrate the efficiency of the proposed algorithms---enabling peak performances of up to 106 pairwise comparisons per second. The utility of distances and non-metric similarity measures for sequences as alternatives to string kernels is demonstrated in applications of text categorization, network intrusion detection and transcription site recognition in DNA.