如何用C实现这样一个索引算法？

xlwang_0903

最近开始学习C语言，有一个问题需要解决，还请大家帮忙出出主意。我先把需要解决的问题描述一下：
        读取文本文件，小到几十K，大到十几G，内容为基因序列字符串，包括基因的id、描述及其对应的序列（也就是由AGCT四种字符组成的文本内容）。现在想对这个文件做索引以便搜索。如果待查询的字符串长度为K，那么我需要得到    这个文件中所有的长度为K的子串的位置以及子串所属的基因（包括基因id等信息），然后写入mysql。

不知道有没有比较好的算法能做这个事情，或者请大家帮我提提思路，我会随时关注大家的回复，谢谢！

呃……我补充一下，好像我没有说明白。实际我是要在一个文件中查询某个字符串是否存在并得到这个字符串的位置信息。字符串的长度相对固定。

hellioncu

你还是举个例子来说明比较好

xlwang_0903

hellioncu 发表于 2013-04-25 09:37
你还是举个例子来说明比较好

比如文件的内容如下：
>0
AGCAGGGGGGCTTATTATTACCCCCCCTGCTCGGGGCGGGACATTCTGTG
ATGGGCTGGGCTTTATGCGGCCAAATAAGCCCATAAAGCCAGATCTGGGC
CCATTTAAGGGCCCGTGGTTTGAAAATGTCGCGTTCCCGCCTAA
……
>1
……
>2
我要查询所有长度为k的子串的位置，例如查询AAGCCCA（k=7），把这个子串的所有位置信息找出来，并且要知道这个子串是在>0对应的序列上，还是在>1对应的序列上。

pandaiam

看了例子才发现和我想的完全不一样..
读取每个基因,然后看输入的字串是否在这个基因的序列里,是的话就插入数据库了..
是否在基因序列里可以用kmp.

xlwang_0903

pandaiam 发表于 2013-04-25 10:03
看了例子才发现和我想的完全不一样..
读取每个基因,然后看输入的字串是否在这个基因的序列里,是的话就插入 ...

我的想法是先对文件做个索引保存到数据库，待查询的序列是到数据库中去查。我是想知道建索引的过程有没有比较好的方法。另外你说的kmp是什么意思？

windoze

MySQL中按子串查找(LIKE '%xxx%')的速度会很慢，一个简单的思路是把每个序列中的每个碱基单独建立倒排链并保存位置，这样在查询时只需要按照单个碱基做phrase query。这么做的缺点是，因为碱基只有4个，每个倒排链都会很长，查询效率只能说比LIKE略高。
一个优化一点的方案是N Gram，也就是把碱基序列切分成长度为N的片段，例如“GCTTAT”的2Gram切分就是GC,CT,TT,TA,AT，3Gram就是GCT,CTT,TTA,TAT，每个切片的位置前进一位，你可以对序列做一个1～N的切片，也就是按照单个碱基切分一遍，按照2Gram切分一遍，按照3Gram切分一遍…………然后针对所有这些切片建立倒排链。
查询时，如果要查询的序列长度大于预先建立好的索引中最大的N，则需要将查询序列按照最大的N做一个NGram切分，将所有的切分片段做一个AND query，在这个结果集中再做单个碱基的phrase query，或者直接查找子串，因为你的查询序列是已知的，所以可以用KMP预先建立跳转表，速度会比较快。
这个过程的作用是确保没有false positive，因为NGram AND query并不能确保得到的结果集一定准确。
这样做的缺点是N越大，索引就会越大，但是N越大查询的速度就会越快。

xlwang_0903

windoze 发表于 2013-04-25 10:19
MySQL中按子串查找(LIKE '%xxx%')的速度会很慢，一个简单的思路是把每个序列中的每个碱基单独建立倒排链并保 ...

我现在的想法有点类似与您说的N Gram。因为待查询的字符串长度K相对固定，所以我想做索引时取的N就等于K。我把所有长度为K的子串的位置直接保存到数据库。

windoze

回复 7# xlwang_0903

如果K基本固定，那你就可以直接针对这些长度做NGram切分然后建立索引。
但有一个问题要注意，索引并不适合存到MySQL里，因为索引本身是一个keyword->document_id_list的映射表，MySQL并不能充分优化这种特定的场景。
建议你找一个专门的search engine干这事，比如Lucene、Xapian，或者…………给自己做个广告…………Argos…………

linux_c_py_php

建一个后缀树就可以了, 10+G的文件建完也用不了1,2个G, 内存里只存后缀数以及文件偏移索引.

cobras

这种算法应该很简单，就是顺序从txt文件中读取每个记录，然后比对。符合要求就写入MySQL中。
只是需要一个比较大的缓冲区，足以容下最大的记录。