8

我有一个长文本（大约 5 MB 文件大小）和另一个称为模式的文本（大约 2000 个字符）。

任务是从长文本中 15 个字符或更长的基因组模式中找到匹配的部分。

例子：

长文本： ACGTACGTGTCA AAAACCCCGGGGTTTTA GTACCCGTAGGCGTAT 并且 更长

模式： ACGGTATTGAC AAAACCCCGGGGTTTA TGTTCCCAG

我正在寻找一种高效（且易于理解和实现）的算法。

如果可能的话，奖金将是一种在 C++ 中仅使用字符数组来实现这一点的方法。

4

6 回答 6

7

这是一种算法——我不确定它是否有名字。它需要一个“滚动散列” - 一个（非加密）散列函数，它具有给定序列散列的属性，AB...C计算序列的散列是有效的B...CD。

  1. 计算序列pattern[0..14], pattern[1..15], pattern[2..16]... 的滚动哈希，并将每个索引存储pattern在哈希表中。

  2. 计算滚动哈希，haystack[0..14]看看它是否在哈希表中。如果是，则与从哈希表中检索haystack[0..14]到的pattern[pos..pos+14]位置进行比较。pos

  3. 从 的滚动哈希中haystack[0..14]，高效计算 的滚动哈希，haystack[1..15]看是否在哈希表中。重复直到到达终点haystack。

请注意，您的 15 个字符串只有 2 30 个可能的值，因此您的“哈希函数”可能是一个简单的映射到字符串的值，该字符串被视为 15 位 base-4 数字，计算速度很快，具有滚动哈希属性并且是独一无二的。

于 2012-05-08T04:34:55.670 回答
4

一种方法是获取Aho-Corasick的实现并使用它来创建可以识别模式中任何 15 个字符块的内容，然后使用它来搜索文本。使用 Aho-Corasick 构建匹配器的成本和搜索成本都是线性的，所以这应该是实用的。

于 2012-05-08T04:12:53.193 回答
2

退后一步，我要现场编码：

void match_substring(const char *a, const char *b, int n) // n=15 in your case
{
    int alen = strlen(a); // I'll leave all the null-checking and buffer-overrun business as an exercise to the reader
    int blen = strlen(b);
    for (int i=0; i<alen; i++) {
        for (int j=0; j<blen; j++) {
            for (int k; (i+k<alen) && (j+k<blen) && a[i+k]==b[i+k]; k++);
            if (k >= n)
                printf("match from (%d:%d) for %d bytes\n", i, j, k);
        }
    }
}
于 2012-05-08T01:17:04.150 回答
1

如果您使用的是 C 库的良好实现（或者甚至是像 glibc 这样的平庸的库，恰好具有该函数的良好实现），strstr那么会做得很好。我听说有一种新算法对 DNA（小字母）特别有用，但我现在找不到参考。除此之外，2way（glibc 使用）是最佳的。

于 2012-05-08T01:15:39.903 回答
1

我强烈建议你去你的图书馆看看 Robert Sedgwick 和 Kevin Wayne 的“Algorithms 4th Edition”。他们有一整章专门讨论子字符串搜索。此外，可能值得查看书籍网站algs4.cs.princeton.edu。

TL;DR——如果你下定决心，你可以在保证时间与输入长度成线性关系时使用 char 数组进行子字符串搜索。书中和网上都有代码示例。没有比这更容易的了。

于 2012-05-08T04:44:35.780 回答
-1

我认为“后缀树”可以通过 O(log n) 的性能更好地解决它

于 2012-05-11T05:16:03.307 回答