LZ七十七佮LZ七十八

LZ 七十七佮LZ 七十八是以色列計算機科學家亞伯搝罕 ・ 藍波佮傑可布 ・ 立夫佇一九七七年以及一九七八年發表之論文中的兩个無去真資料壓縮演的算法。這兩个演算法是大多數 LZ 演算法變體如 LZW、LZSS 佮其他一寡壓縮演算法的基礎。佮上細趁的編碼器抑是行程長度編碼器無仝，這兩个攏是基於字典的編碼器。LZ 七十七是「滑動窗」（Slide window）壓縮演算法，這个演算法後來證明等仝款 LZ 七十八中頭一擺出現的顯式字典編碼技術。

LZ 七十七

LZ 七十七演算法通過使用編碼器或者是解碼器內底已經出現過的相應匹配資料的資訊，替換當前資料對而實現壓縮功能。這个匹配資訊使用號做 _ 長度-距離著 _ 一對資料進行編碼，伊等仝款「逐个予定 _ 長度 _ 個字元攏等於後壁特定 _ 距離 _ 字元位置的未壓縮資料流。」（「 距離」有時嘛叫做「偏徙」。）

編碼器佮解碼器攏必須儲存一定數量的最近的資料，如最近有二 KB、四 KB 抑是三十二 KB 的資料。儲存遮的資料的結構叫做 _ 滑動窗口 _，因為按呢所以 LZ 七十七有時仔嘛叫做滑動窗口壓縮。編碼的物件需要儲存這个資料來揣匹配的資料，解碼器儲存這个資料解說編碼器所指代的匹配資料。所以編碼器會當使用一个比解碼器閣較細的趨動窗仔口，但是顛倒反倒轉來袂使。

真濟有關於著 LZ 七十七演算法的文件攏會長度離對描述做對滑動窗「複製」資料的命令：「 佇緩衝區內底回退 _ 距離 _ 字元然後對彼點開始複製 _ 長度 _ 個字元。」就算講對習慣佇咧指令式的編程來講誠直觀，但是伊猶是會當予人真歹理解 LZ 七十七編碼的一个特點：也就是講，長度距離對中的長度超過距離按呢一款情形毋但是會當接受的而且閣是定定出現的情形。成做一个複製命令，就會予人了解：「 回退 _ 一个 _ 字元然後對彼點開始複製 _ 七个 _ 字元。」但是若是緩衝山內底干焦一字元會當按怎複製七字元咧？毋過共長度距離對看作對特性的描述就會當避免這款透濫：後壁的七字元佮頭前的七个完全仝款。這就意味著每一字元攏會當通過佇咧緩衝區揣著確定落來：就算講佇進前資料對解碼開始的時陣所欲走揣的字元並無佇咧轉衝區內底嘛會當。通過這个定義，按呢的資料著將是 _ 距離 _ 字元序列的濟擺重複，也就是講 LZ 七十七成矣一个靈活容易的行程長度編碼的形式。

就算講所有的 LZ 七十七演算法攏是根據仝款的基本原理的工課，猶毋過按怎輸出編碼了後的資料可能會大無仝款，譬如講長度佮距離的取值的範圍是偌濟佮欲按怎區分長度距離對佮 _ 字面符號 _（即直接用字元本身，毋是用長度距離著表示）。 下跤是一寡實例：

• 佇咧 Lempel 佮 Ziv 頭仔一九七七年論文中描述的演算法每一改將資料輸出三个數值：佇勻衝區內底揣著的上大匹配長度佮位置猶閣有綴咧著這个匹配的字面符號。若輸入流中的兩个相鄰字元干焦會當編碼做字面符號的話，遐長度就是零。
• 佇咧 PalmDoc 格式中，長度距離嘿不三時用兩位元組序列進行偏碼，佇這兩位元組的十六位元內底，十一个表示距離，三位表示長度，後手的兩位用來表示第一个位元組是按呢一个兩个位元組序列的頭殼。
• 一直到二空空四年，上時行的是因為 LZ 七十七的壓縮方法是同時使用矣 LZ 七十七佮哈夫曼編碼的 DEFLATE。字面符號、長度佮用佇指示當前資料塊結束的符號攏囥甲一字母表中。距離會當安全地囥咧一个單獨的字母表內底，因為距離干焦會出現佇一个長度後壁，所以伊無可能佮其他類型的符號透濫。

LZ 七十八

LZ 七十七演算法針對較早的資料進行處理，而且 LZ 七十八演算法煞是針對後來的資料進行處理。LZ 七十八通過對輸入緊取資料進行預先掃描和伊維護的字典中的資料進行匹配來實現這个功能，佇揣著字典內底袂使匹配的資料進前伊掃描進所有的資料，這个時陣伊會輸出資料佇字典內底的位置、匹配的長度嘛閣揣無匹配的資料，並且共結果資料添加到字典內底。

就算講佇上早得著流行，但是尾手仔 LZ 七十八的普及慢慢仔衰微，這可能是因為佇頭拄仔 LZ 七十八出現的一寡年份，一部份 LZ 七十八演算法得著美國專利保護。上時行的 LZ 七十八壓縮的形式是 LZW 演算法，這个演算法是泰瑞 ・ 衛曲所開發的一个 LZ 七十八變體。

參考文獻

• Jacob Ziv and Abraham Lempel ; _ A Universal Algorithm for Sequential Data Compression _，IEEE Transactions on Information Theory , May 一千九百七十七 .

外部連結

• LZ 七十七演算法佮變體的庫、論文佮原始碼列表