如何用C實現(xiàn)這樣一個索引算法？

xlwang_0903

最近開始學(xué)習(xí)C語言，有一個問題需要解決，還請大家?guī)兔Τ龀鲋饕�。我先把需要解決的問題描述一下：
        讀取文本文件，小到幾十K，大到十幾G，內(nèi)容為基因序列字符串，包括基因的id、描述及其對應(yīng)的序列（也就是由AGCT四種字符組成的文本內(nèi)容）�，F(xiàn)在想對這個文件做索引以便搜索。如果待查詢的字符串長度為K，那么我需要得到    這個文件中所有的長度為K的子串的位置以及子串所屬的基因（包括基因id等信息），然后寫入mysql。

不知道有沒有比較好的算法能做這個事情，或者請大家?guī)臀姨崽崴悸罚�我會隨時關(guān)注大家的回復(fù)，謝謝！

呃……我補(bǔ)充一下，好像我沒有說明白。實際我是要在一個文件中查詢某個字符串是否存在并得到這個字符串的位置信息。字符串的長度相對固定。

hellioncu

你還是舉個例子來說明比較好

xlwang_0903

hellioncu 發(fā)表于 2013-04-25 09:37
你還是舉個例子來說明比較好

比如文件的內(nèi)容如下：
>0
AGCAGGGGGGCTTATTATTACCCCCCCTGCTCGGGGCGGGACATTCTGTG
ATGGGCTGGGCTTTATGCGGCCAAATAAGCCCATAAAGCCAGATCTGGGC
CCATTTAAGGGCCCGTGGTTTGAAAATGTCGCGTTCCCGCCTAA
……
>1
……
>2
我要查詢所有長度為k的子串的位置，例如查詢AAGCCCA（k=7），把這個子串的所有位置信息找出來，并且要知道這個子串是在>0對應(yīng)的序列上，還是在>1對應(yīng)的序列上。

pandaiam

看了例子才發(fā)現(xiàn)和我想的完全不一樣..
讀取每個基因,然后看輸入的字串是否在這個基因的序列里,是的話就插入數(shù)據(jù)庫了..
是否在基因序列里可以用kmp.

xlwang_0903

pandaiam 發(fā)表于 2013-04-25 10:03
看了例子才發(fā)現(xiàn)和我想的完全不一樣..
讀取每個基因,然后看輸入的字串是否在這個基因的序列里,是的話就插入 ...

我的想法是先對文件做個索引保存到數(shù)據(jù)庫，待查詢的序列是到數(shù)據(jù)庫中去查。我是想知道建索引的過程有沒有比較好的方法。另外你說的kmp是什么意思？

windoze

MySQL中按子串查找(LIKE '%xxx%')的速度會很慢，一個簡單的思路是把每個序列中的每個堿基單獨建立倒排鏈并保存位置，這樣在查詢時只需要按照單個堿基做phrase query。這么做的缺點是，因為堿基只有4個，每個倒排鏈都會很長，查詢效率只能說比LIKE略高。
一個優(yōu)化一點的方案是N Gram，也就是把堿基序列切分成長度為N的片段，例如“GCTTAT”的2Gram切分就是GC,CT,TT,TA,AT，3Gram就是GCT,CTT,TTA,TAT，每個切片的位置前進(jìn)一位，你可以對序列做一個1～N的切片，也就是按照單個堿基切分一遍，按照2Gram切分一遍，按照3Gram切分一遍…………然后針對所有這些切片建立倒排鏈。
查詢時，如果要查詢的序列長度大于預(yù)先建立好的索引中最大的N，則需要將查詢序列按照最大的N做一個NGram切分，將所有的切分片段做一個AND query，在這個結(jié)果集中再做單個堿基的phrase query，或者直接查找子串，因為你的查詢序列是已知的，所以可以用KMP預(yù)先建立跳轉(zhuǎn)表，速度會比較快。
這個過程的作用是確保沒有false positive，因為NGram AND query并不能確保得到的結(jié)果集一定準(zhǔn)確。
這樣做的缺點是N越大，索引就會越大，但是N越大查詢的速度就會越快。

xlwang_0903

windoze 發(fā)表于 2013-04-25 10:19
MySQL中按子串查找(LIKE '%xxx%')的速度會很慢，一個簡單的思路是把每個序列中的每個堿基單獨建立倒排鏈并保 ...

我現(xiàn)在的想法有點類似與您說的N Gram。因為待查詢的字符串長度K相對固定，所以我想做索引時取的N就等于K。我把所有長度為K的子串的位置直接保存到數(shù)據(jù)庫。

windoze

回復(fù) 7# xlwang_0903

如果K基本固定，那你就可以直接針對這些長度做NGram切分然后建立索引。
但有一個問題要注意，索引并不適合存到MySQL里，因為索引本身是一個keyword->document_id_list的映射表，MySQL并不能充分優(yōu)化這種特定的場景。
建議你找一個專門的search engine干這事，比如Lucene、Xapian，或者…………給自己做個廣告…………Argos…………

linux_c_py_php

建一個后綴樹就可以了, 10+G的文件建完也用不了1,2個G, 內(nèi)存里只存后綴數(shù)以及文件偏移索引.

cobras

這種算法應(yīng)該很簡單，就是順序從txt文件中讀取每個記錄，然后比對。符合要求就寫入MySQL中。
只是需要一個比較大的緩沖區(qū)，足以容下最大的記錄。