blob: 37fd820c5f0ccf1f9171c3342afb6e11f9d94cd7 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
\begin{algorithmic}[1]
\Description LZW Compression using a table with all known sequences of bytes.
\Input A flow of bytes
\Output A flow of bits with the compressed representation of the input bytes
\Statex
\Statep{Initialize a table with all bytes}[each position of the table has a single byte]
\Statep{Initilize \Id{sequence} with the first byte in the input flow}
\While{there are bytes in the input}[wait until all bytes are processed]
\Statep{Get a single byte from input and store it in \Id{byte}}
\If{the concatention of \Id{sequence} and \Id{byte} is in the table}
\Statep{Set \Id{sequence} to $\Id{sequence} + \Id{byte}$}[concatenate without producing any output]
\Else
\Statep{Output the code for \Id{sequence}}[i.e., the binary representation of its position in the table]\label{alg:lzw:output}
\Statep{Add the concatention of \Id{sequence} and \Id{byte} to the table}[the table learns a longer sequence]\label{alg:lzw:add-to-table}
\Statep{Set \Id{sequence} to \Id{byte}}[starts a new sequence with the remaining byte]
\EndIf
\EndWhile
\Statep{Output the code for \Id{sequence}}[the remaining sequence of bits]
\end{algorithmic}
|