Đồ Án Kiểm tra từ: đọc các từ trong một phần văn bản rồi tìm chúng trong một từ điển

Kiểm tra từ: đọc các từ trong một phần văn bản rồi tìm chúng trong một từ điển. Dùng một BST (cây nhị phân tìm kiếm) để lưu trữ từ điển này, đọc danh sách các từ trong một tập tin. Khi kiểm tra các từ trong văn bản, chương trình in ra danh sách tất cả các từ không có trong tự điển

Mục lục :
I. Phân tích và mở rộng đề tài 2
1. Phân tích : 2
2. Mở rộng đề tài : 2
II. Ý tưởng thực hiện: 2
1. Lệch hoàn toàn 1 phía, vd : lệch trái hêt, lêch phải hêt (lệch 2 bậc) 2
2. Lệch 1 phía nhưng cac nhánh con phía đó cân bằng (lệch 2 bậc) 2
3. Trường hợp phưc tạp nhât là lệch trái – phải (khó khăn nhât để chỉnh lại) 3
a. Chỉnh lại sự cân bằng trường hợp 1 và 2: 3
b. Trường hợp 3, ta chỉnh như sau: 4
III. Những thay đổi trong quá trình thực hiện 5
1. Đánh giá về cấu trúc nhị phân tìm kiếm (Binary Search Tree) : 5
2. Đánh giá về cây cân bằng (AVL Tree) : 5
3. Cấu trúc Trie (reTRIEval) : 5
IV. Cấu trúc và thuật toán 5
1. Cấu trúc Trie 5
2. Cấu trúc từ điển : 6
V. Chương trình – thuật toán 6
1. Cấu trúc node : 6
2. Class Trie : 6
3. Các hàm chính trong class Trie (Các hàm khác tham khảo trong file) 7
a. Hàm trả ra node chứa chữ cái cuối của 1 từ nếu có isHaving(Word) : 7
b. Hàm chèn từ vào Insert(Word,line): 7
c. Hàm returnTextOfLine(line) 8
d. Hàm returnWordOfText(inputText) 8
e. Hàm returnMeaningOfText(inputText) 9
f. Hàm returnMeaningOf(Word) 9
g. Hàm InputFromFile(fileName) 9
h. Hàm tìm em út và hàm tìm em chứa kí tự c 10
i. Hàm khởi tạo Trie : 10
4. Các hàm trong winform : 10
a. Sự kiện load form chính : 11
b. Sự kiện nhấn vào button tra từ sau khi nhập từ: 11
c. Sự kiện nhấn vào button chọn file : 12
d. Sự kiện nhấn vào từ trong khung từ gần đúng : 13
e. Sự kiện nhấn button Add : 14
f. Sự kiện nhấn button Chọn trong form Get file 14
g. Các sự kiện khác xin xem chi tiết trong các file, đã được chú thích khá kĩ : 14
VI. Kết quả chạy chương trình : 15
VII. Đánh giá cấu trúc 19
1. Cấu trúc Trie 19
a. Ưu điểm của cấu trúc Trie : 19
b. Tuy nhiên có một số nhược điểm sau : 19
2. Độ phức tạp : 20
VIII. Đánh giá đồ án 20
1. Đã làm được : 20
2. Một số vấn đề 20
IX. Lời cảm ơn : 20

I. Phân tích và mở rộng đề tài
1. Phân tích :
Chúng ta phải đầu tiên tạo một cấu trúc dữ liệu để lưu từ điển với dữ liệu nhập từ một file, cấu trúc dữ liệu được đề nghị là cây nhị phân tìm kiếm. Sau khi tạo cây xong, chúng ta sẽ thực hiện việc chọn file văn bản rồi kiểm tra từ trong văn bản đó. Chương trình sẽ xuất ra những từ không có trong văn bản ra màn hình.
2. Mở rộng đề tài :
Nhóm em đã mở rộng thêm tính năng tra từ thông qua một form, chức năng chọn file văn bản qua một giao diện kiểu winform, tra từ gần giống, tìm file văn bản cần kiểm tra và trả về những từ xuất hiện và không xuất hiện trong văn bản
II. Ý tưởng thực hiện:
Chúng ta cần tạo một cây nhị phân với các node chứa một từ trong từ điển và cả phần định nghĩa của từ đó. Việc xây dựng cây nhị phân sẽ phải chọn node đầu tiên chứa chữ cái có vị trí ở giữa của bảng chữ cái (chữ h, k) để giúp cây không bị lệch quá lớn. (vì từ điển có cấu trúc xếp theo thứ tự chữ cái, số lượng lớn nên khi bổ sung dễ bị lệch).
Tuy vậy, việc cây bị lệch là hoàn toàn có thể, và chúng ta không thể lường trước được (trừ khi nắm rõ tất cả số lượng các chữ và tìm được chữ ở giữa của file từ điển để chèn chữ ở giữa đó vào trước). Khó khăn này làm tụi em cũng nghĩ tới cây cân bằng (AVL tree). Sau khi tìm hiểu về cây cân bằng, tụi em đã rút ra được một số phương án tự điều chỉnh của cây như sau :
Để thay đổi cấu truc cây cân bằng khi thực hiện cân bằng cây bị lệch, ta có 3 trường hợp: