Phương pháp mã hóa độ dài loạt RLE: – Đề tài thực tập cơ sở ngành công nghệ thông tin – https://thomaygiat.com

Mã hóa theo độ dài loạt RLE ( Run Length Encoding ) là một giải pháp nén tài liệu dựa trên sự cắt bớt những dư thừa về khoảng trống. Loạt ở đây đượcđịnh nghĩa là dãy những thành phần tài liệu liên tục có cùng chung một giá trị .

Nguyên tắc:

Nguyên tắc của giải pháp này là phát hiện một loạt những thành phần của tài liệu lặp đi lặp lại liên tục, ví dụ : 110000000000000011. Ta thấy thành phần

có giá trị 0 xuất hiện nhiều lần liên tiếp thay vì phải lưu trữ toàn bộ các phần
tử có giá trị 0 ta chỉ cần lưu trữ chúng bằng cách sử dụng các cặp (độ dài
loạt, giá trị).

Bạn đang đọc: Phương pháp mã hóa độ dài loạt RLE: – Đề tài thực tập cơ sở ngành công nghệ thông tin – https://thomaygiat.com

Loại dư thừa đơn thuần nhất trong một tập tin là những đường chạy dài gồm những kí tự tái diễn, điều này thường thấy trong những tập tin đồ họa bitmap, những vùng tài liệu hằng của những tập tin chương trình, 1 số ít tập tin văn bản …
Ví dụ, xét chuỗi sau :
AAAABBBAABBBBBCCCCCCCCDABCBAAABBBBCCCD
Chuỗi này hoàn toàn có thể được mã hóa một cách cô đọng hơn bằng cách thay thế sửa chữa chuỗi kí tự lặp lại bằng một biểu lộ duy nhất của kí tự lặp lại cùng với một biến đếm số lần kí tự đó được lặp lại. Ta muốn nói rằng chuỗi này gồm bốn chữ A theo sau bởi ba chữ B rồi lại theo sau bởi hai chữ A, rồi lại theo sau bởi năm chữ B. .. Việc nén một chuỗi theo giải pháp này được gọi là mã hóa độ dài loạt. Khi có những loạt dài, việc tiết kiệm ngân sách và chi phí hoàn toàn có thể là đáng kể. Có nhiều cách để thực thi ý tưởng sáng tạo này, tùy thuộc vào những đặc trưng của ứng dụng ( những loạt chạy có khuynh hướng tương đối dài hay không ? Có bao nhiêu bit được dùng để mã hóa những kí tự đang được mã ? ) .
Nếu ta biết rằng chuỗi của tất cả chúng ta chỉ chứa những vần âm, thì ta hoàn toàn có thể mã hóa biến đếm một cách đơn thuần bằng cách xen kẻ những số lượng với những vần âm. Vì vậy chuỗi kí tự trên được mã hóa lại như sau :

#A4#B3#A2#B5#C8#D1#A1#B1#C1#B1#A3#B4#C3#D1

Xem thêm: Mã hóa đối xứng và mã hóa bất đối xứng là gì? – Azcoinvest

Ở đây ” # A4 ” có nghĩa là ” bốn chữ A ” … Chú ý là không đáng để mã hóa những loạt chạy có độ dài 1 hoặc 2 vì cần đến hai kí tự để mã hóa .
Đối với những tập tin nhị phân một phiên bản được tinh chế của chiêu thức này được dùng để thu được sự tiết kiệm chi phí đáng kể. Ý tưởng ở đây là lưu lại những độ dài loạt, tận dụng sự kiện những loạt chạy đổi khác giữa 0 và 1 để tránh phải lưu chính những số 0 và 1 đó. Điều này giả định rằng có một vài loạt chạy ngắn ( Ta tiết kiệm ngân sách và chi phí những bit trên một loạt chạy chỉ khi độ dài của đường chạy là lớn hơn số bit cần để biễu diễn chính nó trong dạng nhị phân ), nhưng khó có chiêu thức mã hóa độ dài loạt nào hoạt động giải trí thật tốt trừ phi hầu hết những loạt chạy đều dài .
trên sẽ không dùng được so với những chuỗi kí tự có chứa số. Nếu những kí tự khác được sử dụng để mã hóa những số đếm, thì nó sẽ không thao tác với những chuỗi chứa những kí tự đó. Giả sử ta phải mã hóa bất kể kí tự nào từ một bảng vần âm cố định và thắt chặt bằng cách chỉ dùng những kí tự từ bảng vần âm đó. Để minh họa, giả sử ta phải mã hóa bất kể một chuỗi nào từ một vần âm đó, ta sẽ giả định rằng ta chỉ có 26 vần âm trong bảng vần âm ( và cả khoảng trống ) để thao tác .
Để hoàn toàn có thể dùng vài vần âm để trình diễn những số và những kí tự khác trình diễn những thành phần của chuỗi sẽ được mã hóa, ta phải chọn một kí tự được gọi là kí tự ” Escape “. Mỗi một sự Open của kí tự đó báo hiệu rằng hai vần âm tiếp theo sẽ tạo thành một cặp ( số đếm, kí tự ) với những số đếm được màn biểu diễn bằng cách dùng kí tự thứ i của bảng vần âm để màn biểu diễn số i. Vì vậy, chuỗi ví dụ của tất cả chúng ta sẽ được màn biểu diễn như sau với Q. được xem là những kí tự ” Escape ”
QDABBBAABQHCDABCBAAAQDBCCCD

Tổ hợp của kí tự “Escape”, số đếm và một kí tự lặp lại được gọi là một dãy
Escape. Chú ý rằng không đáng để mã hoá các đường chạy có chiều dài ít hơn
bốn kí tự, vì ít nhất là cần đến ba kí tự để mã hoá bất kì một loạt chạy nào.

Xem thêm: 7 phương pháp dạy học tiếng việt theo hướng phát triển năng lực hiệu quả – https://thomaygiat.com

Trong trường hợp bản thân kí tự ” Escape ” Open trong dãy kí tự cần mã hóa ta sử dụng một dãy ” Escape ” với số đếm là 0 ( kí tự space ) để màn biểu diễn kí tự ” Escape “. Như vậy trong trường hợp kí tự ” Escape ” Open nhiều thì hoàn toàn có thể làm cho tập tin nén phình to hơn trước .
Các loạt chạy dài hoàn toàn có thể được cắt ra để mã hóa bằng nhiều dãy Escape, ví dụ, một loạt chạy gồm 51 chữ A sẽ được mã hóa như QZAQYA bằng cách dùng trên .

Phương pháp mã hóa độ dài loạt thường được vận dụng cho những tập tin đồ họa bitmap vì ở đó thường có những mảng lớn cùng màu được trình diễn dưới dạng bitmap là những chuỗi bit có đường chạy dài. Trên trong thực tiễn, nó được dùng trong những tập tin. PCX ,. RLE .

Source: https://thomaygiat.com
Category : Kỹ Thuật Số