Mã nén Lecture_4 DictionaryMethods

5
LZ77 – Giới thiệu
LZ77 được Jacov Ziv và Abraham Lempel đưa ra
vào năm 1977. LZ77 là một thuật toán nén dựa
trên từ điển.
Thuật toán:
Sử dụng một con trỏ dịch chuyển trên xâu kí tự
đầu vào. Ban đầu con trỏ trỏ vào vị trí 1.
Qui ước: từ con trỏ trở về trước được gọi là quá
khứ, còn từ con trỏ trở về sau được gọi là tương
lai. Tránh trường hợp quá khứ dài vô tận người ta
đặt kích thước của cửa sổ quá khứ là w bằng số kí
tự dài nhất có thể trùng khớp với các kí tự trong
tương lai.
6
LZ77 – thuật toán nén
Pos - là vị trí đang xét. Ban đầu Pos bằng 1.
Match – xâu dài nhất được tìm thấy trong
cửa sổ.
Char – kí tự vừa đọc.
Output - thể hiện trong dạng (i, j) C:

(i,j) thể hiện vị trí so khớp và độ dài xâu tương
ứng

C kí tự rõ trong buffer.
7
LZ77: Example 1
sir_sid_eastman_easily_teases_sea_sick_seals
search buffer
look-ahead buffer
sir_sid_eastman_ ⇒ (0,0,’s’)
sir_sid_eastman_e ⇒ (0,0,’i’)
sir_sid_eastman_ea ⇒ (0,0,’r’)
sir_sid_eastman_eas ⇒ (0,0,’_’)
sir_sid_eastman_easi ⇒ (4,2,’d’)
8
LZ77: Decoding
Codes: (0, 0,’s’) (0,0,’i’) (0,0,’r’) (0,0,’_’) (4,2,’d’)
Message:
1. (0, 0,’s’): s
2. (0,0,’i’): s+i=si
3. (0,0,’r’): si+r=sir
4. (0,0,’_’): sir+_=sir_
5. (4,2,’d’): sir_+si+d=sir_sid
Get 2 symbols ’si’ starting from position -4 and add symbol ’d’
9
LZ77: Example 2
10
LZ77: Example 3
11
LZ77: Example 4
12
LZSS – Thuật toán nén
Pos - vị trí đang xét. Ban đầu Pos trỏ đến kí
tự đầu tiên và bằng 1.
Match - xâu dài nhất tìm thấy trong cửa sổ
quá khứ.
Output - hiển thị kết quả ở một trong 2 tình
huống sau:

Cặp (i,j) vị trí so khớp và độ dài xâu so khớp

Kí tự vừa đọc được hoặc xâu so khớp nhưng có độ
dài nhỏ hơn MIN_LENGTH.
13
LZSS: Example 1
14
LZ78: Main idea
•
The algorithm does not use any search buffer, lookahead
buffer, sliding window
•
Instead there is a Dictionary of previously encountered
strings
•
This Dictionary starts (almost) empty
•
The encoder add new entries to the Dictionary during
the message encoding
•
The decoder decode codes using Dictionary and
add new entries to the Dictionary during decoding

Xem chi tiết: Mã nén Lecture_4 DictionaryMethods