# data[].attributes.body
IV.        Nén tập tin

1.    Trình bày thuật toán.

- Duyệt từng ký tự, đếm số lần xuất hiện liên tiếp của ký tự đó.

- Tạo cây HUFFMAN:

+Tạo nút lá cho từng ký tự với tần suất tương ứng.

+Đưa các nút vào hàng đợi ưu tiên, sắp xếp theo tần suất tăng dần.

+Lặp lại cho đến khi chỉ còn 1 nút trong hàng đợi:

∙ Lấy ra 2 nút có tần suất thấp nhất.

∙ Tạo nút mới:

Tần suất = tổng của 2 nút con.

Nút trái và phải = 2 nút vừa lấy.

∙ Đưa nút mới vào lại hàng đợi.

→ Nút cuối cùng còn lại là gốc cây Huffman.

- Duyệt cây Huffman khi đi qua trái thêm 0, qua phải thêm 1.

- Thay các kí tự trong chuỗi thành mã nhị phân.

2.    Minh họa thuật toán.

Chuoi

AAAABBCD

[D(1) C(1) B(2) A(4)]

[CD(2) B(2) A(4)]

CD(2)

/       \

C(1)    D(1)

[BCD(4) A(4)]

BCD(4)

/       \

B(2)     CD(2)

/    \

C(1)     D(1)

[ABCD(8)]

Root(8)

/         \

A(4)       BCD(4)

/         \

B(2)     CD(2)

/     \

C(1)    D(1)

A:0

B:10

C:110

D:111

Chuoi sau khi nen:

00001010110111

# data[].attributes.body
I. Tìm kiếm chuỗi

1. Trình bày thuật toán: Duyệt tuần tự (Brute-Force Search)

Tìm kiếm vị trí xuất hiện đầu tiên của một chuỗi con trong một chuỗi mẹ.

+Duyệt chuỗi mẹ từ đầu đến cuối, tại mỗi vị trí kiểm tra xem có sự khớp hoàn toàn với chuỗi con hay không.

+Nếu có sự khớp, trả về vị trí đó.

+Nếu không tìm thấy chuỗi con, trả về -1.

2. Minh họa thuật toán:

Chuỗi 1: hoclaptrinh

Chuỗi 2: lap

Quá trình so sánh

i = 0 “hoc” ≠ “lap”

i = 1 “ocl” ≠ “lap”

i = 2 “cla” ≠ “lap”

i = 3 “lap” = “lap”

Trả về i=3

# data[].attributes.body
III. Sắp xếp bằng trộn

1. Trình bày thuật toán.

- Nếu danh sách có 1 phần tử hoặc rỗng, nó đã được sắp xếp, trả về ngay.

- Nếu danh sách có nhiều hơn 1 phần tử:

Tìm điểm giữa của danh sách để chia thành hai nửa: nửa trái và nửa phải.

Gọi đệ quy thuật toán Merge Sort cho nửa trái.

Gọi đệ quy thuật toán Merge Sort cho nửa phải.

Gộp hai nửa đã sắp xếp thành một danh sách hoàn chỉnh.

- Sau đó so sánh các phần tử của hai nửa đã sắp xếp.

Chọn phần tử nhỏ hơn từ hai nửa, thêm vào danh sách kết quả.

Tiếp tục quá trình này cho đến khi tất cả phần tử từ cả hai nửa được đưa vào danh sách kết quả.

2. Minh họa thuật toán

Dãy số: 38, 27, 43, 3, 9, 82, 10

Chia

38, 27, 43, 3, 9, 82, 10

/            \

38, 27, 43              3, 9, 82, 10

/      \                  /        \

38  27, 43         3, 9    82, 10

/   \            /   \      /    \

27  43       3  9  82  10

Gộp

38, 27, 43, 3, 9, 82, 10

/ \

38, 27, 43 3, 9, 82, 10

/ \ / \

38 27, 43 3, 9 82, 10

/ \ / \ / \

27 43 3 9 82 10

\ / \ / \ /

27, 43 3, 9 10, 82

\ / /

27, 38, 43 3, 9, 10, 82

\ /

3, 9, 10, 27, 38, 43, 82

Danh sách sau khi sắp xếp: 3, 9, 10, 27, 38, 43, 82