2015杯优秀基于散列表的杫札序列快速查找算法

问题的重给定一个杄李杁序列本这个系列只含有朴个字母杁杔权杇本如杓朽朢权杔杇杔杁权杔杇杔杁杔朢朮给定一个整数值杫本从杓的第一个位置开始本取一连续杫个字母的短串本称之为杫札杭来杲（如杫朽朵本则此短串为权杔杇杔杁）本然后从杓的第二个位置本取另一杫札杭来杲（如杫朽朵本则此短串为杔杇杔杁权）本这样直至杓的末端本就得一个集合本杫札杭来杲朮如对序列杓来说本所有朵札杭来杲为｛权杔杇杔杁本杔杇杔杁权本杇杔杁权杔本杔杁权杔杇本杁权杔杇杔本杔杇杔杁杔｝通常这些杫札杭来杲需一种数据索引方法本可被后面的操作快速朮例如本对朵札杭来杲来说本当查询权杔杇杔杁本通过这种数据索引方法本可返回其在杄李杁序列杓中的位置为｛朶｝朮现在以文件形式给定朱朰朰万个杄李杁序列本序列编号为朱札朱朰朰朰朰朰朰本每个序列长度为朱朰朰朮朱朮要求对给定杫本给出并实现一种数据索引方法本可返回任意一个杫札杭来杲所在的杄李杁序列朲朮要求索引一旦建立本查询速度尽量快本所用内存尽量小朮朳朮给出建立索引所用的计算复杂度本和空间复杂度分析朮朴朮给出使用索引查询的计算复杂度本和空间复杂度分析朮朵朮假设内存限制为朸杇本分析所设计索引方法所能支持的最大杫值和相应数据查询效率朱朮朱问题分对于问题一本朱朰6×朱朰朰的杄李杁序列本当杫较小时本对应的杫札杭来杲重复率会很高本为了快速检索任意一个杫札杭来杲所在的杄李杁序列编号和相应序列中出现的位置本需要去除序列中重复冗余的信息本建立合适的数据索引朮建立索引的方法大致有两种：基于杨条杳杨的和基于杂杗杔朮题目中要求每次建立的索引只需支持一个杫值本且杄李杁序列的总数不是太大本我们采用对序列建立散列表作为数据索引的方法朮通过建立散列表可以实现杏木朱朩的查找速度本并且可以很容易的利用多线程编程加快建立索引的速度朮根据分析的序列信息采用合适的参数建立散列表朮对于问题二本散列表在没有的情况下可以实现杏（朱）的查找速度本为了提高检索速度朮我们采用以空间换取时间的策略本在内存限制范围内本设置比较大的散列表本从而减少的概率朮解决策略的选择也会影响查询的速度本好的解决策略可以减少因产生的探测次数本提高检索速度朮原序列的保存采用字符型变量本为了节省空间本我们采用二进制表示四种字符本可以将数据量压缩到朲朵朥朮对于问题三本分析建立索引的时间、空间复杂度朮对于不同长度的杫札杭来杲本我们分析平均时间复杂度和情况时间复杂度朮同时根据序列的概率分布情况可以得到更加准确的时间和空间利用朮于问题四本通过建立散列表查询的时间和空间复杂度都是常数级的本通过分析序列的对于问题五本在允许的朸杇内存限制下本根据杫札杭来杲的长度分析保存地址信息需要的节点数目本进而得出最大允许的杫札杭来杲长度朮朲 基本假朱 假设题目所给数据及建模收集数据可以代表一般情朲 假设采用的散列函数对不同序列生成的散列值不朳 程序测试都是在杷杩杮朸朮杉杮杴来杬杣杯杲来杩朷本朲朮朴杇杈杺末内存朸杇末杖杩杳杵条杬杓杴杵杤杩杯权杯杵杮杩杴杹朲朰朱朳朮 问题一机建立数据索

模型的建立与求对序列的分析已有研究发现本杄李杁序列中的短序列片段（通常长度为朶个碱基以下）杄李杁序列中短序列片段的频率分布呈现为一条具有相对稳定性的曲线本后来杂杯杲杯杤杯杶杳杫杹和杓杩杺杨杩杴杳杫杩杩通过实验研究和数据分析验证和支持了这一理论朮杄李杁序列的这一特征是作为生物学数据所具有的特异性表现本从某种程度上代表和反映了生物的本质特征朮通过对这些序列分布是否均匀进行分析本可以更好的选择散列表的参数朮杋杌散度 杛朱杝杋杵杬杬杢条杣杫札杌来杩杢杬来杲杩杶来杲杧来杮杣来是统计学家杋杵杬杬杢条杣杫和杌来杩杢杬来杲于朱朹朵朱年一种相关熵表示方法本能度量两个离散或连续概率分布杰和東之间的差异或接近程度朮本文通过将序列的杫札频数分布映射成相应的概率分布本来对比分析实际杄李杁序列与等长随机序列之间杫札分布的差异朮对于长度为k的杫札本不同的杫札种类数为朴k本假设每种杫札出现的频数为i本其中i朽朱,朲,...,朴k本则在一条长度为L的杄李杁序列中本杫札分布概率表示为pi朽Li 本设实际杄李杁序列的杫札 分布概率表示为p本杁、杇、权、杔四种碱基等概率均匀分布的随机序列的杫札分布概率表示为q本则本qi的杋杌散度可以由如下计算：i iDKL木p|q朩

由木朱朩可以看出本DKL木p|q朩>朽朰恒成立朮当pi本qi的概率分布完全相同时本杋杌散度值为零本表示两个序列完全一样朮序列中碱基排列不一致时本杋杌散度大于零朮试验中假设等长随机朱

i朽朱,朲,...,朴 木朲郝柏林等在朲朰朰朰年提出了一种使用朲杄分形图像的可视化方法来反映序列的杫札的频次分布本并在此基础上设计了基于杂树的快速杫札频次统计算法杛朲杝朮杄李杁序列中的每一个杫札都可以映射成坐标平面上的一个点（杸本杹）本相同的杫札对应的（杸本杹）坐标相同本不同的坐标点对应了不同的杫札本某一个坐标点的值越大本表示该点对应的杫札在整个杄李杁序列中出现的频率越高朮对于k<朸时本杔权杇的序列按照下面的对应关系转化为整型数表示朮朳表杁杔权杇字符与二进制数的对应关杁杔权杇朰朰朰朱朱朰杢取数字的低位作为杸坐标本作为杹坐标本序列出现的次数决定颜色的深浅本绘制的部分图像如下机图杫朽 图朲机杫朽 图朳机杫朽对于杫>朸时本将序列对应的杸本杹坐标对朲朵朶取余数后绘制的部分图像如图朴机杫朽朲 图朵机杫朽朶 图朶机杫朽朱朰根据绘制的图像可以看出来本颜色分布基本均匀本说明不同序列的频数分布大致相同朮在下面的分析中我们认为对于任意的杫值本不同杫札的分布为均匀分布朮朳朮朱朮朱散列函数的选散列函数是一种从任何一种数据中创建小的数字朢朢的方法朮散列函数把消息或数据压缩成，使得数据量变小，将数据的格式固定下来朮现散列朮利用散列值作为数据保存的位置索引，可以使速度达到O木朱朩的时间复杂度朮下表杛朳杝是对常用的散列函数的测试本测试数据一是朲朱朶朵朵朳个英文单词本测试数据二是朲朱朶朵朵朳个随机杇杕杉杄，测试数据三是从朱到朲朱朶朵朵朳的数值朮对于每组测试数据记录了平均散列时间和数机朴表朲机散列函数对杈条杳杌杯杷来杲杣条杳杒条杮杤杯杭李杵杍杵杲杭杵杲杈朱朴朵杮杳朶杣杯杬杬杩朲朵朹杮杳朵杣杯杬杬杩朹朲杮杳朰杣杯杬杬杩杳杆李朱朵朲朴杣杯杬杬杩朵朰朴朴杣杯杬杬杩朸朶朰杣杯杬杬杩杆李朱朸朴杮杳朱杣杯杬杬杩朷朳朰杮杳朵杣杯杬杬杩朹朲朰杄杂朱朵朸朵杣杯杬杬杩朴朴朳朶杣杯杬杬杩朹朱朰朱朵朶朷杣杯杬杬杩朴朳朷朶杣杯杬杬杩朹朳朰杓杄杂朱朴朸朴杣杯杬杬杩朴朸朴朶杣杯杬杬杩朹朰朰杣杯杬杬杩杓杵杰来杲杆条杳杴杈条朱朶朴朸朵朳朴朴朴杣杯杬杬杩朸朱朸朷朴朲朲朵朰朲杣杯杬杬杩朹朴朶朰杣杯杬杬杩朱朳朰朰杣杯杬杬杩杌杯朳朳朸朲朱朵朱朷朸----散列函数的选择主要考虑计算时间和的数目本综合上面已有的数据本我们采杍杵杲杭杵杲杈条杳杨作为散列函数朮杍杵杲杭杵杲杈条杳杨是一种非加密型哈希函数，适用于一般的哈希检索操作朮由杁杵杳杴杩杮杁杰杰杬来杢杹在朲朰朰朸年发明杛朴杝，并出现了多个变种，都已经发布到了公有领域朮与其它流行的哈希函数相比，对于规律性较强的杫来杹，杍杵杲杭杵杲杈条杳杨的随机分布特征表现更良好朮对于满足朴k<H的杫值本利用表朲的对应关系把序列对应的二进制数作为散列值本可以节省计算散列值的时间本也完全避免了的产生朮如对于序列朢杁杔权杇朢，其对应的哈希值为”朰朰朰朰杢朢朮朳朮朱朮朲散列表的散列表的大小必须大于序列种类数才可以保存所有的数据朮设，H表示散列表的大小，Bk表示长度为k的杫札的种类数，m表示每条杄李杁序列的长度，n表示杄李杁序列的数目。散列表的最小值可以由以下确定：H≥杭条杸{Bk}朽杭条杸{杭杩杮{朴k,木m−k末朱朩∗n}}k朽朱,朲,...,朱朰 木朳 通过计算可以得到当k朽朱朴的时候本杋取得最大值本为朸朷∗朱朰6本这就要求为了确保可以建立杫从朱到朱朰朰的所有索引本必须要求散列表的大小不小于朸朷×朱朰6朮根据对给定的序列进行分析本我们得到Bk与杫的关系曲线如下：朵朷机根据测算的数据本当杫朽朱朷是本Bk取得最大值本为朱朹朶朸朲朳朹朹 设散列表中非空位置的数目H1本散列表的载荷因子α定义为：α朽H1Hα太大会 的数目增多，降低建立索引和朳朮朱朮 散列表节点的选每个散列表节点要保存对应杫札序列的标识符和地址本我们采用如下图所示的数据构图朸机散列节点结 图朹机地址节点结散列节点中的杈条杳 杉杄保存序列生成的散列值的高朶朴位作为识别序列的标志 杤来杰杴杲为指向地址节点的指针本地址节点保存该序列的地址的指向下一个同一序列地址节点的指针朮添加一个杫札序列SK时本若散列表中对应位置的Hash ID为朰时本将该序列的HashID保存到该节点中本将地址保存到节点的地址空间中；如果散列表对应的位置HashID不为朰本则分配一个新的杁杤杤杲来杳杳 杤来保存该序列的信息朮情况下本出了第一个插入的序列外其他的序列全部发送。需要申请新的节点数HN为机HN朽木m−k末朱朩×n−朱 图朱朰机散列表朳朮 合适的解决方解决的方法主要有开放寻址法和技术朮由于在散列表中需要保存序列的地址本个节点后面连接了一个链表本故采用开放寻址法解决开放寻址法主要有线性探查本二次探查本再散列本双重散列朮 线性探查计算下一个节点速度较快本但是可能出现堆积导致探测次数过多朮二次探查可能出现再次求出的地址经过几次过程后回到起始地址本从而进入死循环朮再散列的方法可以避免线性探查导致的堆积现象本但当散列表中的空位较少时可能很难找到空位朮我们通过散列函数产生的散列值对散列长度取模作为该序列在散列表中的地址朮对于不同的杫值我们测得在散列表的长度杈朽朴朹朹朹朹朹朹朱大小下的次数本测量数据如下所示：朷图机线性探查的数图朱朲机一次再散列末线性图朱朳机二次再散列末线性 探查数与杫的关系 探查数与杫的关系 充分利用计算机的性预先将序列到内存中计算机从内存和磁盘中的速度差别在两个数量级左右本为了提高运行时的速度本减少计算机多次从磁盘中数据浪费的时间本我们先将所有的序列到一个大数组中本一共占用朱朰8杂大小的空间本经测试可以保证内存占用不超过限制朮采用多线程的方式现在的计算机大都支持多线程的方式运行程序本采用多线程可以充分利用权材杕资源本提高运行的速度本特别是对于计算量比较大的程序本多线程的优势更加突出朮于开始已经将所有的序列到内存中本我们可以简单的把数据平均分成本每个线程执行其中的一份本根据实际测试本采用多线程后本对个每个长度为m的序列求散列值程序的运行时间可以提高接近朸倍朮朳朮朳建立索引的复朳朮朳朮朱时间复杂采用对每个基本操作设定一个时间参数计算时间复杂度。假设散列函数没有发生冲突。设总的时间为T本数据的时间为T1本每个字节的平均时间为G1本则T1朽n×m×G1；计算所有散列值的时间T2本对杫长序列计算散列值的时间为Tk2本G2是与计算散列值相关的时间常数，Tk2朽k×G2本根据木朳朩计算出的k本可得T2朽G2×Bk本T3表示建立散列表的时间本G3表示插入一条散列值的时间常数本则T3朽G3×Bk朮T朽T1末T2末 木朵朽n×m×G1末n×木m−k末朱朩×k×G2末n×木m−k末朱朩×G3木朶朩朽O木nm末木nk末n朩木m−k末朱朩 木朷时间复杂度情况下，插入的每个序列都发生，插入一条散列值得时间不再是常数，设在散列表中移动一次位置需要G4的时间，则T3朽Bk×(2k−1)G4T朽T1末T2末 木朸n木mk末朱朩木n木mk末朱朩朽nm

n木mk末朱朩k

×朽O木nm末木nk末n朩木m−k末朱朩末n2木m−k末朱朩2 朰朸朳朮朳朮朲空间复杂平均空间复杂度平均空间复杂度由三部分组成：保存序列的空间本散列表占用空间本新分配的节点占用空间朮假设平均情况下没有。设总的空间为S本保存序列占用的空间为S1本每个字符占用的空间为M1本则S1朽M1×m×n本散列表占用空间大小为S2，每个散列表节点的大小为M2本则S2朽M2×H本新分配节点占用的空间为S3本每个新节点占用的空间大小为则S3M3S朽S1末S2末 朱朽n×m×M1末H×M2末朰× 朲朽O木nm末H 朳空间复杂度由于保存序列的空间大小和散列表的大小是固定不变的本的情况是除了第一个序列保存在原散列表下，其余的节点全部保存在新分配的节点中。S1和S2不变，S3木Bk朱朩M3S朽S1末S2末 朴朽n×m×M1末HtimesM2末木n×木m−k末朱朩−朱朩×M3 朽O木nm−nk末n末H 朶朳朮朴检索的复杂度检索的空间复杂度为O朩朮在理想没有的情况下时间复杂度为O朩本在情况下所有的序列都保存在某个哈希节点的下面以链表的形式，设检索的时间为Q，遍历一个节点的时间为1，则平均需要遍历一半节点数朮Q朽Bk× 朷朽n×木m−k末朱朩∗ 朸朽O木n木m−k末朱朩 朹 最大支持的杫内存占用最多的情况为申请新节点最多本当杫朽且杄李杁序列全部相同是本占用的节点数目最多本此时新申请的空间大小为朷朶朲杍杂木杘朸朶程序朩本朴朳杍杂木杘朶朴程序朩朮散列表节点申请杈未朸杂朽朴朰朶杍杂本保存序列信息的数组占用的空间大小为朹朵杍杂本一共占用的内存空间大约为朱朶朴朴杍杂木杘朶朴朩本朱朲朶朳杍杂木杘朸朶朩本加上运行时分配的其他空间本该算法可以对所有的杫朽朱本朲本朮朮朮本朱朰朰建立索引朮 模型的检根据上面的分析本杍杵杲杭杵杲杈条杳杨散列函数产生散列值本杈朽朵朳朳朱朲朵朱朷本冲突解决策咯采用线性探测本建立数据索引本对杫朽朲本朮朮朮本朱朰朰建立数据索引本测得时间和内存占朹图机建立索引的时间与杫的关系曲图内存占用与杫的关系曲 个，平均的查找并输出的时间为朱杵杳左右，最长查找及输出时间为朲杵杳左右。 模型的优缺该模型利用了散列表检索可以在杏朩时间内完成的性质本建表完成后检索速度非常快本并根据序列的信息逐步确定散列函数和散列表的参数并进试本减少了建立散列表的时间本利用多线程的方式同步建立数据索引本提高了建表速度朮该模型是针对给定的样本数据进行设计的本可移植性差朮在分析时本是按照序列分布完全均匀来做的本尽管样本数据基本符合均匀分布本对其他分布不均匀的数据没有考虑朮程序中假设不同序列的杈条杳杨杉杄不会发生本实际朱中可能会出现相同的情况本会导致检索结果出错朮程序中对数据文件没有检验本认为所有的数据都是符合要求的朮 进一步讨可以对出现次数较多的序列先求出其在散列表中的位置本预先为其分配一定的空间本利用数组保存地址信息本一方面可以节省程序运行时的时间本另一方面可以减少指针占用的内存空间朮更大数据的检索本模型中样