串編輯和LZW壓縮算法設(shè)計(jì)

趙美勇 史昊臻 朱珍珍

摘? 要：串編輯一類字符串轉(zhuǎn)換的問題，將兩個(gè)字符串按照某種規(guī)則進(jìn)行轉(zhuǎn)換，轉(zhuǎn)換將有三個(gè)消費(fèi)函數(shù)，利用動(dòng)態(tài)規(guī)劃的方法可以得到各個(gè)操作的耗費(fèi)之和，解決串編輯的問題。利用HASH鏈?zhǔn)缴⒘衼韺?shí)現(xiàn)LZW壓縮方法，利用字典組織，節(jié)省空間降低算法的復(fù)雜度，從而達(dá)到快速的代碼簡(jiǎn)化法。

關(guān)鍵詞：串編輯;LZW壓縮;動(dòng)態(tài)規(guī)劃;HASH

中圖分類號(hào)：TP301.6? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2019）08-0094-03

Abstract：String editing a class of string conversion problem，the two strings are converted according to a certain rule，the conversion will have three consumption functions，using the dynamic programming method can get the sum of the cost of each operation，solve the problem of string editing. LASH compression method is implemented by HASH chain hashing，which uses dictionary organization to save space and reduce the complexity of the algorithm，thus achieving fast code simplification.

Keywords：string editing;LZW compression;dynamic programming;HASH

0? 引? 言

串編輯是一類動(dòng)態(tài)規(guī)劃問題，也是一類優(yōu)化問題。在一些大型的字符串算法中，比如：后綴樹、AC自動(dòng)機(jī)、KMP等算法中，其作用相當(dāng)重要。它主要解決的就是字符串轉(zhuǎn)換問題，將兩個(gè)字符串按照某種規(guī)則轉(zhuǎn)換，其中轉(zhuǎn)換的代價(jià)就是所要求得目標(biāo)。它利用的動(dòng)態(tài)規(guī)劃的思想，通過記憶化搜索保存每種狀態(tài)，這個(gè)算法在轉(zhuǎn)換一些大字符串時(shí)表現(xiàn)相當(dāng)優(yōu)秀。LZW壓縮算法是處理圖像壓縮的，應(yīng)用在某些神經(jīng)網(wǎng)絡(luò)算法中，因?yàn)槠鋬?yōu)秀的圖像壓縮功能，可以大幅度減少神經(jīng)網(wǎng)絡(luò)在處理卷積時(shí)的復(fù)雜度。

1? 串編輯和LZW壓縮算法需求描述

1.1? 串編輯算法需求

在串編輯問題中，給出兩個(gè)串a(chǎn)=a1a2…an和b=b1b2…bm及三個(gè)耗費(fèi)函數(shù)C，D和I。其中C（i，j）為將ai改為bj的耗費(fèi)，D（i）為從a中刪除ai的耗費(fèi)，I（i）為將bi插入a中的耗費(fèi)。通過修改、刪除和插入操作可把串a(chǎn)改為串b。如可刪除所有ai，然后插入所有bi;或者當(dāng)n≥m時(shí)，可先把a(bǔ)i變成bi（i≤i≤n），然后刪除其余的ai。整個(gè)操作序列的耗費(fèi)為各個(gè)操作的耗費(fèi)之和。

1.2? LZW壓縮算法需求

在一個(gè)文本文件上實(shí)現(xiàn)LZW壓縮和解壓縮，其中每個(gè)字符就是該文本的8位ASCLL碼;對(duì)一個(gè)256色BMP圖片文件實(shí)現(xiàn)壓縮和解壓縮。

2? 串編輯和LZW壓縮算法設(shè)計(jì)

2.1 串編輯設(shè)計(jì)

2.1.1? 數(shù)據(jù)及數(shù)據(jù)類型定義

（1）輸入模塊：

用戶使用鍵盤完成字符串a(chǎn)和b的輸入。

（2）編輯模塊：

首先調(diào)用隨機(jī)模塊，隨機(jī)產(chǎn)生三個(gè)函數(shù)的值。設(shè)f[i][j]為將字符串a(chǎn)的前i個(gè)字符改為字符串b的前j個(gè)字符的最小耗費(fèi)，考慮f[i][j]可能的取值：將字符串a(chǎn)的前i個(gè)字符改為字符串b的前j-1個(gè)字符，再將字符串b的第j個(gè)字符插入到a中，即：f[i][j]=f[i][j-1]+I[j]。將字符串a(chǎn)的前i-1個(gè)字符改為字符串b的前j個(gè)字符，再將字符串a(chǎn)的第i個(gè)字符刪除，即：f[i][j]=f[i-1][j]+D[i]。如果字符a[i]和b[j]相等，則：f[i][j]=f[i-1][j-1]。如果字符a[i]和b[j]不相等，可以將字符串a(chǎn)的前i-1個(gè)字符改為字符串b的前j-1個(gè)字符，再將a[i]改為b[j]，即：f[i][j]=f[i-1][j-1]+C[i][j]，f[i][j]的取值為上面四種情況的最小值。為了方便輸出路徑，還需要記錄它的前一個(gè)狀態(tài)指針和得到當(dāng)前狀態(tài)的操作。

（3）隨機(jī)模塊：

通過分析可知，函數(shù)C對(duì)應(yīng)一個(gè)大小為|a|*|b|的二維數(shù)組，函數(shù)D對(duì)應(yīng)長(zhǎng)度為|a|的一維數(shù)組，函數(shù)I對(duì)應(yīng)長(zhǎng)度為|b|的一位數(shù)組;通過C++的隨機(jī)函數(shù)rand（）為數(shù)組每一個(gè)位置賦值，并且分析可知，修改、刪除、插入操作都可以在線性時(shí)間內(nèi)完成，因此每個(gè)的大小應(yīng)該小于字符串的長(zhǎng)度，大于0。

（4）輸出模塊：

通過編輯模塊中記錄的狀態(tài)指針，從f[|a|][|b|]移動(dòng)到f[1][1]，將得到的編輯序列逆序輸出，即為最小耗費(fèi)對(duì)應(yīng)的編輯序列。

2.1.2? 數(shù)據(jù)及數(shù)據(jù)類型定義

（1）每個(gè)狀態(tài)需要儲(chǔ)存的信息：

w為當(dāng)前狀態(tài)的最小耗費(fèi)，fi、fj為上一狀態(tài)的下標(biāo)，id表示得到當(dāng)前狀態(tài)操作的標(biāo)號(hào)。

（2）操作序列每一項(xiàng)的信息：

記錄對(duì)a[i]和b[j]進(jìn)行對(duì)應(yīng)操作的id號(hào)。

（3）串編輯類：

C、D、I三個(gè)數(shù)組分別代表修改、刪除、插入三個(gè)函數(shù)，edg存儲(chǔ)編輯序列，f為存儲(chǔ)狀態(tài)。

2.1.3? 設(shè)計(jì)及分析

（1）編輯模塊：

（2）時(shí)間復(fù)雜度分析：

隨機(jī)模塊中生成D和I數(shù)組需要線性時(shí)間，生成C數(shù)組的時(shí)間復(fù)雜度為O（|a|*|b|）;編輯模塊中狀態(tài)共有|a|*|b|個(gè)，每次狀態(tài)轉(zhuǎn)移為常數(shù)時(shí)間，因此時(shí)間復(fù)雜度為O（|a||b|）;輸出編輯序列需要線性時(shí)間。綜上，總的時(shí)間復(fù)雜度為O（|a|*|b|）。

2.2? LZW壓縮算法設(shè)計(jì)

2.2.1? 結(jié)構(gòu)設(shè)計(jì)

LZW壓縮和解壓使用了鏈?zhǔn)缴⒘斜?BMP圖片構(gòu)造圖片信息格式。

2.2.2? 數(shù)據(jù)及數(shù)據(jù)類型定義

字典中的元素使用數(shù)對(duì)來表示，類型定義：template <class K， class E>;圖片類型包括文件類型、信息頭、像素信息。

2.2.3? 算法設(shè)計(jì)及分析

（1）抽象字典類：

（2）Hashchains實(shí)現(xiàn)字典類：

（3）壓縮LZW類：

（4）解壓縮UNLZW類：

3? 結(jié)? 論

利用動(dòng)態(tài)規(guī)劃方法，基本解決了串編輯問題。但因?yàn)轭}目中C、D、I三個(gè)函數(shù)的限制較少，我們采用隨機(jī)生成的方式并不是很好，這里就沒有考慮字符串中出現(xiàn)相同的字符的問題，例如：對(duì)于相同的字符，執(zhí)行插入操作和刪除操作的耗費(fèi)是不是一樣？因此，具體的串編輯問題還需要重新設(shè)計(jì)隨機(jī)模塊。另外，我們還期望將執(zhí)行每個(gè)操作之后a數(shù)組的變化展現(xiàn)給用戶。

HASH鏈?zhǔn)缴⒘袑?shí)現(xiàn)形式下的一個(gè)應(yīng)用LZW壓縮的實(shí)現(xiàn)方法。在壓縮中對(duì)字典組織的使用，以及為了節(jié)省空間降低算法復(fù)雜度以達(dá)到加快速度的代碼簡(jiǎn)化法，還有在對(duì)圖片文件處理時(shí)了解BMP文件本身不單單是多個(gè)像素塊的堆疊，它有明確的格式，復(fù)雜的構(gòu)造，包括三個(gè)頭部信息，一個(gè)圖片像素信息。

參考文獻(xiàn)：

[1] Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，等.算法導(dǎo)論 [M].第3版.殷建平，徐云，王剛，等，譯.北京：機(jī)械工業(yè)出版社，2012.

[2] Robert Sedgewick，Kevin Wayne.算法 [M].第4版.謝路云，譯.北京：人民郵電出版社，2012.

[3] Brian W. Kernighan，Dennis M. Ritchie.C程序設(shè)計(jì)語言 [M].徐寶文，李志，譯.北京：機(jī)械工業(yè)出版社，2004.

[4] 劉汝佳，陳鋒.算法競(jìng)賽入門經(jīng)典：訓(xùn)練指南 [M].北京：清華大學(xué)出版社，2012.

[5] 劉汝佳.算法競(jìng)賽入門經(jīng)典 [M].第2版.北京：清華大學(xué)出版社，2014.

作者簡(jiǎn)介：趙美勇（1997-），男，漢族，山東聊城人，本科，主要研究方向：計(jì)算機(jī)科學(xué)與技術(shù);史昊臻（1998-），女，漢族，山東菏澤人，本科，主要研究方向：通信工程;朱珍珍（1998-），女，漢族，河南駐馬店人，本科，主要研究方向：信息管理與信息系統(tǒng)。