Digital Signal Processing Reference
In-Depth Information
Sliding windows
history buffer
search buffer
N
M
Figure 13.17
Sliding window for data compression algorithm
The algorithmworks by identifying the longest repeated string in a buffer of data in awindow. The
string is coded with its earlier location in thewindow. The algorithmworks on a sliding window. The
window has two parts, a history buffer and a search buffer, with sizes N and M characters,
respectively (Figure 13.17).
The encoder finds the longest match of a string of character in a search buffer into the entire sliding
windowand codes the string by appending the last unmatched character with the backward pointer to
the matched string and its length. The decoder then can easily decode by looking at the pointer and
the last unmatched character. Figure 13.18 and the following code explain the working of the
algorithm.
while (search buffer not empty)
{
find_longest_match()
!
(position, length);
code_match()
!
(position, length, next unmatched character);
shift left the window by length +1 characters;
}
6
4
a
a
c
a
a
c
a
b
c
a
b
a
a
a
c
( 0, 0, a)
(1, 1, c)
a
a
c
a
a
c
a
b
c
a
b
a
a
a
a
a
a
c
a
a
c
a
b
c
a
b
a
a
a
c
( 3, 4, b)
Next character
a
a
c
a
a
c
a
b
c
a
b
a
a
a
c
( 3, 3, a)
Dictionary (size=6)
Longest match
a
a
c
a
a
c
a
b
c
a
b
a
a
a
c
( 1, 2, c)
6
Figure 13.18
Looking for the longest match
Search WWH ::
Custom Search