Active LeZi算法的改進

黃穎琦

（貴陽中醫學院 基礎醫學院 數學微機教研室，貴陽 550025 ）

0 引言

壓縮算法可用于數據預測和文本統計分析領域。Karthik Gopalrathma等人在LZ壓縮算法基礎上提出Active Lezi即ALZ[1]算法用于文本數據和時序數據的預測、機器人定位及機器人智能學習、模式識別算法，應用前景廣闊。算法實現為：按字母順序編碼具體發生行為，統計一定時期內的實際發生行為對應字母，作為輸入源碼輸入給ALZ算法，該算法通過下表算法1的編碼計算分析，預測出以后將要發生的行為系列。但在大量相同行為重復的情況下，原算法滑動窗口設立的缺陷，導致預測編碼的遺漏而降低預測率。本論文對原算法進行了研究和介紹，提出了一種雙窗口結構的改進ALZ算法，

在不改變算法復雜度的情況下增加了預測編碼生成，提高了編碼數據頻率統計的準確率，從而提高預測算法的預測率。

1 ALZ預測算法編碼誤差分析

ALZ算法是LZ壓縮算法的改進算法，提出使用一個滑動窗口的方式控制輸入的源碼的數量，生成存儲在Trie樹中的壓縮編碼，利用存儲在Trie樹中的編碼字典，找到系列中的編碼值，從而推測下一個輸入的數據值，實現預測目的。從大量重復出現的數據中尋求規律，用滑動窗口來生成壓縮編碼。原算法中滑動窗口條件的設立，使重復數據在編碼生成上造成遺漏，并且因統計數據頻率的誤差影響算法的預測率，原論文中給出的算法，由于生成樹中形成的編碼遺漏在重碼率高的情況下出現頻繁，導致算法預測準確率降低。原論文[1]中給出的ALZ算法如圖1所示。

圖1 ALZ算法

原算法中，當大量的輸入源碼為重復代碼時，在Trie樹深度無需增長的情況下，就能在編碼字典中找到已有編碼，不能生成新的長度更大的編碼，作為壓縮算法來說，這正是原壓縮算法的優點，但ALZ作為預測算法來說，會因生成編碼的遺漏而影響預測的準確率，如本來可以生成長度為4的“aaaa”的編碼，因只生成長度為3的“aaa”而減少了能預測的編碼長度值，同時因為生成編碼的不完善影響編碼頻率統計。原論文中給出的原例，用原算法對輸入字符串：“aaababbbbbaabccddcbaaaa”進行編碼，算法生成的存儲在字典中的編碼字符串為：“a,b,c,d,aa,ab,ba,bb,bc,cb,cc,cd,dc,dd,aaa,aab,abc,baa,bba,bcc,cba,ccd,cdd,dcb,ddc”,查找源代碼可見，編碼中遺漏了重復率最高的“b”字符的生成編碼“bbb”；由生成的Trie樹統計頻率見圖，編碼“aa”出現的實際頻率應為6次，而算法僅統計為5次，“aaa”僅統計為2次……

圖2 原ALZ算法輸入字符串：“aaababbbbbaabccddcbaaaa”生成Trie樹

原算法生成的Trie樹如圖2所示。

2 ALZ預測算法改進

2.1 ALZ改進算法雙窗口結構

針對以上算法缺陷，本文對輸入數據的重復源碼，提出雙窗口結構，以完善ALZ算法滑動窗口的程式設計。算法設計為用兩個窗口來檢測源碼，一個窗口記錄滑動前的窗口值prewindow，一個窗口記錄滑動后的窗口值window，每次滑動后比較兩個值,如果不同則window繼續向前滑動，如果相同的話，說明出現了重碼現象，記錄下相同的次數time，繼續向前滑動，當再次相同時time值加1，循環滑動，當time值等于滑動窗口的長度值時，說明出現了相當于兩個窗口量的重復源碼，增長Trie樹深度的可能性得以滿足，將窗口長度增加1，加入新編碼，同時Trie樹深度加1。循環讀入新字符進行編碼，當編碼長度超過窗口長度時，滑動窗口長度亦增加為編碼長度。

2.2 ALZ改進算法偽碼

改進后的ALZ算法如圖3所示。

圖3 改進后的ALZ算法

2.3 ALZ改進算法應用分析

用改進ALZ算法對上例輸入字符串：“aaababbbbbaabccddcbaaaa” 進 行編碼，算法生成的存儲在字典中的編碼字符串為：“a,b,c,d,aa,ab,ba,bb,bc,cb,cc,cd,dc,dd,aaa,bbb,aab,abc,baa,bba,bcc,c ba,ccd,cdd,dcb,ddc”，改進的ALZ算法生成的trie樹如圖4所示。

圖4 改進ALZ算法生成Trie樹

由改進算法生成的編碼比原算法生成的編碼多生成了后綴“bbb”，生成的字典編碼為：(a, aa,aaa)，比原算法提前生成了最長可能的編碼aaa，達到生成樹編碼的收斂。對于大量出現重碼的輸入數據，由于此雙窗口程式的設立，對同一字符的編碼能實現長度順序遞增的編碼組合，在不同層生成長度不一的相同編碼組合，防止了生成編碼的遺漏。

在算法的編碼預測方面，ALZ采用PPM預測方式，利用已知的概率預測下一編碼，在trie樹的每一個結點都分配一個概率值，每次讀入字符都要對樹中相應結點的概率進行新的計算和分配。頻率統計準確率的提高，將提高概率統計預測的準確率。

3 ALZ 原算法與ALZ改進算法的比較分析

表1是改進算法與未改進算法對于圖2，圖4示例數據的比較。

由表1可看出，在輸入樣本數據僅為23個字符，重碼現象僅為2個字符，“aaa”3次，“bbb”3次的情況下，改進的ALZ算法就將編碼統計準確率從68.97%提高到86.21%，在編碼生成各方面都有所改進。輸入的樣本數據重碼率越高，即同一字符重復出現越頻繁，原ALZ算法的編碼遺漏現象越嚴重，準確率越低，而改進的ALZ算法較之未改進的算法，編碼統計準確率提高越大，在以上各方面的改進效果越明顯。

表1 ALZ原算法與改進算法比較

4 結束語

改進后的算法在未改變原算法時間復雜度的情況下，對如何滑動窗口以及何時需要增長窗口的長度進行了詳細設置，對于重碼現象進行了程式處理，彌補了原算法在編碼生成遺漏方面的缺陷。改進ALZ算法采用雙窗口結構防止了生成編碼的遺漏，提高了ALZ算法的預測準確率。改進后的算法可廣泛應用于大量機械動作重復的機器智能學習、機器人定位等領域。

[1] KARTHIK GOPALRATNAM and DIANE J.COOK,Online Sequential Prediction via Incremental Parsing: The Active LeZi Algorithm，IEEE Intelligent Systems, 2007,22(1): P52-58.

[2] SAJAL K.DAS, 等.THE ROLE OF PREDICTION ALGORITHMS IN THE MAVHOME SMART HOME ARCHITECTURE, IEEE Wireless Communications, 2002,(11): P2-9.

[3] 黃穎琦, SmartHome預測算法研究與比較[J].計算機光盤軟件與應用, 2010, (9): 93.