1. Introduction > 1.

1 Introduction / Overview

Please provide the introduction / overview on this lesson

 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

Overview
In this chapter, you are going to learn about:
• Introduction to LZ77
• How to make encoder and decoder of LZ77
• Examples on encoder and decoder of LZ77
1. Introduction > 1.2 Learning Content

Please make sure the hierarch of the content is well formed.

Please organize the lesson in 3-5 main topics and use 3-level headings.

Level 1 Level 2 Level 3

1. Concept of LZ77 1.1 Introduction to LZ77

1.2 Algorithm of LZ77

1.3 Encoder
1.4 Decoder
2. Examples
1. Introduction > 1.3 Learning Content

ID Will do it by looking at 1.1 Lesson overview

Image Processing
I. General knowledge in image p 1. Introduction to Image Processing
rocessing and multimedia 2. Data Structure and Color of Images
3. Ms. Visual Studio 2008 and OpenCV
4. Introduction to Multimedia Systems
5. Introduction to Video and Lossless Compression
6. Huffman Coding
7. LZ77
8. LZ78
9. LZW

II. Advance knowledge in image 10. Sampling

segmentation and luminance 11. Image Segmentation-I
12. Image Segmentation-II
13. Luminance and Histogram Equalization
1. Introduction > 1.4 Learning Objectives

Please provide objective of the lesson by high light keyword and

follow (Audience, Behavior, Condition, Degree) to write the objective

 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

Objective
Upon completion of this chapter, you will be able to:
• Understand concept of LZ77
• Use method of compression and decompression of LZ77 for applying to text.
1. Introduction > 1.5 Keywords

Please provide keywords of the lesson with explanation

 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

Keywords Description
Metadata is XML-formatted data that defines the characteristics of an update, including its title, description, rul
es for determining whether the update is applicable to a client computer, and instructions for installin
g the update content.
Input stream is the sequence of bytes to be compressed.

Byte is the basic data element in the input stream.

Coding position is the position of the byte in the input stream that is currently being coded (the beginning of the look
ahead buffer).
Lookahead buffer is the byte sequence from the coding position to the end of the input stream.

Window is a buffer of size that indicates the number of bytes from the coding position backward. The window
is empty at the beginning of the compression, then grows to size as the input stream is processed.
Once it reaches size, it then "slides" along with the coding position.
Pointer is information about the starting offset of the match in the window and its length. The starting offset i
s expressed as the count of bytes from the coding position backwards into the window. The length is
the number of bytes to read forward from the starting offset.
Match is the string that is used to find a match of the byte sequence between the lookahead buffer and the
window.
2. Learn> Topic: 1.1 Introduction to LZ77
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Q: What is LZ77?
▪ A: LZ77 is come from the full word “Lempel-Ziv Data Compression Algorithm, 19
77”.
▪ The data compression algorithm developed in 1977 by Abraham Lempel and Jac
ob Ziv.
▪ It became a basis for enabling data transmission via the Internet in an efficient w
ay.
▪ It contributed significantly in making the Internet a global communication medium
(1)
Learning
.
Contents

LempelZiv Sign
6
2. Learn> Topic: 1.1 Introduction to LZ77
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ LZ77 is dynamic dictionary based method.

▪ Dictionary based method is a way to capture the correlation of symbols.

▪ For static dictionary:

➢ Good when the data to be compressed is specific in some application.
➢ For instance, to compress a student database, the word “Name”, “Student I
D” will often appear.
▪ Static dictionary based method does not work well if the source characteristics c
(1)
Learning
hange.
Contents
▪ On the other hand, dynamic dictionary based method can apply to flexible source
characteristics.

7
2. Learn> Topic: 1.2 Algorithm of LZ77
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ The LZ77 compression algorithm is used to analyse input data and determine ho
w to reduce the size of that input data by replacing redundant information with met
adata.

▪ A match is encoded by a pair of numbers called a length-distance pair, which is

equivalent to the statement.
➢ Each of the next length characters is equal to the characters exactly distanc
e characters behind it in the uncompressed stream.
(1)
Learning
Contents ▪ The structure in which this data is held is called a sliding window.

▪ The encoder needs to keep this data to look for matches, and the decoder needs
to keep this data to interpret the matches the encoder refers to.

8
2. Learn> Topic: 1.2 Algorithm of LZ77
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Q: How can we use LZ77 compression algorithm?

▪ A: We can use LZ77 compression algorithm by:
1) Set the coding position to the beginning of the input stream (first block and
second block). Example: ababbbaaa (first block = 5; second block = 2).
2) Find the longest match in the window for the lookahead buffer. Example: a
babbbaaa.
3) If a match is found, output the pointer. Move the coding position (and the w
indow) n bytes forward. Example: n = 2.
(1)
Learning
4) If a match is not found, output a null pointer and the first byte in the lookah
Contents ead buffer. Move the coding position (and the window) 1 byte forward. Exa
mple: n = 1.
5) If the lookahead buffer is not empty, return to step 2. Unless, finish searchi
ng.

9
2. Learn> Topic: 1.2 Algorithm of LZ77
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ The pseudocode is a reproduction of the LZ77 compression algorithm sliding wi

ndow.

begin
fill view from input
while (view is not empty) do

(1) begin
Learning
Contents
find longest prefix p of view starting in coded part
i := position of p in window
j := length of p
X := first char after p in view
output(i, j, X)
add j+1 chars
end
end

10
2. Learn> Topic: 1.3 Encoder
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Q: If we have an input string: “abcaacdaabcdabbbab”. What is encode of this stri

ng?
▪ A: Assume that we take first block = 8 and second block = 6.
➢ abcaacdaabcdabbbab

▪ Step 1:
➢ Compare 6 characters from first block with second block.
(1) abcaacdaabcdabbbab
Learning
Contents o “abcaac” ≠ “abcdab” → move 1 character from first block
o “bcaacd” ≠ “abcdab” → move 1 character from first block
o “caacda” ≠ “abcdab” → no more character from first block.
o So, remove 1 character at the end from second block.
o It rests 5 characters from second block: “abcda”.

11
2. Learn> Topic: 1.3 Encoder
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 1 (cont.):
➢ Compare 5 characters from first block with second block.
abcaacdaabcdabbbab

o “abcaa” ≠ “abcda” → move 1 character from first block

o “bcaac” ≠ “abcda” → move 1 character from first block
o “caacd” ≠ “abcda” → move 1 character from first block
o “aacda” ≠ “abcda” → no more character from first block
(1)
Learning
o So, remove 1 character at the end from second block.
Contents o It rests 4 characters from second block: “abcd”.

12
2. Learn> Topic: 1.3 Encoder
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 1 (cont.):
➢ Compare 4 characters from first block with second block.
abcaacdaabcdabbbab

o “abca” ≠ “abcd” → move 1 character from first block

o “bcaa” ≠ “abcd” → move 1 character from first block
o “caac” ≠ “abcd” → move 1 character from first block
o “aacd” ≠ “abcd” → move 1 character from first block
(1)
Learning
o “acda” ≠ “abcd” → no more character from first block
Contents o So, remove 1 character at the end from second block.
o It rests 3 characters from second block: “abc”.

13
2. Learn> Topic: 1.3 Encoder
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 1 (cont.):
➢ Compare 3 characters from first block with second block.
abcaacdaabcdabbbab
o “abc” = “abc” → match or equal each other
o Start to give index in the first block (8 character) from 1 by reversing fr
om the end to the beginning.
(1) abcaacdaabcdabbbab
Learning 87654321
Contents
o Use formula: Codeword<position, length, C(x)> (x is next character
from the last matching character in second block)
o If no match all character from first block and second block, use formul
a: Codeword<0, 0, C(0)> (0 is first character in second block).
o According to formula, we get: Codeword<8, 3, C(d)> (n=length=3)

14
2. Learn> Topic: 1.3 Encoder
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 2: move n+1 (3+1=4) window at first block

➢ Keep taking 8 characters from first block and 6 characters from second blo
ck.
abcaacdaabcdabbbab

➢ Compare 6 characters from first block with second block.

acdaabcdabbbab
(1)
Learning
o “acdaab” ≠ “abbbab” → move 1 character from first block
Contents o “cdaabc” ≠ “abbbab” → move 1 character from first block
o “daabcd” ≠ “abbbab” → no more character from first block.
o So, remove 1 character at the end from second block.
o It rests 5 characters from second block: “abbba”.

15
2. Learn> Topic: 1.3 Encoder
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 2 (cont.):
➢ Compare 5 characters from first block with second block.
acdaabcdabbbab

o “acdaa” ≠ “abbba” → move 1 character from first block

o “cdaab” ≠ “abbba” → move 1 character from first block
o “daabc” ≠ “abbba” → move 1 character from first block
o “aabcd” ≠ “abbba” → no more character from first block
(1)
Learning
o So, remove 1 character at the end from second block.
Contents o It rests 4 characters from second block: “abbb”.

16
2. Learn> Topic: 1.3 Encoder
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 2 (cont.):
➢ Compare 4 characters from first block with second block.
acdaabcdabbbab

o “acda” ≠ “abbb” → move 1 character from first block

o “cdaa” ≠ “abbb” → move 1 character from first block
o “daab” ≠ “abbb” → move 1 character from first block
o “aabc” ≠ “abbb” → move 1 character from first block
(1)
Learning
o “abcd” ≠ “abbb” → no more character from first block
Contents o So, remove 1 character at the end from second block.
o It rests 3 characters from second block: “abb”.

17
2. Learn> Topic: 1.3 Encoder
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 2 (cont.):
➢ Compare 3 characters from first block with second block.
acdaabcdabbbab

o “acd” ≠ “abb” → move 1 character from first block

o “cda” ≠ “abb” → move 1 character from first block
o “daa” ≠ “abb” → move 1 character from first block
o “aab” ≠ “abb” → move 1 character from first block
(1)
Learning
o “abc” ≠ “abb” → move 1 character from first block
Contents o “bcd” ≠ “abb” → no more character from first block
o So, remove 1 character at the end from second block.
o It rests 2 characters from second block: “ab”.

18
2. Learn> Topic: 1.3 Encoder
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 2 (cont.):
➢ Compare 2 characters from first block with second block.
acdaabcdabbbab

o “ac” ≠ “ab” → move 1 character from first block

o “cd” ≠ “ab” → move 1 character from first block
o “da” ≠ “ab” → move 1 character from first block
o “aa” ≠ “ab” → move 1 character from first block
(1)
Learning
o “ab” = “ab” → match
Contents
acdaabcdabbbab
87654321

o We get: Codeword<4, 2, C(b)> (n=2)

19
2. Learn> Topic: 1.3 Encoder
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 3: move n+1 (2+1=3) window at first block

➢ Keep taking 8 characters from first block, but second block rests only 3 cha
racters, so we take only 3 from second block.
acdaabcdabbbab

➢ Compare 3 characters from first block with second block.

aabcdabbbab
(1)
Learning
o “aab” ≠ “bab” → move 1 character from first block
Contents o “abc” ≠ “bab” → move 1 character from first block
o “bcd” ≠ “bab” → move 1 character from first block
o “cda” ≠ “bab” → move 1 character from first block
o “dab” ≠ “bab” → move 1 character from first block
o “abb” ≠ “bab” → no more character from first block.
o So, remove 1 character at the end from second block.
o It rests 2 characters from second block: “ba”.

20
2. Learn> Topic: 1.3 Encoder
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 3 (cont.):
➢ Compare 2 characters from first block with second block.
aabcdabbbab

o “aa” ≠ “ba” → move 1 character from first block

o “ab” ≠ “ba” → move 1 character from first block
o “bc” ≠ “ba” → move 1 character from first block
o “cd” ≠ “ba” → move 1 character from first block
(1)
Learning
o “da” ≠ “ba” → move 1 character from first block
Contents o “ab” ≠ “ba” → move 1 character from first block
o “bb” ≠ “ba” → no more character from first block.
o So, remove 1 character at the end from second block.
o It rests 1 characters from second block: “b”.

21
2. Learn> Topic: 1.3 Encoder
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 3 (cont.):
➢ Compare 1 characters from first block with second block.
aabcdabbbab

o “a” ≠ “b” → move 1 character from first block

o “a” ≠ “b” → move 1 character from first block
o “b” = “b” → match
(1) aabcdabbbab
Learning
Contents 87654321
o We get: Codeword<6, 1, C(a)> (n=1)

22
2. Learn> Topic: 1.3 Encoder
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 4: move n+1 (1+1=2) window at first block

➢ Keep taking 8 characters from first block, but second block rests only 1 cha
racters, so we take only 1 from second block.
aabcdabbbab

➢ Compare 1 characters from first block with second block.

bcdabbbab
(1)
Learning
o “b” = “b” → match
Contents
bcdabbbab
87654321
o We get: Codeword<8, 1, null> (n=1)

23
2. Learn> Topic: 1.3 Encoder
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Because there is no more characters in second block, we stop here.

➢ Encode: {<8, 3, C(d)>, <4, 2, C(b)>, <6, 1, C(a)>, <8, 1, null>}
▪ But when we store in compress file, we keep the first block string too.
➢ result = {“abcaacda”, {<8, 3, C(d)>, <4, 2, C(b)>, <6, 1, C(a)>, <8, 1, null>}

▪ Q: Why do we have to keep the first block string?

▪ A: We have to keep the first block string because:
➢ we want to make decoder in order to get the original string.
(1)
Learning
Contents

24
2. Learn> Topic: 1.4 Decoder
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Input string is the result of encoder.

➢ result = {“abcaacda”, <8, 3, C(d)>, <4, 2, C(b)>, <6, 1, C(a)>, <8, 1, null>}

▪ Q: How to make decoder?

▪ A: Step 1: we have to write the first block string.
➢ So, we get: “abcaacda”
➢ Then use the first result of encoder: <8, 3, C(d)>
➢ Give index from 1 as in the encoder.
(1)
Learning
Contents abcaacda
87654321

abcaacdaabc
87654321

abcaacdaabcd
87654321

25
2. Learn> Topic: 1.4 Decoder
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 2: move n+1 (3+1=4) window

abcaacdaabcd (result from step 1)

abcaacdaabcd

➢ Use the second result of encoder: <4, 2, C(b)>

abcaacdaabcd
(1) 87654321
Learning
Contents abcaacdaabcdab
87654321

abcaacdaabcdabb
87654321

26
2. Learn> Topic: 1.4 Decoder
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 3: move n+1 (2+1=3) window

abcaacdaabcdabb (result from step 2)

abcaacdaabcdabb

➢ Use the third result of encoder: <6, 1, C(a)>

abcaacdaabcdabb
(1) 87654321
Learning
Contents abcaacdaabcdabbb
87654321

abcaacdaabcdabbba
87654321

27
2. Learn> Topic: 1.4 Decoder
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 4: move n+1 (1+1=2) window

a b c a a c d a a b c d a b b b a (result from step 3)

abcaacdaabcdabbba

➢ Use the last result of encoder: <8, 1, null>

abcaacdaabcdabbba
(1) 87654321
Learning
Contents abcaacdaabcdabbbab
87654321

a b c a a c d a a b c d a b b b a b EOF
87654321
➢ Decoder: “abcaacdaabcdabbbab”

28
2. Learn> Topic: 1.4 Decoder
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Conclusion:
➢ The result of decoder must exactly the same as input string.
➢ Number of steps in decoder part must equal to number of steps in encoder
part.
➢ Unless, you have to check your encoder part and decoder part again.
➢ If you do wrong in any steps in encoder or decoder, you will get wrong resu
lt.
➢ Be careful at moving window and matching characters!
(1)
Learning
Contents

29
2. Learn> Topic: 2. Examples
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Example1: Input string: “bcabadbcac”. Find encoder and decoder of LZ77? Assu
me that we take first block = 5 and second block = 3.
➢ bcabadbcac

▪ Step 1: Compare 3 characters from first block with second block.

bcabadbcac

➢ “bca” ≠ “dbc” → move 1 character from first block

(1)
Learning
➢ “cab” ≠ “dbc” → move 1 character from first block
Contents ➢ “aba” ≠ “dbc” → no more character from first block
➢ Compare 2 characters → no match: “ba” ≠ “db”
➢ Compare 1 characters → no match: “a” ≠ “d”
➢ Codeword<0, 0, C(d)> (n=0)

30
2. Learn> Topic: 2. Examples
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 2: move n+1 (0+1=1) window at first block

➢ Keep taking 5 characters from first block and 3 characters from second blo
ck.
bcabadbcac

➢ Compare 3 characters from first block with second block.

cabadbcac
(1)
Learning
➢ “cab” ≠ “bca” → move 1 character from first block
Contents ➢ “aba” ≠ “bca” → move 1 character from first block
➢ “bad” ≠ “bca” → no more character from first block
➢ Compare 2 characters → no match: “ad” ≠ “bc”
➢ Compare 1 characters → match: “b” = “b”

cabadbcac
54321
➢ Codeword<3, 1, C(c)> (n=1)

31
2. Learn> Topic: 2. Examples
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 3: move n+1 (1+1=2) window at first block

➢ Keep taking 5 characters from first block, but second block rests only 2 cha
racters, so we take only 2 from second block.
cabadbcac

➢ Compare 2 characters from first block with second block.

badbcac
(1)
Learning
➢ “ba” ≠ “ac” → move 1 character from first block
Contents ➢ “ad” ≠ “ac” → move 1 character from first block
➢ “db” ≠ “ac” → move 1 character from first block
➢ “bc” ≠ “ac” → no more character from first block
➢ Compare 1 characters → match: “a” = “a”

badbcac
54321
➢ Codeword<4, 1, C(c)> (n=1)

32
2. Learn> Topic: 2. Examples
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 4: move n+1 (1+1=2) window at first block

➢ Keep taking 5 characters from first block, but there is no character in secon
d block.
b a d b c a c EOF

➢ So, we stop here. Actually, there are only 3 steps

➢ Encoder = {“bcaba”, <0, 0, C(d)>, <3, 1, C(c)>, <4, 1, C(c)>}
(1)
Learning
bcabadbcac <0,0,d><3,1,c><4,1,c>
Contents
Input string Encoder

33
2. Learn> Topic: 2. Examples
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Decoder:
➢ Input string: {“bcaba”, <0, 0, C(d)>, <3, 1, C(c)>, <4, 1, C(c)>}

▪ Step 1: we have to write the first block string.

➢ So, we get: “bcaba”
➢ Then use the first result of encoder: <0, 0, C(d)>
➢ Give index from 1 as in the encoder.
(1) bcaba
Learning 54321
Contents
bcabad
54321

34
2. Learn> Topic: 2. Examples
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 2: move n+1 (0+1=1) window

bcabad (result from step 1)

bcabad

➢ Use the second result of encoder: <3, 1, C(c)>

bcabad
(1) 54321
Learning
Contents bcabadb
54321
bcabadbc
54321

35
2. Learn> Topic: 2. Examples
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 3: move n+1 (1+1=2) window

b c a b a d b c (result from step 2)

bcabadbc

➢ Use the last result of encoder: <4, 1, C(c)>

bcabadbc
(1) 54321
Learning
Contents bcabadbca
54321

bcabadbcac
54321
➢ Decoder: “bcabadbcac”

36
2. Learn> Topic: 2. Examples
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Example2: Input string: “aabacdabaccbadb”. Find encoder and decoder of LZ77?

Assume that we take first block = 6 and second block = 4.
➢ aabacdabaccbadb

▪ Step 1: Compare 4 characters from first block with second block.

aabacdabaccbadb

➢ “aaba” ≠ “abac” → move 1 character from first block

(1)
Learning
➢ “abac” ≠ “abac” → move 1 character from first block
Contents ➢ “bacd” ≠ “abac” → no more character from first block
➢ Compare 3 characters → match: “aba” = “aba”

aabacdabaccbadb
654321
➢ Codeword<5, 3, C(c)> (n=3)

37
2. Learn> Topic: 2. Examples
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 2: move n+1 (3+1=4) window at first block

➢ Keep taking 6 characters from first block and 4 characters from second blo
ck.
aabacdabaccbadb

➢ Compare 4 characters from first block with second block.

cdabaccbadb
(1)
Learning
➢ “cdab” ≠ “cbad” → move 1 character from first block
Contents ➢ “daba” ≠ “cbad” → move 1 character from first block
➢ “abac” ≠ “cbad” → no more character from first block
➢ Compare 3 characters → no match: “bac” ≠ “cba”
➢ Compare 2 characters → no match: “ac” ≠ “cb”
➢ Compare 1 characters → match: “c” = “c”

cdabaccbadb
654321
➢ Codeword<6, 1, C(b)> (n=1)

38
2. Learn> Topic: 2. Examples
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 3: move n+1 (1+1=2) window at first block

➢ Keep taking 6 characters from first, but second block rests only 3 character
s, so we take only 3 from second block.
cdabaccbadb

➢ Compare 3 characters from first block with second block.

abaccbadb
(1)
Learning
➢ “aba” ≠ “adb” → move 1 character from first block
Contents ➢ “bac” ≠ “adb” → move 1 character from first block
➢ “acc” ≠ “adb” → move 1 character from first block
➢ “ccb” ≠ “adb” → no more character from first block
➢ Compare 2 characters → no match: “cb” ≠ “ad”
➢ Compare 1 characters → match: “a” = “a”

abaccbadb
654321
➢ Codeword<6, 1, C(d)> (n=1)

39
2. Learn> Topic: 2. Examples
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 4: move n+1 (1+1=2) window at first block

➢ Keep taking 6 characters from first, but second block rests only 1 character
s, so we take only 1 from second block.
abaccbadb

➢ Compare 1 characters from first block with second block.

accbadb
(1)
Learning
➢ “a” ≠ “b” → move 1 character from first block
Contents ➢ “c” ≠ “b” → move 1 character from first block
➢ “c” ≠ “b” → move 1 character from first block
➢ “b” = “b” → match

accbadb
654321
➢ Codeword<3, 1, null> (n=1)
➢ So, we stop here.

40
2. Learn> Topic: 2. Examples
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Encoder = {“aabacd”, <5, 3, C(c)>, <6, 1, C(b)>, <6, 1, C(d)>, <3, 1, null>}

Input string

aabacdabaccbadb

(1)
Learning
Contents

<5, 3, C(c)>, <6, 1, C(b)>, <6, 1, C(d)>, <3, 1, null>

Encoder

41
2. Learn> Topic: 2. Examples
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Decoder:
➢ Input string: {“aabacd”, <5, 3, C(c)>, <6, 1, C(b)>, <6, 1, C(d)>, <3, 1, null>
}

▪ Step 1: we have to write the first block string.

➢ So, we get: “aabacd”
➢ Then use the first result of encoder: <5, 3, C(c)>
➢ Give index from 1 as in the encoder.
(1)
Learning aabacd
Contents
654321

aabacdaba
654321

aabacdabac
654321

42
2. Learn> Topic: 2. Examples
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 2: move n+1 (3+1=4) window

aabacdabac (result from step 1)

aabacdabac

➢ Use the second result of encoder: <6, 1, C(b)>

aabacdabac
(1) 654321
Learning
Contents aabacdabacc
654321

aabacdabaccb
654321

43
2. Learn> Topic: 2. Examples
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 3: move n+1 (1+1=2) window

aabacdabaccb (result from step 2)

aabacdabaccb

➢ Use the second result of encoder: <6, 1, C(d)>

aabacdabaccb
(1) 654321
Learning
Contents aabacdabaccba
654321

aabacdabaccbad
654321

44
2. Learn> Topic: 2. Examples
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

▪ Step 4: move n+1 (1+1=2) window

a a b a c d a b a c c b a d (result from step 3)

aabacdabaccbad

➢ Use the last result of encoder: <3, 1, null>

aabacdabaccbad
(1) 654321
Learning
Contents aabacdabaccbadb
654321

a a b a c d a b a c c b a d b EOF
654321

➢ Decoder: “aabacdabaccbadb”

45
4. Outro > 4.1 Summarize

Please give a lesson summary.

Each topic can be summarized into a sentence, diagram, or even a word.

 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

Summarize

▪ LZ77 is come from the full word “Lempel-Ziv Data Compression Algorithm, 1
977”. It became a basis for enabling data transmission via the Internet in an ef
ficient way. It contributed significantly in making the Internet a global commun
ication medium.

▪ We can use LZ77 compression algorithm by:

1) Set the coding position to the beginning of the input stream (first block
and second block).
2) Find the longest match in the window for the lookahead buffer.
3) If a match is found, output the pointer. Move the coding position (and t
he window) n bytes forward.
4) If a match is not found, output a null pointer and the first byte in the lo
okahead buffer. Move the coding position (and the window) 1 byte forw
ard.
5) If the lookahead buffer is not empty, return to step 2. Unless, finish sea
rching.
4. Outro > 4.2 References

Provide references if you think the students need.

Reference

▪ https://en.wikipedia.org/wiki/LZ77_and_LZ78

▪ https://msdn.microsoft.com/en-us/library/ee916854.aspx

▪ http://www.stringology.org/DataCompression/lz77/index_en.html

▪ https://sites.google.com/site/datacompressionguide/lz77
4. Outro > 4.3 Assignment

Please provide the assignment such as exercise , discussion, research topic,

Short essay, case studies, ….

 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

Assignment

1) Find encoder and decoder of LZ77? If we have:

➢ Input string: “abdcaedbdcecabbdeacb” (first block = 7 and second block = 5)

2) Find encoder and decoder of LZ77? If we have:

➢ Input string: “daddacabeacaebccdaabbeacb” (first block = 8 and second block = 6)
4. Outro > 4.4 Next Lesson

This is the end of the lesson.

Ending message and introduction to next lesson including lesson title and topics
should be given.
 A : Text-based + Audio
□ B : Text-based + Video
□ C : Only Video

Overview
• Introduce to LZ78
• Concept of LZ78

LZ78
1. Concept of LZ78
Next Lesson 2. Examples
Title