基于BWT的文本压缩算法研究.pdfVIP

第 J9卷 第 5期 计 算 机 技 术 与 发 展 Vo1．19 No．5 2009年 5月 ODMPU1、ERTECHNoLOGY ANDDE＼rELOPMENT May 2009 基于BWT的文本压缩算法研究 李彦军，苏红旗，杨 峰 ，李述迪，姚书科 (中国矿业大学机 电学院，北京 100083) 摘 要：为了理解高效的文本压缩算法 ，探究文本压缩的原理和意义，对基于BwT的字符串轮转理论进行了深入的理解 ； 游程编码作为一种简单有效的压缩方式，在数据压缩中有十分广泛的应用，文本压缩的研究对于多媒体的压缩研究有着 十分重要 的意义。把BwT结合游程编码对选定的文本信息进行了压缩比较 ，实验证明了该算法的高效性和实用性。同 时对基于B、vT压缩算法的发展趋势进行了展望及分析。 关键词 ：BWT；压缩算法 ；文本压缩 ；游程编码 中图分类号：TP301．6 文献标识码 ：A 文章编号 ：1673—629X(2009)05—0089—04 ResearchofBW T CompressionAlgorithm BasedonText LIYah—jun，SUHong—qi，YANGFeng，LIShu—di，YAOShu．ke (ChinaUniversityofMiningandTechnology，Beijing100083，China) Abstract：Inordertounderstandthetextefficientcompressionalgorithm ，inquiringtextandmeaningoftheprincipleofcompression，the paperisbasedonthestring transformationhasocnductedin—depthunderstanding．therun—lengthcoding asasimpleandeffectivecorn— pre~ionindataocmpressionhasaverywidersllgeofapplication．ocmpressedversionofthemultirndeiaocmpressionresearchisveryim— pol-tant．CombiningtheBwT andtherun—lengthcodingthetextofselectde informationiscompressed．theexperimnetpmvde thatthe algoritmh isefficientna dpractica1．Atthesametime，BWT compressionalgorithm basedonthedevelopmenttrendsandanalysisofthe prospect． Keywords：BW T；compressionalgoritmh ；textcompression；run—lengthcoding O 引 言 较用BwT具有比较理想的效果。 数据压缩分为有损压缩和无损压缩两大类，而无 损压缩的迅速发展催生了诸如：Huffman编码，算术 1 文本压缩 编码，L—Z系列编码，动态 马尔科夫压缩编码 1．1 数据压缩 (DMC)，PPM 编码和 Burrows一、 eelerTransfo-／in 数据压缩的目的就是用较少的数码来表示原始的 (BWT)编码算法的产生。1994年 MichaelBurrows和 信号数据。在实际的应用中数据压缩的方法按照不同 DavidWheeler在 {ABlock—sortingLosslessDataCom— 的压缩原理有不同的方法，根据解码后数据与原始数 pressionAlgorithm)--文 中共同提 出的通用数据压缩