A Simple String Compression Algorithm

Thuật toán đơn giản dùng để giảm dung lượng bộ nhớ để lưu string

Giả sử ta cần lưu string như thế này: string1 =  "ABCDAAB"

Dễ thấy, với một ký tự trong string ta cần 1 byte hay 8 bít để biểu diễn

Vậy string1 sẽ cần 7 byte (7*8 = 56 bít) trong bộ nhớ.

Vậy làm thế nào để lưu string này với ít hơn 7 byte?

Cách 1:

1. Dễ thấy string 1 được biểu diễn bới 4 ký tự: 'A', 'B', 'C', 'D'

Bước 1: Lập 1 bảng hằng số để định nghĩa lại các ký tự này

A là số 1 => A = 00000001

B là số 2 => B = 00000010

C là số 3 => C = 00000011

D là số 4 => D = 00000100

Bước 2: Nhìn bảng, ta thấy mỗi ký tự chỉ cần 3 bít để biểu diễn

A là số 1 => A = 001

B là số 2 => B = 010

C là số 3 => C = 011

D là số 4 => D = 100

Bước 3: Biểu diễn string1 theo bảng hằng số vừa được định nghĩa

before: string1 = A     B   C     D   A    A    B

after  :  string1 = 001 010 011 100 001 001 010

Vậy rõ ràng, sau khi biến đổi, ta chỉ cần 3*7 = 21 bít (<56 bít) để biểu diễn string1

Thank to: http://www.codeproject.com/Articles/223610/A-Simple-String-Compression-Algorithm

Cách 2:

For example, consider a screen containing plain black text on a solid white background. There will be many long runs of white pixels in the blank space, and many short runs of black pixels within the text. Let us take a hypothetical single scan line, with B representing a black pixel and W representing white:

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

If we apply the run-length encoding (RLE) data compression algorithm to the above hypothetical scan line, we get the following:

12W1B12W3B24W1B14W

Cách này cũng có ưu điểm và nhược điểm nhất định, tùy từng trường hợp mà áp dụng cho phù hợp

Reference:

http://www.inference.phy.cam.ac.uk/itprnn/code/c/compress/

http://en.wikipedia.org/wiki/Run-length_encoding