资源描述：
《东三省论文封面》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、封一答卷编号（参赛学校填写）:答卷编号（竞赛组委会填写）:论文题目：医保欺诈行为的主动发现（A）组另IJ：本科生参赛队员信息（必填）:姓名学号联系电话参赛队员1参赛队员2参赛队员3参赛学校：东北农业大学封二答卷编号（参赛学校填写）:答卷编号（竞赛组委会填写）:评阅情况（学校评阅专家填写）：学校评阅1.学校评阅2.学校评阅3.评阅情况（联赛评阅专家填写）:联赛评阅1.联赛评阅2.联赛评阅3.题目摘要本文先提炼出了题目对索引的主要要求是查询时间和内存消耗，因此我们利用哈希表建立了链地址哈希表模型以提供高效的查询速度，同时利用满四叉树模型来实现哈
2、希函数来完全避免哈希冲突，使用vs2012编译了源代码，并进行了准确度和稳定性分析和评估了该索引方法的性能。对于问题1,我们利用链地址哈希表从数据中提取出长度为k的DNA序列的所有可能值，用哈希函数将DNA序列转化为特征码值，并将其在文件的位置存储在哈希表中特征码值对应的链表中，如果出现特征码值重复则利用拉链法将处理冲突。对于问题2,我们首先利用满四叉树模型为原型优化了哈希函数，将k长度的DNA序列所有可能组合用满四叉树分别列出，然后利用求和公式求出DNA序列的特征码值，使得每一个特征码值只对应一个DNA序列，避免了哈希冲突，提高最后输出结
3、果的准确性，同时降低了内存消耗。对于问题3,我们将实现索引的源码以所属的函数的不同分为create（）,n_keyO,input（）,剩余语句以上四个部分，分别计算四个部分的计算（时间）复杂度为0（举）、0（疋）、0（6£）、0（1）,空间复杂度为0（1）、0（1）、0（k）、0（举），最后利用求和法则得到索引的空间复杂度0（举）与时间复杂度0（4“）。对于问题4,由于查询索引的源码只有一个函数，所以我们只计算出该函数的空间复杂度0（1）和计算（时间）复杂度0（1）即可。对于问题5,我们对源码进行了细致的分析，将源码中哈希表提取出来，在以下
4、限制条件下：分配内存时不会产生内存碎片，不会发生内存泄露的情况下模糊计算了内存消耗，得到内存关于k的函数，最后对函数结果的正确性给予了分析，得到最大k值14,最后使用时间复杂度0（1）来表示当k取最大时的查询效率。对于问题6,我们分别以建立索引和查询索引的时间复杂度和空间复杂度为依据对四个方面进行了分析，最后综合起来，得到该模型在查询时和小内存限制下的高效性和准确性。最后，我们利用vs2012编译了程序，并减少输入的数据，用人工和程序两方面分别计算结果，利用表格得出结论，再输入大数据量以检验程序的稳定性，最后验证了该模型的正确性，科学性和稳
5、定性，并将模型向学校的学生成绩查询系统进行了推广。关键词：哈希表链表满四叉树模糊计算复杂度一•问题重述1.1模型假设1•假设以文件形式给定的100万个每个基因序列长度为100的DNA序列数据准确无误。2.假设读取文件、建立索引和检索DNA序列过程中碱基的属性不受影响。3.假设计算机硬件环境对结果输出没有影响。4.组成DNA序列的碱基有且只有A.G.C.T四种。5,假设运行时程序在分配内存中不会产生内存碎片。1,2符号说明k要查询的DNA序列长度key特征码值，是每一种DNA序列用哈希函数转化为的int值哈作表g(x)自变量为链表里元素的个数
6、，因变量是链表有兀个元素的概率的函数p将任何一个元素投到m个链表中的任意一个的概率L平均查找长度£(加*g(x)*F)/〃x=0x从0到n,的和再除以n,表示总的查找次数除以总的元素得到平均查找长度帥才）兀+1为四叉树的深度，y根据当前深度时所对应的碱基而变化，为A时取0,为G时取1,为C时取2,为T时取3,表示x从1到k,yx4k~x的和时间复杂度%)语句频度s@)空间复杂度冋题一和二:1.3模型的建立与求解根据问题1和2的要求，要求给出一种索引方法，可返回任意一个k-mer所在的DNA序列编号和相应序列中出现的位置，并且保证当索引建立后
7、查询的速度尽量快，所耗内存尽量小；因此首先假设在只考虑查询速度尽量快的情况下可建立链地址哈希表模型。哈希表是一种根据关键码值而直接进行访问的数据结构，关键码值通过哈希函数将将要查询的DNA序列转换而成，记录存放在散列表内，哈希表通过把关键码值映射到表中的一个位置来访问记录；链地址哈希表的实现方法是分配一个足够长度的数组，数组中每一个元素都是一个链表，将key映射到每个数组的链表上去。所以理论上哈希表在查询一个特定的DNA序列时，可通过哈希函数将该DNA序列转换为对应的关键码值key,则该DNA序列所有可能存在的位置便可通过f(k)读取出来，
8、因此，我们不需将查询的DNA序列与文件中的DNA序列进去比对便可直接取得所需记录。哈希函数根据实现方法对于不同的DNA序列可能得到相同的key值即同一散列地址，在这种情况下，会导
