summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/algxpar/algxpar-lzw.tex
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}