Multi-sorting algorithm for finding pairs of similar short substrings from large-scale string data
Multi-sorting algorithm for finding pairs of similar short substrings from large-scale string data
复制标题
DOI：
10.1007/s10115-009-0271-6
复制
发表时间：
2010-11-01
影响因子：
2.7
通讯作者：
Uno, Takeaki
中科院分区：
文献类型：
--
作者：
Uno, Takeaki
寻找相似的子串/子结构是分析巨大的字符串数据（例如基因组序列、网络文档、日志数据、图片、照片、视频等的特征向量）的核心任务。尽管由于子串的数量受其长度的平方限制，因此此类问题的多项式时间算法的存在是微不足道的，但由于计算时间的高阶次，简单的算法不适用于大型数据库。本文解决了从由固定长度的短字符串组成的庞大数据库中查找具有小汉明距离的字符串对的问题。长字符串的比较可以通过输入其所有固定长度的子串来解决，这样我们就可以找到相似的非短子串的候选者。我们关注算法的实际效率，并提出一种运行时间与输入/输出大小几乎呈线性关系的算法。我们证明，当短字符串的长度恒定时，其变体的计算时间与数据库大小呈线性关系，并且基因组序列和网络文本的计算实验显示了其实用效率。轻微修改适应编辑距离和失配容差计算。作者的主页上提供了一个实现。
Finding similar substrings/substructures is a central task in analyzing huge string data such as genome sequences, Web documents, log data, feature vectors of pictures, photos, videos, etc. Although the existence of polynomial time algorithms for such problems is trivial since the number of substrings is bounded by the square of their lengths, straightforward algorithms do not work for huge databases because of their high degree order of the computation time. This paper addresses the problem of finding pairs of strings with small Hamming distances from huge databases composed of short strings of a fixed length. Comparison of long strings can be solved by inputting all their substrings of fixed length so that we can find candidates of similar non-short substrings. We focus on the practical efficiency of algorithms, and propose an algorithm that runs in time almost linear in the input/output size. We prove that the computation time of its variant is linear in the database size when the length of the short strings is constant, and computational experiments for genome sequences and Web texts show its practical efficiency. Slight modifications adapt to the edit distance and mismatch tolerance computation. An implementation is available at the author's homepage.