字典压缩方法、字典解压缩方法与字典建构方法

摘要

本发明公开了字典压缩方法、字典解压缩方法与字典建构方法，其中字典压缩方法的一个实施例包含：接收数位资料，所述数位资料包含复数个资料区块；以及依据一多层级字典压缩算法压缩所述数位资料，其中所述多层级字典压缩算法包含第一、第二与第三字典压缩规则。所述第一字典压缩规则以N个所述资料区块为单位范围来进行压缩处理；所述第二字典压缩规则以M个所述资料区块为单位范围来进行压缩处理；所述第三字典压缩规则以L个所述资料区块为单位范围来进行压缩处理，所述N、M、L为正整数且不大于所述复数个资料区块的总数，且所述N大于所述M，所述M大于所述L。

说明书

技术领域

本发明关于压缩与解压缩方法，尤其关于字典压缩方法、字典解压缩方法与字典建构方法。

背景技术

数位资料压缩演算法有许多种，有些会导致资料部分失真，有些不会，Lempel-Ziv即是一种常见的无失真压缩演算法，它有许多变形，主要特征在于利用字典及字典索引来代替原资料，举例来说，所述演算法可扫描原资料，将资料中的独特且重复的内容(例如单一符号或复数符号的组合)储存于一字典中，并用较精简的码字来代替所述独特内容，藉此达成无失真的资料压缩。然而，多数字典压缩演算法(Dictionary-BasedCompressionAlgorithm)仅涉及单一层级的字典，亦即均按同样的单位范围来进行字典压缩，鲜有复数层级的字典压缩演算法，更未见三个层级或更多层级的字典压缩演算法。

另外，为节省微控制单元(MicroControlUnit,MCU)(亦称为微控制器)的指令集的储存空间以节省成本及/或加快指令集的传输效率，指令集的压缩已是常见的技术，有些指令集压缩技术是将指令集压缩并存放于一非高速缓存(例如闪存或主要动态随机存取存储器等)，而在将指令集载入一高速缓存时再对压缩后的指令集进行解压缩，然而，目前的指令集压缩技术(例如采用赫夫曼编码(HuffmanEncoding)的压缩技术)多半具有下列问题的至少其中之一：解压缩所需的时间不固定，或说无法事先预估，因此不易评估运作效率；以及需从压缩后的指令集的起点或某个编码区块的起点开始解压缩，不能从任意编码单元开始解压缩，因而降低解压缩效率。此外，目前的指令集压缩技术鲜少利用前述的字典压缩演算法来对指令集进行压缩，此部分仍有待研究探讨。

更多关于字典压缩演算法以及指令集压缩技术的内容可由下列文献得知：CharlesLefurgy,PeterBird,I-ChengChen,TrevorMudge,“ImprovingCodeDensityUsingCompressionTechniques”,ProceedingsofMicro-30,December1-3,1997；YoshihisaMano,YutakaSato,“ADataCompressionSchemewhichAchievesGoodCompressionforPracticalUse”,IEEE,1991。

发明内容

本发明的一目的在于提出字典压缩方法、字典解压缩方法与字典建构方法，以解决先前技术问题。

本发明提出一种字典压缩方法，其一实施例包含下列步骤：接收数位资料，所述数位资料包含复数个资料区块，每所述资料区块包含复数个资料单元，每所述资料单元由复数个位元组成；以及依据一多层级字典压缩演算法压缩所述数位资料，其中所述多层级字典压缩演算法包含第一、第二与第三字典压缩规则，所述第一字典压缩规则以N个所述资料区块为单位范围对所述数位资料中的第一内容进行压缩处理，所述第二字典压缩规则以M个所述资料区块为单位范围对所述数位资料中的第二内容进行压缩处理，第三字典压缩规则以L个所述资料区块为单位范围对所述数位资料中的第三内容进行压缩处理，所述第一、第二与第三内容不同，所述N、M、L为正整数且不大于所述复数个资料区块的总数，且所述N大于所述M，所述M大于所述L。

本发明另提出一种字典压缩方法，用来压缩一微控制单元的指令集。所述方法的一实施例包含：接收所述指令集，所述指令集包含复数个指令区块，每所述指令区块包含复数个资料单元，每所述资料单元由复数个位元组成；以及依据复数个字典压缩规则压缩所述指令集，其中所述复数个字典压缩规则包含第一与第二字典压缩规则，所述第一字典压缩规则以N个指令区块为单位范围对所述指令集中的第一内容进行压缩处理，所述第二字典压缩规则以M个指令区块为单位范围对所述指令集中的第二内容进行压缩处理，所述第一与第二内容不同，所述N、M为正整数且不大于所述复数个指令区块的总数，且所述N大于所述M。

本发明进一步提出一种字典解压缩方法，用来通过解压缩产生一数位资料。所述方法的一实施例包含：接收一第一偏移量；依据所述第一偏移量找到一第一编码单元，其中所述第一编码单元属于复数个编码单元，且所述些编码单元对应至少三个字典压缩规则；依据所述第一编码单元决定一字典起始位址；依据复数个参数决定一字典内容位址，其中所述复数个参数包含所述第一编码单元与所述字典起始位址；以及依据所述字典内容位址存取一存储器以得到所述第一编码单元所对应的一或复数个第一资料单元，其中所述一或复数个第一资料单元属于数位资料。

本发明进一步提出一种字典解压缩方法，用来通过解压缩产生一微控制单元的指令集。所述方法的一实施例包含：接收一第一程序计数值；依据所述第一程序计数值找到一第一编码单元，其中所述第一编码单元属于复数个编码单元，且这些编码单元对应复数个字典压缩规则；依据复数个参数决定一字典内容位址，其中所述复数个参数包含所述第一编码单元与所述字典起始位址；以及依据所述字典内容位址存取一存储器以得到所述第一编码单元所对应的一或复数个第一资料单元，其中所述一或复数个第一资料单元属于一微控制单元的指令集。

本发明进一步提出一种字典建构方法，用于数位资料的压缩或解压缩。所述方法的一实施例包含：依据复数个字典压缩规则分析所述数位资料的资料组成及/或压缩率，藉此得到一分析结果，其中所述数位资料包含复数个资料区块，每所述资料区块包含复数个资料单元，每所述资料单元由复数个位元组成；以及依据所述分析结果以及所述数位资料建立至少三个字典，所述至少三个字典包含第一、第二与第三字典，分别对应第一、第二与第三字典压缩规则，所述第一字典压缩规则用来以N个所述资料区块为单位范围对所述数位资料中的第一内容进行压缩处理，所述第二字典压缩规则用来以M个所述资料区块为单位范围对所述数位资料中的第二内容进行压缩处理，第三字典压缩规则用来以L个所述资料区块为单位范围对所述数位资料中的第三内容进行压缩处理，所述第一、第二与第三内容不同，所述N、M、L为正整数且不大于所述复数个资料区块的总数，且所述N大于所述M，所述M大于所述L。

本发明进一步提出一种字典建构方法，用于一微控制单元的指令集的压缩或解压缩。所述方法的一实施例包含：依据复数个字典压缩规则分析一指令集的资料组成及/或压缩率，藉此得到一分析结果，其中所述指令集包含复数个指令区块，每所述指令区块包含复数个资料单元，每所述资料单元由复数个位元组成；以及依据所述分析结果以及所述指令集建立复数个字典，所述复数个字典包含第一与第二字典，分别对应第一与第二字典压缩规则，所述第一字典压缩规则用来以N个指令区块为单位范围对所述指令集中的第一内容进行压缩处理，所述第二字典压缩规则用来以M个指令区块为单位范围对所述指令集中的第二内容进行压缩处理，所述第一与第二内容不同，所述N、M为正整数且不大于所述复数个指令区块的总数，且所述N大于所述M。

有关本发明的特征、实作与功效，兹配合附图作优选实施例，详细说明如下。

附图说明

图1是微控制单元的一架构的示意图；

图2是微控制单元的另一架构的示意图；

图3是本发明的字典压缩方法的一实施例的流程图；

图4是储存本发明的压缩结果的记忆电路的一实施例的示意图；

图5a是采用全范围字典压缩的结果示意图；

图5b是采用局部范围字典压缩的结果示意图；

图5c是采用全范围与局部范围字典压缩的结果示意图；

图5d是采用多层级字典压缩的结果示意图；

图6是本发明的字典压缩方法用于指令集压缩的一实施例的流程图；

图7是本发明的字典解压缩方法的一实施例的流程图；

图8是本发明的字典解压缩方法用于指令集解压缩的一实施例的流程图；

图9是本发明的字典建构方法的一实施例的流程图；以及

图10是本发明的字典建构方法用于指令集的一实施例的流程图。

具体实施方式

以下说明内容的技术用语是参照本技术领域的习惯用语，如本说明书对部分用语加以说明或定义，所述部分用语的解释应以本说明书的说明或定义为准。

本发明包含字典压缩方法、字典解压缩方法与字典建构方法，这些方法可无失真地压缩与解压缩数位资料(例如微控制单元(MicroControlUnit)的指令集)，除能减少资料储存所需的存储器以降低成本，并能从压缩资料的任意单元开始进行解压缩，故能让实施者正确地估计解压缩所需的时间。本发明可应用于一储存电路(例如图4的记忆电路400)或一终端产品(例如包含所述储存电路的电子产品)，且在实施为可能的前提下，本技术领域具有通常知识者能够依本说明书的公开选择等效元件来实现本发明。本发明的方法可以是软件及/或固件形式，并可藉由通常的微控制单元架构(例如图1与图2的微控制单元架构100、200，包含：存储器及其控制器110、210；系统汇流排120、220；指令储存高速缓存130、230；资料储存高速缓存140、240；与微控制单元150、250)或其等效架构来执行，换言之，本发明在不更动微控制单元或其等效单元的架构下即可实现。在实施为可能的前提下，本技术领域人士可依本发明的公开内容及自身的需求选择性地实施任一实施例的部分或全部技术特征，或者选择性地实施复数个实施例的部分或全部技术特征的组合，藉此增加实施本发明的弹性。

为帮助了解本发明，在此简述本发明的一综合范例如下：

(1)接收或产生一数位资料，例如编译一来源码(SourceCode)以产生微控制单元所需的指令集。

(2)分析所述数位资料以产生复数层级的字典，亦即将所述数位资料的资料单元分门别类地储存于所述复数层级的字典中。

(3)使用压缩码和所述复数层级字典代替所述数位资料，以节省储存空间。

(4)解压缩时，依据一偏移量(例如一程序计数值(ProgramCounterValue)或具有类似作用的数值)来找到所述压缩码的一编码单元，再依据所述编码单元从所述复数层级的字典找到相对应的一或复数个资料单元。

基于上述，接下来的篇幅将说明本发明各实施例。

图3是本发明的字典压缩方法的一实施例的流程图。如图3所示，所述实施例包含下列步骤：

步骤S310：接收数位资料，所述数位资料包含复数个资料区块(或说可区分为复数资料区块)，每所述资料区块包含复数个资料单元，每所述资料单元由复数个位元组成。

步骤S320：依据一多层级字典压缩演算法(MultilayerDictionary-BasedCompressionAlgorithm)压缩所述数位资料，其中所述多层级字典压缩演算法包含第一、第二与第三字典压缩规则，所述第一字典压缩规则以N个所述资料区块为单位范围对所述数位资料中的第一内容进行压缩处理，所述第二字典压缩规则以M个所述资料区块为单位范围对所述数位资料中的第二内容进行压缩处理，第三字典压缩规则以L个所述资料区块为单位范围对所述数位资料中的第三内容进行压缩处理，所述第一、第二与第三内容不同，所述N、M、L为正整数且不大于所述复数个资料区块的总数，且所述N大于所述M，所述M大于所述L。举例而言，所述第一字典压缩规则为一全范围(Global)字典压缩规则；所述第二字典压缩规则为一中范围(Intermediate)字典压缩规则；以及所述第三字典压缩规则为一局部范围(Local)字典压缩规则，进一步而言，所述N等于所述复数个资料区块的总数，所述M小于所述N但大于1；所述L等于1。另举例而言，所述第一字典压缩规则用于处理于所有资料区块中以单一资料区块为单位而出现频率高于第一频率(例如最高频率或一预设频率)的一或复数个资料单元(例如表1的资料单元X)，所述第二字典压缩规则用于处理于所有资料区块中以单一资料区块为单位而出现频率介于第一与第二频率之间的一或复数个资料单元(例如表1的资料单元Y、Z)，所述第三字典压缩规则适用于处理于所有资料区块中以单一资料区块为单位而出现频率小于第二频率的一或复数个资料单元(例如表1的资料单元A、B、C、D)，其中所述第三字典压缩规则于本实施例中是用于处理于同一资料区块中出现频率最高的一或复数个所述资料单元(例如表1的资料单元A、B、C、D)。另外，压缩后的数位资料(即压缩码与字典)可储存于一记忆电路，例如图4的记忆电路400，包含：一压缩码储存单元410，用来储存代表所述数位资料的压缩码(或称索引)，并依据一偏移量(例如一程序计数值)输出所述压缩码的一编码单元；一字典储存单元420，用来储存对应所述压缩码的资料单元；以及一选择电路430，用来依据所述编码单元令所述字典储存单元420输出一相对应的资料单元。

承上所述，在此通过具体资料进一步说明如下。请参阅下表1，表1包含数位资料「AAXYBBXYCCXZDDXZ」，其包含或说可区分为复数个资料区块「AAXY」、「BBXY」、「CCXZ」、「DDXZ」，每个资料区块包含复数个资料单元「A,A,X,Y」、「B,B,X,Y」、「C,C,X,Z」、「D,D,X,Z」，每个资料单元由复数个位元组成(本例中每一资料单元由32个位元组成)，故所述数位资料所需的原始储存空间为16×32位，其中每个资料区块均出现的资料单元X可视为同一字典中的第一笔资料(例如图5a或图5b所示)、或不同字典中的第一字典(或说第一层)的资料(例如图5c或图5d所示)；前2个资料区块均出现的资料单元Y与后2个资料区块均出现的资料单元Z可视为同一字典中的二笔资料(例如图5a或图5b所示)、或不同字典中的第二字典(或说第二层)的资料(例如图5c或图5d所示)；只在单一资料区块出现的资料单元A、B、C、D则可视为同一字典中的四笔资料(例如图5a或图5b所示)、或不同字典中的第三字典(或说第三层)的资料(例如图5c或图5d所示)。因此，若令步骤S320所述的第一、第二与第三字典压缩规则依序为全范围、中范围与局部范围字典压缩规则，则如表1所示，有至少以下几种压缩情形：

(1)仅采用全范围字典压缩规则来压缩：请参阅图5a，在本情形下，全范围字典压缩规则以N个资料区块(本例中为4个资料区块，亦即所有资料区块)为单位范围，于一全范围字典(可区分为7个单位，如图5a所示)中储存每所述单位范围中的独特(Unique)资料单元X,Y,Z,A,B,C,D，并将数位资料压缩如下：011,011,000,001；100,100,000,001；101,101,000,010；110,110,000,010(其中000代表X、001代表Y、010代表Z、011代表A、100代表B、101代表C、110代表D，然上述对应关系仅为举例，可由实施者依其需求调整)。此时，由于每个32位的资料单元改由3位的编码单元来代表，7个独特的32位资料单元储存于全范围字典中，因此数位资料压缩后所需的储存空间为3×16+7×32位，其小于原储存空间16×32位。请注意，本情形中，由于仅采用全范围字典压缩规则，不同的资料单元均对应不同的编码单元，因此在解压缩时，本情形可依据一偏移量(例如一程序计数值，用来指示待存取的一资料单元的序号，例如12)找出相对应的一编码单元(例如对应程序计数值12的编码单元010)，再依据所述编码单元的值及所述全范围字典的起始位址找出一相对应的字典内容位址，进而找到储存于所述字典内容位址的资料单元(例如对应编码单元010的资料单元Z)。更精确地说，决定字典内容位址的一范例如下：

字典内容位址＝全范围字典的起始位址(例如为一预设位址0)+编码单元。

(2)仅采用局部范围字典压缩规则来压缩：请参阅图5b，在本情形下，局部范围字典压缩规则以L个资料区块(本例中为1个资料区块)为单位范围，于一局部范围字典(可区分为12个单位，如图5b所示)中依序储存每所述单位范围中的独特资料单元「X,Y,A」、「X,Y,B」、「X,Z,C」、「X,Z,D」，并将所述数位资料压缩如下：10,10,00,01；10,10,00,01；10,10,00,01；10,10,00,01(其中00代表所述4个资料区块中的X；01代表前2个资料区块中的Y与后2个资料区块中的Z；10分别代表4个资料区块中的A、B、C、D，然此对应关系仅为举例，可由实施者依其需求调整)，此时由于每个资料区块中32位的资料单元改由2位的编码单元来代表且每个单位范围包含3个独特的32位资料单元，因此压缩后所需的储存空间为(2×4+3×32)×4＝13×32位，其小于原始储存空间16×32位，但大于采用全范围字典压缩规则的3×16+7×32位。

请注意，本情形中，由于仅采用局部范围字典压缩规则，因此在解压缩时，本情形可通过一偏移量(例如一程序计数值8)找到一相对应的编码单元(例如对应程序计数值8的编码单元01)，再依据所述偏移量、所述编码单元的值与所述局部范围字典的起始位址即可找出一相对应的字典内容位址，进而找到所述编码单元所对应的资料单元(例如对应程序计数值8与编码单元01的资料单元Y)。更明确地说，决定字典内容位址的一范例如下：

字典内容位址＝局部范围字典的起始位址(例如一预设位址或所述程序计数值的函数值)+编码单元(或说此编码单元的字典位址排序)

(3)采用全范围与局部范围字典压缩规则来压缩：请参阅图5c，在本情形下，全范围字典压缩规则用来压缩每单位范围(即4个资料区块)中出现的重复内容X，使用的字典储存空间为1×32位；局部范围字典压缩规则用来压缩每单位范围(即1个资料区块)中X以外的内容(亦即为「Y,A」、「Y,B」、「Z,C」、「Z,D」)，使用的字典储存空间为(2×32)×4＝8×32位；此时，全范围字典、局部范围字典(可区分为8个单位，如图5c所示)使用的储存空间为1×32+8×32＝9×32位。因此，此二字典压缩规则可将所述数位资料压缩如下：10,10,00,01；10,10,00,01；10,10,00,01；10,10,00,01(其中00代表重复内容X；01依序代表前2个资料区块中的Y与后2个资料区块中的Z；10分别代表所述4个资料区块中的A、B、C、D，然此对应关系仅为举例，可由实施者依其需求调整)，此时由于每个32位的资料单元改由2位的编码单元来代表且所有字典使用了9×32位的储存空间，因此压缩后所需的储存空间为(2×4+2×32)×4+1×32＝10×32位，其小于原始储存空间16×32位以及仅采用局部范围压缩规则的13×32位，但大于仅采用全范围压缩规则的3×16+7×32位。

请注意，本情形中，由于采用双层级字典压缩规则，因此在解压缩时，本情形可通过一偏移量(例如一程序计数值6)找到一相对应的编码单元(例如对应程序计数值6的编码单元10)，再依据所述编码单元与局部范围字典的最小编码值来判断此编码单元是对应全范围字典或局部范围字典(例如基于编码单元10大于局部范围字典的最小编码值01而判断此编码单元10所对应的内容储存于局部范围字典中)，接着再依据复数个参数来找出一相对应的字典内容位址，进而找到所述编码单元所对应的资料单元。上述找出字典内容位址的一范例(以对应编码单元10为例)如下：

字典内容位址＝局部范围字典的起始位址+(偏移量/局部范围字典所对应的资料区块大小)×局部范围字典所对应的编码区块大小+(编码单元－全范围字典的最小编码值(若为0则可忽略))。

另请注意，各字典(若不影响实施则可排除最底层的字典)的起始位址(简称layer_mem_start)、最小编码值(简称layer_code_start)、对应的资料区块大小(或说所包含的资料单元数，简称为layer_data_blksize)、对应的编码区块大小(或说所包含的编码单元数，简称为layer_code_blksize)等可储存于一或多个记忆单元(例如缓存器)中，由于记忆单元的数目有限，故不实质影响本发明的整体压缩率。

(4)采用多层级字典压缩规则来压缩：请参阅图5d，在本情形下，全范围字典压缩规则用来压缩每单位范围(即4个资料区块)中的重复内容X，使用的字典储存空间为1×32位；中范围字典压缩规则用来压缩每单位范围(即2个资料区块)中的重复内容Y、Z，使用的字典储存空间为2×32位；局部范围字典压缩规则用来压缩每单位范围(即1个资料区块)中的重复内容A、B、C、D，使用的字典储存空间为4×32位；此时，全范围字典、中范围字典(可区分为2个单位，如图5d所示)以及局部范围字典(可区分为4个单位，如图5d所示)使用的储存空间为1×32+2×32+4×32＝7×32位。因此，多层级字典压缩规则可将所述数位资料压缩如下：10,10,00,01；10,10,00,01；10,10,00,01；10,10,00,01(其中00代表所述4个资料区块中的X；01分别代表前2个资料区块中的Y与后2个资料区块中的Z；10分别代表所述4个资料区块中的A、B、C、D，然此对应关系仅为举例，可由实施者依其需求调整)，此时由于每个资料区块中32位的资料单元改由2位的编码单元来代表且所有字典使用了7×32位的储存空间，因此压缩后所需的储存空间为2×16+7×32＝8×32位，小于原始储存空间16×32位，同时也小于前述各情形所需的储存空间，简言之，以多层级字典压缩规则来进行压缩对于所述数位资料而言能达到最佳压缩率。

请注意，本情形中，由于采用多层级字典压缩规则，因此在解压缩时，本情形可通过一偏移量(例如一程序计数值5)找到一相对应的编码单元(例如对应程序计数值5的编码单元10)，再依据所述编码单元与最高层(即第三层)的局部范围字典的最小编码值(本例中为10)来判断此编码单元是否对应局部范围字典(例如依据编码单元10等于或大于局部范围字典的最小编码值10而判断此编码单元10所对应的内容储存于局部范围字典中)，若否再依据所述编码单元与次一层(即第二层)的中范围字典的最小编码值(本例中为01)来判断此编码单元是对应中范围或全范围字典所储存的内容，接着依据复数个参数来找出一相对应的字典内容位址，进而找到所述编码单元所对应的资料单元。上述找出字典内容位址的一范例(以对应编码单元10为例)如下：

字典内容位址＝局部范围字典的起始位址+(偏移量/局部范围字典所对应的资料区块大小)×局部范围字典所对应的编码区块大小+(编码单元－中范围字典的最小编码值)。

类似地，各字典(若不影响实施则可排除最底层的字典)的起始位址、最小编码值、对应的资料区块大小、对应的编码区块大小等可储存于一或多个记忆单元中。

表1

在上述4种情形中，采用多层级压缩规则可达到最佳压缩率，虽然对某些特殊图样的数位资料而言，采用单一压缩规则或双层级压缩规则可能有最佳压缩率，但本实施例着重于多层级(至少三层)的压缩规则。另外，本实施例的数位资料中4个资料单元构成一资料区块，然此仅为举例，针对不同图样的数位资料，本方法可依一预设规范或一资料组成分析结果决定一资料区块所对应的资料单元数。再者，本技术领域具有通常知识者可依本说明书的公开(例如上述4种情形)推导出更多层级的压缩处理、采用不同的编码单元与资料单元的对应关系、及/或增减编码单元的位元数等，凡此种种均包含于本发明的实施变化范围内。

请注意，如图5d所示，表1的第(4)种情形虽以全范围字典做为所有字典的最底层(储存资料单元X)、以中范围字典做为所有字典的中间层(储存资料单元Y、Z)而以局部范围字典做为所有字典的最上层(储存资料单元A、B、C、D)，然此仅为举例以供了解。原则上本发明的特征着重于字典层级数，可不对字典的编排顺序做特别限制，例如上述三种字典的层级顺序可以任意变换。然而，为方便查找字典，本发明的实施例将对应相同字典的资料单元储存于连续的位址，藉此确定同一字典的起始位址。

由于字典压缩方法罕见于微控制单元的指令集的压缩，本发明另公开一种字典压缩方法，专用于压缩一微控制单元的指令集。所述方法的一实施例如图6所示，包含：

步骤S610：接收一指令集，所述指令集包含复数个指令区块(或说可区分为复数个指令区块)，每所述指令区块包含复数个资料单元，每所述资料单元由复数个位元组成。

步骤S620：依据复数个字典压缩规则压缩所述指令集，其中所述复数个字典压缩规则包含第一与第二字典压缩规则，所述第一字典压缩规则以N个指令区块为单位范围对所述指令集中的第一内容进行压缩处理，所述第二字典压缩规则以M个指令区块为单位范围对所述指令集中的第二内容进行压缩处理，所述第一与第二内容不同，所述N、M为正整数且不大于所述复数个指令区块的总数，且所述N大于所述M。举例来说，所述N等于所述复数个资料区块的总数，所述M小于所述N。另举例而言，所述第一字典压缩规则用于处理于所有资料区块中以单一资料区块为单位而出现频率高于第一频率的一或复数个资料单元(例如表1的资料单元X)，所述第二字典压缩规则用于处理于所有资料区块中以单一资料区块为单位而出现频率较低的一或复数个资料单元(例如表1的资料单元Y,Z,A,B,C,D)。

类似图3的实施例，本实施例所述的复数个字典压缩规则可进一步包含：一第三字典压缩规则，以L个指令区块为单位范围对所述指令集中的第三内容进行压缩处理，所述第一、第二与第三内容不同，所述L为正整数且不大于所述复数个指令区块的总数，且所述L小于所述M。举例来说，所述N等于所述复数个指令区块的总数，所述M小于所述N但大于1；所述L等于1。另举例而言，所述第一字典压缩规则用于处理于所有所述指令区块中以单一所述指令区块为单位而出现频率高于第一频率的一或复数个所述资料单元(例如表1的资料单元X)，所述第二字典压缩规则用于处理于所有所述指令区块中以单一所述指令区块为单位而出现频率介于第一与第二频率之间的一或复数个所述资料单元(例如表1的资料单元Y,Z)，所述第三字典压缩规则适用于处理于所有所述指令区块中以单一所述指令区块为单位而出现频率小于第二频率的一或复数个所述资料单元(例如表1的资料单元A,B,C,D)。

另外，为了对未经分析或尚未有相对应字典的指令集以较佳压缩方式进行压缩，本实施例可进一步包含下列步骤：

步骤S615(未图示)：依据复数个字典压缩规则分析所述指令集的资料组成及/或压缩率，藉此得到一分析结果。此时步骤S620进一步包含：依据所述分析结果使用所述复数个字典压缩规则压缩所述指令集。

更多关于图6的实施例的细节与变化可由图3的实施例的说明得知。

除上述的压缩方法外，本发明亦公开一种字典解压缩方法，用来通过解压缩产生一数位资料，适用于处理图3的实施例所产生的压缩码。如图7所示，所述解压缩方法的一实施例包含：

步骤S710：接收一第一偏移量(例如一第一程序计数值)；

步骤S720：依据所述第一偏移量找到一第一编码单元，其中所述第一编码单元属于复数个编码单元，且这些编码单元对应至少三个字典压缩规则。本实施例中，所有编码单元的位元数相同，相较之下，使用不同位元数的复数个编码单元来代表所述数位资料属于本领域的通常知识，然实施本发明者可依其需求决定编码单元的位元数的变化。

步骤S730：依据所述第一编码单元决定一字典起始位址。更详细的例子可由前述表1的说明得知。

步骤S740：依据复数个参数决定一字典内容位址，其中所述复数个参数包含所述第一编码单元与所述字典起始位址。举例而言，这些参数包含所述字典起始位址、所述第一偏移量、所述第一编码单元所属的一资料区块的大小、所述第一编码单元所属的一编码区块的大小以及所述第一编码单元决定一字典内容位址。更详细的例子可由前述表1的说明得知。

步骤S750：依据所述字典内容位址存取一存储器以得到所述第一编码单元所对应的一或复数个第一资料单元，所述一或复数个第一资料单元属于所述数位资料，其中所述字典起始位置对应至少三个字典的其中之一，所述至少三个字典分别对应前述至少三个字典压缩规则。举例来说，这些字典压缩规则包含第一、第二与第三字典压缩规则，所述第一字典压缩规则以N个资料区块为单位范围对所述数位资料中的第一内容进行压缩处理，所述第二字典压缩规则以M个资料区块为单位范围对所述数位资料中的第二内容进行压缩处理，第三字典压缩规则以L个资料区块为单位范围对所述数位资料中的第三内容进行压缩处理，所述第一、第二与第三内容不同，所述N、M、L为正整数且不大于所述复数个资料区块的总数，且所述N大于所述M，所述M大于所述L。更详细的例子可由前述表1的说明得知。

本发明另公开一种字典解压缩方法，专用于解压缩一微控制单元的压缩指令集。所述方法的一实施例如图8所示，包含：

步骤S810：接收一第一程序计数值。

步骤S820：依据所述第一程序计数值决定一第一编码单元，其中所述第一编码单元属于复数个编码单元，且这些编码单元对应复数个字典压缩规则。本实施例中，所有编码单元的位元数相同。

步骤S830：依据所述第一编码单元决定一字典起始位址。更详细的例子可由述揭表1的说明得知。

步骤S840：依据复数个参数决定一字典内容位址，其中所述复数个参数包含所述第一编码单元与所述字典起始位址。举例而言，这些参数包含所述字典起始位址、所述第一程序计数值、所述第一编码单元所属的一资料区块的大小、所述第一编码单元所属的一编码区块的大小以及所述第一编码单元决定一字典内容位址。更详细的例子可由前述表1的说明得知。

步骤S850：依据所述字典内容位址存取一存储器以得到所述第一编码单元所对应的一或复数个第一资料单元，所述一或复数个第一资料单元属于所述微控制单元的指令集，其中所述字典起始位置对应复数个字典的其中之一，所述复数个字典分别对应前述复数个字典压缩规则。举例而言，这些字典压缩规则包含第一与第二字典压缩规则，所述第一字典压缩规则以N个指令区块为单位范围对所述指令集中的第一内容进行压缩处理，所述第二字典压缩规则以M个指令区块为单位范围对所述指令集中的第二内容进行压缩处理，所述第一与第二内容不同，所述N、M为正整数且不大于所述复数个指令区块的总数，且所述N大于所述M。更详细的例子可由前述表1的说明得知。

本发明亦提出一种字典建构方法，用于数位资料的压缩或解压缩。如图9所示，所述方法的一实施例包含：

步骤S910：依据复数个字典压缩规则分析所述数位资料的资料组成及/或压缩率，藉此得到一分析结果，其中所述数位资料包含复数个资料区块，每所述资料区块包含复数个资料单元，每所述资料单元由复数个位元组成。举例来说，分析所述数位资料的步骤包含：扫描所述数位资料以建立复数个常数，其包含储存所述数位资料所需的存储器空间与所述数位资料中独立资料单元(亦即不同于其它资料单元的单元)；依据所述复数个字典压缩规则建立复数个变量，其包含一字典(例如全范围字典)占所述所有字典的比例；依据这些常数及变量的一部分或全部建立至少一推导参数，其包含所述字典所需的储存空间；以及根据所述复数个常数、所述复数个变量以及所述至少一推导参数产生所述分析结果。由于已知或自定义的演算法均可用来对资料进行分析，本领域人士可依其需求产生更多参考值(例如编码单元的位元数或资料区块所包含的资料单元数目等，又例如其它字典所需的储存空间等)或选用适当的参考值，藉此产生符合要求的分析结果。

步骤S920：依据所述分析结果以及所述数位资料建立至少三个字典，所述至少三个字典包含第一、第二与第三字典，分别对应第一、第二与第三字典压缩规则，所述第一字典压缩规则以N个所述资料区块为单位范围对所述数位资料中的第一内容进行压缩处理，所述第二字典压缩规则以M个所述资料区块为单位范围对所述数位资料中的第二内容进行压缩处理，第三字典压缩规则以L个所述资料区块为单位范围对所述数位资料中的第三内容进行压缩处理，所述第一、第二与第三内容均不同，所述N、M、L为正整数且不大于所述复数个资料区块的总数，且所述N大于所述M，所述M大于所述L。举例而言，第一、第二与第三字典压缩规则依序为全范围字典压缩规则、中范围字典压缩规则与局部范围字典压缩规则。更详细的例子可由前述表1的说明得知。

本发明另提出一种字典建构方法，专用于一微控制单元的指令集的压缩或解压缩。如图10所示，所述方法的一实施例包含：

步骤S110：依据复数个字典压缩规则分析所述指令集的资料组成及/或压缩率，藉此得到一分析结果，其中所述指令集包含复数个指令区块，每所述指令区块包含复数个资料单元，每所述资料单元由复数个位元组成。举例来说，分析所述指令集的步骤包含：扫描所述指令集以建立复数个常数，其包含储存所述指令集所需的存储器空间与所述指令集中的独立资料单元；依据所述复数个字典压缩规则建立复数个变量，其包含一字典占所述所有字典的比例；依据这些常数及变量的一部分或全部建立至少一推导参数，其包含所述字典所需的存储器空间；以及根据所述复数个常数、所述复数个变量以及所述至少一推导参数产生所述分析结果。类似地，由于已知或自定义的演算法均可用来对指令集进行分析，本领域人士可依其需求产生更多参考值(例如编码单元的位元数或资料区块所包含的资料单元数目等，又例如其它字典所需的储存空间等)或选用适当的参考值，藉此产生符合要求的分析结果。

步骤S120：依据所述分析结果以及所述指令集建立复数个字典，所述复数个字典包含第一字典与一第二字典，分别对应第一与第二字典压缩规则，所述第一字典压缩规则以N个指令区块为单位范围对所述指令集中的第一内容进行压缩处理，所述第二字典压缩规则以M个指令区块为单位范围对所述指令集中的第二内容进行压缩处理，所述第一与第二内容不同，所述N、M为正整数且不大于所述复数个指令区块的总数，且所述N大于所述M。举例而言，第一与第二字典压缩规则依序为全范围字典压缩规则与中范围或局部范围字典压缩规则。更详细的例子可由前述表1的说明得知。

由于本技术领域人士能够依不同实施例的说明来交互了解实施细节与变化，更明确地说，各实施例的技术特征均可合理应用于其它实施例中，因此，在不影响本发明的公开要求与可实施性的前提下，重复及冗余的说明在此予以节略。

综上所述，本发明的字典压缩方法、字典解压缩方法与字典建构方法采用了复数层级的字典，能够应用于数位资料或指令集的无失真压缩或解压缩，除能减少储存所需的存储器空间以降低成本，并能从任一编码单元开始进行解压缩。

虽然本发明的实施例如上所述，然而这些实施例并非用来限定本发明，本技术领域具有通常知识者可依据本发明的明示或隐含的内容对本发明的技术特征施以变化，凡此种种变化均可能属于本发明所寻求的专利保护范畴，换言之，本发明的专利保护范围须视本说明书的申请专利范围所界定者为准。

【符号说明】

100、200微控制单元架构

110、210存储器及其控制器

120、220系统汇流排

130、230指令储存高速缓存

140、240资料储存高速缓存

150、250微控制单元

400记忆电路

410压缩码储存单元

420字典储存单元

430选择电路

S310接收数位资料，所述数位资料包含复数个资料区块

S320依据一多层级字典压缩演算法压缩所述数位资料，其中所述多层级字典压缩演算法包含第一、第二与第三字典压缩规则分别对应不同单位范围

S610接收一指令集，所述指令集包含复数个指令区块

S620依据复数个字典压缩规则压缩所述指令集，其中所述复数个字典压缩规则包含第一与第二字典压缩规则分别对应不同单位范围

S710接收一第一偏移量

S720依据所述第一偏移量找到一第一编码单元，其中所述第一编码单元属于复数个编码单元，且这些编码单元对应至少三个字典压缩规则

S730依据所述第一编码单元决定一字典起始位址

S740依据复数个参数决定一字典内容位址，其中所述复数个参数包含所述第一编码单元与所述字典起始位址

S750依据所述字典内容位址存取一存储器以得到所述第一编码单元所对应的一或复数个资料单元

S810接收一第一程序计数值

S820依据所述第一程序计数值找到一第一编码单元，其中所述第一编码单元属于复数个编码单元，且这些编码单元对应复数个字典压缩规则

S830依据所述第一编码单元决定一字典起始位址

S840依据复数个参数决定一字典内容位址，其中所述复数个参数包含所述第一编码单元与所述字典起始位址

S850依据所述字典内容位址存取一存储器以得到所述第一编码单元所对应的一或复数个资料单元

S910依据复数个字典压缩规则分析数位资料的资料组成及/或压缩率，藉此得到一分析结果，其中所述数位资料包含复数个资料区块

S920依据所述分析结果以及所述数位资料建立至少三个字典，所述至少三个字典包含第一、第二与第三字典，分别对应不同单位范围的第一、第二与第三字典压缩规则

S110依据复数个字典压缩规则分析一指令集的资料组成及/或压缩率，藉此得到一分析结果，其中所述指令集包含复数个指令区块

S120依据所述分析结果以及所述指令集建立复数个字典，所述复数个字典包含第一字典与一第二字典，分别对应不同单位范围的第一与第二字典压缩规则。