LZW（Limpel - 謝夫 - 韋爾奇）字典編碼定界符問題

Question

這個問題可能不被嚴格限制在LZW算法，並可以覆蓋LZ77的其他實現和LZ78：

我一直想寫一個壓縮/涉及LZW字典編碼方案的解壓縮實用程序。 問題在於，我發現在編碼階段寫出每個代碼字（或「代碼」）後，必須包含一個分隔字符（空格）。 我一直在這樣做，因爲我不能假定輸出是直接傳輸到解碼器，並且可以存儲在一個壓縮文件中以後解碼（在這種情況下，解碼器需要一些方法來檢測什麼分隔碼字 - 分隔符）。

我最近被告知，這是不必要的，並且解碼器應該能夠動態地「找出」每次讀取的壓縮文件的大小，可能是基於先前讀取的代碼， 。這可以消除在每個代碼之後插入額外字節的（昂貴的）需求。

我只是不確定解碼器如何解決這個問題。也許有人瞭解它的工作原理可以向我解釋？謝謝。

編輯：

字典是一個哈希表映射「輸入字符串」到整數（代碼），並且建立了以通常方式隨着更多數據被讀出的輸入的代碼寫入了到壓縮文件。解碼器從壓縮文件中讀取每個代碼（整數），並查找其字典以輸出相關聯的字符串，或者如果沒有該代碼的條目，則它會以通常的方式計算出該字符串應該是什麼並更新它的字典。

「爲什麼文件流式傳輸或存儲會有所幫助？」 如果編碼器的輸出每次向解碼器傳輸一個代碼，則解碼器可以在接收到每個代碼時使用它。但是，如果編碼器將所有代碼寫入文件（壓縮文件），然後將該文件送入解碼器，那麼解碼器如何知道一個代碼的起始位置和另一個代碼的起始位置。該文件只是一個混合的數字序列。

例如： 分隔壓縮文件：127 32 45 22 228 122 209 .... 非分隔壓縮文件：127324522228122209 ...

-Rob

Answer 1

在LZW字典是不與壓縮文件一起存儲。 （或字典是該文件，取決於您的觀點。）寫入文件的每個值根據其位置具有預定義的位寬。例如，它可以以9位字典索引和8位數據之間的對爲起點，直到索引切換到10位索引時耗盡（這發生在精確位置）。

細節取決於你如何實現壓縮。一些做一個恆定的12位索引。但絕不要求額外的分隔符。

此外，由於數據未在8位邊界上對齊，因此如果您尚未正確讀取數據，則無法檢測分隔符！

編輯：

如果你希望爲LZW壓縮算法實際生成小於輸入數據，然後有幾件事情是你應該做的。

首先，您必須將該文件編寫爲二進制而不是文本。將它寫爲文本將擴展，而不是縮小文件的大小。值127可以以二進制形式（01111111）存儲在單個字節中，但需要具有分隔空間的四個字節的UTF-8（「127」= 00110001 00110010 00110111 00100000）。

第二，LZW設計與大於一個字節但小於兩個字節碼值工作，所以你必須做一些位變換輸出數據正確。單個字節僅足以對前256個隱式定義的表項進行編碼。另一位會爲您提供另外256個條目，但9位索引表中的條目很快耗盡。使用12位，您可以獲得4096個表條目，這是一個合理的表格大小。如果您要使用兩個完整字節，那麼您將擁有一個帶有65 K條目的相當大的表。這樣做的麻煩在於，如果你沒有使用你的表空間的全部容量，那麼你正在浪費點數。輸出中有很多位總是零，這對你的壓縮比來說真的很糟糕。

第三，流編碼器/解碼器不能做一次單一值，因爲所述編碼數據重疊字節邊界。如果使用恆定的12位代碼大小，則可以一次處理兩個編碼值的一些倍數。但總的來說，該算法被設計用於處理完整的文件。

Answer 2

使用LZW，碼書是在讀取文件時生成的，無需使用分隔符。由於每個字符都添加到LZW輸出中，因此它會從8位轉換爲更高的值（通常爲10或12位），以便爲碼本留出空間。例如：

banana

在LZW中，b已經在碼本（參考文獻2），所以去到ba。 ba不在碼本中，所以添加它。

輸出當前

ba是具有碼本是

27 = ba

（1-26是索引爲z）

接着它保持a並讀取n - >an。這也不在碼本中，因此它被添加。

輸出當前

ban是具有碼本是

27 = ba 28 = an

重複直到結束。其結果是：

bana29一個碼本是

27 = ba 28 = an 29 = na

無需添加分隔符，因爲這個詞bana29被解碼時，查找29已存在於碼本中。

我希望這有助於解釋爲什麼沒有必要與LZW delimination