# data[].attributes.body
Thuật toán đối sánh mẫu là một thuật toán trong khoa học máy tính được sử dụng để tìm kiếm một chuỗi con trong một chuỗi lớn hơn. Có nhiều thuật toán đối sánh mẫu khác nhau, bao gồm thuật toán Brute Force, thuật toán Knuth-Morris-Pratt, thuật toán Boyer-Moore và thuật toán Rabin-Karp 123. Mỗi thuật toán có ưu điểm và hạn chế riêng, và được sử dụng trong các trường hợp khác nhau tùy thuộc vào yêu cầu của bài toán.

# data[].attributes.body
Thuật toán KMP sẽ tính toán một mảng LPS (Longest Proper Prefix which is also Suffix) để lưu trữ thông tin về độ dài của chuỗi con dài nhất mà là đồng thời tiền tố và hậu tố của một vị trí trong mẫu.

Sau đó, thuật toán sẽ duyệt qua chuỗi với hai con trỏ i và j, trong đó i là con trỏ cho chuỗi lớn hơn và j là con trỏ cho mẫu.

Nếu các ký tự tại vị trí i và j khớp nhau, con trỏ i và j sẽ tăng lên một đơn vị.

Nếu j đạt đến cuối mẫu, tức là tìm thấy một chuỗi con khớp, thuật toán sẽ in ra vị trí xuất hiện của chuỗi con đó trong chuỗi lớn hơn và cập nhật con trỏ j bằng giá trị tương ứng trong mảng LPS.

Nếu các ký tự tại vị trí i và j không khớp nhau, thuật toán sẽ di chuyển con trỏ j dựa trên giá trị trong mảng LPS.

# data[].attributes.body
Với thuật toán tìm kiếm chuỗi, mình đã đưa ra 2 phương án, một là tìm kiếm chuỗi dựa trên vị trí của chuỗi trong mảng, và tìm kiếm chuỗi dựa trên kí tự của chuỗi con tương ứng với chuỗi mẹ.

Với tìm kiếm dựa trên vị trí trong mảng, mình sử dụng 2 vòng lặp lồng nhau, chạy song song để tìm kiếm vị trí của chuỗi con trong chuỗi mẹ.

Với tìm kiếm dựa trên sự tương đương của chuỗi con trong chuỗi mẹ, mình sử dụng hàm tìm kiếm chuỗi thuộc thư viện string.h.

# data[].attributes.body
#include <stdio.h>

#include <string.h>

//Nguyen Quoc Cuong

//22115053122308

//Ham nhap chuoi

void NhapChuoi(char String1, char String2)

{

fflush (stdin);

printf("Nhap vao chuoi chinh: ");

gets(String1);

printf("Nhap vao chuoi can tim: ");

gets(String2);

}

//Ham tim kiem tra ve vi tri cua chuoi ( chi can giong ki tu dau cua chuoi )

int TimKiemChuoi1(char Chuoi, char ChuoiCanTim)

{

int a = strlen(Chuoi);

int b = strlen(ChuoiCanTim);

int i, j;

if (b > a)

return -1;

for (i = 0; i <= a - b; i++)

{

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

{

if (Chuoi[i + j] == ChuoiCanTim[j])

j++;

else

break;

}

if (j == b)

return i+1;

}

return -1;

}

//Ham nay dung de kiem tra 1 chuoi doc lap (tranh truong hop trung ki tu nhung khong trung toan bo chuoi)

int KiemTraChuoi(char *String, int a, int b)

{

for (int i = a; i <= b; i++)

{

if (String[i] ' ' || i == b)

return 1;

}

return 0;

}

//Ham tra ve ket qua co/khong ( bat buoc giong hoan toan cac ki tu trong chuoi )

int TimKiemChuoi2(char Chuoi, char ChuoiCanTim)

{

char *KetQua = strstr(Chuoi, ChuoiCanTim);

while (KetQua != NULL) {

int a = KetQua - Chuoi;

int b = a + strlen(ChuoiCanTim) - 1;

if (KiemTraChuoi(Chuoi, a, b))

return 1;

KetQua = strstr(KetQua + 1, ChuoiCanTim);

}

return 0;

}

main()

{

char Chuoi[100];

char ChuoiCanTim[100];

NhapChuoi(Chuoi, ChuoiCanTim);

printf("\n");

int KetQua1 = TimKiemChuoi1(Chuoi, ChuoiCanTim);

int KetQua2 = TimKiemChuoi2(Chuoi, ChuoiCanTim);

if (KetQua1 != -1)

printf("Chuoi can tim xuat hien tai vi tri %d.\n", KetQua1);

else

printf("Khong tim thay chuoi can tim.\n");

if (KetQua2 == 1)

printf("Chuoi can tim xuat hien trong chuoi chinh.");

else

printf("Khong tim thay chuoi can tim.");

}

# data[].attributes.body
Định Nghĩa

Nén dữ liệu là phương pháp loại bỏ những thông tin dư thừa trong việc biểu diễn dữ liệu. Nó có nhiều ứng dụng, đặc biệt là trong việc truyền tin vì giúp rút gọn thông tin gửi đi

-Có 2 loại thuật toán nén dư liệu đó là thuật toán nén không mất mát và thuật toán nén mất

-Trong đó thuật toán nén không mất mát là các thuật toán nén không mất mát có thể xây dựng lại chính xác dữ liệu gốc từ dữ liệu nén. Nhiều thuật toán khác nhau được thiết kế với một loại dữ liệu đầu vào điển hình hoặc bằng cách giả sử về loại dự phòng mà dữ liệu không nén có thể chứa. Sau đây là một lời giải thích ngắn gọn về một số thuật toán nén không mất mát được sử dụng rộng rãi nhất:

-BZIP2

-Huffman mã hóa

-Lempel-Ziv nén

-Mã hóa độ dài chạy (RLE)

-Thuật toán nén mất

Các thuật toán nén mất là một bước đi trước để giảm kích thước lưu trữ của các tệp. Trong khi đó, mất một số thông tin được chấp nhận là bỏ chi tiết không cần thiết.

-Biến đổi cosine rời rạc (DCT)

-Nén sóng con

-Nén nhận thức Cartesian (CPC)

-Nén fractal

# data[].attributes.body
Thuật toán nén tập tin trong lập trình C thường sử dụng các kỹ thuật nén dữ liệu để giảm dung lượng của tập tin mà vẫn giữ được thông tin gốc. Một trong những thuật toán nén phổ biến là thuật toán nén Huffman.

Thuật toán nén Huffman là một phương pháp nén không mất dữ liệu, nó dựa trên việc sử dụng mã hóa độ dài biến đổi cho các ký tự khác nhau dựa trên tần suất xuất hiện của chúng. Ý tưởng cơ bản là sử dụng ít bit hơn để biểu diễn các ký tự thường xuất hiện nhiều trong tập tin.

Cách thức hoạt động cơ bản của thuật toán Huffman như sau:

Bước 1: Đếm tần suất xuất hiện của các phần tử trong chuỗi đầu vào.

Bước 2: Xây dựng cây Huffman (cây nhị phân mã hóa).

2.1. Tạo danh sách chứa các nút lá bao gồm phần tử đầu vào và trọng số nút là tần suất xuất hiện của nó.

2.2. Từ danh sách này, lấy ra 2 phần tử có tần suất xuất hiện ít nhất. Sau đó gắn 2 nút vừa lấy ra vào một nút gốc mới với trọng số là tổng của 2 trọng số ở nút vừa lấy ra để tạo thành một cây.

2.3. Đẩy cây mới vào lại danh sách.

2.4. Lặp lại bước 2 và 3 cho đến khi danh sách chỉ còn 1 nút gốc duy nhất của cây.

2.5. Nút còn lại chính là nút gốc của cây Huffman.

Bước 3: Từ cây Huffman, ta có được các giá trị mã hóa. Lúc này, ta có thể xây dựng chuỗi mã hóa từ các giá trị này.

# data[].attributes.body
//Phan Anh Duy 22T3

//22115053122313

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

void tinhMangLPS(char pat[], int M, int lps[])

{

int len = 0;

int i = 1;

lps[0] = 0;

while (i < M)

{

if (pat[i] == pat[len])

{

len++;

lps[i] = len;

i++;

}

else

if (len != 0)

len = lps[len - 1];

else

{

lps[i] = 0;

i++;

}

}

}

void KMP(char txt[], char pat[])

{

int M = strlen(pat);

int N = strlen(txt);

int lps[M];

tinhMangLPS(pat, M, lps);

int i = 0; // index for txt[]

int j = 0; // index for pat[]

while (i < N)

{

if (pat[j] == txt[i])

{

j++;

i++;

}

if (j == M)

{

printf("Tim thay mang con o vi tri: %d\n", i - j);

j = lps[j - 1];

}

else if (i < N && pat[j] != txt[i])

if (j != 0)

j = lps[j - 1];

else

i = i + 1;

}

}

void NhapTXT(char txt[])

{

fflush(stdin);

printf("Nhap mang me: ");

gets(txt);

}

void NhapBTXT(char btxt[])

{

fflush(stdin);

printf("Nhap mang con: ");

gets(btxt);

}

main()

{

char txt[100], btxt[100];

NhapTXT(txt);

NhapBTXT(btxt);

KMP(txt, btxt);

}

# data[].attributes.body
Các thuật toán phân tích câu là các thuật toán xử lý chuỗi, được sử dụng để xác định cấu trúc ngữ pháp và ngữ nghĩa của một câu. Các thuật toán này có thể sử dụng các văn phạm, các quy tắc hoặc các mô hình học máy để xác định các thành phần và mối quan hệ của chúng trong câu. Một số ứng dụng của các thuật toán phân tích câu là: phân tích cú pháp, phân tích ngữ nghĩa, dịch máy, trả lời câu hỏi, tóm tắt văn bản, v.v.

-        Thuật toán phân tích câu trong xử lý chuỗi có thể sử dụng các phương pháp như phân tích ngữ pháp, phân tích cú pháp và phân tích ngữ nghĩa.

+ Phân tích ngữ pháp giúp xác định các thành phần cú pháp của câu như danh từ, động từ, tính từ, trạng từ, v.v.

+Phân tích cú pháp giúp xác định cấu trúc câu và mối quan hệ giữa các thành phần câu. Phân tích ngữ nghĩa giúp hiểu ý nghĩa của câu và các từ trong câu. Có nhiều thuật toán phân tích câu được sử dụng trong xử lý chuỗi, bao gồm thuật toán Earley và các phương pháp dựa trên quy tắc hoặc học máy. Tuy nhiên, việc phân tích câu là một lĩnh vực phức tạp và đang được nghiên cứu và phát triển liên tục.

Một số thuật toán phân tích câu nổi tiếng là:

Thuật toán Earley: Một thuật toán phân tích cú pháp kiểu trên xuống, có thể phân tích cú pháp các ngôn ngữ thuộc lớp LR(k)¹.

Thuật toán CYK: Một thuật toán phân tích cú pháp kiểu dưới lên, chỉ có thể phân tích cú pháp các ngôn ngữ được xác định bởi các văn phạm Chomsky dạng chuẩn ².

Thuật toán LR: Một thuật toán phân tích cú pháp kiểu dưới lên, có thể phân tích cú pháp các ngôn ngữ thuộc lớp LR(k), thường được sử dụng trong các trình phân tích cú pháp của các ngôn ngữ lập trình³.

Thuật toán RNN: Một thuật toán phân tích cú pháp dựa trên mạng nơ-ron hồi quy, có thể học được các cấu trúc và ý nghĩa của các câu từ các dữ liệu huấn luyện⁴.

Thuật toán BERT: Một thuật toán phân tích cú pháp dựa trên mô hình biểu diễn ngôn ngữ

# data[].attributes.body
một phiên bản đơn giản của thuật toán phân tích câu là Tokenization.

Tokenization (Phân đoạn): Quá trình chia một câu thành các đơn vị nhỏ hơn gọi là "token", chẳng hạn như từ, ký tự, hoặc cụm từ. Tokenization giúp phân tách và chuẩn hóa văn bản để dễ dàng xử lý tiếp theo.

//code

//T.Thảo-22115053122342

#include <stdio.h>

#include <string.h>

void phantichcau(char cau[]) {

char *token;

token = strtok(cau, " ");

while (token != NULL) {

printf("%s\n", token);

token = strtok(NULL, " ");

}

}

//Hàm trên sử dụng hàm strtok() để tách câu thành các từ dựa trên dấu cách. Sau đó, nó in ra từng từ trên một dòng.

int main() {

printf("nhap cau can phan tich: ");

fflush(stdin);

gets(sentence);

// xóa kí tự xuống dòng cuối chuỗi

if (sentence[strlen(sentence) - 1] == '\n') {

sentence[strlen(sentence) - 1] =='\0';

}

phantichcau(sentence);

}

# data[].attributes.body
Thuật toán:

struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size)

{

struct MinHeapNode left, right, *top;

struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size);

while (!isSizeOne(minHeap)) {

left = extractMin(minHeap);

right = extractMin(minHeap);

top = newNode('$', left->freq + right->freq);

top->left = left;

top->right = right;

insertMinHeap(minHeap, top);

}

return extractMin(minHeap);

}