Nguyễn Thị Hương k49db Khóa luận tốt nghiệp
LỜI MỞ ĐẦU
Trong thập kỉ trước nén dữ liệu đã được sử dụng ở khắp mọi nơi. Có thể nói rằng
nén dữ liệu đã trở thành yêu cầu chung cho các hầu hết các phần mềm ứng dụng, và
cũng là một lĩnh vực nghiên cứu quan trọng và hấp dẫn trong khoa học máy tính. Nếu
không có các kĩ thuật nén dữ liệu thì sẽ không bao giờ có sự phát triển của Internet, TV
số, truyền thông di động hay sự phát triển của các kĩ thuật truyền thông video. Ưu điểm
nổi bật và hiệu quả của nén đã được áp dụng và phát triển nhiều lĩnh vực khác như
truyền thông đa phương tiện hay các lĩnh vực nghiên cứu khác. Thời gian gần đây, một
lĩnh vực đang phát triển rất nhanh và ngày càng thu hút sự quan tâm của nhiều người đó
là y tế từ xa (Telemedicine), mà nén đóng vai trò rất quan trọng. Từ đó con người sẽ
được chăm sóc sức khoẻ tốt hơn bằng cách có thể khám, chữa bệnh từ bất kì một bệnh
viện nào trên thế giới mà không cần phải đến tận nơi đó. Chỉ cần giao tiếp với bác sĩ qua
thiết bị thu ghi và phương tiện truyền thông thì sau đó sẽ nhận được kết quả chẩn đoán
và phương thức chữa bệnh của bác sĩ gửi về. Một trong những tín hiệu EEG quan trọng
nhất đó là tín hiệu EEG. Và trong bài báo cáo này sẽ trình bày các phương pháp nén
được sử dụng để nén tín hiệu EEG. Sự cần thiết của việc này như thế nào sẽ được trình
bày sau đây.
4/25/2013 - 1 -
Nguyễn Thị Hương k49db Khóa luận tốt nghiệp
CHƯƠNG 1: GIỚI THIỆU CHUNG
1.1. Nén dữ liệu
Nén dữ liệu hay còn gọi là mã hóa nguồn (source coding), là sự biểu diễn thông
tin của dữ liệu nguồn dưới dạng nén. Nó đã là một công nghệ then chốt trong cuộc cách
mạng truyền thông đa phương tiện số trong nhiều thập kỉ.
Mục tiêu của nén dữ liệu bao gồm việc tìm ra một thuật toán hiệu quả để loại bỏ dư thừa
tồn tại trong dữ liệu đó. Ví dụ cho một xâu kí tự S, thì cái gì là chuỗi kí tự có thể thay
thế được để cho ta một không gian tích trữ nhỏ hơn? Những giải pháp cho vấn đề này là
những thuật toán nén mà sẽ xuất phát từ chuỗi kí tự có thể thay thế được để thu được số
bit ít hơn trong toàn bộ số bit cần biểu diễn, cùng với những thuật toán giải nén để khôi
phục lại dữ liệu ban đầu.

bệnh. Cần phải truyền một lượng lớn dữ liệu y sinh đã thúc đẩy sự cần thiết của việc
nén dữ liệu y sinh mà không mất thông tin quan trọng mang trên những tín hiệu ghi
đựơc mà có thể dẫn tới hành động chuẩn đoán hay đánh giá bệnh sai. Do đó, nghiên cứu
về nén tín hiệu y-sinh là rất cần thiết. Một trong những tín hiệu y-sinh phổ biến hiện nay
là tín hiệu điện não (EEG- Electroencephalogram). Tín hiệu EEG ghi lại các hoạt động
điện của não nhằm phục vụ các nghiên cứu về não, hay chẩn đoán và điều trị bệnh nhân
có rối lọan não. Ví dụ như, chuẩn đoán động kinh và vị trí não bị tổn thương liên quan
đến rối loạn này- một chứng bệnh rất phổ biến trên thế giới cũng như ở Việt Nam.
1.2.1. Tín hiệu EEG
4/25/2013 - 4 -
Nguyễn Thị Hương k49db Khóa luận tốt nghiệp
Những hoạt động điện của vỏ não thường là những tín hiệu nhịp (rhythms) vì
chúng thường dao động lặp đi lặp lại. Sự đa dạng của tín hiệu nhịp EEG vô cùng lớn và
phụ thuộc vào nhiều yếu tố trong trạng thái tinh thần của đối tượng, như là mức độ kích
động, trạng thái đi bộ hay trạng thái ngủ. Thông thường, những tín hiệu được ghi trên da
đầu có biên độ nằm trong khoảng từ vài microvolts tới xấp xỉ 100 µV, và tần số trong
khoảng từ 0.5 đến 30-40 Hz.
Hình 4 : các tín hiệu nhịp EEG
Tín hiệu EEG cơ bản được chia thành 5 dải tần sau :
 Nhịp Alpha : là nhịp cơ sở của não người lớn. Là dạng sóng dễ nhận biết nhất, đi
thành chuỗi sóng 8-13 Hz với biên độ 30-50 mV
Hình 5: tín hiệu alpha
 Nhịp Beta : là sóng có tần số 4-35 Hz, điện thế khoảng 5-30 mV
Hình 6: tín hiệu Beta
 Nhịp Delta : là một sóng chậm dưới 4 Hz và có biên độ thay đổi
4/25/2013 - 5 -
Nguyễn Thị Hương k49db Khóa luận tốt nghiệp
Hình 7: tín hiệu Delta
 Nhịp Theta : bao gồm các sóng 4-8 Hz , thường có biên độ lớn hơn 20 mV
Hình 8: tín hiệu Theta

Động kinh đôi khi biến chứng và tai nạn có thể gặp khi bệnh nhân lên cơn động kinh: cắn
phải lưỡi, viêm phổi do hít phải dãi hay chất nôn ói; gãy xương do chấn thương; tổn thương
não do cưoin kéo dài làm não thiếu oxy; ngừng thở do tắc nghẽn đường thở… Tuy nhiên,
bệnh hoàn toàn có thể điều trị nếu được phát hiện sớm và điều trị đúng cách thì khả năng
hoàn toàn khỏi bệnh là rất cao. Đối với trẻ em, nếu không được điều trị kịp thời, hoặc điều
trị không đúng cách dẫn tới tình trạng không khống chế được cơn co giật. Lâu dần, trẻ sẽ bị
thiểu năng trí tuệ, rối loạn hành vi. Những cơn co giật sẽ làm cho hệ miễn dịch của trẻ yếu
đi, dễ nhiễm các bệnh khác và dễ tử vong hơn trẻ bình thường. Tre bị động kinh không
được điều trị đúng thuốc, đúng phác đồ nên sinh ra kháng thuốc. Khi đó, khả năng hồi phục
sẽ khó khăn hơn rất nhiều. Do đó việc phát hiện kịp thời động kinh, chẩn đoán chính xác
bệnh và điều trị hợp lý là vô cùng quan trọng, cấp bách và cần thiết. Song không phải bất kì
bệnh viện nào cũng làm được điều đó vì nó hoàn toàn phụ thuộc vào trình độ và khả năng
của bác sĩ đọc điện đồ não. Tín hiệu EEG ghi được rất phức tạp bởi bản ghi không chỉ có
tín hiệu nền cơ bản (alpha, gamma,…), các xung bất thường (spike, sharp…) mà nó còn có
rất nhiều các loại artifact (ECG, EMG…). Hơn nữa việc nhận biết các sóng nhịp cơ bản
cũng không đơn giản, dễ dàng do các nhịp này xuất hiện phụ thuộc vào tuổi, vào trạng thái
tinh thần của bệnh nhân. Song chúng ta có thể khắc phục được khó khăn này bằng việc gửi
4/25/2013 - 7 -
Nguyễn Thị Hương k49db Khóa luận tốt nghiệp
tín hiệu điện não EEG từ một nơi không đáng tin cậy đến những nơi tin cậy mà ở đó có
những bác sĩ giỏi, kinh nghiệm thực hiện việc đọc bản ghi và chẩn đoán lâm sàng. Từ đây
phát sinh một yêu cầu cần thiết là thực hiện truyền hiệu quả tín hiệu EEG cả về mặt vật lý
lẫn hiệu quả kinh tế. Do đó thực hiện nén EEG là cần thiết. Hơn nữa thực hiện công việc
này cũng sẽ giúp ích rất nhiều trong việc nghiên cứu về tín hiệu EEG như việc loại bỏ
artifacts, dò tìm xung động kinh, và phân loại các dạng xung này bằng việc gửi bản ghi điện
não từ bệnh viện đến nơi thực hiện nghiên cứu. Trước tiên nén là để giảm thời gian truyền,
giảm không gian lưu trữ, và trong những hệ thống xách tay, nó giảm yêu cầu bộ nhớ hay
tăng số lượng kênh và dải thông. Một trong những mục đích đầu tiên của việc làm này là tự
động thu thập những dữ liệu EEG mà được yêu cầu với những đặc tính hạn chế từ trước
( luồng dữ liệu 20 480 bps) từ bệnh viện ngoại vi hay từ nhà bệnh nhân, mà truyền qua môi

xuất hiện thường xuyên và những từ mã dài hơn cho những kí tự xuất hiện ít hơn.
Ví dụ, cho mã chiều dài thay đổi (0, 100, 101, 110, 111) với chiều dài từ mã (1, 3, 3, 3,
3) cho bảng kí tự (A, B, C, D, E), và chuỗi kí tự nguồn là BAAAAAAAC với tần suất
của mỗi kí tự là (7, 1, 1, 0, 0). Khi đó lượng bít trung bình được yêu cầu là:
(2.1)
Việc này đã tiết kiệm được gần một nửa số bit so với việc biểu diễn bằng mã chiều dài
cố định 3 bits/symbol
Một nguồn được mô hình hoá bằng một bảng S = (s1, s2, …, sn) và sự phân phối xác
suất tương ứng là P = (p1, p2,…,pn)
Giả sử chúng ta xuât phát từ mã C =(c1, c2, …, cn) với chiều dài mỗi từ mã là L = (l1,
l2,…, ln).

Hình 11 : Code and source data
4/25/2013 - 9 -
Nguyễn Thị Hương k49db Khóa luận tốt nghiệp
Mục tiêu của chúng ta là cực tiểu hoá chiều dài trung bình của từ mã :
(2.2)
Do vậy mã chiều dài thay đổi rất hữu ích cho việc nén dữ liệu. Tuy nhiên, một mã
chiều dài thay đổi sẽ trở nên vô giá trị nếu như không thể nhận ra một cách duy nhất
những từ mã của mã này từ bản tin đã được mã hoá
Ví dụ : Cho mã chiều dài thay đổi (0, 10, 010, 101) của bảng kí tự (A, B, C, D) . Một
đoạn tin là ‘0100101010’ có thể được giải mã nhiều hơn một cách. Ví dụ ‘0100101010’
có thể dịch là ‘ 0 10 010 101 0’ là ‘ ABCDA’ hoặc ‘010 0 101 010 ‘ là CADC.
Khi đó sẽ không nhận được chính xác dữ liệu nguồn
Một mã được coi là có khả năng giải mã duy nhất nếu có duy nhất một cách có thể
để giải mã bản tin mã hoá.
Một giải pháp dường như khả quan cho những trường hợp mã không phải là mã có khả
năng giải mã duy nhất đó là thêm vào những kí tự phân cách mở rộng trong giai đoạn
mã hoá. Ví dụ, chúng ta sử dụng kí tự ‘/’, sau đó mã hoá chuối kí tự ABCDA là
‘0/10/010/101/0’. Tuy nhiên, phương pháp này phải trả giá quá đắt bởi vì kí tự mở rộng

chứa trong nó khác không. Nếu ta càng không thể ngờ tới điều ấy thì thông tin
điều đó mang lại cho ta càng lớn
Tóm lại, ta nhận thấy khái niệm thông tin gắn liền với sự bất định của đối tượng ta
cần xét. Có sự bất định về một đối tượng nào đó thì những thông báo về đối tượng
đó sẽ cho ta thông tin. Khi không có sự bất định thì sẽ không có thông tin về đối
tượng đó. Như vậy, khái niệm thông tin chỉ là một cách diễn đạt khác đi của khái
niệm sự bất định.
Trước khi nhận tin (được thông báo) về một đối tượng nào đấy thì vẫn còn sự bất
định về đối tượng đó, tức là độ bất định về đối tượng đó khác không (có thể lớn hay
nhỏ). Sau khi nhận tin (đã được hiểu rõ hoặc hiểu một phần) về đối tượng thì độ bất
định của nó giảm đến mức thấp nhất, hoặc hoàn toàn mất. Như vậy, “ thông tin là độ
bất định đã bị thủ tiêu” hay nói một cách khác “ làm giảm độ bất định kết quả cho ta
thông tin”
4/25/2013 - 11 -
Nguyễn Thị Hương k49db Khóa luận tốt nghiệp
2.2.2. Lượng thông tin
2.2.2.1. Định nghĩa lượng thông tin
Như chúng ta đã biết : trước khi nhận tin thì độ bất định lớn nhất, sau khi nhận tin
(hiểu rõ hoặc hiểu một phần về đối tượng thì độ bất định giảm đến mức thấp nhất), có
khi triệt tiêu hoàn toàn. Như vậy, có một sự chệnh lệch giữa độ bất định trước khi nhận
tin và độ bất định sau khi nhận tin. Sự chênh lệch đó là mức độ thủ tiêu độ bất định. Độ
lớn, nhỏ của thông tin mang đến cho ta phụ thuộc trực tiếp vào mức độ lệch đó. Vậy :
“Lượng thông tin là mức độ bị thủ tiêu của độ bất định  Lượng thông tin = độ
chêch của độ bất định trước và sau khi nhận tin = độ bất định trước khi nhận tin - độ bất
định sau khi nhận tin (độ bất định tiên nghiệm - độ bất định hậu nghiệm) “.
2.2.2.2.Giới thiệu về lý thuyết thông tin
Mặc dù những kiến thức về đo lượng thông tin đã được sử dụng một thời gian,
song người đã gom góp tất cả mọi thứ lại thành một lĩnh vực được gọi là lý thuyết thông
tin (information theory) là Claude Elwood Shannon, một kĩ sư điện ở phòng thí nghiệm
Bell. Shannon đã định nghĩa một đại lượng gọi là lượng thông tin (self-information).

P(AB) = P(A)P(B) (2.5)
Và do đó
i(AB) = log
b
)()(
1
BPAP
= log
b
)(
1
AP
+ log
b
)(
1
BP
= i(A) + i(B) (2.6)
Đơn vị thông tin phụ thuộc vào cơ số của hàm log. Nếu chúng ta sử dụng cơ số 2,
thì đơn vị là bits, nếu sử dụng cơ số e, đơn vị là nats; và nếu sử dụng có số 10, thì đơn vị
là hartleys.
4/25/2013 - 13 -
Nguyễn Thị Hương k49db Khóa luận tốt nghiệp
Lưu ý rằng tính toán thông tin bằng bits, chúng ta cần phải lấy logarithm cơ số 2
của xác suất. Bởi vì hàm này không xuất hiện trong máy tính, nên ta phải thực hiện như
sau :
Ta có : log
b
x = a
Suy ra : b

) = - ΣP(A
i
)log
b
P(A
i
). (2.8)
Đại lượng này được gọi là entropy của thí nghiệm. Một trong những đóng góp của
Shannon là ông đã chỉ ra rằng nếu thí nghiệm là một nguồn bao gồm những kí tự A
i
, từ
tập hợp A, thì entropy là đại lượng đo số lượng kí tự nhị phân trung bình cần để mã hoá
lối ra của nguồn. Shanno đã chứng minh rằng một sơ đồ nén không mất thông tin tốt
nhất (lossless compression) là có thể thực hiện được nén lối ra nguồn với lượng bit trung
bình bằng với entropy của nguồn.
Tập hợp những kí tự A thường được gọi là bảng chữ của nguồn, và những kí tự
được gọi là những chữ cái. Đối với một nguồn S tổng quát với bảng chữ A = {1, 2,…,
m} mà tạo ra một chuỗi {X
1
, X
2
, …}, thì entropy được cho bởi
H(S) =
∞→
n
lim
Gn
n
1
(2.9)

=i
2
,
…, X
n
=i
n
) (2.10)
4/25/2013 - 14 -
Nguyễn Thị Hương k49db Khóa luận tốt nghiệp
Và (X
1
, X
2
, …, X
n
) là một chuỗi chiều dài n từ nguồn. Nếu mỗi thành phần trong
chuỗi là phân phối độc lập đồng nhất (independent and identically distributed (iid)) , thì
chúng ta cho có chứng minh rằng
Gn = -n
∑
=
=
==
mi
i
iXPiXP
1
1
1

Chúng ta dễ dàng nhận ra rằng quan sát đầu tiên là đúng. Nếu những kí tự mà xảy ra
thường xuyên hơn có từ mã dài hơn từ mã của những kí tự xảy ra ít thường xuyên hơn,
thì số lượng bit trung bình trên mỗi kí tự sẽ lớn hơn nếu trường hợp ngược lại.
Vì vậy, một mã gán những từ mã dài hơn cho những kí tự xảy ra thường xuyên không
thể tối ưu
4/25/2013 - 15 -
Nguyễn Thị Hương k49db Khóa luận tốt nghiệp
Chúng ta hãy xem xét tại sao quan sát thứ hai đúng, xét trường hợp sau. Giả sử tồn
tại một mã tối ưu C trong đó hai từ mã tương ứng với hai kí tự xác suất thấp nhất không
có chiều dài giống nhau. Giả sử từ mã dài hơn dài hơn k bits so với từ mã ngắn hơn. Do
đây là mã prefix, nên từ mã ngắn hơn không thể là tiền tố của từ mã dài hơn. Điều này
có nghĩa là thậm chí nếu chúng ta để k bits rơi vào k vị trí cuối cùng của từ mã dài hơn,
thì hai từ mã này vẫn hoàn toàn khác biệt. Do những từ mã này tương ứng với những kí
tự xác suất thấp nhất trong bảng kí tự, nên sẽ không có một từ mã nào khác có thể dài
hơn những từ mã này; vì vậy, sẽ không có nguy cơ là từ mã ngắn hơn sẽ trở thành tiền
tố của từ mã khác nào đó. Hơn nữa, cắt bỏ k bit này chúng ta sẽ thu được một từ mã mới
có chiều dài trung bình ngắn hơn C . Nhưng điều này vi phạm đến luận điểm ban đầu
của chúng ta là C là một mã tối ưu. Vì vậy đối với một mã tối ưu quan sát thứ hai là
đúng.
Thu được thủ tục mã Huffman bằng cách bổ sung một yêu cầu đơn giản đối với
hai quan sát này. Yêu cầu này là những từ mã tương ứng với hai kí tự có xác suất thấp
nhất chỉ khác nhau ở bit cuối cùng. Có nghĩa là, nếu γ và δ là hai kí tự xác suất thấp nhất
trong bảng kí tự, nếu từ mã của γ là m*0, thì từ mã của δ sẽ là m*1. Ở đây m là một
chuỗi bit 0 và 1, và * biểu thị sự móc nối vào nhau.
Yêu cầu này không vi phạm hai quan sát của chúng ta và dẫn đến một thủ tục mã
hoá rất đơn giản.
Chiều dài trung bình của một mã là :
L =
∑
)()(


a4(0.1) 0 (0.2)
a5(0.1) 1
Hình 14: Cây huffman
Một cách khác xây dựng mã Huffman sử dụng thực tế là mã Huffman, do ưu điểm
của mã tiền tố, có thể biểu diễn là một cây nhị phân trong đó những nút ngoài hay lá
ngoài sẽ tương ứng với những kí tự. Mã Huffman này đối với bất kì kí tự nào có thể thu
được bằng cách di chuyển trên cây từ nút gốc đến lá tương ứng với kí tự, cộng bit 0 tới
từ mã mỗi lần chúng ta đi qua một cành cao hơn, và bit 1 mỗi lần đi qua cành thấp hơn.
Chúng ta xây dựng cây nhị phân bắt đầu tại những nút lá. Như đã biết những từ mã
của hai kí tự với xác suất nhỏ nhất là giống nhau ngoại trừ bit cuối cùng. Điều này có
nghĩa là việc di chuyển từ gốc tới lá tương ứng với hai kí tự này là như nhau trừ bước
cuối cùng. Tức là những lá tương ứng với hai kí tự với xác suất thấp nhất sẽ là con của
cùng một gốc. Khi chúng ta kết nối những lá tương ứng với những kí tự có xác suất thấp
nhất tới một nút duy nhất, thì chúng ta coi như nút này là một kí tự của bảng chữ đã
được giảm bớt. Xác suất của kí tự này sẽ là tổng xác suất của các con của nó. Bây giờ
chúng ta sẽ sắp xếp những nút tương ứng bảng kí tự giảm bớt và áp dụng quy tắc như
trên để tạo ra một nút bố cho những nút tương ứng với hai kí tự có xác suất thấp nhất
trong bảng giảm bớt. Cứ tiếp tục như thế cho đến khi ta thu được một nút duy nhất, đó
chính là nút gốc. Để thu được một mã cho mỗi kí tự, chúng ta di chuyển trên cây từ gốc
tới mỗi nút lá, bằng cách gán 0 tới cành cao hơn và 1 cho cành thấp hơn
Ví dụ :
4/25/2013 - 17 -
Nguyễn Thị Hương k49db Khóa luận tốt nghiệp
Cho bảng tần suất của 5 chữ cái A,B,C,D,E như sau tương ứng là 0.10; 0.15; 0.30;
0.16; 0.29
A B C D E
0.10 0.15 0.30 0.16 0.29
Quá trình xây dựng cây Huffman diễn ra như sau :
N

nhỏ. Tuy nhiên, có những trường hợp ở đó bảng chữ là nhỏ và xác suất xảy ra của
những kí tự khác nhau rất lệch, giá trị của p
max
có thể khá lớn và mã Huffman có thể trở
nên khá không hiệu quả khi so sánh với entropy. Một cách để tránh vấn đề này là chặn
khối nhiều hơn một kí tự với nhau và tạo ra một mã Huffman mở rộng. Tuy nhiên, thực
tế không phải phương thức này bao giờ cũng thực hiện được.
Tạo ra những từ mã (codewords) cho nhóm hoặc chuỗi kí tự thực sự hiệu quả
hơn là tạo ra một từ mã riêng biệt cho mỗi kí tự trong chuỗi. Song phương pháp này
trở nên không khả thi khi cố gắng tạo ra mã Huffman cho chuỗi kí tự dài. Để tìm từ
mã Huffman cho một chuỗi dài m (sequence of symbols m) riêng biệt chúng ta cần
những từ mã cho tất cả những chuỗi chiều dài m có thể. Việc này sẽ làm cho kích
thước của sách mã (codebook) tăng theo hàm mũ. Chúng ta cần một phương pháp gán
từ mã cho chuỗi riêng biệt này mà không phải tạo những mã cho tất cả các chuỗi có
cùng chiều dài. Kĩ thuật mã hoá số học (arithmetic coding technique) sẽ thực hiện
được yêu cầu này.
4/25/2013 - 19 -
Nguyễn Thị Hương k49db Khóa luận tốt nghiệp
Trong mã hoá số học, phải tạo ra một bộ nhận dạng duy nhất hay một nhãn
(tag)cho chuỗi được mã hoá. Nhãn này tương ứng với một phân số nhị phân, cái mà sẽ
trở thành mã nhị phân của chuỗi. Thực tế việc tạo nhãn và mã nhị phân là hai quá trình
giống nhau. Tuy nhiên, chúng ta có thể hiểu dễ dàng hơn phương pháp mã số học nếu
về mặt lý thuyết chia phương pháp này thành hai giai đoạn. Trong giai đoạn đầu tạo ra
một bộ nhận dạng duy nhất hay nhãn cho chuỗi kí tự đã cho. Sau đó cho nhãn này một
mã nhị phân duy nhất . Mã số học duy nhất có thể được tạo ra cho một chuỗi dài m mà
không cần phải tạo ra mọi từ mã cho những chuỗi cùng chiều dài. Điều này không giống
với mã Huffman.
Để phân biệt một chuỗi kí tự này với một chuỗi kí tự khác chúng ta cần phải gán
nhãn cho nó bằng một bộ nhận dạng duy nhất. Một tập hợp nhãn có thể dùng biểu diễn
những chuỗi kí tự là những số trong khoảng đơn vị [0, 1). Do trong khoảng đơn vị [0, 1)

i
k=1
P(X = k) (2.14)
Chú ý rằng đối với mỗi kí tự a
i
với xác suất khác không chúng ta có một giá trị
riêng biệt của F
x
(i). Chúng ta sẽ sử dụng điều này để sau đó phát triển mã số học.
Thủ tục tạo nhãn thực hiện bằng cách giảm kích thước của khoảng mà trong đó
nhãn cư trú do càng ngày nhận càng nhiều những phần tử của chuỗi.
Hãy bắt đầu bằng việc đầu tiên chia khoảng đơn vị thành những khoảng con có
dạng [F
x
(i-1), F
x
(i)), i = 1, …, m. Vì giá trị cực tiểu của hàm phân phối tích luỹ (cdf)
bằng không và giá trị cực đại bằng một, nên việc phân chia phải chính xác khoảng đơn
vị. Chúng ta liên kết khoảng con [F
x
(i-1), F
x
(i)) với kí tự a
i
. Sự xuất hiện của kí tự đầu
4/25/2013 - 20 -
Nguyễn Thị Hương k49db Khóa luận tốt nghiệp
tiên trong chuỗi sẽ giới hạn khoảng chứa nhãn từ một trong những khoảng con này. Giả
sử rằng kí tự đầu tiên là a
k

(k-1) + F
x
(j-1)/(F
x
(k) – F
x
(k-1), F
x
(k-1) +
F
x
(j)/(F
x
(k) – F
x
(k-1)). Mỗi kí tự tiếp theo khiến cho nhãn tương ứng bị giới hạn tới một
khoảng mà được phân chia nữa với tỉ lệ giống nhau.
Xét Ví dụ:
Xét một bảng chữ 3 kí tự A = {a
1
, a
2
, a
3
} với xác suất p(a
1
) = 0.7, p(a
2
) = 0.1, và
p(a

. Nhãn sẽ nằm trong
4/25/2013 - 21 -
Nguyễn Thị Hương k49db Khóa luận tốt nghiệp
khoảng con [0.0, 0.7). Sau đó khoảng này lại được chia theo tỉ lệ chính xác giống như
khoảng nguồn, để tạo ra những khoảng con [0.0, 0.49), [0.49, 0.56), [0.56, 0.7). Khoảng
đầu tiên tương ứng với kí tự a
1
, khoảng thứ hai tương ứng với kí tự a
2
, và khoảng còn lại
[0.56, 0.7) tương ứng với kí tự a
3
. Giả sử rằng kí tự thứ hai trong chuỗi là a
2
. Khi đó giá
trị nhãn được giới hạn nằm trong khoảng [0.49, 0.56). Bây giờ chúng ta phân chia
khoảng này thành các khoảng con theo cùng tỉ lệ như khoảng ban đầu, thu được các
khoảng sau : khoảng [0.49, 0.539) tương ứng với kí tự a
1
, [0.539, 0.546) tương ứng với
kí tự a
2
, và [0.546, 0.56) tương ứng với kí tự a
3
. Nếu kí tự thứ ba là a
3
, nhãn sẽ bị giới
hạn trong khoảng [0.546, 0.56), sau đó khoảng này có thể sẽ được chia nhỏ hơn nữa.
Quá trình này sẽ tiếp tục cho đến khi hoàn thành xong chuỗi nguồn theo cách thức như
trên.

đồng khả năng, thì chúng ta sẽ có một mã mà gán 20 bít cho mỗi mẫu 4 kí tự này. Giả
sử đặt 256 mẫu 4 kí tự mà có khả năng nhất vào trong từ điển. Lưu đồ truyền thực hiện
như sau : bất cứ khi nào muốn gửi một mẫu mà có tồn tại trong từ điển, chúng ta sẽ gửi
một bit cờ (flag), giả sử bit 0, theo sau bởi một chỉ số 8 bit tương ứng với mục từ trong
từ điển. Nếu mẫu đó không có trong từ điển, chúng ta sẽ gửi bit 1 theo sau bởi 20 bit mã
hóa mẫu. Tính hữu dụng của lưu đồ này phụ thuộc vào phần trăm những từ mà chúng ta
bắt gặp có trong từ điển. Có thể đánh giá tính hữu dụng này bằng cách tính số bit trung
bình trên mỗi mẫu. Nếu xác suất bắt gặp một mẫu trong từ điển là p, thì số bit trung bình
trên mỗi mẫu R là :
R=9p + 21(1-p) = 21- 12p (2.15)
Để sơ đồ này hiệu quả, R phải có giá trị nhỏ hơn 20, khi đó p ≥ 0.084. Giá trị này
dường như không lớn. Tuy nhiên, nếu các mẫu xảy ra là đồng khả năng, thì xác suất bắt
gặp một mẫu trong từ điển thấp hơn 0.00025.
Chúng ta hoàn toàn không muốn một lưu đồ mã hóa mà chỉ thực hiện tốt hơn một chút
phương pháp mã hóa thông thường cho những mẫu đồng khả năng; mà chúng ta muốn
cải thiện hiệu suất nhiều nhất có thể. Để đạt được điều này, p phải lớn nhất có thể. Có
nghĩa là chúng ta phải lựa chon cẩn thận những mẫu có khả năng xảy ra nhất để đưa vào
trong từ điển. Do đó chúng ta phải có những hiểu biết khá tốt về cấu trúc lối ra nguồn.
Nếu không có thông tin giá trị kiểu này trước khi mã hóa một lối ra nguồn cụ thể, bằng
cách này hay cách khác chúng ta cần phải có được thông tin trong khi đang thực hiện
mã hóa. Nếu cảm thấy đã có đầy đủ hiểu biết trước, chúng ta có thể sử dụng phương
pháp tĩnh (static approach); nếu không, nên sử dụng phương pháp thích nghi (adaptive
approach).
2.3.1.4. Phương pháp nén dựa vào ngữ cảnh (context-based compression)
Phần này chúng ta sẽ trình bày một phương pháp nén sử dụng tối thiểu những giả
thuyết từ trước về thống kê của dữ liệu. Thay vào đó chúng sử dụng ngữ cảnh của dữ
liệu đang được mã hoá và lịch sử quá khứ của dữ liệu để cung cấp kĩ thuật nén hiệu quả
hơn.
Như chúng ta học, chúng ta sẽ nhận được hiệu suất nén càng cao khi bản tin mã
hoá có tập hợp xác suất càng “lệch” (“skewed). “Skewed” có nghĩa rằng những kĩ tự có

cặp đôi toán học tại điểm kết thúc nhận sẽ cho phép chuỗi lệch này biểu diễn chuỗi
nguồn tại bộ nhận. Shannon đã sử dụng thí nghiệm của mình để tiến đến giới hạn trên
và dưới cho bảng chữ cái tiếng Anh (lần lượt là 1.3 bit /chữ cái và 0.6 bit / chữ cái)
Cái khó trong việc sử dụng những thí nghiệm này là đối tượng đoán là người dự
đoán kí tự tiếp theo trong chuỗi tốt hơn nhiều bất kí một bộ dự đoán toán học nào mà
chúng ta có thể triển khai. Giả sử rằng ngữ văn là bẩm sinh đối với mỗi người, ở đó
trường hợp phát triển một bộ dự đoán hiệu quả như con người đối với ngôn ngữ là
không thể trong tương lai gần. Tuy nhiên thí nghiệm thực hiện cung cấp một phương
pháp nén hữu dụng cho nén tất cả mọi loại chuỗi , chứ không chỉ đơn giản cho những
biểu diễn ngôn ngữ.
4/25/2013 - 24 -
Nguyễn Thị Hương k49db Khóa luận tốt nghiệp
Nếu chuỗi kí tự được mã hoá không bao gồm sự xảy ra độc lập của các kí tự, thì
những kiến thức về những kí tự đã xảy ra ở lân cận của kí tự đang mã hoá sẽ cung cấp
cho chúng ta một hiểu biết tốt hơn nhiều về giá trị của kí tự đang mã hoá. Nếu chúng ta
biết được ngữ cảnh trong đó một kí tự xảy ra chúng ta có thể đoán với khả năng thành
công lớn hơn nhiều so với giá trị của kí tự. Nói cách khác, trong ngữ cảnh cho trước,
một số kí tự xảy ra với xác suất lớn hơn nhiều những chữ khác. Có nghĩa là, sự phân bố
xác suất trong ngữ cảnh cụ thể sẽ lệch hơn. Nếu ngữ cảnh được biết ở cả hai bộ mã hoá
và giải mã, thì chúng ta có thể sử dụng sự phân bố lệch này để thực hiện mã hoá, vì vậy
sẽ tăng mức nén. Bộ giải mã có thể sử dụng những hiểu biết về ngữ cảnh của nó để xác
định sự phân bố được sử dụng để giải mã. Nếu chúng ta có thể bằng cách nào đó nhóm
những ngữ cảnh giống nhau với nhau, thì rất có thể là những kí tự theo sau những ngữ
cảnh này sẽ giống nhau, cho phép sử dụng chiến lược nén đơn giản và hiệu quả. Chúng
ta có thể nhận thấy ngữ cảnh đóng vai trò quan trọng trong việc nâng cao hiệu quả nén.
Xem xét việc mã hoá từ “probability”. Giả sử chúng ta đã mã hoá bốn chữ cái đầu
tiên và muốn mã hoá chữ cái thứ năm , “ a”. Nếu chúng ta bỏ qua bốn chữ cái đầu tiên,
xác suất của “a” là 0.06. Nếu chúng ta sử dụng thông tin về chữ cái trước nó là “b”, thì
sẽ làm giảm xác suất của vài kí tự giống như là q và z và tăng xác suất xảy ra của “a”.
Trong ví dụ này, “ b” sẽ là ngữ cảnh bậc nhất đối với “a”, “ob” là ngữ cảnh bậc hai đối