Luận văn Xây dựng chương trình từ điển tiếng Nga

sẽ làm cho tập tin .exe phình to về kích thước. Vì vậy, có thể đặt Form vào bên trong DLL và gọi hiển thị Form từ chương trình chính. Có hai cách để hiển thị Form chứa trong DLL: + Hiển thị Form ở dạng modeless: khi Form phụ ở dạng modeless, người sử dụng có thể quay lại tương tác với Form chính trong khi Form phụ đang hiển thị. + Hiển thị Form ở dạng dạng model: người sử dụng không thể quay về tương tác với cửa sổ Form chính nếu cửa sổ Form phụ chưa được đóng lại. 1.2.9. Giới thiệu về WIN32 API và hệ thống thông điệp * API (Application Programming Interface), còn gọi là Giao tiếp lập trình ứng dụng, là tập hợp các lời gọi hàm cấp cao do hệ điều hành Windows cung cấp. Sử dụng Win32 API trong Delphi cần khai báo hai Unit Windows và Messages trong mệnh đề USES ở đầu chương tình như sau: Uses Windows, Messages; Trong đó thư viện Windows chứa các khai báo hàm Windows API, thư viện Messages chứa các khai báo hằng và kiểu dữ liệu. * Thông điệp Thông điệp là một mẫu tin báo hiệu do Windows phát sinh và gửi đến cửa sổ ứng dụng và hàm WndProc chính là nơi tiếp nhận và xử lý các thông điệp đó. Mỗi thông điệp chuẩn của Windows là một hằng số bắt đầu bằng tiếp đầu ngữ WM_. Mỗi thông điệp đều có ý nghĩa và cách thức xử lý khác nhau. Ví dụ: WM_KEYDOWN: Nút bàn phím bị nhấn xuống. WM_KEYUP: Nút bàn phím được nhả ra. CHƯƠNG II: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 2.1. GIỚI THIỆU 2.1.1. Giải thuật và cấu trúc dữ liệu Giải thuật là một dãy các câu lệnh chặt chẽ và rõ ràng xác định một trình tự các thao tác trên một số đối tượng nào đó sao cho sau một số hữu hạn bước thực hiện ta đạt được kết quả mong muốn. Việc giải thuật đó được tác động lên dữ liệu nào và dữ liệu ấy cần được tác động giải thuật gì để đưa tới kết quả tốt. Như vậy giữa cấu trúc dữ liệu và giải thuật có mối quan hệ mật thiết. Chính điều đó đã dẫn tới việc cần nghiên cứu các cấu trúc dữ liệu đi đôi với việc xác lập các giải thuật xử lý trên các cấu trúc ấy. 2.1.2. Cấu trúc dữ liệu và các vấn đề liên quan Trong một bài toán, dữ liệu bao gồm một tập các phần tử cơ sở gọi là dữ liệu nguyên tử. Lựa chọn một cấu trúc dữ liệu thích hợp để tổ chức dữ liệu vào và trên cơ sở đó xây dựng được giải thuật xử lý hữu hiệu đưa tới kết quả mong muốn cho bài toán, đó là khâu rất quan trọng. Cách biểu diễn một cấu trúc dữ liệu trong bộ nhớ được gọi là cấu trúc lưu trữ. Đó chính là cách cài đặt cấu trúc ấy trên máy tính và trên cơ sở các cấu trúc lưu trữ này mà thực hiện các phép xử lý. 2.1.3. Các tiêu chuẩn đánh giá cấu trúc dữ liệu Một cấu trúc dữ liệu tốt phải thỏa mãn các tiêu chuẩn sau: - Phản ánh đúng thực tế: Đây là tiêu chuẩn quan trọng nhất, quyết định tính đúng đắn của toàn bộ bài toán. - Phù hợp với các thao tác trên đó: tiêu chuẩn này giúp tăng tính hiệu quả của đề án: việc phát triển các thuật toán đơn giản, tự nhiên hơn; chương trình đạt hiệu quả cao hơn về tốc độ xử lý. - Tiết kiệm tài nguyên hệ thống: thông thường có 2 loại tài nguyên cần lưu tâm nhất: CPU và bộ nhớ. 2.1..4. Đánh giá độ phức tạp giải thuật Cần tìm những phương pháp đánh giá thuật toán ít phụ thuộc môi trường cũng như phần cứng hơn. Một phương pháp như vậy là phương pháp đánh giá thuật toán theo hướng xấp xỉ tiệm cận qua các khái niệm toán học O(), o(),... Hầu hết các thuật toán đều có một tham số chính là N, thông thường đó là số lượng các phần tử dữ liệu được xử lý mà ảnh hưởng rất nhiều tới thời gian chạy. Hầu hết tất cả các thuật toán trong giáo trình này có thời gian chạy tiệm cận tới một trong các hàm sau: hằng số, logN, N, NlogN, N2, N3, 2N 2.2. SẮP XẾP VÀ TÌM KIẾM Trong hầu hết các hệ lưu trữ, quản lý dữ liệu, thao tác tìm kiếm thường được thực hiện nhiều nhất để khai thác thông tin. Ví dụ: tra cứu từ điển, tìm sách trong thư viện... Do các hệ thống thông tin thường phải lưu trữ một khối lượng dữ liệu đáng kể, nên việc xây dựng các giải thuật cho phép tìm kiếm nhanh sẽ có ý nghĩa rất lớn. Nếu dữ liệu trong hệ thống đã được tổ chức theo một trật tự nào đó, thì việc tìm kiếm sẽ tiến hành nhanh chóng và hiệu quả hơn. Ví dụ: các từ trong từ điển được sắp xếp theo từng vần, trong mỗi vần lại được sắp xếp theo thứ tự bảng chữ cái; sách trong thư viện được xếp theo chủ đề, tên tác giả.... Hiện nay đã có nhiều giải thuật tìm kiếm và sắp xếp được xây dựng, mức độ hiệu quả của từng giải thuật còn phụ thuộc vào tính chất của cấu trúc dữ liệu cụ thể mà nó tác động đến. Dữ liệu được lưu trữ chủ yếu trong bộ nhớ chính và trên bộ nhớ phụ do đặc điểm khác nhau của thiết bị lưu trữ, các thuật toán sắp xếp và tìm kiếm được xây dựng cho các cấu trúc lưu trữ trên bộ nhớ chính hoặc phụ cũng có những đặc thù khác nhau. Các thuật toán sắp xếp được phân thành hai nhóm chính là: - Sắp thứ tự nội: toàn bộ dữ liệu cần sắp thứ tự phải được đưa vào trong bộ nhớ chính, nên thời gian để sắp thứ tự tương đối nhanh. - Sắp thứ tự ngoại: một phần các dữ liệu cần sắp thứ tự được đưa vào trong bộ nhớ chính, phần dữ liệu còn lại được lưu trữ ở trên bộ nhớ ngoài. Thời gian để sắp thứ tự tương đối chậm. 2.2.1.Một số giải thuật sắp xếp. Sắp xếp là quá trình xử lý một danh sách các phần tử (hoặc các mẫu tin) để đặt chúng theo một thứ tự thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thông tin lưu giữ tại mỗi phần tử. Một số phương pháp sắp xếp thông dụng như: + Sắp xếp kiểu lựa chọn (Selection Sort) + Sắp xếp kiểu thêm dần (Insertion Sort) + Sắp xếp kiểu đổi chỗ (Exchange Sort) + Sắp xếp kiểu nổi bọt (Bubble Sort) + Sắp xếp kiểu phân đoạn (Quick Sort) + Sắp xếp kiểu vun đống (Heap Sort) + Sắp xếp kiển hòa nhập (Merge Sort) + Sắp xếp với độ dài bước giảm dần (Shell Sort) + Sắp xếp theo phương pháp cơ số (Radix Sort) Nhận xét và đánh giá các thuật toán sắp xếp: Phần lớn các thuật toán sắp xếp cơ bản dựa trên sự so sánh giá trị giữa các phần tử. Đó là các thuật toán chọn lựa, thêm dần, nổi bọt, đổi chỗ. Các thuật toán này đều có một điểm chung là chi phí thực hiện chung là tỉ lệ với n2. Các thuật toán shell-sort (cải tiến của phương pháp thêm dần), heap-sort (cải tiến của phương pháp chọn lựa) lại có độ phức tạp nhỏ hơn hẳn các thuật toán gốc. Thuật toán shell-sort có độ phức tạp O(nx) với 1 < x < 2 và thuật toán heap-sort có độ phức tạp O(nlog2n). Các thuật toán merge-sort và quick-sort là những thuật toán thực hiện theo chiến lược chia để trị. Cài đặt chúng tuy phức tạp hơn các thuật toán khác nhưng chi phí thực hiện lại thấp, cả hai thuật toán đều có độ phức tạp O(nlog2n). Merge-sort có nhược điểm là cần dùng thêm bộ nhớ đệm. Thuật toán này sẽ phát huy tốt ưu điểm khi cài đặt trên các cấu trúc dữ liệu khác phù hợp hơn như danh sách liên kết hay phi. Thuật toán quick-sort được đánh giá là thuật toán sắp xếp nhanh nhất trong số các thuật toán sắp xếp dựa trên nền tảng so sánh giá trị của các phần tử. Tuy có chi phí trong trường hợp xấu nhất là O(n) nhưng trong kiểm nghiệm thực tế, thuật toán quick-sort chạy nhanh hơn hai thuật toán cùng nhóm O(nlog2n) là merge-sort và heap-sort. Thuật toán Radix-sort là một thuật toán được phát triển theo hướng khác với các thuật toán trên. Nó được phát triển dựa trên mô phỏng qui trình phân phối thư của người đưa thư. Thuật toán này đại diện cho nhóm các thuật toán sắp xếp có độ phức tạp tuyến tính. Tuy nhiên, thường thì các thuật toán này không thích hợp cho việc cài đặt trên cấu trúc dữ liệu mảng một chiều. 2.2.2. Các giải thuật tìm kiếm nội Thông thường các dữ liệu được phân chia thành các bản ghi, mỗi bản ghi có một khoá được sử dụng trong việc tìm kiếm. Vấn đề của việc tìm kiếm là tìm tất cả các mẩu tin có cùng khoá k cho biết trước để truy xuất nội dung của bản ghi. Công việc tìm kiếm sẽ hoàn thành khi có một trong hai tình huống sau xảy ra: - Tìm được bản ghi có giá trị khóa tương ứng, lúc đó ta nói: phép tìm kiếm được thỏa. - Không tìm được bản ghi nào có giá trị khóa tương ứng: phép tìm kiếm không thỏa. Sau khi phép tìm kiếm không thỏa có khi xuất hiện yêu cầu bổ sung thêm bản ghi mới có khóa không tìm thấy vào bảng. Giải thuật thể hiện cả yêu cầu này được gọi là giải thuật “Tìm kiếm có bổ sung”. Ta có một số thuật toán tìm kiếm như: + Tìm kiếm tuần tự + Tìm kiếm nhị phân + Tìm kiếm dựa vào giá trị khóa Nhận xét và đánh giá các thuật toán tìm kiếm: Giải thuật tìm nhị phân dựa vào quan hệ giá trị của các phần tử mảng để định hướng trong quá trình tìm kiếm, do vậy chỉ áp dụng được cho những dãy đã có thứ tự. Giải thuật tìm nhị phân tiết kiệm thời gian hơn rất nhiều so với giải thuật tìm kiếm tuần tự do Tnhị phân(n) = O(log2n) < Ttuần tự(n) = O(n). Tuy nhiên khi muốn áp dụng giải thuật tìm nhị phân cần phải xét đến thời gian sắp xếp dãy số để thỏa điều kiện dãy số có thứ tự. Với phương pháp tìm kiếm dựa vào giá trị khóa, các khóa có giá trị khác nhau cũng có thể cùng ứng với một địa chỉ và hiện tượng này được gọi là hiện tượng đụng độ. Vì vậy khi xét phương pháp này, không những cần chú ý đến cách xây dựng hàm địa chỉ mà còn phải xét cả tới phương pháp khắc phục đụng độ. 2.3. CẤU TRÚC CÂY 2.3.1. Định nghĩa và khái niệm * Định nghĩa cây Cây là một tập hợp T rỗng hoặc gồm nhiều phần tử được gọi là nút, trong đó: - Một nút được gọi là nút gốc (root). - Các nút còn lại được phân chia thành m nhóm (m>=0), mỗi nhóm là một cây và được gọi là cây con. Trong đó nút có thể được xem như là một phần tử của một danh sách và có thể có kiểu bất kỳ. Các nút được biểu diễn bởi một ký tự chữ, một chuỗi, một số ghi trong một vòng tròn. Giữa các nút có một quan hệ phân cấp gọi là “quan hệ cha con”, các nút ngay bên trên trực tiếp là nút cha, các nút ngay bên dưới trực tiếp là các con của nút đó. Một cây không có một nút nào cả gọi là cây rỗng. * Một số khái niệm cơ bản - Bậc của một nút: là số cây con của nút đó - Bậc của một cây: là bậc lớn nhất của các nút trong cây (số cây con tối đa của một nút thuộc cây). Cây có bậc n thì gọi là cây n-phân. - Nút gốc: là nút không có nút cha. - Nút lá: là nút có bậc bằng 0. - Nút nhánh: là nút có bậc khác 0 và không phải là gốc - Rừng cây: là tập hợp nhiều cây trong đó thứ tự các cây là quan trọng. 2.3.2. Các cách biểu diễn cây Để biểu diễn một cây, ta có nhiều cách: a) Biểu diễn cây bằng đồ thị b) Biểu diễn cây bằng giản đồ c) Biểu diễn cây bằng các dấu ngoặc lồng nhau d) Biểu diễn cây bằng phương pháp Indentation e) Biểu diễn cây bằng chỉ số 2.3.3. Cây nhị phân * Khái niệm: Cây nhị phân là một dạng quan trọng của cấu trúc cây. Nó có đặc điểm là: mọi nút trên cây chỉ có tối đa là hai cây con (cây con trái và cây con phải). Cây nhị phân là cây có thứ tự. 2.3.3.1. Biểu diễn cây nhị phân - Lưu trữ kế tiếp: cây được lưu trữ bằng một vectơ V với nút thứ i của cây được lưu trữ ở V[i]. Với cách lưu trữ này nếu biết được địa chỉ nút cha sẽ tính được địa chỉ nút con và ngược lại. Tuy nhiên nếu cây nhị phân không đầy đủ thì cách lưu trữ này không thích hợp vì sẽ gây ra lãng phí do có nhiều phần tử nhớ bỏ trống (ứng với cây con rỗng). A B C F D E G Ví dụ: Với cây nhị phân Hình số 1 Biểu diễn phương pháp lưu trữ kế tiếp của cây nhị phân trên như sau: A B C D E E G V[1] V[2] V[3] V[4] V[5] V[6] V[7] Hình số 2 - Lưu trữ móc nối: mỗi nút của cây ứng với một phần tử nhớ gồm ba trường là: trường INFO ứng với thông tin dữ liệu của nút; trường LPTR ứng với con trỏ trỏ tới cây con trái của nút đó; trường RPTR ứng với con trỏ trỏ tới cây con phải của nút đó. Với cách biểu diễn này thì nút cha có thể truy nhập vào nút con dễ dàng, nhưng ngược lại thì không làm được Ví dụ: Với cây nhị phân trên ta có phương pháp lưu trữ móc nối như sau A B C D G E F Hình số 3 2.3.3.2. Duyệt cây nhị phân Có ba phép duyệt khác nhau đối với cây nhị phân. - Duyệt theo thứ tự trước: Kiểu duyệt này trước tiên thăm gốc sau đó thăm các nút của cây con trái rồi đến cây con phải. - Duyệt theo thứ tự giữa: Kiểu duyệt này trước tiên thăm các nút của cây con trái sau đó thăm nút gốc rồi đến cây con phải. - Duyệt theo thứ tự sau: Kiểu duyệt này trước tiên thăm các nút của cây con trái sau đó thăm đến cây con phải rồi cuối cùng mới thăm nút gốc. 2.3.4. Biểu diễn cây tổng quát bằng cây nhị phân - Cây tổng quát: có đặc điểm là mọi nút trên cây có thể có nhiều hơn hai cây con. - Nhược điểm của các cấu trúc cây tổng quát là bậc của các nút trên cây có thể dao động trong một biên độ lớn, nên việc biểu diễn gặp nhiều khó khăn và lãng phí. Hơn nữa, việc xây dựng các thao tác trên cây tổng quát phức tạp hơn trên cây nhị phân nhiều. Vì vậy, thường nếu không quá cần thiết phải sử dụng cây tổng quát, người ta chuyển cây tổng quát thành cây nhị phân. Ta có thể biến đổi một cây bất kỳ thành một cây nhị phân theo qui tắc sau: + Giữ lại nút con trái nhất làm nút con trái. + Các nút con còn lại chuyển thành nút con phải. + Như vậy, trong cây nhị phân mới, con trái thể hiện quan hệ cha con và con phải thể hiện quan hệ anh em trong cây tổng quát ban đầu. Khi đó cây tổng quát biểu diễn theo qui tắc trên được gọi là cây nhị phân tương đương. B A C E F G D H I J A B E C D G H I J F Ví dụ: Cây tổng quát chuyển sang cây nhị phân Hình số 4 2.3.5. Cây nhị phân tìm kiếm * Định nghĩa: Cây nhị phân tìm kiếm (CNPTK) là cây nhị phân trong đó tại mỗi nút, khóa của nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn khóa của tất cả các nút thuộc cây con phải. Nhờ ràng buộc về khóa trên CNPTK, việc tìm kiếm trở nên có định hướng. Hơn nữa, do cấu trúc cây việc tìm kiếm trở nên nhanh đáng kể. Nếu số nút trên cây là N thì chi phí tìm kiếm trung bình chỉ khoảng log2N. * Các thao tác trên cây nhị phân tìm kiếm: a) Duyệt cây: Thao tác duyệt cây trên cây nhị phân tìm kiếm hoàn toàn giống như trên cây nhị phân. Chỉ có một lưu ý nhỏ là khi duyệt theo thứ tự giữa, trình tự các nút duyệt qua sẽ cho ta một dãy các nút theo thứ tự tăng dần của khóa. b) Thêm một phần tử x vào cây: Việc thêm vào phải bảo đảm điều kiện ràng buộc của CNPTK. Ta có thể thêm vòa nhiều chỗ khác nhau trên cây, nhưng nếu thêm vào một nút lá sẽ là tiện lợi nhất do ta có thể thực hiện quá trình tương tự thao tác tìm kiếm. Khi chấm dứt quá trình tìm kiếm cũng chính là lúc tìm được chỗ cần thêm. c) Hủy một phần tử có khóa x: Việc hủy một phần tử x ra khỏi cây phải bảo đảm điều kiện ràng buộc của CNPTK. Có 3 trường hợp khi hủy nút x có thể xảy ra: + x là nút lá: chỉ đơn giản hủy x vì nó không móc nối đến phần tử nào khác. + x chỉ có 1 con (trái hoặc phải): trước khi hủy x ta móc nối cha của x với con duy nhất của nó. + x có đủ cả 2 con: ta không thể hủy trực tiếp do x có đủ 2 con. Vì vậy ta sẽ hủy gián tiếp. Thay vì hủy x, ta sẽ tìm một phần tử thế mạng y. Phần tử này có tối đa một con. Thông tin lưu tại y sẽ được chuyển lên lưu tại x. Sau đó, nút bị hủy thật sự sẽ là y giống như 2 trường hợp đầu. Vấn đề là phải chọn y sao cho khi lưu y vào vị trí của x, cây vẫn là CNPTK. Có 2 phần tử thỏa mãn yêu cầu: Phần tử nhỏ nhất (trái nhất) trên cây con phải và phần tử lớn nhất (phải nhất) trên cây con trái. d) Tạo một cây CNPTK: Ta có thể tạo một cây nhị phân tìm kiếm bằng cách lặp lại quá trình thêm 1 phần tử vào một cây rỗng. e) Hủy toàn bộ CNPTK: Việc toàn bộ cây có thể được thực hiện thông qua thao tác duyệt cây theo thứ tự sau. Nghĩa là ta sẽ hủy cây con trái, cây con phải rồi mới hủy nút gốc. 2.3.6. Cây nhị phân cân đối * Cây nhị phân cân đối hoàn toàn: là cây nhị phân tìm kiếm mà tại mỗi nút của nó, số nút của cây con trái chênh lệch không quá một so với số nút của cây con phải. Nhận xét: Một cây khó đạt được trạng thái cân bằng hoàn toàn. Tuy nhiên nếu cây cân đối thì việc tìm kiếm sẽ nhanh, trong trường hợp xấu nhất ta chỉ phải tìm qua log2n phần tử (với n là số nút trên cây). Do cây cân đối hoàn toàn là một cấu trúc kém ổn định nên trong thực tế không thể sử dụng. * Cây nhị phân cân đối: là cây mà tại mỗi nút của nó độ cao của cây con trái và của cây con phải chênh lệch không quá một. Nhận xét: Cây cân đối hoàn toàn là cây cân bằng. Điều ngược lại không đúng. Tuy nhiên cây cân đối là cấu trúc dữ liệu ổn định hơn hẳn cây cân đối hoàn toàn. Từ cây cân đối người ta đã phát triển thêm nhiều lại cấu trúc dữ liệu hữu dụng khác như cây đỏ-đen, B-cây,... 2.3.7. Cây nhị phân tìm kiếm tối ưu Xây dựng cây nhị phân tìm kiếm tương ứng với các từ khóa. Đối với các từ khóa có xác suất xuất hiện lớn thì cần phải được tìm thấy nhanh hơn, nghĩa là tương ứng với đường đi ngắn hơn. Muốn thế gắn với mỗi khóa (nút) một trọng số, đó chính là xác suất xuất hiện của khóa này trong tìm kiếm. Và mục đích là xác định được cây nhị phân tìm kiếm sao cho tổng độ dài đường đi có trọng số tương ứng với mọi nút trên cây (hay còn gọi là độ dài đường đi có trọng số của cây) có giá trị nhỏ nhất. Tuy nhiên việc chọn một cây có trọng số nhỏ nhất là một công vệc khó thực hiện khi n khá lớn. Vậy để giải quyết vấn đề này ta thực hiện theo nguyên tắc sau: “Đối với một cây nhị phân tìm kiếm tối ưu thì bất kỳ một cây con nào của nó cũng phải là cây nhị phân tìm kiếm tối ưu ”. Từ đó dẫn tới một giải thuật cho phép dựng được cây nhị phân tìm kiếm tối ưu lớn dần lên bắt đầu từ một nút lá mà ta gọi là kỹ thuật dựng cây nhị phân tìm kiếm tối ưu theo kiểu “từ đáy lên” (bottom up). CHƯƠNG III: TỔ CHỨC LƯU TRỮ CÂY TỪ ĐIỂN Một cấu trúc dữ liệu khá điển hình và hợp lý với bài toán từ điển là: cấu trúc cây từ điển. Quản lý từ điển có dạng cây là kỹ thuật thường được sử dụng để xử lý những từ điển lớn nhằm thu nhỏ dung lượng. Cây từ điển là tập hợp các bản ghi liên kết với nhau (còn gọi là phương pháp lưu trữ móc nối). Mỗi bản ghi gọi là một nút trong cây. Để quản lý cây từ điển ta luôn luôn phải giữ địa chỉ của cây, tức là nút gốc (nút đầu tiên của cây). Mỗi nút cây từ điển gồm có 3 trường: + Trường Info: chứa một kí tự kiểu CHAR. + Trường Left: chỉ đến nút Anh Em của nó. + Trường Right: chỉ đến nút con của nó. Một nút B gọi là con của nút A nếu B = A.left Tương tự nút B gọi là nút Anh Em của nút A nếu: B = A.right (hoặc A = B.right). Từ đây mở rộng ra: nếu B là Con của A và C là Anh Em của B thì cả B và C đều là Con của A. Nếu A là Anh Em của B và B là Anh Em của C thì A cũng là Anh Em của C. Để tạo thành cây từ điển trong quá trình chạy chương trình, ta phải làm thao tác nạp các từ tiếng Nga vào cây. Về trường nghĩa của từ, vì nó rất lớn nên không thể nạp vào bộ nhớ chương trình được. Vì vậy ta phải để nghĩa của từ ở trong File. Điều này bắt buộc ta phải xen kèm vào trong cây từ điển (tương ứng sau mỗi từ tiếng Nga) chỉ số vị trí của từ tiếng Nga đó trong File. Và tất nhiên chỉ số này phải được đổi thành chuỗi kí tự thập phân trước khi thực hiện xen từ. Khi đọc thì sẽ chuyển ngược chuỗi chỉ số này sang số thập phân. Ví dụ: Với các từ tiếng Nga: а/абажур/абзац/база/базар/бак/бакалея/ баклажан Khi lưu trữ trên cây, các từ tiếng Nga này sẽ là các chuỗi có cấu trúc như sau: а*1 абажур*2 абзац*3 база*4 базар*5 бак*6 бакалея*7 баклажан*8 ta có cấu trúc cây từ điển như sau : * а * 1 б Б а ж у р 2 з а ц * * 3 а з а * 4 р * 5 * к 6 а л е * я 7 а ж а н * 8 Root Nút đánh dấu kết thúc của mỗi từ Nút đánh dấu số thứ tự bản ghi của mỗi từ, sử dụng cho việc tìm kiếm và tra từ Nút thể hiện từng ký tự của mỗi từ Hình số 5 Nhận xét : Theo cây từ điển được minh họa như hình số 5 , ký tự ‘*’ được sử dụng làm ký tự đánh dấu ở đầu cấu trúc cây và làm ký tự kết thúc của một từ. Như vậy theo cây từ điển thì mỗi từ tiếng Nga ngoài các ký tự hình thành còn có thêm ký tự ‘*’ ở cuối mỗi từ để đánh dấu và các ký tự chữ số để đánh số thứ tự từng bản ghi trong file dữ liệu hỗ trợ cho quá trình tìm kiếm trên cây. Mỗi từ trong từ điển tương ứng với một bản ghi gồm ba trường: wordRec = record wordRus: string[25]; // trường Tiếng Nga wordMea: string[200]; // trường nghĩa Tiếng Việt STT:string[6];// trường số thứ tự cho hình ảnh, âm thanh end; Như vậy để chứa các từ trên cây chỉ mất rất ít số bản ghi so với dữ liệu của nó. Với cấu trúc này ta có thể nạp vào chương trình khi chạy tất cả các từ có trong một bộ từ điển lớn khoảng 100.000 từ mà không sợ bị tràn bộ nhớ. Hơn nữa thuật toán xây dựng các thao tác trên cây từ điển này sẽ hoạt động rất nhanh mà không phụ thuộc vào kích thước dữ liệu đầu vào. Khi chương trình hoạt động, mỗi lần ta đánh vào một kí tự (trong quá trình nhập từ để tra) chương trình sẽ phải duyệt cây từ điển để tìm ra các từ gần giống với chuỗi từ mà ta đang nhập nhất. Danh sách các từ này sẽ hiện ra giao diện chương trình. Quá trình duyệt bắt đầu từ nút gốc (Root) dần dần xuống tới các nút con. Đặc điểm của cây từ điển có rất nhiều nút lá, chiều cao của cây lại rất thấp (do số kí tự tạo ra từ không nhiều). Điều này rất thích hợp cho ta trong việc thường xuyên phải tìm kiếm trên cây. Thuật toán xây dựng trên cấu trúc dữ liệu này sẽ đơn giản và hoạt động rất nhanh. Kết luận: Đối với dạng cây Từ Điển đã nói ở trên ta thấy cây Từ Điển là một cây dạng tổng quát có tiền tố chung. Nhưng để ở dạng cây tổng quát thì việc thực hiện các thao tác và các phép xử lý trên cây khó khăn, cho nên cây được chuyển về dạng cây nhị phân với thuật toán chuyển đã trình bày. Qua dạng cấu trúc của cây nhị phân Từ Điển ta có nhận xét chung: Một từ luôn được kết thúc trên nhánh cây con trái. Các từ có tiền tố chung khi chúng là cây con phải của nút con trái của nút chứa kí tự cuối cùng thuộc chuỗi tiền tố. Từ nhận xét trên chúng ta có thể xây dựng được các giải thuật tìm kiếm, thêm, loại bỏ một cách chính xác. CHƯƠNG IV: THIẾT KẾ CHƯƠNG TRÌNH 4.1. TẠO BỘ GÕ VÀ FONT TIẾNG NGA CÓ DẤU NHẤN TRỌNG ÂM CHO NGƯỜI DÙNG 4.1.1. Khái quát về bộ gõ Khi nhập từ, vấn đề xác định kí tự tiếng Nga trên bàn phím đối với người sử dụng là rất khó khăn. Vì thế, chương trình Từ điển này đã hỗ trợ một bộ gõ tiếng Nga cho người dùng trong quá trình tra từ, khi người dùng không nhớ vị trí của kí tự. Tuy thô sơ nhưng giải pháp này phần nào đã mang lại cho người dùng cảm giác thoải mái khi sử dụng bộ gõ. Với giao diện bàn phím nhìn thấy được trên màn hình, người sử dụng chưa quen với bàn phím tiếng Nga có thể xác định được các phím của kí tự tiếng Anh tương ứng với từng ký tự tiếng Nga, qua đó người sử dụng có thể gõ được các từ tiếng Nga một cách dễ dàng. Cũng với giao diện này ta có thể thiết kế để người sử dụng dùng chuột click vào các phím trên bộ gõ để được từ mong muốn. Hình số 6 4.1.2. Cách thiết kế bộ gõ Tiếng Nga và Tiếng Việt cho riêng chương trình Khi sử dụng chương trình Từ điển, nếu trên máy người dùng không cài đặt các chương trình như VietKey, VietWare.... thì không thể thực hiện được chức năng tra từ tiếng Nga cũng như thêm từ tiếng Việt. Vì vậy, việc tạo một bộ gõ tiếng Nga và tiến Việt riêng cho chương trình là điều cần thiết. Bằng font tiếng Nga tự thiết kế và một số font tiếng Việt có sẵn của VietKey, dựa vào bảng mã ASCII của phông chữ chúng ta có thể biết được các mã tương ứng từng chữ cái tiếng Nga cũng như tiếng Việt. Với ngôn ngữ Delphi có hỗ trợ thủ tục chặn thông điệp các phím bấm từ bàn phím (thủ tục PostMessage). Để tạo ra được các ký tự tiếng Nga, tiếng Việt tương ứng với phím gõ chương trình cần phải chặn được thông điệp đến từ bàn phím, xác định được phím gõ tương ứng với phím nào của bàn phím tiếng Nga cũng như tiếng Việt. Bình thường thì ký tự hiển thị trên màn hình sẽ là ký tự Latinh tương ứng phím gõ, do đó để hiển thị được ký tự tiếng Nga chương trình cần phải xóa ký tự Latinh và thay thế bằng ký tự tiếng Nga. Việc thay thế ký tự tiếng Nga được dựa trên mã ASCII của font chữ tiếng Nga được dùng để hiển thị. Hai thủ tục sau trong chương trình sẽ thực hiện việc xóa ký tự Latinh và thay vào ký tự tiếng Nga: 1 PostMessage (frmNgaVietAnh.cboNhapTu.handle, WM_CHAR, 8, 1); 2 PostMessage (frmNgaVietAnh.cboNhapTu.handle, WM_CHAR, MaFont, 1); 1 Dùng để xóa ký tự Latinh với mã ASCII bằng 8 là mã của phím Del. 2 Dùng để hiển thị ký tự Nga có MaFont tương ứng với mã ASCII trong phông tiếng Nga của phím được gõ. Hàm PostMessage cũng được sử dụng tương tự cho ký tự tiếng Việt. 4.1.3. Phương pháp tạo Font Tiếng Nga mới Phông chữ tiếng Nga hiện nay vẫn đang là một vấn đề quan tâm của người dùng. Trong những font chữ hỗ trợ tiếng Nga hiện nay của các phần mềm như Vietkey 2002, VietKey4.0, Unikey,...thì không một font nào có kí tự dấu trọng âm ( là một âm nhấn trên đầu mỗi từ ) nhằm giúp người dùng biết cách phát âm của từ một cách chính xác . Tạo một bộ font mới tưởng chừng là một vấn đề nan giải, nhưng hiện nay với sự hỗ trợ của nhiều phần mềm chuyên dụng thì việc giải quyết không còn mấy khó khăn. Với phần mềm Photographer 4.1, bạn có thể tạo ra một bộ font tùy ý với kí tự do chính bạn thiết kế. Các bước tạo font trên Photographer được tiến hành như sau: - Chọn một bộ font mới, sau đó ứng với từng kí tự trên bàn phím ta có thể vẽ các kí tự bằng các công cụ thiết kế đồ họa được cung cấp sẵn trong phần mềm này. - Sau đó lưu lại để tạo ra một bộ font mơi, đó chính là font RussTimes SNG được sử dụng trong chươn