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

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越大查询的速度就会越快。

windoze

回复 7# xlwang_0903

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

windoze

回复 12# yulihua49

你不嫌慢么？