存储程序、存储方法、存储装置、解压缩程序、解压缩方法和解压缩装置

技术领域

本发明涉及一种数据压缩/解压缩技术。

背景技术

在被称为哈夫曼(Huffman)编码的压缩/解压缩算法中，包括在要 被压缩的数据中的每个符号(字符等)与被分配给该符号的压缩码之间的 关系由二叉树结构指示。该二叉树被称为哈夫曼树。哈夫曼树的每个叶部 分(尾端)的数据指示符号，并且与该符号相对应的压缩码指示从哈夫曼 树的根(开始端)至叶的搜索路径。在使用哈夫曼编码的解压缩处理中， 通过反复从经压缩数据读出1位的数据并且确定在哈夫曼树中的与所读 取数据相对应的分支(树结构的根或节点部分)来执行对哈夫曼树的搜索。 通过执行对哈夫曼树的搜索来识别与压缩数据中的位串(即，压缩码)相 对应的符号。

在针对哈夫曼编码的压缩/解压缩算法中，包括指示引用(reference) 目的地的信息(诸如指针；在下文中被称为指针)以及解压缩字符码的数 据结构被包括在哈夫曼树的数据结构中的每个中。在对哈夫曼树的搜索中 进行的分支的确定是通过根据从压缩数据所读出的位选择指示下一个引 用目的地的指针执行的。也就是说，根据从压缩数据所读出的位来确定包 括在每个分支的数据结构中的多个指针中的哪个指针被使用。下一个要被 引用的数据结构由与从压缩数据所读出的位相对应的指针指示。在经历了 根据压缩码的末位进行的确定的数据结构中，指示与压缩码相对应的符号 的叶的数据结构被存储。

同时，存在有从压缩数据读出预定长度位串并且基于所读取的位串来 识别解压缩字符数据的技术(例如，专利文献1)。在哈夫曼编码中，根 据出现的频率来设置压缩码的码长，所以存在有其码长小于预定长度的压 缩码。因此，通过额外的位被添加至压缩码的预定长度位串以及到包括解 压缩字符数据的数据结构的关联指针来指示解压缩字符数据与压缩码之 间的对应关系。不同位被添加至同一压缩码的预定长度位串与同一指针关 联。在使用该算法的解压缩处理中，从压缩数据读出包括额外的位的预定 长度位串，并且基于所读取的预定长度位来获取指针，以及基于所获取的 指针来读出解压缩字符数据。此外，下一次从压缩数据读出预定长度位串 的读出位置被设置成从上一次读出位置前进压缩码长度的位的位置。因 此，基于用于根据出现的频率来分配压缩码与码长的压缩/解压缩算法， 解压缩处理基于从压缩数据所读出的位而执行。

在以上所描述的技术中，解压缩的字符串是根据从压缩数据所读取的 位串获取的；因此，同一指针被冗余地存储在不同的位被添加至同一压缩 码的位串中的每个位串中。

专利文献

专利文献1：日本公开专利公报第2010-93414号

专利文献2：国际公布册第WO 2008/142800号

发明内容

技术问题

根据以上描述的技术，在解压缩处理中产生两个引用处理，即基于读 取的位串对指针的引用以及基于指针对解压缩字符数据的引用。

本发明的一个方面是减小解压缩处理的量。

根据一个方面，一种使得计算机执行下述的存储程序：将要被压缩的 字符数据存储在存储区域内的由多种类型的预定长度位串指定的相应的 存储位置中，该多种类型的预定长度位串包括分配给字符数据的压缩码， 在该存储区域中，存储位置由预定长度位串指定。

根据一个方面，一种用于使得计算机执行下述的存储方法：将要被压 缩的字符数据存储在存储区域内的由多种类型的预定长度位串指定的相 应的存储位置中，该多种类型的预定长度位串包括分配给字符数据的压缩 码，在该存储区域中，存储位置由预定长度位串指定。

根据一个方面，一种存储装置包括：存储单元，该存储单元包括存储 区域，在该存储区域中，存储位置由预定长度位串指定；以及控制单元， 该控制单元将要被压缩的字符数据存储在存储区域内的由多种类型的预 定长度位串指定的相应的存储位置中，该多种类型的预定长度位串包括分 配给字符数据的压缩码。

根据一个方面，一种使得计算机执行下述的解压缩程序：当在压缩文 件中的读出位置从存储区域读出包括共有(common)压缩码的多种类型 的预定长度位串时，从由所读取的预定长度位串指定的存储位置读出解压 缩字符数据和码长，在该存储区域中，与压缩码相对应的解压缩字符数据 和压缩码的码长被存储在由包括该压缩码的预定长度位串指定的相应的 存储位置中；将从压缩文件所读出的预定长度位串转换成解压缩字符数 据；以及基于码长来调节读出位置。

根据一个方面，一种用于使得计算机执行下述的解压缩方法：当在压 缩文件中的读出位置从存储区域读出包括共有压缩码的多种类型的预定 长度位串时，从由所读取的预定长度位串指定的存储位置读出解压缩字符 数据和码长，在该存储区域中，与压缩码相对应的解压缩字符数据和压缩 码的码长被存储在由包括该压缩码的预定长度位串指定的相应的存储位 置中；将从压缩文件所读出的预定长度位串转换成解压缩字符数据；以及 基于码长来调节读出位置。

根据一个方面，一种解压缩装置，包括：存储单元，该存储单元包括 存储区域，在该存储区域中，与共有压缩码相对应的解压缩字符数据和压 缩码的码长被存储在由包括该压缩码的多种类型的预定长度位串指定的 相应的存储位置中；读出单元，该读出单元当在压缩文件中的读出位置读 出包括压缩码的预定长度位串时，将解压缩字符数据和码长从由所读取的 预定长度位串指定的存储位置读出到存储单元；转换单元，该转换单元将 从压缩文件读出的预定长度位串转换成解压缩字符数据；以及调节单元， 该调节单元基于码长对读出位置进行调节。

发明的有益效果

根据本发明的一个方面，可以减小解压缩处理的量。

附图说明

图1示出了哈夫曼树的示例。

图2示出了数据结构之间的引用关系。

图3示出了压缩/解压缩字典的数据结构的示例。

图4示出了修改的哈夫曼树的示例。

图5示出了压缩/解压缩字典的数据结构的示例。

图6示出了压缩/解压缩字典的修改的数据结构的示例。

图7示出了计算机1的功能块的配置示例。

图8示出了计算机1的硬件配置示例。

图9示出了计算机1的软件配置示例。

图10示出了使用计算机1的系统的配置示例。

图11示出了通过压缩单元101执行的压缩处理的流程的示例。

图12示出了生成压缩/解压缩字典数据的处理的流程的示例。

图13示出了频率制表表格T7的示例。

图14示出了字符串列表T8的示例。

图15示出了码长分布表格T9的示例。

图16示出了转换处理的流程的示例。

图17示出了通过解压缩单元102执行的解压缩处理的流程的示例。

图18示出了转换处理的流程的示例。

图19示出了通过检索单元103执行的检索处理的流程的示例。

图20示出了压缩/解压缩字典数据T10的示例。

图21示出了交叉检查处理的流程的示例。

具体实施方式

首先，说明使用哈夫曼编码的压缩/解压缩处理和修改示例。

图1示出了哈夫曼树的示例。在图1中示出的哈夫曼树表示字符数据 (0，>，<br>，1，<，a，s，t，x)与压缩码之间的对应关系。

字符数据(0，>，<br>，1，<，a，s，t，x)仅是用于说明哈夫曼树 的字符数据的示例。作为要被压缩的字符数据，例如，使用诸如数字、字 母、平假名字符、片假名字符、汉字字符、阿拉伯字母、西里尔字母或符 号(两字节或一字节)的字符码，包括多个字符的组合的字符串(保留字)， 以及固定长度位串等。在图1中示出的列表T1是根据在压缩目标数据中 的出现的频率排序的要被压缩的字符数据的列表。此外，在要被压缩的字 符数据中，通过进一步使用不同于列表T1的列表来管理其位长与字符码 不同的字符数据(在图1的示例中，保留字“<br>”等)。在列表T1中 的字符数据分别存储在哈夫曼树的叶的数据结构HL(HL1至HL9)中。

列表T1中的每条字符数据与压缩码之间的对应关系由从哈夫曼树的 根的数据结构HR到叶的数据结构HL(HL1至HL9)的搜索路径来指示。 在根的数据结构HR和节点的数据结构HN(HN11、HN12、HN21至HN23、 HN31和HN32)中的每个中，依赖于位为“0”还是为“1”而存在有分 支，并且压缩码由在搜索路径上的分支中使用的位来指示。此外，在哈夫 曼编码中，字符数据的出现频率越高，被分配给该字符数据的压缩码的长 度越短；字符数据的出现的频率越低，被分配给该字符数据的压缩码的长 度越长。例如，字符数据“t”的压缩码由到存储有字符数据“t”的叶的 数据结构HL8的搜索路径来指示。通过顺序地追踪由位“1”指示的从根 HR至节点HN12的路径、由位“1”指示的从节点HN12至节点HN23 的路径、由位“1”指示的从节点HN23至节点HN32的路径、以及由位 “0”指示的从节点HN32至叶HL8的路径来进行从根HR至数据结构 HL8的搜索。在图1中，“1110”为被分配给字符数据“t”的压缩码，其 是指示从根HR至叶的数据结构HL8的搜索路径中包括的路径的位串。

图2示出了数据结构之间的引用关系。通过使用在图2中示出的指针 引用的关系来进行采用图1所说明的搜索。在HX1至HX3中指示根的数 据结构HR和节点的数据结构HN的附注。附注HX1包括到高层 (high-order)数据结构的指针、指示指针被存储的第一标识符(在图2 中的“0”)、到(第一)低层(low-order)数据结构的指针、指示指针被 存储的第二标识符(在图2中的“0”)、以及到(第二)低层数据结构的 指针。附注HX2包括到高层数据结构的指针、指示字符码被存储的标识 符(在图2中的“1”)、字符码、指示指针被存储的标识符(在图2中的 “0”)、以及到低层数据结构的指针。附注HX3包括到高层数据结构的指 针、指示(第一)字符码被存储的标识符(在图2中的“1”)、(第一)字 符码、指示(第二)字符码被存储的标识符(在图2中的“1”)、以及(第 二)字符码。根的数据结构和节点的数据结构HN是附注HX1至HX3中 任一个中的数据结构。此外，可以在叶的数据结构中存储指示字符串的字 符码(保留字)被存储的存储位置的指针而不是存储字符码。该指针指示 在随后要描述的列表T8中的对应字符串的存储位置。基于从数据结构所 读出的标识符，确定从数据结构所读出的信息是指针还是字符码。例如， 预先确定读出到(第一)标识符的指针的偏移以及读出到(第二)标识符 的指针的偏移。例如，当在数据结构中存储的指针和标识符或字符码和标 识符的相应存储位置为32位，并且读取位是x时，通过32×(1+x)来 计算读出标识符的偏移。

在解压缩处理中，基于压缩码读出与压缩码相对应的字符数据。例如， 当从压缩数据所读出的位是“0”时，引用(第一)低层数据结构；当位 是“1”时，引用(第二)低层数据结构。然后，通过使用与从压缩数据 所读出的位相对应的指针来识别下一个要被引用的数据结构。例如，假设 按照“1110…”的顺序从压缩数据读出数据。则在根的数据结构HR中的 到(第二)低层数据结构的指针是到节点的数据结构HN12的指针，并且 基于该指针来引用节点的数据结构HN12。此外，在节点的数据结构HN12 中的到(第二)低层数据结构的指针是到节点的数据结构HN23的指针， 并且基于该指针来引用节点的数据结构HN23。在节点的数据结构HN23 中的到(第二)低层数据结构的指针是到节点的数据结构HN32的指针， 并且基于该指针来引用节点的数据结构HN32。字符码被存储在节点的数 据结构HN32中，并且第四个压缩码是“1”，所以引用在其中存储有与压 缩码“1110”相对应的字符数据“t”的叶的数据结构HL8。在叶的数据 结构中，添加了指示包括在数据结构中的信息是字符码的标识符(在图2 中的“1”)；因此，基于该标识符来确定获取字符码而不是获取指针。

另一方面，在压缩处理中，基于字符数据来读出压缩码。通过基于到 高层数据结构的指针引用数据结构来从在其中存储有字符数据的叶的数 据结果中获得压缩码。然而，在压缩处理中，例如，替代追踪哈夫曼树， 可以使用如下方法：生成使字符数据与压缩码关联的表格，并且基于所生 成的表格来获取压缩码。

图3示出了压缩/解压缩字典的数据结构T3的示例。在图3中示出的 压缩/解压缩字典包括数据头区域的数据结构HH、根的数据结构HR和节 点的数据结构HN。数据头区域的数据结构HH包括关于根的数据结构 HR和节点的数据结构HN的信息。数据结构HH包括在根的数据结构 HR的存储空间上的开始地址以及根的数据结构HR和节点的数据结构 HN的数据大小。

在图3的示例中，图2中示出的根的数据结构HR和叶的数据结构 HN(HN11、HN12、HN21至HN23,、HN31和HN32)依次被存储。如 图3所示，当数据结构是连续的时，在根的数据结构HR和节点的数据结 构HN中包括的指针可以是与存储在数据头区域HH中的开始地址的偏 移。例如，当根的数据结构HR和节点的数据结构HN的数据大小是32 ×3位时，到节点的数据结构HN21的指针由32×3×3来指示。然后， 可以确定节点的数据结构HN21存在于与开始地址偏移32×3×3相对应 的位置处。

图4示出了修改的哈夫曼树的示例。另外在图4中，正如图1一样， 0，>，<br>，1，<，a，s，t，x是要被压缩的字符数据的示例。此外， 同样在图4中示出的修改的哈夫曼树中，将与在图1中示出的哈夫曼树相 同的压缩码分配给字符数据。在图4中，字符数据和分配给该字符数据的 压缩码的码长被存储在叶的数据结构KL(KL1至KL9)中。叶的数据结 构KL的内容如在图4的表格T4中所指示地一样。

在图4中示出的修改示例中，基于4位的位串来执行对在根的数据结 构KR中的分支的确定。在图4的示例中，分支由4位的位串来确定；然 而，当然，根据要被压缩的字符数据的类型的数量，该确定可以被修改为 通过具有不同于4位的位的位串来执行。例如，当从压缩数据读出位串 “0100”时，叶的数据结构KL2被读出。此外，同样当从压缩数据读出 位串“0101”时，叶的数据结构KL2被读出。也就是说，在确定根的数 据结构KR中的分支时，在不同的位串“0100”和“0101”中的任一个位 串被读出的情况下，到同一叶的数据结构KL2的指针被读出，并且基于 该指针来执行叶的数据结构的读出。

此外，尽管从压缩数据中以4位读出，但是与存储在叶的数据结构 KL2中的字符数据“>”相对应的压缩码是“010”。因此，根据存储在叶 的数据结构KL2中的码长，从压缩数据读出位的位置不是以实际读取的 4位而是以3位前进。因此，从压缩数据中所读取的比实际分配的压缩码 多出的位被调节。此外，正如在图2中示出的哈夫曼树一样，同样在根的 数据结构KR中，根据读取位串来确定读出指针的偏移。

图5示出了在图4中示出的修改的哈夫曼树中的压缩/解压缩字典数 据T5的数据结构的示例。压缩/解压缩字典数据T5包括数据头区域HH (包括数据头的数据结构KH1和数据头的数据结构KH2)、根的数据结 构KR、以及叶的数据结构KL(KL1至KL9)。数据头的数据结构KH1 包括根的数据结构KR在存储空间上的开始地址和根的数据结构KR的数 据大小。数据头的数据结构KH2包括叶的数据结构KL在存储空间上的 开始地址和叶的数据结构KL的数据大小。

在压缩/解压缩字典数据T5的根的数据结构KR中，到叶的数据结构 的指针分别存储在基于4位的位串“0000”至“1111”确定的偏移位置中。 当到叶的数据结构的指针的大小是32位时，偏移由例如从数据结构T5 的开始点起的4位的位串×32的位置来指示。到在其中存储有其压缩码 长比4位短的字符数据的叶的数据结构的指针被存储在多个位置。例如， 压缩码“010”被分配给字符数据“>”，并且压缩码长比4位短1位。在 该情况下，到在其中存储有字符数据“>”的叶的数据结构KL2的指针被 存储在由通过将1位冗余地添加到压缩码“010”而获得的4位的位串 “0100”和“0101”所指定的位置中。以该方式，通过冗余地存储到叶的 数据结构的指针，执行基于读取的位串对字符数据的读出。

压缩/解压缩字典数据T5的叶的数据结构KL包括要被压缩的字符码 以及分配给该字符码的压缩码的码长。此外，根的数据结构KR各自包括 指示在其中存储有指针的标识符，并且叶的数据结构KL各自包括指示在 其中存储有字符码的标识符。

在图4和图5的修改示例中，针对字符数据和分配给该字符数据的压 缩码的配对，同一指针被存储在多个位置中，从而可以基于读取位串来识 别指针。

在图4和图5中示出的修改的哈夫曼树中，不包括到节点的数据结构 的指针。因此，不存在有包括到节点的数据结构的指针和到叶的数据结构 的指针两者的数据结构。因此，例如，即使包括在叶的数据结构中的信息 诸如字符数据和压缩码长而不是到叶的数据结构的指针被存储的情况下， 也不会产生字符数据和指针被混合在数据结构中的情况。也就是说，即使 在不检查数据结构的内容的情况下，也可以从压缩/解压缩字典数据中获 取要被压缩的字符数据组。此外，压缩码长与字符数据存储在一起，所以 可以基于压缩码长来计算多少条相同的字符数据被依次地存储在压缩/解 压缩字典中。因此，当从压缩/解压缩字典读出字符数据时，可以跳过冗 余的字符数据。

因此，在本实施方式中，例如，使用在图6中示出的压缩/解压缩字 典数据。在图6中示出的压缩/解压缩字典数据T6包括数据头区域H和 叶的数据结构L。数据头区域H包括叶的数据结构L在存储空间上的开 始地址和该叶的数据结构L的数据大小。在叶的数据结构L中，与位串 相对应的字符数据和压缩码长分别存储在基于4位的位串“0000”至“1111” 确定的偏移位置中。当数据结构L的大小是32位时，读出每个叶的数据 结构的位置，例如，与叶的数据结构L的开始地址的偏移由4位的位串 ×32的位置来指示。在其中存储有所分配的压缩码的压缩码长比4位短 的字符数据的叶的数据结构L被存储在多个位置中。例如，压缩码“010” 被分配给字符数据“>”，并且压缩码长比4位短1位。在该情况下，在压 缩/解压缩字典数据T6中，在其中存储有字符数据“>”的叶的数据结构 被存储在由通过将1位冗余地添加到压缩码“010”而获得的4位的位串 “0100”和“0101”所指定的位置中。以该方式，通过冗余地存储叶的数 据结构L，执行基于读取的位串对字符数据的读出。

例如，在使用压缩/解压缩字典数据T6的解压缩处理中，当读出包括 字符码的位串时，执行从数据头区域H对叶的数据结构L的开始地址的 读出，然后基于所读取的位串来执行与所读取的开始地址的偏移的计算。 此外，通过基于所计算的偏移执行字符数据和码长的读取来执行解压缩。 另一方面，在使用压缩/解压缩字典数据T5的解压缩处理中，当读出包括 字符码的位串时，执行从数据头的数据结构KH1对根的数据结构KR的 开始地址的读取，然后基于所读取的位串来执行与所读取的开始地址的偏 移的计算。当基于所计算的偏移读出指针时，进一步执行从数据头的数据 结构KH2中读取叶的数据结构KL的开始地址。基于所读取的指针执行 与所读取的开始地址的偏移的计算，作为结果，基于所计算的偏移来执行 字符数据和码长的读出。如上所述，在使用压缩/解压缩字典数据T5的解 压缩处理中，访问数据头区域的次数大于使用压缩/解压缩字典数据T6的 解压缩处理。在使用压缩/解压缩字典数据T6的解压缩处理中，没有执行 对数据头区域KH1的访问以及对根的数据结构KR的访问，而在使用压 缩/解压缩字典数据T5的解压缩处理中执行对数据头区域KH1的访问以 及对根的数据结构KR的访问。因此，使用压缩/解压缩字典数据T6的解 压缩处理期望获得比使用压缩/解压缩字典数据T5的解压缩处理更快的 解压缩速度。

此外，例如，假设在压缩/解压缩字典数据T5中的节点和叶的数据结 构与在压缩/解压缩字典数据T6中的叶的数据结构具有相同的数据大小。 然后，叶的数据结构L适合于压缩/解压缩字典数据T5中存储有指针的节 点的数据结构KN。因此，压缩/解压缩字典数据T6的数据大小变得比压 缩/解压缩字典数据T5的数据大小小要被压缩的字符数据的类型的数量 与每个数据结构的数据大小的乘积。

根据本实施例的另一方面，抑制了指针引用处理，并且因此，可以提 高解压缩速度。

随后说明本实施方式的细节。

图7示出了计算机1的功能块的配置示例。计算机1包括控制单元 10和存储单元11。控制单元10对整个计算机1进行控制，并且对存储在 存储单元11中的数据执行压缩处理、解压缩处理和检索处理。存储单元 11将经历了由控制单元10执行的压缩处理、解压缩处理和检索处理的数 据以及在处理中使用的数据存储在其中。此外，当控制单元10执行处理 时存储单元11被用作工作区。例如，存储单元11可以存在于计算机1的 外部，并且控制单元10可以通过与计算机1通信来访问存储在存储单元 11中的数据。

控制单元10包括压缩单元101、解压缩单元102和检索单元103。压 缩单元101对存储在存储单元11中的要被压缩的数据执行压缩处理；解 压缩单元102对存储在存储单元11中的数据执行解压缩处理；检索单元 103响应于检索请求来执行存储在存储单元11中的要被检索的数据的检 索处理。

压缩单元101包括生成单元1011和转换单元1012。生成单元1011 基于要被压缩的数据以及要被压缩的字符数据的列表来生成在图6中示 出的压缩/解压缩字典数据。转换单元1012基于由生成单元1011生成的 压缩/解压缩字典数据来将要被压缩的数据转换成压缩码。随后将描述由 生成单元1011和转换单元1012执行的处理的细节。

解压缩单元102包括转换单元1021和调节单元1022。转换单元1021 基于与要被解压缩的数据相对应的压缩/解压缩字典数据来将要被解压缩 的数据转换成字符数据。调节单元1022基于压缩/解压缩字典数据来调节 转换单元1021从其读出要被解压缩的数据的读出位置。随后将描述由转 换单元1021和调节单元1022执行的处理的细节。

检索单元103包括搜索单元1031、调节单元1032和交叉检查单元 1033。搜索单元1031基于包括在检索请求中的检索条件来设置用于提取 要被交叉检查的对象的提取条件，并且搜索在压缩数据中满足提取条件的 任何数据，以及解压缩满足提取条件的压缩数据。调节单元1032基于压 缩/解压缩字典数据来调节搜索单元1031从其读出压缩数据的读出位置。 交叉检查单元1033采用检索条件来交叉检查由搜索单元1031通过解压缩 获得的字符数据。随后将描述由搜索单元1031、调节单元1032和交叉检 查单元1033执行的处理的细节。

图8示出了计算机1的硬件配置示例。计算机1包括例如处理器301、 随机存取存储器(RAM)302、只读存储器(ROM)303、驱动装置304、 存储介质305、输入接口(I/F)306、输入装置307、输出接口(I/F)308、 输出装置309、通信接口(I/F)310、存储区域网络(SAN)接口(I/F) 311、以及总线312等。通过总线312连接这些硬件。

RAM 302是能够进行数据读/写的存储装置；作为RAM 302可以使 用，例如，诸如静态RAM(SRAM)和动态RAM(DRAM)的半导体 存储器、或无论是否具有RAM的闪速存储器等。ROM 303包括可编程 ROM(PROM)等。驱动装置304是执行读取记录在存储介质305上的 信息或将信息写在存储介质305上至少两者之一的设备。存储介质305 将由驱动装置304写的信息存储在其中。存储介质305是例如，硬盘、诸 如固态驱动器(SSD)的闪速存储器、或如致密盘(CD)、数字多功能盘 (DVD)和蓝光盘的存储介质。此外，例如，计算机1设置有针对存储 介质的若干类型中的每个类型的驱动装置304和存储介质305。

输入I/F 306被连接至输入装置307，并且将从输入装置307接收的 输入信号传传送到处理器301。输出I/F 308被连接至输出装置309，并且 使得输出装置309根据来自处理器301的指令进行输出。通信I/F 310经 由网络3来控制通信。SAN I/F 311经由存储区域网络来控制与被连接至 计算机1的存储装置的通信。

输入装置307是根据操作发送输入信号的装置。输入信号是例如键 盘、诸如安装在计算机1的主机身上的按钮的键装置、以及诸如鼠标和触 摸板的指点装置。输出装置309是根据计算机1的控制来输出信息的装置。 输出装置309是例如，诸如显示器的图像输出装置(显示装置)以及诸如 扬声器的音频输出装置。此外，例如，诸如触摸屏的输入/输出设备被用 作输入装置307和输出装置309。此外，输入装置307和输出装置309可 以是例如未包括在计算机1中并且外部地连接至计算机1的外部装置。

处理器301读取存储在ROM 303或存储介质305中的程序并且将程 序加载到RAM 302上，以及根据所读取的程序的过程执行控制单元10 的处理。此时，RAM 302用作处理器301的工作区域。存储单元11的功 能通过以下情况实现：在该情况中，ROM 303和存储介质305在其中存 储有程序文件(应用程序24、中间件23、和OS 22等)以及数据文件(要 被压缩的数据文件和压缩文件)，并且RAM 302被用作处理器301的工 作区域。采用图9说明通过处理器301读出的程序。

图9示出了在计算机1上运行的程序的配置示例。控制在图8中示出 的硬件组21的操作系统(OS)22在计算机1上运行。处理器301根据依 照OS 22的过程进行操作，并且控制/管理硬件组21，从而该硬件组21 根据应用程序24或中间件23来执行处理。此外，在计算机1中，中间件 23或应用程序24被加载到RAM 302上并且由处理器301执行。

处理器301基于包括在中间件23或应用程序24中的压缩功能来执行 处理，从而(通过控制硬件21基于OS 22执行处理)实现压缩单元101 的功能。此外，处理器301基于包括在中间件23或应用程序24中的解压 缩功能来执行处理，从而(通过控制硬件21基于OS 22执行处理)实现 解压缩单元102的功能。此外，处理器301基于包括在中间件23或应用 程序24中的检索功能来执行处理，从而(通过控制硬件21基于OS 22 执行处理)实现检索单元103的功能。压缩功能、解压缩功能以及检索功 能可以被限定在应用程序24中，或可以是通过根据应用程序24被调用而 执行的中间件23的功能。

图10示出了使用计算机1的系统的配置示例。在图10中示出的系统 包括计算机1a、计算机1b、基站2以及网络3。计算机1a通过有线连接 或无线连接至少两者之一而被连接至连接有计算机1b的网络3。例如， 在图10示出的系统中，计算机1a获取由计算机1b执行根据本实施例的 压缩处理而被压缩的数据文件，并且通过执行根据本实施例的解压缩处理 来对从计算机1b获取的压缩文件进行解压缩。相反地，例如在图10示出 的系统中，计算机1b获取由计算机1a执行根据本实施例的压缩处理而被 压缩的数据文件，并且通过执行根据本实施例的解压缩处理来对从计算机 1a获取的压缩文件进行解压缩。此外，例如，在图10示出的系统中，计 算机1a获取由计算机1b执行根据本实施例的压缩处理而被压缩的数据文 件，并且通过执行根据本实施例的检索处理来对从计算机1b获取的压缩 文件进行检索。相反地，例如在图10示出的系统中，计算机1b获取由计 算机1a执行根据本实施例的压缩处理而被压缩的数据文件，并且通过执 行根据本实施例的检索处理来对从计算机1a获取的压缩文件进行检索。 此外，可以在计算机1a中执行压缩处理、解压缩处理以及检索处理中的 至少两个处理。此外，可以在计算机1a或计算机1b中执行压缩处理和检 索处理，并且可以将检索请求从一个计算机发送至另一计算机。

接下来，说明在计算机1中执行的压缩处理的过程。

图11示出了由压缩单元101执行的压缩处理的流程的示例。当响应 于应用程序24的功能或由用户所输入的指令已经调用了压缩处理功能时 (步骤S100)，压缩单元101从存储单元11读出在调用压缩处理功能时 指定的要被压缩的数据文件(步骤S101)。基于在步骤S101处读取的要 被压缩的数据文件，生成单元1011生成在图6中示出的压缩/解压缩字典 数据T6(步骤S102)。随后将采用图12描述由生成单元1011进行的压 缩/解压缩字典数据T6的生成。然后，转换单元1012基于由生成单元1011 生成的压缩/解压缩字典数据T6来将要被压缩的数据文件转换成压缩码 (步骤S103)。随后将采用图16描述通过转换单元1012进行的到压缩码的 转换。当由转换单元1012执行将要被压缩的数据到压缩码的转换时，压 缩单元101通过将经由转换所获得的数据进行归档来生成压缩文件(步骤 S104)。当压缩单元101获得压缩文件时，终止在步骤S100处调用的压缩 处理(步骤S105)。

图12示出了生成压缩/解压缩字典数据T6的处理的流程的示例。当 执行在图11中的步骤S102处的处理(S200)时，生成单元1011将包括 在步骤S101处读出的要被压缩的数据文件中的字符数据的出现的频率制 表(S201)。在S201处的处理中，保留用于存储压缩/解压缩字典数据的 存储区域，并且生成数据头的数据结构H。生成单元1011从要被压缩的 数据文件中顺序地读出字符数据，并且将读出的结果反映在图13中示出 的频率制表表格T7中。

图13示出了频率制表表格T7的示例。在图13中示出的示例中，在 包括在频率制表表格T7中的记录中的每个记录中，字符数据和指示该字 符数据的出现的次数的计数值以关联的方式被存储。存储在频率制表表格 T7中的字符数据是例如，诸如在要被压缩的数据文件中使用的字符码系 统中的数字、字母、平假名字符、片假名字符、汉字字符、阿拉伯字母以 及西里尔字母的至少部分的字符。对于汉字字符而言，例如，可以仅将针 对日常使用指定的汉字的字符码存储在频率制表表格T7中。此外，字符 数据还包括例如不同于字符码的固定长度数据。例如，由于与滑动窗口 (sliding window)中的地址一致的数据长度信息输出作为压缩码串，所 以基于LZ77获得的压缩码串具有固定长度。在压缩算法诸如ZIP中，相 对于基于LZ77获得的固定长度的压缩码串来使用哈夫曼编码。此外，字 符数据可以包括字符串。例如，字符数据包括在图14中示出的字符串列 表T8中包括的字符串。在本实施例中，作为仅用于说明的示例，包括在 频率制表表格T7中的字符数据应当是在图1中的列表T1中示出的字符 数据。

在S201的处理中，生成单元1011从要被压缩的数据文件中顺序地读 出数据。此时，生成单元1011读出例如在要被压缩的数据文件中使用的 字符码系统中具有一个字母的位长的数据。生成单元1011检测例如与从 频率制表表格T7读取的数据一致的字符码，并且使存储在所检测的记录 中的计数值递增一。当存储在字符串列表T8中的字符串还包括在频率制 表表格T7中时，在从要被压缩的数据文件读出数据时，生成单元1011 首先确定是否是对存储在字符串列表T8中的字符串的读出。在该确定中， 当确定是对存储在字符串列表T8中的字符串的读出时，生成单元1011 读出字符串，并且在频率制表表格T7中，使包括读取的字符串的记录中 的计数值递增一。当在该确定中确定不是对存储在字符串列表T8中的字 符串的读出时，生成单元1011读出具有一个字母的位长的数据，并且将 读出的结果反映在频率制表表格T7的计数值中。

当在S201处的频率制表处理完成时，生成单元1011基于反映在频率 制表表格T7中的制表的结果来按频率的顺序对频率制表表格T7进行排 序(S202)。此外，生成单元1011基于字符数据在要被压缩的数据文件中 出现的频率的分布来计算压缩码长的分布(S203)。所计算的压缩码长被 存储在图15中示出的码长分布表格T9中。

图15示出了码长分布表格T9的示例。在图15的示例中，字符数据 的数量与码长1至4中的每个码长关联。在图15的示例中，码长为1的 字符数据的数量是0，码长为2的字符数据的数量是1，码长为3的字符 数据的数量是4，以及码长为4的字符数据的数量是4。

根据要被压缩的字符数据的频率的分布来计算码长的分布。例如，针 对要被压缩的每条字符数据，可以基于频率来设置码长。例如，当在要被 压缩的文件中出现的频率是整个压缩文件的1/(2的n次幂)的频率时， 可以分配n位压缩码。

当执行了在S203处的处理时，生成单元1011将压缩码分配给要被压 缩的每个字符数据(S204至S210)。当存在k种类型的要被压缩的字符 数据时，例如以排序的顺序反复地执行对要被压缩的第一种至第k种字符 数据的压缩码的分配。此外，用i表示对压缩码的分配已执行了多少次。 i的初始值是1。

首先，确定i是否小于k(S204)。当i达到k(在S204处为否)时， 针对要被压缩的字符数据的压缩码的分配以及压缩/解压缩字典的数据结 构的生成完成，所以终止生成压缩/解压缩字典数据的处理(S211)。

当i小于k(在S204处为是)时，生成单元1011从排序的频率制表 表格中读出要被压缩的字符数据的第i条字符数据(S205)。此外，生成 单元1011从码长分布表格T9中读出与所读取的第i条字符数据对应的码 长，并且根据所读取的码长来计算拷贝数C(S206)。拷贝数C指示所读 取的字符数据的再现的次数。通过例如底2的(预定长度－所读取的码长) 次幂来表示拷贝数C。

此外，生成单元1011生成在S205处读取的字符数据的叶的结构 (S207)。在S207处生成的叶的结构包括第i条字符数据的字符码和码长。 此外，叶的结构包括交叉检查标志。S206和S207可以调换顺序。

然后，生成单元1011复制与在S206处计算的拷贝数C一样多的在 S207处生成的叶的结构的拷贝，并且将通过复制获得的信息存储在存储 单元11的存储区域中(S208)。然后，生成单元1011根据拷贝数C更新 写信息的位置(S209)。例如，当每个叶的结构是32位时，写位置以32 ×拷贝数C前进。此外，生成单元1011使i的值递增一(S210)，并且再 次执行在S204处的处理。

图16示出了转换处理的流程的示例。当执行在图11中示出的步骤 S103处的处理(S300)时，首先，转换单元1012确定在要被压缩的数据 文件中是否存在有剩余的任何字符数据(S301)。然后，转换单元1012 从要被压缩的数据文件读出字符数据(S302)。转换单元1012通过引用由 生成单元生成的压缩/解压缩字典数据T6来搜索与所读取的字符数据一 致的字符数据(S303)。转换单元1012基于存储有与所读取的字符数据一 致的字符数据的叶的结构的存储位置来计算压缩码，并且将所计算的压缩 码写入存储单元11的存储位置中(S304)。通过将叶的结构的存储位置(与 叶的数据结构L的开始地址的偏移)除以每个叶的结构的数据大小来获 得压缩码。当执行了在S304处的处理时，转换单元1012再次执行在S301 处的处理。转换单元1012反复地执行在S301至S304处的处理直到在要 被压缩的数据文件中不存在有剩余的字符数据为止，并且终止转换处理 (S305)。

当在图11中的步骤S103处的处理完成时，压缩单元101生成压缩文 件(步骤S104)，该压缩文件包括由生成单元1011生成的压缩/解压缩字 典数据T6以及由转换单元1012写在存储单元11中的压缩码。当执行了 在步骤S104处的处理时，终止文件压缩处理(步骤S105)。

接下来，说明在计算机1中执行的解压缩处理的过程。

图17示出了由解压缩单元102执行的解压缩处理的流程的示例。当 响应于应用程序24的功能或由用户所输入的指令调用解压缩处理功能时 (S400)，解压缩单元102从存储单元11读出在调用解压缩处理功能时指 定的压缩文件(S401)。解压缩单元102将来自在S401处读取的压缩文件 的压缩/解压缩数据展开到存储单元11中(S402)。如果其是在图11中示 出的压缩数据，则展开在图6中示出的压缩/解压缩数据T6。然后，解压 缩单元102通过由转换单元1021和调节单元1022执行的处理来解压缩压 缩文件(S403)。

图18示出了将压缩码转换成解压缩字符数据的转换处理的流程的示 例。当执行在图17中的S403处的解压缩处理(S500)时，调节单元1022 将读出位置设置为在S401处读取的压缩文件中的压缩码串的开始点 (S501)。转换单元1021确定是否可以从所设置的读出位置读出压缩码 (S502)。当不能从所设置的读出位置读出压缩码(所有压缩码已被读出) (在S502处为否)时，终止转换处理的流程(S506)。

当在S502处的处理中可以读出压缩码(在S502处为是)时，转换 单元1021从所设置的读出位置读出预定长度的位串。该预定长度是例如 在压缩中使用的压缩码中的最大位长。此外，转换单元1021从在S402 处展开的压缩/解压缩字典数据中读出位于由所读取的位串指定的位置处 的叶的数据结构(S503)。在S503处，首先，从数据头的结构H读出叶 的数据结构L的开始地址。由所读取的位串指定的位置是例如下述位置： 在该位置中，与叶的数据结构L的开始地址的偏移由每个叶的数据结构 的数据大小与所读取的位串的乘积指示。在S503处的处理中读出的叶的 数据结构包括字符数据(解压缩的字符数据)和压缩码长。

然后，转换单元1021将在S503处的处理中读出的字符数据写入存储 单元11的存储区域(S504)。此外，调节单元1022使读出位置前进由在 S503处的处理中读出的压缩码长指示的位数(S505)。反复地执行以上所 描述的在S502至S505处的处理，从而将压缩数据被转换成解压缩的字符 串，并且将所转换的解压缩字符串写入存储单元11。

当在图17中示出的S403处的处理被执行时，解压缩单元102生成解 压缩文件，该解压缩文件包括由转换单元1021写入存储单元11的解压缩 字符数据组。当在S404处解压缩文件被生成时，终止在图17中示出的解 压缩处理的流程(S405)。

此外，说明在计算机1中执行的检索处理的过程。

图19示出了由检索单元103执行的检索处理的流程的示例。当检索 单元103接收到从存储在存储单元11中的压缩文件提取检索的字符串的 检索请求(S600)时，读出要被检索的压缩文件(S601)。此外，检索单 元103对在S600处接收的检索请求进行分析，并且根据分析的结果在图 20中示出的压缩/解压缩字典数据T10的交叉检查标志区域中设置标志 (S602)。

图20示出了根据本实施例与检索对应的压缩/解压缩字典数据T10。 如在图20中示出地，除在图6中示出的压缩/解压缩字典数据T6以外， 压缩/解压缩字典数据T10还具有交叉检查标志区域。在初始状态中，交 叉检查标志区域的位都被设置为“0”。当在本实施例中的交叉检查标志区 域的位是“0”时，其指示“不需要交叉检查处理”；当位是“1”时，其 指示“需要交叉检查处理”。

检索单元103设置例如与包括在S600处接收的检索请求中的检索字 符串的第一字符数据对应的交叉检查标志。例如，如果检索字符串是 “apple”，则在压缩/解压缩字典数据T10中将与字符数据“a”对应的交 叉检查标志设置为“1”(参见图20)。

在S602处的处理之后，调节单元1032以与在S501处由调节单元1022 执行的处理相同的方式设置从压缩文件读出位串的位置(S603)。然后， 搜索单元1031以与在S502处由转换单元1021执行的处理相同的方式确 定在压缩文件中是否存在任何尚未读取的数据(S604)。当在压缩文件中 不存在尚未读取的数据(在S604处为否)时，终止检索处理的流程(S610)。

当在压缩文件中存在尚未读取的数据(在S604处为是)时，搜索单 元1031从该压缩文件读出预定长度的位串(S605)。预定长度是例如在压 缩中使用的压缩码中的最大位长。此外，搜索单元1031在压缩/解压缩字 典数据T10中对与在S605处的处理中读出的位串对应的区域的交叉检查 标志进行引用(S606)。搜索单元1031确定在S606处的处理中引用的交 叉检查标志是“0”还是“1”(S607)。当交叉检查标志已被设置为“1” (在S607处为是)时，交叉检查单元1033执行针对检索的字符串的交叉 检查处理(S608)。当针对检索的字符串的交叉检查处理已由交叉检查单 元1033执行时或当在S607处的确定中交叉检查标志已被设置成“0”(在 S607处为否)时，调节单元1032以与在S505处由调节单元1032执行的 处理相同的方式更新读出位置(S609)。调节单元1032基于存储在S606 处的引用处理中引用的区域中的码长来调节读出位置。在S609处的处理 之后，由搜索单元1031再次执行在S604处的处理。

图21示出了由交叉检查单元1033执行的交叉检查处理的流程的示 例。当执行在图19中的S608处的处理(S700)时，交叉检查单元1033 基于拷贝的读出位置信息来执行交叉检查处理。交叉检查单元1033使计 数器的值i递增一，计数器的值i指示什么编号的字符被交叉检查(S702)。 i的初始值是1。交叉检查单元1033基于码长更新在S701处拷贝的读出 位置(S703)。基于在S606处引用的区域的码长来执行对读出位置的第一 更新。基于要在随后描述的在S705处的处理中获取的码长来执行对读出 位置的第二及后续更新。

然后，交叉检查单元1033以与在S605处由搜索单元1031执行的处 理相同的方式读出预定长度的位串(S704)。交叉检查单元1031在压缩/ 解压缩字典数据T10中读出存储在由在S704处读出的位串指定的位置中 的字符数据和码长(S705)。然后，交叉检查单元1033获取检索的字符串 的第i条字符数据(S706)。此外，交叉检查单元1033确定在S705处读 取的字符数据是否与在S706处获取的字符数据一致(S707)。当在S707 处的确定中确定该两条字符数据彼此不一致(在S707处为否)时，终止 交叉检查处理的流程(S710)，并且执行在图19中的S609处的处理。

当在S707处的确定中确定该两条字符数据彼此一致(在S707处为 是)时，交叉检查单元1033确定在S706处获取的字符数据是否是检索的 字符串的最后字符(S708)。作为在S708处的确定的结果，当确定出不是 检索的字符串的最后字符(在S708处为否)时，交叉检查单元1033再次 执行在S702处的处理。

作为在S708处的确定的结果，当确定出是检索的字符串的最后字符 (在S708处为是)时，交叉检查单元1033将读出位置作为与检索字符串 一致的字符数据存在的位置存储在存储单元11中(S709)。作为在S709 处存储的读出位置，例如，使用在S701处拷贝的拷贝源读出位置或在S703 处更新的读出位置两者之一。当读出位置在S709处被存储时，返回图19 的流程(S710)，执行在图19中的S609处的处理。

当使用压缩/解压缩字典数据T5时也可以执行在图19中示出的交叉 检查。然而，在该情况下，在S606处的处理中，通过引用根的数据结构 KR来读出指针，然后通过访问叶数据结构KL来检查交叉检查标志。以 与使用压缩/解压缩字典数据T5执行的交叉检查处理相同的例程，可以实 现使用压缩/解压缩字典数据T6的交叉检查处理。

在以上描述的实施例中，假设2000种类型的字符数据为要通过使用 字符码系统而被压缩的对象，其中一条字符数据由16位表示。此外，假 设分配给要被压缩的字符数据的压缩码的码长高达12位。

例如，在压缩/解压缩字典数据T5中使用的指针需要确定要被压缩的 字符数据的类型，所以采用足以标识2000种或更多种类型的位数。当使 用以1字节为单位管理数据的存储器时，根数据结构KR包括存储在每2 字节区域中的指针。另一方面，16位字符码以及其码长被存储在叶数据 结构KL中的每个中，提供了3字节区域。因此，根数据结构KR(2的 十二次幂×2字节)以及叶数据结构KL(2000×2字节)需要约14kb 的存储区域。

在压缩/解压缩字典数据T6中，叶数据结构L中的每个以与叶数据 结构KL相同的方式设置有3字节存储区域。因此，采用约12kb的存储 区域，其通过2的12次幂×3字节算出。

在以上的示例中，如果要被压缩的字符数据为约1330种字符，则压 缩/解压缩字典数据T6的数据大小小于压缩/解压缩字典数据T5的数据大 小。

以上说明的实施方式仅是示例性的，并且可以在本发明的范围内进行 适当地修改。此外，对于以上说明的处理的进一步详细内容而言，适当地 使用本领域技术人员所公知的技术。

参考标记列表

1    计算机

2    基站

3    网络

1a   计算机

1b   计算机

10   控制单元

11   存储单元

101  压缩单元

102  解压缩单元

103  检索单元

1011 生成单元

1012 转换单元

1021 转换单元

1022 调节单元

1031 搜索单元

1032 调节单元

1033 交叉检查单元