基于多层哈希结构与游程编码的数据无损压缩方法

摘要

本发明公开了一种基于多层哈希结构与游程编码的数据无损压缩方法，主要解决LZO压缩方法对重复数据压缩效果不佳以及搜索匹配字符串时难以找到最长匹配字符串的问题。其实现步骤是：(1)读入原始数据并用游程编码对其进行预处理，得到待压缩数据；(2)判断所读数据是否为新字符，若不是，则搜索最长匹配字符串，并根据字符重复长度和指回距离进行编码，若是，则按照新字符的编码方法进行编码；(3)根据编码字符更新读取位置，并根据读取位置判断是否编码到待压缩数据的结尾，若是则终止，若不是，则继续读入待压缩数据，返回步骤(2)。本发明与现有的其他无损压缩方法相比，压缩效率更好，可用在对数据的压缩速度和压缩效率均有要求的存储设备中。

主权项

一种基于多层哈希结构与游程编码的数据无损压缩方法，包括以下步骤：（1）初始化：读入原始数据，用游程编码方法对其进行预处理，即把原始数据中有重复的字符串编码为重复字符加上重复长度的格式，得到待压缩数据；（2）初始化读取位置为待压缩数据中第一个字符位置，初始化哈希表为空表，并设置读取规则，即每次从初始化后的待压缩数据中读取四个字符，每一次读取后，读取位置后移四个字符；（3）区分新字符和匹配字符，若是匹配字符则在哈希表中寻找最长匹配字符串：（3a）按照读取规则从待压缩数据中读取四个字符，若这四个字符没有记录在哈希表中，则判为新字符，执行步骤（4），并把该新字符存入哈希表中，初始化匹配次数p为0；若哈希表中有记录，则不是新字符，即当前字符与哈希表中记录字符匹配，进行步骤（3b），更新匹配次数p为1；（3b）按照读取规则继续从待压缩数据中读取四个字符，若该四个字符与步骤（3a）中找到的哈希表中记录的字符串依然匹配，则令匹配次数p加1，更新哈希表中记录的字符位置为当前匹配字符位置；否则，执行步骤（4），并把当前字符串存入哈希表；（3c）重复执行步骤（3b），至多5次，在哈希表记录的字符串中找出与当前字符串最长的匹配字符串并将其存入哈希表；（4）若是新字符，则按照LZO新字符的编码方法进行压缩编码；否则根据字符重复长度和指回距离即当前字符位置与哈希表内记录位置之间的距离，按照LZO的编码格式进行压缩编码；（5）判断是否编码至待压缩数据结尾，若是，则输出压缩后数据和压缩后数据的长度，并记下结束标志，否则，执行步骤（6）；（6）若匹配次数p等于1，按照新模式从待压缩数据中读取字符并存储至哈希表，返回步骤（3）；否则，更新读取位置为待编码字符位置按照原读取规则从待压缩数据中读取字符，返回步骤（3）。