ActiveLeZi算法的改进.pdfVIP

学兔兔 1造 訇 化 Active LeZi算法的改进 The improvement and research of A Z algorithm design 黄颖琦 HUANG Ying．qi (贵阳中医学院 基础医学院 数学微机教研室，贵阳550025) 摘 要：基于Lz压缩算法的Active Lezi算法，用于机器人定位、文本数据和时序数据的预测及统计 时，原滑动窗口设立的缺陷。导致生成编码的遗漏而降低预测率及统计效率，本文对ALZ算 法进行了研究和改进，在原滑动窗口设计缺陷上提出了双窗口结构，在滑动窗口处理大量重 复源码方面实现了程序改进，提高了生成编码统计和预测准确率，改进了ALZ算法。 关键词：Active Lezi算法；滑动窗口；ALZ编码；预测算法；机器学习算法；Lz算法 中国分类号：TP311．1 文献标识码：A 文童编号：1 009-01 34(201 2)07(下)-o11 0-02 Doi：1 0．3969／J．issn．1 009-01 34．201 2．7(下)．35 0 引言 压缩算法可用于数据预测和文本统计分 析领域。Kard~k Gopalrathma等人在LZ压 缩算法基础上提出Active Lezi即ALZ[ 算法 用于文本数据和时序数据的预测、机器人定 位及机器人智能学习、模式识别算法，应用 前景广阔。算法实现为：按字母顺序编码具 体发生行为，统计一定时期内的实际发生行 图1 ALZ算法 为对应字母，作为输入源码输入给ALZ算法，该 算法通过下表算法1的编码计算分析，预测出以后 的算法，由于生成树中形成的编码遗漏在重码率 将要发生的行为系列。但在大量相同行为重复的情 高的情况下出现频繁，导致算法预测准确率降低。 况下，原算法滑动窗口设立的缺陷，导致预测编码 原论文 中给出的ALz算法如图1所示。 的遗漏而降低预测率。本论文对原算法进行了研究 原算法中，当大量的输入源码为重复代码时， 和介绍，提出了一种双窗口结构的改进 算法， 在Trie树深度无需增长的情况下，就能在编码字典 在不改变算法复杂度的情况下增加了预测编码生 中找到已有编码，不能生成新的长度更大的编码， 成，提高了编码数据频率统计的准确率，从而提高 作为压缩算法来说，这正是原压缩算法的优点，但 预测算法的预测率。 作为预测算法来说，会因生成编码的遗漏而 1 ALZ预测算法编码误差分析 影响预测的准确率，如本来可以生成长度为4的 “ ALZ算法是LZ压缩算法的改进算法，提出 aaaa”的编码，因只生成长度为3的 “aaa”而减少 使用一个滑动窗口的方式控制输入的源码的数量， 了能预测的编码长度值，同时因为生成编码的不完 生成存储在Trie树中的压缩编码，利用存储在 善影响编码频率统计。原论文中给出的原例，用原 Tile树中的编码字典，找到系列中的编码值，从而 算法对输入字符串：“aaababbbbbaabccddcbaaaa”进 推测下一个输入的数据值，实现预测目的。