首页> 中国专利> 基于标签数据生长基因的数据序列处理方法

基于标签数据生长基因的数据序列处理方法

摘要

本发明提供了基于标签数据生长基因的数据序列处理方法,包括数据序列中标签数据生长基因的提取方法,该方法使用数据序列S扫描标签数据库,得到一组标签数据段及该数据段在数据序列S中的位置,用所述标签数据段对应的标签及其在数据序列S中的位置作为本次扫描结果参数,记录这些本次扫描结果参数,然后在数据序列S中去除所述标签数据段,用剩余数据段组装成新的数据序列S重新扫描,最后组织每一次扫描结果参数,生成原始数据序列S的生长基因序列。本发明还提供了基于标签数据生长基因的数据存储方法和数据存储方法。

著录项

  • 公开/公告号CN113035282A

    专利类型发明专利

  • 公开/公告日2021-06-25

    原文格式PDF

  • 申请/专利权人 江苏数字产权交易有限公司;

    申请/专利号CN202110581056.0

  • 发明设计人 白杰;

    申请日2021-05-27

  • 分类号G16B50/40(20190101);G16B50/50(20190101);

  • 代理机构11363 北京弘权知识产权代理有限公司;

  • 代理人逯长明;许伟群

  • 地址 211800 江苏省南京市中国(江苏)自由贸易试验区南京片区滨江大道396号1号楼

  • 入库时间 2023-06-19 11:35:49

说明书

技术领域

本发明涉及数据处理方法,特别涉及处理包含大量数据的数据序列的方法。

背景技术

在任何形式的计算机系统中,数据的存储和传输都是重要的任务。例如,网络中的数据在被传输前,为了减少实际传输的数据量,通常需要对待传输的数据进行压缩,以减少网络传输资源的占用以及减少传输失败的机会,提高数据传输的效率。通常,我们在希望数据存储的可靠和安全的同时,还希望能够尽可能少地占用存储资源,然而这是难以两全的一对矛盾。数据的可靠意味着要有一定的冗余,数据的安全通常靠编码实现对数据的加密计算,这些通常都是以多占用存储资源为基础的。

在数据传输的各个层次,减少传输重复数据的传输都具有重要意义。而减少数据重复传输的关键,在于如何获知哪些数据是重复的,以及在数据接收端迅速且无瑕疵地恢复数据发送端的原始数据。对于静态数据,即内容确定的数据集合,如果能够获知需要重复传输的数据或数据集合,为重复的数据分配一个标签或标识,就可以用所述标签替代重复的数据进行传输,从而减少数据的重传以及在数据接收端恢复原始数据。而且,标签的长度和重复数据长度的比值越小,数据传输效率就越高。

在一个数据集合中找到标签能够替代的数据段的过程,就是在数据传输前对其实施的一种处理过程。现有的数据压缩或预处理方法,通常认为一个数据集合中存在的重复“倾向于大量出现短语式的重复,而且重复倾向于出现在离当前压缩位置较近的地方,重复长度倾向于比较短(20字节以内)”,重复的字节越短,重复的概率越高。例如目前广为流行的ZIP压缩算法,就是以“短字节”的重复为基础的。然而,这样就可能导致重复的“短字节”标签的长度和重复的“短字节”的数据长度比值变大,使得高重复概率的“短字节”并不一定导致数据序列的高压缩率,因此,这种方法的压缩效果是有限的,尤其在数据重复特征明显的领域,难以与数据特征结合达到更好的数据压缩效果。

实际上,在包含大量数据的数据序列中,仍然存在着数据的构成规律,即数据序列的生长基因或构成基因,如果将这些基因提取出来,将有利于数据序列的压缩、存储以及加密等操作。

发明内容

本发明解决的问题是,提供基于标签数据生长基因的数据序列处理方法,该方法包括数据序列中标签数据生长基因的提取方法、基于标签数据生长基因的数据存储方法和基于标签数据生长基因的数据压缩方法。

其中,数据序列中标签数据生长基因的提取方法的一个实施例的操作是:通过数据序列S对标签数据库进行扫描,获取一组标签数据段以及所述标签数据段在数据序列S中的位置,判断获取的所述标签数据段是否为有效标签数据段,若获取的是有效标签数据段,用所述标签数据段对应的标签及其在数据序列S中的位置作为本次扫描结果参数,记录这些本次扫描结果参数,其中,所述标签为生长基因,标签在数据序列S中的位置为生长参数,在数据序列S中去除所述标签数据段,用剩余数据段组装成新的数据序列S,再次从通过数据序列S对标签数据库进行扫描,获取一组标签数据段以及所述标签数据段在数据序列S中的位置的步骤开始,循环所述在数据序列中提取标签数据生长基因的方法。若得到的是无效标签数据段,组织每一次扫描结果参数,生成原始数据序列S的生长基因序列。

按照数据序列中标签数据生长基因的提取方法的实施例,如果数据序列S足够长,每次扫描该数据序列S,通常都会得到一组重复的数据段及该数据段在数据序列S中的位置,而以标签数据库为基础选择标签数据段及其在数据序列S中的重复位置作为扫描结果参数,这样,就可以用长度很小的标签代替长度很大的重复数据段作为数据序列S的生长基因,用数据段的重复位置作为基因生长参数,就能获得原来的数据序列S的生长基因序列,再结合残余数据序列中的数据,就能够复原原始的数据序列。而通过对不断产生的残余数据序列进行扫描,更能多次得到每次扫描对应的生长基因和基因生长参数,通过这样一组生长基因和基因生长参数,由于没有了对重复数据长度的限制,有利于实现对数据序列S更高效率地压缩和还原,因此,本发明实施例有利于提取生长效率更高的原始数据序列S的生长基因和生长参数。

其中,基于标签数据生长基因的数据存储方法的一个实施例的操作是:先建立一个标识标签与数据段对照关系的标签数据库,标签数据库可采用滑动窗口技术生成;再基于标签数据库,预先将一个待处理的数据集合形成一个数据序列S;使用数据序列S扫描标签数据库;判断是否存在有效标签数据段,如果存在,将数据序列S中去除所述标签数据段,同时记录标签在数据序列S中的位置为生长参数,标签为生长基因;对去除标签后的数据序列S继续执行扫描操作,直到不存在有效标签数据段为止;最后将每一次扫描得到的结果参数组织起来,生成原始数据序列S的生长基因序列。

按照基于标签数据生长基因的数据存储方法的实施例,如果数据序列S足够长,每次扫描该数据序列S,通常都会得到一组重复的数据段及该数据段在数据序列S中的位置,而选择标签数据段及其在数据序列S中的重复位置作为扫描结果参数,这样,就可以用更高重复效率的重复数据段作为数据序列S的生长基因,用数据段的重复位置作为基因生长参数,再结合残余数据序列中的数据就能获得原来的数据序列S,这一点对某个特别领域尤其具有价值。而通过对不断产生的残余数据序列进行扫描,更能多次得到每次扫描对应的生长基因和基因生长参数,通过这样一组生长基因和基因生长参数,由于没有了对重复数据长度的限制,还由于标签的长度远小于其对应的数据段的长度,有利于实现对数据序列S更高效率的压缩,从而占据相对较少的存储资源。另外,由于生长基因和基因生长参数具有完全随机性,因此这样的存储方法也使数据序列S得到了很好的加密。

其中,基于标签数据生长基因的数据压缩方法的一个实施例的操作是:首先选择一个具有至少两个字符子集的字符集,两个字符子集具有互不相同的编码,使用字符集中第一字符子集的字符编码规则对待压缩的二进制数据序列进行编码,得到数据序列S;再使用数据序列S扫描预先采用滑动窗口技术生成的标签数据库,得到标签数据段以及数据段在数据序列S中的位置;判断是否存在有效标签数据段,如果存在,将数据序列S中去除所述标签数据段,同时记录标签在数据序列S中的位置为生长参数,标签为生长基因;对去除标签后的数据序列S继续执行扫描操作,直到不存在有效标签数据段为止;最后将每一次扫描得到的结果参数组织起来,生成原始数据序列S的生长基因序列。

按照基于标签数据生长基因的数据压缩方法的实施例,如果二进制数据序列S

附图说明

图1-1是本发明所述数据序列中标签数据生长基因的提取方法第一实施例流程图;

图1-2-1到图1-2-3是说明图1-1所述实施例步骤111的示意图;

图1-3是图1-1所述实施例采用的扫描子步骤流程图;

图1-4-1到图1-4-3是说明图1-3所述流程的扫描模式示意图;

图1-5是本发明所述数据序列中标签数据生长基因的提取方法第二实施例流程图;

图1-6是本发明所述数据序列中标签数据生长基因的提取方法第三实施例流程图;

图1-7-1到图1-7-3是说明图1-6所述流程的扫描模式示意图;

图2-1是本发明所述基于标签数据生长基因的数据压缩方法第一实施例流程图;

图2-2-1是说明图2-1所述实施例步骤211中第一次扫描的示意图;

图2-2-2是说明图2-1所述实施例步骤211中第二次扫描的示意图;

图2-2-3是说明图2-1所述实施例步骤211中第三次扫描的示意图;

图2-3是图2-1所述实施例采用的扫描子步骤流程图;

图2-4-1是说明图2-3所述流程在第一个位置的扫描模式示意图;

图2-4-2是说明图2-3所述流程在第二个位置的扫描模式示意图;

图2-4-3是说明图2-3所述流程在第三个位置的扫描模式示意图;

图2-5是本发明所述基于标签数据生长基因的数据压缩方法第二实施例流程图;

图2-6是本发明所述基于标签数据生长基因的数据压缩方法第三实施例流程图;

图2-7-1是说明图2-5、图2-6所述流程中扫描1级标签数据库的扫描模式示意图;

图2-7-2是说明图2-5、图2-6所述流程中扫描2级标签数据库的扫描模式示意图;

图2-7-3是说明图2-5、图2-6所述流程中扫描3级标签数据库的扫描模式示意图;

图2-7-4是说明图2-5、图2-6所述流程中扫描4级标签数据库的扫描模式示意图;

图2-8是本发明所述基于标签数据生长基因的数据恢复方法的第一实施例流程图;

图2-9是本发明所述基于标签数据生长基因的数据恢复方法的第二实施例流程图;

图3-1是本发明所述基于标签数据生长基因的数据压缩方法第一实施例流程图;

图3-2是本发明所述基于标签数据生长基因的数据压缩方法第二实施例流程图;

图3-3-1是说明图3-1、图3-2所述实施例步骤311中第一次扫描的示意图;

图3-3-2是说明图3-1、图3-2所述实施例步骤311中第二次扫描的示意图;

图3-3-3是说明图3-1、图3-2所述实施例步骤311中第三次扫描的示意图;

图3-4是图3-1、图3-2所述实施例采用的扫描子步骤流程图;

图3-5-1是说明图3-4所述流程在第一个位置的扫描模式示意图;

图3-5-2是说明图3-4所述流程在第二个位置的扫描模式示意图;

图3-5-3是说明图3-4所述流程在第三个位置的扫描模式示意图;

图3-6是本发明所述基于标签数据生长基因的数据压缩方法第三实施例流程图;

图3-7是本发明所述基于标签数据生长基因的数据压缩方法第四实施例流程图;

图3-8-1是说明图3-6、图3-7所述流程中扫描1级标签数据库的扫描模式示意图;

图3-8-2是说明图3-6、图3-7所述流程中扫描2级标签数据库的扫描模式示意图;

图3-8-3是说明图3-6、图3-7所述流程中扫描3级标签数据库的扫描模式示意图;

图3-8-4是说明图3-6、图3-7所述流程中扫描4级标签数据库的扫描模式示意图。

具体实施方式

下面将结合本发明实施例中的附图,对本发明实施例中的技术方案进行清楚、完整地描述,显然,所描述的实施例仅仅是本发明一部分实施例,而不是全部的实施例。基于本发明中的实施例,本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其它实施例,都属于本发明保护的范围。

实际上,在包含大量数据的数据序列中,存在着大量重复的数据段,如果将这些数据段及其重复规律提取出来作为生长要素和生长参数,即数据序列的生长基因,那么就能够以生长基因为基础还原出来原来的数据序列。

在某些领域,数据序列具有较弱的随机性,但是较强的规律性和一定的构成特征,例如高重复概率的数据段构成特征具有高度的相似性,此时,将预先生成的标签数据库中存在的重复数据段提取出来作为数据序列的生长基因,会使数据序列得到较高的压缩效率。

图1-1是本发明所述数据序列中标签数据生长基因的提取方法第一实施例流程图。图1-1所示实施例需要一个标签数据库,该标签数据库的生成是通过对大量特定领域的数据分析预先完成的。通常按照数据应用领域的数据特性,尽可能多地确定多个重复概率较高的数据段,为这些数据段设置彼此不重复的标签标识,将所述标签与所述数据段绑定在一起,存储入标签数据库,即标签与数据段对照关系数据库。利用所述标签数据库中的标签和所述数据段的绑定关系,就可以用标签代替截取的数据段。

一般采用滑动窗口技术生成标签数据库。即,借助于一个指纹函数和一个窗口,来确定重复的数据段。为了更有效地确定所述数据段,可以通过动态调整窗口偏移量来辅助确定。需要指出的是,这个窗口大小的选择,可能与重复数据段的确定原则对应的窗口大小不同,应当适应不同层次数据段划分的需要。

基于所述标签数据库,预先将一个待处理的数据集合,例如一个二进制的静态数据段或动态数据流读入到计算机内存储器,经过必要的处理,例如编码处理,形成一个数据序列S。然后按照图1-1,在步骤111使用数据序列S扫描标签数据库,如果数据序列S中有与数据库的标签对应的数据段,就会被标识出来。因此,经过步骤111就可能得到一组标签数据段及该数据段在数据序列S中的位置。经过步骤111扫描得到的具体内容可以通过步骤112知道。

如果数据序列S中没有与数据库的标签对应的数据段,通常就会得到一个特殊的标识,例如一个特定的字符串或空串,这样有利于步骤112的判断操作。

在步骤112判断是否得到有效的标签数据段,如果得到,在步骤113用所述标签数据段对应的标签及其在数据序列S中的位置作为本次扫描结果参数,记录这些本次扫描结果参数,其中,所述标签为生长基因,标签在数据序列S中的位置为生长参数,然后转步骤114继续后续的处理。如果没有得到标签数据段,说明在当前的数据序列S中已经没有标签数据库的标签对应的数据段,这时转步骤115,将每一次扫描得到的结果参数组织起来,生成原始数据序列S的生长基因序列。

在步骤114,在数据序列S中去除所述标签数据段,用剩余数据段组装成新的数据序列S,转步骤111继续下一次的标签数据段的扫描操作。

图1-2-1到图1-2-3是说明图1-1所述实施例的示意图。

假设标签数据库如下述表1-1所示,它有三个字段,分别是“编号”、“标签”、“数据段”。

图1-2-1所示,经过步骤111的扫描操作,数据序列S中有三个标签数据段被标识出来,即起点为a的数据段SA,起点为b的数据段SB,起点为c的数据段SC。经过步骤113,生成对应的第一次扫描结果如下述表1-2所示。

经过步骤114生成的新的数据序列S参考图1-2-2。经过步骤111继续扫描当前的数据序列S,即图1-2-2所示的数据序列S,有二个标签数据段被标识出来,即起点为d的数据段SD,起点为e的数据段SE。经过步骤113,生成对应的第二次扫描结果如下述表1-3所示。

经过步骤114生成的新的数据序列S参考图1-2-3。经过步骤111继续扫描当前的数据序列S,即图1-2-3所示的数据序列S,没有标签数据段被标识出来,经过步骤112的判断,转步骤115将前二次扫描得到的结果参数组织起来,生成原始数据序列S的生长基因序列,参考下述表1-4。

图1-3是图1-1所述实施例步骤111采用的扫描子步骤流程图。

在图1-1所述实施例中,步骤111所述使用S扫描标签数据库有很多方法,在本例中采用反向扫描的方式,即用标签数据库的内容与S的内容比较,而实现使用S扫描标签数据库的操作。

按照图1-3,首先在121设置扫描起点i。本例中i=1,即指示从第一个字符开始扫描。i也可以是其它起点,例如一个特别的数据头后面的一位字符的位置。需要说明,在实际应用中,i的不同起点有特别的价值,例如增加提取出来的数据基因的还原原始数据时的生长效率,以及增加提取过程的灵活性和保密性等等。

然后在122,先计算获得i位起到数据序列S的尾部的数据段的长度,以及从标签数据库中获得数据库中长度最小的数据段的长度,接着判断数据序列S中从i位起到S的尾部的数据段的长度是否大于标签数据库中最小标签的长度,如果是,转步骤123进行扫描操作;否则,说明S的长度过短,已经没有提取生长基因的价值,这时就转步骤128结束扫描操作。

在步骤123,用标签数据库的内容引导数据S的分割或扫描。这个过程是:依次从标签数据库中取出每一个标签对应的数据段,使用这些数据段从数据序列S的扫描起点i起,扫描或顺序扫描从i点到数据序列S尾部的数据段。即依次使用这些数据段去匹配从起点i开始的相应长度的数据段,例如用该数据段的指纹或散列值去比较S的相应部分,就可以得知是否在第一数据库中找到了能够用标签替代的数据段。

如果标签数据库中的每一个标签对应的数据段都不能在数据序列S中找到与之相同的数据段,说明在标签数据库中没有找到能够匹配的数据段,此时,将空串作为扫描结果,即用空串作为匹配的数据段,如果在标签数据库中有一个标签对应的数据段能够与从起点i开始的相应长度的数据段匹配,则将该数据段作为扫描结果,即用该数据段作为匹配的数据段。如果有多个匹配数据段,即在标签数据库中有多个标签对应的数据段能够与从起点i开始的相应长度的数据段匹配,则将第一个匹配的数据段或者最长的数据段作为扫描结果,本例中用第一个匹配的数据段作为扫描结果。

步骤123的扫描结果可以通过步骤124获知。步骤124是一个判断步骤,如果判断得知步骤123得到匹配数据段,则在步骤125将起点i顺序后移一个数据位,即使i=i+1,然后转步骤122从新的i指示的位置起开始扫描数据序列S剩余的数据位;如果有匹配数据段,在步骤126记录该数据段的标签及该数据段在数据序列S中的位置,然后在步骤127将起点i顺序后移该数据段的长度个数据位,即使i=i+L,L为数据段的长度,然后转步骤122从新的i指示的位置起开始扫描数据序列S剩余的数据位。

步骤128是一个输出步骤,将所有数据段的标签及其在数据序列S中的位置作为参数输出,具体的形式参考表1-2。如果没有扫描到与标签数据库内标签数据段相同的数据段,步骤128就会输出空集或空字符串。

步骤123采用的扫描模式有两种:扫描或顺序扫描。可以采用其中任意一种模式。具体参考图1-4-1到图1-4-3。

扫描模式的方式是,用标签数据库中的第一个标签对应的数据段从i点开始匹配相应长度的数据段,如图1-4-1,从i=1的位置开始匹配操作,如果该数据段匹配不成功,则用标签数据库中的第二个标签对应的数据段从i点开始匹配相应长度的数据段,直到找到匹配的数据段或者标签数据库中的所有标签数据段全部匹配完毕。如果没有找到匹配的数据段,则从图1-4-2所示的下一个数据位开始继续扫描,此时i=2。如果仍没有找到匹配的数据段,则从图1-4-3所示的下一个数据位开始继续扫描,此时i=3。

顺序扫描模式的方式是,用标签数据库中的第一个标签对应的数据段从i点开始匹配相应长度的数据段,如图1-4-1,从i=1的位置开始匹配操作,如果该数据段匹配不成功,则仍然用第一个标签对应的数据段从下一个位置,如图1-4-2所示的下一个数据位开始继续扫描,此时i=2。如果该数据段匹配还不成功,则仍然用第一个标签对应的数据段从下一个位置,如图1-4-3所示的下一个数据位开始继续扫描,此时i=3。以上方式直到匹配成功或者扫描完毕。如果第一个数据段匹配不成功,则用标签数据库中的第二个标签对应的数据段按照图1-4-1到图1-4-3的模式从i点开始匹配相应长度的数据段,直到匹配成功或者扫描完毕。以此类推直到有匹配的数据段或者标签数据库的标签对应的数据段全部匹配完毕。

图1-5是本发明所述数据序列中标签数据生长基因的提取方法第二实施例流程图。

图1-5所述实施例基于所述标签数据库,预先将一个待处理的数据集合,例如一个二进制的静态数据段或动态数据流读入到计算机内存储器,经过必要的处理,例如编码处理,形成一个数据序列S。然后按照图1-5,在步骤161判断数据序列S是否满足扫描条件,如果是,转步骤162进行扫描操作;否则,转步骤165终止扫描输出扫描结果。这里所述条件是两个并列的条件,一个条件是数据序列S的长度小于标签数据库中最小标签的长度,这时没有扫描的意义,数据序列S太短。第二个条件是,经过扫描没有找到匹配标签数据段,这时也没有必要继续扫描。实际中也可以设置其它终止扫描的条件,当扫描中发现某个特定的字符或字符串,等等。

在步骤162使用数据序列S扫描标签数据库,如果数据序列S中有与数据库的标签对应的数据段,就会被标识出来。如果数据序列S中没有与数据库的标签对应的数据段,通常就会得到一个特殊的标识,例如一个特定的字符串或空串。因此步骤162结束后能够得到一组标签数据段及该数据段在数据序列S中的位置,将这些数据作为本次的扫描结果参数。

在步骤163将步骤162得到的本次扫描结果参数记录下来,这个结果只能是具体的数据段等参数,或是“空”参数,其中,所述标签为生长基因,标签在数据序列S中的位置为生长参数。接着在步骤164将数据序列S中的所述标签数据段去除,用剩余数据段组装成新的数据序列S,转步骤161继续下一次的标签数据段的扫描操作。如果没有得到标签数据段,说明在当前的数据序列S中已经没有标签数据库的标签对应的数据段,这时的数据序列S与扫描前相比没有变化,这时也转步骤161,由步骤161引导结束。

在步骤165,将每一次扫描得到的结果参数组织起来,生成原始数据序列S的生长基因序列,参考表1-4。

图1-6是本发明所述数据序列中标签数据生长基因的提取方法第三实施例流程图。图1-6所述实施例就是一个基于多级标签数据库的实施例。本例中,有三个标签数据库,即一级标签数据库、二级标签数据库和三级标签数据库。

按照图1-6,在步骤181,设置标签数据库的初始级数n为1,n的最大值N=3,N为标签数据库的级数,这样就能保证扫描操作以这三个标签数据库为基础。

在步骤182,判断n是否小于或等于N,如果是,在步骤183使用数据序列S扫描n级标签数据库,得到一组标签数据段及该数据段在数据序列S中的位置。如果数据序列S中有与该级标签数据库的标签对应的数据段,就会被标识出来。如果数据序列S中没有与数据库的标签对应的数据段,通常就会得到一个特殊的标识,例如一个特定的字符串或空串,因此,该组标签数据段及该数据段在数据序列S中的位置是真实的数据或者是“空”。

如果步骤184判断得知得到了标签数据段,则在步骤185用所述标签数据段对应的标签及其在数据序列S中的位置作为本级扫描结果参数,将这些本级的扫描结果参数记录下来,其中,所述标签为生长基因,标签在数据序列S中的位置为生长参数然后转步骤186继续下一级标签数据库的扫描;如果没有得到标签数据段,则转步骤187结束生长基因的提取操作;

在步骤186,在数据序列S中,用所述标签数据段的标签代替所述标签数据段,组装成新的数据序列S,令n=n+1,指示以下级标签数据库为基础扫描新的数据序列S,转步骤182继续。

在步骤187,将每一级扫描得到的结果参数组织起来,生成原始数据序列S的生长基因序列。

假设有如下三个标签数据库,表5-1为一级标签数据库,表5-2为二级标签数据库,表5-3为三级标签数据库,其内容如下:

按照图1-6所述实施例,在步骤181设置n=1,N=3。由于在步骤182判断得知n小于N,则在步骤183使用数据序列S扫描1级标签数据库,结果参考图1-7-1,得到了标签数据段S1A、S1B、S1C、S1D及其在数据序列S中的位置,其中S1C出现三次,S1A、S1B、S1C连续,连续两次的S1C和S1D连续。这样,经过步骤184的判断,得知扫描得到了标签数据段,在步骤185,用所述标签数据段S1A、S1B、S1C、S1D对应的标签L1A、L1B、L1C、L1D及其在数据序列S中的位置作为本级扫描结果参数,并记录了这些本次扫描结果参数。在步骤186,在数据序列S中用所述标签数据段的标签L1A、L1B、L1C、L1D代替对应的标签数据段,组装成新的数据序列S,参考图1-7-2,然后令n=n+1,转步骤112继续以下级标签数据库,即2级标签数据库为基础扫描新的数据序列S。

假设连续的S1A、S1B、S1C就是表5-2所示的二级数据库中的S2C,连续的S1C就是表5-2所示的二级数据库中的S2D,这样经过第二次扫描,经过步骤184的判断,得知扫描得到了标签数据段,在步骤185,用所述标签数据段S2C、S2D对应的标签L2C和L2D及其在数据序列S中的位置作为本级扫描结果参数,并记录了这些本次扫描结果参数。在步骤186,在数据序列S中用所述标签数据段的标签L2C、L2D代替对应的标签数据段,组装成新的数据序列S,参考图1-7-3,然后令n=n+1,转步骤112继续以下级标签数据库,即3级标签数据库为基础扫描新的数据序列S。

假设第三次扫描没有得到重复数据段,则要在步骤187,组织每一级扫描结果参数,生成原始数据序列S的生长基因序列,参考表1-6。

在步骤183使用数据序列S扫描n级标签数据库的过程例如:

A.设置扫描起点i,例如另i=1;

B.判断数据序列S中从i位起到S的尾部的数据段的长度是否小于n级标签数据库中最小标签的长度,如果小于,要么数据序列S长度过短,要么扫描应当结束,因此转步骤E;否则,转步骤C;

C.依次使用标签数据库的每一个标签对应的数据段从数据序列S的扫描起点i起,扫描或顺序扫描从i点到数据序列S尾部的数据段;

D.如果没有匹配数据段,将起始点i顺序后移一个数据位,转步骤B;如果有匹配数据段,记录该数据段的标签及该数据段在数据序列S中的位置,将起始点i顺序后移该数据段的长度个数据位,转步骤B;

E.将所有数据段的标签及其在数据序列S中的位置作为一组参数输出。

在基于图1-6所述实施例的另一个实施例中,在步骤181之前增加了一个判断步骤180(图1-6中未绘出),判断数据序列S是否满足扫描条件,如果满足条件,再转步骤182;否则,直接转步骤116结束。鉴于本实施例其它部分与图1-6 所述实施例相同,此不再赘述。

实际上,在包含大量数据的数据序列中,存在着大量重复的数据段,如果将这些数据段及其重复规律提取出来作为生长要素和生长参数,即数据序列的生长基因,那么就能够以生长基因为基础还原出来原来的数据序列。

在某些领域,数据序列具有较弱的随机性,但是较强的规律性和一定的构成特征,例如高重复概率的数据段构成特征具有高度的相似性,此时,将预先生成的标签数据库中存在的重复数据段提取出来作为数据序列的生长基因,会使数据序列得到较高的压缩效率。

图2-1是本发明所述基于标签数据生长基因的数据存储方法第一实施例流程图。

图2-1所示实施例需要一个标签数据库,该标签数据库的生成是通过对大量特定领域的数据分析预先完成的。通常按照数据应用领域的数据特性,尽可能多地确定多个重复概率较高的数据段,为这些数据段设置彼此不重复的标签标识,将所述标签与所述数据段绑定在一起,存储入标签数据库,即标签与数据段对照关系数据库。利用所述标签数据库中的标签和所述数据段的绑定关系,就可以用标签代替截取的数据段。

一般采用滑动窗口技术生成标签数据库。即,借助于一个指纹函数和一个窗口,来确定重复的数据段。为了更有效地确定所述数据段,可以通过动态调整窗口偏移量来辅助确定。需要指出的是,这个窗口大小的选择,可能与重复数据段的确定原则对应的窗口大小不同,应当适应不同层次数据段划分的需要。

基于所述标签数据库,预先将一个待处理的数据集合,例如一个二进制的静态数据段或动态数据流读入到计算机内存储器,经过必要的处理,例如编码处理,形成一个数据序列S。然后按照图2-1,在步骤211使用数据序列S扫描标签数据库,如果数据序列S中有与数据库的标签对应的数据段,就会被标识出来。因此,经过步骤211就可能得到一组标签数据段及该数据段在数据序列S中的位置。经过步骤211扫描得到的具体内容可以通过步骤212知道。

如果数据序列S中没有与数据库的标签对应的数据段,通常就会得到一个特殊的标识,例如一个特定的字符串或空串,这样有利于步骤212的判断操作。

在步骤212判断是否得到有效的标签数据段,如果得到,在步骤213用所述标签数据段对应的标签及其在数据序列S中的位置作为本次扫描结果参数,记录这些本次扫描结果参数,其中,所述标签为生长基因,标签在数据序列S中的位置为生长参数,然后转步骤214继续后续的处理。如果没有得到标签数据段,说明在当前的数据序列S中已经没有标签数据库的标签对应的数据段,这时转步骤215,将每一次扫描得到的结果参数组织起来,生成原始数据序列S的生长基因序列。

在步骤214,在数据序列S中去除所述标签数据段,用剩余数据段组装成新的数据序列S,转步骤211继续下一次的标签数据段的扫描操作。

在步骤216,用当前的或者新的数据序列S和原始数据序列的生长基因序列组装成基因数据序列S’存储。

步骤216执行的结果可以有多种样式,只要能够在其中正确解析出当前的数据序列S和原始数据序列的生长基因序列即可。例如下述数据串表达的S’:

因此,S’就是存储到存储器中的原始数据序列对应的基因数据序列。

下面参考图2-2-1到图2-2-3继续说明。

图2-2-1到图2-2-3是说明图2-1所述实施例的示意图。

假设标签数据库如下述表2-1所示,它有三个字段,分别是“编号”、“标签”、“数据段”。

图2-2-1所示,经过步骤211的扫描操作,数据序列S中有三个标签数据段被标识出来,即起点为a的数据段SA,起点为b的数据段SB,起点为c的数据段SC。经过步骤213,生成对应的第一次扫描结果如下述表2-2所示。

经过步骤214生成的新的数据序列S参考图2-2-2。经过步骤211继续扫描当前的数据序列S,即图2-2-2所示的数据序列S,有二个标签数据段被标识出来,即起点为d的数据段SD,起点为e的数据段SE。经过步骤213,生成对应的第二次扫描结果如下述表2-3所示。

经过步骤214生成的新的数据序列S参考图2-2-3。经过步骤211继续扫描当前的数据序列S,即图2-2-3所示的数据序列S,没有标签数据段被标识出来,经过步骤212的判断,转步骤215将前二次扫描得到的结果参数组织起来,生成原始数据序列S的生长基因序列,参考下述表2-4。

步骤216执行的结果得到的下述数据串表达的S’可以这样解释:

本次扫描得到当前数据序列S和二次基因序列,其中:

当前数据序列S,是图2-2-3所示的数据序列S。二次基因序列,是[LD,d]和[LE,e];一次基因序列,是[LC,c]、[LB,b]和[LA,a]。

因此,S’就是存储到存储器中的原始数据序列对应的基因数据序列,其内容为:

[S] [LA,a] 、[LB,b]、[LC,c]、[LD,d]、[LE,e]。

图2-3是图2-1所述实施例步骤211采用的扫描子步骤流程图。

在图2-1所述实施例中,步骤211所述使用S扫描标签数据库有很多方法,在本例中采用反向扫描的方式,即用标签数据库的内容与S的内容比较,而实现使用S扫描标签数据库的操作。

按照图2-3,首先在221设置扫描起点i。本例中i=1,即指示从第一个字符开始扫描。i也可以是其它起点,例如一个特别的数据头后面的一位字符的位置。需要说明,在实际应用中,i的不同起点有特别的价值,例如增加提取出来的数据基因的还原原始数据时的生长效率,以及增加提取过程的灵活性和保密性等等。

然后在222,先计算获得i位起到数据序列S的尾部的数据段的长度,以及从标签数据库中获得数据库中长度最小的数据段的长度,接着判断数据序列S中从i位起到S的尾部的数据段的长度是否大于标签数据库中最小标签的长度,如果是,转步骤223进行扫描操作;否则,说明S的长度过短,已经没有提取生长基因的价值,这时就转步骤228结束扫描操作。

在步骤223,用标签数据库的内容引导数据S的分割或扫描。这个过程是:依次从标签数据库中取出每一个标签对应的数据段,使用这些数据段从数据序列S的扫描起点i起,扫描或顺序扫描从i点到数据序列S尾部的数据段。即依次使用这些数据段去匹配从起点i开始的相应长度的数据段,例如用该数据段的指纹或散列值去比较S的相应部分,就可以得知是否在第一数据库中找到了能够用标签替代的数据段。

如果标签数据库中的每一个标签对应的数据段都不能在数据序列S中找到与之相同的数据段,说明在标签数据库中没有找到能够匹配的数据段,此时,将空串作为扫描结果,即用空串作为匹配的数据段,如果在标签数据库中有一个标签对应的数据段能够与从起点i开始的相应长度的数据段匹配,则将该数据段作为扫描结果,即用该数据段作为匹配的数据段。如果有多个匹配数据段,即在标签数据库中有多个标签对应的数据段能够与从起点i开始的相应长度的数据段匹配,则将第一个匹配的数据段或者最长的数据段作为扫描结果,本例中用第一个匹配的数据段作为扫描结果。

步骤223的扫描结果可以通过步骤224获知。步骤224是一个判断步骤,如果判断得知步骤223没有得到匹配数据段,则在步骤225将起点i顺序后移一个数据位,即使i=i+1,然后转步骤222从新的i指示的位置起开始扫描数据序列S剩余的数据位;如果有匹配数据段,在步骤226记录该数据段的标签及该数据段在数据序列S中的位置,然后在步骤227将起点i顺序后移该数据段的长度个数据位,即使i=i+L,L为数据段的长度,然后转步骤222从新的i指示的位置起开始扫描数据序列S剩余的数据位。

步骤228是一个输出步骤,将所有数据段的标签及其在数据序列S中的位置作为参数输出,具体的形式参考表2-2。如果没有扫描到与标签数据库内标签数据段相同的数据段,步骤228就会输出空集或空字符串。

步骤223采用的扫描模式有两种:扫描或顺序扫描。可以采用其中任意一种模式。具体参考图2-4-1到图2-4-3。

扫描模式的方式是,用标签数据库中的第一个标签对应的数据段从i点开始匹配相应长度的数据段,如图2-4-1,从i=1的位置开始匹配操作,如果该数据段匹配不成功,则用标签数据库中的第二个标签对应的数据段从i点开始匹配相应长度的数据段,直到找到匹配的数据段或者标签数据库中的所有标签数据段全部匹配完毕。如果没有找到匹配的数据段,则从图2-4-2所示的下一个数据位开始继续扫描,此时i=2。如果仍没有找到匹配的数据段,则从图2-4-3所示的下一个数据位开始继续扫描,此时i=3。

顺序扫描模式的方式是,用标签数据库中的第一个标签对应的数据段从i点开始匹配相应长度的数据段,如图2-4-1,从i=1的位置开始匹配操作,如果该数据段匹配不成功,则仍然用第一个标签对应的数据段从下一个位置,如图2-4-2所示的下一个数据位开始继续扫描,此时i=2。如果该数据段匹配还不成功,则仍然用第一个标签对应的数据段从下一个位置,如图2-4-3所示的下一个数据位开始继续扫描,此时i=3。以上方式直到匹配成功或者扫描完毕。如果第一个数据段匹配不成功,则用标签数据库中的第二个标签对应的数据段按照图2-4-1到图2-4-3的模式从i点开始匹配相应长度的数据段,直到匹配成功或者扫描完毕。以此类推直到标签数据库的标签对应的数据段全部匹配完毕。

图2-5是本发明所述基于标签数据生长基因的数据存储方法第二实施例流程图。

图2-5所述实施例基于所述标签数据库,预先将一个待处理的数据集合,例如一个二进制的静态数据段或动态数据流读入到计算机内存储器,经过必要的处理,例如编码处理,形成一个数据序列S。然后按照图2-5,在步骤261判断数据序列S是否满足扫描条件,如果是,转步骤262进行扫描操作;否则,转步骤265终止扫描输出扫描结果。这里所述条件是两个并列的条件,一个条件是数据序列S的长度小于标签数据库中最小标签的长度,这时没有扫描的意义,数据序列S太短。第二个条件是,经过扫描没有找到匹配标签数据段,这时也没有必要继续扫描。实际中也可以设置其它终止扫描的条件,当扫描中发现某个特定的字符或字符串,等等。

在步骤262使用数据序列S扫描标签数据库,如果数据序列S中有与数据库的标签对应的数据段,就会被标识出来。如果数据序列S中没有与数据库的标签对应的数据段,通常就会得到一个特殊的标识,例如特定的字符串或空串。因此步骤262结束后能够得到一组标签数据段及该数据段在数据序列S中的位置,将这些数据作为本次的扫描结果参数。

在步骤263将步骤262得到的本次扫描结果参数记录下来,这个结果只能是具体的数据段等参数,或是“空”参数,其中,所述标签为生长基因,标签在数据序列S中的位置为生长参数。接着在步骤264将数据序列S中的所述标签数据段去除,用剩余数据段组装成新的数据序列S,转步骤261继续下一次的标签数据段的扫描操作。如果没有得到标签数据段,说明在当前的数据序列S中已经没有标签数据库的标签对应的数据段,这时的数据序列S与扫描前相比没有变化,这时也转步骤261,由步骤261引导结束。

在步骤265,将每一次扫描得到的结果参数组织起来,生成原始数据序列S的生长基因序列,参考表2-4。

在步骤266,用当前的或者新的数据序列S和原始数据序列的生长基因序列组装成基因数据序列S’存储。

步骤266执行的结果可以有多种样式,只要能够在其中正确解析出当前的数据序列S和原始数据序列的生长基因序列即可。例如下述数据串表达的S’:

因此,S’就是存储到存储器中的原始数据序列对应的基因数据序列。

与上述实施例对应的基于标签数据生长基因的数据恢复方法的第一实施例参考图2-8。

如果一个数据序列以基因数据序列的形式被存储到存储器中,要获得原始的数据序列们就要对基因数据序列执行相应的还原操作。按照图2-8,首先在步骤2101分解基因数据序列,即分解或解析数据序列S’,就会得到其中的当前数据序列S和原始数据序列全部的生长基因序列。

由于数据序列的还原要逆向进行,因此,在步骤2102从生长基因序列中取出产生的时间最晚或级别最低的生长基因及生长参数,即获得了重复数据段和其在S中的位置参数。考虑到在极限的情况下,可能得到的是无效基因,例如,原始数据序列过短没有有效的基因参数,生长基因序列操作完毕后,将会以“空”数据作为操作完毕的标志,等等,因此在步骤2103通过生长基因或生长参数判断该基因是否有效,如果有效说明能够进行正常的数据序列的恢复操作,此时转步骤2104;否则说明全部恢复操作已经结束,或者不能进行有效的恢复操作,此时转步骤2105结束操作。

在步骤2104,从标签数据库中按照生长基因对应的标签取出相应的数据段,按照生长参数的数值指示,将表达生长基因的数据段插入到当前数据序列S的相应位置,形成新的当前数据段S,此时的S已经通过该基因的生长得到了某种恢复,此时转步骤2102继续后续数据序列的恢复操作。

在步骤2105,将最后得到的当前数据序列S就是原始数据序列,因此将最后得到的当前数据序列S作为恢复后的原始数据序列。

下面参考图2-2-1到图2-2-3进行说明。图2-1所述实施例的步骤216执行的结果得到的下述数据串表达的S’为:

[S] [LA,a] 、[LB,b]、[LC,c]、[LD,d]、[LE,e]。

按照图2-8进行数据恢复操作时,首先在步骤2101分解基因数据序列,即分解或解析数据序列S’,就会得到[S]、 [LA,a] 、[LB,b]、[LC,c]、[LD,d]、[LE,e]。

在步骤2102从生长基因序列中取出产生的时间最晚或级别最低的生长基因及生长参数[LE,e],即获得了重复数据段LE和其在S中的位置参数e。在步骤2103通过生长基因LE或生长参数e判断本级数据基因是否有效,由于这是有效数据,说明能够进行正常的本级数据序列的恢复操作,此时转步骤2104;否则说明全部恢复操作已经结束,或者不能进行有效的恢复操作,此时转步骤2105结束操作。

在步骤2104,从标签数据库中按照生长基因LE对应的标签取出相应的数据段SE,按照生长参数e的数值指示,将表达生长基因的数据段SE插入到当前数据序列S的相应位置,形成新的当前数据段S,此时的S已经通过该基因的生长得到了某种恢复,此时转步骤2102继续后续数据序列的恢复操作。

在步骤2102继续从生长基因序列中取出产生的时间最晚或级别最低的生长基因及生长参数[LD,d],在步骤2103判断该基因是否有效,由于这是有效数据,此时转步骤2104;从标签数据库中按照生长基因LD对应的标签取出相应的数据段SD,按照生长参数d的数值指示,将表达生长基因的数据段SD插入到当前数据序列S的相应位置,形成新的当前数据段S,此时的S已经通过该基因的生长进一步得到了某种恢复,此时转步骤2102继续后续数据序列的恢复操作。依此类推,最后得到的当前数据序列S就是恢复后的原始数据序列。

需要说明的是,图2-8所述实施例也可能有多种变形,例如通过步骤2101得到的全部生长基因序列的数据量的多少判断基因是否有效,等等。

在前述实施例中,往往希望标签数据段越大越好,如果得到的数据段大,会认为得到的标签数据生长基因更具有效性。因为拥有固定存储位数的标签会生长为位数更长的数据段。但是,问题的另一方面,标签数据段如果比较大,会使重复性变差,这样反倒影响数据的压缩率。

同样,如果标签数据段尺寸太小,固定存储位数的标签生长效率就会变低,因为一个具体的拥有固定存储位数的标签能够生长的数据段的位数会比较少,但是这样会增加标签的重复生长机会。因此,在很多情况下,需要在数据段的长度方面取得一个平衡。

解决这个问题的一个方法,就是利用数据段小而重复性高的特点,采用多级标签解决标签生长率、重复率以及数据段大小之间的矛盾,这样就能将大数据段和高重复性的优点结合起来。

二级标签的方式可以这样理解。一级标签预处理结果中可能存在一个连续的标签段有高度的重复性,显然,用更高一级的标签,即二级标签替代连续的一级标签段将进一步提高从原始数据序列S中提取有效生长基因的可能性。

因此,可以按照数据应用领域的特性,选择多个满足重复率要求的一级标签组及标识该一级标签组的二级标签生成二级标签数据库,这样,利用所述二级标签与所述一级标签组的绑定关系,就可以通过所述二级标签数据库和一级标签处理结果,生成基于二级标签的二级标签数据生长基因。以此类推,选择多个满足重复率要求的二级标签组及标识该二级标签组的三级标签生成三级标签数据库。

图2-6是本发明所述基于标签数据生长基因的数据存储方法第三实施例流程图。图2-6所述实施例就是一个基于多级标签数据库的实施例。本例中,有三个标签数据库,即一级标签数据库、二级标签数据库和三级标签数据库。

按照图2-6,在步骤281,设置标签数据库的初始级数n为1,n的最大值N=3,N为标签数据库的级数,这样就能保证扫描操作以这三个标签数据库为基础。

在步骤282,判断n是否小于或等于N,如果是,在步骤283使用数据序列S扫描n级标签数据库,得到一组标签数据段及该数据段在数据序列S中的位置。如果数据序列S中有与该级标签数据库的标签对应的数据段,就会被标识出来。如果数据序列S中没有与数据库的标签对应的数据段,通常就会得到一个特殊的标识,例如一个特定的字符串或空串,因此,该组标签数据段及该数据段在数据序列S中的位置是真实的数据或者是“空”。

如果步骤284判断得知得到了标签数据段,则在步骤285用所述标签数据段对应的标签及其在数据序列S中的位置作为本级扫描结果参数,将这些本级的扫描结果参数记录下来,其中,所述标签为生长基因,标签在数据序列S中的位置为生长参数然后转步骤286继续下一级标签数据库的扫描;如果没有得到标签数据段,则转步骤287结束生长基因的提取操作;

在步骤286,在数据序列S中,用所述标签数据段的标签代替所述标签数据段,组装成新的数据序列S,令n=n+1,指示以下级标签数据库为基础扫描新的数据序列S,转步骤282继续。

在步骤287,将每一级扫描得到的结果参数组织起来,生成原始数据序列S的生长基因序列。

在步骤288,用当前的或者新的数据序列S和原始数据序列的生长基因序列组装成基因数据序列S’存储。

步骤288执行的结果可以有多种样式,只要能够在其中正确解析出当前的数据序列S和原始数据序列的生长基因序列即可。例如:

[当前数据序列S][一级基因序列][二级基因序列][三级基因序列];

假设有如下三个标签数据库,表5-1为一级标签数据库,表5-2为二级标签数据库,表5-3为三级标签数据库,其内容如下:

按照图2-6所述实施例,在步骤281设置n=1,N=3。由于在步骤282判断得知n小于N,则在步骤283使用数据序列S扫描1级标签数据库,结果参考图2-7-1,得到了标签数据段S1A、S1B、S1C、S1D及其在数据序列S中的位置,其中S1C出现三次,S1A、S1B、S1C连续,连续两次的S1C和S1D连续。这样,经过步骤284的判断,得知扫描得到了标签数据段,在步骤285,用所述标签数据段S1A、S1B、S1C、S1D对应的标签L1A、L1B、L1C、L1D及其在数据序列S中的位置作为本级扫描结果参数,并记录了这些本次扫描结果参数。在步骤286,在数据序列S中用所述标签数据段的标签L1A、L1B、L1C、L1D代替对应的标签数据段,组装成新的数据序列S,参考图2-7-2,然后令n=n+1,转步骤212继续以下级标签数据库,即2级标签数据库为基础扫描新的数据序列S。

假设连续的S1A、S1B、S1C就是表5-2所示的二级数据库中的S2C,连续的S1C就是表5-2所示的二级数据库中的S2D,这样经过第二次扫描,经过步骤284的判断,得知扫描得到了标签数据段,在步骤285,用所述标签数据段S2C、S2D对应的标签L2C和L2D及其在数据序列S中的位置作为本级扫描结果参数,并记录了这些本次扫描结果参数。在步骤286,在数据序列S中用所述标签数据段的标签L2C、L2D代替对应的标签数据段,组装成新的数据序列S,参考图2-7-3,然后令n=n+1,转步骤212继续以下级标签数据库,即3级标签数据库为基础扫描新的数据序列S。

假设第三次扫描没有得到重复数据段,则要在步骤287,组织每一级扫描结果参数,生成原始数据序列S的生长基因序列,参考表2-6。

此时,新的数据序列S,即当前的数据序列S如图2-7-3所示,由于图2-7-3中的标签已经在表2-6中记载,因此,步骤288所示的当前数据序列S是在图2-7-3基础上去除了L2C、L2D后的数据段,参考图2-7-4。因此,当前数据序列S,是图2-7-4所示的数据序列S。二级基因序列,是[L2D,d21]和[L2C,c21];一次基因序列,是[L1D,d11]、 [L1C,c11,c12,c13]、[L1B,b11]和[L1A,a11]。特别指出,由于图2-7-3的L1D没有被包含在二级标签中,因此,步骤288所示的当前数据序列S包含L1D,参考图2-7-4。在另外的例子中,当前数据序列S也可以不经过去除L2C、L2D的操作,如图2-7-3所示,这样也能实现原始数据序列的恢复操作。

因此,S’就是存储到存储器中的原始数据序列对应的基因数据序列,其内容为:

[S] [L1D,d11]、 [L1C,c11,c12,c13]、[L1B,b11]和[L1A,a11]、[L2D,d21]、[L2C,c21]。

在步骤283使用数据序列S扫描n级标签数据库的过程例如:

A、设置扫描起点i,例如另i=1;

B、判断数据序列S中从i位起到S的尾部的数据段的长度是否小于n级标签数据库中最小标签的长度,如果小于,要么数据序列S长度过短,要么扫描应当结束,因此转步骤E;否则,转步骤C;

C、依次使用标签数据库的每一个标签对应的数据段从数据序列S的扫描起点i起,扫描或顺序扫描从i点到数据序列S尾部的数据段;

D、如果没有匹配数据段,将起始点i顺序后移一个数据位,转步骤B;如果有匹配数据段,记录该数据段的标签及该数据段在数据序列S中的位置,将起始点i顺序后移该数据段的长度个数据位,转步骤B;

E、将所有数据段的标签及其在数据序列S中的位置作为一组参数输出。

在基于图2-6所述实施例的另一个实施例中,在步骤281之前增加了一个判断步骤280(图6中未绘出),判断数据序列S是否满足扫描条件,如果满足条件,再转步骤282;否则,直接转步骤216结束。鉴于本实施例其它部分与图2-6 所述实施例相同,此不再赘述。

与图2-6所述实施例对应的基于标签数据生长基因的数据恢复方法的第二实施例流程图参考图2-9。

如果一个数据序列以基因数据序列的形式被存储到存储器中,要获得原始的数据序列们就要对基因数据序列执行相应的还原操作。按照图2-9,首先在步骤2111分解基因数据序列,即分解或解析数据序列S’,就会得到其中的当前数据序列S和原始数据序列全部的生长基因序列。根据生长基因序列中的基因序列提供的信息,确定生长基因序列的级数N,即涉及的标签数据库的级数。为实现基于多级标签数据库的操作,设置计数器i,令i=1。

在步骤2112判断i是否小于等于N,如果小于,说明存在一组或多组未被使用的生长基因及生长参数可以用于恢复数据,因此,从生长基因序列中的未被使用的生长基因中,取出产生的时间最晚或级别最低的一组生长基因及生长参数,转步骤2113继续恢复原始数据序列的操作,否则,说明已经没有未被使用的生长基因及生长参数可以用于恢复数据,或者说明全部恢复操作已经结束,转步骤2114结束操作。

在步骤2113,从i指示级别的标签数据库中按照本组或本级生长基因对应的标签的指示,顺序取出相应的数据段,按照与标签对应的生长参数的数值指示,以及按照生长基因序列记录的顺序,将一个具体标签表达的生长基因的数据段插入到当前数据序列S的相应位置,形成新的当前数据段S,此时的S已经通过该基因的生长得到了某种恢复,然后令i=i+1,转步骤2112进行下一级别的数据恢复操作;

由于最后得到的当前数据序列S就是原始数据序列,因此在步骤2114将最后得到的当前数据序列S作为恢复后的原始数据序列。

下面参考图2-7-1到图2-7-4进行说明。假设图2-6所述实施例的步骤288执行的结果得到的下述数据串表达的S’为:

[S] [L1D,d11]、 [L1C,c11,c12,c13]、[L1B,b11]和[L1A,a11]、[L2D,d21]、[L2C,c21]。

其中,当前数据序列S,参考图2-7-4所示。

按照图2-9进行数据恢复操作时,首先在步骤2111分解基因数据序列,即分解或解析数据序列S’,就会得到[S] 、[L1D,d11]、 [L1C,c11,c12,c13]、[L1B,b11]和[L1A,a11]、[L2D,d21]、[L2C,c21]。得到生长基因序列的级数N=2,设置计数器i=1。

在步骤2112判断得知i小于等于N的条件满足,由于N=2,说明存在二组未被使用的生长基因及生长参数可以用于恢复数据,因此,从生长基因序列中的未被使用的生长基因中,取出产生的时间最晚或级别最低的一组生长基因及生长参数[L2D,d21]、[L2C,c21],转步骤2113继续恢复原始数据序列的操作。

在步骤2113,从i指示级别的二级标签数据库中按照本组或本级生长基因对应的标签L2D、L2C的指示,顺序取出相应的数据段S2D、S2C,按照与标签L2D、L2C对应的生长参数c21、d21的数值指示,以及按照生长基因序列记录的顺序,此处为L2D、L2C,将L2D、L2C表达的生长基因的数据段S2D、S2C插入到当前数据序列S的相应位置,形成新的当前数据段S,参考图2-7-2。此时的S已经通过该基因的生长得到了某种恢复,然后令i=i+1,此时i=2,转步骤2112进行下一级别的数据恢复操作;

在步骤2112判断得知i小于等于N的条件仍满足,由于N=2,i=2,说明存在一组未被使用的生长基因及生长参数可以用于恢复数据,因此,从生长基因序列中的未被使用的生长基因中,取出产生的时间最晚或级别最低的一组生长基因及生长参数[L1D,d11]、 [L1C,c11,c12,c13]、[L1B,b11]和[L1A,a11],转步骤2113继续恢复原始数据序列的操作。

在步骤2113,从i指示级别的一级标签数据库中按照本组或本级生长基因对应的标签L1D、L1C、L1B、L1A的指示,顺序取出相应的数据段S1D、S2C、S1B、S1A,按照与标签L1D、L1C、L1B、L1A对应的生长参数d11、[c11,c12,c13]、b11、a11的数值指示,以及按照生长基因序列记录的顺序,此处为从L1D、L1C、L1B到L1A的顺序,将L1D、L1C、L1B、L1A表达的生长基因的数据段S1D、S1C、S1B、S1A插入到当前数据序列S的相应位置,形成新的当前数据段S,参考图2-7-1。此时的S已经通过该基因的生长得到了全部恢复,然后令i=i+1,此时i=3,转步骤2112判断i小于等于N的条件不满足,因此在步骤2114结束数据恢复操作。

需要说明的是,图2-9所述实施例也可能有多种变形,例如通过步骤2111得到的全部生长基因序列的具体值判断基因是否有效,等等。

实际上,在包含大量数据的数据序列中,存在着大量重复的数据段,如果将这些数据段及其重复规律提取出来作为生长要素和生长参数,即数据序列的生长基因,那么就能够以生长基因为基础压缩以及还原出原来的数据序列。在某些领域,数据序列具有较弱的随机性,但是较强的规律性和一定的构成特征,例如高重复概率的数据段构成特征具有高度的相似性,此时,将预先生成的标签数据库中存在的重复数据段提取出来作为数据序列的生长基因,会使数据序列得到较高的压缩效率。

图3-1是本发明所述基于标签数据生长基因的数据压缩方法实施例流程图。

图3-1所示实施例需要一个标签数据库,该标签数据库的生成是通过对大量特定领域的数据分析预先完成的。通常按照数据应用领域的数据特性,尽可能多地确定多个重复概率较高的数据段,为这些数据段设置彼此不重复的标签标识,将所述标签与所述数据段绑定在一起,存储入标签数据库,即标签与数据段对照关系数据库。利用所述标签数据库中的标签和所述数据段的绑定关系,就可以用标签代替截取的数据段。

一般采用滑动窗口技术生成标签数据库。即,借助于一个指纹函数和一个窗口,来确定重复的数据段。为了更有效地确定所述数据段,可以通过动态调整窗口偏移量来辅助确定。需要指出的是,这个窗口大小的选择,可能与重复数据段的确定原则对应的窗口大小不同,应当适应不同层次数据段划分的需要。

基于所述标签数据库实施图3-1实施例,在步骤310需要预先将一个待压缩的数据集合,例如一个二进制的静态数据段或动态数据流读入到计算机内存储器,经过必要的处理,例如编码处理,形成一个数据序列S。

为做到这一点,首先要选择一个具有至少两个字符子集的字符集,所述两个字符子集具有互不相同的编码。这样选择字符集,是为了利用该字符集的不同子集的编码不同的特点,对被压缩数据序列的数据部分和控制部分进行不同的编码,以便能够准确获得这两部分数据。实际中,在计算机领域使用的任何一个字符集都满足步骤1中所述的具有至少两个字符子集的条件,只要将所述字符集划分为两部分即可。

然后从所述字符集中确定该两个子集。所述子集的确定在于字符编码的需求。由于待压缩的数据序列为二进制数据序列,子集的确定在于要对多少位二进制数据进行编码。例如,如果对5位二进制进行编码,所述子集的容量最少为2

有了这个具有至少两个字符子集的字符集,按照图3-1的步骤310,使用所述字符集中第一字符子集的字符编码规则,对待压缩的二进制数据序列进行编码,将所述二进制数据序列S

接着在步骤311使用数据序列S扫描标签数据库,如果数据序列S中有与数据库的标签对应的数据段,就会被标识出来。因此,经过步骤311就可能得到一组标签数据段及该数据段在数据序列S中的位置。经过步骤311扫描得到的具体内容可以通过步骤312知道。

如果数据序列S中没有与数据库的标签对应的数据段,通常就会得到一个特殊的标识,例如一个特定的字符串或空串,这样有利于步骤312的判断操作。

在步骤312判断是否得到有效的标签数据段,如果得到,在步骤313用所述标签数据段对应的标签及其在数据序列S中的位置作为本次扫描结果参数,记录这些本次扫描结果参数,其中,所述标签为生长基因,标签在数据序列S中的位置为生长参数,然后转步骤314继续后续的处理。如果没有得到标签数据段,说明在当前的数据序列S中已经没有标签数据库的标签对应的数据段,这时转步骤315,生成原始数据序列S的生长基因序列。

在步骤314,在数据序列S中去除所述标签数据段,用剩余数据段组装成新的数据序列S,转步骤311继续下一次的标签数据段的扫描操作。

在步骤315,对于每一次扫描结果得到的各级生长基因及其生长参数,使用所述字符集中第二字符子集的字符编码规则编码每一次扫描结果参数中标签的位置参数,按照产生的时间顺序或级别,将编码后的每一次扫描结果参数组织为原始数据序列的生长基因序列,这样就生成了原始数据序列S的生长基因序列。

最后在步骤316,用当前的数据序列S和原始数据序列的生长基因序列组装成基因数据序列S’,S’就是得到压缩后的结果。

图3-2是本发明所述基于标签数据生长基因的数据压缩方法第二实施例流程图。

与图3-1所述实施例相比,图3-2所述实施例增加了步骤317。在传统意义上,步骤316的结果,在实际应用中只是简单的二进制处理,即得到压缩后的二进制数据序列。而步骤317的意义在于,改变这种简单的处理模式,而采用各种适合的方法,如公知的无损压缩的方法,压缩基因数据序列S’为二进制数据序列,将其作为当前二进制数据序列S

在另一个基于图3-2的实施例中,增加了判断步骤318。由于当前二进制数据序列S

另外,步骤318判断二进制数据序列S

下面是图3-2实施例的步骤317采用S-F编码方法压缩压缩基因数据序列S’为二进制数据序列S

举例:假设数据序列S为:aaannckkkhddanafffndddgghhancckdandgghha;

其长度为40个字符,由a、n、c、d、k、f、g、h共8种字符构成。假设在数据序列S中,每种字符出现的概率为:

a:8,n:6,c:3,d:7,k:4,f:3,g:4,h:5。

首先将各个符号按概率递减顺序排列,然后,再把符号序列分成两部分,使两部分的概率和相等或接近相等。得到:

第一部分,a:8,d:7,n:6;

第二部分,h:5,k:4,g:4,c:3,f:3。

其中,第一部分符号序列概率和为21,编码为0;第二部分符号序列概率和为19,编码为1。然后对两个部分符号序列利用一棵二叉树进行辅助划分,最终得到的符号编码分别为:

a:00,n:011,c:1110,d:010,k:101,f:1111,g:110,h:100。

则数据序列S的编码总位数L等于每种字符编码位数与字符出现次数乘积的和,即:

L=2×8+3×6+4×3+3×7+3×4+4×3+3×4+3×5=118(位)

如果直接用ASCII码,则要用40×8=320位。因此,S-F编码实现了数据压缩。

步骤316执行的结果可以有多种样式,只要能够在其中正确解析出当前的数据序列S和原始数据序列的生长基因序列即可。例如下述数据串表达的S’:

下面参考图3-3-1到图3-3-3继续说明。

图3-3-1到图3-3-3是说明图3-1所述实施例的示意图。

假设标签数据库如下述表3-1所示,它有三个字段,分别是“编号”、“标签”、“数据段”。

图3-3-1所示,经过步骤311的扫描操作,数据序列S中有三个标签数据段被标识出来,即起点为a的数据段SA,起点为b的数据段SB,起点为c的数据段SC。经过步骤313,生成对应的第一次扫描结果如下述表3-2所示。

经过步骤314生成的新的数据序列S参考图3-3-2。经过步骤311继续扫描当前的数据序列S,即图3-3-2所示的数据序列S,有二个标签数据段被标识出来,即起点为d的数据段SD,起点为e的数据段SE。经过步骤313,生成对应的第二次扫描结果如下述表3-3所示。

经过步骤314生成的新的数据序列S参考图3-3-3。经过步骤311继续扫描当前的数据序列S,即图3-3-3所示的数据序列S,没有标签数据段被标识出来,经过步骤312的判断,转步骤315将前二次扫描得到的结果参数组织起来,生成原始数据序列S的生长基因序列,参考下述表3-4。

步骤316执行的结果得到的下述数据串表达的S’可以这样解释:

本次扫描得到当前数据序列S和二次基因序列,其中:

当前数据序列S,是图3-3-3所示的数据序列S。二次基因序列,是[LD,d]和[LE,e];一次基因序列,是[LC,c]、[LB,b]和[LA,a]。

因此,S’就是存储到存储器中的原始数据序列对应的基因数据序列,其内容为:

[S] [LA,a] 、[LB,b]、[LC,c]、[LD,d]、[LE,e]。

因此,S’就是存储到存储器中的原始数据序列对应的基因数据序列,某次的基因序列的基本内容就包括表中所述级别、生长基因,即标签和基因生长参数,即起点。其中的当前数据序列S用所述字符集中第一字符子集的字符编码规则编码,基因生长参数用所述字符集中第二字符子集的字符编码规则编码,当然,第二字符子集的字符编码规则不同于标签的编码规则。

图3-4是图3-1所述实施例步骤311采用的扫描子步骤流程图。

在图3-1、图3-2所述实施例中,步骤311所述使用S扫描标签数据库有很多方法,在本例中采用反向扫描的方式,即用标签数据库的内容与S的内容比较,而实现使用S扫描标签数据库的操作。

按照图3-4,首先在321设置扫描起点i。本例中i=1,即指示从第一个字符开始扫描。i也可以是其它起点,例如一个特别的数据头后面的一位字符的位置。需要说明,在实际应用中,i的不同起点有特别的价值,例如增加提取出来的数据基因的还原原始数据时的生长效率,以及增加提取过程的灵活性和保密性等等。

然后在322,先计算获得i位起到数据序列S的尾部的数据段的长度,以及从标签数据库中获得数据库中长度最小的数据段的长度,接着判断数据序列S中从i位起到S的尾部的数据段的长度是否大于标签数据库中最小标签的长度,如果是,转步骤323进行扫描操作;否则,说明S的长度过短,已经没有提取生长基因的价值,这时就转步骤328结束扫描操作。

在步骤323,用标签数据库的内容引导数据S的分割或扫描。这个过程是:依次从标签数据库中取出每一个标签对应的数据段,使用这些数据段从数据序列S的扫描起点i起,扫描或顺序扫描从i点到数据序列S尾部的数据段。即依次使用这些数据段去匹配从起点i开始的相应长度的数据段,例如用该数据段的指纹或散列值去比较S的相应部分,就可以得知是否在第一数据库中找到了能够用标签替代的数据段。

如果标签数据库中的每一个标签对应的数据段都不能在数据序列S中找到与之相同的数据段,说明在标签数据库中没有找到能够匹配的数据段,此时,将空串作为扫描结果,即用空串作为匹配的数据段,如果在标签数据库中有一个标签对应的数据段能够与从起点i开始的相应长度的数据段匹配,则将该数据段作为扫描结果,即用该数据段作为匹配的数据段。如果有多个匹配数据段,即在标签数据库中有多个标签对应的数据段能够与从起点i开始的相应长度的数据段匹配,则将第一个匹配的数据段或者最长的数据段作为扫描结果,本例中用第一个匹配的数据段作为扫描结果。

步骤323的扫描结果可以通过步骤324获知。步骤324是一个判断步骤,如果判断得知步骤323没有得到匹配数据段,则在步骤325将起点i顺序后移一个数据位,即使i=i+1,然后转步骤322从新的i指示的位置起开始扫描数据序列S剩余的数据位;如果有匹配数据段,在步骤326记录该数据段的标签及该数据段在数据序列S中的位置,然后在步骤327将起点i顺序后移该数据段的长度个数据位,即使i=i+L,L为数据段的长度,然后转步骤322从新的i指示的位置起开始扫描数据序列S剩余的数据位。

步骤328是一个输出步骤,将所有数据段的标签及其在数据序列S中的位置作为参数输出,具体的形式参考表3-2。如果没有扫描到与标签数据库内标签数据段相同的数据段,步骤328就会输出空集或空字符串。

步骤323采用的扫描模式有两种:扫描或顺序扫描。可以采用其中任意一种模式。具体参考图3-5-1到图3-5-3。

扫描模式的方式是,用标签数据库中的第一个标签对应的数据段从i点开始匹配相应长度的数据段,如图3-5-1,从i=1的位置开始匹配操作,如果该数据段匹配不成功,则用标签数据库中的第二个标签对应的数据段从i点开始匹配相应长度的数据段,直到找到匹配的数据段或者标签数据库中的所有标签数据段全部匹配完毕。如果没有找到匹配的数据段,则从图3-5-2所示的下一个数据位开始继续扫描,此时i=2。如果仍没有找到匹配的数据段,则从图3-5-3所示的下一个数据位开始继续扫描,此时i=3。

顺序扫描模式的方式是,用标签数据库中的第一个标签对应的数据段从i点开始匹配相应长度的数据段,如图3-5-1,从i=1的位置开始匹配操作,如果该数据段匹配不成功,则仍然用第一个标签对应的数据段从下一个位置,如图3-5-2所示的下一个数据位开始继续扫描,此时i=2。如果该数据段匹配还不成功,则仍然用第一个标签对应的数据段从下一个位置,如图3-5-3所示的下一个数据位开始继续扫描,此时i=3。以上方式直到匹配成功或者扫描完毕。如果第一个数据段匹配不成功,则用标签数据库中的第二个标签对应的数据段按照图3-5-1到图3-5-3的模式从i点开始匹配相应长度的数据段,直到匹配成功或者扫描完毕。以此类推直到标签数据库的标签对应的数据段全部匹配完毕。

在图3-1、图3-2所述实施例中,采用默认的位置编码需要的二进制位数。但是,当数据序列过长时,可能位置编码的二进制位数不足以完成重复数据段的位置编码;如果数据序列过短,则会浪费位置编码二进制位。因此,在另外的实施例中,在步骤310和步骤311之间还包括一个预处理步骤,该步骤根据数据序列S的长度预先确定位置编码需要的最大二进制位数。例如,如果数据序列S的长度为1M,则位置编码需要的二进制位数最多为3个字节。这样,有利于生成较优化的生长基因及对应的生长参数。

在基于图3-1或图3-2的另外的实施例中,步骤310和步骤311之间增加一个判断子步骤,该子步骤判断数据序列S是否满足扫描条件,如果是,转步骤311进行扫描操作;否则,转步骤315终止扫描输出扫描结果。这里所述条件是两个并列的条件,一个条件是数据序列S的长度小于标签数据库中最小标签的长度,这时没有扫描的意义,数据序列S太短。第二个条件是,经过扫描没有找到匹配标签数据段,这时也没有必要继续扫描。实际中也可以设置其它终止扫描的条件,当扫描中发现某个特定的字符或字符串,等等。在第一种情况下,输出的是一个提示信息,而没有压缩后的基因数据序列。

图3-6是本发明所述基于标签数据生长基因的数据压缩方法第三实施例流程图。

图3-6所示实施例需要一个标签数据库,该标签数据库的生成是通过对大量特定领域的数据分析预先完成的。利用所述标签数据库中的标签和所述数据段的绑定关系,就可以用标签代替截取的数据段。

基于所述标签数据库实施图3-6实施例,在步骤380需要预先将一个待压缩的数据集合,例如一个二进制的静态数据段或动态数据流读入到计算机内存储器,经过必要的处理,例如编码处理,形成一个数据序列S。

为做到这一点,首先要选择一个具有至少两个字符子集的字符集,所述两个字符子集具有互不相同的编码。这样选择字符集,是为了利用该字符集的不同子集的编码不同的特点,对被压缩数据序列的数据部分和控制部分进行不同的编码,以便能够准确获得这两部分数据。实际中,在计算机领域使用的任何一个字符集都满足步骤中所述的具有至少两个字符子集的条件,只要将所述字符集划分为两部分即可。

有了这个具有至少两个字符子集的字符集,按照图3-6的步骤380,使用所述字符集中第一字符子集的字符编码规则,对待压缩的二进制数据序列进行编码,将所述二进制数据序列S

在步骤381,设置标签数据库的初始级数n为1,n的最大值N=3,N为标签数据库的级数,这样就能保证扫描操作以这三个标签数据库为基础。

在步骤382,判断n是否小于或等于N,如果是,在步骤383使用数据序列S扫描n级标签数据库,得到一组标签数据段及该数据段在数据序列S中的位置。如果数据序列S中有与该级标签数据库的标签对应的数据段,就会被标识出来。如果数据序列S中没有与数据库的标签对应的数据段,通常就会得到一个特殊的标识,例如一个特定的字符串或空串,因此,该组标签数据段及该数据段在数据序列S中的位置是真实的数据或者是“空”。

如果步骤384判断得知得到了标签数据段,则在步骤385用所述标签数据段对应的标签及其在数据序列S中的位置作为本级扫描结果参数,将这些本级的扫描结果参数记录下来,其中,所述标签为生长基因,标签在数据序列S中的位置为生长参数然后转步骤386继续下一级标签数据库的扫描;如果没有得到标签数据段,则转步骤387结束生长基因的提取操作;

在步骤386,在数据序列S中,用所述标签数据段的标签代替所述标签数据段,组装成新的数据序列S,令n=n+1,指示以下级标签数据库为基础扫描新的数据序列S,转步骤382继续。

在步骤387,对于每一次扫描结果得到的各级生长基因及其生长参数,使用所述字符集中第二字符子集的字符编码规则编码每一次扫描结果参数中标签的位置参数,按照产生的时间顺序或级别,将编码后的每一次扫描结果参数组织为原始数据序列的生长基因序列,这样就生成了原始数据序列S的生长基因序列。

最后在步骤388,用当前的数据序列S和原始数据序列的生长基因序列组装成基因数据序列S’,S’就是得到压缩后的结果。

步骤388执行的结果可以有多种样式,只要能够在其中正确解析出当前的数据序列S和原始数据序列的生长基因序列即可。例如:

[当前数据序列S][一级基因序列][二级基因序列][三级基因序列]。

图3-7是本发明所述基于标签数据生长基因的数据压缩方法第四实施例流程图。

与图3-6所述实施例相比,图3-7所述实施例增加了步骤389。在传统意义上,对于步骤388的处理结果,在实际应用中只是进行简单的二进制处理,即得到压缩后的二进制数据序列。而步骤389的意义在于,改变这种简单的处理模式,而采用各种适合的方法,如公知的无损压缩的方法,压缩基因数据序列S’为二进制数据序列,将其作为当前二进制数据序列S

在另一个基于图3-7的实施例中,在步骤389之后增加了一个判断步骤390。由于当前二进制数据序列S

以图3-6、图3-7实施例为基础,假设有如下三个标签数据库,表5-1为一级标签数据库,表5-2为二级标签数据库,表5-3为三级标签数据库,其内容如下:

按照图3-6所述实施例,在步骤381设置n=1,N=3。由于在步骤382判断得知n小于N,则在步骤383使用数据序列S扫描1级标签数据库,结果参考图3-8-1,得到了标签数据段S1A、S1B、S1C、S1D及其在数据序列S中的位置,其中S1C出现三次,S1A、S1B、S1C连续,连续两次的S1C和S1D连续。这样,经过步骤384的判断,得知扫描得到了标签数据段,在步骤385,用所述标签数据段S1A、S1B、S1C、S1D对应的标签L1A、L1B、L1C、L1D及其在数据序列S中的位置作为本级扫描结果参数,并记录了这些本次扫描结果参数。在步骤386,在数据序列S中用所述标签数据段的标签L1A、L1B、L1C、L1D代替对应的标签数据段,组装成新的数据序列S,参考图3-8-2,然后令n=n+1,转步骤312继续以下级标签数据库,即2级标签数据库为基础扫描新的数据序列S。

假设连续的S1A、S1B、S1C就是表5-2所示的二级数据库中的S2C,连续的S1C就是表5-2所示的二级数据库中的S2D,这样经过第二次扫描,经过步骤384的判断,得知扫描得到了标签数据段,在步骤385,用所述标签数据段S2C、S2D对应的标签L2C和L2D及其在数据序列S中的位置作为本级扫描结果参数,并记录了这些本次扫描结果参数。在步骤386,在数据序列S中用所述标签数据段的标签L2C、L2D代替对应的标签数据段,组装成新的数据序列S,参考图3-8-3,然后令n=n+1,转步骤312继续以下级标签数据库,即3级标签数据库为基础扫描新的数据序列S。

假设第三次扫描没有得到重复数据段,则要在步骤387,组织每一级扫描结果参数,生成原始数据序列S的生长基因序列,参考表3-6。

此时,新的数据序列S,即当前的数据序列S如图3-8-3所示,由于图3-8-3中的标签已经在表3-6中记载,因此,步骤388所示的当前数据序列S是在图3-8-3基础上去除了L2C、L2D后的数据段,参考图3-8-4。因此,当前数据序列S,是图3-8-4所示的数据序列S。二级基因序列,是[L2D,d21]和[L2C,c21];一次基因序列,是[L1D,d11]、 [L1C,c11,c12,c13]、[L1B,b11]和[L1A,a11]。特别指出,由于图3-8-3的L1D没有被包含在二级标签中,因此,步骤388所示的当前数据序列S包含L1D,参考图3-8-4。在另外的例子中,当前数据序列S也可以不经过去除L2C、L2D的操作,如图3-8-3所示,这样也能实现原始数据序列的恢复操作。

因此,S’就是存储到存储器中的原始数据序列对应的基因数据序列,其内容为:

[S] [L1D,d11]、 [L1C,c11,c12,c13]、[L1B,b11]和[L1A,a11]、[L2D,d21]、[L2C,c21]。

图3-6或图3-7实施例的步骤383使用数据序列S扫描n级标签数据库的过程例如:

A、设置扫描起点i,例如令i=1;

B、判断数据序列S中从i位起到S的尾部的数据段的长度是否小于n级标签数据库中最小标签的长度,如果小于,要么数据序列S长度过短,要么扫描应当结束,因此转步骤E;否则,转步骤C;

C、依次使用标签数据库的每一个标签对应的数据段从数据序列S的扫描起点i起,扫描或顺序扫描从i点到数据序列S尾部的数据段;

D、如果没有匹配数据段,将起始点i顺序后移一个数据位,转步骤B;如果有匹配数据段,记录该数据段的标签及该数据段在数据序列S中的位置,将起始点i顺序后移该数据段的长度个数据位,转步骤B;

E、将所有数据段的标签及其在数据序列S中的位置作为一组参数输出。

在基于图3-6或图3-7所述实施例的另一个实施例中,在步骤380和步骤381之间增加了一个判断步骤3801(图6中未绘出),判断数据序列S是否满足扫描条件,如果满足条件,再转步骤382;否则,直接转步骤387结束,或者直接结束。鉴于本实施例其它部分与图3-6或图3-7 所述实施例相同,此不再赘述。

去获取专利,查看全文>

相似文献

  • 专利
  • 中文文献
  • 外文文献
获取专利

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号