# data[].attributes.body
Trong thuật toán xử lý chuỗi nén tập tin, mục tiêu chính là giảm dung lượng của tập tin thông qua việc áp dụng các phương pháp nén để lưu trữ dữ liệu một cách hiệu quả mà vẫn có thể khôi phục lại dữ liệu gốc mà không mất thông tin.

1) Phân loại nén tập tin

a)Nén không mất mát (Lossless Compression):

+LZW (Lempel-Ziv-Welch): Là một thuật toán nén không mất mát đượcsử dụng chủ yếu cho văn bản và hình ảnh có thể lặp lại. Nó hoạt độngbằng cách xây dựng một bảng từ điển từ các chuỗi ký tự lặp lại trong dữ liệu và thay thế chúng bằng các mã viết tắt trong quá trình nén. Khi giải nén, bảng từ điển này được sử dụng để khôi phục dữ liệu ban đầu.

+Huffman Coding: Đây là một thuật toán nén không mất mát dựa trên việc sắp xếp các ký tự hoặc cụm ký tự theo tần suất xuất hiện trong dữ liệu. Các ký tự phổ biến được mã hóa bằng các mã ngắn hơn, trong khi các ký tự ít phổ biến hơn sẽ được mã hóa bằng các mã dài hơn. Khi giải nén, dữ liệu được phục hồi dựa trên bảng mã Huffman.

+ZIP: ZIP là một định dạng nén phổ biến sử dụng thuật toán nén không mất mát để giảm kích thước của tập tin. Nó thường kết hợp cả hai phương pháp LZW và Huffman Coding cùng các kỹ thuật khác nhau để tối ưu hóa việc nén tập tin.

b)Nén mất mát (Lossy Compression):

+JPEG (Joint Photographic Experts Group): JPEG là định dạng nén mất mát thường được sử dụng cho hình ảnh số. Thuật toán này loại bỏ thông tin không cần thiết từ hình ảnh để giảm kích thước tập tin. Nó áp dụng việc chia hình ảnh thành các khối, sau đó sử dụng các phép

biến đổi và các kỹ thuật lượng tử hóa để giảm chi tiết trong hình ảnh.

+MP3 (MPEG Audio Layer III): MP3 là một định dạng nén âm thanh mất mát. Nó loại bỏ dữ liệu không nghe thấy được trong âm thanh để giảm kích thước tập tin mà vẫn giữ được chất lượng âm thanh tương đối tốt. Thuật toán này sử dụng mã hóa dựa trên các thuật toán nén âm thanh psychoacoustic để loại bỏ thông tin không cần thiết mà không gây ra sự thay đổi rõ rệt đối với tai người nghe.

c)Các Thuật Toán Nén Tập Tin:

1. Nén không mất mát (Lossless Compression): Các thuật toán nén này giữ nguyên dữ liệu gốc khi giải nén, đảm bảo không mất mát thông tin. Ví dụ như thuật toán LZW (Lempel-Ziv-Welch), Huffman, và ZIP.

2. Nén mất mát (Lossy Compression): Loại nén này giúp giảm kích thước tập tin bằng cách loại bỏ một số thông tin không cần thiết, thường dẫn đến mất mát một phần nào đó của dữ liệu. Ví dụ như các định dạng nén hình ảnh như JPEG, nén video như MP4 hoặc nén âm thanh như MP3.

d)Ví Dụ Với Thuật Toán Nén Không Mất Mát(thuật toán nén ZIP) :

A.Thuật Toán:

1. Khởi tạo: Bắt đầu bằng việc mở xle nguồn cần nén và xle đích để lưu trữ dữ liệu đã được nén.

2. Đọc và Nén: Đọc dữ liệu từ xle nguồn theo từng phần (chunk) và áp dụng thuật toán nén ZIP để giảm kích thước dữ liệu. Thuật toán nén ZIP thực hiện việc nén bằng cách sử dụng các kỹ thuật như mã hóa từ điển hoặc mã hóa Huffman để mã hóa dữ liệu thành dạng nén.

3. Ghi Dữ Liệu Nén: Ghi dữ liệu đã nén vào xle đích, và tiếp tục quá trình nén cho đến khi toàn bộ dữ liệu được xử lý.

4. Kết thúc nén và Đóng xle: Khi toàn bộ dữ liệu đã được nén, kết thúc quá trình nén và đóng cả xle nguồn và xle đích.

5. Giai đoạn Giải nén: Để giải nén dữ liệu, quá trình tương tự sẽ được áp dụng ngược lại. Đọc dữ liệu từ xle đã nén, giải nén dữ liệu và ghi vào xle khôi phục.

B. Chương Trình:

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <zlib.h>

#dexne CHUNK 16384 // Kích thước chunk khi đọc xle

int main() {

FILE source_xle, dest_xle;

int ret;

z_stream stream;

unsigned char in[CHUNK];

unsigned char out[CHUNK];

const char source_xlename = "xle_to_compress.txt";

const char dest_xlename = "compressed_xle.zip"; // Tên xle sau khi nén

// Mở xle nguồn

source_xle = fopen(source_xlename, "rb"); if (!source_xle) {

perror("Không thể mở xle nguồn");

return EXIT_FAILURE;

}//

Mở xle đích

dest_xle = fopen(dest_xlename, "wb");

if (!dest_xle) {

perror("Không thể mở xle đích");

return EXIT_FAILURE;

}//

Khởi tạo cấu trúc nén zlib memset(&stream, 0, sizeof(stream));

ret = deyateInit(&stream, Z_DEFAULT_COMPRESSION);

if (ret != Z_OK) {

perror("Không thể khởi tạo zlib");

return EXIT_FAILURE;

}//

Đọc dữ liệu từ xle nguồn, nén và ghi vào xle đích

do {

stream.avail_in = fread(in, 1, CHUNK, source_xle);

if (ferror(source_xle)) { deyateEnd(&stream);

perror("Lỗi khi đọc xle nguồn");

return EXIT_FAILURE;

}if

(stream.avail_in == 0)

break;

stream.next_in = in;

do {

stream.avail_out = CHUNK; stream.next_out = out;

ret = deyate(&stream, Z_FINISH);

if (ret == Z_STREAM_ERROR) {

perror("Lỗi khi nén dữ liệu"); deyateEnd(&stream);

return EXIT_FAILURE;

}in

t have = CHUNK - stream.avail_out;

if (fwrite(out, 1, have, dest_xle) != have || ferror(dest_xle)) {

deyateEnd(&stream);Trần Minh Nhật

perror("Lỗi khi ghi vào xle đích");

return EXIT_FAILURE;

}}

while (stream.avail_out == 0);

} while (ret != Z_STREAM_END);

// Kết thúc nén, đóng xle và giải phóng bộ nhớ

deyateEnd(&stream);

fclose(source_xle);

fclose(dest_xle);

return EXIT_SUCCESS;

}

# data[].attributes.body
THUẬT TOÁN BRUTE FORCE

Input: chuỗi a, chuỗi b.

Output: vị trí xuất hiện b trong a.

Mô tả thuật toán:

- n, m lần lượt là độ dài chuỗi a và b.

- Đi từ đầu đến ký tự thứ n-m của a, trong quá trình đi thì so sánh từng ký tự của b trong a nếu có ký tự của b không khớp với a thì chuyển sang ký tự tiếp theo của a.

- Nếu b có trong a thì return vị trí xuất hiện đầu tiên trong a.

- Ngược lại return 0.

Minh họa thuật toán: hình ảnh trên

Cài đặt thuật toán:

int BruteForce(char a[], char b[])

{

    int n, m, i, j;

    n = strlen(a);

    m = strlen(b);

    for (i = 0; i <= n - m; i++)

    {

        for (j = 0; j < m; j++)

            if (a[i + j] != b[j])

                break;

        if (j == m)

            return i+1;

    }

    return 0;

}

# data[].attributes.body
Input: chuỗi A, chuỗi mẫu p

Output: số lần trùng của chuỗi mẫu p trong A

Mô tả thuật toán:

-M là độ dài chuỗi mẫu p.N là độ dài chuỗi A. Cho biến 'dem'=0

-Duyệt qua từng phần tử chuỗi A

-So sánh kí tự tại vị trí i trong chuỗi A, với kí tự tại vị trí j trong chuỗi mẫu p.

-Nếu kí tự khớp, tăng giá trị của j và kiểm tra j có bằng với độ dài của mẫu p hay không,nếu bằng tức là đã tìm thấy một chuỗi khớp hoàn toàn trong chuỗi A, tăng biến đếm lên 1 lần và đặt j về 0 để so sánh mẫu lại từ đầu .

-Nếu không khớp điều chỉnh lại biến i và đặt j về 0 để so sánh mẫu lại từ đầu

-Khi duyệt hết chuỗi văn bản A ta trả về biến đếm.

Minh hoạ thuật toán:Hình trên

Cài đặt thuật toán:

int brutesearch(char p, char A) {

int i, j, M = strlen(p), N = strlen(A),dem=0;

for (i = 0, j = 0; i < N; i++) {

if (a[i] == p[j]) {

j++;

if (j == M) {

dem++;

j=0;

}

} else {

i -= j;

j = 0;

}

}

return dem;

}

# data[].attributes.body
Xử lý chuỗi trong Cấu trúc dữ liệu và giải thuật thường đòi hỏi sự sáng tạo và kiến thức vững về mật mã học. Thuật toán mật mã là một loại các bước hoặc quy tắc được thiết kế để bảo vệ thông tin khỏi sự truy cập trái phép hoặc thay đổi. Thuật toán mật mã là một bộ quy tắc hoặc quy trình được sử dụng để mã hóa hoặc giải mã thông tin. Các thuật toán này đóng vai trò quan trọng trong việc đảm bảo tính bảo mật của thông tin khi truyền tải qua mạng hoặc lưu trữ trong các hệ thống.

A. Một số thuật toán mật mã phổ biến:

I.AES (Advanced Encryption Standard):

-Mô tả: AES là một thuật toán mã hóa simetric, được sử dụng rộng rãi trên thế giới. Nó có khả năng mã hóa và giải mã dữ liệu bằng cách sử dụng cùng một khóa, và có các chế độ hoạt động như ECB, CBC, và GCM.

-Cách hoạt động: AES sử dụng một khóa để mã hóa và giải mã dữ liệu theo cách xử lý trên từng khối dữ liệu.

II.AES-GCM (Advanced Encryption Standard - Galois/Counter Mode):

Mục đích: Một biến thể của AES, AES-GCM thường được sử dụng để cung cấp cả mã hóa và xác thực cho dữ liệu.

Cách hoạt động: Nó kết hợp việc mã hóa AES với một chế độ xác thực được xây dựng trên cơ sở Galois Counter Mode (GCM) để đảm bảo tính toàn vẹn của dữ liệu.

III.RSA (Rivest-Shamir-Adleman):

-Mô tả: RSA là một thuật toán mã hóa không simetric sử dụng cặp khóa công khai và khóa riêng tư. Dữ liệu được mã hóa bằng khóa công khai và chỉ có thể được giải mã bằng khóa riêng tư và ngược lại.

-Cách hoạt động: RSA sử dụng cặp khóa (khóa công khai và khóa bí mật) để mã hóa và giải mã dữ liệu. Khóa công khai có thể được chia sẻ công khai, trong khi khóa bí mật được giữ bí mật.

IV.DES (Data Encryption Standard):

-Mô tả: DES là một thuật toán mã hóa simetric được phát triển bởi IBM. Tuy nhiên, do các vấn đề về an ninh, DES đã được thay thế bằng AES trong nhiều ứng dụng.

-Cách hoạt động: DES sử dụng một khóa để mã hóa và giải mã dữ liệu theo cách xử lý trên từng khối dữ liệu.

V.3DES (Triple DES):

-Mô tả: 3DES là một biến thể của DES, nó sử dụng ba vòng mã hóa để tăng cường tính bảo mật. Tuy nhiên, do độ dài khóa ngắn, nó không được khuyến nghị cho các ứng dụng mới.

-Cách hoạt động:Tương tự DES là sử dụng một khóa để mã hóa và giải mã dữ liệu theo cách xử lý trên từng khối dữ liệu.

VI.Blowfish:

-Mô tả: Blowfish là một thuật toán mã hóa simetric được thiết kế để thay thế DES. Nó nhanh, an toàn, và có khóa có thể được thiết lập lên đến 448 bit.

-Cách hoạt động:

Khởi tạo: Blowfish sử dụng một bảng con trỏ có kích thước lớn để lưu trữ các giá trị hằng số và s-boxes (hộp S). Ban đầu, nó sẽ được khởi tạo bằng cách sử dụng giá trị PI (số PI đến từ các số trong dãy số π) và các khối dữ liệu được đưa vào từ khóa.

Phân rã khóa: Blowfish chia khóa thành các khối con để sử dụng trong việc mở rộng bảng con trỏ.

Mã hóa dữ liệu: Dữ liệu đầu vào được chia thành các khối cố định (ví dụ: 64 bit). Blowfish sau đó áp dụng một số vòng lặp mã hóa cho mỗi khối.

Vòng lặp mã hóa: Blowfish sử dụng F-function (hàm F) trong mỗi vòng lặp mã hóa. Hàm F thực hiện một số phép toán, bao gồm các phép toán XOR, AND, OR, modulo, và các phép toán trên các hộp S (s-boxes). Các giá trị được lấy từ bảng con trỏ sẽ thay thế các giá trị trong khối dữ liệu.

Phản hồi chuỗi (Feedback Loop): Blowfish sử dụng phản hồi chuỗi (feedback loop) từ khối trước để ảnh hưởng đến khối tiếp theo trong quá trình mã hóa.

Giải mã: Quá trình giải mã tương tự như quá trình mã hóa, nhưng ngược lại. Blowfish sử dụng các khối con của khóa đã phân rã để ngược lại quá trình mã hóa và trả lại dữ liệu gốc.

VII.ECC (Elliptic Curve Cryptography):

-Mô tả: ECC sử dụng các đường cong elliptic trong trường hữu hạn để tạo ra các cặp khóa. Nó cung cấp mức độ bảo mật cao với khóa ngắn hơn so với các thuật toán không simetric truyền thống.

Cách hoạt động:1.Lựa chọn đường cong elip (Elliptic Curve),2.Chọn điểm cơ sở (Base Point) trên đường cong elip,3.Phép toán cộng điểm (Point Addition),4.Phép toán nhân điểm (Point Multiplication),5.Tạo khóa công khai và khóa bí mật

VIII.Hash Functions (ví dụ: SHA-256, MD5):

-Mô tả: Hash functions không dùng khóa và chủ yếu được sử dụng để tạo ra một "bản tóm tắt" độ dài cố định cho một lượng dữ liệu, giúp kiểm tra tính toàn vẹn của dữ liệu.

-Cách hoạt động: SHA-256 chuyển đổi một đoạn dữ liệu thành một giá trị băm có độ dài cố định (256-bit). Nó được sử dụng rộng rãi để kiểm tra tính toàn vẹn của dữ liệu và tạo chữ ký số.

=> Mỗi thuật toán có những ưu điểm và hạn chế riêng, và sự lựa chọn phụ thuộc vào ngữ cảnh cụ thể của ứng dụng và mức độ bảo mật yêu cầu.

B. Mô tả bằng code của một số thuật toán

#include <stdio.h>

void ma_hoa_chuoi_mo_ta(char chuoi[], int khoa)

{

for (int i = 0; chuoi[i] != '\0'; ++i)

{

chuoi[i] = chuoi[i] + khoa;

}

}

void giai_ma_chuoi_mo_ta(char chuoi[], int khoa)

{

for (int i = 0; chuoi[i] != '\0'; ++i)

{

chuoi[i] = chuoi[i] - khoa;

}

}

main()

{

char chuoi_goc[1000];

printf("Nhap chuoi can ma hoa: ");

gets(chuoi_goc);

int khoa = 3;

ma_hoa_chuoi_mo_ta(chuoi_goc, khoa);

printf("Chuoi da ma hoa: %s\n", chuoi_goc);

char chuoi_ma_hoa[1000];

printf("Nhap ma can giai ma: ");

gets(chuoi_ma_hoa);

giai_ma_chuoi_mo_ta(chuoi_ma_hoa, khoa);

printf("Chuoi da giai ma: %s\n", chuoi_ma_hoa);

}

# data[].attributes.body
Phân tích câu trong chuỗi là quá trình tách một chuỗi văn bản thành các thành phần cấu trúc, chủ yếu là các câu. Điều này có thể hữu ích trong nhiều ứng dụng, chẳng hạn như xử lý ngôn ngữ tự nhiên (NLP), trích xuất thông tin, và phân tích văn bản. Dưới đây là một số phương pháp và khái niệm liên quan đến phân tích câu:

1. Phân đoạn (Sentence Segmentation): Quá trình phân tách văn bản thành các câu. Các câu thường được kết thúc bởi dấu chấm, dấu chấm phẩy, hoặc dấu chấm than, nhưng có những trường hợp đặc biệt cần xem xét.

2. Dựa trên dấu câu: Một phương pháp đơn giản nhưng hiệu quả là sử dụng các dấu câu (., !, ?) để xác định điểm kết thúc của mỗi câu. Tuy nhiên, điều này có thể phức tạp hơn do có nhiều trường hợp đặc biệt như viết tắt, từ viết tắt, hay sử dụng dấu chấm trong các viết tắt.

Hàm strtok trong C được sử dụng để phân tách một chuỗi thành các phần (token) dựa trên một ký tự phân cách (delimiter). Thông thường, hàm này được sử dụng trong việc phân tích câu trong một chuỗi văn bản thành các câu riêng biệt.

Hàm strtok trả về một con trỏ đến token đầu tiên trong chuỗi str. Nếu không tìm thấy token nào, nó trả về NULL. Các lần gọi tiếp theo của strtok sẽ trả về các token tiếp theo trong chuỗi, cho đến khi không còn token nào hoặc khi bạn gọi hàm với NULL.

Ví dụ về hàm strtok được sử dụng để phân tích câu:

#include <stdio.h>

#include <string.h>

main() {

char sentence[] = "This is the first sentence. This is the second sentence; And here is the third sentence!";

char *token;

int i = 1;

token = strtok(sentence, " .;!"); //" .&!");

while (token != NULL) {

printf("Cau %d: %s\n", i, token);

token = strtok(NULL, " .;!"); //" .&!");

i++;

}

}