Đề tài Nghiên cứu và xây dựng ứng dụng từ điển trên điện thoại di động

lưu trữ mảng chuỗi, trong đó ta có thể dễ dàng thêm, cập nhật xóa và truy xuất các phần tử chuỗi trong mảng. Mảng chuỗi cũng có các dạng: 16 bit, 8 bit và build independent type. Bao gồm mảng chuỗi không thể chỉnh sửa (non-modifiable) và có thể chỉnh sửa (modifiable). 4.4.1.1 Mảng chuỗi không thể thay đổi Dạng mảng này gồm các TPtrC (non-modifiable pointer descriptor). Mỗi pointer descriptor này trỏ đến dữ liệu (chuỗi) của từng phần tử trong mảng. Hình 4.13 Mảng chuỗi không thể thay đổi Khi dùng mảng non-modifiable pointer descriptor array, dữ liệu được trỏ đến nhờ các pointer descriptor TPtrC. Như vậy mảng chỉ cần số vùng nhớ rất nhỏ đủ chứa các thành phần TPtrC (không có vùng nhớ cấp cho phần dữ liệu). Mặt khác, khi sử dụng dạng mảng này, phải đảm bảo dữ liệu các thành phần (chuỗi) trong mảng không được hủy hoặc thay đổi ngoài ý muốn. Bao gồm các lớp: CPtrC16Array, CPtrC8Array và CPtrCArray 4.4.1.2 Modifiable descriptor array Thành phần của mảng là con trỏ đến heap descriptor (HBuC*). Khi đưa một descriptor vào mảng, một heap descriptor khác được cấp phát lấy dữ liệu từ descriptor muốn đưa vào mảng; và phần tử mới của mảng chính là con trỏ đến heap descriptor vừa được cấp. Chương 4 . Kĩ thuật lập trình C++ trên Symbian 48 Hình 4.14 Mảng con trỏ chuỗi Khi sử dụng dạng mảng chuỗi này, một heap descriptor được cấp cho mỗi phần tử đưa vào mảng. Điều này làm tăng tổng số vùng nhớ yêu cầu cho mảng. Mặt khác chuỗi sau khi đưa vào có thể bị hủy hoặc chỉnh sửa mà không ảnh hưởng đến các phần tử trong mảng. Cũng như mảng động bình thường, lập trình viên có thể sử dụng mảng chuỗi với 2 loại vùng nhớ: vùng nhớ cấp phát liên tục (flat array buffer) và vùng nhớ cấp phát phân đoạn (segmented array buffer) Bao gồm các lớp cụ thể: CDesC16ArrayFlat, CDesC16ArrayFlat và CDesCArrayFlat; CDesC16ArraySeg, CDesC16ArraySeg và CDesCArraySeg. Chương 5 . Các giải pháp chính cho việc xây dựng từ điển trên điện thoại di động Series 60 49 Chương 5 Các giải pháp chính cho việc xây dựng từ điển trên điện thoại di động Series 60 Trong chương 3 ta đã đề cập đến hai mâu thuẫn là: ƒ Mâu thuẫn giữa khả năng lưu trữ của điện thoại di động và yêu cầu về dữ liệu của từ điển. ƒ Mâu thuẫn giữa tốc độ xử lý của điện thoại di động và tốc độ xử lý của ứng dụng. Đối với mâu thuẫn thứ nhất ta có thể giải quyết bằng cách: hoặc là gia tăng khả năng lưu trữ của điện thoại di động bằng cách nâng cấp thẻ nhớ hoặc là tổ chức nén dữ liệu (đồng thời phải cung cấp một cơ chế để có thể giải nén và truy xuất dữ liệu nhanh). Tuy nhiên việc nâng cấp thẻ nhớ không nằm trong nội dung xây dựng từ điển cho điện thoại di động. Đối với mâu thuẫn thứ hai, bộ vi xử lý của điện thoại di động khó có thể nâng cấp giống như máy tính cá nhân được do đó ta chỉ có thể tìm cách xây dựng cấu trúc dữ liệu hỗ trợ tìm kiếm nhanh. Như vậy ứng dụng không những cần tổ chức cấu trúc dữ liệu lưu trữ thích hợp mà còn phải giải quyết các mâu thuẫn trên thông qua tổ chức nén dữ liệu và tổ chức cấu trúc dữ liệu hỗ trợ cho việc tìm kiếm nhanh. 5.1 Tổ chức cấu trúc dữ liệu lưu trữ Mỗi một mục từ trong từ điển cần lưu trữ các trường dữ liệu sau: từ gốc, từ loại, ý nghĩa của từ. Bảng sau mô tả vắn tắt về các trường dữ liệu này. STT Trường dữ liệu Ghi chú 1. Từ gốc Có kích thước biến động. 2. Từ loại Mỗi từ có thể thuộc về nhiều từ loại khác nhau: 9 Danh từ 9 Động từ 9 Tính từ 9 Trạng từ 9 Giới từ 9 Các từ loại khác 3. Ý nghĩa (các nghĩa con của từ) Có kích thước biến động, bao gồm: 9 Phiên âm quốc tế (nếu có) 9 Các nghĩa khác của từ. Bảng 5.1 Bảng mô tả các trường dữ liệu Chương 5 . Các giải pháp chính cho việc xây dựng từ điển trên điện thoại di động Series 60 50 Với các trường dữ liệu như vậy, ta có một số giải pháp tổ chức mục từ như sau: ƒ Tổ chức các mục từ có kích thước bằng nhau. ƒ Tổ chức các mục từ có kích thước biến động. Ta sẽ đi vào xem xét kỹ hơn những ưu điểm và khuyết điểm của từng giải pháp và chọn ra một giải pháp thích hợp. 5.1.1 Tổ chức các mục từ có kích thước bằng nhau Ưu điểm: ƒ Dễ dàng truy xuất ngẫu nhiên đến một mục từ khi biết vị trí của nó. Khuyết điểm: ƒ Gây lãng phí không gian lưu trữ vì các mục từ có kích thước biến động nhiều. Nếu chúng ta tổ chức các mục từ cùng một kích thước thì sẽ có rất nhiều mục từ không dùng hết kích thước đó, điều này dẫn đến bộ nhớ bị lãng phí. Khuyết điểm này rất nghiêm trọng vì bộ nhớ lưu trữ của điện thoại di động là rất hạn chế. Kích thước tập tin dữ liệu khi chỉ có từ gốc của 3 loại từ điển thông dụng: Anh – Việt (68998 từ), Việt – Anh (91146 từ) và Anh – Anh (121962 từ) được liệt kê trong bảng sau: Từ điển Ví dụ về từ có kích thước lớn nhất Kích thước Tổng kích thước (KB) Anh – Việt “ extra-sensory perception” 24 1617 Việt – Anh “không đúng với đặc tính của một ngôn ngữ” 40 3560 Anh – Anh “American Federation of Labor-Congress of Industrial Organizations” 65 7741 Bảng 5.2 Tổ chức từ điển với cáctừ gốc có kích thước bằng nhau Trong bảng trên ta phải sử dụng kích thước từ lớn nhất: xét trong điều kiện mỗi ký tự được biểu diễn bởi 1 byte và kích thước mục từ ở mỗi từ điển khác nhau. Quy định kích thước đồng nghĩa với việc hạn chế kích thước của mục từ, do đó có thể không lưu được những mục từ thông dụng có kích thước từ gốc lớn và nghĩa lớn. Khuyết điểm này cũng không kém phần nghiêm trọng vì làm hạn chế khả năng lưu trữ của từ điển và cách thức tổ chức có vẻ không tự nhiên. Chương 5 . Các giải pháp chính cho việc xây dựng từ điển trên điện thoại di động Series 60 51 5.1.2 Tổ chức các mục từ có kích thước biến động Ưu điểm: ƒ Tránh được sự lãng phí bộ nhớ lưu trữ do đó tối ưu bộ nhớ lưu trữ của điện thoại di động. ƒ Không hạn chế kích thước của các mục từ, cách thức tổ chức tự nhiên hơn. Khuyết điểm: ƒ Do kích thước của các mục từ biến động nên cần phải tốn thêm thông tin để có thể truy cập đến một mục từ bất kỳ, nói cách khác là chúng ta phải tổ chức thêm cấu trúc dữ liệu hỗ trợ cho việc tìm kiếm nhanh. Kích thước tập tin dữ liệu khi chỉ có từ gốc của 3 loại từ điển thông dụng: Anh – Việt (68998 từ), Việt – Anh (91146 từ) và Anh – Anh (121962 từ) được liệt kê trong bảng sau: Từ điển Tổng kích thước (KB) Kích thước từ trung bình (ký tự) Anh – Việt 610 9 Việt – Anh 1204 13 Anh – Anh 1334 11 Bảng 5.3 Tổ chức từ điển với cáctừ gốc có kích thước không bằng nhau Trong bảng trên mỗi từ được lưu với kích thước thật và mỗi ký tự được biểu diễn bởi 1 byte. Như vậy giải pháp lưu trữ mục từ với kích thước khác nhau đã tiết kiệm được rất nhiều không gian lưu trữ. (Nhỏ hơn từ 2.5 đến 7 lần). Rõ ràng việc tổ chức các mục từ có kích thước bằng nhau đã bộc lộ nhiều khuyết điểm mà một trong những khuyết điểm nghiêm trọng không thể chấp nhận được đó là gây lãng phí không gian lưu trữ của điện thoại di động. Trong khi đó việc tổ chức các mục từ có kích thước biến động đã thể hiện ưu điểm vượt trội của mình là tránh được sự lãng phí không cần thiết đối với không gian lưu trữ . Do đó dữ liệu của ứng dụng từ điển trong luận văn này sẽ được tổ chức theo cách tổ chức tối ưu này. Phần tiếp theo sẽ trình bày cách thức nén dữ liệu để sao cho có được kích thước dữ liệu tối ưu nhất có thể có. Chương 5 . Các giải pháp chính cho việc xây dựng từ điển trên điện thoại di động Series 60 52 5.2 Tổ chức nén dữ liệu Việc tổ chức các mục từ có kích thước biến động vẫn chưa thể thực sự tối ưu hóa không gian lưu trữ. Kích thước của dữ liệu từ điển vẫn còn lớn so với không gian lưu trữ của điện thoại di động. Ngoài việc tổ chức các mục từ có kích thước biến động ta chỉ có thể làm giảm kích thước dữ liệu bằng cách nén dữ liệu để lưu trữ và khi cần truy xuất thì giải nén dữ liệu. Nhưng việc tổ chức nén và giải nén dữ liệu khi cần thiết có thể làm giảm tốc độ truy xuất, do đó chúng ta cần phải lựa chọn phương pháp nén và giải nén sao cho tốc độ truy xuất có thể chấp nhận được. Có hai chiến lược nén dữ liệu là: nén toàn bộ dữ liệu và nén từng khối dữ liệu. Ta hãy lần lượt phân tích mặt mạnh, mặt yếu của từng chiến lược nén để chọn ra chiến lược nén thích hợp cho bài toán xây dựng từ điển trên thiết bị di động. 5.2.1 Nén toàn bộ dữ liệu Ưu điểm: ƒ Vì dữ liệu được nén toàn bộ nên nếu sử dụng thuật toán nén tốt ta có thể nén nhỏ tối ưu. Khuyết điểm: ƒ Khi cần tra cứu một từ dữ liệu phải được giải nén toàn bộ kể cả những phần không cần thiết. Việc giải nén toàn bộ làm cho ứng dụng chậm và tốn không gian lưu trữ tạm không cần thiết. 5.2.2 Nén từng khối dữ liệu Ưu điểm: ƒ Dữ liệu được nén thành từng khối, khi cần truy xuất đển một mục từ nào ta chỉ cần giải nén khối nén chứa dữ liệu tương ứng với mục từ đó. Nhờ vậy mà thời gian giải nén và không gian lưu trữ tạm được giảm đáng kể. Khuyết điểm: ƒ Do dữ liệu được nén theo từng khối nên hiệu quả của việc nén từng khối sẽ thấp hơn hiệu quả của việc nén toàn bộ. Chương 5 . Các giải pháp chính cho việc xây dựng từ điển trên điện thoại di động Series 60 53 Như vậy chỉ có chiến lược nén từng khối với khuyết điểm có thể chấp nhận mới có thể đáp ứng yêu cầu vừa có thể nén được dữ liệu vừa có thể truy xuất ngẫu nhiên nhanh. Chiến lược nén từng khối dữ liệu đòi hỏi phải tổ chức một cấu trúc lưu trữ thích hợp để có thể truy xuất ngẫu nhiên nhanh. Cách thức nén và cấu trúc lưu trữ như thế được gọi là chuẩn nén. Hiện nay, trên thế giới chuẩn nén Dictzip được sử dụng rộng rãi nhất cho việc nén dữ liệu từ điển. 5.2.3 Chuẩn nén Dictzip Chuẩn nén Dictzip được giới thiệu lần đầu tiên vào năm 1996 bởi Rickard E.Faith, và được phát triển với nguồn mở. Chuẩn nén này có cách thức nén và cấu trúc lưu trữ lần lượt như sau. 5.2.3.1 Cách thức nén Dictzip dựa vào chuẩn nén Gzip với mục đích là các chương trình giải nén tập tin Gzip đều giải nén được tập tin Dictzip. Dictzip khác Gzip ở chỗ một phần thông tin mở rộng được thêm vào tập tin nén Gzip để lưu thêm thông tin về các khối nén. Các chương trình giải nén tập tin Gzip sẽ bỏ qua phần thông tin mở rộng này. Các chương trình đọc tập tin Dictzip sẽ đọc phần thông tin thêm này để có thể truy xuất ngẫu nhiên trong tập tin. 5.2.3.2 Cấu trúc lưu trữ Ý tưởng cơ bản của cấu trúc lưu trữ này là dữ liệu gốc sau khi nén sẽ thành các khối nén có kích thước tối đa là 64 KB. Nghĩa là Dictzip nén các khối khối dữ liệu (của tập tin ban đầu) không biết trước kích thước il thành các khối dữ liệu nén đã biết kích thước bl (bl tối đa 64KB). Khối cuối cùng có thể không có cùng kích thước với các khối trước. Kích thước của từng khối dữ liệu sau khi giải nén được lưu ở phần thông tin mở rộng thêm vào nói trên. Khi cần truy cập ngẫu nhiên ta dựa vào vị trí, kích thước cần đọc và thông tin đầu tập tin nén mà lấy ra các khối nén tương ứng và giải nén chúng. Chương 5 . Các giải pháp chính cho việc xây dựng từ điển trên điện thoại di động Series 60 54 Hình 5.1 Ý tưởng cấu trúc lưu trữ chuẩn Dictzip 5.2.4 Những khó khăn khi áp dụng Dictzip trên điện thọai di động Tuy nhiên việc áp dụng chuẩn nén Dictzip cho dữ liệu trên điện thoại di động gặp phải khó khăn sau: ƒ Hiện tại chưa có bộ thư viện nén Dictzip hoàn chỉnh cho môi trường lập trình trên điện thoại di động. Hầu hết các bộ thư viện nén này đều là mã nguồn mở, tính đúng đắn còn hạn chế, thiếu nhiều hàm quan trọng, một trong những hàm quan trọng là hàm nén các khối khối dữ liệu không biết trước kích thước thành các khối dữ liệu nén đã biết kích thước. ƒ Việc xây dựng bộ thư viện nén Dictzip hoàn chỉnh trên môi trường lập trình cho điện thoại di động tốn nhiều thời gian cho phép, đòi hỏi các thuật toán phức tạp. Một cách tiếp cận để giải quyết khó khăn trên là xây dựng một chuẩn nén theo từng khối khác. Chuẩn nén này được xây dựng với các hàm đơn giản hơn và phải đảm bảo tối ưu được kích thước nén và tốc độ truy xuất ngẫu nhiên phải nhanh. Chương 5 . Các giải pháp chính cho việc xây dựng từ điển trên điện thoại di động Series 60 55 5.2.5 Chuẩn nén Dictzip# Chuẩn nén Dictzip# được chúng em đề nghị để giải quyết khó khăn khi áp dụng Dictzip cho dữ liệu trên điện thoại di động. Chuẩn nén Dictzip# có cách thức nén và cấu trúc lưu trữ như sau. 5.2.5.1 Cách thức nén Tùy chọn bộ thư viện nén và giải nén. Trong chương trình ứng dụng của mình, chúng em sử dụng bộ thư viện mã nguồn mở zlib version 1.1.4. 5.2.5.2 Cấu trúc lưu trữ Hình 5.2 Ý tưởng cấu trúc lưu trữ chuẩn Dictzip# Ý tưởng cơ bản của cấu trúc lưu trữ này là dữ liệu gốc được chia thành từng khối có kích thước tối đa là 64 KB để nén. Kích thước của khối cuối cùng có thể không bằng với kích thước của các khối trước. Dictzip# nén các khối dữ liệu đã biết trước kích thước l ( l tối đa là 64KB) thành các khối nén có kích thước ibl (kích thước các khối nén của chuẩn Dictzip# không biết trước được, kích thước các khối nén của chuẩn Dictzip là một số cố định tối đa 64KB, đây chính là điểm khác nhau cơ bản giữa Dictzip# và Dictzip). Kích thước sau nén của từng khối dữ liệu sẽ được lưu vào thông tin đầu tập tin nén. Khi cần truy cập ngẫu nhiên ta dựa vào vị trí, kích thước cần đọc và thông tin đầu tập tin nén mà lấy ra các khối nén tương ứng và giải nén chúng. Chương 5 . Các giải pháp chính cho việc xây dựng từ điển trên điện thoại di động Series 60 56 5.2.5.3 So sánh tỉ lệ nén giữa Dictzip và Dictzip# So sánh kích thước tập tin dữ liệu đã nén của 3 loại từ điển thông dụng: Anh – Việt (68998 từ), Việt – Anh (91146 từ) và Anh – Anh (121962 từ). Các tập tin dữ liệu nén chuẩn DictZip lấy từ khóa luận “Xây dựng ứng dụng từ điện trên Pocket PC” của Nguyễn Thiện Chương và Phạm Tuấn Sơn (Th.S Nguyễn Tấn Trần Minh Khang và Th.S Trần Minh Triết hướng dẫn). Mỗi bộ dữ liệu DictZip gồm 3 tập tin (1 tập tin nghĩa, 2 tập tin chỉ mục) trong đó 2 tập tin chỉ mục chưa được nén. Để tiện so sánh, chúng em đã nén 2 tập tin chỉ mục này theo chuẩn DictZip rồi cộng kích thước của cả 3 tập tin lại. Tỉ lệ % là tỉ lệ kích thước tập tin nén so với tập tin gốc. Từ điển Kích thước chưa nén (KB) Kích thước tập tin DiztZip (KB) Kích thước tập tin DiztZip# (KB) Anh – Việt 11505 3994 (34.7%) 4363 (37.9%) Việt – Anh 5238 1827 (34.9%) 1993 (38.0%) Anh – Anh 22180 7486 (33.7%) 8121 (36.6%) Bảng 5.4 So sánh tỉ lệ nén giữa DictZip và Dictzip# Như vậy có thể thấy chuẩn nén DictZip và DictZip# không có nhiều sự khác biệt về tỉ lệ nén. 5.2.5.4 So sánh các khối nén trong chuẩn Dictzip# 5.2.5.4.1 Kích thước tập tin sau khi nén Từ điển 8 KB 16 KB 32 KB 64 KB Anh – Việt 4616 4363 4168 4029 Việt – Anh 2053 1993 1950 1916 Anh – Anh 8510 8121 7805 7558 Bảng 5.5 Kích thước tập tin sau khi dùng Dictzip# nén 5.2.5.4.2 Tốc độ truy xuất Từ điển Anh – Việt: (thời gian tính bằng mili giây) Khối nén Load từ điển Chuyển từ list ‘a’ sang ‘d’ Hiển thị nghĩa “a” lần đầu 8 KB 734 109 2953 16 KB 734 125 2968 32 KB 781 171 2984 64 KB 953 250 3015 Bảng 5.6 Tốc độ truy xuất từ điển Anh-Việt khi sử dụng Dictzip# Chương 5 . Các giải pháp chính cho việc xây dựng từ điển trên điện thoại di động Series 60 57 Từ điển Việt – Anh: (thời gian tính bằng mili giây) Khối nén Load từ điển Chuyển từ list ‘a’ sang ‘d’ Hiển thị nghĩa “a” lần đầu 8 KB 703 93 234 16 KB 718 109 250 32 KB 750 156 250 64 KB 953 218 281 Bảng 5.7 Tốc độ truy xuất từ điển Anh-Việt khi sử dụng Dictzip# 5.3 Tổ chức cấu trúc dữ liệu hỗ trợ cho việc tìm kiếm nhanh Đến thời điểm này, ta đã giải quyết được hai vấn đề cơ bản: vấn đề tổ chức cấu trúc lưu trữ và vấn đề nén dữ liệu. Ta vẫn còn một vấn đề nữa là tổ chức cấu trúc dữ liệu hỗ trợ cho việc tìm kiếm nhanh. Một số cấu trúc tập tin hỗ trợ cho việc tìm kiếm nhanh hiện nay là: ƒ Tập tin tuần tự: tập tin này là một tập các mẫu tin lưu trữ các bản ghi liên tiếp nhau. Việc tìm kiếm một mẫu tin có giá trị khoá K cho trước được thực hiện bằng cách so sánh từng khoá của từng mẫu tin trong tập tin. ƒ Tập tin chỉ mục: khi mẫu tin có kích thước lớn để làm tăng thêm hiệu quả thao tác trên các mẫu tin người ta sử dụng tập tin chỉ mục. Tập tin chỉ mục là tập tin chứa thông tin về vị trí của một mẫu tin trong một tập tin khác. Một cách hình thức, có thể xem tập tin chỉ mục là một tập tin phụ mà mỗi mẫu tin là một tập (K, i), với K là giá trị của khoá và i là địa chỉ của mẫu tin trong tập tin chính. Ta còn có thể gia tăng tốc độ tìm kiếm bằng cách xây dựng tập tin chỉ mục có thứ tự để tiến hành tìm kiếm nhị phân trên tập tin chỉ mục này. ƒ Tập tin băm: được sử dụng để giới hạn phạm vi tìm kiếm khi số lượng mẫu tin lớn. Thao tác băm chính là thao tác phân loại các khoá có cùng tính chất nào đó vào chung một cụm. ƒ Ta còn có thể đọc tất cả các mẫu tin chỉ mục rồi phát sinh ra cây tìm kiếm, sau đó lưu cây này lên một tập tin. Cách này khai thác được ưu điểm về tốc độ tìm kiếm của các loại cây tìm kiếm nhưng có nhược điểm Chương 5 . Các giải pháp chính cho việc xây dựng từ điển trên điện thoại di động Series 60 58 là chiếm nhiều bộ nhớ (kể cả bộ nhớ trong lần bộ nhớ phụ) cho việc lưu trữ cây. Theo thông kê đối với dữ liệu từ điển Anh – Việt gồm 68.998 từ thì ta cần khoảng 3,4 MB để tổ chức cây trong bộ nhớ. Qua việc xem xét các cấu trúc tập tin hỗ trợ cho việc tìm kiếm nhanh, ta thấy kết hợp phương pháp chỉ mục có thứ tự và băm tập tin nghĩa là thích hợp nhất cho việc tìm kiếm nhanh nhất. 5.3.1 Tổ chức tập tin nghĩa Như đã trình bày, phần nghĩa của từ sẽ có kích thước biến động. Để phần hiển thị nghĩa thêm sinh động, ta thêm phần định dạng font chữ và màu sắc. Do đó mỗi mẫu tin trong tập tin nghĩa sẽ bao gồm: ƒ Phần nghĩa thực sự của từ gồm các nghĩa con. Các nghĩa con này gồm phiên âm quốc tế (nếu có) và các nghĩa khác của từ. ƒ Các byte định dạng (font chữ và màu sắc) tương ứng với từng nghĩa con. Như vậy có bao nhiêu nghĩa con sẽ có bấy nhiêu định dạng tương ứng. Hình 5.3 Tổ chức tập tin nghĩa Chương 5 . Các giải pháp chính cho việc xây dựng từ điển trên điện thoại di động Series 60 59 5.3.2 Tổ chức tập tin chỉ mục Trong phần này ta sẽ trình bày cách thức chỉ mục cho các mẫu tin nghĩa trong tập tin nghĩa. Tập tin chỉ mục của tập tin nghĩa từ điển là một tập các mẫu tin chỉ mục có khoá là từ gốc của từ, các khoá được sắp theo thứ tự tăng dần của bảng chữ cái. Ngoài các thông tin về từ, từ loại, các mẫu tin chỉ mục còn phải lưu thêm thông tin về vị trí bắt đầu và chiều dài mẫu tin nghĩa vì các mẫu tin nghĩa có kích thước biến động. 5.3.2.1 Các trường dữ liệu trong mẫu tin chỉ mục STT Trường dữ liệu Kiểu dữ liệu Kích thước Ý nghĩa 1. Word Mảng ký tự Biến động Từ gốc 2. Attribute Byte 1 byte Tổ hợp các cờ quy định từ loại của từ: 9 Danh từ 9 Động từ 9 Tính từ 9 Trạng từ 9 Giới từ 9 Các từ loại khác 3. MeaningPosition Số nguyên không dấu 4 byte Vị trí mẫu tin nghĩa trong tập tin nghĩa 4. MeaningLength Số nguyên không dấu 2 byte Kích thước mẫu tin nghĩa Bảng 5.8 Các trường dữ liệu trong mẫu tin chỉ mục Hình 5.4 Cấu trúc mẫu tin chỉ mục Chương 5 . Các giải pháp chính cho việc xây dựng từ điển trên điện thoại di động Series 60 60 Khi tìm một từ, trước hết ta khoanh vùng phạm vi tìm kiếm (thao tác băm) để lấy ra đoạn buffer rồi phân tích ra thành các mẫu tin chỉ mục sau đó tiến hành tìm kiếm trên tập các mẫu tin chỉ mục đó. Theo bảng trên ta thấy trường dữ liệu Word (từ gốc của từ) có kích thước biến động, ta không thể phân tích mẫu tin chỉ mục bằng cách tạo thêm một tập tin chỉ mục nữa để lưu vị trí và chiều dài của mẫu tin chỉ mục trên vì biện pháp này không khả thi. Ta chỉ có thể đánh dấu vị trí kết thúc mỗi mẫu tin chỉ mục bằng một giá trị. Nếu ta chọn giá trị đánh dấu có kích thước là 1 byte thì mỗi từ trong từ điển sẽ được biểu diễn bởi 249 byte ( 256 trừ đi 1 byte attribute, 4 byte MeaningPostion và 2 byte MeaningLength) thì mỗi từ trong từ điển có không quá 120 ký tự nếu mỗi ký tự được biểu diễn bằng 2 byte. Việc phân tích buffer chứa các mẫu tin chỉ mục bây giờ là công việc tìm vị trí kết thúc mỗi mẫu tin chỉ mục. Hình 5.5 Các giá trị cần thiết để phân tích mục từ 5.3.3 Tổ chức băm tập tin chỉ mục Việc băm tập tin chỉ mục là nhằm mục đích thu nhỏ phạm vi tìm kiếm. Tiêu chí chọn hàm băm trong bài toán xây dựng từ điển được đề nghị theo thứ tự ưu tiên tăng dần trong bài viết này là: ƒ Sau khi băm, nếu lần lượt gộp các cụm mẫu tin chỉ mục lại thì kết quả phải là tập tin chỉ mục có thứ tự ban đầu. ƒ Việc tính toán cho hàm băm phải nhanh. ƒ Ít xảy ra đụng độ (giới hạn tốt không gian tìm kiếm). ƒ Các khoá được phân bố đều trong bảng băm. Chương 5 . Các giải pháp chính cho việc xây dựng từ điển trên điện thoại di động Series 60 61 Do tập tin chỉ mục của ta được tổ chức thành các mẫu tin tăng dần theo bảng chữ cái nên ta sẽ băm theo các chữ cái đầu của từ. Như vậy theo cách này, hàm băm của ta có thể đảm bảo được hai tiêu chí đầu tiên đã đề ra. Ta có thể băm một hay nhiều cấp tương ứng với một hay nhiều ký tự đầu của từ để có thể đáp ứng được hai tiêu chí còn lại. Thực nghiệm trên máy điện thoại di động thật (Nokia NGate QD và Nokia 7610) cho thấy khi số mục từ nạp lên listbox có giá trị > 2000 thì ta bắt đầu cảm nhận được thời gian nạp từ. Gọi: ƒ N là tổng số cụm. ƒ minS là số mục từ nhỏ nhất trong một cụm. ƒ _S là số mục từ trung bình trong một cụm. ƒ maxS là số mục từ lớn nhất trong một cụm. ƒ maxc là cụm ký tự xuất hiện nhiều nhất. ƒ 2000>S là số cụm có số mục từ > 2000. ƒ Size là kích thước bộ nhớ bị chiếm dụng bởi bảng băm tính bằng byte. Ta lần lượt xem xét các cách thức băm có thể được. 5.3.3.1 Băm cấp một Các từ có cùng một ký tự đầu tiên sẽ thuộc một cụm. Bảng thống kê sự phân bố các cụm trong bảng băm của các từ điển như sau: Từ điển N minS _S maxS maxc 2000>S %1002000 ×> N S Size (byte) Tin học 56 1 246.39 1405 “s” 0 0 336 Anh – Anh 38 1 3209.53 1325 “s” 19 50 228 Anh – Việt 29 1 2379.24 9406 “s” 17 57 174 Việt – Anh 68 1 1340.38 12813 “c” 14 21 408 Bảng 5.9 Bảng thống kê sự phân bố các cụm trong bảng băm cấp 1 Theo bảng trên ta thấy trung bình phân bố nhỏ nhất và lớn nhất trong một cụm là 246.39 và 12813. Phạm vi tìm kiếm vẫn còn rất lớn. Hơn nữa số cụm có số mục từ > 2000 chiếm khoảng 21% đến 57%, đều này sẽ gây cảm giác ứng dụng chạy chậm, ta cần phải phân hoạch nhỏ hơn nữa. Chương 5 . Các giải pháp chính cho việc xây dựng từ điển trên điện thoại di động Series 60 62 5.3.3.2 Băm cấp hai Các từ có cùng hai ký tự đầu tiên sẽ thuộc một cụm. Bảng thống kê sự phân bố trong bảng băm của các từ điển như sau: Từ điển N minS _S maxS maxc 2000>S %1002000 ×> N S Size (byte) Tin học 802 1 17.20 506 “co” 0 0 6416 Anh – Anh 608 1 200.60 4186 “ge” 7 1 4864 Anh – Việt 198 1 138.55 2328 “co” 3 2 594 Việt – Anh 1050 1 86.81 7626 “ng” 7 1 8400 Bảng 5.10 Bảng thống kê sự phân bố các cụm trong bảng băm cấp 2 Theo bảng trên ta thấy trung bình phân bố nhỏ nhất và lớn nhất trong một cụm là 17.20 và 7626. So với băm cấp một, phạm vi tìm kiếm và số cụm có số mục từ > 2000 đã giảm đáng kể. Tuy nhiên vẫn có thể gây cảm giác chậm đối với người sử dụng khó tính. 5.3.3.3 Băm cấp ba Các từ có cùng ba ký tự đầu tiên sẽ thuộc một cụm. Bảng thống kê sự phân bố trong bảng băm của các từ điển như sau Từ điển N minS _S maxS maxc 2000>S %1002000 ×> N S Size (byte) Tin học 3991 1 3.46 211 “com” 0 0 39910 Anh – Anh 3906 1 31.22 3800 “gen” 1 0.03 39960 Anh – Việt 3211 1 21.49 752 “con” 0 0 32110 Việt – Anh 3755 1 24.27 5984 “ngư” 2 0.05 37550 Bảng 5.11 Bảng thống kê sự phân bố các cụm trong bảng băm cấp 3 Theo bảng trên ta thấy trung bình phân bố nhỏ nhất và lớn nhất trong một cụm là 3.46 và 5984. So với băm cấp một và hai, phạm vi tìm kiếm và số cụm có số mục từ > 2000 đã giảm đi rất nhiều. Số lần làm chậm ứng dụng không đáng kể. 5.3.3.4 Băm cấp bốn Các từ có cùng bốn ký tự đầu tiên sẽ thuộc một cụm. Khi tiến hành băm theo cách này, tập tin chỉ mục sẽ bị chia quá vụn, kích thước bộ nhớ bị chiếm dụng bởi bảng băm sẽ gia tăng, điều này không cần thiết vì băm cấp ba đã dung hòa được kích thước bộ nhớ và thời gian nạp từ. Chương 5 . Các giải pháp chính cho việc xây dựng từ điển trên điện thoại di động Series 60 63 Từ điển N %1002000 ×> N S Size (byte) Tin học >> 3991 > 39910 Anh – Anh >> 3906 > 39960 Anh – Việt >> 3211 > 32110 Việt – Anh >> 3755 > 37550 Bảng 5.12 Bảng thống kê sự phân bố các cụm trong bảng băm cấp 4 5.3.3.5 Kết luận Như vậy, việc băm cấp một và cấp hai gây ra cảm giác ứng dụng chạy chậm khi nạp từ. Việc băm cấp bốn sẽ chia quá vụn tập tin chỉ mục và gia tăng kích thước bộ nhớ bị chiếm vụng một cách không cần thiết. Ta chỉ có thể băm cấp ba để có thể dung hoà đượcthời gian nạp t