Giải thuật nén LZW
Giải Thuật Nén LZW
Bộ môn : Cấu trúc dữ liệu 2
Giảng viên : Lê Văn Vinh
Nội dung
1. Ý Tưởng
2. Thuật toán nén (Encoding)
3. Thuật toán giải nén (Decoding)
4. Biến thiên độ rộng của mã(Variable-Width codes)
5. Ví dụ
6. Ứng dụng
1.Ý tưởng
Thuật toán LZW được phát triển theo nguyên lý tạo ra 1 dãy mã:
-Mã từ 0 đến 255 miêu tả 1 dãy ký tự thay thế cho ký tự 8-bit
tương ứng.
-Mã từ 256 đến 4095 được tạo bên trong 1 từ điển cho trường
hợp lặp chuỗi trong dữ liệu.
-Mỗi bước trong khi nén,byte nhập vào được tập hợp lại thành
1 chuỗi cho đến khi ký tự tiếp theo sẽ tạo thành 1 chuỗi chưa
tồn tại trong từ điển,và 1 mã mới cho chuỗi được tạo sẽ được
thêm vào từ điển,và mã ấy sẽ được xuất ra file output.
2.Nén(Compression)
•Thuật toán mã hóa :
1. Khởi tạo từ điển chứa tất cã chuỗi có 1 ký tự
2. Tìm chuỗi W dài nhất trong từ điển đối chiếu với
dữ liệu nhập hiện tại
3. Xuất vị trí từ điển cho W ra file output và xóa W
khỏi dữ liệu nhập.
4. Thêm W và ký tự tiếp theo trong dữ liệu nhập
vào từ điển
5. Đến bước 2.
3.Giải nén
•Đọc giá trị từ dữ liệu nhập đã mã hóa và xuất ra
chuỗi tương ứng từ từ điển đã được khởi tạo.
•Tại cùng 1 thời điểm nó thu được giá trị tiếp theo từ
dữ liệu nhập,thêm vào từ điển xích chuỗi của chuỗi
xuất.Và ký tự đầu tiên của chuỗi nhận được khi mã
hóa ký tự tiếp theo.
•Sau đó trình giải nén xử lý giá trị nhập tiếp theo,quá
trình lặp cho đến khi dữ liệu nhập không còn,tại thời
điểm giá trị nhập cuối cùng được mã hóa không còn
bất kỳ giá trị nào thêm vào từ điển.
4.Biến thiên độ rộng.
(Variable-width codes)
•Là khoảng rộng của dãy bit chứa các mã đã
được mã hóa trong vùng nhớ máy tính
•Trình nén mã sẽ tăng độ rộng từ p lên p+1 khi
1 chuỗi w+s không tồn tại trong từ điển(vì vậy
1 mã phải được thêm vào) nhưng giá trị tiếp
theo có thể thêm trong bảng lại là 2^p.
có thể bạn quan tâm
Nghiên cứu, đánh giá các giải thuật đối sánh chuỗi. Trên cơ sở đó lựa...
25
1.075
555
Thạc sĩ cao học
25
(New)
Kỹ thuật giải thuật trong lập trình và ứng dụng
0
760
318
Lập trình
(New)
Tìm hiểu về thuật toán và thuật giải
97
2.153
443
Cơ sở dữ liệu
97
(New)
Kỹ thuật phân tích giải thuật
7
946
325
Lập trình
7
(New)
Luận văn thạc sỹ kỹ thuật điện: Tổng quan về kỹ thuật WiMAX và giải ph...
93
774
365
Thạc sĩ cao học
93
(New)
Slide môn thuật giải
142
520
390
Cơ sở dữ liệu
142
(New)
Giải thuật trong xử lý các bài toán
8
968
260
Lập trình
8
(New)
Cấu trúc dữ liệu và giải các thuật toán
229
756
275
Cơ sở dữ liệu
229
(New)
thông tin tài liệu
Tài liệu cung cấp cái nhìn tổng quan về thuật nén LZD và ứng dụng
Mở rộng để xem thêm
từ khóa liên quan
tài liệu mới trong mục này
tài liệu hot trong mục này
tài liệu giúp tôi
Nếu bạn không tìm thấy tài liệu mình cần có thể gửi yêu cầu ở đây để chúng tôi tìm giúp bạn!
×
