Skip to main content

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
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:



Comments

Popular posts from this blog

[STM32] How to configure Timer 1, Channel 3 is PWM 1kHz, duty cycle 20% to control BLDC motor

 To configure Timer1 for a 1 kHz PWM signal with a 20% duty cycle on an STM32H7S3L8 microcontroller, follow these steps: 1. Understand the Timer Parameters PWM Frequency : 1 kHz → Period = 1 ms. Duty Cycle : 20% → ON time = 0.2 ms. The timer’s clock frequency is derived from the APB clock (e.g., TIMCLK). Let’s assume you know the APB clock frequency. The Timer prescaler and auto-reload register (ARR) define the PWM frequency. 2. Compute Timer Parameters Formula: PWM Frequency = Timer Clock (Prescaler + 1) * (ARR + 1) \text{PWM Frequency} = \frac{\text{Timer Clock}}{\text{(Prescaler + 1) * (ARR + 1)}} PWM Frequency = (Prescaler + 1) * (ARR + 1) Timer Clock ​ For 1 kHz PWM: A R R = Timer Clock PWM Frequency ∗ ( Prescaler + 1) − 1 ARR = \frac{\text{Timer Clock}}{\text{PWM Frequency} * (\text{Prescaler + 1)}} - 1 A RR = PWM Frequency ∗ ( Prescaler + 1) Timer Clock ​ −...

[CanadaLife] Example of answers for final test in Smart Service Ontario 2024

If you have failed the final exam in the first attempt. Congratulations, you are not odd. Here, take a look and grab some corrected answers for your next attempt.  Don't waste your money and time for more failure.  Good luck bros. Quick note: remember that, the system will change the bunch of questions after each attempt. Then your next questionnaire will be different compared with the first trial. ========================================== =============FINAL TEST=================== ========================================== TIP: Here is a list of questions you did not answer correctly. *Please note: You will only be able to view this list immediately following your test attempt. ========================================== Alcohol slows down the central nervous system and impacts how a person thinks, acts, and moves. This means alcohol is a: depressant ========================================== Alcohol is metabolized in the body at a set rate. For most people, that rate is: one...

How to test frame buffer in linux

The intended goal of this article is to provide the user with enough information so they can display an image onto a screen of their choosing. How to re-build frame buffer testing application. Base knowledge http://trac.gateworks.com/wiki/OpenEmbedded/Video_Out Frame buffer test application - rebuild fb-test-app step 1: Download soure code ( git installed on your machine and account in git-hub is required) https://github.com/prpplague/fb-test-app Command in git: git init git clone https://github.com/prpplague/fb-test-app.git step 2: Change makefile vi Makefile //open Makefile by vim editor :set nu //show line number replace from line 6 to line 12 by folow code: CC=arm-linux-gnueabi-gcc CFLAGS=-02 -Wall Save change command :wq step 3: Rebuid Type “make” command step 4: Copy execute file to target system by filezilla or something like that step 5: Remote target by root account, change mode of execute file (what copied from host) ...