差分数据生成系统、数据更新系统以及差分数据生成方法转让专利
申请号 : CN201480080799.8
文献号 : CN106663050B
文献日 : 2018-04-13
发明人 : 御厨诚
申请人 : 三菱电机株式会社
摘要 :
本发明的目的在于提供一种能够提高差分数据的数据量削减效果的技术。比特移位部(4a)将旧数据和新数据中的一方数据向其比特串的正向及逆向分别移动0，1，2，…，n比特，从而生成多个数据。复制比特串提取部(4b)基于多个数据和未被移位的另一方数据，提取复制比特串信息。追加比特串提取部(4c)从新数据提取去除复制比特串后的追加比特串信息。差分数据生成部(6)基于复制比特串信息和追加比特串信息，生成差分数据。
权利要求 :
1.一种差分数据生成系统，生成用于从旧数据生成与新数据相同的数据的差分数据，其特征在于，包括：比特移位部，该比特移位部将所述旧数据和所述新数据中的一方数据向其比特串的正向及逆向分别移动0，1，2，…，n比特，从而并行地生成多个数据，n是自然数；
复制比特串提取部，该复制比特串提取部基于由所述比特移位部生成的所述多个数据、以及没有被所述比特移位部移位的另一方数据，提取所述旧数据和所述新数据中共通的比特串的信息作为复制比特串的信息；
追加比特串提取部，该追加比特串提取部提取所述新数据中所述复制比特串以外的比特串的信息作为追加比特串的信息；以及差分数据生成部，该差分数据生成部基于所述复制比特串的信息和所述追加比特串的信息，生成所述差分数据。
2.如权利要求1所述的差分数据生成系统，其特征在于，
所述复制比特串提取部包括：
中间复制比特串提取部，该中间复制比特串提取部对所述比特移位部所生成的所述多个数据中的每一个数据，提取该一个数据和没有被所述比特移位部移位的所述另一方数据中共通的比特串的信息，作为中间复制比特串的信息；以及最终复制比特串提取部，该最终复制比特串提取部基于所述中间复制比特串提取部所提取到的多个所述中间复制比特串的信息，提取包含多个所述中间复制比特串中彼此不重复的中间复制比特串和将多个所述中间复制比特串中互相重复的中间复制比特串彼此相结合而得到的比特串中的至少一个的比特串的信息，作为所述复制比特串的信息。
3.如权利要求2所述的差分数据生成系统，其特征在于，
所述n为7，
所述中间复制比特串提取部进行下述动作：
对所述比特移位部所生成的所述多个数据中的每一个数据，提取该一个数据和没有被所述比特移位部移位的所述另一方数据中共通的字节串，按所述一个数据的比特串的所述逆向的顺序，判定紧挨着所述一个数据中所提取出的所述字节串之前的一个字节所包含的比特、与紧挨着所述另一方数据中所提取出的所述字节串之前的一个字节所包含的比特是否一致，从而求取最后一致的所述一个数据的比特的第1地址和所述另一方数据的比特的第2地址，按所述一个数据的比特串的所述正向的顺序，判定紧挨着所述一个数据中所提取出的所述字节串之后的一个字节所包含的比特、与紧挨着所述另一方数据中所提取出的所述字节串之后的一个字节所包含的比特是否一致，从而求取最后一致的所述一个数据的比特的第3地址和所述另一方数据的比特的第4地址，将所述第1地址和所述第3地址中的至少任一个地址校正为所述比特移位部进行移位前的地址，基于所述第2地址和所述第4地址、以及经校正的所述第1地址和所述第3地址中的至少任一个地址，生成所述中间复制比特串的信息。
4.如权利要求1至3的任一项所述的差分数据生成系统，其特征在于，由所述差分数据生成部生成的所述差分数据是下述数据：
按所述新数据所包含的所述复制比特串和所述追加比特串在该新数据中的地址顺序，对表示所述旧数据包含的所述复制比特串的地址和长度的信息、以及表示所述新数据包含的所述追加比特串和所述追加比特串的长度的信息进行排列而得到的数据。
5.一种数据更新系统，其特征在于，
基于由权利要求1至4的任一项所述的差分数据生成系统生成的所述差分数据、以及所述旧数据，生成与所述新数据相同的所述数据。
6.一种差分数据生成方法，生成用于从旧数据生成与新数据相同的数据的差分数据，其特征在于，通过将所述旧数据和所述新数据中的一方数据向其比特串的正向及逆向分别移动0，
1，2，…，n比特，从而并行地生成多个数据，n是自然数，
基于所生成的所述多个数据、以及未被移位的另一方数据，提取所述旧数据与所述新数据中共通的比特串的信息作为复制比特串的信息，提取所述新数据中所述复制比特串以外的比特串的信息作为追加比特串的信息，基于所述复制比特串的信息和所述追加比特串的信息，生成所述差分数据。
说明书 :
差分数据生成系统、数据更新系统以及差分数据生成方法
技术领域
[0001] 本发明涉及生成差分数据的差分数据生成系统及其方法、以及使用该差分数据的数据更新系统，该差分数据用于从旧数据生成与新数据相同的数据。
背景技术
[0002] 关于用于从旧数据生成与新数据相同的数据的差分数据的提取(生成)，提出了各种技术。
[0003] 例如，在专利文献1所示的技术中，以字节为单位对旧数据和新数据进行比较，将两者相一致的字节串提取作为复制数据(Move data：移动数据)，并将仅存在于新数据的字节串提取作为追加数据。于是生成包含表示提取到的复制数据的复制命令(移动命令)和表示提取到的追加数据的追加命令的差分数据。
[0004] 复制命令表示旧数据中复制数据的存储位置和大小，而不包含复制数据本身。通常，由于复制数据的存储位置及大小的数据量比复制数据本身要小，因此，这种复制数据越多，差分数据的数据量削减效果越好。
[0005] 例如，将在32字节的旧数据A的起始处插入1字节的插入数据B后得到的数据设为新数据C。即，33字节的数据{B，A}成为新数据C。在这种情况下，利用专利文献1所示的技术提取出的差分数据包含下述追加命令及复制命令。
[0006] 追加命令(1字节)：由表示插入数据B的1字节的追加数据构成。其中，取定界符(0x0F)以外的值。另外，(0x**)表示十六进制记载。
[0007] 复制命令(2字节)：由表示是复制命令这一内容的1字节的定界符(0x0F)和表示复制数据的大小(32字节)的1字节的数据(0x20)构成。这里，由于旧数据A中复制数据的起始地址为0，因此不需要地址字段。
[0008] 其结果使得，用于从旧数据A生成与新数据C相同的数据的差分数据不是33字节的数据而成为3字节的数据，因此差分数据的数据量得以减小。在差分数据中，复制数据越是增加，追加数据越是减少，则这种差分数据的数据量削减效果就越是显著。
[0009] 现有技术文献
[0010] 专利文献
[0011] 专利文献1：日本专利特开2004-152136号公报
发明内容
[0012] 发明所要解决的技术问题
[0013] 在数据以字节为单位来表示，新数据通过改变旧数据的字节单位(例如插入、删除等)来生成的情况下，如专利文献1所示的技术那样，能够通过以字节为单位提取旧数据和新数据的差分的技术来进行应对。但是，从数据削减的观点出发，也提出了用所需最低限度的比特数来表示数据，通过改变旧数据的比特单位来生成新数据的技术。
[0014] 在所提出的该技术中，例如，在1字节的插入数据中仅1比特有效的情况下，向旧数据插入1比特的插入数据b后得到的数据成为新数据。可考虑下述情况作为具体例，即：旧数据是32字节即256比特的比特串数据A，新数据D是在比特串数据A的起始插入了1比特的插入数据b后得到的257比特的比特串数据D。
[0015] 比特串数据A(旧数据A)、比特串数据D(新数据D)在存储介质中分别从起始比特开始依次以字节为单位按下述方式存储。
[0016] A：a1、a2、…、a32
[0017] D：d1、d2、…、d32、d33
[0018] 新数据D中相当于旧数据A的比特串因插入数据b的插入而与旧数据A偏离了1比特，因此，di≠ai(i＝1、2、…、32)。
[0019] 该情况下，若如专利文献1的技术那样以字节为单位提取以字节为单位存储的旧数据A与新数据D的差分，则由于di≠ai(i＝1、2、…、32)，因此复制数据不会被提取出，而认为提取到的是由d1～d33构成的33字节的追加数据。其结果是，用于从旧数据A生成与新数据D相同的数据的差分数据成为33字节的数据，差分数据的数据量削减效果下降。
[0020] 如上所述，在新数据是通过向旧数据插入比特单位的插入数据而得到的数据的情况下，在专利文献1所示的技术中，由于在差分数据中，复制数据减少且追加数据增加，因此存在差分数据的数据量削减效果下降的问题。
[0021] 因此，本发明是为了解决上述问题点而完成的，其目的在于提供一种能够提高差分数据的数据量削减效果的技术。
[0022] 解决技术问题的技术方案
[0023] 本发明所涉及的差分数据生成系统生成用于从旧数据生成与新数据相同的数据的差分数据，该差分数据生成系统包括：比特移位部，该比特移位部将旧数据和新数据中的一方数据向其比特串的正向及逆向分别移动0，1，2，…，n比特，从而生成多个数据；复制比特串提取部，该复制比特串提取部基于由比特移位部生成的多个数据以及没有被比特移位部移位的另一方数据，提取旧数据和新数据中共通的比特串的信息作为复制比特串的信息；追加比特串提取部，该追加比特串提取部提取新数据中复制比特串以外的比特串的信息作为追加比特串的信息；以及差分数据生成部，该差分数据生成部基于复制比特串的信息和追加比特串的信息，生成差分数据。
[0024] 本发明所涉及的差分数据生成方法生成用于从旧数据生成与新数据相同的数据的差分数据，该差分数据生成方法中：通过将旧数据和新数据中的一方数据向其比特串的正向及逆向分别移动0，1，2，…，n比特，从而生成多个数据，基于所生成的多个数据以及未被移位的另一方数据，提取旧数据与新数据中共通的比特串的信息作为复制比特串的信息，提取新数据中复制比特串以外的比特串的信息作为追加比特串的信息，基于复制比特串的信息和追加比特串的信息来生成差分数据。
[0025] 发明效果
[0026] 根据本发明，基于旧数据和新数据中在0，1，2，…，n比特的范围内向比特串的正向和逆向进行了移位的一方数据、以及没有被移位的另一方数据，求取复制比特串的信息和追加比特串的信息。因此，即使旧数据与新数据之间产生了比特单位的偏差，也能够使差分数据中的复制比特串增加，能够减少追加比特串。其结果，能够提高差分数据的数据量削减效果。
[0027] 本发明的目的、特征、方式及优点可通过下述详细说明及附图来得以更为明确。
附图说明
[0028] 图1是表示实施方式1所涉及的差分数据生成装置及数据更新装置的框图。
[0029] 图2是表示实施方式1所涉及的差分数据生成装置的构成例的框图。
[0030] 图3是表示实施方式1所涉及的数据更新装置的构成例的框图。
[0031] 图4是表示实施方式1所涉及的信息处理装置的构成例的框图。
[0032] 图5是表示实施方式1所涉及的旧数据和新数据的构成例的图。
[0033] 图6是表示实施方式1所涉及的旧数据和新数据的关系的图。
[0034] 图7是表示实施方式1所涉及的从旧数据向新数据进行变更的变更例的图。
[0035] 图8是表示实施方式1所涉及的从旧数据向新数据进行变更的变更例的图。
[0036] 图9是表示实施方式1所涉及的从旧数据向新数据进行变更的变更例的图。
[0037] 图10是表示实施方式1所涉及的从旧数据向新数据进行变更的变更例的图。
[0038] 图11是表示实施方式1所涉及的从旧数据向新数据进行变更的变更例的图。
[0039] 图12是表示实施方式1所涉及的旧数据和新数据的构成例的图。
[0040] 图13是表示实施方式1所涉及的旧数据和新数据的构成例的图。
[0041] 图14是表示实施方式1所涉及的差分数据生成装置的处理的一个示例的图。
[0042] 图15是表示实施方式1所涉及的差分提取部及差分数据生成部的构成例的框图。
[0043] 图16是表示实施方式1所涉及的差分提取部的动作的一个示例的流程图。
[0044] 图17是表示实施方式1所涉及的中间复制比特串信息的构成例的图。
[0045] 图18是表示实施方式1所涉及的复制比特串信息的构成例的图。
[0046] 图19是表示实施方式1所涉及的追加比特串信息的构成例的图。
[0047] 图20是表示实施方式1所涉及的比特移位处理的一个示例的流程图。
[0048] 图21是表示实施方式1所涉及的中间复制比特串信息的提取处理的一个示例的流程图。
[0049] 图22是表示实施方式1所涉及的字节差分数据的构成例的图。
[0050] 图23是表示实施方式1所涉及的追加命令的构成例的图。
[0051] 图24是表示实施方式1所涉及的复制命令的构成例的图。
[0052] 图25是表示实施方式1所涉及的结束命令的构成例的图。
[0053] 图26是表示实施方式1所涉及的复制比特串信息的提取处理的一个示例的流程图。
[0054] 图27是表示实施方式1所涉及的结合复制范围的一个示例的图。
[0055] 图28是表示实施方式1所涉及的追加比特串信息的提取处理的一个示例的流程图。
[0056] 图29是表示实施方式1所涉及的追加比特串信息的提取处理的一个示例的图。
[0057] 图30是表示实施方式1所涉及的差分数据的构成例的图。
[0058] 图31是表示实施方式1所涉及的追加比特命令的构成例的图。
[0059] 图32是表示实施方式1所涉及的复制比特命令的构成例的图。
[0060] 图33是表示实施方式1所涉及的结束命令的构成例的图。
[0061] 图34是表示实施方式1所涉及的差分数据生成部的动作的一个示例的流程图。
[0062] 图35是表示实施方式1所涉及的合并信息的构成例的图。
[0063] 图36是表示实施方式1所涉及的数据更新动作的一个示例的流程图。
[0064] 图37是表示实施方式1所涉及的数据更新部的处理的一个示例的图。
[0065] 图38是表示实施方式1所涉及的数据更新部的处理的一个示例的图。
[0066] 图39是表示实施方式2所涉及的差分提取部及差分数据生成部的构成例的框图。
[0067] 图40是表示实施方式2所涉及的差分数据生成装置的处理的一个示例的图。
具体实施方式
[0068] <实施方式1>
[0069] 在下述说明中，以下述情况为例进行说明，即：将本发明所涉及的差分数据生成系统应用于差分数据生成装置单体，将本发明所涉及的数据更新系统应用于数据更新装置单体。
[0070] 图1是表示本发明的实施方式1所涉及的差分数据生成装置1的主要结构以及本发明的实施方式1的数据更新装置11的框图。差分数据生成装置1生成差分数据，该差分数据用于从旧数据生成与新数据相同的数据。旧数据和新数据是比特串数据，新数据是以比特为单位变更(例如插入、删除等)旧数据后得到的数据。
[0071] 图1的差分数据生成装置1包括比特移位部4a、复制比特串提取部4b、追加比特串提取部4c、以及作为差分数据生成部的差分数据生成部6。
[0072] 比特移位部4a将旧数据和新数据中的一方向其比特串的正向及逆向分别移动0，1，2，…，n(n：自然数)比特而生成多个数据。
[0073] 这里，比特串的正向例如采用数据的比特流的方向，或者从被移位的数据的最上位比特到最下位比特的方向等。比特串的逆向指的是与比特串的正向相反的方向。
[0074] 本实施方式1中，上述n为7，被移位的一方的数据为新数据。即，比特移位部4a将新数据向其比特串的正向及逆向分别移位0，1，2，…，7比特，从而生成多个数据(这里为15个数据)。
[0075] 复制比特串提取部4b基于比特移位部4a生成的多个数据、以及没有被比特移位部4a移位的另一方的数据，提取出旧数据和新数据中共通的比特串的信息作为复制比特串信息(复制比特串的信息)。本实施方式1中，由于一方的数据为新数据，因此这里所说的另一方的数据为旧数据。
[0076] 追加比特串提取部4c提取新数据中除复制比特串以外的比特串的信息来作为追加比特串信息(追加比特串的信息)。
[0077] 差分数据生成部6基于复制比特串信息和追加比特串信息，生成(制作)差分数据。
[0078] 图1的数据更新装置11从差分数据生成装置1获取差分数据生成装置1所生成的差分数据。接着，数据更新装置11基于该差分数据和旧数据，生成与新数据相同的数据。
[0079] <差分数据生成装置>
[0080] 这里，不仅对差分数据生成装置1的主要结构要素进行说明，还对附加的结构要素进行说明。
[0081] 图2是表示本实施方式1所涉及的差分数据生成装置1的主要的构成以及附加的构成例的框图。图2的差分数据生成装置1包括数据输入部2、数据存储部3、差分提取部4、中间数据存储部5、差分数据生成部6、差分数据存储部7、差分数据输出部8。
[0082] 数据输入部2输入有例如由未图示的数据生成装置等外部生成的旧数据和新数据、或者例如在未图示的半导体存储器、数字通用光盘(DVD)等存储介质所存储的旧数据和新数据。
[0083] 数据存储部3存储输入到数据输入部2的旧数据和新数据。
[0084] 差分提取部4包括图1的比特移位部4a、复制比特串提取部4b以及追加比特串提取部4c。因此，差分提取部4对新数据进行移位，或者对复制比特串信息进行提取，或者对追加比特串信息进行提取。这里，差分提取部4从数据存储部3所存储的旧数据和新数据中提取复制比特串信息和追加比特串信息。
[0085] 中间数据存储部5存储提取复制比特串信息的中途阶段的结果。这里，中途阶段的结果相当于后述的中间复制比特串信息(中间复制比特串的信息)。
[0086] 差分数据生成部6与图1的差分数据生成部6相同，基于差分提取部4的提取结果(复制比特串信息和追加比特串信息)生成差分数据。
[0087] 差分数据存储部7存储差分数据生成部6所生成的差分数据。
[0088] 差分数据输出部8将差分数据存储部7所存储的差分数据通过存储于未图示的半导体存储器、DVD等存储介质的方式提供给图3的数据更新装置11或图4的信息处理装置21，或者经由未图示的通信网提供给图3的数据更新装置11或图4的信息处理装置21。
[0089] 另外，由例如未图示的硬盘驱动器(HDD)、半导体存储器等存储装置构成数据存储部3、中间数据存储部5及差分数据存储部7。差分提取部4及差分数据生成部6例如通过差分数据生成装置1的未图示的一个或多个中央处理器(CPU)执行未图示的内部存储器等存储装置中所存储的程序，从而作为该CPU的功能来实现。
[0090] <数据更新装置>
[0091] 图3是表示本实施方式1所涉及的数据更新装置11的构成例的框图。图3的数据更新装置11包括差分数据输入部12、差分数据存储部13、数据存储部14、数据更新部15。
[0092] 差分数据输入部12输入有通过差分数据生成装置1存储于存储介质的差分数据，或者从差分数据生成装置1通过通信网向差分数据输入部12输入差分数据。另外，也可从外部向差分数据输入部12输入旧数据。
[0093] 差分数据存储部13存储输入到差分数据输入部12的差分数据。
[0094] 数据存储部14预先存储旧数据。另外，在旧数据被输入到差分数据输入部12的情况下，数据存储部14也存储该旧数据。
[0095] 数据更新部15基于存储于数据存储部14的旧数据、以及存储于差分数据存储部13的差分数据，生成与新数据相同的数据。
[0096] 新数据存储于数据存储部14。新数据可以通过半导体存储器、DVD等存储介质或通信网输出到外部。
[0097] 另外，由例如未图示的HDD、半导体存储器等存储装置构成差分数据存储部13和数据存储部14。数据更新部15例如通过数据更新装置11的未图示的CPU执行未图示的内部存储器等存储装置中所存储的程序，从而作为该CPU的功能来实现。
[0098] <信息处理装置>
[0099] 图4是表示本实施方式1所涉及的信息处理装置21的构成例的框图。图4的信息处理装置21包括差分数据输入部22、差分数据存储部23、数据存储部24、数据更新部25、位置检测部26、操作输入部27、信息处理部28、显示部29。该信息处理装置21的内部具备与图3的数据更新装置11的结构(差分数据输入部12、差分数据存储部13、数据存储部14、数据更新部15)相同的结构，使用通过该结构获得的新数据来进行各种信息处理。
[0100] 数据存储部24存储旧的地图信息(旧数据)。数据存储部24存储通过上述更新而得到的新的地图信息(新数据)。
[0101] 位置检测部26检测搭载有信息处理装置21的移动体、通信终端(例如移动电话、智能手机、以及平板电脑等移动终端)的位置。位置检测部26例如由接收来自GPS(Global Positioning System：全球定位系统)卫星的GPS信号的GPS接收机等构成。
[0102] 操作输入部27从使用者等接受对信息处理装置21的各种操作，例如目的地的指定操作等。
[0103] 信息处理部28根据利用操作输入部27接受到的使用者的操作，基于位置检测部26检测到的位置，从数据存储部24获取所需的地图信息，并将该地图信息表示的地图、以及位置检测部26检测到的位置显示到显示部29。此外，信息处理部28还进行从当前地(位置检测部26检测出的位置)到目的地的路线的搜索、以及路线引导、其他的导航处理。
[0104] 地图信息包含有使用表示交叉点的节点和表示连接交叉点间的道路的链路来表示道路网的信息、以及表示地形的形状的信息。节点、链路的数量因地域的不同而不同，为识别这些而附加的识别编号的最大值因地域的不同而不同。并且，道路形状、地形使用形状的变化量来表示，根据道路、地形的特性的不同，形状变化量存在偏差。因此，地图信息中，为表示各要素而所需的最小限度的字段长度的偏差较大，若以字节单位或字单位的长度的字段来表示各要素，则数据大小会增大到所需以上。因此，作为削减地图信息的数据大小的方式，优选采用下述方式，即：将表示各要素的字段设为比特单位的可变长度，字段长度能够变更为所需最低限度的长度。
[0105] 本实施方式1所涉及的差分数据生成装置1中，对于这种地图信息等能以比特为单位进行变更的数据，能够抑制上述差分数据的大小。
[0106] <旧数据和新数据>
[0107] 地图信息等所适用的旧数据和新数据设为由排列多个比特而成的比特串构成的数据，即比特串数据。比特串的各比特使用比特地址来确定。此处，比特地址表示一个比特位于从比特串数据起始的比特起的第几个，从起始的比特起依次附加0、1、2、…的编号。
[0108] 图5是表示本实施方式1所涉及的旧数据和新数据的构成例的图。
[0109] 图5所示的旧数据的比特串(旧比特串BS0)中，附加有0或1的值的比特如下所述从起始(最上位比特)开始向末尾(最下位比特)依次排列。
[0110] e(0),e(1),e(2),…,e(lngBS0-1)
[0111] e(p)：比特地址为p的比特(p＝0,1,2,…,lngBS0-1)
[0112] lngBS0：旧比特串BS0的比特串长度
[0113] 图5所示的新数据的比特串(新比特串BS1)是对旧比特串BS0进行了以比特为单位的数据的删除、插入、替换、追加等变更后得到的比特串。该新比特串BS1中，附加有0或1的值的比特也如下所述从起始(最上位比特)开始向末尾(最下位比特)依次排列。
[0114] a(0),a(1),a(2),…,a(lngBS1-1)
[0115] a(p)：比特地址为p的比特(p＝0,1,2,…,lngBS1-1)
[0116] lngBS1：新比特串BS1的比特串长度
[0117] 图6是表示实施方式1所涉及的旧数据和新数据的关系的图。
[0118] 新比特串BS1包含有与旧比特串BS0共通的部分比特串(以下记为“复制比特串”)E(i)、以及因变更而新生成的不与旧比特串BS0共通的部分比特串(以下记为“追加比特串”)A(i)。新比特串BS1例如可表示为下述那样的复制比特串E(i)和追加比特串A(i)的排列。
[0119] A(0),E(0),A(1),E(1),…,A(numE-1),E(numE-1),A(numE)
[0120] A(i)：因变更而新生成的追加比特串(i＝0,1,…,numE)
[0121] 另外，A(i)的比特长度可以为0。
[0122] E(i)：新比特串BS1、旧比特串BS0中共通的复制比特串(i＝0,1,…,numE-1)[0123] numE：复制比特串的个数
[0124] 各复制比特串E(i)的各比特的排列如下所述。下述说明中，记载有旧比特串BS0中复制比特串E(i)的起始的比特地址adrE(i)。而新比特串BS1中复制比特串E(i)的起始的比特地址会在之后进行说明。
[0125] e(adrE(i)),e(adrE(i)+1),e(adrE(i)+2),…,e(adrE(i)+lngE(i)-1)[0126] e(p)：旧比特串BS0中比特地址为p的比特
[0127] (adrE(i)≦p≦adrE(i)+lngE(i)-1)
[0128] adrE(i)：旧比特串BS0中复制比特串E(i)的起始的比特地址
[0129] lngE(i)：复制比特串E(i)的比特串长度(＞0)
[0130] 各追加比特串A(i)的各比特的排列如下所述。另外，复制比特串E(i)存在于旧比特串BS0和新比特串BS1中，而追加比特串A(i)仅存在于新比特串BS1。
[0131] a(adrA(i)),a(adrA(i)+1),a(adrA(i)+2),…,a(adrA(i)+lngA(i)-1)[0132] a(p)：新比特串BS1中比特地址为p的比特
[0133] (adrA(i)≦p≦adrA(i)+lngA(i)-1)
[0134] adrA(i)：新比特串BS1中追加比特串A(i)的起始的比特地址
[0135] lngA(i)：追加比特串A(i)的比特串长度(≧0)
[0136] 若边复制了旧比特串BS0(旧数据)的复制比特串E(i)，边追加了追加比特串A(i)，则可得到新比特串BS1(新数据)。鉴于此，差分数据生成为包含有与复制比特串E(i)和追加比特串A(i)相关的信息。
[0137] 另外，作为从旧数据到新数据的变更，设想是删除、插入、替换及追加中的至少一种。图7到图11示出这种变更的示例。
[0138] 图7是表示删除了位于旧比特串BS0的复制比特串E(i)、E(i+1)间的部分比特串X1的示例的图。其中，将新比特串BS1中的追加比特串A(i+1)的比特长度设为0。
[0139] 图8是表示向旧比特串BS0的复制比特串E(i)、E(i+1)间追加了追加比特串A(i+1)的示例的图。
[0140] 图9是表示将位于旧比特串BS0的复制比特串E(i)、E(i+1)间的部分比特串X2替换为追加比特串A(i+1)的示例的图。
[0141] 图10是表示将包含旧比特串BS0的末尾的部分比特串X3替换为追加比特串A(numE)的示例的图。
[0142] 图11是表示在旧比特串BS0的末尾追加了追加比特串A(numE)的示例的图。
[0143] 若进行上述那样的变更，则在大多数情况下，复制比特串E(i)的新比特串BS1的比特地址与旧比特串BS0的比特地址相比会发生偏移。复制比特串E(i)的起始的比特地址在旧比特串BS0中为上述的比特地址adrE(i)，而在新比特串BS1中则成为下式(1)所示的比特地址adr1E(i)。
[0144] [数学式1]
[0145]
[0146] 图6示出新比特串BS1中复制比特串E(2)的起始的比特地址adr1E(2)作为比特地址adr1E(i)的一个示例。
[0147] ＜比特串数据的文件＞
[0148] 旧比特串BS0和新比特串BS1例如作为文件F0和文件F1分别存储于数据存储部3。
[0149] 图12是表示旧比特串BS0和新比特串BS1作为文件F0和文件F1被存储的示例的图。
[0150] 在文件F0的起始处，表示旧比特串BS0的比特串的长度的比特串长度lngBS0作为32比特的非负整数被存储，紧接其后，将对应于旧比特串BS0的数据D0存储为矩阵状。旧比特串BS0从起始的比特开始依次将每8比特作为bylngD0(＝lngBS0/8，余数进位)字节的数据进行存储。另外，在最后的1字节的剩余的比特中存储0。
[0151] 与上述同样，新比特串BS1也作为文件F1被存储。即，新比特串BS1的比特串长度lngBS1作为32比特的非负整数被存储，紧接其后，将对应于新比特串BS1的数据D1存储为矩阵状。新比特串BS1从起始的比特开始依次将每8比特作为bylngD1(＝lngBS1/8，余数进位)字节的数据进行存储。另外，在最后的1字节的剩余的比特中存储0。
[0152] 数据D0、D1的各字节使用偏移量(offset)来确定。此处，偏移量表示所关注的字节位于从数据D0或数据D1的起始的字节起的第几个。偏移量例如从起始的字节开始依次附加0，1，2，…的编号。
[0153] 数据D0、D1的各字节的各比特使用比特编号来确定。此处，比特编号表示所关注的比特位于构成一个字节的8个比特中的第几个。比特编号例如从最上位到最下位的比特(朝向比特串的正向)依次附加7，6，5，4，3，2，1，0的编号。
[0154] 图13是表示数据D0、D1中一个复制比特串E(i)(图6)的一个示例的图。图13中标注有沙地阴影的部分对应于复制比特串，标注有斜线阴影的部分对应于追加比特串。
[0155] 如上所述，复制比特串E(i)在旧比特串BS0中所占的比特地址为adrE(i)～adrE(i)+lngE(i)-1，因此旧比特串BS0中复制比特串E(i)的起始和末尾的比特的偏移量及比特编号如下所述。另外，在下述说明中，“/”表示计算除法运算的商的运算，“％”表示计算除法运算的余数的运算。
[0156] 复制比特串E(i)的起始比特的偏移量：ofsEs(i)＝adrE(i)/8
[0157] 复制比特串E(i)的起始比特的比特编号：bitnEs(i)＝7-adrE(i)％8
[0158] 复制比特串E(i)的末尾比特的偏移量：ofsEe(i)＝(adrE(i)+lngE(i)-1)/8[0159] 复制比特串E(i)的末尾比特的比特编号：bitnEe(i)＝7-(adrE(i)+lngE(i)-1)％8
[0160] 如上所述，复制比特串E(i)在新比特串BS1中所占的比特地址为adr1E(i)～adr1E(i)+lngE(i)-1，因此新比特串BS1中复制比特串E(i)的起始和末尾的比特的偏移量及比特编号如下所述。
[0161] 复制比特串E(i)的起始比特的偏移量：ofsAs(i)＝adr1E(i)/8
[0162] 复制比特串E(i)的起始比特的比特编号：bitnAs(i)＝7-adr1E(i)％8[0163] 复制比特串E(i)的末尾比特的偏移量：ofsAe(i)＝(adr1E(i)+lngE(i)-1)/8[0164] 复制比特串E(i)的末尾比特的比特编号：bitnAe(i)＝7-(adr1E(i)+lngE(i)-1)％8
[0165] 数据D1所包含的复制比特串E(i)的比特地址与数据D0所包含的复制比特串E(i)的比特地址相比，若除去偏移量的不同，则仅相差下述S(i)比特。
[0166] S(i)＝bitnAs(i)-bitnEs(i)
[0167] 在S(i)＞0的情况下，意味着新比特串BS1的复制比特串E(i)与旧比特串BS0的复制比特串E(i)相比，更向新比特串BS1的末尾(比特串的正向)偏移。在S(i)＜0的情况下，意味着新比特串BS1的复制比特串E(i)与旧比特串BS0的复制比特串E(i)相比，更向新比特串BS1的起始(比特串的逆向)偏移。在S(i)＝0的情况下，意味着没有偏移。
[0168] 此外，由于0≦bitnAs(i)＜8、0≦bitnEs(i)＜8，因此，0≦|S(i)|＜8。即，若忽略偏移量的不同，则数据D1中复制比特串E(i)的比特地址与数据D0中复制比特串E(i)的比特地址相比，要么不存在比特单位的偏移，要么仅向末尾方向(比特串的正向)偏移1～7比特，要么仅向起始方向(比特串的逆向)偏移1～7比特。
[0169] 另外，在图13的示例中，S(i)＝2，即，新比特串BS1的复制比特串E(i)与旧比特串BS0的复制比特串E(i)相比，向新比特串BS1的末尾(比特串的正向)偏移2比特。
[0170] 在S(i)＝0的情况、或者相同值连续等特殊的情况下，数据D0中偏移量范围为ofsEs(i)～ofsEe(i)的字节串与数据D1中偏移量范围为ofsAs(i)～ofsAe(i)的字节串一致。但是，通常情况下，由于存在上述那样的比特单位的偏移，因此，这些字节串在大多数情况下是不一致的。
[0171] 无论是怎样的情况，在现有技术中，直接在数据D0的复制比特串E(i)与数据D1的复制比特串E(i)以比特为单位产生了偏移的状态下求取字节单位的差分。因此，无法提取偏移量范围为ofsEs(i)～ofsEe(i)内的复制比特串E(i)，在差分数据中，复制比特串减少，追加比特串增加的情况较多。从而导致存在下述问题，即：差分数据的数据量削减效果下降。
[0172] 与此相对，根据本实施方式1所涉及的差分数据生成装置1，如通过以下说明可更为清楚了解的那样，在差分数据中，能够使复制比特串增加，并且能够使追加比特串减少，因此，能够提高差分数据的数据量削减效果。
[0173] <复制比特串及追加比特串的提取的概要>
[0174] 图14是表示利用差分数据生成装置1来提取图6的一个复制比特串E(i)的处理的一个示例的图。数据D1_s是将数据D1的各比特向比特串的正向移动-S(i)(＝-2)比特后得到的数据，即，是向比特串的逆向移动2比特后的数据。另外，虽然数据D1所应该移动的适当的移位量(此处为-S(i))是未知数，但关于此的准备工作将在后文中进行详细说明，此处，将适当的移位量设为已知来进行说明。
[0175] 如图14所示那样，通过该移动，数据D0中偏移量范围为ofsEs(i)～ofsEe(i)的字节串与数据D1_s中偏移量范围为ofsAs(i)～ofsAe(i)的字节串之间的偏移得以消除。
[0176] 若与现有方法同样地以字节为单位来比较数据D0与已消除了比特单位的偏移的数据D1_s并求取差分，则数据D0中偏移量范围为ofsEs(i)+1～ofsEe(i)-1的字节串至少被提取作为复制比特串。在下述说明中，将形成该偏移量范围的字节串的比特串设为比特串MI。
[0177] 如图14所示那样，数据D1(新数据)中，偏移量为ofsAs(i)的一个字节串、即包含复制比特串E(i)起始部分的比特串的一个字节串包含标注有斜线阴影的追加比特串。因此，数据D0中偏移量为ofsEs(i)的一个字节串整体与数据D1_s中偏移量为ofsAs(i)的一个字节串整体相比，两者在字节单位下是不一致的。其结果是，可认为在字节单位的比较和差分中，有时会没有提取出复制比特串E(i)的起始部分的比特串，即图14的粗线所包围的比特串ST。
[0178] 该情况在复制比特串E(i)的末尾部分的比特串中也是一样。即，数据D0中偏移量为ofsEe(i)的一个字节串整体与数据D1_s中偏移量为ofsAe(i)的一个字节串整体相比，两者在字节单位下是不一致的。因此，可认为在字节单位的比较和差分中，有时会没有提取出复制比特串E(i)的末尾部分的比特串，即图14的粗线所包围的比特串EN。
[0179] 因此，在本实施方式1中，差分提取部4不以字节为单位而是以比特为单位对数据D0中偏移量为ofsEs(i)的一个字节串与数据D1_s中偏移量为ofsAs(i)的一个字节串进行比较，由此来求取差分。由此，能够提取出字节单位的比较和差分中所不能提取的由图14的粗线包围的比特串ST。
[0180] 同样地，差分提取部4也不以字节为单位而是以比特为单位对数据D0中偏移量为ofsEe(i)的一个字节串与数据D1_s中偏移量为ofsAe(i)的一个字节串进行比较，由此来求取差分。由此，能够提取出字节单位的比较和差分中所不能提取的由图14的粗线包围的比特串EN。
[0181] 通过合并上述的比特串MI、比特串ST以及比特串EN，从而提取出图6的一个复制比特串E(i)。
[0182] 如上所述，虽然应该移动数据D1的适当的移位量是未知的，但0≦|S(i)|＜8。鉴于此，差分提取部4的比特移位部4a通过使数据D1移动从-7比特到7比特为止的各比特，从而生成多个(此处为15)数据D1_s(s＝-7～7)。由此生成的多个数据D1_s中的任一个与数据D0之间，复制比特串E(i)彼此的偏移得以消除。
[0183] 此处，在数据D0与数据D1_s(s＝-7～7)中，共通的比特串为下述的比特串。
[0184] CopyBS_s_0,CopyBS_s_1,…,CopyBS_s_Z(s)
[0185] Z(s)：相对于数据D0的数据D1_s的复制比特串的数减1后的数
[0186] 比特移位量s＝-7～7的任一个中，CopyBS_s_z(z＝0，1，…，Z(s))与复制比特串E(i)基本一致。
[0187] 其中，作为特殊的情况，在复制比特串E(i)的一部分中相同值连续的情况下，不仅仅只求出与复制比特串E(i)完全一致的CopyBS_s_z，还求出与复制比特串E(i)部分一致的CopyBS_s_z。此外，根据数据D1_s中复制比特串E(i)前后的值的不同，比特串ST或比特串EN(图14)有时包含有复制比特串E(i)以外的比特，在该情况下，有可能会求得比复制比特串E(i)要大的CopyBS_s_z。
[0188] 在这些情况下，在比特移位量s＝-7～7整体中，CopyBS_s_z彼此有可能具有重复部分。
[0189] 因此，本实施方式1所涉及的差分提取部4不将上述那样提取出的CopyBS_s_z提取作为复制比特串E(i)，而生成(提取)用于生成(提取)复制比特串E(i)的中间复制比特串。其中，CopyBS_s_z是数据D1_s的比特串，直接通过比特移位部4a对比特进行移动而得到。因此，在下述内容中，将向逆向移动了该移位量的CopyBS_s_z，即进行了恢复至数据D1中的比特串的校正的CopyBS_s_z作为中间复制比特串进行说明。
[0190] 通过上述方式生成了多个中间复制比特串之后，差分提取部4生成(提取)包含下述比特串中的至少一个的比特串信息作为最终的复制比特串信息，即：多个中间复制比特串中彼此不重复的中间复制比特串，结合多个中间复制比特串中彼此重复的中间复制比特串彼此而得到的比特串。
[0191] 然后，差分提取部4从数据D1(新数据)中提取去除复制比特串得到的比特串作为追加比特串。图6的新比特串BS1(数据D1)中，在获得E(i)(i＝1，2，…)作为复制比特串的情况下，提取A(i)(i＝1，2，…)作为追加比特串。
[0192] <差分提取部及差分数据生成部的详细结构>
[0193] 图15是表示本实施方式1所涉及的差分提取部4和差分数据生成部6的详细结构的一个示例的框图。
[0194] 图15的差分提取部4包括-7比特移位部4a1、-6比特移位部4a2、…、7比特移位部4a15、比特差分提取部4b1、4b2、…、4b15、复制比特串数据生成部4b30、追加比特串数据生成部4c1。图15的差分数据生成部6具备差分命令生成部6a。
[0195] 另外，图2的比特移位部4a包含图15的-7比特移位部4a1～7比特移位部4a15。图2的复制比特串提取部4b包含图15的比特差分提取部4b1～4b15(中间复制比特串提取部)、复制比特串数据生成部4b30(最终复制比特串提取部)。图2的追加比特串提取部4c包含图15的追加比特串数据生成部4c1。
[0196] -7比特移位部4a1～7比特移位部4a15按-7～7比特对新数据(文件F1的数据D1)进行移位。即，-7比特移位部4a1～7比特移位部4a15将新数据向其比特串的正向及逆向分别移动0，1，2，…，7比特，从而生成多个(此处为15)数据D1_-7～D1_7。多个数据D1_-7～D1_7存储于未图示的内部存储器。
[0197] 比特差分提取部4b1按比特单位和字节单位对数据D1_-7和没有进行移位的旧数据(文件F0的数据D0)进行比较。于是，比特差分提取部4b1通过该比较，提取数据D1_-7和旧数据中共通的比特串的信息作为中间复制比特串信息。比特差分提取部4b1将提取到的中间复制比特串信息作为中间差分文件MDF_-7存储到中间数据存储部5(图2)。
[0198] 同样地，比特差分提取部4b2～4b15按比特单位和字节单位对多个数据D1_-6～D1_7和没有进行移位的旧数据(文件F0的数据D0)进行比较。于是，比特差分提取部4b2～4b15通过该比较，提取出多个数据D1_-6～D1_7和旧数据中共通的比特串的信息作为多个中间复制比特串信息。于是，比特差分提取部4b2～4b15将提取出的多个中间复制比特串信息分别作为中间差分文件MDF_-6～MDF_7存储到中间数据存储部5(图2)。
[0199] 复制比特串数据生成部4b30基于比特差分提取部4b1～4b15中提取出的中间差分文件MDF_-7～MDF_7，求取包含下述比特串中的至少一个的比特串的信息作为复制比特串信息，即：这些中间复制比特串中彼此不重复的中间复制比特串、以及结合这些文件的中间复制比特串中彼此重复的中间复制比特串彼此而得到的比特串。复制比特串数据生成部4b30将求得的复制比特串的信息存储到未图示的内部存储器。
[0200] 追加比特串数据生成部4c1从文件F1的数据D1(新数据)中去除复制比特串，求取剩余的比特串的信息作为追加比特串信息。追加比特串数据生成部4c1将求得的追加比特串信息存储到未图示的内部存储器。
[0201] 差分命令生成部6a基于追加比特串信息和复制比特串信息生成差分数据。所生成的差分数据存储于差分数据存储部7(图2)。
[0202] 另外，可以利用差分数据生成装置1的未图示的一个CPU来依次(连续)进行-7比特移位部4a1～7比特移位部4a15、及比特差分提取部4b1～4b15的各处理。或者，通过将差分数据生成装置1的未图示的多个CPU分配给-7比特移位部4a1～7比特移位部4a15、及比特差分提取部4b1～4b15的各个，来并行地进行各个处理。此外，例如，关于移位量为-7～7比特的各个移位量，也可通过分别分配一个CPU，从而并行地进行针对各移位量的比特移位部和比特差分提取部的处理。
[0203] <差分提取部的动作>
[0204] 图16是表示差分提取部4的动作的一个示例的流程图。这里，对依次(连续)进行-7比特移位部4a1～7比特移位部4a15、及比特差分提取部4b1～4b15各个处理的动作例进行说明。即，对下述动作例进行说明：差分提取部4的比特移位部4a(图2)依次进行图15的-7比特移位部4a1～7比特移位部4a15的各个处理，差分提取部4的复制比特串提取部4b(图2)依次进行图15的比特差分提取部4b1～4b15的各个处理。
[0205] 首先，在步骤S1中，差分提取部4从数据存储部3读取文件F0的比特串长度lngBS0和数据D0(图12)，并存储于内部存储器。
[0206] 在步骤S2中，差分提取部4从数据存储部3读取文件F1的比特串长度lngBS1和数据D1(图12)，并存储于内部存储器。
[0207] 在步骤S3中，差分提取部4将内部存储器内所设的比特移位量s设定为-7，进行初始化。
[0208] 在步骤S4中，比特移位部4a(-7比特移位部4a1～7比特移位部4a15)对数据D1进行比特移位，将其移动比特移位量s，并将由此获得的数据D1_s存储到内部存储器。另外，s＝0的情况下的数据D1_0是没有被移位的数据D1。
[0209] 在步骤S5中，复制比特串提取部4b(比特差分提取部4b1～4b15)基于数据D0和数据D1_s，以比特单位和字节单位来进行比较，从而提取出中间复制比特串信息。复制比特串提取部4b将该中间复制比特串信息作为中间差分文件MDF_s存储到中间数据存储部5。
[0210] 图17是表示中间复制比特串信息(中间差分文件MDF_s)的构成例的图。
[0211] 中间复制比特串信息包含中间复制比特串记录数、以及该中间复制比特串记录数所表示数量的中间复制比特串记录。中间复制比特串记录的各个记录包含中间复制目的比特地址、中间复制源比特地址、以及中间复制比特串长度的字段。这里，中间复制目的比特地址表示数据D1(新数据)中的中间复制比特串的比特地址，中间复制源比特地址表示数据D0(旧数据)的中间复制比特串的比特地址，中间复制比特串长度表示中间复制比特串的比特长度。
[0212] 在图16的步骤S6中，差分提取部4判定比特移位量s是否为7。在判定为比特移位量s为7的情况下，判定为比特移位处理已结束，并前进至步骤S8，在判定为比特移位量s不为7的情况下，前进至步骤S7。
[0213] 在步骤S7中，差分提取部4将比特移位量s的值加1，对比特移位量s进行更新。然后，返回至步骤S4。
[0214] 在从步骤S6前进至步骤S8的情况下，复制比特串提取部4b(复制比特串数据生成部4b30)基于中间差分文件MDF_s(s＝-7～7)提取出最终的复制比特串信息，并将该复制比特串信息存储到内部存储器。
[0215] 图18是表示最终的复制比特串信息的构成例的图。
[0216] 复制比特串信息包含复制比特串记录数、以及该复制比特串记录数所表示数量的复制比特串记录。复制比特串记录的各个记录包含记录识别符、复制目的比特地址、复制源比特地址、以及复制比特串长度的字段。这里，记录识别符是用于表示该记录为复制比特串记录这一情况的字段，存储有1的值。复制目的比特地址表示数据D1(新数据)中复制比特串的起始比特的比特地址。复制源比特地址表示数据D0(旧数据)中复制比特串的起始比特的比特地址。复制比特串长度表示复制比特串的比特长度。
[0217] 在图16的步骤S9中，追加比特串提取部4c(追加比特串数据生成部4c1)从数据D1中，基于复制比特串信息去除复制比特串从而提取追加比特串信息，并将该追加比特串信息存储到内部存储器。然后，结束图16的差分提取部4的动作。
[0218] 图19是表示追加比特串信息的构成例的图。
[0219] 追加比特串信息包含追加比特串记录数、以及该追加比特串记录数所表示数量的追加比特串记录。追加比特串记录的各个记录包含记录识别符、追加目的比特地址、追加比特串长度和追加比特串的字段。这里，记录识别符是用于表示该记录为追加比特串记录这一情况的字段，存储有2的值。追加目的比特地址表示数据D1(新数据)中追加比特串的起始比特的比特地址。追加比特串长度表示追加比特串的比特长度。追加比特串表示追加比特串其本身。
[0220] 如上所述，差分提取部4对数据D0与在-7～+7比特的范围内进行了移位的数据D1进行比较，求取复制比特串和追加比特串。因此，即使旧数据与新数据之间产生了比特单位的偏差，也能够使复制比特串增加，能够减少追加比特串。其结果，能够提高差分数据的数据量削减效果。
[0221] 另外，以上对下述情况进行了说明，即：通过使用一个CPU来依次(连续)进行针对各移位量的步骤S4和步骤S5的处理。但是，如上所述，也可以通过使用多个CPU来并行地进行针对各移位量的步骤S4和步骤S5的处理。
[0222] 接着，对图16的处理中的主要内容进行详细说明。
[0223] <比特移位处理(步骤S4)>
[0224] 图20是详细示出图16的步骤S4，即比特移位处理的一个示例的流程图。
[0225] 首先，在步骤S11中，差分提取部4对比特移位量s的值进行调查。在s＝0的情况下，设为不需要进行比特移位，从而结束图20的比特移位处理。在s＜0的情况下，判定为应向比特串的逆向(朝向比特串的起始的方向)移动比特移位量s的绝对值，并前进至步骤S12。在s＞0的情况下，判定为应向比特串的正向(朝向比特串的末尾的方向)移动比特移位量s，并前进至步骤S15。
[0226] 在步骤S12中，图2的比特移位部4a直接将数据D1作为数据D1_s存储到内部存储器。
[0227] 在步骤S13中，比特移位部4a将1字节的数据(值为0)插入到该数据D1_s的起始处。
[0228] 在步骤S14中，比特移位部4a将该数据D1_s向起始移动比特移位量s的绝对值。然后，结束图20的比特移位处理。
[0229] 从步骤S11前进到步骤S15的情况下，比特移位部4a直接将数据D1作为数据D1_s存储到内部存储器。
[0230] 在步骤S16中，比特移位部4a将1字节的数据(值为0)插入到该数据D1_s的末尾处。
[0231] 在步骤S17中，比特移位部4a将该数据D1_s向末尾移动比特移位量s。然后，结束图20的比特移位处理。
[0232] <中间复制比特串信息的提取处理(步骤S5)>
[0233] 图21是详细示出图16的步骤S5，即中间复制比特串信息的提取处理(生成处理)的一个示例的流程图。
[0234] 首先，在步骤S21中，图2的复制比特串提取部4b以字节为单位来对数据D0(没有被移位的旧数据)和数据D1_s(进行了移位后的新数据)进行比较，由此提取出它们的差分。这里，复制比特串提取部4b基于数据D1_s和没有被移位的数据D0，从数据D1_s中提取出数据D0也包含的字节串作为复制字节串，从数据D1_s中提取出数据D0不包含的字节串作为追加字节串。提取得到的差分作为字节差分数据存储于内部存储器。
[0235] 图22是表示字节差分数据的构成例的图。
[0236] 字节差分数据包含所需数量的字节差分命令。字节差分命令中分配有下述命令中的任意命令，即：与追加字节串相关的追加命令、与复制字节串相关的复制命令、以及结束命令。
[0237] 图23是表示追加命令的构成例的图。
[0238] 追加命令包含命令代码、追加字节串长度以及追加字节串的字段。命令代码是表示该字节差分命令是追加命令这一内容的1字节的数据，值为248。追加字节串长度通过32比特的整数来表示追加字节串的字节数。追加字节串表示追加字节串其本身。
[0239] 图24是表示复制命令的构成例的图。
[0240] 复制命令包含命令代码、复制源偏移量及复制字节串长度。命令代码是表示该字节差分命令是复制命令这一内容的1字节的数据，值为254。复制源偏移量通过32比特的整数来表示数据D0中复制字节串的起始字节串的偏移量。复制字节串长度通过32比特的整数来表示复制字节串的字节数。
[0241] 图25是表示结束命令的构成例的图。
[0242] 结束命令是1字节的数据(值为0)。结束命令仅设置于字节差分数据的末尾，表示字节差分数据的结束。
[0243] 图21的步骤S22中，复制比特串提取部4b将内部存储器中所设的偏移量OFS1和复制命令数CCN均初始化为0。另外，在图21的动作中，偏移量OFS1表示数据D1_s中的复制字节串或追加字节串的起始字节串的偏移量。
[0244] 在每次进行步骤S23时，复制比特串提取部4b从起始开始一个一个地依次获取字节差分数据中的字节差分命令(图22)。即，在第一次进行步骤S23的情况下，获取字节差分数据中起始的字节差分命令(图22)，在第二次之后再进行步骤S23的情况下，获取上一次获得的字节差分命令的下一个字节差分命令。
[0245] 步骤S24中，复制比特串提取部4b调查步骤S23中所获得的字节差分命令的命令代码的值是否为0，调查该字节差分命令是否是结束命令。在该字节差分命令是结束命令的情况下，判定为关于字节差分命令的处理已结束，并前进至步骤S34，在不是结束命令的情况下，前进至步骤S25。
[0246] 步骤S25中，复制比特串提取部4b调查步骤S23中所获得的字节差分命令的命令代码的值是否为254，调查该字节差分命令是否是复制命令。在该字节差分命令为复制命令的情况下前进至步骤S26，在不是复制命令的情况下，认为该字节差分命令为追加命令，并前进至步骤S33。
[0247] 在前进到步骤S26的情况下，即字节差分命令为复制命令的情况下，复制比特串提取部4b将该复制命令的复制源偏移量和复制字节串长度分别设定为OFS0和CBYTL。
[0248] 此处，上述复制命令表示从数据D0的OFS0(复制源偏移量)起到前进了CBYTL(复制字节串长度)的偏移量为止的字节串、与从数据D1_s的偏移量OFS1起到前进了CBYTL(复制字节串长度)的偏移量为止的字节串相同。形成数据D0和数据D1_s中相同的这些字节串、即复制字节串的比特串与图14所示的比特串MI相对应，因此，以下记为比特串MI来进行说明。
[0249] 在紧挨着比特串MI之前或之后的1字节内，有可能包含有与比特串MI连续，且在数据D0和数据D1_s中相同的比特串。包含于紧挨着比特串MI之前的1字节内，且在数据D0和数据D1_s中相同的比特串与图14所示的比特串ST相对应，因此以下记为比特串ST来进行说明。包含于紧挨着比特串MI之后的1字节内，且在数据D0和数据D1_s中相同的比特串与图14所示的比特串EN相对应，因此以下记为比特串EN来进行说明。
[0250] 比特串MI通过步骤S21来求得，因此，只要求出比特串ST和比特串EN，就能够求出中间复制比特串。
[0251] 因此，在步骤S26中，在上述OFS0和CBYTL的设定之后，复制比特串提取部4b求出比特串ST。例如，复制比特串提取部4b按比特串的逆向的顺序(从最下位比特到最上位比特的顺序)对数据D0中偏移量为“OFS0-1”的1字节和数据D1_s中偏移量为“OFS1-1”的1字节进行比较，求出变为不一致之前的比特数(XBN)。
[0252] 接着，通过下述方式求出起始的数据D0的中间复制比特串的起始的比特地址adr0Is(以下仅记为“adr0Is”)以及数据D1_s的中间复制比特串的起始的比特地址adr1Is(以下仅记为“adr1Is”)。
[0253] adr0Is＝OFS0*8-XBN
[0254] adr1Is＝OFS1*8-XBN
[0255] 即，在步骤S26中，复制比特串提取部4b按照比特串的逆向的顺序，判定数据D1_s中紧挨着以字节单位提取出的字节串(比特串MI)之前的1字节内所包含的比特、与数据D0中紧挨着以字节单位提取出的字节串(比特串MI)之前的1字节内所包含的比特是否一致，最后求得一致的数据D1_s的adr1Is(第1地址)及数据D0的adr0Is(第2地址)。
[0256] 步骤S27中，复制比特串提取部4b求取比特串EN。例如，复制比特串提取部4b按比特串的正向的顺序(从最上位比特到最下位比特的顺序)对数据D0中偏移量为“OFS0+CBYTL”的1字节和数据D1_s中偏移量为“OFS1+CBYTL”的1字节进行比较，求出变为不一致之前的比特数(YBN)。
[0257] 接着，通过下述方式求出数据D0的中间复制比特串的末尾的比特地址adr0Ie(以下仅记为“adr0Ie”)，以及数据D1_s的中间复制比特串的末尾的比特地址adr1Ie(以下仅记为“adr1Ie”)。
[0258] adr0Ie＝(OFS0+CBYTL)*8+YBN-1
[0259] adr1Ie＝(OFS1+CBYTL)*8+YBN-1
[0260] 即，在步骤S27中，复制比特串提取部4b按照比特串的正向的顺序，判定数据D1_s中紧挨着以字节单位提取出的字节串(比特串MI)之后的1字节内所包含的比特、与数据D0中紧挨着以字节单位提取出的字节串(比特串MI)之后的1字节内所包含的比特是否一致，求得最后一致的数据D1_s的adr1Ie(第3地址)及数据D0的adr0Ie(第4地址)。
[0261] 这里，步骤S26、S27中所求得的adr1Is、adr1Ie是移位后的数据D1_s的中间复制比特串的比特地址。
[0262] 鉴于此，在步骤S28中，复制比特串提取部4b将adr1Is、adr1Ie校正为比特移位部4a进行移位之前的地址。即，复制比特串提取部4b使adr1Is、adr1Ie的值向比特移位部4a的移位(步骤S4)的相反方向进行移位。
[0263] 在步骤S29中，复制比特串提取部4b通过下述方式来求取中间复制比特串的比特串长度ICBL。
[0264] ICBL＝adr0Ie-adr0Is+1
[0265] 步骤S30中，复制比特串提取部4b分别将校正后的adr1Is、adr0Is、以及ICBL设定为中间复制比特串记录(图17)的中间复制目的比特地址、中间复制源比特地址、以及中间复制比特串长度。由此，生成中间复制比特串记录(图17)。
[0266] 通过上述的步骤S28～S30，复制比特串提取部4b对adr1Ie和adr1Is进行校正，基于adr0Ie和adr0Is以及校正后的adr1Ie和adr1Is，生成中间复制比特串信息。
[0267] 其中，由于adr0Ie、adr0Is彼此的差、以及adr1Ie、adr1Is彼此的差相等，因此，只要确定adr1Ie、adr1Is中的一个，就能确定另外一个。鉴于此，复制比特串提取部4b也可以对adr1Ie或adr1Is进行校正，基于adr0Ie和adr0Is、以及校正后的adr1Ie或adr1Is来生成中间复制比特串信息。
[0268] 在步骤S31中，复制比特串提取部4b将复制命令数CCN加1，对复制命令数CCN进行更新。
[0269] 在步骤S32中，复制比特串提取部4b将步骤S23中最近获得的复制命令所包含的复制字节串长度(图18)与偏移量OFS1相加，对偏移量OFS1进行更新。由此，偏移量OFS1表示下一个追加命令所表示的数据D1_s中追加字节串的起始字节串的偏移量、或者下一个复制命令所表示的数据D1_s中复制字节串的起始字节串的偏移量。然后，返回至步骤S23。
[0270] 从步骤S25前进到步骤S33的情况下，复制比特串提取部4b将步骤S23中最近获得的追加命令所包含的追加字节串长度(图19)与偏移量OFS1相加，对偏移量OFS1进行更新。由此，偏移量OFS1表示下一个追加命令所表示的数据D1_s中追加字节串的起始字节串的偏移量、或者下一个复制命令所表示的数据D1_s中复制字节串的起始字节串的偏移量。然后，返回至步骤S23。
[0271] 从步骤S24前进到步骤S34的情况下，复制比特串提取部4b将复制命令数CCN设定为中间复制比特串记录数。
[0272] 在步骤S35中，复制比特串提取部4b生成包含步骤S30中所生成的中间复制比特串记录、以及步骤S34中所设定的中间复制比特串记录数的图17的中间复制比特串信息，并将其作为中间差分文件MDF_s存储到中间数据存储部5。然后，结束图21的中间复制比特串的提取处理(生成处理)。
[0273] 此处，以图14为例来说明图21的处理。图14中，应对数据D1进行移位的比特移位量s＝-S(i)＝-2。
[0274] 步骤S21中，复制比特串提取部4b根据数据D0和数据D1_s(移动了-2比特后的数据D1)求取字节差分数据。此处求得的字节差分数据是与图14的比特串MI相关的数据，包含具有下述字段的复制命令。另外，将图14的ofsEs(i)和bylngCopyE(i)用于下述复制命令的记载。
[0275] 复制源偏移量＝ofsEs(i)+1
[0276] 复制字节串长度＝bylngCopyE(i)
[0277] 在步骤S22中，复制比特串提取部4b获取上述复制命令。经过步骤S23～S25，在步骤S26中，复制比特串提取部4b将复制源偏移量(数据D0的ofsEs(i)+1)设定为OFS0，将复制字节串长度(bylngCopyE(i))设定为CBYTL。另外，OFS1表示数据D1_s中的追加字节串或复制字节串的起始字节串的偏移量，此处相当于图14的数据D1_s的ofsAs(i)+1。
[0278] 步骤S26中，复制比特串提取部4b从最下位比特起依次对数据D0的偏移量为OFS0-1＝ofsEs(i)的1字节、和数据D1_s的偏移量为OFS1-1＝ofsAs(i)的1字节进行比较。由此获得比特串ST，并得到XBN＝6。其结果是获得数据D0中的中间复制比特串的起始的adr0Is(＝bitnEs(i))、以及数据D1_s中的中间复制比特串的起始的adr1Is(＝bitnAs_s(i))。
[0279] 步骤S27中，复制比特串提取部4b从最上位比特起依次对数据D0的偏移量为OFS0+CBYTL＝ofsEe(i)的1字节、和数据D1_s的偏移量为OFS1+CBYTL＝ofsAe(i)的1字节进行比较。由此获得比特串EN，并得到YBN＝4。其结果是获得数据D0中的中间复制比特串的末尾的adr0Ie(＝bitnEe(i))、以及数据D1_s中的中间复制比特串的末尾的adr1Ie(＝bitnAe_s(i))。
[0280] 步骤S28中，复制比特串提取部4b使数据D1_s中的adr1Is(＝bitnAs_s(i))、以及adr1Ie(＝bitnAe_s(i))向比特移位部4a的移位(步骤S4)的相反方向进行移位。由此，获得数据D1的bitnAs(i)、bitnAe(i)。
[0281] 通过上述这样的动作，对于比特移位量s(s＝-7～7)的各个比特移位量，对数据D0和数据D1_s中共通的比特串进行了比特移位的校正，从而获得中间复制比特串。其结果如图15所示那样，获得多个中间差分文件MDF_s(图17)。
[0282] <复制比特串信息的提取处理(步骤S8)>
[0283] 图26是详细示出图16的步骤S8，即复制比特串信息的提取处理(生成处理)的一个示例的流程图。
[0284] 首先，在步骤S41中，复制比特串提取部4b读取中间差分文件MDF_-7，并将该中间差分文件MDF_-7作为中间比特串合并信息IMERGE存储到内部存储器。由此，图17所示的中间复制比特串信息作为中间比特串合并信息IMERGE被存储到内部存储器。
[0285] 在步骤S42中，复制比特串提取部4b通过对文件指定fs(fs＝-6～7)设定-6，来对文件指定fs进行初始化。另外，文件指定fs指定应独立于步骤S41进行读取的中间差分文件MDF_fs。
[0286] 步骤S43中，复制比特串提取部4b读取由文件指定fs指定的中间差分文件MDF_fs，并将该中间差分文件MDF_fs作为暂时中间复制比特串信息TEMP存储到内部存储器。由此，图17所示的中间复制比特串信息作为暂时中间复制比特串信息TEMP被存储到内部存储器。
[0287] 在步骤S44中，复制比特串提取部4b通过将暂时中间复制比特串信息TEMP的中间复制比特串记录数设定到内部存储器所设定的计数器，来对计数器进行初始化。
[0288] 在每次进行步骤S45时，复制比特串提取部4b从起始开始依次从暂时中间复制比特串信息TEMP中获取一个中间复制比特串记录。即，在第一次进行步骤S45的情况下，获取起始的一个中间复制比特串记录，在第二次以后再进行步骤S45时，获取上一次所获取的一个中间复制比特串记录的下一个的中间复制比特串记录。
[0289] 在步骤S46中，复制比特串提取部4b针对中间比特串合并信息IMERGE的各中间复制比特串记录、以及暂时中间复制比特串信息TEMP的一个中间复制比特串记录，求取中间复制比特串的复制范围。此处，中间复制比特串的复制范围是指基于中间复制比特串记录(图17)的中间复制源比特地址和中间复制比特串长度来规定的数据D0中的中间复制比特串的比特地址的范围。此处，复制范围设为从“中间复制源比特地址”到“中间复制源比特地址+中间复制比特串长度-1”为止的数据D0的比特地址的范围。
[0290] 于是，复制比特串提取部4b判定中间比特串合并信息IMERGE的各中间复制比特串记录的复制范围与暂时中间复制比特串信息TEMP的一个中间复制比特串记录的复制范围是否局部重复。在重复的情况下前进至步骤S49，在不重复的情况下前进至步骤S47。
[0291] 在步骤S47中，复制比特串提取部4b将步骤S45中所获得的一个中间复制比特串记录插入到中间比特串合并信息IMERGE或者追加到中间比特串合并信息IMERGE的末尾。其中，以使暂时中间复制比特串信息TEMP的一个中间复制比特串记录和中间比特串合并信息IMERGE的各中间复制比特串记录按中间复制源比特地址的升序排列的方式来进行上述插入和追加。
[0292] 在步骤S48中，复制比特串提取部4b将中间比特串合并信息IMERGE的中间复制比特串记录数加1，对中间复制比特串记录数进行更新。然后，前进至步骤S52。
[0293] 从步骤S46前进到步骤S49的情况下，复制比特串提取部4b对于重复的复制范围，将中间比特串合并信息IMERGE的中间复制比特串记录和暂时中间复制比特串信息TEMP的一个中间复制比特串记录相结合。
[0294] 由此获得结合这些中间复制比特串记录的复制范围后的结合复制范围，并且获得具有该结合复制范围的结合比特串。结合复制范围设为包含重复的所有复制范围的最小范围。将结合复制范围的最小的比特地址记为adrCAmin，将结合复制范围的最大的比特地址记为adrCAmax，以下，具体地进行说明。
[0295] 图27是表示结合复制范围的一个示例的图。
[0296] 图27的示例中，中间比特串合并信息IMERGE的各中间复制比特串记录#u、#v、#w的复制范围与暂时中间复制比特串信息TEMP的一个中间复制比特串记录#t的复制范围相重复。因此，包含这些所有复制范围的最小范围成为结合复制范围。
[0297] 图26的步骤S50中，复制比特串提取部4b仅保留中间比特串合并信息IMERGE的成为结合对象的中间复制比特串记录中起始的中间复制比特串记录，而删除其他的记录。按下述那样对所保留的起始的中间复制比特串记录(图17)的中间复制目的比特地址、中间复制源比特地址、中间复制比特串长度进行变更和设定。
[0298] (1)从所保留的起始的中间复制目的比特地址(数据D1中的比特地址)减去“中间复制源比特地址-adrCAmin”。其中，中间复制源比特地址设为下述(2)的设定前的值。由此，中间复制目的比特地址变化了结合了复制范围的部分。(2)对所保留的起始的中间复制源比特地址(数据D0中的比特地址)设定adrCAmin。(3)对所保留的起始的中间复制源比特串长度设定“adrCAmax-adrCAmin+1”。
[0299] 图27的示例中，中间比特串合并信息IMERGE的中间复制比特串记录#u、#v、#w中，保留起始的中间复制比特串记录#u，其他的中间复制比特串记录#v、#w被删除。所保留的起始的中间复制比特串记录#u的各字段按上述那样进行变更。
[0300] 在步骤S51中，复制比特串提取部4b从中间比特串合并信息IMERGE的中间复制比特串记录数中减去步骤S50中删除掉的中间比特串合并信息IMERGE的中间复制比特串记录的数量，对中间复制比特串记录数进行更新。然后，前进至步骤S52。
[0301] 步骤S52中，复制比特串提取部4b将计数器减去1，对计数器进行更新。
[0302] 步骤S53中，复制比特串提取部4b判定计数器是否为0。在判定为0的情况下，判定对暂时中间复制比特串信息TEMP的所有的中间复制比特串记录的处理结束，并前进至步骤S54。在不为0的情况下返回至步骤S45。
[0303] 在步骤S54中，复制比特串提取部4b将文件指定fs加1，对文件指定fs进行更新。
[0304] 步骤S55中，复制比特串提取部4b判定文件指定fs是否大于7。在判定为大于7的情况下，关于中间差分文件MDF_fs(fs＝-6～7)的处理结束，并前进至步骤S56。在判定为不是该情况时，返回至步骤S43。
[0305] 在步骤S56中，复制比特串提取部4b将中间比特串合并信息IMERGE的中间复制比特串记录数设定为复制比特串信息(图18)的复制比特串记录数。并且，复制比特串提取部4b将向中间比特串合并信息IMERGE的中间复制比特串记录追加了记录识别符(＝1)后得到的记录设定为复制比特串信息(图18)的复制比特串记录。由此生成复制比特串信息(图
18)。然后，结束图26的复制比特串的提取处理(生成处理)。
18)。然后，结束图26的复制比特串的提取处理(生成处理)。
[0306] 通过上述处理，从而获得包含中间差分文件MDF_-7～MDF_7的各中间复制比特串的复制范围中复制范围与其他不重复的中间复制比特串、以及具有结合了重复的复制范围的结合复制范围的结合比特串中的至少一个的比特串的信息，来作为最终的复制比特串信息。
[0307] 因此，最终的复制比特串的复制范围变得尽可能大。由此，能够将多个复制比特串记录汇总为一个复制比特串记录，从而能够减小复制比特串记录所需的数据量，进而减小差分数据的数据量。
[0308] <追加比特串信息的提取处理(步骤S9)>
[0309] 图28是详细示出图16的步骤S9，即追加比特串信息的提取处理(生成处理)的一个示例的流程图。图29是表示追加比特串信息的提取处理(生成处理)的一个示例的图。
[0310] 首先，在图28的步骤S61中，追加比特串提取部4c对内部存储器所设的追加比特地址ABA(以下仅记为“ABA”)、复制计数器CCNT(以下仅记为“CCNT”)、追加计数器ACNT(以下仅记为“ACNT”)进行初始化。此处，作为初始化，对ABA设定0，对CCNT设定复制比特串信息(图18)的复制比特串记录数，对ACNT设定0。另外，图28的动作中ABA大概表示数据D1中追加比特串的起始的比特地址。
[0311] 在每次进行步骤S62时，追加比特串提取部4c从起始开始依次从复制比特串信息(图18)中获取一个复制比特串记录。即，在第一次进行步骤S62的情况下，获取起始的一个复制比特串记录，在第二次以后再进行步骤S62时，获取上一次所获取的一个复制比特串记录的下一个的复制比特串记录。
[0312] 关于步骤S62中所获得的复制比特串记录，将复制目的比特地址设定为CBA1，将复制源比特地址设定为CBA0，将复制比特串长度设定为CBL。
[0313] 图29的示例中，在第一次进行步骤S62的情况下，将作为复制目的比特地址的cba1_0设定为CBA1，将作为复制源比特地址的cba0_0设定为CBA0，将作为复制比特串长度的cb1_0设定为CBL。
[0314] 在步骤S63中，追加比特串提取部4c对步骤S62中所获得的复制比特串记录的CBA1和ABA进行比较。在一致的情况下前进至步骤S68，在不一致的情况下前进至步骤S64。
[0315] 此处，在CBA1和ABA一致的情况下，表示在数据D1中，从ABA(＝CBA1)表示的比特开始，到上述复制比特串记录的复制比特串长度CBL为止存在复制比特串。在CBA1和ABA不一致的情况下，表示在数据D1中，从ABA(＜CBA1)表示的比特开始，到“CBA1-1”表示的比特为止存在追加比特串。
[0316] 例如，如图29所示那样，在数据D1的起始存在有追加比特串的情况下，在第一次的步骤S63中，对于复制比特串记录#0，CBA1(＝cba1_0≠0)和ABA(＝0)不一致。该情况下，从数据D1的ABA(＝0)起到“CBA-1(＝cba1_0-1)”为止存在有追加比特串。
[0317] 另一方面，虽然未进行图示，但在数据D1的起始存在有复制比特串的情况下，在第一次的步骤S63中，对于复制比特串记录#0，CBA1(＝cba1_0＝0)和ABA(＝0)一致。该情况下，从数据D1的ABA(＝0)起到“CBA-1(＝cba1_0-1)”为止存在有复制比特串。
[0318] 从图28的步骤S63前进到步骤S64的情况下，即如图29所示的情况下，追加比特串提取部4c求取从数据D1的比特地址ABA到“CBA-1”为止的比特串作为追加比特串ABS。
[0319] 例如，在图29的状态下第一次进行步骤S64时，求得数据D1的追加比特串A0作为追加比特串ABS。
[0320] 图28的步骤S65中，追加比特串提取部4c将ABA、“CBA1-1”及追加比特串ABS分别设定为追加比特串记录(图19)的追加目的比特地址、追加比特串长度和追加比特串，向由此得到的数据追加记录识别符(＝2)。由此，生成追加比特串记录(图19)。
[0321] 例如，在图29的状态下第一次进行步骤S65时，关于追加比特串A0生成追加比特串记录#0。
[0322] 步骤S66中，追加比特串提取部4c将步骤S65中所生成的追加比特串记录存储在至此为止所存储的追加比特串记录之后。但是，最初的追加比特串记录存储在紧挨着存储追加比特串记录数的区域之后。
[0323] 例如，在图29的状态下第一次进行步骤S66时，最初的追加比特串记录#0存储在紧挨着追加比特串记录数之后。
[0324] 在图28的步骤S67中，追加比特串提取部4c将ACNT加1，对至此为止所存储的追加比特串记录数进行计数。
[0325] 在步骤S68中，追加比特串提取部4c将步骤S62中所获得的复制比特串记录的CBA1与该复制比特串记录的CBL相加后得到的值设定为ABA。其结果是，ABA表示下一个追加比特串的起始的比特地址。
[0326] 例如，在图29的状态下第一次进行步骤S68时，基于步骤S62中所获得的复制比特串记录#0，“cba1_0+cb1_0”被设定为第二次的ABA。此处，“cba1_0+cb1_0”表示追加比特串A1的起始的比特地址。
[0327] 图28的步骤S69中，追加比特串提取部4c将CCNT减1，对CCNT进行更新。
[0328] 在步骤S70中，追加比特串提取部4c判定CCNT是否为0。在判定为0的情况下，设为对所有的复制比特串记录的处理结束，并前进至步骤S71。在判定为不是该情况时，返回至步骤S62。
[0329] 在图29的示例中，在第二次进行步骤S63的情况下，关于复制比特串记录#1，CBA1(＝cba1_1)与ABA(＝cba1_0+cb1_0)不一致。该情况下，前进至步骤S64，追加比特串提取部4c求取从数据D1的ABA(＝cba1_0+cb1_0)到“CBA1-1(＝cba1_1-1)”为止的比特串作为追加比特串A1。
[0330] 然后，在步骤S65中，关于追加比特串A1生成追加比特串记录#1。步骤S66中，追加比特串记录#1被存储到追加比特串记录#0之后。经过步骤S67，在步骤S68中，基于步骤S62中所获得的复制比特串记录#1，“cba1_1+cb1_1”被设定作为第三次的ABA。此处，“cba1_1+cb1_1”表示追加比特串A2的起始的比特地址。
[0331] 在从图28的步骤S70前进至步骤S71的情况下，追加比特串提取部4c将ACNT设定为追加比特串信息(图19)的追加比特串记录数。由此，生成追加比特串信息(图19)。然后，结束图28的追加比特串信息的提取处理(生成处理)。
[0332] <差分数据生成部的动作>
[0333] 至此，对图2和图15所示的差分提取部4的动作进行了说明。接着，对图2和图15所示的差分数据生成部6(差分命令生成部6a)的动作进行说明。另外，在对差分数据生成部6的动作进行说明之前，对通过差分数据生成部6的动作而生成的差分数据进行说明。
[0334] 图30是表示差分数据生成部6所生成的差分数据的构成例的图。
[0335] 差分数据包含所需数量的比特差分命令。比特差分命令中分配有下述命令中的任意命令，即：与追加比特串相关的追加比特命令、与复制比特串相关的复制比特命令、以及结束命令。以下，对比特差分命令的构成例进行说明，但比特差分命令的结构并不限于下述结构。
[0336] 图31是表示追加比特命令的构成例的图。
[0337] 追加比特命令包含命令代码、追加比特串长度以及追加比特串的字段。
[0338] 命令代码是表示该比特差分命令是追加比特命令这一内容的2比特长度的数据，值为1。
[0339] 追加比特串长度表示追加比特串的比特长度(比特数)。此处，追加比特串长度包含追加比特串长度头、追加比特串长度商部、以及追加比特串长度余数部。
[0340] 追加比特串长度头用2比特来表示追加比特串长度商部所能够使用的字节数。例如，0、1、2、3分别表示追加比特串长度商部所能够使用的字节数为1、2、3、4字节。
[0341] 追加比特串商部表示追加比特串长度除以256时的商。追加比特串商部所能够使用的字节数由追加比特串长度头来决定。
[0342] 追加比特串长度余数部用1字节来表示追加比特串长度除以256时的余数。
[0343] 追加比特串表示数据D1中的追加比特串其本身。
[0344] 图32是表示复制比特命令的构成例的图。
[0345] 复制比特命令包含命令代码、复制源比特地址及复制比特串长度的字段。
[0346] 命令代码是表示该比特差分命令是复制比特命令这一内容的2比特长度的数据，值为2。
[0347] 复制源比特地址表示关于应从数据D0复制到数据D1的复制比特串，数据D0的该复制比特串的起始的比特地址。此处，复制源比特地址包含复制源比特地址头、复制源比特地址商部、以及复制源比特地址余数部。
[0348] 复制源比特地址头用2比特来表示复制源比特地址商部所能够使用的字节数。例如，0、1、2、3分别表示复制源比特地址商部所能够使用的字节数为1、2、3、4字节。
[0349] 复制源比特地址商部表示复制源比特地址除以256时的商。复制源比特地址商部所能够使用的字节数由复制源比特地址头来决定。
[0350] 复制源比特地址余数部用1字节来表示复制源比特地址除以256时的余数。
[0351] 复制比特串长度表示应从数据D0复制到数据D1的复制比特串的比特长度(比特数)。此处，复制比特串长度包含复制比特串长度头、复制比特串长度商部、以及复制比特串长度余数部。
[0352] 复制比特串长度头通过2比特来表示复制比特串长度商部所能够使用的字节数。例如，0、1、2、3分别表示复制比特串长度商部所能够使用的字节数为1、2、3、4字节。
[0353] 复制比特串长度商部表示复制比特串长度除以256时的商。复制比特串长度商部所能够使用的字节数由复制比特串长度头来决定。
[0354] 复制比特串长度余数部用1字节来表示复制比特串长度除以256时的余数。
[0355] 图33是表示结束命令的构成例的图。
[0356] 结束命令仅由命令代码构成。命令代码为2比特长度的字段，值设为0。结束命令仅设置于差分数据的末尾，表示差分数据的结束。
[0357] 图34是表示差分数据生成部6(差分命令生成部6a)的动作的一个示例的流程图。另外，作为前提，将复制比特串信息(图18)和追加比特串信息(图19)设为已存储在内部存储器的信息。
[0358] 首先，在步骤S81中，差分数据生成部6将复制比特串信息(图18)的复制比特串记录数和追加比特串信息(图19)的追加比特串记录数相加后的值g设定为内部存储器所设的生成记录数。
[0359] 在步骤S82中，差分数据生成部6将复制比特串信息(图18)的复制比特串记录和追加比特串信息(图19)的追加比特串记录合并，并将由此获得的信息作为合并信息存储到内部存储器。另外，在合并信息中，复制比特串记录和追加比特串记录以各记录的第2字段(复制目的比特地址和追加目的比特地址)成为升序的方式进行合并。
[0360] 图35是表示合并信息的构成例的图。
[0361] 合并信息中，复制比特串记录和追加比特串记录按这些记录的第2字段的升序进行存储。所存储的复制比特串记录和追加比特串记录的总计与生成记录数的值g相同。另外，在图35中，SECF(i)(i＝0，1，…，g-1)表示各记录内的第2字段的值。
[0362] 图34的步骤S83中，差分数据生成部6将内部存储器所设的记录计数器设定为0来进行初始化。
[0363] 在每次进行步骤S84时，差分数据生成部6从起始开始一个一个地依次获取合并信息中作为复制比特串记录和追加比特串记录中的任一个的记录。即，在第一次进行步骤S84的情况下，获取合并信息中起始的记录#0，在第二次之后再进行步骤S84的情况下，获取上一次获得的记录#0的下一个记录#1。
[0364] 于是，差分数据生成部6判定所获得的记录的记录识别符是否是表示复制比特串记录的识别符(＝1)。在识别符为1的情况下，判定为所获得的记录为复制比特串记录，并前进至步骤S85。在识别符不为1的情况下，判定为所获得的记录是追加比特串记录，并前进至步骤S86。
[0365] 在步骤S85中，差分数据生成部6基于步骤S84中所获得的复制比特串记录，生成按下述方式设定的复制比特命令(图32)，并将该复制比特命令追加到生成中的差分数据的末尾。然后，前进至步骤S87。
[0366] 命令代码：
[0367] 设定表示复制比特命令的2
[0368] 复制源比特地址：
[0369] 设定该复制比特串记录的复制源比特地址
[0370] 复制比特串长度：
[0371] 设定该复制比特串记录的复制比特串长度
[0372] 在步骤S86中，差分数据生成部6基于步骤S84中所获得的追加比特串记录，生成按下述方式设定的追加比特命令(图31)，并将该追加比特命令追加到生成中的差分数据的末尾。然后，前进至步骤S87。
[0373] 命令代码：
[0374] 设定表示追加比特命令的1
[0375] 追加比特串长度：
[0376] 设定该追加比特串记录的追加比特串长度
[0377] 追加比特串：
[0378] 设定该追加比特串记录的追加比特串
[0379] 在步骤S87中，差分数据生成部6将记录计数器的值加1，对记录计数器进行更新。
[0380] 在步骤S88中，差分数据生成部6判定记录计数器的值是否与生成记录数的值g一致。判定为一致的情况下，判定为比特差分命令的生成已结束，并前进至步骤S89。在判定为不一致的情况下返回步骤S84。
[0381] 在步骤S89中，差分数据生成部生成结束命令(图33)，并追加到生成中的差分数据的末尾。由此，生成图30的差分数据。
[0382] 在步骤S90中，差分数据生成部6将所生成的差分数据存储到差分数据存储部7(图2)。然后，结束图34的差分数据生成部6的动作。
[0383] 通过上述处理生成的差分数据包含有复制比特命令(表示数据D0所包含的复制比特串的地址和长度的信息)、追加比特命令(表示数据D1所包含的追加比特串和追加比特串的长度的信息)。并且，在差分数据中，复制比特命令和追加比特命令按数据D1中所包含的复制比特串和追加比特串在该数据D1中的地址顺序进行排列。由此，能够尽可能地减少差分数据的数据量。
[0384] <数据更新部的动作>
[0385] 以上，对图2的差分数据生成装置1中的主要构成要素的动作进行了说明。接着，对图3的数据更新装置11的数据更新部15的动作进行说明。另外，图4的信息处理装置21的数据更新部25的动作与以下说明的数据更新部15的动作相同。
[0386] 图36是表示数据更新部15的数据更新动作的一个示例的流程图。通过以下说明可得以明确，通过该更新动作可生成与新数据(数据D1)相同的数据D2。
[0387] 首先，在图36的步骤S101中，数据更新部15从数据存储部14(图3)读取作为旧数据的文件F0(图12)的lngBS0和数据D0，并将它们存储到内部存储器。
[0388] 在步骤S102中，数据更新部15从差分数据存储部13(图3)读取差分数据，并将该差分数据存储到内部存储器。
[0389] 在步骤S103中，数据更新部15将内部存储器内所设的存储比特地址SBA设定为0，以进行初始化。此处，图36的动作中，存储比特地址SBA表示数据D2中的追加比特串或复制比特串的起始的比特地址。
[0390] 在每次进行步骤S104时，数据更新部15从起始开始一个一个依次获取内部存储器所存储的差分数据中的比特差分命令。即，在第一次进行步骤S104的情况下，获取差分数据中起始的比特差分命令，在第二次之后再进行步骤S104的情况下，获取上一次获得的比特差分命令的下一个比特差分命令。
[0391] 在步骤S105中，数据更新部15判定步骤S104中所获得的比特差分命令的命令代码是否是表示追加比特命令的命令代码(＝1)。在命令代码为1的情况下，判定为所获得的比特差分命令为追加比特命令，并前进至步骤S108。在不为1的情况下前进至步骤S106。
[0392] 在步骤S106中，数据更新部15判定步骤S104中所获得的比特差分命令的命令代码是否是表示复制比特命令的命令代码(＝2)。在命令代码为2的情况下，判定为所获得的比特差分命令为复制比特命令，并前进至步骤S110。在不为2的情况下前进至步骤S107。
[0393] 在步骤S107中，数据更新部15判定步骤S104中所获得的比特差分命令的命令代码是否是表示结束命令的命令代码(＝0)。在命令代码为0的情况下，判定为所获得的比特差分命令为结束复制比特命令，并前进至步骤S113。在不为0的情况下，判定所获得的比特差分命令为无效命令，并返回步骤S104。
[0394] 在从步骤S105前进到步骤S108的情况下，数据更新部15将步骤S104中所获得的追加比特命令(图31)的追加比特串存储到数据D2。
[0395] 图37是表示步骤S108和S109中数据更新部15的处理的一个示例的图。图37的示例中，在进行步骤S108的情况下，数据更新部15将追加比特命令的追加比特串AddBS的起始与数据D2的存储比特地址SBA的位置相匹配，由此将追加比特串AddBS存储到数据D2。
[0396] 图36的步骤S109中，数据更新部15将存储比特地址SBA与步骤S104中所获得的追加比特命令(图31)的追加比特串长度相加，对存储比特地址SBA进行更新。图37的示例中，在进行步骤S109的情况下，将存储比特地址SBA与追加比特命令的追加比特串长度lngAddBS相加。由此，存储比特地址SBA表示紧挨着步骤S108中所存储的追加比特串AddBS之后的比特地址。在步骤S109之后，返回步骤S104。
[0397] 在从步骤S106前进到步骤S110的情况下，数据更新部15基于步骤S104中所获得的复制比特命令(图32)的复制源比特地址和复制比特串长度，从数据D0获取复制比特串。
[0398] 图38是表示步骤S110～S112中数据更新部15的处理的一个示例的图。在图38的示例中，在进行步骤S110的情况下，数据更新部15获取从数据D0中复制源比特地址adrCopyBS表示的地址起到复制比特串长度lngCopyBS为止的复制比特串CopyBS。
[0399] 图36的步骤S111中，数据更新部15将步骤S110中所获得的复制比特串存储到数据D2。图38的示例中，在进行步骤S111的情况下，数据更新部15将复制比特串CopyBS的起始与数据D2的存储比特地址SBA的位置相匹配，由此将复制比特串CopyBS存储到数据D2。
[0400] 图36的步骤S112中，数据更新部15将存储比特地址SBA与步骤S104中所获得的复制比特命令(图32)的复制比特串长度相加，对存储比特地址SBA进行更新。图38的示例中，在进行步骤S112的情况下，将存储比特地址SBA与复制比特命令的复制比特串长度lngCopyBS相加。由此，存储比特地址SBA表示紧挨着步骤S111中所存储的复制比特串CopyBS之后的比特地址。在步骤S112之后，返回步骤S104。
[0401] 在从步骤S107前进到步骤S113的情况下，生成与新数据(数据D1)相同的数据D2。因此，数据更新部15将存储比特地址SBA作为数据D2的比特串长度lngBS2进行存储。
[0402] 在步骤S114中，数据更新部15将与新数据相同的数据D2存储到数据存储部14(图3)。然后，结束图36的数据更新动作。另外，此时，可以将旧数据改写为与新数据相同的数据D2，也可以将旧数据从数据存储部14中删除。
[0403] <实施方式1的总结>
[0404] 根据上述本实施方式1所涉及的差分数据生成装置1，基于旧数据、以及在0，1，2，…，n比特的范围内向比特串的正向及逆向进行了移位的新数据，来求取复制比特串和追加比特串。因此，即使旧数据与新数据之间产生了比特单位的偏差，也能够使差分数据中的复制比特串增加，能够减少追加比特串。其结果，能够提高差分数据的数据量削减效果。
[0405] 此外，在本实施方式1中，基于中间复制比特串信息，提取包含多个中间复制比特串中彼此不重复的中间复制比特串和结合比特串中的至少一个的比特串的信息，来作为最终的复制比特串信息。由此，能够将多个复制比特串信息汇总成一个复制比特串信息，从而能够进一步减少差分数据的数据量。
[0406] 此外，在本实施方式1中，通过以比特为单位对多个数据D1_s和没有被移位的旧数据(数据D0)进行比较，来提取中间复制比特串信息。由此，能够提取出复制比特串的起始部分和末尾部分。
[0407] 此外，在本实施方式1中，差分数据中，复制比特命令(表示数据D0所包含的复制比特串的地址和长度的信息)和追加比特命令(表示数据D1所包含的追加比特串和追加比特串的长度的信息)会按数据D1(新数据)中所包含的复制比特串和追加比特串在该数据D1中的地址顺序进行排列。由此，能够尽可能地减少差分数据的数据量。
[0408] 此外，根据本实施方式1所涉及的数据更新装置11和信息处理装置21，基于差分数据生成装置1所生成的差分数据和旧数据，生成与新数据相同的数据。因此，能够使用相对较少的差分数据来进行数据的更新。
[0409] <实施方式2>
[0410] 实施方式1所涉及的差分数据生成装置1不对旧数据(文件F0的数据D0)进行移位，而以-7～7比特对新数据(文件F1的数据D1)进行移位。与此相对，本发明的实施方式2所涉及的差分数据生成装置1不对新数据(文件F1的数据D1)进行移位，而以-7～7比特对旧数据(文件F0的数据D0)进行移位。另外，在本实施方式2所涉及的差分数据生成装置1中，对于与以上说明的构成要素相同或类似的部分标注相同的参照标号，下面，以不同部分为主进行说明。
[0411] 图39是表示本实施方式2所涉及的差分提取部4和差分数据生成部6的详细结构的一个示例的框图。图39的结构是通过将图15的结构中的文件F1和文件F0相互交换而得到的。图39的结构中，-7比特移位部4a1～7比特移位部4a15按-7～7比特对旧数据(文件F0的数据D0)进行移位。即，-7比特移位部4a1～7比特移位部4a15将旧数据向其比特串的正向及逆向分别移动0，1，2，…，7比特，从而生成多个数据D0_-7～D0_7。所生成的多个数据D0_-7～D0_7存储于未图示的内部存储器。
[0412] 比特差分提取部4b1～4b15通过以比特单位和字节单位对数据D0_-7～D0_7和未进行移位的新数据(文件F1的数据D1)进行比较，并将这些数据中共通的比特串的信息提取作为中间复制比特串信息。比特差分提取部4b1～4b15将提取到的信息作为中间差分文件MDF_-7～MDF_7存储到中间数据存储部5。
[0413] 此外，实施方式1中所说明的图16、20、21在本实施方式2中按下述方式变更。
[0414] 在图16的步骤S4中，比特移位部4a(-7比特移位部4a1～7比特移位部4a15)对数据D0进行比特移位，将其移动比特移位量s，并将由此获得的数据D0_s存储到内部存储器。另外，s＝0的情况下的数据D0_0是没有被移位的数据D0。
[0415] 另外，在详细示出该步骤S4的图20的各步骤的处理中，对本实施方式2的数据D1、D0、D0_s分别进行实施方式1中对数据D0、D1、D1_s的处理。
[0416] 在图16的步骤S5中，复制比特串提取部4b(比特差分提取部4b1～4b15)基于数据D0_s和数据D1，以比特单位和字节单位来进行比较，从而提取出中间复制比特串。复制比特串提取部4b将该中间复制比特串信息作为中间差分文件MDF_s存储到中间数据存储部5。
[0417] 另外，在详细示出该步骤S5的图21的各步骤的处理中，对本实施方式2的数据D0_s、D1分别进行实施方式1中对数据D0、D1_s的处理。
[0418] 但在实施方式1的图21的步骤S28中，鉴于adr1Is、adr1Ie是移位后的数据D1_s中的中间复制比特串的起始的比特地址和末尾的比特地址，对adr1Is、adr1Ie进行了校正。
[0419] 与此相对，在本实施方式2中，由于adr1Is、adr1Ie是未被移位的数据D1中的中间复制比特串的起始的比特地址和末尾的比特地址，因此，复制比特串提取部4b不对adr1Is、adr1Ie进行校正。另一方面，在本实施方式2中，由于adr0Is、adr0Ie是移位后的数据D0_s中的中间复制比特串的起始的比特地址和末尾的比特地址，因此，复制比特串提取部4b将adr0Is、adr0Ie校正为比特移位部4a进行移位之前的地址。
[0420] 图40是表示利用本实施方式2所涉及的差分数据生成装置1来提取图6的复制比特串E(i)的处理的一个示例的图。以下，以图40为例，对本实施方式2所涉及的步骤S5的处理进行说明。图40中，应对数据D0进行移位的比特移位量s＝S(i)＝2。
[0421] 步骤S21中，复制比特串提取部4b根据数据D0_s(将数据D0移动了2比特后的数据)、以及数据D1来求取字节差分数据。此处求得的字节差分数据是与图40的比特串MI相关的数据，包含具有下述字段的复制命令。另外，图40的ofsEs(i)和bylngCopyE(i)用于下述复制命令的记载。
[0422] 复制源偏移量＝ofsEs(i)+1(数据D0_s中的偏移量)
[0423] 复制字节串长度＝bylngCopyE(i)
[0424] 在步骤S22中，复制比特串提取部4b获取上述复制命令。经过步骤S23～S25，在步骤S26中，复制比特串提取部4b将复制源偏移量(数据D0_s的ofsEs(i)+1)设定为OFS0，将复制字节串长度(bylngCopyE(i))设定为CBYTL。另外，OFS1表示数据D1中的追加字节串或复制字节串的起始字节串的偏移量，此处相当于图40的数据D1的ofsAs(i)+1。
[0425] 步骤S26中，复制比特串提取部4b从最下位比特起依次对数据D0_s的偏移量为OFS0-1＝ofsEs(i)的1字节和数据D1的偏移量为OFS1-1＝ofsAs(i)的1字节进行比较。由此获得比特串ST，并得到XBN＝4。其结果是获得数据D0_s中的中间复制比特串的起始的adr0Is(＝bitnEs_s(i))、以及数据D1中的中间复制比特串的起始的adr1Is(＝bitnAs(i))。
[0426] 步骤S27中，复制比特串提取部4b从最上位比特起依次对数据D0_s的偏移量为OFS0+CBYTL＝ofsEe(i)的1字节和数据D1的偏移量为OFS1+CBYTL＝ofsAe(i)的1字节进行比较。由此获得比特串EN，并得到YBN＝6。其结果是获得数据D0_s中的中间复制比特串的末尾的adr0Ie(＝bitnEe_s(i))、以及数据D1中的中间复制比特串的末尾的adr1Ie(＝bitnAe(i))。
[0427] 步骤S28中，复制比特串提取部4b使数据D0_s中的adr0Is(＝bitnEs_s(i))、以及adr0Ie(＝bitnEe_s(i))向比特移位部4a的移位(步骤S4)的相反方向进行移位。由此，获得数据D0的bitnEs(i)、bitnEe(i)。
[0428] <实施方式2的总结>
[0429] 根据上述本实施方式2所涉及的差分数据生成装置1，可获得与实施方式1相同的效果(例如，提高差分数据的数据量削减效果等)。
[0430] <实施方式1和实施方式2的变形例>
[0431] 在以上所说明的结构中，对数据整体为比特串的情况进行了说明。但并不限于此，也可以混合存在字节单位的数据和比特串数据(比特单位的数据)。
[0432] 此外，在以上的说明中，在步骤S8(图16)中，先求得复制比特串信息，再在步骤S9中通过从新数据中去除复制比特串来求得追加比特串信息。但并不限于此，也可以先求得追加比特串信息，然后通过从新数据中去除追加比特串来求取复制比特串信息。
[0433] 并且，在以上所说明的差分数据中，复制比特命令和追加比特命令会按数据D1中所包含的复制比特串和追加比特串在该数据D1中的地址的升序进行排列。但它们也可以不按升序来排列，例如可以按降序来排列。若对上述方式进行概括，则复制比特命令和追加比特命令只要按数据D1中所包含的复制比特串和追加比特串在该数据D1中的地址顺序进行排序即可。
[0434] 此外，上述所说明的结构中，在图21的步骤S23、S24、S25、S26、S27中，复制比特串提取部4b通过从比特单位和字节单位这两方面来对多个数据D1_s和未被移位的旧数据进行比较，从而提取出中间差分文件MDF_s。但并不限于此，复制比特串提取部4b可以仅以比特单位对多个数据D1_s和未被移位的旧数据进行比较，由此提取出中间差分文件MDF_s。
[0435] 并且，差分数据生成装置1也可以适用于通过适当组合可搭载于车辆的导航装置、便携式导航装置、通信终端(例如，移动电话、智能手机和平板电脑等移动终端)、安装于这些设备的应用程序的功能、以及服务器等而作为系统构建的差分数据生成系统。该情况下，上述所说明的差分数据生成装置1的各功能或各构成要素可以分散地配置在构建所述系统的各设备，也可以集中配置在任意的设备。
[0436] 此外，本发明可以在该发明的范围内对各实施方式及各变形例自由地进行组合，或对各实施方式及各变形例进行适当的变形、省略。
[0437] 本发明进行了详细的说明，但上述说明在所有方式中均为示例，本发明并不限于此。未例示的无数变形例可解释为在不脱离本发明的范围内能够设想得到。
[0438] 标号说明
[0439] 1差分数据生成装置、4a比特移位部、4b复制比特串提取部、4c追加比特串提取部、6差分数据生成部、11数据更新装置、21信息处理装置。