ngoi1minhnhodenem
New Member
Download miễn phí Luận văn Nén và xử lý dữ liệu
Mã có từ điển cố định được gọi là mã tĩnh hay nói cách khác là từ điển tĩnh.
Một số những nhược điểm của từ điển tĩnh:
+ Kích thước của từ điển tĩnh không thể mở rộng ra, để cập nhật các thông tin mới so với các loại dữ liệu khác.
+ Quá trình nghiên cứu thiết kế từ điển đòi hỏi nhiều công sức.
+ Các thuật toán sử dụng từ điển tĩnh chạy tương đối chậm.
+ Tốn không gian lưu trữ dữ liệu.
Tuy nhiên bên cạnh những nhược điểm này thì từ điển tĩnh cũng có ưu điểm là: Thiết kế các thuật toán áp dụng cho việc tìm kiếm trên từ điển tĩnh đơn giản tốn ít thời gian.
Do những đặc tính hạn chế của từ điển tĩnh, kết hợp với những đặc điểm nổi bật của thuật toán nén là "sự cứng nhắc" đã làm cho người dùng chương trình để tiết kiệm bộ nhớ nhàm chán không thích sử dụng các chương trình nén nữa. Vậy phải có cách để khắc phục những hạn chế đó và làm cho chương trình nén dữ liệu trở nên mềm dẻo hơn. Chính vì vậy những thuật toán nén chỉ đạt hiệu quả cao nếu chúng ta xử lý tốt "từ điển" được sử dụng trong các thuật toán nói chung.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
g pháp dùng để nén dữ liệu thì phương pháp đơn giản nhất là phương pháp mã hoá theo độ dài.+ Nguyên tắc mã:
Nguyên tắc cơ bản của phương pháp này là phát hiện một ký tự có số lần xuất hiện liên tiếp vượt qua một ngưỡng cố định nào đó. Trong trường hợp này dãy sẽ được thay thế bằng 3 ký tự.
Ký tự thứ nhất là ký tự đặc biệt, thông báo dãy tiếp là dãy đặc biệt.
Ký thự thứ hai chỉ số lần lặp.
Ký tự thứ ba chỉ ký tự lặp
Như vậy, tư tưởng của phương pháp này là thay thế một dãy bằng một dãy khác ngắn hơn tuân theo một ngưỡng nào đó, và thông thường ngưỡng có giá trị là 4.
+Ví dụ:
Dãy nguồn: ..SSOOOOONNNLLLLLLAAANNN..
Dãy nhận được sau khi nén:
.... HH CS S O NNN CS 6L AAAN...
Tuy nhiên phương pháp này cũng có nhiều khuyết điểm. Trước hết là ký tự đặc biệt không được phép xuất hiện trong tệp dữ liệu nguồn. Nếu ký tự đó xuất hiện với tư cách là dữ liệu thì khi gỡ nén nó sẽ dẫn đến tình trạng nhập nhằng.
Ngoài ra người ta còn chú ý đến chỉ số lặp. Nếu chỉ số lặp được lưu trữ trên 1 byte thì số lần lặp của một ký tự không vượt qua 255.
Khi số lần lặp của một ký tự vượt quá 255 thì chỉ số lặp sẽ được lưu trữ trên 2 byte. Trong trường hợp này, chỉ số lặp tối đa sẽ được nâng lên thành 65535. Tuy nhiên trong thực tế sẽ số lần lặp của một ký tự thường £ 255 -> quá trình nén sẽ chiếm 1 byte vô ích.
Dựa vào những đặc điểm trên ta thấy phương pháp mã hoá theo độ dài không được lợi nhiều trong việc nén tệp văn bản.
Nhưng đối với những tệp hình ảnh thì phương pháp này lại có hiệu quả cao vì ảnh đen trắng là dãy các số 0 (điểm đen) và các số 1 (điểm trắng) đan xen nhau. Trong trường hợp này việc đếm số lần xuất hiện liên tiếp của các số 0 và số 1 tương đối dễ dàng và khi mã hoá không cần ký tự đặc biệt cũng như không cần chỉ rõ ký tự lặp là ký tự nào mà chỉ cần ghi số lần xen kẽ.
+ Ví dụ:
Nguồn: 0000000000 11111111 00000 111111
=> sẽ có mã: 10 8 5 6
N... với hình ảnh mà điểm đầu tiên không phải là điểm đen như ví dụ trên thì phải bắt đầu dãy mã bằng 1 số 0.
+ Ví dụ: Nguồn: ... 00 .. 0 11111100 ...
280 lần
Nén:
... 2550 25 52 ...
Đối với ảnh màu thì mỗi màu sắc được hiểu thị bằng một số nguyên. Để phân biệt được sự khác nhau trong lặp mầu người ta phải xen vào một ký tự đặc biệt và tiếp theo sau sẽ là chỉ số lặp và ký tự được lặp. Có nghĩa là để mã hoá ảnh màu có thể dùng một cặp, ký tự đầu là lần lặp lại, ký tự sau là một màu và dùng một ký tự đặc biệt (ví dụ như #) để báo hiệu sẽ xuất hiện các cập nhật.
+Ví dụ:
Nguồn: 11111122223344444444
Nén: #61 # 42 # 23 # 84
Đối với những màu là duy nhất (ký tự có chỉ số lặp là 1) thì màu đó không cần đi với ký tự đặc biệt.
+ Thuật toán mã theo độ dài:
* Nén: Tệp nguồn: f
Ký tự đặc biệt: db
Số lần lặp: dem
db = 255
dem = 1
Đọc ký tự đầu tiên trong f là ktlap
While not eof (f) do
begin
- Đọc ký tự tiếp theo -kt;
if kt := kt lặp then dem = dem + 1
else if dem > 3 then
begin
In db;
In dem;
In ktlap;
End;end;
for |:= 1 to dem do
In ktlap
End;
Dem: = 1
ktlap := kt
End;
* Giải nén:
Tệp nén: f
Ký tự đặc biệt: db
Số lần lặp: dem
db = 255
While not eof (f) do
begin
Đọc ký tự trong f là kt;
If kt:=db then
begin
Đọc ký tự tiếp - dem;
Đọc ký tự tiếp - ktlap;
for | = 1 to dem do
In ktlap
else
Đọc ký tự tiếp;
end;
End ;
Trong phương pháp này, người ta sử dụng ký tự đặc biệt với tư cách là ký tự không bao giờ xuất hiện trong tệp dữ liệu nguồn. Đây là tư tưởng không chuẩn mực bởi vì tệp dữ liệu nguồn có thể chứa tất cả các ký tự của bảng mã ASCII. Do đó phương pháp này được sử dụng nhiều nhất trong việc nén hình ảnh.
E. Mã hoá thích nghi dần của tần số (AFE)
Phương pháp này là phương pháp mã hoá thích nghi dần của từng ký tự theo tần số xuất hiện.
Khởi đầu của việc nén, nếu một ký tự được mã hoá trên 5 bits thì nó cũng có thể được mã hoá bằng 1 hay 9 bits tuỳ từng trường hợp vào sự xuất hiện của nó là nhiều hay ít.
Trong phương pháp này, việc nén và gỡ nén phải tiến hành song song. Mỗi modul sẽ có chung bảng mã ban đầu cho 1 byte truyền đi. Nhưng chúng sẽ phụ thuộc vào tần số xuất hiện của ký tự và tuân theo qui tắc cải biến.
Với mục đích như vậy, phải lập mã cho mỗi byte và lưu trữ chúng trong một bảng tham khảo hay là trong một từ điển. Bảng này dùng làm cơ sở cho sự lập mà của mỗi ký tự, có mặt tổng hai modul nén và gỡ nén.
Mã của mỗi byte bao gồm 2 phần: Phần đầu (Header) và phần thân (Body). Phần đầu thường gồm 3 bits và phần thân có 1 - 8 bits, tuỳ từng trường hợp vào byte để lập mã và nhất là tần số xuất hiện của mã. Phần đầu chỉ ra độ dài của thân mã. Khi giải mã không cần xử lý từng bit để phân biệt các byte đã truyền như trong phương pháp Huffman. Để giải mã chỉ cần đọc 3 bits đầu để xác định độ dài n của thân mã, sau đó đọc n bits tiếp theo để khôi phục lại mã đã truyền đi.
3.3- MÔ HÌNH NÉN
Chúng ta có thể có thuật toán nén tốt khi biết được mô hình sinh ra nguồn tin. Song việc tìm ra mô hình sinh ra dữ liệu đó là không thể. Vậy có cách nào nén được mà không biết mô hình sinh nguồn tin. Chúng ta có 2 phương pháp sau:
- Mô hình tĩnh: Đó là mô hình tìm được thông qua nghiên cứu các đặc trưng thống kê của văn bản rồi sau đó sử dụng chúng.
- Mô hình thích ứng: Mô hình thích ứng có xuất phát điểm là một mô hình tổng quát nào đó sau đó hiệu chỉnh dần.
Đặc điểm của mô hình thích ứng:
+ Mô hình thích ứng dựa vào thống kê của một số rất lớn các văn bản cùng loại và áp dụng cho văn bản mới. Ưu điểm của phương pháp này là trình nén dãn chạy nhanh.
+ Dựa vào mô hình nén giả định để chúng ta tính giá trị các trọng tải và tiến hành nén.
3.3.1. Nén dữ liệu có mô hình nguồn
Một trong những đặc điểm của việc nén dữ liệu này là cả người nén cùng biết nguồn sinh ra tin. Những thuật toán nén dữ liệu đặc trưng cho việc nén dữ liệu có mô hình nguồn này là:
+ Thuật toán Fano - Shannon
+ Thuật toán Huffman.
3.3.2. Nén dữ liệu chưa có mô hình nguồn
Một trong những ví dụ điển hình về nén chưa có mô hình nguồn là ngôn ngữ tự nhiên. Chúng ta luôn rơi vào tình trạng có văn bản mà không có mô hình nguồn. Để tìm ra một thuật toán nén tốt nhất thì chúng ta phải tìm ra qui luật của chúng. Qua nghiên cứu có thể rút ra được hai cách tiếp cận sau:
a. Cách tiếp cận tổng thể:
Cách tiếp cận này còn được gọi là phương pháp thống kê. Cách này dựa vào nhận xét tinh tế, đó là những gì đã xảy ra trong quá khứ thì sẽ xảy ra trong tương lai. Điều này cũng đã được thừa nhận trên thực tế mà đặc trưng là những câu tục ngữ của cha ông chúng ta được đúc kết từ nhiều đời nay như: "Đêm tháng 5 chưa nằm đã sáng, ngày tháng 10 chưa cười đã tối", ...
Như vậy, để có mô hình luồng tin, chúng ta phải tìm ra một số điều kiện cho luồng tin. Ở đây chúng ta chỉ xét mô hình sinh tin là ngẫu nhiên nhận hữu hạn các giá trị từ một ngùôn tin bất kỳ sao cho sự xuất hiện của thông tin sau phụ thuộc vào giá trị của lượng thông tin đứng trư...