黃穎琦

（貴陽中醫(yī)學(xué)院 基礎(chǔ)醫(yī)學(xué)院 數(shù)學(xué)微機(jī)教研室，貴陽 550025 ）

0 引言

壓縮算法可用于數(shù)據(jù)預(yù)測(cè)和文本統(tǒng)計(jì)分析領(lǐng)域。Karthik Gopalrathma等人在LZ壓縮算法基礎(chǔ)上提出Active Lezi即ALZ[1]算法用于文本數(shù)據(jù)和時(shí)序數(shù)據(jù)的預(yù)測(cè)、機(jī)器人定位及機(jī)器人智能學(xué)習(xí)、模式識(shí)別算法，應(yīng)用前景廣闊。算法實(shí)現(xiàn)為：按字母順序編碼具體發(fā)生行為，統(tǒng)計(jì)一定時(shí)期內(nèi)的實(shí)際發(fā)生行為對(duì)應(yīng)字母，作為輸入源碼輸入給ALZ算法，該算法通過下表算法1的編碼計(jì)算分析，預(yù)測(cè)出以后將要發(fā)生的行為系列。但在大量相同行為重復(fù)的情況下，原算法滑動(dòng)窗口設(shè)立的缺陷，導(dǎo)致預(yù)測(cè)編碼的遺漏而降低預(yù)測(cè)率。本論文對(duì)原算法進(jìn)行了研究和介紹，提出了一種雙窗口結(jié)構(gòu)的改進(jìn)ALZ算法，

在不改變算法復(fù)雜度的情況下增加了預(yù)測(cè)編碼生成，提高了編碼數(shù)據(jù)頻率統(tǒng)計(jì)的準(zhǔn)確率，從而提高預(yù)測(cè)算法的預(yù)測(cè)率。

1 ALZ預(yù)測(cè)算法編碼誤差分析

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

圖1 ALZ算法

原算法中，當(dāng)大量的輸入源碼為重復(fù)代碼時(shí)，在Trie樹深度無需增長的情況下，就能在編碼字典中找到已有編碼，不能生成新的長度更大的編碼，作為壓縮算法來說，這正是原壓縮算法的優(yōu)點(diǎn)，但ALZ作為預(yù)測(cè)算法來說，會(huì)因生成編碼的遺漏而影響預(yù)測(cè)的準(zhǔn)確率，如本來可以生成長度為4的“aaaa”的編碼，因只生成長度為3的“aaa”而減少了能預(yù)測(cè)的編碼長度值，同時(shí)因?yàn)樯删幋a的不完善影響編碼頻率統(tǒng)計(jì)。原論文中給出的原例，用原算法對(duì)輸入字符串：“aaababbbbbaabccddcbaaaa”進(jìn)行編碼，算法生成的存儲(chǔ)在字典中的編碼字符串為：“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”,查找源代碼可見，編碼中遺漏了重復(fù)率最高的“b”字符的生成編碼“bbb”；由生成的Trie樹統(tǒng)計(jì)頻率見圖，編碼“aa”出現(xiàn)的實(shí)際頻率應(yīng)為6次，而算法僅統(tǒng)計(jì)為5次，“aaa”僅統(tǒng)計(jì)為2次……

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

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

2 ALZ預(yù)測(cè)算法改進(jìn)

2.1 ALZ改進(jìn)算法雙窗口結(jié)構(gòu)

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

2.2 ALZ改進(jìn)算法偽碼

改進(jìn)后的ALZ算法如圖3所示。

圖3 改進(jìn)后的ALZ算法

2.3 ALZ改進(jìn)算法應(yīng)用分析

用改進(jìn)ALZ算法對(duì)上例輸入字符串：“aaababbbbbaabccddcbaaaa” 進(jìn) 行編碼，算法生成的存儲(chǔ)在字典中的編碼字符串為：“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”，改進(jìn)的ALZ算法生成的trie樹如圖4所示。

圖4 改進(jìn)ALZ算法生成Trie樹

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

在算法的編碼預(yù)測(cè)方面，ALZ采用PPM預(yù)測(cè)方式，利用已知的概率預(yù)測(cè)下一編碼，在trie樹的每一個(gè)結(jié)點(diǎn)都分配一個(gè)概率值，每次讀入字符都要對(duì)樹中相應(yīng)結(jié)點(diǎn)的概率進(jìn)行新的計(jì)算和分配。頻率統(tǒng)計(jì)準(zhǔn)確率的提高，將提高概率統(tǒng)計(jì)預(yù)測(cè)的準(zhǔn)確率。

3 ALZ 原算法與ALZ改進(jìn)算法的比較分析

表1是改進(jìn)算法與未改進(jìn)算法對(duì)于圖2，圖4示例數(shù)據(jù)的比較。

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

表1 ALZ原算法與改進(jìn)算法比較

4 結(jié)束語

改進(jìn)后的算法在未改變?cè)惴〞r(shí)間復(fù)雜度的情況下，對(duì)如何滑動(dòng)窗口以及何時(shí)需要增長窗口的長度進(jìn)行了詳細(xì)設(shè)置，對(duì)于重碼現(xiàn)象進(jìn)行了程式處理，彌補(bǔ)了原算法在編碼生成遺漏方面的缺陷。改進(jìn)ALZ算法采用雙窗口結(jié)構(gòu)防止了生成編碼的遺漏，提高了ALZ算法的預(yù)測(cè)準(zhǔn)確率。改進(jìn)后的算法可廣泛應(yīng)用于大量機(jī)械動(dòng)作重復(fù)的機(jī)器智能學(xué)習(xí)、機(jī)器人定位等領(lǐng)域。

[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預(yù)測(cè)算法研究與比較[J].計(jì)算機(jī)光盤軟件與應(yīng)用, 2010, (9): 93.