串編輯和LZW壓縮算法設計

趙美勇 史昊臻 朱珍珍

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

關鍵詞：串編輯;LZW壓縮;動態規劃;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? 引? 言

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

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

1.1? 串編輯算法需求

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

1.2? LZW壓縮算法需求

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

2? 串編輯和LZW壓縮算法設計

2.1 串編輯設計

2.1.1? 數據及數據類型定義

（1）輸入模塊：

用戶使用鍵盤完成字符串a和b的輸入。

（2）編輯模塊：

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

（3）隨機模塊：

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

（4）輸出模塊：

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

2.1.2? 數據及數據類型定義

（1）每個狀態需要儲存的信息：

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

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

記錄對a[i]和b[j]進行對應操作的id號。

（3）串編輯類：

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

2.1.3? 設計及分析

（1）編輯模塊：

（2）時間復雜度分析：

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

2.2? LZW壓縮算法設計

2.2.1? 結構設計

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

2.2.2? 數據及數據類型定義

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

2.2.3? 算法設計及分析

（1）抽象字典類：

（2）Hashchains實現字典類：

（3）壓縮LZW類：

（4）解壓縮UNLZW類：

3? 結? 論

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

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

參考文獻：

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

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

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

[4] 劉汝佳，陳鋒.算法競賽入門經典：訓練指南 [M].北京：清華大學出版社，2012.

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

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