CN1183683C

CN1183683C - 使用前缀预测的位自适应编码方法

Info

Publication number: CN1183683C
Application number: CNB021045534A
Authority: CN
Inventors: 胡笑平
Original assignee: Individual
Current assignee: Individual
Priority date: 2001-02-09
Filing date: 2002-02-08
Publication date: 2005-01-05
Anticipated expiration: 2022-02-08
Also published as: EP1231717B1; CA2371375C; CA2371375A1; JP3989745B2; US7274671B2; JP2002319865A; EP1231717A2; EP1231717A3; US20020141422A1; CN1369970A

Abstract

本发明涉及一种使用前缀预测的位自适应编码方法，首先对数据串的前缀进行估算，并按照表格形式来预测所有字符的概率，各个字符按照其是否在表中来领取“已知”和“未知”的标签，在单个数位值的基础上将节点分为0组和1组，从而产生一棵二值树；接下来选择一个区别位使得0组和1组中的已知字符的概率差异达到最大，若0组或1组中有一个不包含已知字符，则必须做特殊处理，然后，在已知字符和未知字符的概率基础上，为每一个分支指定概率值，最后，编码或解码一个字符都变得非常简单，从根节点到包含单个字符的叶子节点之间找到一条最短路径，对这条路径上的分支概率直接使用算术编码或解码即可，采用本发明能有效压缩数据。

Description

使用前缀预测的位自适应编码方法

技术领域

本发明涉及数据的压缩技术，用于实现有效的存储和传输。

背景技术

由于内存容量和传输带宽资源的有限性，在对大量数据进行存储和传输的过程中，需要对数据进行压缩。经过压缩，数据量变少，不但节省了带宽，而且能更加有效地利用信息通道；同样，压缩后的数据比未被压缩的数据占用更小的内存。为此，人们提出了各种不同的编码技术，例如：跑长编码、哈夫曼编码、算术编码和适应性统计技术等等，这些技术都能以无损的形式压缩数据。把这些无损编码技术和其它的一些算法(例如：Burrows-Wheeler transform)结合使用还能取得更好的压缩效果。

但是，这些技术存在的不足在于：

跑长编码的一种简单形式是首先找出数据中的一个或多个出现频率较高的字符串，例如单词“the”，然后把这些高频率词汇用一些比其本身短很多的码字来代表。这种方法对英文文本能达到将近4∶1的压缩率。跑长编码的一些较为复杂的形式也被经常使用。跑长编码的一个主要缺点是那些出现频率高的数据串常常不能作为先验知识事先知道，于是需要建立模型：即假定一些字符作为高频率字符，并为其分配相应的码字。然而当实际数据中经常重复的字符和事先定好的模型有出入时，压缩率便不能达到预期目标。

哈夫曼编码及其变种算法在从摩尔斯码到UNIX的打包/解包、压缩/解压缩命令的许多领域都有应用。哈夫曼编码及其变种算法包括决定字符的出现频率，并为不同的频率分配不同的码字。频繁出现的字符具有较短的码字，而较少出现的字符则有较长的码字。一般从底部最长的码字开始，逐步向上结束于最短的码字来产生二值树结构。虽然由下到上的方式对于建树比较适合，但在实际读取时还是采用由上向下的方式，例如解码器就是从顶部根节点出发，根据位编码信息，按照树的不同分支追溯下去。按照这种方法，最经常出现的字符会最先被找到。哈夫曼编码的一个缺点是每个字符的出现概率不能预先知道，于是，通常用预先建立的频率来产生哈夫曼二值树，而对于一组特定字符集合，这些频率可能适合，也可能不适合。

算术编码也有着广泛的应用。和哈夫曼编码一样，算术编码也是一种基于数据概率模型的无损压缩技术。和哈夫曼编码不同的是，算术编码产生的是一个单独的符号而非若干独立的码字，数据被作为0到1之间的一个实数来进行编码。不凑巧的是，算术编码也有一系列的缺点：首先，算术编码比其它编码算法慢得多，当算术编码使用了高阶预测模型时，这一点表现得尤为严重；其次，由于算术编码会更加真实的反映在编码过程中使用的概率分布模型，因而不准确或是不正确的概率模型会导致低下的压缩效率。

一般来说，当数据的概率较为随机时，算术编码的压缩效率高于哈夫曼编码。

适应性统计技术可以解决先验模型带来的某些问题。一般来说，适应性编码技术提供了对从未在字符表或是前缀表中出现的字符的一种编码方法。当一个未知的字符出现时，首先编一个“殊况”ESC码，将其送入码流中，然后编码器继续用较低阶的前缀对其进行编码，并将增加的数据也送入码流。最低阶的预测表(通常为0阶表)必须包含所有可能的字符，便于每一个可能字符都能在其中被找到，ESC码也必须以一定的概率来编码。然而，由于新字符的不可预知性，仅从前面的数据不可能对ESC码的概率进行精确的估计，因此，一般具有给定前缀的ESC值概率只能按经验确定，导致编码效率不能达到最优。这样，在适应性编码中引进ESC码带来了两个问题。一个是ESC码只能给出关于新字符的有限信息，新字符仍然按照较低阶的前缀预测表来编码；第二个问题是ESC码的概率不能被精确地建模。

发明内容

本发明的目的在于克服上述现有技术的不足和缺陷，提出一种高倍的无损压缩技术，使其不再具有前面所述技术的各种缺点，降低在自适应性编码算法中ESC码概率模型的不精确性对编码带来的影响，从而有效压缩数据。

实现上述目的的技术方案是一种使用前缀预测的位自适应编码方法，包括如下步骤：

a、对字符串里的字符进行排序，每一字符用二进制表示。

b、每一个相关字符都包含在具有一个上下文的字符集合里，上下文中包含一个前缀。

c、前缀和一个字符集合对应，对字符串的前缀进行判定，并对可能跟在该前缀后的所有字符的概率用已经发生过的前缀后字符数据的统计概率来代表，为此前缀产生一个预测表，表中包含上述概率。一般情况下，前缀包含一个或两个元素。虽然前缀的尺寸可以变化，但其阶数最好小于或等于3以便控制数据量。

d、基于预测表，选择一个区别位，使其按此区别位产生的O组中的已知字符的概率总和与1组中的已知字符的概率总和的差异达到最大，产生一棵对应的二值树结构，结束于叶子节点，每一个叶子节点都包含一个单独的字符。这种树是为了使预测表中的字符尽可能的不均衡。

e、确定从根节点到每一字符的路径，树中每个分支都被指定了一个概率：如果一组内有一个或多个已知字符，则该组的概率用已知字符的概率和来代替，当一组内没有任何已知字符，则该组的概率用未知字符的概率和来代替。

f、利用从根节点到相关字符的叶子节点的一条最短路径上所有分支指定的概率来编码或解码一个字符。

二值树结构的建立步骤包括：

1.从根节点开始，每一个节点都选择一个区别位。区别位的选择应使按此区别位产生的0组中的已知字符(不包含ESC)的概率总和与1组的已知字符(不包含ESC)的概率总和的差异应达到最大，此一方法称为最大差异方法。若某个位在一个父节点中已经用作过区别位，它就不能在后面的节点中被再次使用。如果某个区别位产生的0组或1组中只包含一个未知字符，那么该位的处理将被推迟，直至所有剩余位也进入了相同的情况。如果一个节点只包含单个已知字符，那么将选择区别位使得包含这个已知字符的字符组中的所有字符(包含已知及未知字符)的概率和达到最大。如果一个节点不包含已知字符，选择的区别位应使1组和0组中的未知字符的差异最大。

2.所有的字符(包括未知字符)都以在第一步中选择的区别位为基础，在每一个节点被分成0组和1组。分组是按区别位上的值来进行的，结束于叶子节点，每一个叶子节点都包含一个单独的字符。

上述的后继节点、根节点以及叶子节点都包含在节点集合中，单个字符都包含在字符集合中。

分支操作取决于字符的二进制表示中单个数位的值，也就是区别位的值。如果一个字符的当前数位为0，那么这个字符进入“0组”；如果一个字符的当前数位是1，则此字符进入“1组”。举个例子，如果对一个用3位b₂b₁b₀来表示的字符集用b₁来做分区，那么无论X是0还是1，所有具有X0X形式的字符(如101,000)都被归入0组；而所有具有X1X形式的字符(如110,011)都被归入1组。

对于一个用M个数位(M-bits)来表示的字符集来说，这种二值树具有M层，每一层对应于字符的一个数位(bit)。

树结构中为每一个分支指定概率，这个概率对应于字符集合中包含的字符的概率。和具有未知概率、不精确概率和人工指定概率的字符相比，那些具有已知概率的字符具有更高的优先级。

为树中的每一个分支指定概率的方法：每一个节点的分支概率都被表示为一对浮点数或是有理数，每个节点的左支和右支被同时赋值，且左支和右支的概率和应为1。首先使用已知的概率，以便将已知的概率和未知概率、不精确概率或人工指定概率清楚的分开，其中，概率已知的字符的概率用预测表来表示；而剩余的字符子集：即具有未知概率、不精确概率或人工指定的概率的字符的概率总和用ESC值表示。

指定概率赋值操作分为两步：第一步，对0组和1组的已知字符分别求概率和，这两个和用Z_p和O_p表示，若其中一个概率为零，或两个全为零，Z_p和O_p须重新用0组和1组中的所有(已知和未知)字符的概率相加算得。第二步，将左支的概率赋为Z_p/(Z_p+O_p)；将右支的概率赋为O_p/(Z_p+O_p)。第二步做的是归一计算。我们将此一指定分支概率的方法称之为已知优先法。

所谓已知优先法，就是说，如果一组(0组或1组)内，有一个或多个已知字符，则该组的概率就用已知字符的概率和来代替。只有当一个组内没有任何已知字符，则未知的概率才参加该组的概率计算。两个分支的概率的和必须为1。

这种浮点数对或有理数对之间的差异与选用其它的数位产生的分支所得的差异相比是最大的。

所述节点集合包括根节点、后继节点和终止的叶子节点。其中，终止叶子是和一个字符的概率相联系的，此概率可能来自于先验知识，也可能来自于之前的统计数据，也可能未知，但通过公式将其进行模型化。

通过对字符串进行编码后，来压缩或解压缩数据。

所述排序步骤可以包括或不包括进行一个或多个下列操作：一个巴罗斯—维勒(Burrows-Wheeler)变换和前移(Move-to-front)变换。

所述编码是标准算术编码。

预测表包括产生一个或多个下列表：零阶表、一阶表、二阶表和三阶表。

指定概率可以是概率已知的字符的概率，也可是概率未知、不准确或是人工指定的字符的概率，但概率已知的字符具有较高优先级而首先被选用。

采用上述技术方案，本发明有益的技术效果在于：传统压缩技术难以对那些没有在概率表中出现的字符进行有效压缩，而本发明能对这些字符进行有效的估值和编码。例如，在哈夫曼编码中，这些从未出现过的字符或ESC值的频率可能相当高，从而需要一个短码(相应的，需要加长其余已知字符的码长)。正常情况下，一个字符通过在对应的二值树中从根追溯到叶子来编码。传统的方法都是在一个步骤里编完一个字符，本发明方法则是在若干步骤中完成这一过程，其中每一个步骤都对应二值树中的一层。等效来看，每个字符是逐位编码的。这种按位分解的方法具有两个优点：第一是当还不太确定当前字符的时候，推迟了ESC码的使用；第二是一个从未出现过的字符可在追溯ESC值的过程中找到，从而不需要使用低阶前缀对这个字符再次编码。无论通过何种路径，二值树都将终止于某一个字符，故编码路径能够遍历所有的字符。采用本发明技术能相当理想的压缩数据，以实现有效的存储和传输。经过压缩，数据量变少，不但节省了带宽，而且能更加有效的利用信息通道；同样，压缩后的数据比未被压缩的数据占用更小的内存。

下面结合附图，通过实施例对本发明作进一步详细的说明。

附图说明

图1是使用前缀预测编码系统的一个方框图；

图2A和图2B都是图表，分别表示各阶前缀预测表的概率分布情况；

图3中是一棵二值树，表示一个前缀字符串的概率分布；

图4是一个使用前缀预测编码的数据压缩方法的流程图。

具体实施方式

下面按照优化的操作步骤和数据结构对本发明的具体实施方式进行描述。本发明技术可使用通用处理器或是程序控制下的特殊用途处理器来实现，也可使用符合此处描述的操作步骤和数据结构的电路来实现。本节给出的操作步骤和数据结构的实现即时可用，不需要进一步的实验或研究。

系统组成：如图1所示，是具有前缀预测编码系统的一个方框图，这个使用前缀预测的编码系统(本发明用100来统称)包括一个运算设备110。运算设备110中包含一个核心处理单元115、内存器120，以及一对耦合设备：输入/输出单元125和使用者接口130。内存器120包括存储大量信息的各种设备，如磁碟、磁带、光盘等等各种存储介质。和内存器一样，这里的“运算设备”也是最广义的一个说法，它包括具有可编程处理器以及普通的计算机在内的各种设备，如PC机、掌上电脑、个人数字助理等等。内存器120包括计算机程序140，它包含一个完成如下四种过程的指令集145：(1)排列数据，(2)BurrowsWheeler变换，(3)前缀预测编码，(4)算术编码。正常情况下，120也包含一组数据150，它是计算机程序140的操作对象。

图2A和图2B表示的是各阶前缀情况下，其后数据元素的概率分布表。为说明方便起见，一组8个字符的集合{A，B，C，D，E，F，G，H}被作为字符的全集。

根据数据150的类别，系统100会产生一个一阶表210，或是一个二阶表230，或是一个零阶表250，或是以上所有表。这些表的例子都在图2A和图2B中，表中的字符以及数据只是例子而已，不具限制性。在另外一些情况下，也可以产生其它阶数的前缀表如三阶表。

一阶预测表210包含一组一个或多个前缀字符215，一组一个或多个跟在215后的可能字符220，以及一组概率值225。前缀字符215位于字符串的最前端。集合220既包含真正的字符也包含ESC值221。概率值225则反映某一个字符220跟在前缀字符215后的概率。在一阶表210中，每一个前缀字符215都被限制成一个字符长度。

ESC是一个码字，它代表所有在当前表中没有找到的字符的集合。这些没有出现在表中的字符称为“未知字符”，与此对应，那些在预测表中能找到的称为“已知字符”。总的来说，ESC值的概率由整个未知字符集合决定，单个的未知字符不能起决定性的作用。在下面的讨论中，ESC将被进一步分解成二值树中的字符，在这样的情况下，ESC的概率分布将反映每一个未知字符的概率分布。表210中例子假设ESC的概率均匀地分摊在每个未知字符上。

二阶预测表230包含一个或多个前缀字符235的集合，一个或多个跟在235后面的可能字符的集合240以及概率值245。前缀字符235位于字符串的最前端。240字符集合中既包含已知字符也包含ESC值241。ESC是一个表示在当前二阶表中的没有出现过的字符集合的值。概率值245表示某一个字符240跟在当前前缀255后面的概率。在二阶表210中，每一个前缀字符215的长度为两个字符。

零阶预测表250包括前缀字符集合255，它是一个空集，还包括一组一个或多个跟在255后的字符集合260以及概率值265。通常，零阶预测表运用于无前缀预测编码。字符集合260是字符全集，但不包含ESC值，因为零阶表中只包含所有可能字符。概率值265反映某个字符260的出现概率情况，这时，没有前缀的限制。

图3是一棵数据树，它表示在前缀为A的情况下，一个字符的位编码流程。图中显示的字符和数值只是例子而已，不具限制性。这棵树是基于图2中一阶表210使用的数值和字符建立起来的，针对的数据是具有前缀215“A“的字符串。而且，字符集合{A，B，C，D，E，F，G，H}是用二进制b₂b₁b₀的形式来表示，并分别取下表中的值：

字符	值(b₂b₁b₀)
字符	值(b₂b₁b₀)	A	000
B	010	A	000
B	010	C	011
D	110	C	011
D	110	E	001
F	100	E	001
F	100	G	101
H	111	G	101

上述字符集和其取值只是例子，不具限制性。当然，当字符采用其它的值时会产生不同的树。

如图3所示，数据树300是一个二值树，它的读取方法是自顶向下。树中，根节点305包含字符全集(即在给定环境下的所有可能字符)；分叉节点(如310、320、330、340、350或360)包含字符子集；终止节点也称为叶子节点，每一个叶子节点都代表一个不同的字符。节点的左向分支称为0组，右向分支称为1组。0组和(区别位)位值取0的分支相关联，同理，1组和位值取1的分支相联系。每一个分支都和一个浮点数关联，它代表向下连接的节点中所有字符的概率，此节点可能是属于0组也可能属于1组。

图3中的二值数据树300通过3个步骤建立：

1.从根节点开始，每一个节点都选择一个区别位；

2.所有的字符(包括未知字符)都以在第一步中选择的区别位为基础，在每一个节点被分成0组和1组。分组是按区别位上的值来进行的，结束于叶子节点。在叶子节点上，一个单独的字符被编码；

3.树中每个分支都被指定了一个概率。

在每个节点选择的区别位应满足下述要求：即按此区别位产生的0组中的已知字符(不包含ESC)的概率总和与1组的已知字符(不包含ESC)的概率总和的差异应达到最大。这个区别位必须是字符的二值表示中的各位当中的一个。例如，在当前的例子中，区别位必须为b₂，b₁，，或b₀。若某个位在一个父节点中已经用作过区别位，它就不能在后面的节点中被再次使用。如果某个区别位产生的0组或1组中只包含一个未知字符，那么该位的处理将被推迟，直至所有剩余位也进入了相同的情况。如果一个节点只包含单个已知字符，那么将选择区别位使得包含这个已知字符的字符组中的所有字符(包含已知及未知字符)的概率和达到最大。如果一个节点不包含已知字符，选择的区别位应使1组和0组中的未知字符的差异最大。

位于一个节点上的各个字符将继续向下分解，分往0分支还是分往1分支主要是基于选择的区别位上的位值。若区别位上的字符为0则并入0组，若为1则进入1组。对一个给定的节点，已知字符对区别位的选择起着重要作用。然而，一旦区别位选定，此节点上的所有字符(包括已知和未知字符)都用同样的分支操作方法一起分支。

分支操作结束后，来到建立二值树的最后一步，即为树中的每一个分支指定概率值。每个节点的左支和右支被同时赋值，且左支和右支的概率和应为1。赋值操作分为两步：首先，对0组和1组的已知字符分别求概率和，这两个和用Z_p和O_p表示，若其中一个为0，或两个全为0，Z_p和O_p须重新用0组和1组中的所有(已知和未知)字符的概率相加算得。最后，左支的概率是Z_p/(Z_p+O_p)；右支的概率是O_p/(Z_p+O_p)。

二值数据树300根据表210中的数据和概率建造而成。如图3所示，根节点305包括字符全集(此例中为{A、B、C、D、E、F、G、H})，其中，A、B、C和D是已知字符，E、F、G和H是未知字符，这个字符集合基于b₂位分为0组和1组：节点310即0组包括A、B、C和E，因为这些字符的b₂位是0。节点320即1组则包括D、F、G和H，因为它们的b₂位是1。选择b₂位作为区别位的原因是0组中的已知字符(A，B，C)的概率和Z_p是0.9，1组中的已知字符D的概率和O_p是0.07。这是所能得到的最大差异结果。现在来看看，选择其它bit位会出现什么情况：若选择b₁会产生0.65(0组的A，E，F，G)和0.32(1组的C，E，G，H)，而选择b₀会产生0.87(0组的A，E，D，F)和0.10(1组的C，E，G，H)，可见选择b₂最符合要求。沿树继续向下产生分支，节点310由b₀做区别位，节点320由b₁或b₀做区别位，这是因为它们产生的树具有相同的概率值。b₁位产生一个0组，只包含未知字符(F和G)，而b₀位产生一个1组，也只包含未知字符(G和H)为避免二义性，选择具有较高位置(即左侧)的bit位作为区别位。

下面将详细描述如何给二值树300的各个分支赋概率值。根节点305的0组分支是节点310，310包括已知字符A、B和C；305的1组分支是节点320，320中的唯一已知节点是D。这些节点的概率值都列于表210中。0组分支节点310的已知节点概率和Z_p是0.65+0.15+0.1(A、B、C的概率分别是0.65、0.15和0.1)；1组分支节点320的已知节点的概率和O_p为0.07，其唯一的已知字符D的概率是0.07。因此，节点305的左支的概率是Z_p/(Z_p+O_p)＝0.9278，右支的概率是O_p/(Z_p+O_p)＝0.0722。

节点360是节点320的1组分支。当节点360在b₀位继续分解时，产生了一个只包含单个未知字符H的1组分支，因此，在计算概率和时，既要使用未知字符，也要使用已知字符。在这种情况下，Z_p＝0.07和O_p＝0.0075，得到左支的概率是0.9032，右支的概率是0.0968。其余节点可以按同样步骤推导出来。

在一个给定的前缀的情况下，对字符X进行编码可以分3步来做：

1.在给定前缀的预测表基础上建立二值树；

2.确定从根节点到字符X的路径；

3.对此路径上的每一个概率进行编码。

例如，在图3中，字符D使用3个概率：0.0722、0.8378和0.9032进行编码，而字符E则使用概率0.9278、0.1111和0.0698来编码。每一个概率值都使用标准算术编码来编。

使用方法：图4是表示使用前缀预测编码的数据压缩方法的一个流程图，下面将逐步解释其功能。

方法400在系统100上运行。虽然方法400是按顺序方式进行描述的，实际上它的几个步骤可以作为独立的单元进行联合操作或是并行操作。

在流程点405，系统100已经为开始一个使用前缀预测编码的数据压缩流程作好准备。

接下来410模块给出了一个命令去压缩指定数据(字符串)150。正常情况下，这个命令既可以由用户手动操作发出，也可以自动执行。

415模块中，计算程序140执行了一组指令用来重新排列数据150。例如，把一组二维数据重新排列成一维。

420模块中，计算程序140执行了一组指令，使用一个Burrows-Wheeler变换和一个Move-to-front变换改变了数据150的顺序。对数据做顺序上的变动改变了概率分布，并使输入值由一个位置索引代替。

模块425把经过变化的数据150存储在内存中。

模块430，计算程序140为数据150中的每一个字符产生预测概率表，这些表是基于字符前缀的条件表。在另外的一些情况下，概率表以经验概率值为基础生成的。

模块435中，计算程序140产生了一个二值树结构，使图3中表示的每一对0-1分支组里的已知字符(不包含未知字符)概率和的差异性达到最大。每一个字符都由一条唯一的路径表示，连接根和字符。这条路径包含分支，每个分支都被指定了一个概率值。编码一个字符等价于编码这条从根到字符的路径上的所有概率值。

440模块中，计算程序140遍历需要编码的字符前缀对应的二值树结构，并对从根到字符这条路径上的所有概率进行编码。正常情况下，概率值使用算术编码方法编码。随着不同字符串和不同前缀的读入，这一过程可能会重复多次，直至整个数据集合编码完毕。

必须指出，在这里仅对本发明技术的基本算法进行了描述，实际上无论是从概念、范围的角度，还是从创造的精神来看，仍存在许多的可供发挥的地方，从而得到不同的衍生算法，对于那些精于图象压缩技术又熟读本文的人来说，这件事轻而易举。

Claims

1.一种使用前缀预测的位自适应编码方法，其特征在于，包括如下步骤：

a、对字符串里的字符进行排序，每一字符用二进制表示；

b、每一个相关字符都包含在具有一个上下文的字符集合里，上下文中包含一个前缀；

c、前缀和一个字符集合对应，对字符串的前缀进行判定，并对可能跟在该前缀后的所有字符的概率用已经发生过的前缀后字符数据的统计概率来代表，为此前缀产生一个预测表，表中包含上述概率；

d、基于预测表，选择一个区别位，使其按此区别位产生的0组中的已知字符的概率总和与1组中的已知字符的概率总和的差异达到最大，产生一棵对应的二值树结构，结束于叶子节点，每一个叶子节点都包含一个单独的字符；

e、确定从根节点到每一字符的路径，树中每个分支都被指定了一个概率：如果一组内有一个或多个已知字符，则该组的概率用已知字符的概率和来代替，当一组内没有任何已知字符，则该组的概率用未知字符的概率和来代替；

f、利用从根节点到相关字符的叶子节点的一条最短路径上所有分支指定的概率来编码一个字符。

2.根据权利要求1所述使用前缀预测的位自适应编码方法，其特征在于，二值树结构的建立步骤包括：

a、从根节点开始，每一个节点都选择一个区别位，此区别位是单个的数位；

b、所有的字符都以在步骤a中选择的区别位为基础，在每一个节点被分成0组和1组，分组是按区别位上的值来进行，结束于叶子节点，每一个叶子节点都包含一个单独的字符，后继节点、根节点以及叶子节点都包含在节点集合中，单个字符都包含在字符集合中；

c、区别位的选择应使按此区别位产生的0组中的已知字符的概率总和与1组的已知字符的概率总和的差异应达到最大；

d、若某个位在一个父节点中已经用作过区别位，它就不能在后面的节点中被再次使用，如果一个节点只包含单个已知字符，那么将选择区别位使得包含这个已知字符的字符组中的所有字符的概率和达到最大，如果一个节点不包含已知字符，选择的区别位应使1组和0组中的未知字符的差异最大。

3.根据权利要求1所述使用前缀预测的位自适应编码方法，其特征在于：

树结构中为每一个分支指定概率对应于字符集合中包含的字符的概率；

概率已知的字符的概率用预测表来表示；

剩余的字符子集：即具有未知概率、不精确概率或人工指定的概率的字符的概率总和用ESC值表示；

和具有未知概率、不精确概率和人工指定概率的字符相比，那些具有已知概率的字符具有更高的优先级。

4.根据权利要求1所述使用前缀预测的位自适应编码方法，其特征在于为树中的每一个分支指定概率的方法包括：每一个节点的分支概率都被表示为一对浮点数或是有理数，每个节点的左支和右支被同时赋值，且左支和右支的概率和应为1。

5.根据权利要求4所述使用前缀预测的位自适应编码方法，其特征在于，赋值操作分为两步：第一步，对0组和1组的已知字符分别求概率和，这两个和用Z_p和O_p表示，若其中一个为0，或两个全为0，Z_p和O_p须重新用0组和1组中的所有字符的概率相加算得；第二步，将左支的概率赋为Z_p/(Z_p+O_p)，将右支的概率赋为O_p/(Z_p+O_p)。

6.根据权利要求1所述使用前缀预测的位自适应编码方法，其特征在于，预测表包括产生一个或多个下列表：零阶表、一阶表、二阶表和三阶表。

7.根据权利要求1所述使用前缀预测的位自适应编码方法，其特征在于，所述排序步骤可以包括或不包括进行一个或多个下列操作：一个巴罗斯—维勒变换和前移变换。

8.根据权利要求1所述使用前缀预测的位自适应编码方法，其特征在于，所述编码是标准算术编码。

9.根据权利要求1所述使用前缀预测的位自适应编码方法，其特征在于，通过对字符串进行编码后，用来压缩或解压缩数据。

10.根据权利要求1所述使用前缀预测的位自适应编码方法，其特征在于，终止叶子是和一个字符的概率相联系的，此概率可能来自于先验知识，也可能来自于之前的统计数据，也可能未知，但通过公式将其进行模型化。