识别要压缩的数据块中的表边界检测的方法与系统

摘要

本发明公开识别要压缩的数据块中的表边界检测的方法与系统。通过根据用于建立表边界形成模式的符号表示将数据流分类，利用后缀树把数据转换成最小化的数据表示。在维持最小的头信息的同时，转换后的数据对于重构是完全可逆的。

说明书

技术领域

本发明总体上涉及计算机，尤其涉及在计算环境中要压缩的数据 块中的表边界检测。

背景技术

在当今社会，计算机系统是很平常的。计算机系统可以在工作场 所、在家里或者在学校找到。计算机系统可以包括数据存储系统、或 者磁盘存储系统，以处理和存储数据。数据存储系统，或者磁盘存储 系统，用于处理和存储数据。存储系统可以包括一个或多个磁盘驱动 器。这些数据处理系统一般需要大量的数据存储。消费者数据，或者 由用户在数据处理系统中产生的数据，占用了这种数据存储的大部 分。这些计算机系统中的许多都包括虚拟存储部件。

数据压缩广泛地用于减少处理、发送或存储给定量的信息所需的 数据量。数据压缩是对数据的编码，以最小化其表示。压缩可以用于 例如减少文件的存储需求，以便增加信道上的通信率，或者在加密之 前减少冗余以获得更大安全性。

发明内容

计算系统用于存储和管理各种类型的数据，诸如所谓的“表格数 据(tabular data)”。表格数据一般组织成行与列，以形成常见的表， 例如，就像在关系表、文字处理文档、电子数据表或者像电子数据表 的结构或者类似的数据库结构中所使用的那样。这些表的形成包括用 于行与列的多种有组织的阵列与布置。但是，表格数据的实际物理存 储可以采取多种形式。例如，尽管表格数据的逻辑结构可以是多维 的，但是表格数据也可以按线性格式物理地存储，诸如以行为主或者 以列为主的格式。在以行为主的格式中，来自类似表(table-like)的结 构的一行的列值在永久性存储装置中连续地存储。在大多数数据文件 中，重要的信息一般是以表的形式存储和布置的。表中的数据可以被 存储和提取。但是，表中数据形成(formation)的识别对于通过利用其 它各种管理系统的数据查询数据和将数据与利用其它各种管理系统的 数据的结合是必需的。目前，由于各种挑战，难以改进要压缩的数据 块中表边界的检测。

相应地，并且鉴于前面所述，提供了在计算环境中由处理器设备 检测要压缩的数据块中的表边界的各种示例性方法、系统与计算机程 序产品实施例。仅仅是作为例子，在一种实施例中，通过根据用于建 立表边界形成模式的符号表示给数据流分类，利用后缀树把数据转换 成最小化的数据表示。在维持最小的头信息的同时，转换后的数据对 于重构是完全可逆的。

除了以上的示例性方法实施例，还提供了其它的示例性系统与计 算机产品实施例并且提供相关的优点。以上概述的提供是为了以简化 的形式介绍在以下具体描述中进一步描述的概念的选择。本概述不是 要识别所保护主题的关键特征或必需特征，也不是要用于帮助确定所 保护主题的范围。所保护的主题不限于解决背景中所提到的任何或全 部缺点的实现。

附图说明

为了很容易地理解本发明的优点，以上简要描述过的本发明的更 特定描述将通过参考在附图中说明的具体实施例来给出。应当理解， 这些附图绘出了本发明的实施例而且因此不应当认为是限定其范围， 将通过附图的使用来描述并解释本发明附加的特殊性和细节，附图 中：

图1是说明其中可以实现本发明各方面的、具有示例性存储设备 的计算机存储环境的框图；

图2是说明其中可以实现本发明各方面的计算机系统中的示例性 数据存储系统的硬件结构的框图；

图3是说明其中可以实现本发明各方面的、用于识别“最佳”建 议数据表格式的示例性方法的流程图；

图4是说明其中同样可以实现本发明各方面的、用于识别最佳建 议数据表格式的另一种示例性方法的流程图；

图5A-5B是说明其中可以同样实现本发明各方面的、用于识别 最佳建议数据表格式的另外一种示例性方法的流程图；及

图6是说明具有头信息的示例性输出数据文件的框图。

具体实施例

如前面所提到的，计算系统用于存储和管理各种类型的数据，诸 如表格数据。表格数据一般组织成行与列，以形成常见的表，例如， 就象在关系表、文字处理文档、电子数据表或者类似电子数据表的结 构或者类似的数据库结构中所使用的那样。作为特殊的文档组件，表 格数据列的格式广泛地在网页、科学文献、财务报告等中使用。例 如，研究人员一般使用表来以浓缩的方式简明地显示最近的实验结果 或者统计财务数据。与互联网的快速扩张一道，表变成信息检索领域 中一个有价值的信息来源。在大部分数据文件（例如，文章/数据库 /Excel/Word）中，所报告的最重要的信息是以表的形式给出的。此 外，表中所报告的大部分数据可以按改进数据搜索与压缩的方式提取 并存储。一旦识别出数据的形成，数据就可以通过利用其它管理系统 的数据来查询并与其结合。

但是，由于以下问题，几乎不可能改进存储阵列中表边界的识别 与检测。1）大部分表检测工作是基于预定义布局的算法，这通常对 于一个域工作得很好但是难以扩展。2）对于基于规则的方法，性能 总是严重地受到规则质量的影响。当测试数据集足够大时，难以确定 阈值的“好”值。3）写到存储装置的数据是以渐进模式，这意味着 存储装置只接收数据流的一部分。4）大部分分类检测操作以可能无 法重构的方式改变原始数据流。5）大部分分类检测操作需要在输出 数据中维护大量资源用于重构原始块。由于这些问题，效率和生产率 可能降低。

相对于此，并且为了解决所述的低效与性能问题，所说明的实施 例提供了改进存储阵列中表形成检测的机制。该机制通过构建最小化 的数据块映射方案并且以识别“最佳”（例如，最长模式表示和/或 最常见模式）表边界形成匹配的方式给映射块分类来提供用于检测表 边界的有效预处理操作。因而，该机制简化了表边界检测问题并且在 保持输出形成所需的头信息非常少量的同时以完全可逆的方式给数据 流分类。换句话说，通过建立最小化的数据块映射方案并且然后以识 别“最佳”表形成匹配的方式给映射块分类来提供检测表边界的操 作，数据可以被有效地分类到重新排序后的数据输出流中以供压缩。 在分类后的数据输出文件中，可以列出包含识别出的表边界模式的头 信息。而且，在重新排序后的（分类后的）数据输出流中，分隔符符 号可以添加在每个检测出的表边界模式前面，以便区分表边界。输出 文件还可以包含尺寸（例如，行数）和所找到的表的个数。在重新排 序后的数据输出文件中利用如上所述的信息，数据流对于解码返回到 原始的数据流是完全可逆的。

不像基于预定义布局的方法和基于规则的方法的大多数表检测方 法，所说明的实施例设法提供通用算法，该算法可以应用到所有数据 块类型和格式的表边界检测。在一种这样的实施例中，所述机制通过 利用后缀树进行搜索而识别表及其布局，来转换要进行数据压缩的数 据，并且把识别信息放到头中和压缩该数据。所说明实施例的机制可 以实时地应用于渐进存储写而且可以在存储阵列中实现。而且，应当 指出，本发明是通过为数据的映射版本建立后缀树而不是通过检查元 数据或内容头来识别数据结构的，而且还没有假设任何特殊的数据形 成依赖关系。后缀树的使用允许动态建立数据分类形成。换句话说， 所说明实施例的机制通过经由所创建的原始数据的映射分析数据块的 内容来识别给定数据块的数据分类。

现在转向图1，绘出了计算环境中数据存储系统（例如，虚拟带 系统）的示例性体系结构10。计算机系统10包括中央处理单元 （CPU）12，它连接到大容量存储设备14和存储器设备16。大容量 存储设备可以包括硬盘驱动器（HDD）设备、固态设备（SSD）等， 这些存储设备可以在独立磁盘冗余阵列（RAID）中配置。进一步描 述的备份操作可以在位于系统10中或者别的地方的设备14上执行。 存储器设备16可以包括如电可擦除可编程只读存储器（EEPROM） 这样的存储器或者相关设备的主机。存储器设备16和大容量存储设 备14经信号承载介质连接到CPU12。此外，CPU12通过通信端口 18连接到通信网络20，通信网络20具有附连的多个附加计算机系统 22和24。

图2是显示在根据本发明的计算机系统中数据存储系统的硬件结 构的示例性框图200。参考图2，示出了主机计算机210、220、 225，每个都充当用于执行数据处理，其是数据存储系统200的一部 分，的中央处理单元。为了在数据存储系统200中实现本发明的目 的，主机（物理的或者虚拟的设备）210、220、225可以是一个或多 个新的物理设备或逻辑设备。仅仅是作为例子，在一种实施例中，数 据存储系统200可以实现为System Storage^TMDS8000^TM。网络 连接260可以是光纤通道架构、光纤通道点到点链路、以太网架构或 者点到点链路之上的光纤通道、FICON或者ESCON I/O接口、任何 其它I/O接口类型、无线网络、有线网络、LAN、WAN、异质的、 同质的、公共的（即，互联网）、专用的或者其任意组合。主机 210、220和225可以是本地的或者在一个或多个位置之间分布的， 而且可以配备有到存储控制器240的任何类型的架构（或架构通道） （在图2中未示出）或者网络适配器260，诸如光纤通道、FICON、 ESCON、以太网、光纤、无线的或同轴适配器。数据存储系统200 相应地配备有合适的架构（在图2中未示出）或者网络适配器260， 以便通信。数据存储系统200在图1中绘制为包括存储控制器240和 存储装置230。

为了方便对在此所述方法的更清楚的理解，存储控制器240在图 2中示为单个处理单元，包括微处理器242、系统存储器243和非易 失性存储装置（“NVS”）216，这些将在以下更具体地描述。应当 指出，在有些实施例中，存储控制器240由多个处理单元组成，每个 处理单元都具有其自己的处理器联合体与系统存储器，而且通过数据 存储系统200中的专用网络互连。存储装置230可以由一个或多个存 储设备组成，诸如存储阵列，该阵列可以通过存储网络连接到存储控 制器240。

在有些实施例中，存储装置230中所包括的设备可以以环形体系 结构连接。存储控制器240管理存储装置230并且方便对存储装置 230的写和读请求的处理。存储控制器240的系统存储器243存储程 序指令与数据，处理器242可以访问这些程序指令与数据来执行与管 理存储装置230关联的功能与方法步骤并且执行在计算机存储环境中 识别要压缩的数据块中表边界的本发明的步骤与方法。在一种实施例 中，系统存储器243包括用于在计算机存储环境中识别数据块中的表 边界的操作软件250、与其关联或者与其通信，操作软件250包括在 此所述的方法与操作。如图2中所示，系统存储器243还可以包括用 于存储装置230的高速缓存245，在这里也称为“高速缓存存储 器”，或者与其通信，其中高速缓存245用于缓冲“写数据”和“读 数据”，其中写数据和读数据分别指读/写请求及其相关数据。在一 种实施例中，高速缓存245在系统存储器243外面的设备中被分配， 但是保持可以被微处理器242访问，而且除了执行在此所述的操作， 还可以用来提供防止数据丢失的附加安全性。

在有些实施例中，高速缓存245是利用易失性存储器和非易失性 存储器实现的而且经本地总线（在图2中未示出）耦合到微处理器 242，来增强数据存储系统200的性能。数据存储控制器中所包括的 NVS216可以由微处理器242访问并且用来为在其它图中描述的本发 明的操作与执行提供附加的支持。NVS216也称为“永久性”高速缓 存或者“高速缓存存储器”，并且是利用可以用或者可以不用外部电 力来保留其中所存储的数据的非易失性存储器实现的。为了适于实现 本发明目标的任何目的，NVS可以存储在高速缓存245中或者利用 其进行存储。在有些实施例中，备用电源（在图2中未示出），诸如 电池，在数据存储系统200断电的情况下为NVS216提供用于保留 其中所存储数据的足够电力。在某些实施例中，NVS216的容量小于 或者等于高速缓存245的总容量。

存储装置230可以物理地由一个或多个存储设备组成，诸如存储 阵列。存储阵列是单个存储设备，诸如硬盘，的逻辑分组。在某些实 施例中，存储装置230是由JBOD（简单磁盘捆绑）阵列或者RAID （独立磁盘冗余阵列）阵列组成的。物理存储阵列的集合可以进一步 组合，以形成秩(rank)，其中秩去除了物理存储装置与逻辑配置的关 联。秩中的存储空间可以分配到逻辑卷中，其中逻辑卷定义在写/读 请求中指定的存储位置。

仅仅是作为例子，在一种实施例中，在图2中所示出的存储系统 可以包括可能具有不同类型的分配的逻辑卷，或者简单地说就是 “卷”。存储装置230a、230b和230n示为数据存储系统200中的 秩，并且在这里被称为秩230a、230b和230n。秩对于数据存储系统 200而言可以是本地的，或者可以位于物理上远端的位置。换句话 说，本地存储控制器可以与远端存储控制器连接并且管理处于远端位 置的存储装置。秩230a示为配置成具有两个完整的卷234和236， 及一个部分卷232a。秩230b示为具有另一个部分卷232b。因而， 卷232跨秩230a和230b分配。秩230n示为完全分配给卷238– 即，秩230n指用于卷238的整个物理存储装置。从以上例子将认识 到，秩可以配置成包括一个或多个部分和/或完整卷。卷和秩可以进 一步分成所谓的“轨道”，其中轨道代表存储装置的固定块。因此， 轨道与给定的卷关联而且可以赋予给定的秩。

存储控制器240可以包括数据转换模块255、表边界检测模块 257、列压缩模块259和帮助在计算机存储环境中识别数据块中的表 边界的后缀树映射模块260。数据转换模块255、表边界检测模块 257、列压缩模块259和后缀树映射模块260可以与存储控制器 240、主机210、220、225和存储设备230中的每一个组件联合工 作。数据转换模块255、表边界检测模块257、列压缩模块259和后 缀树映射模块260从结构上可以是一个一起工作的完整模块并且彼此 联合用于执行诸如识别数据块的表边界的此类功能性，或者可以是各 单个模块。数据转换模块255、表边界检测模块、列压缩模块259和 后缀树映射模块260还可以位于高速缓存245或者存储控制器240的 其它组件当中，来实现本发明的目的。

存储控制器240可以构造成具有用于控制到主机计算机210、 220、225的光纤通道协议的控制交换器241、用于控制所有存储控制 器240的微处理器242、用于存储控制存储控制器240的操作的微程 序（操作软件）250、用于控制的数据和稍后所述的每个表的非易失 性控制存储器243、用于临时存储（缓冲）数据的高速缓存245及用 于帮助高速缓存245读写数据的缓冲区244、用于控制对到存储设备 230或者来自存储设备230的数据传输进行控制的协议的控制交换器 241、数据转换模块255、表边界检测模块、按列比较模块259和可 以对其设置信息的后缀树映射模块260。多个缓冲区244可以利用本 发明来实现，以帮助在计算环境中识别数据块中的表边界，或者根据 所说明实施例的机制执行其它功能性。

仅仅是作为例子，在一种实施例中，主机计算机或者一个或多个 物理或虚拟设备210、220、225和存储控制器240经有时候称为“架 构”的交换器通过作为接口的网络适配器（这可以是光纤通道）260 连接。仅仅是作为例子，在一种实施例中，将描述图2中所示系统的 操作。微处理器242可以控制存储器243存储来自主机设备（物理的 或者虚拟的）210的命令信息和用于识别主机设备（物理的或者虚拟 的）210的信息。控制交换器241、缓冲区244、高速缓存245、操作 软件250、微处理器242、存储器243、NVS216、数据转换模块 255、表边界检测模块、按列比较模块259和后缀树映射模块260彼 此通信，而且可以是独立的或者是一个单独的组件。而且，如果不是 全部组件的话，至少是一些部件，诸如操作软件245，可以包括在存 储器243中，用于在计算机存储环境中识别要压缩的数据块中的表边 界。为了适于本发明的目的，存储设备中的每个组件都可以链接到一 起而且可以彼此通信。

现在转向图3，说明了用于识别“最佳”建议数据表格式的示例 性方法300。通过根据用于建立表边界形成模式的符号表示给数据流 分类而利用后缀树把数据转换成最小化的数据表示（步骤304），方 法300开始识别要压缩（例如，列压缩）的数据块中的表边界（步骤 302）。数据流是根据用于建立表边界模式的符号表示（例如，字母 “T”可以用于文本数据而字母“N”可以用于数值数据）来分类。 通过根据符号表示转换数据流，方法300能够把最小化的数据表示建 立成映射机制并且以识别最长模式表示表边界匹配的方式给映射块分 类。给定最小化的映射输入缓冲区作为树的输入，后缀树用于找出最 佳（例如，最小化数据的最长模式表示）建议表形成。检测到的转换 后数据的表边界形成模式被重新排序成具有最小头信息的对重构完全 可逆的输出文件数据流（步骤306），上述输出文件数据流在保持最 小头信息的同时对于重构是完全可逆的。方法300结束（步骤 308）。

在一种实施例中，所说明实施例的机制基于以下六个步骤识别表 边界。1）数据流被转换成最小化的表示。2）建立所提议的表边界模 式列表。3）搜索并识别最常见的表边界形成模式。4）通过在找到的 每种模式之前添加“\n”（和/或其它符号表示，诸如“”符号）来 重新排序分类后的数据流，并且区分表形成边界。5）在输出文件 中，列出包含识别出的表边界形成模式（例如，标记为“格式”）、 分隔符符号（例如，“”）、尺寸（例如，行数），及所找到的表 的个数的头信息。如果还存在后续的表的话，可以重复这些步骤以找 到后续的表。而且，所说明实施例的机制可以添加带序列的图形与 表。图形可以利用模式匹配过程的结果来产生，并且排除比所找到的 阈值模式小的所有模式。

数据（例如，数据块）到最小化表示的转换对于减少检测时间和 最小化处理后的数据是很重要的。在一种实施例中，以下规则可以用 于数据的转换。文本数据可以用指示数据为文本的符号和/或字符代 替。例如，对于最小化的数据表示，所述机制可以用字母“T”代替 文本数据。“T”文本列定义为一系列字符，这些字符不包括在定界 符列表和数字列表中。数值数据可以用指示数据为数值的备选符号和 /或备选字符来代替。例如，对于最小化的数据表示，所说明实施例 的机制可以用字母“N”来代替数值数据。“N”数字列被定义为一 系列数字字符，这些数字字符不包括在定界符列表中。换句话说，文 本数据是不包括在定界符列表与数字列表中的一系列字符，而数值数 据是不包括在定界符列表中的一系列数字字符。数字列表与定界符列 表可以由所说明实施例的机制使用。而且，对于最小化的数据表示， 定界符也可以用唯一符号和/或字符代替。例如，对于最小化的数据 表示，所说明实施例的机制可以用字符“”代替定界符。“”是 用于检测数据块中表边界的预定义的已知定界符与分隔的列表。基于 用于文本、数字和定界符的符号和/或字符，为数据表示而最小化的 转换后的数据可以翻译成：

TTTNNNNTTNTT  TNNNT  TNNNTNNN.

一旦数据块被转换成了最小化的数据表示，就建立了所提议的表 边界模式列表。在一种实施例中，所说明实施例的机制扫描转换后的 数据串，以得到最佳的（例如，最长和最常见的）表边界模式。该机 制可以根据以下扫描规则操作。规则（1）：该机制可以搜索最小化 数据表示的后缀并且识别该序列，该序列包括多于一个项（例如， TN|NT|TT|NN）。规则（2）：该机制可以跳过只包括定 界符（例如，可以指第三种符号和/或字符的“”符号）的所有最 小化的数据表示，即使最小化的数据表示每个字节都不同也是如此， 直到在第一个规则（1）中定义的下一个后缀串为止。换句话说，只 包括用于识别定界符的第三种符号（例如，“”符号）的数据被跳 过，直到包括代表文本与数值数据的第一和第二种符号的下一个数据 序列为止。应当指出，“T”符号/字符可以指第一符号/字符，而 “N”符号/字符可以指第二符号/字符。规则（3）：该机制可以建立 转换后的数据流表示的后缀树。应当指出，为了性能，只考虑转换后 的表示的一部分。规则（4）：在建立并生成后缀树后，所述机制排 除与规则（1）和规则（2）不匹配的所有叶子（例如，扫描顺序 (scan-order)）。

在建立所提议的表边界形成模式列表之后，所说明实施例的机制 搜索最常见的表边界形成模式。从根据扫描规则生成的扫描顺序表 中，所说明实施例的机制搜索所有分支节点而且可以选择最常见的模 式串。例如，可以识别出以下模式串和出现的次数：模式1： TTNN而且所发现的对应的出现次数等于2。模式2： TNN而且所发现的对应的出现次数等于2。模式3：NN而 且所发现的对应的出现次数等于2。在这个例子中，模式1说明了最 长的表示模式（和/或最常见的公共模式串）TTNN，它代表 用于给定数据流的最佳（例如，最长模式表示）表边界形成。应当指 出，在几个叶子都具有相同出现次数的情况下，所述机制可能更愿意 用最长的模式表示作为用于数据流的最佳建议表格式。

在这个时候，所述机制可以通过在所找到的最常见串模式前面添 加“\n”来重新排序数据流，以便区分表的边界。例如：如果该机制 找到的最长的常见模式是TTNN，则以下重新排序之前和之 后的操作可以利用识别出的TTNN模式来说明：

在重新排序之前：

TTTNNNNTTNTT  TNNNT  TNNNTNNN

在重新排序之后：

TTTNNNNTTNTT  TNNNT  TNNN TNNN

这种处理是可逆的而且使得所述机制能够重构原始数据块次序， 而没有输出格式所需的任何附加信息。换句话说，在输出文件中，列 出包含识别出的表格式模式（例如，在头中标记为“格式”）、分隔 符符号、尺寸（例如，行数）、是否实现并使用\n及找到的表的个 数的头信息。应当指出，如果所述机制识别出多于一个表（例如，2 个表），则可以在第一个头之后添加另一个头而且所添加的头描述第 二个表。如果所述机制识别出多于一个表，则第一个表格行在位置[1 +表的个数]处。在这个时候，所述机制提供了可逆的数据流，这种可 逆的数据流可以清楚地分离成所找到的表格式。

基于前面所述，现在转向图4，绘出了用于识别最佳建议数据表 格式的附加示例性方法400。方法400通过跳过块处理并且处理下一 个数据块（步骤402）开始。一旦接收到输入流，方法400就确定数 据流是否是基于ASCII的（步骤404）。如果不是，方法400就转向 步骤402。如果是，方法400就把数据流转换成最小化的数据表示 （步骤406）。方法400可以建立后缀树（步骤408）。后缀树被最 小化（步骤410）。然后，方法400将建立所提议的表边界形成模式 列表（步骤412）。方法400将找出最常见的表格式模式（例如，最 长的匹配格式是希望的和优选的）（步骤414）。然后，方法400可 以通过在找到的每个识别出的模式前面添加\n来给数据流重新排序 （步骤416）。如果存在后续的表，为了找出后续的表，方法400将 重复前面的每个步骤，并且返回步骤404。

接下来，图5A和5B说明用于识别最佳建议数据表格式的附加 示例性方法500。方法500以把数据转换成最小化的数据格式（步骤 502）开始。应当指出，在图5中说明了样本数据、后缀树和其它各 种例子与图，以便显示方法500每个步骤的结果。建立后缀树（步骤 504）。方法500去除不匹配任何扫描规则的所有叶子（例如，扫描 顺序），如上所述（步骤508）。方法500找出最常见的表格式模式 （例如，最长的匹配格式是希望的和优选的）（步骤510）。方法 500通过在每个表格式模式前面添加\n来给数据流重新排序（步骤 512）。方法500结束（步骤514）。

如前面所提到的，通过建立最小化的数据块映射方案并且然后以 识别“最佳”表形成匹配的方式给映射块分类，提供用于检测表边界 的操作，数据可以更有效地分类到重新排序后的（例如，分类后的） 数据输出流中，以供压缩。在分类后的数据输出文件中，可以列出包 含所识别的表边界模式的头信息。而且，在重新排序后的（分类后 的）数据输出流中，分隔符符号可以加在每种检测到的表边界模式前 面，以区分表边界。输出文件还可以包含尺寸（例如，行数）和所找 到的表的个数。在重新排序的数据输出文件中利用如上所述的信息， 数据流可以被压缩而且对于解码回原始的数据流是完全可逆的。接下 来，图6说明了具有头信息的示例性输出数据文件600。在输出文件 600中，列出了包含所识别的表格式模式（例如，标记为“格 式”）、分隔符符号、尺寸（例如，行数），及所找到的表的个数的 头信息。如果后续的表存在的话，这些步骤可以重复以找出后续的 表。

根据在数据块压缩中识别表边界的以上讨论，独立地压缩每一列 将提供比利用一个流压缩整个表更高的压缩比。应当指出，为了实现 本发明的机制（例如，列压缩），可以使用各种压缩技术。增加的压 缩比的原因是每一列中的数据是相对同质的。因此，基于本发明的机 制，效率和生产率提高了。

所属技术领域的技术人员知道，本发明可以实现为系统、方法或 计算机程序产品。因此，本公开可以具体实现为以下形式，即：可以 是完全的硬件、也可以是完全的软件（包括固件、驻留软件、微代码 等），还可以是硬件和软件结合的形式，本文一般称为“电路”、“模 块”或“系统”。此外，在一些实施例中，本发明还可以实现为在一个 或多个计算机可读介质中的计算机程序产品的形式，该计算机可读介 质中包含计算机可读的程序代码。

可以采用一个或多个计算机可读的介质的任意组合。计算机可读 介质可以是计算机可读信号介质或者计算机可读存储介质。计算机可 读存储介质例如可以是——但不限于——电、磁、光、电磁、红外 线、或半导体的系统、装置或器件，或者任意以上的组合。计算机可 读存储介质的更具体的例子（非穷举的列表）包括：具有一个或多个 导线的电连接、便携式计算机磁盘、硬盘、随机存取存储器 （RAM）、只读存储器(ROM)、可擦式可编程只读存储器(EPROM 或闪存)、光纤、便携式紧凑磁盘只读存储器(CD-ROM)、光存储器 件、磁存储器件、或者上述的任意合适的组合。在本文件中，计算机 可读存储介质可以是任何包含或存储程序的有形介质，该程序可以被 指令执行系统、装置或者器件使用或者与其结合使用。

计算机可读介质上包含的程序代码可以用任何适当的介质传输， 包括——但不限于——无线、有线、光缆、RF等等，或者上述的任 意合适的组合。可以以一种或多种程序设计语言或其组合来编写用于 执行本发明操作的计算机程序代码，所述程序设计语言包括面向对象 的程序设计语言—诸如Java、Smalltalk、C++，还包括常规的过程 式程序设计语言—诸如”C”语言或类似的程序设计语言。程序代码可 以完全地在用户计算机上执行、部分地在用户计算机上执行、作为一 个独立的软件包执行、部分在用户计算机上部分在远程计算机上执 行、或者完全在远程计算机或服务器上执行。在涉及远程计算机的情 形中，远程计算机可以通过任意种类的网络——包括局域网(LAN)或 广域网(WAN)—连接到用户计算机，或者，可以连接到外部计算机 （例如利用因特网服务提供商来通过因特网连接）。

以上已经将参照本发明实施例的方法、装置（系统）和计算机程 序产品的流程图和/或框图描述本发明。应当理解，流程图和/或框图 的每个方框以及流程图和/或框图中各方框的组合，都可以由计算机 程序指令实现。这些计算机程序指令可以提供给通用计算机、专用计 算机或其它可编程数据处理装置的处理器，从而生产出一种机器，这 些计算机程序指令通过计算机或其它可编程数据处理装置执行，产生 了实现流程图和/或框图中的方框中规定的功能/操作的装置。

也可以把这些计算机程序指令存储在能使得计算机或其它可编程 数据处理装置以特定方式工作的计算机可读介质中，这样，存储在计 算机可读介质中的指令就产生出一个包括实现流程图和/或框图中的 方框中规定的功能/操作的指令装置(instruction means)的制造品 （manufacture）。也可以把计算机程序指令加载到计算机、其它可 编程数据处理装置、或其它设备上，使得在计算机、其它可编程数据 处理装置或其它设备上执行一系列操作步骤，以产生计算机实现的过 程，从而使得在计算机或其它可编程装置上执行的指令能够提供实现 流程图和/或框图中的方框中规定的功能/操作的过程。

以上图中的流程图和框图说明了根据本发明各种实施例的系 统、方法和计算机程序产品的可能实现的体系结构、功能性与操作。 就此而言，流程图或框图中的每一块都可以代表代码的一个模块、片 段或者部分，所述模块、片段或者部分包括用于实现指定逻辑功能的 一条或多条可执行指令。还应当指出，在有些备选实现中，块中所指 出的功能可以不按图中指示的次序发生。例如，依赖于所涉及的功能 性，顺次示出的两个块事实上可以基本上同时执行，或者有时候这些 块可以颠倒的次序执行。还应当指出，框图和/或流程图说明中的每 一个块及框图和/或流程图说明中块的组合可以由执行指定功能或行 为的基于硬件的专用系统或者专用硬件与计算机指令的组合来实现。

尽管已经具体地说明了本发明的一种或多种实施例，但是本领 域技术人员将认识到，在不背离如以下权利要求所阐述的本发明的情 况下，可以对那些实施例进行修改与调整。