Luận văn Xây dựng ứng dụng từ điển trên pocket pc

voke để truy cập đến registry. ∗ Nói “chủ yếu” là bởi vì có một số thư viện hướng mạng (network-oriented), gồm các thư viện socket và thư viện wininet.dll, hỗ trợ cả ANSI lẫn Unicode. KH OA C NT T – Đ H KH TN Chương 4. Các vấn đề khi xây dựng ứng dụng Từ điển trên Pocket PC 29 Chương 4 Các vấn đề khi xây dựng ứng dụng Từ điển trên Pocket PC Khi bắt đầu xây dựng bất cứ một ứng dụng nào thì một trong những điều đầu tiên cần quan tâm chính là các đặc tính của nó. Sau đó, ta cũng cần phải chú ý đến môi trường cài đặt ứng dụng để có thể nắm bắt được các khó khăn, hạn chế khi tiến hành cài đặt ứng dụng này. 4.1 Đặc trưng của một ứng dụng Từ điển Để xây dựng một ứng dụng Từ điển hiệu quả, ta cần quan tâm 2 đặc tính quan trọng sau đây: • Tốc độ xử lý nhanh. Có thể nói thao tác cơ bản nhất của một ứng dụng Từ điển là tra cứu. Do đó, việc tìm kiếm phục vụ cho thao tác tra cứu xảy ra hết sức thường xuyên, yêu cầu nhanh chóng hiện kết quả cho người sử dụng. • Dữ liệu lưu trữ lớn. Từy theo các loại Từ điển khác nhau mà có kích thước lưu trữ khác nhau. Nhưng nhìn chung, thường thì dữ liệu lưu trữ của một Từ điển là khá lớn. Bên cạnh đó, ta cũng cần quan tâm đến số lượng các phần tử trong một Từ điển. Ngoài ra yêu cầu dễ sử dụng cũng là một đặc tính quan trọng không chỉ riêng với ứng dụng Từ điển. Với những tính chất cơ bản trên, thì việc khảo sát các đặc trưng của Pocket PC, đồng thời phân tích các vấn đề phát sinh khi xây dựng một ứng dụng Từ điển trên Pocket PC là rất cần thiết để từ đó đưa ra những giải pháp phù hợp (sẽ được trình bày trong Chương 5). KH OA C NT T – Đ H KH TN Chương 4. Các vấn đề khi xây dựng ứng dụng Từ điển trên Pocket PC 30 4.2 Giới hạn về bộ xử lý Đặc điểm chung của các bộ xử lý trên thiết bị PDA là tiết kiệm pin, nhỏ gọn, nhất là không đòi hỏi các thiết bị giải nhiệt chuyên dụng. Ngoài ra, vì lý do tối ưu giữa chi phí sản xuất và nhu cầu sử dụng chủ yếu của các thiết bị PDA, bộ xử lý cho PDA thường có tốc độ thấp và không ứng dụng hoặc ứng dụng hạn chế một số công nghệ tăng tốc xử lý dùng cho các bộ xử lý Pentium.Pocket PC sử dụng một loại CPU khác với CPU thông thường. Máy Pocket PC 2002 sử dụng CPU StrongARM hoặc XScale của Intel. Các CPU này được gọi là các bộ xử lý RISC (Reduced Instruction Set Computer) vì nó chỉ thực hiện một lệnh trong một chu kì CPU. (Mỗi chu kì CPU trong một giây gọi là 1 Hertz hay 1 Hz). Máy PC thông thường của chúng ta sử dụng bộ xử lý CISC (Complex Instruction Set Computer), đòi hỏi nhiều chu kì CPU để xử lý một lệnh xác định. Do đó, các bộ xử lý RISC như StrongARM theo lý thuyết, có thể tính toán lên tới 206 triệu lệnh một giây nếu nó xử lý ở tốc độ 206 Mhz. Các bộ xử lý StrongARM và XScale cũng xử lý các lệnh 32bit, giống như PC thông thường. Tuy nhiên, lại có một khác biệt lớn trong việc xử lý kích thước lệnh. Bộ xử lý CISC cho phép lệnh có thể có chiều dài biến đổi, vì vậy, nó phải tính toán kích thước của dữ liệu cần đọc khi xử lý lệnh. Trong kiến trúc RISC, mỗi lệnh 32bit sẽ có 32 dữ liệu đi kèm. Vì vậy, bộ xử lý luôn biết được phải đọc bao nhiêu dữ liệu., đây là một điểm mạnh của kiến trúc này. Độ rộng của bus cùng với tốc độ bus cũng có một ảnh hướng lớn đến tốc độ xử lý và tính toán của máy tính. Độ rộng của bus chỉ ra số lượng bit (hay byte) dữ liệu có thể đọc từ / ghi lên RAM vào bộ vi xử lý. Còn tốc độ bus chỉ ra dữ liệu có thể được đọc từ RAM vào bộ vi xử lý với độ nhanh như thế nào. Ta có thể hình dung, độ rộng bus như số làn giao thông trên xa lộ, còn tốc độ bus như giới hạn về tốc độ khi lưu thông. Hiện nay, StrongARM và XScale sử dụng bus tốc độ 100Mhz và thiết kế hiện nay của Pocket PC cho phép dùng bus 16bit. Điều này có nghĩa là tốc độ bus tối đa là 200MB/giây. KH OA C NT T – Đ H KH TN Chương 4. Các vấn đề khi xây dựng ứng dụng Từ điển trên Pocket PC 31 Vấn đề đặt ra ở đây là như vậy, bộ vi xử lý có thể đạt được tốc độ xử lý bao nhiêu. Do chúng ta cần đọc 8bytes dữ liệu trước khi xử lý một lệnh, nên giả sử chúng ta có được tốc độ bus tối đa là 200MB/giây, thì thực sử, bộ xử lý chỉ thi hành được 25 triệu lệnh. Ngoài ra, lại có một vấn đề khác, đó là cache. Cache là một loại RAM đặc biệt được chứa bên trong CPU và xử lý với cùng tốc độ của CPU. Cache trong bộ xử lý StrongARM là 16K cho mã chương trình và 8K cho dữ liệu, cache trong XScale là 32K cho mã chương trình và 32K cho dữ liệu. Nếu dữ liệu và mã chương trình cần xử lý được chứa trọn trong cache, hệ thống sẽ có thể thi hành với tốc độ thật của CPU. Như vậy, tốc độ của ứng dụng có thể được thi hành sẽ có thể tăng từ 25 lên 206 triệu lệnh một giây, tuỳ theo chương trình và dữ liệu có vừa với kích thước cache không. Tốc độ của hệ thống cũng phụ thuộc vào nguồn cung cấp năng lượng, do đó, khi sử dụng Pocket PC, ta có thể nhận thấy sự khác biệt về tốc độ khi thực thi chương trình. Bây giờ, sử dụng các để so sánh về hiệu suất hoạt động giữa máy Desktop PC và Pocket PC. Xét các hệ thống Desktop PC sử dụng bus 100-133 Mhz. Pentium IV có thể sử dụng DDR RAM hoặc RAM BUS (RD RAM) có tốc độ từ 200-800Mhz. Vì vậy, chỉ xét trên phương diện RAM, nếu sử dụng RAM 133Mhz, hiệu suất Desktop PC đã tăng 1/3 lần (25 lên 33 triệu lệnh một giây). Tốc độ CPU của Desktop cũng lớn hơn rất nhiều khi hiện tại đã đạt tới tốc độ trên 3Ghz dẫn đến hiệu suất toàn hệ thống cao hơn. Khi xây dựng ứng dụng Từ điển trên Pocket PC, đặc điểm về bộ xử lý của Pocket PC ảnh hưởng rất lớn đến tốc độ xử lý, hiển thị các từ trong Từ điển cũng như nghĩa của chúng. Để giải quyết vấn đề này, ta cần có những giải pháp phù hợp để tăng hiệu năng của ứng dụng, giúp người sử dụng có thể sử dụng được chương trình với tốc độ chấp nhận được. KH OA C NT T – Đ H KH TN Chương 4. Các vấn đề khi xây dựng ứng dụng Từ điển trên Pocket PC 32 4.3 Giới hạn về bộ nhớ và khả năng lưu trữ Các Pocket PC thông thường có ROM ít nhất là 8MB, RAM ít nhất là 8MB. Các Pocket PC chuyên dụng có ROM ít nhất là 12MB, RAM ít nhất là 16MB. Tuy nhiên, yêu cầu về dung lượng của RAM và ROM tuỳ thuộc vào loại CPU sử dụng, những thành phần mà nhà sản xuất hỗ trợ trên Pocket PC và tuỳ thuộc vào loại Pocket PC. Do hạn chế về nguồn năng lượng pin và kích thước của thiết bị, Pocket PC không sử dụng các thiết bị lưu trữ như đĩa cứng hay đĩa mềm mà nó sử dụng một cơ chế gọi là Bộ lưu trữ đối tượng (Object store). Object store là một vùng RAM được người dùng định nghĩa, dùng để lưu trữ các tập tin, các thông tin registry và các database (gọi là Object Store dạng Storage). Vùng RAM còn lại dùng làm bộ nhớ cho các chương trình được thực thi (gọi là Object Store dạng Program). Object store vẫn lưu giữ được thông tin của các ứng dụng và dữ liệu ngay cả khi năng lượng cung cấp chính bị mất nhờ nguồn pin dự trữ. Có thể xem object store như là đĩa cứng trên thiết bị dùng Windows CE. Vì các end-user không biết về object store nên Microsoft đã cung cấp trình WinCE Explorer để đọc nội dung của nó (tương tự như Microsoft Windows Explorer để đọc nội dung của đĩa cứng trên máy desktop PC). Hình 4.1: Tình trạng bộ nhớ trên Pocket PC KH OA C NT T – Đ H KH TN Chương 4. Các vấn đề khi xây dựng ứng dụng Từ điển trên Pocket PC 33 Để cung cấp thêm khả năng lưu trữ cho Pocket PC (cũng nhu các thiết bị PDA khác), hấu hết các máy đều cho phép gắn thêm các thẻ nhớ (Flash Memory Card) đóng vai trò một bộ nhớ ngoài. Đặc điểm chung của các thẻ nhớ là có tốc độ chậm hơn nhiều so với bộ nhớ RAM nhưng giá thành rẻ và cơ động, có thể dùng chung cho các thiết bị điện tử khác. Ta có thể tận dụng khả năng lưu trữ của thẻ nhớ để giảm bớt hạn chế về khả năng lưu trữ của Pocket PC. Hình 4.2: Một số thẻ nhớ cho PDA Những hạn chế về bộ nhớ trên Pocket PC ảnh hưởng rất nhiều đến việc tổ chức dữ liệu Từ điển của ứng dụng. Giải pháp gắn thêm các thẻ nhớ để tăng khả năng lưu trữ cho Pocket PC là không khả thi do các thẻ nhớ có tốc độ chậm trong khi ứng dụng Từ điển lại có tần suất truy cập dữ liệu rất lớn, đòi hỏi tốc độ nhanh. Một giải pháp khác được đưa ra là nén dữ liệu Từ điển. Phương pháp này có vẻ khả thi hơn. Tuy nhiên, cái giá phải trả là phải truy cập dữ liệu nén. Điều này cũng ảnh hưởng nhiều đến tốc độ của ứng dụng. Vì vậy, việc dung hòa giữa tốc độ xử lý và dữ liệu lưu trữ của ứng dụng là một trong những vấn đề quan trọng nhất khi xâ dựng ứng dụng Từ điển trên Pocket PC. Chi tiết về việc giải quyết vấn đề này sẽ được trình bày cụ thể trong Chương 5. Ngoài ra, ta còn phải xem xét đến hình thức lưu trữ dữ liệu Từ điển. Trên Pocket PC, có 2 hình thức lưu trữ dữ liệu chính, đó là lưu trữ dưới dạng Tập tin và dưới dạng Cơ sở dữ liệu (xem chi tiết ở phần Phụ lục B ). Cũng như trên desktop, cơ sở dữ liệu thường được dùng để lưu các cấu trúc dữ liệu biến động, có nhu cầu KH OA C NT T – Đ H KH TN Chương 4. Các vấn đề khi xây dựng ứng dụng Từ điển trên Pocket PC 34 truy xuất phức tạp,…trong khi dữ liệu Từ điển lại có cấu trúc dữ tĩnh, truy xuất tương đối đơn giản Hơn nữa, cơ sở dữ liệu trên Pocket PC (SQLCE) chưa được sử dụng rộng rãi. Hiện nay, có rất ít ứng dụng sử dụng cơ sở dữ liệu trên Pocket PC. Do đó việc chọn tập tin là hình thức lưu trữ dữ liệu của ứng dụng Từ điển là hợp lý. 4.4 Hạn chế về khả năng tương tác giữa người dùng và thiết bị Hạn chế về khả năng tương tác người dùng tuy không làm cản trở đến hiệu quả thi hành chương trình nhưng lại gây khó khăn cho công việc thiết kế giao diện chương trình. Việc xác định rõ các hạn chế về khả năng tương tác người dùng giúp chúng ta xây dựng các ứng dụng trên Pocket PC thân thiện, tiện dụng với người dùng hơn. 4.4.1 Màn hình hiển thị nhỏ Do đặc tính nhỏ gọn, nên nên màn hình hiển thị của Pocket PC thường có kích thước nhỏ. Với màn hình quá nhỏ, sẽ rất khó để vừa hiển thị danh sách các từ và nghĩa của nó trong Từ điển, vừa bố trí tất cả các chức năng trên các thanh công cụ, thanh thực đơn. Giải pháp thường thấy trong các ứng dụng trên Pocket PC là sử dụng tối đa các popup menu, context menu, dropdown toolbar button để người dùng chọn lựa chức năng. Chỉ có các chức năng thường xuyên sử dụng mới được thiết kế nằm sẵn trên màn hình như chức năng tra nghĩa của từ, chức năng phát âm, … 4.4.2 Bàn phím Pocket PC không có bàn phím vật lý mà sử dụng một bàn phím ảo (Hình 2.2: Bàn phím ảo của Pocket PC). Khi được kích hoạt, bàn phím ảo sẽ chiếm một phần của màn hình (khoảng 1/3) và có thể sẽ che đi các nút chức năng, ô nhập liệu quan trọng. Các ứng dụng cho Pocket PC khi thiết kế phải lưu ý đến trường hợp này để có thiết kế giao diện phù hợp. Microsoft khuyến cáo các lập trình viên thiết kế các ô KH OA C NT T – Đ H KH TN Chương 4. Các vấn đề khi xây dựng ứng dụng Từ điển trên Pocket PC 35 nhập liệu (cần đến bàn phím) ở phía trên, tránh tình trạng khi bật bàn phím ảo để nhập liệu lại không thể nhìn thấy ô này. 4.5 Kết luận Sau khi phân tích các đặc tính của một ứng dụng Từ điển cũng như các hạn chế của Pocket PC, ta có thể đưa ra một số vấn đề cần phải giải quyết như sau: • Mâu thuẫn giữa yêu cầu xử lý nhanh của ứng dụng Từ điển với hạn chế về tốc độ xử lý của Pocket PC. • Mâu thuẫn giữa khối lượng dữ liệu lớn của ứng dụng Từ điển với hạn chế về khả năng lưu trữ của Pocket PC. • Mâu thuẫn giữa tính tiện dụng của chương trình và hạn chế về khả năng tương tác người dùng. Chương sau sẽ đưa ra giải pháp khả thi để giải quyết các vấn đề chính trên. KH OA C NT T – Đ H KH TN Chương 5. Một số giải pháp chính cho việc xây dựng ứng dụng Từ điển trên Pocket PC 36 Chương 5 Một số giải pháp chính cho việc xây dựng ứng dụng Từ điển trên Pocket PC Dữ liệu của ứng dụng Từ đỉển này được chuyển từ 2 bộ Từ điển Anh-Việt (68.998 từ) và Việt-Anh (91.146 từ) của phần mềm “English Study 4.0”. Những so sánh và khảo sát dưới đây đều dựa vào 2 bộ dữ liệu này. Các số liệu đo thử nghiệm được thực hiện trên máy Pocket PC HP Jornada 928, bộ nhớ 61.64 MB. Khi tổ chức lưu trữ dữ liệu cho ứng dụng Từ điển, ta phải giải quyết 2 vấn đề chính : • Tổ chức cấu trúc dữ liệu lưu trữ. • Tổ chức cấu trúc dữ liệu khác 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ữ Ứng dụng Từ điển có chứa khối lượng dữ liệu rất lớn. Dữ liệu này bao gồm số lượng lớn các mục từ lưu trữ liên tiếp trong tập tin. Các mục từ có kích thước động. Vấn đề đặt ra là các mục từ phải được lưu trữ hiệu quả và dễ dàng truy cập nhanh chóng. Ta lần lượt xét qua các cách tổ chức để chọn ra được cách tối ưu. 5.1.1 Tổ chức các mục từ có kích thước bằng nhau Cách tổ chức này qui định tất cả các mục từ đều có kích thước xác định bằng nhau. Cách này có ưu điểm là dễ dàng truy cập đến một mục từ khi biết thứ tự của nó nhưng có khuyết điểm lớn là gây lãng phí không gian lưu trữ. Các mục từ có kích thước biến động nhiều. Nếu ta đặt kích thước xác định cho tất cả các mục từ thì sẽ có rất nhiều mục từ không dùng hết phần kích thước đó và dữ liệu của ta có kích thước dư thừa, không hiệu quả. Ví dụ với dữ liệu Từ điển Anh –Việt, mục từ lớn nhất có kích thước 20.000 bytes được lấy làm kích thước cho tất cả các mục từ, suy ra kích thước của Từ điển này là 1.28 GB. Con số này là không thực tế cho ứng dụng Từ điển trên Pocket PC. KH OA C NT T – Đ H KH TN Chương 5. Một số giải pháp chính cho việc xây dựng ứng dụng Từ điển trên Pocket PC 37 5.1.2 Tổ chức các mục từ có kích thước biến đổi Các mục từ có kích thước biến đổi được lưu liêp tiếp sát nhau. Các mục từ được lưu với kích thước thực của chúng nên tránh được lãng phí như cách trên. Nhưng ta phải lưu thêm thông tin để truy cập đến chúng. Dữ liệu cho ứng dụng Từ điển này sẽ được lưu trữ theo cách này. Ví dụ với cách tổ chức này, Từ điển Anh – Việt có kích thước 10 MB và Từ điển Việt – Anh có kích thước 2.8 MB. 5.1.3 Nén dữ liệu Ứng dụng Từ điển trên Pocket PC yêu cầu kích thước lưu trữ dữ liệu càng nhỏ càng tốt. Nên ta phải tiến hành nén dữ liệu trên. Khi dữ liệu bị nén thì kích thước lưu trữ giảm xuống nhưng cũng làm giảm tốc độ truy xuất. Ta phải áp dụng phương pháp nén sao cho vẫn đảm bảo được tốc độ truy xuất hợp lý. Có 2 cách nén dữ liệu: • Nén toàn bộ: áp dụng các thuật toán như Zip, Gzip, Huffman… để nén toàn bộ tập tin dữ liệu. Ưu điểm của cách này là dữ liệu được nén nhỏ tối ưu. Nhưng khi yêu cầu truy cập đến các mục từ thì dữ liệu phải được giải nén toàn bộ nên làm ứng dụng chậm và tốn nhiều bộ nhớ cho lưu trữ dữ liệu giải nén. • Nén từng khối: dữ liệu được nén lại theo từng khối một. Khi cần truy xuất đến entry nào ta chỉ cần giải nén khối dữ liệu tương ứng. Nhưng do nén theo từng phần nên tỉ lệ nén sẽ thấp hơn nén toàn bộ. Ví dụ với dữ liệu Từ điển Anh – Việt được nén theo từng mục từ với thuật toán Zip sẽ có kích thước 8 MB, chỉ nén được khoảng 20%. Ta chỉ có thể áp dụng phương pháp nén từng khối. Ta phải áp dụng cách nén dung hòa giữa tỉ lệ nén cao và tốc độ truy cập dữ liệu ngẫu nhiên nhanh. Trong các chuẩn nén hiện nay, chuẩn nén Dictzip với đặc điểm nén dữ liệu theo từng khối và cho phép truy cập dữ liệu ngẫu nhiên nên thỏa yêu cầu ta đề ra. KH OA C NT T – Đ H KH TN Chương 5. Một số giải pháp chính cho việc xây dựng ứng dụng Từ điển trên Pocket PC 38 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. Nó được phát triển với nguồn mở và phiên bản mới nhất là 1.25. Cấu trúc lưu trữ: • Dictzip dựa vào chuẩn Gzip (tham khảo “Phụ lục C : Chuẩn nén Gzip”) nên hoàn toàn tương thích với Gzip. Một phần thông tin mở rộng được thêm vào tập tin nén Gzip để có thể lưu thêm dữ liệu vào phần đầu tập tin nén. Các chương trình giải nén tập tin Gzip đều giải nén được tập tin Dictzip nhưng chúng sẽ bỏ qua phần thông tin thêm này. Một số chương trình sẽ đọc phần thông tin thêm này và cho phép truy xuất dữ liệu ngẫu nhiên trong tập tin. • Cấu trúc phần thông tin thêm: o Khi bit FLG.FEXTRA được đặt (tham khảo “Phụ lục C : Chuẩn nén Gzip”), một trường mở rộng có kích thước XLEN được thêm vào phần đầu tập tin. o SI1, SI2 là 2 byte nhận dạng. Trong trường hợp này thì SI1 là ‘R’ và SI2 là ‘A’ (Random Access – Truy cập ngẫu nhiên). LEN lưu kích thước phần dữ liệu liền sau nó. Phần này có cấu trúc : o VER cho biết phiên bản của kiểu lưu dữ liệu. Với VER là 1 thì các giá trị được lưu dài 2 byte và là số nguyên không dấu. Dữ liệu khi nén được chia thành các khối có kích thước tối đa 64 KB.Trường CHLEN cho biết chiều dài của khối dữ liệu. Trường CHCNT cho biết số lượng khối dữ liệu đã lưu. Trường sau cùng (CHCNT words of data) cho KH OA C NT T – Đ H KH TN Chương 5. Một số giải pháp chính cho việc xây dựng ứng dụng Từ điển trên Pocket PC 39 biết kích thước của từng khối dữ liệu sau khi giải nén. Khi truy cập ngẫu nhiên, vị trí và kích thước dữ liệu được đưa vào và chương trình sẽ dựa vào đó để lấy được một hay nhiều khối dữ liệu tương ứng và giải nén chúng. Đặc điểm: • Kích thước lưu trữ: qua nhiều khảo sát với dữ liệu Từ điển dạng text, quá trình nén các khối 64KB với chế độ nén LZ77 cao nhất thì kích thước tập tin nén Dictzip chỉ lớn hơn 4% so với tập tin được nén hoàn toàn. Dưới đây là biểu đồ minh họa tỉ lệ nén của 2 bộ dữ liệu Từ điển Anh – Việt, Việt – Anh: 10 3,17 3,33 0 2 4 6 8 10 12 Kí ch th ướ c (M B) Chưa nén Nén Zip Nén Dictzip Hình 5.1: Biểu đồ nén dữ liệu Từ điển Anh – Việt 2,76 0,859 0,878 0 0,5 1 1,5 2 2,5 3 3,5 4 Kí ch th ướ c (M B ) Chưa nén Nén Zip Nén Dictzip Hình 5.2: Biểu đồ nén dữ liệu Từ điển Việt – Anh KH OA C NT T – Đ H KH TN Chương 5. Một số giải pháp chính cho việc xây dựng ứng dụng Từ điển trên Pocket PC 40 • Truy cập ngẫu nhiên: dữ liệu nén có thể được truy xuất ngẫu nhiên. Khi cần truy xuất, từng khối có kích thước tối đa 64KB tương ứng sẽ được đọc lên và giải nén. Vì vậy nó sẽ chậm hơn so với truy xuất dữ liệu trong tập tin không nén (không phải giải nén khi đọc) nhưng lại nhanh hơn nhiều so với truy xuất dữ liệu trong tập tin nén hoàn toàn (phải tốn 1 khoảng thời gian đáng kể để giải nén toàn bộ tập tin). Dưới đây là biểu đồ minh họa thời gian đọc dữ liệu của 100 từ ngẫu nhiên (theo thứ tự abc) trong Từ điển Anh – Việt được lưu trong tập tin không nén và tập tin nén bằng chuẩn Dictzip. 0 20 40 60 80 100 120 140 1 11 21 31 41 51 61 71 81 91 Từ Th ời g ia n (m s) Dictzip Không nén Hình 5.3: Biểu đồ thời gian đọc dữ liệu của tập tin không nén và tập tin nén chuẩn Dictzip Thời gian(ms) Cách lưu Lớn nhất Nhỏ nhất Trung bình Không nén 29 2 7,34 Nén Dictzip 128 1 26,90 Bảng 5.1: Thời gian truy xuất dữ liệu 100 từ ngẫu nhiên của Từ điển Anh – Việt KH OA C NT T – Đ H KH TN Chương 5. Một số giải pháp chính cho việc xây dựng ứng dụng Từ điển trên Pocket PC 41 Nhận xét: • Trong phần lớn các trường hợp, thời gian truy xuất tập tin nén Dictzip lớn hơn so với tập tin không nén. • Một số trường hợp truy xuất dữ liệu tập tin nén Dictzip nhanh hơn tập tin không nén. • Thời gian trung bình truy cập tập tin không nén là 7,34 ms và tập tin nén Dictzip là 26,9 ms. Tỉ lệ chênh lệch tương đối lớn nhưng khoảng thời gian chênh lệch là rất nhỏ (19,56 ms) và có thể chấp nhận được. Kết luận: chuẩn nén Dictzip đã thỏa mãn các yêu cầu mà ta đề ra là dữ liệu được tổ chức sao cho dung hòa giữa tỉ lệ nén cao và tốc độ truy cập ngẫu nhiên nhanh. Do đó dữ liệu của ứng dụng Từ điển này sẽ được lưu trữ theo chuẩn nén Dictzip. 5.2 Tổ chức cấu trúc dữ liệu hỗ trợ tìm kiếm nhanh Để truy xuất đến dữ liệu Từ điển được lưu và nén dạng Dictzip trên, ta cần lưu thông tin về vị trí và chiều dài dữ liệu của từng từ. Phần thông tin này sẽ được tổ chức lưu trữ chung với những thông tin khác như từ, từ loại...Vấn đề đặt ra là ta phải tổ chức lưu trữ hợp lý để truy xuất được hiệu quả và đảm bảo yêu cầu tốc độ cho ứng dụng Từ điển. 5.2.1 Tổ chức lưu trữ tập tin chỉ mục Tập tin chỉ mục là tập tin có chứa thông tin về vị trí của 1 mẩu tin trong 1 tập tin khác (thường có kích thước lớn hơn nhiều so với tập tin chỉ mục) để giúp cho việc truy xuất các mẩu tin này được dễ dàng và nhanh chóng. Ta sẽ tổ chức 1 tập tin chỉ mục để hỗ trợ việc truy xuất tập tin dữ liệu Từ điển. Các thông tin như từ, từ loại, vị trí, kích thước dữ liệu được tổ chức thành các mẩu tin và lưu trữ tuần tự. KH OA C NT T – Đ H KH TN Chương 5. Một số giải pháp chính cho việc xây dựng ứng dụng Từ điển trên Pocket PC 42 Từ Từ loại Vị trí nghĩa Kích thước nghĩa Nghĩa Vị trí nghĩa Kích thước nghĩa File chỉ mục File nghĩa Mẩu tin ... Mẩu tin i Hình 5.4: Tổ chức tập tin chỉ mục hỗ trợ truy xuất tập tin dữ liệu Từ điển Để truy xuất nghĩa 1 từ, ta tiến hành tìm kiếm trong tập tin chỉ mục để lấy ra được mẩu tin tương ứng. Từ vị trí nghĩa và kích thước nghĩa trong mẩu tin này, ta đọc được phần nghĩa trong tập tin dữ liệu nghĩa của Từ điển. Tốc độ tra cứu từ của ứng dụng Từ điển phụ thuộc vào cách truy xuất tập tin chỉ mục này. Ta có thể áp dụng các cách sau: • Tiến hành tìm kiếm tuần tự trên tập tin chỉ mục để lấy ra được mẩu tin thích hợp. Cách này có độ phức tạp là O(n), rất chậm, không tối ưu và không đáp ứng yêu cầu tốc độ của ứng dụng. • Đọc tất cả các mẩu tin và xây dựng thành một cây tìm kiếm. 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 là chiếm rất nhiều bộ nhớ cho việc lưu trữ cây. Ví dụ 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ớ. Với dung lượng bộ nhớ giới hạn của Pocket PC thì cách này không thể áp dụng được. • Băm nhỏ tập tin chỉ mục để thu hẹp phạm vi tìm kiếm. Sau đó tiến hành tìm kiếm trên vùng vừa giới hạn. KH OA C NT T – Đ H KH TN Chương 5. Một số giải pháp chính cho việc xây dựng ứng dụng Từ điển trên Pocket PC 43 Trong 3 cách trên thì giải pháp băm là hiệu quả nhất cho vấn đề ta đặt ra. Với giải pháp băm, phạm vi tìm kiếm được giới hạn nên thỏa mãn yêu cầu tiết kiệm bộ nhớ và tốc độ tìm kiếm. Vậy ta phải tiến hành băm tập tin chỉ mục này để giải quyết vấn đề tốc độ tra cứu từ của ứng dụng. 5.2.2 Tổ chức băm tập tin chỉ mục Băm tập tin chỉ mục nhằm làm nhỏ phạm vi tìm kiếm. Do tập tin chỉ mục của ta được tổ chức thành các mục từ tăng dần theo thứ tự abc nên ta sẽ băm theo các chữ cái đầu của từ. Ta có thể tiến hành băm 1 hay nhiều cấp tương ứng với 1 hay nhiều kí tự đầu của từ. Ta thử xem xét các khả năng: • Băm 1 cấp: các mục từ có cùng 1 kí tự đầu tiên sẽ thuộc 1 nhóm. Với Từ điển Anh – Việt 68.998 từ bắt đầu bằng 26 chữ cái thì trung bình mỗi nhóm phân hoạch sẽ có 265426998,68 = từ. Phạm vi tìm kiếm vẫn còn rất lớn. Ta nên phân hoạch nhỏ hơn nữa. • Băm 2 cấp: các mục từ có cùng 2 kí tự đầu tiên sẽ thuộc 1 nhóm. Tương tự như trên thì trung bình mỗi nhóm phân hoạch có 10226998,68 2 = từ. Phạm vi tìm kiếm đã được giới hạn đáng kể. • Băm 3 cấp: các mục từ có cùng 3 kí tự đầu tiên sẽ thuộc 1 nhóm. Tương tự như trên thì trung bình mỗi nhóm phân hoạch có 426998,68 3 = từ. Phạm vi tìm kiếm là rất nhỏ. Cách này không thể áp dụng được vì tập tin chỉ mục bị chia quá vụn ,việc duy trì bảng băm tốn nhiều bộ nhớ, bảng băm xuất hiện quá nhiều tổ hợp 3 kí tự vô nghĩa và rất dễ biến động khi ta thêm từ mới. Nhận xét: • Ta chỉ có thể băm tập tin chỉ mục theo 1 cấp hay 2 cấp. KH OA C NT T – Đ H KH TN Chương 5. Một số giải pháp chính cho việc xây dựng ứng dụng Từ điển trên Pocket PC 44 • Mỗi phần tử trong bảng băm bao gồm khóa là 1 kí tự (2 byte) hay 2 kí tự (4 byte), vị trí bắt đầu (4 byte) và kích thước (4 byte) của các mục từ trong tập tin chỉ mục tương ứng với khóa. • Xét cụ thể Từ điển Anh – Việt trên: o Bảng băm 1 cấp có kích thước lưu trữ là (2+4+4)*26 = 260 byte với phạm vi tìm kiếm trong tập tin chỉ mục là 2654 từ. o Bảng băm 2 cấp có kích thước lưu trữ là (4+4+4)*26*26 = 8112 byte với phạm vi tìm kiếm trong tập tin chỉ mục là 102 từ. Mặc dù bảng băm 2 cấp có kích thước lớn hơn nhiều so với băm 1 cấp nhưng kích thước lưu trữ của nó vẫn là rất nhỏ (tương đương 8 KB). Như vậy, băm 2 cấp sẽ hiệu quả hơn băm 1 cấp. Ta sẽ áp dụng cách băm 2 cấp cho tập tin chỉ mục. Hình dưới đây minh họa các tìm kiếm 1 từ trong tập tin chỉ mục với bảng băm 2 cấp : g o o d g ... o ... Vị trí chỉ mục Kích thước chỉ mục Khóa Vị trí chỉ mục Kích thước chỉ mục Bảng băm File chỉ mục Từ go... go... go... ... ... Hình 5.5: Cách tìm kiếm chỉ mục của 1 từ với bảng băm 2 kí tự KH OA C NT T – Đ H KH TN Chương 5. Một số giải pháp chính cho việc xây dựng ứng dụng Từ điển trên Pocket PC 45 Cách tìm kiếm 1 từ : • Từ 2 kí tự đầu