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

趙美勇 史昊臻 朱珍珍

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

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

中圖分類號：TP301.6? ? ? ?文獻標識碼：A 文章編號：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? 引? 言

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

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

1.1? 串編輯算法需求

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

1.2? LZW壓縮算法需求

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

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

2.1 串編輯設(shè)計

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

（1）輸入模塊：

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

（2）編輯模塊：

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

（3）隨機模塊：

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

（4）輸出模塊：

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

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

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

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

（2）操作序列每一項的信息：

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

（3）串編輯類：

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

2.1.3? 設(shè)計及分析

（1）編輯模塊：

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

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

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

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

LZW壓縮和解壓使用了鏈式散列表;BMP圖片構(gòu)造圖片信息格式。

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

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

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

（1）抽象字典類：

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

（3）壓縮LZW類：

（4）解壓縮UNLZW類：

3? 結(jié)? 論

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

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

參考文獻：

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

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

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

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

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

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