Chương 1:
Các thuật toán trên chuỗi
GV: TRẦN HỮU QUỐC THƯ
1.3 Thuật toán nén chuỗi
GV: TRẦN HỮU QUỐC THƯ
+ Trong thực tế khi biểu diễn thông tin là van bản thì
máy tính thường dùng bộ mã ASCII, Unicode, … đây
là các bộ mã mà độ dài dãy bít dành cho ký tự luôn là
cố định
+ Tối ưu hoá dãy bít biểu diễn chuỗi => cho phép các
dãy bít biểu diễn các ký tự là không bằng nhau về
chiều dài
- Làm giảm đáng kể số lượng bit biểu diễn cho
cả chuỗi
- Nhưng làm nảy sinh sự nhập
nhằng khi giải mã
1.3Thuật toán nén chuỗi
GV: TRẦN HỮU QUỐC THƯ
Ví dụ: với chuỗi: “This is a book”
Ký tự Dãy bit Ký tự Dãy bit
T 0 I 00
H 01 S 10
T H I S

0 01 00 10
0 0 10 0 10

T T S T S
0 0 10 01 0

T T S H S

e
e
6
6
4
4
10
10
Trái mã bit 0
Phải mã bit 1
0 1
0
0
0
1
1
1
K.tự
Dãy
bit
o 00
u 01
a 100
e 101
i 11
Chương 2:
Bảng băm
(Hashing Table)
GV: TRẦN HỮU QUỐC THƯ
2.1. Giới thiệu về bảng băm

- Hiển nhiên phần tử được “băm” đầu tiên sẽ
chiếm lĩnh vị trí đó, các phần tử sau cần phải
được lưu vào các vị trí trống khác sao cho vấn đề
truy xuất và tìm kiếm phải dễ dàng
a. Làm giảm xung đột
GV: TRẦN HỮU QUỐC THƯ
-
Hàm băm cần được sao cho:
-
Xác xuất phân bố khoá là đều nhau
-
Dễ dàng tính toán thao tác
Thông thường, hàm băm sử dụng các số nguyên
tố (vì xác suất ngẫu nhiên phân bố các số nguyên
tố là đều nhất
b. Giải quyết xung đột
GV: TRẦN HỮU QUỐC THƯ
i. Sử dụng danh sách liên kết (nối kết)
GV: TRẦN HỮU QUỐC THƯ
-
Ý tưởng:”Các phần tử băm vào trùng vị trí được
nối vào DS nối kết” tại vị trí đó
0 1 2 3 4
21 18
Hàm băm:
F(k) = k mod 5
Thêm
6, 16
6
16

i. Danh sách liên kết
GV: TRẦN HỮU QUỐC THƯ
- Sử dụng DSLK tại mỗi vị trí lưu trữ
- Nếu xảy ra xung đột thì lưu vào cuối DS
tại vị trí trùng
A B C D E F X Y Z
1 2 3 4 5 6 24 25 26
i. Danh sách liên kết
GV: TRẦN HỮU QUỐC THƯ
A SEARCHING EXAMPLE
0 1 2 3 4 5 6 7 8 9
1
0
* * * * * * * * * * *
A
A
C
E
R
S
H
code
GV: TRẦN HỮU QUỐC THƯ
const int M = 101; //Kich thuoc bảng băm
LINKLIST HashTable[M]; //bảng băm
Khởi tạo bảng băm
GV: TRẦN HỮU QUỐC THƯ
void Init_HashTable()
{
for (int i = 0 ; i< M; ++ i)