Đề tài Xây dựng một số công cụ hổ trợ tra cứu và tổng hợp thông tin trong thư viện số

Đề tài: Xây dựng một số công cụ hổ trợ tra cứu và tổng hợp thông tin trong thư viện số 1-1 CHƯƠNG 1 TỔNG QUAN 1.1. Thư viện số Thư viện số là thư viện phục vụ thông tin điện tử ( được số hóa) - được đọc với sự trợ giúp của máy vi tính. Thông tin điện tử có thể được chứa trong những Tư liệu điện tử nằm trong và ngoài thư viện. Tư liệu điện tử bao gồm: • CD-ROM và băng từ - CD-ROM thường chứa những CSDL chuyên ngành, được phục vụ riêng lẻ hay trên mạng máy tính. • Tạp chí điện tử - ấn hành trên mạng Internet. Thư viện có thể đặt mua như tạp chí in và sẽ được cấp quyền login vào để truy cập. • Cơ sở dữ liệu trực tuyến - có rất nhiều trên mạng Internet do những trường đại học, những cơ sở thông tin, và những công ty tư nhân như LEXIX- NEXIX, DIALOG, vv... - Cũng như tạp chí điện tử, thư viện có thể đặt mua quyền sử dụng. • Tài liệu khác trên Internet - tài liệu trong những web site của những cơ sở chính quyền, trường đại học, công ty, hội đoàn, vv... Việc truy cập thường là miễn phí. Thông tin điện tử đôi khi còn bao gồm tư liệu được số hóa, tập hợp dưới hình thức Thư viện số. Tư liệu được số hóa trước tiên là tranh ảnh, tài liệu quý hiếm, vv... Ngày nay nhiều thư viện có khuynh hướng số hóa đại bộ phận tư liệu trong thư viện để phục vụ dưới dạng điện tử. 1.2. Nghiên cứu về thư viện số tại Mỹ Vấn đề nghiên cứu về thư viện số là một trong 5 hướng nghiên cứu chủ yếu về CNTT của Mỹ hiện nay. Những tiến bộ cực kỳ nhanh chóng của kỹ thuật tính toán và mạng máy tính làm cho một tư liệu chỉ trong nháy mắt đã có thể “nhân bản” và chuyển tới hành trăm triệu người trên khắp thế giới. Năm 1994, người ta đưa ra một vấn đề gọi là SÁNG KIẾN THƯ VIỆN SỐ (SKTVS) mà ngày nay gọi là DLI pha 1. SKTVS pha 1 tập trung làm sáng tỏ từng 1-2 bước các vấn đề về mô hình quan niệm, cấu trúc, những thách thức về tính toán nhằm tạo ra các các kho tri thức nhân loại dạng điện tử. Trong 5 năm, SKTVS pha 1 đã có những thành công bước đầu mà chúng ta đang chứng kiến, chẳng hạn đó là các công cụ tìm kiếm nổi tiếng trên Internet. SKTVS pha 2 – DLI pha 2 bắt đầu từ 1999 và đã thu hút rất nhiều nhà khoa học và kỹ sư CNTT, các nhà nghiên cứu của nhiều ngành KHXH, nghệ thuật, sinh học…Mục tiêu là phát triển các nguồn tư liệu số, thử nghiệm liên kết giữa các nguồn tư liệu phân tán, thiết lập nguyên tắc, phần mềm và cấu trúc mạng có khả năng liên hợp các tư liệu đa phương tiện thành các bản ghi nhất thể, giải quyết vấn đề ngữ nghĩa hiện đang cản trở việc tích hợp tư liệu số từ các tư liệu từ các sưu tập phân tán và rất khác nhau về cấu trúc. Pha 2 của SKTVS tập trung vào 3 hướng nghiên cứu lớn sau: • Human-centered research-nghiên cứu hỗ trợ việc tạo ra thông tin và sử dụng thông tin. • Content and collections-tạo lập thư viện số chứa đựng các dạng tri thức. • System-centered research-các vấn đề kỹ thuật, phần mềm, phân loại khi tổ chức và liên kết các bộ dữ liệu số dạng thức khác nhau thông qua Internet. Để hình dung rõ hơn về 3 hướng nghiên cứu trên, chúng ta sẽ lược qua các dự án chính, các vấn đề quan trọng nhất của 3 hướng nghiên cứu và triển khai này. 1.2.1.Human-centered research (nghiên cứu hướng nguời dùng) Trong hướng này, có các dự án và chương trình lớn: Personalized Retrieval and Summarization of Image, Video, and Language Resources (PERSIVAL). Trong dự án PERSIVAL, các nhà nghiên cứu ở Đại học Columbia đang thử nghiệm thiết kế hệ thống giúp cho các bệnh nhân truy cập dễ dàng và nhanh chóng đến các nguồn thông tin y học trực tuyến thích hợp cho từng người bệnh. Digital resource designed for children. Các nhà nghiên cứu ở Đại học Maryland phát triển các công cụ thích hợp cho phép nghe, xem, tìm kiếm, hỏi đáp 1-3 và tổ chức thông tin nghe, nhìn, văn bản…cho trẻ em. Technologies and tools for students. Nhiều đại học và cơ quan nghiên cứu như Đại Học Quốc Gia Georgia, Hiệp Hội Máy Tính (Association for Computing Machinery-ACM), Ủỵ Ban Giáo Dục của SIGGRAPH (SIGGRAPH Education Committee) đang phát triển các kỹ thuật và công cụ cho sinh viên để việc truy cập thông tin trực tuyến phục vụ học tập ở đại học được hiệu quả. Video information college. Dự án được triển khai tại Đại Học Carnegie Mellon nhằm thiết lập môi trường làm việc với các tư liệu video, văn bản, ảnh và âm thanh. Alexandria Digital Earth prototype (ADEPT). Đây là một bộ phận của chương trình hợp tác về thư viện số giữa Đại học Berkeley, Đại học Santa Barbara (UCSB), Đại học Stanford, Trung tâm Siêu Máy Tính San Diego và Thư Viện Số California, liên quan chủ yếu đến việc sử dụng các loại thông tin không gian, thư mục hóa chúng, những vấn đề tìm kiếm trên Web… http:/www.alexandria.ucsb.edu/adept/ 1.2.2. Content and collections (Nội dung và các bộ sưu tập) Hướng này tập trung nghiên cứu việc tổ chức các kho thông tin về mọi lĩnh vực tri thức. Một số dự án lớn có thể kể đến như: Digital Library for the humanity. Đại Học Tuffs hợp tác với viện Max Planck ở Berlin, Hội Ngôn Ngữ Hiện Đại (the Modern Language Association), Bảo Tàng Nghệ Thuật Boston (the Boston Museum of Fine Arts) và Tổ Hợp Xuất Bản Điện Tử Stoa (the Stoa electronic pubishing consortium) phát triển một thư viện điện tử chứa các tư liệu từ thời Ai Cập cổ đại đến thế kỷ 19. National Gallery of Spoken Word (NGSW). Đại Học Quốc Gia Michigan đang thực hiện một thư viện các bài nói lịch sử suốt thế kỷ 20 với các công cụ xử lý hiệu quả. 1-4 National digital library for science, mathematics, engineering, ang technology education (SMETE). Đại Học Berkeley California phát triển một thư viện số tập hợp các ngành khoa học, toán học và công nghệ hỗ trợ việc học tập ở bậc phổ thông trung học. Digital Atheneum. Đại Học Kentucky được Quỹ Khoa Học Quốc Gia tài trợ phối hợp với Thư Viện Anh và Chương Trình Shared University Research của IBM đang làm việc với kho tư liệu của Thư Viện Anh chứa đựng các tư liệu cổ của Hi Lạp, Do Thái từ thế kỷ 17. Digital workflow management. Hơn 29.000 ngàn bản nhạc Mỹ từ 1790 đến 1960 đang được Đại Học Hopkins chuyển thành một thư viện số. Data provenance. Các nghiên cứu tại Đại Học Pennsylvania hướng tới vấn đề nan giải bậc nhất của các tập hợp dữ liệu trực tuyến. Đó là độ trung thực của một bản tin số và những vấn đề liên quan, có thể xếp vào nhóm các vấn đề hệ thống được trình bày dưói đây. 1.2.3.System-centered research (nghiên cứu hướng hệ thống ) Phát triển các thư viện số đòi hỏi phải giải quyết rất nhiều vấn đề về hệ thống. Có thể nêu vài cái trong số các vấn đề quan trọng mà các nhà khoa học Mỹ đang tập trung giải quyết: New model for scholarly publishing. Bản chất vấn đề là việc xuất bản bây giờ khác xa cách in ấn truyền thống. Xuất bản tức thời, phân tán, liên tục… Mọi quy trình đều phải thay đổi thích hợp để thực hiện việc “xuất bản” trên các hệ thống tính toán phân tán. Vấn đề đang được Đại Học Berkeley California nghiên cứu. Classification systems. Một trong những vấn đề kỹ thuật phức tạp nhất của thư viện là phân loại tư liệu. Mọi công cụ lưu trữ, tìm kiếm đều rất phụ thuộc vào kỹ thuật phân loại. Với các thư viện số chứa đựng, tích hợp mọi dạng thức thông tin, tri thức thì vấn đề càng phức tạp. Rất nhiều đại học và các viện nghiện cứu đang 1-5 tập trung cho vấn đề này. Có thể xem trong Web site: Security, quality, access, and reliability. Với thư viện số thì an toàn, bảo mật, chống sao chép bất hợp pháp, kỹ thuật tìm kiếm… còn chứa đựng rất nhiều vấn đề mở. Chẳng hạn ở Đại Học Cornell, các nhà nghiên cứu đang tập trung cho tính toàn vẹn của một thư viện số. 1.3. Nghiên cứu về thư viện số tại Việt nam Ở Việt nam, các nghiên cứu về thư viện số mới chỉ ở các buớc khởi đầu. Trong những năm qua nhiêề phần mền quản lý thư viện và hỗ trợ đọc sách trên Internet đã được đầu tư phát triển. Bảng 1.1 là đặc tính của một số phần mềm quản lý thư viện do các nhà sản xuất phần mềm trong nước phát triển. Bảng 1.1. Danh sách một số phần mền quản lý thư viện do các nhà sản xuất phần mềm Việt nam phát triển Tên thuộc tính LIBOL (Tinh Vân) ILIB (CMC Soft) VEBRARY (Lạc Việt) Mô tả Phát triển vì nhu cầu trong nước (1997) và sau đó được thay đổi theo các chuẩn quốc tế Có giao diện dạng Web và được thiết kế theo mô hình mở 3 lớp. Đây là hệ thống quản lý thư viện điện tử, được dùng đầu tiên tại Trung Tâm Thông Tin Tư Liệu Đại Học Đà Nẵng Hệ điều hành WinNT, Unix, Linux Cơ sở dữ liệu NA Oracle 8i đối với phiên bản lớn SQL-Server đối với phiên bản nhỏ SmiLib NA Hỗ trợ tiếng Việt Hỗ trợ tiếng Việt mà một số ngôn ngữ khác như Anh, Nga, Nhật, Hoa, hỗ trợ Unicode Hỗ trợ đa ngôn ngữ, trong đó tiêng Việt theo bảng mã Unicode và TVCN Hỗ trợ tìm kiếm Tìm kiếm tra cứu mạnh, hỗ trợ tất cả các khung phân loại Hỗ trợ tìm kiếm tra cứu theo nhiều tiêu chí khác nhau Các chức năng chuyên môn Môi trường hiển thị: Web Chuẩn giao tiếp dữ liệu ISO2709 Hỗ trợ tra cứu liên thư viện qua chuẩn Z39.50 Có khả năng tùy biến giao diện Có 8 phân hệ nhgiệp vụ chuyên môn: tra cứu (Z39.50), , biên mục, ấn phẩm điện tử, ấn phẩm định kỳ, phân hệ bổ sung, phân hệ quản lý, phân hệ bạn đọc và phân hệ mượn trả. Hỗ trợ tôi đa khả năng liên thư việ theo các chuẩn (MARC, USMARC, UNIMARC Cho phép tra cứu liên thư viện theo chuẩn Z39.50 Có chức năng hỗ trợ mã vạch Cho phép thay đổi các module khác nhau qua các thông số Mọi thao tác trên thư viện đều qua trình duyệt Web Lưu trữ và lập chỉ mục với số lượng lớn các dạng tài liệu SGML, XML, MARC, RTF, các dạng tài liệu đa phương tiện theo chuẩn open-ebook của W3C Hỗ trợ các tiêu chuẩn về sách điện tử và thư viện như Z39.50, Unicode… Biên mục theo chuẩn MARC, ÚMARC (ngầm định là MARC21) Có nhiều tính năng khác như bổ sung tài liệu, lưu thông tài liệu, quản lý xuất bản phẩm nhiều kỳ, mượn liên thư viện, báo cáo thống kê. Tính năng bảo mật đáng lưu ý. Nhận xét Có khả năng đáp ứng hầu hết các nhu cầu chuẩn hóa về nghiệp vụ Thân thiện với người dùng, chức năng tìm kiếm nhanh chóng, chính xác trên nhiều ngôn ngữ và nhiều tiêu chí Có tính mở và linh hoạt Đã được ứng dụng tại một số nơi như Học Viện Quan hệ Quốc tế… Tuân thủ những tiêu chuẩn mở về hệ thống thư viện và được xây dựng trên nền công nghệ hiện đại, quản lý thư viện hiệu quả, có khả năng liên thông với các thư viện khác trên thế giới. 1-6 Thông tin liên lạc Cty Công nghệ Tin học Tinh Vân 371 Kim Mã, Hà NộI ĐT: (4) 771 5737 dlin@hn.cmc.com.vn Cty CMC Soft 777 GiảI Phóng, Hà NộI ĐT: (4) 664 1595 vebrary@lacviet.com.vn Cty Cổ phần Tin học Lạc VIệt 191A Hoàng Văn THụ, q. Phú Nhuận, tp. Hồ Chí Minh ĐT: (8) 842 3333 Fax: (8) 842 2370 1.4. Mục tiêu nghiên cứu của đề tài Các nghiên cứu-ứng dụng CNTT vào quản lý và khai thác thông tin trong các thư viện đã và đang được quan tâm. Sự phát triển nhanh chóng của CNTT và Internet vào những thập niên sau của thế kỷ 20 đã tạo ra lượng thông tin khổng lồ. Các thư viện số hóa đã được hình thành và hiện đang lưu trữ một lượng lớn thông tin, dễ dàng truy cập qua Internet. Do đó cần phải xây dựng các công cụ hỗ trợ tổ chức, tìm, đọc, tổng hợp thông tin. Những năm qua, nhiều thư viện và các trung tâm lưu trữ trong nước đã có những bước phát triển đáng kể trong việc sử dụng các công cụ CNTT để quản lý tư liệu, độc giả và hỗ trợ công tác tra cứu thông tin. Tuy nhiên hướng nghiên cứu phát triển các công cụ hỗ trợ tìm kiến, phân tích, tổng hợp thông tin vẫn đang còn chưa được đầu tư phát triển. Ngoài nuớc, nhóm nghiên cứu về thư viện số thuộc Đại học Arizona ở địa chỉ trang web là là một trong các nhóm thức đẩy các 1-7 nghiên cứu nhằm phát triển các kỹ thuật phân loại tư liệu hỗ trợ tìm đọc và tổng hợp thông tin. Đề tài “Xây dựng một số công cụ hỗ trợ tra cứu và tổng hợp thông tin trong thư viên số “ tập trung vào các nội dung sau: • Nghiên cứu nhu cầu khai thác thông tin của độc giả trong một số thư viện số hóa tiêu biểu như thư viện cao học trường ĐHKHTN; thư viện sách điện tử thuộc chương trình đào tạo từ xa ĐHQG-HCM làm cơ sở cho việc áp dụng trong các thư viện khác. • Nghiên cứu đề xuất qui trình tổ chức thông tin hỗ trợ tiến trình sưu tầm, tổ chức và khai thác thông tin trong các thư viện số hóa và xây dựng hệ thống phần mềm hỗ trợ qui trình. • Nghiên cứu và xây dựng các công cụ phần mềm hỗ trợ tìm kiếm, phân tích tổng hợp thông tin trong các thư viện số hóa. Giai đoạn 1: từ tháng 12/2001 đến 7/2002 • Nghiên cứu các nhu cầu khai thác thông tin trong thư viện số • Nghiên cứu đặc trưng của thông tin tư liệu • Nghiên cứu các công nghệ sưu tầm, tổ chức thông tin theo tiếp cận tác nhân thông minh, phân lớp gom cụm • Thiết kế hệ thống và cài đặt một số phần mềm phân lớp gom cụm Giai đoạn 2: Từ 08/2002 đến 3/2003 • Nghiên cứu công nghệ tìm kiếm thông tin theo tiếp cận tác nhân thông minh • Cài đặt một số phần mềm phân lớp, gom cụm, hỗ trợ tra cứu thông tin 1.5. Các kết quả đạt được của đề tài • Xây dựng khung tiêu đề đề mục Việt, Anh , từ điển từ đồng hiện CNTT • Xây dựng công cụ Search và Download • Xây dựng công cụ tìm các dãy từ phổ biến để đặc trưng văn bản • Xây dựng công cụ tổng hợp văn qua gom cụm bằng mạng Kohonen • Xây dựng thư viện số trên Web với hàng ngàn bài báo khoa học. Phát triển truy vấn thư viện qua từ khóa, qua tiêu đề đề mục, qua từ đồng hiện, qua lớp ra Kohonen trên giao diện Web. 2-1 CHƯƠNG 2 TỔ CHỨC KHAI THÁC THÔNG TIN THƯ VIỆN 2.1. Tổ chức phục vụ khai thác thông tin Bước qua giai đoạn quản lý tư liệu đã tồn tại nhiều thế hệ, đến giai đoạn quản lý thông tin đã đặt ra cho nghề thư viện vấn đề trao đổi và chia sẻ thông tin. Đây là bước ngoặt quan trọng trong nghề thư viện, đồng thời việc ứng dụng triệt để thành tựu CNTT đã đặt ra một thách thức cho nghề thư viện là phải nhanh chóng thay đổi quan niệm ngành nghề đề đối phó với với sự phát triển như vũ bảo của CNTT. Ngày nay lượng thông tin dồi dào trở nên quá tải, CNTT lại giúp người ta chọn lọc thông tin có ích và có ý nghĩa được gọi là tri thức và CNTT đồng thời cũng giúp người ta tự hình thành tri thức – Đây là giai đoạn quản lý tri thức. Ngày nay để đánh giá một thư viện, người ta cho rằng: “Giá trị thư viện không phải ở chỗ thư viện có bao nhiêu nguồn thông tin mà là thư viện đáp ứng nhu cầu thông tin một cách có hiệu quả như thế nào từ rất nhiều nguồn thông qua công nghệ mới”; Trong một quan niệm mới khác về thư viện, người ta cho rằng “Chuyên môn cốt lõi của nghề thư viện là điểm giao nhau của ba mặt: thông tin, công nghệ thông tin và người sử dụng”. Hiểu biết về nguồn thông tin và cách tổ chức thông tin là năng lực quan trọng của cán bộ thư viện. Nghiệp vụ thư viện cho chúng ta biết cách thu thập thông tin – biểu thị qua công tác quản lý và phương thức truy hồi thông tin; biết cách tổ chức thông tin – biểu thị qua công tác phân loại, biên mục, chỉ mục và thiết lập cơ sở dữ liệu; biết cách lưu trữ thông tin – biểu thị qua công tác quản lý vật lý nguồn thông tin và các hoạt động tìm kiếm. Nói chung, người cán bộ thư viện phải biết cách tạo điều kiện để người sử dụng truy cập được thông tin. Công nghệ thông tin và truyền thông đã có ảnh hưởng trong 20 năm qua và ngày nay đang có khả năng thay đổi cuộc sống của chúng ta về mọi mặt. Động lực thay đổi quan trọng nhất chính là thông tin. Công nghệ thông tin mở rộng bốn bức tường của thư viện nhằm cung cấp nguồn thông tin trong thư viện ra ngoài, đồng thời cung 2-2 cấp nguồn tư liệu ngoài phạm vi thư viện cho người sử dụng trong thư viện. CNTT đã đưa ngành thông tin thư viện đạt đến đỉnh cao của quản lý thông tin. Trong giai đoạn này – người cán bộ thư viện đã thay đổi vai trò của mình từ người giữ sách thụ động sang vai trò chủ động của người cung cấp thông tin – là đã bắt đầu quan tâm đến người sử dụng. Ngày nay trong công tác phục vụ thông tin, áp lực thường trực đối với người cán bộ thư viện là phải thực hiện: - Cung cấp lượng thông tin đúng, - Thời điểm đúng, - Hình thức trình bày đúng, - Nhằm sử dụng đúng mục đích, - Chi phí hợp lý. Muốn hoàn thành tốt công việc trên thì người cán bộ thư viện phải quan tâm đến người sử dụng với việc sử dụng thông tin: - Hiểu nhu cầu người sử dụng, - Phương thức sử dụng thông tin, - Khả năng đáp ứng nhu cầu Giá trị chuyên nghiệp của nghề thư viện sẽ được nâng cao một khi chúng ta không phải chỉ tập trung vào việc mua và cho mượn sách và những tài liệu khác mà là phải biết nhận định nhu cầu và tìm ra giải pháp thông tin cho người sử dụng, đồng thời bằng cách sử dụng CNTT để quản lý thông tin một cách hợp lý nhằm đưa thông tin đến với người sử dụng một cách nhanh nhất. Bước qua giai đoạn quản lý tri thức, yêu cầu đặt ra cho người cán bộ thư viện là phải quản lý lượng thông tin điện tử khổng lồ nhằm đáp ứng nhu cầu tìm kiếm của người sử dụng ngày càng gia tăng. Biên mục tự động là một trong những vấn đề then chốt trong giai đoạn này để quản lý thư viện kỹ thuật số. Sử dụng hệ thống ngôn ngữ tiêu đề đề mục để giúp người sử dụng tìm kiếm và tập trung thông tin theo chủ đề là một công việc biên mục mang tính nghiệp vụ cao nhất - đòi hỏi cả hai tính chất đặc thù là kỹ thuật và nghệ thuật. Việc biên mục tự động do đó đòi hỏi chuyên gia tin học và cán bộ thư viện phải có một sự phối hợp đồng bộ để tạo nên một hệ thống tiêu đề đề mục phản 2-3 ánh đúng nội dung của kho tin. Đồng thời hỗ trợ việc tìm kiếm thông tin cho người sử dụng thông qua hệ thống tiêu đề đề mục hoàn chỉnh đó. Tiêu đề đề mục hay đề mục là một danh từ hay cụm từ được hình thành theo những nguyên tắc định sẳn với một cấu trúc nhất định hay ngữ pháp ngôn ngữ tiêu đề đề mục. Một tiêu đề đề mục phản ánh một nội dung của tài liệu. Một danh sách tiêu đề đề mục được biên soạn trước và đưa vào trong CSDL được xem như là một tập tin có thẩm quyền (authority file) dùng để kiểm soát tính nhất quán (authority control) của tiêu đề đề mục. Đồng thời được dùng để ấn định tiêu đề đề mục cho từng tài liệu điện tử một cách tự động. Ngôn ngữ tiêu đề đề mục không quá máy móc và đơn giản như từ khóa, và cũng không dài dòng như ngôn ngữ thường. Tiêu đề đề mục có một cấu trúc nhất định gồm đề mục mục chính với những phân mục phản ánh tính khoa học và đại chúng sẽ trở nên gần gũi với những tìm tin phục vụ công tác nghiên cứu; bản thân danh sách tiêu đề đề mục cũng đã đóng góp một phần trong công tác nghiên cứu cho những ai theo đuổi một đề tài theo một chủ đề nào đó. Để ấn định một tiêu đề đề mục cho một cuốn sách hay một tài liệu, người cán bộ biên mục phải mất nhiều thời gian trước khi đưa vào CSDL một biểu ghi có chứa tiêu đề đề mục đó, đây là công việc tiền kết hợp (pre-coordinating). Tiền kết hợp theo cách này sẽ không thực hiện được khi khối lượng thông tin cần xử lý trở nên quá lớn. Tuy nhiên với giải pháp hỗ trợ của CNTT được trình bày trong đề tài nghiên cứu khoa học này, công việc biên mục trở nên tự động. Ngoài ra với các nghiên cứu gom cụm thông tin sẽ cung cấp giải pháp đề xuất tập các từ khóa đặc trưng cho nhóm thông tin cần khảo sát tạo điều kiện cho việc xây dựng các khung tiêu đề đề mục. 2-4 2.2. Một ví dụ điển hình về thư viện điện tử trực tuyến (www.webcrawler.com) Webcrawler là một trong những thí dụ điển hình về thư viện điện tử online. Trên trang chủ của Webcrawler, ở trên cùng bên góc trái là Ô hội thoại để tìm theo Từ khóa. Phía dưới là 18 chanels cho các chủ đề khác nhau (Giải trí, Giáo dục, Máy tính và Internet, Tin tức, Sức khỏe, Mua sắm,vv…). 2-5 Ví dụ khi nhấp chuột vào chanel Giáo dục (Education), ta sẽ đi đến một trang web mà trên đó, trong phần Thư mục (Directory) sẽ bao gồm 14 lãnh vực thuộc Giáo dục (Ái hữu, Nghệ thuật và Nhân văn, Hỗ trợ tài chánh, Luật học, Thư viện, Tham khảo, Khoa học & Tự nhiên, Khoa học Xã hội, Các Viện và Trường đại học, ...). Nếu ta thử nhấp chuột vào mục Khoa học và Tự nhiên, ta sẽ lại đi đến một webpage gồm 17 ngành Khoa học tự nhiên (Hóa học, Vật lý, vv…). Nếu cần tìm các thông tin về Hóa học, ta lại nhấp chuột vào mục Hóa học, dưới đề mục Hóa học này lại gồm 15 chuyên ngành nhỏ và các vấn đề liên quan đến Hóa học (Hóa phân tích, Hóa đại cương,v.v…). Webcrawler sẽ đề nghị những website tốt nhất về những vấn đề này mỗi khi ta nhấp chuột vào các đề mục trong Directory. Sự tổ chức của một thư viện điện tử online về bản chất không khác với một thư viện truyền thống: một chủ đề lớn bao gồm những chủ đề nhỏ, rồi đến lượt các chủ đề nhỏ này bao gồm các chủ đề nhỏ hơn, và cứ thế tiếp tục cho đến tận nguồn thông tin cuối cùng là một trang web hay một bài viết. Điều làm cho các nguồn thông tin trong một thư viện điện tử online như trong phần Directory của Webcrawler khác với các nguồn thông tin truyền thống là khối lượng khổng lồ của khả năng nối kết to lớn giữa các thông tin trên mạng. Ví dụ khi tìm các thông tin về Hóa học, từ những web site tốt nhất được đề nghị trong phần Directory Matches của Webcrawler, chúng ta sẽ được dẫn đến rất nhiều web site lớn khác như web site của Hiệp hội Hóa học Hoa Kỳ, và nhiều web site khác mà chính bản thân chúng cũng có 2-6 thể coi như những thư viện về hóa học vì khối lượng thông tin to lớn được nối kết trong mọi web site này. 3-1 CHƯƠNG 3 TIÊU ĐỀ ĐỀ MỤC 3.1 TIÊU ĐỀ ĐỀ MỤC Tiêu đề đề mục được dịch từ Subject Heading (Subject = Đề mục và Heading = Tiêu đề) đôi khi được gọi là Đề mục như ta đã biết, cùng với Tác giả và Nhan đề là những điểm truy cập quan trọng nhất trong Hệ thống tra cứu thư viện. Tác giả và Nhan đềø được mô tả dựa vào dữ liệu có sẵn của tư liệu, trong khi đó Tiêu đề đề mục do cán bộ biên mục xác định dựa vào nội dung tư liệu rồi đưa vào hệ thống như một dữ liệu mới, tiến trình này được gọi là Phân tích Đề mục hay Phân tích Chủ đề (Subject Analysis) phải được thực hiện với nghệ thuật và kỹ thuật biên mục. Từng tư liệu được xác định đúng tiêu đề đề mục hay hệ thống tiêu đề đề mục của một thư viện được xử lý tốt thì nội dung kho tư liệu của thư viện đó được phản ánh một cách đầy đủ. Do đó Tiêu đề đề mục được dùng rộng rãi trong Biên mục sách (Cataloging). Thư viện của một quốc gia sử dụng ngôn ngữ nào thì Tiêu đề đề mục được thể hiện bằng ngôn ngữ đó. Từng quốc gia do đó thiết lập một Hệ thống Tiêu đề Đề mục bằng ngôn ngữ của riêng mình, nhưng phải tuân theo những cấu trúc và nguyên tắc thiết lập chung để dần dần tiến đến một ngôn ngữ chung "Ngôn ngữ tiêu đề đề mục = Subject Heading Language". Một vài minh họa phô hiện thông tin trên biểu ghi về tư liệu với Đề mục. sử dụng Tiếng Việt cho Hệ thống Tiêu đề đề mục của Thư viện mình như minh họa trong Hình 3.1 - Hai Đề mục được đánh số thứ tự Ả Rập ở dòng cuối cùng của Thẻ Thư mục. 3-2 Hình 3.1: Thông tin về sách (Hệ thống Online Catalog của Thư viện ĐH Khoa học Tự Nhiên) Độc giả có thể nhấp chuột vào các Đề mục sau để tìm tài liệu có nội dung tương ứng: C++ (NGÔN NGỮ LẬP TRÌNH MÁY TÍNH) ĐỒ HỌA MÁY TÍNH Thư viện Quốc hội Hoa kỳ sử dụng Khung Đề mục LC (Library of Congress Subject Headings) để định Tiêu đề đề mục. Ví dụ ở Hình 3.2 cho ta thấy thông tin về một cuốn sách xuất bản bằng Tiếng Việt có hai Đề mục bằng Tiếng Anh được dịch như sau: BỘ ĐỘI--GIÁO DỤC NGOẠI KHÓA--VIỆT NAM VIỆT NAM--LỰC LƯỢNG VŨ TRANG--SINH HOẠT CHÍNH TRỊ 3-3 Hình 3.2: Thông tin về sách (Hệ thống Online Catalog của Thư viện Quốc hội Hoa kỳ) Ví dụ ở Hình 3.3 là một biểu ghi thư mục một tác phẩm Tiếng Ba Lan của Thư viện Quốc gia Anh gồm 4 Tiêu đề mục bằng Tiếng Anh. Đề mục ở đây được chọn từ Khung LCSH (Library of Congress Subject Headings). Những đề mục được dịch như sau: KINH TẾ DỰ BÁO--BA LAN BA LAN--ĐIỀU KIỆN KINH TẾ--1990- BA LAN--CHÍNH SÁCH KINH TẾ--1990- 3-4 Hình 3.3: Thông tin về sách (Hệ thống Online Catalog của Thư viện Quốc gia Anh) Hình 3.4 trình bày một biểu ghi thư mục của một bài tạp chí trong Cơ sở dữ liệu CD-ROM "General Science" của EBSCO. Bài tạp chí này được phân tích thành hai Đề mục mang nội dung khác nhau, được dịch như sau: Y TẾ, CHĂM SÓC--VIỆT NAM VIỆT NAM--CHÍNH SÁCH KINH TẾ 3-5 Search/Subjects/Find GENERAL SCIENCE (FEB'91 - MAR'96) +--------------------------Detailed Display - 1 of 1---------------------------+ Subject: MEDICAL care -- Vietnam; VIETNAM -- Economic policy Title: The influence of market economics on primary health care in Vietnam. Author: Gellert, George A. Summary: Analyzes the impact of economic reforms introduced in Vietnam in 1986 on health care in the country. Information on Vietnam's health care system; Abolishing the subsidy system; Details of factors affecting primary health care; Disease prevention and health promotion programs;Conclusions. Source: (Journal of the American Medical Association, 5/17/95, Vol. 273 Issue 19,p1498,5p) ISSN: 0098-7484 Item No: 9506043952 Hình 3.4: Thông tin về bài tạp chí (CSDL CD-ROM EBSCO) Qua các minh họa trên ta thấy Tiêu đề đề mục đóng vai trò quan trọng trong việc giới thiệu nội dung của một tư liệu (sách hoặc bài tạp chí...). Tiêu đề đề mục là một trường độc lập trong một biểu ghi. 3.2. TỪ KHÓA Từ khóa là từ được dùng để định vị thông tin trong một Cơ sở dữ liệu. Thông tin có thể là một biểu ghi thư mục (bibligographic record), bản tóm tắc (abstract), hay toàn văn (full text) mà Từ khóa hiện diện trong đó. Có hai loại Từ khóa: 3-6 • Từ khóa tự do (Free Style Keyword) là từ nằm sẵn trong tư liệu hay CSDL. Từ khóa này không có riêng một trường độc lập. • Từ khóa có kiểm soát (Controlled Style Keyword) là từ được chọn lọc đưa vào CSDL. Từ khóa loại này có riêng một trường độc lập. Khác với Tiêu đề đề mục đã có từ lâu, Từ khóa chỉ mới xuất hiện khi computer được áp dụng trong ngành Thông tin Thư viện. Từ khóa giúp ta tìm nhanh tài liệu có chứa từ khóa đó. Nhờ các Phép toán Boolean giúp ta kết hợp nhiều nội dung tìm hay hạn chế số lượng kết quả tìm. Do đo Từ khóa được dùng để định vị và chỉ điểm (pointing) thông tin cần tìm trong CSDL. Từ khóa được dùng rộng rãi trong công tác Chỉ mục tạp chí (Indexing). 3.3. SO SÁNH TIÊU ĐỀ ĐỀ MỤC VỚI TỪ KHÓA. Tiêu đề đề mục với Từ khóa tự do: Được dùng trong Biên mục sách • Tiêu đề đề mục là do Cán bộ biên mục đưa vào Cơ sở dữ liệu để phản ánh nội dung tư liệu. • Từ khóa tự do có thể là Từ khóa trong Nhan đề, Từ khóa trong Tác giả, Từ khóa trong Đề mục. Vài minh họa cách sử dụng Từ khóa tự do trong Hệ thống tra cứu Online Catalog. So sánh với cách sử dụng Tiêu đề đề mục. Hình 3.5 và Hình 3.6 cho ta thấy hai cách tìm theo Tiêu đề (Heading) và Từ khóa tự do (Keyword) trong Hệ thống Online Catalog của Thư viện Baker, Đại học Harvard, Hoa kỳ. 3-7 Hình 3.5 Khi ta chọn BASIC SEARCH màn hình sẽ hiện ra như Hình 3.5 cho ta phương thức tìm theo Tiêu đề gồm: Tiêu đề Tác giả, Tiêu đề Nhan đề, Tiêu đề Tên Tạp chí, Tiêu đề đề mục, và Tiêu đề ký hiệu Phân loại (Xếp giá). Mỗi Tiêu đề là một Trường trong CSDL. Ta phải gõ đầy đủ thông tin về Tiêu đề. Chẳng hạn như đối với Tiêu đề đề mục thì ta phải gõ đầy đủ Đề mục chính, Tiểu phân mục, dấu phân cách,v.v... Ví dụ: VIETNAM--HISTORY--1954-1975 Nếu ta chọn KEYWORD SEARCH Màn hình như Hình3.6 cho ta phương thức tìm theo Từ khóa tự do kèm theo giải thích cách tìm theo những Toán tử logic: • thêm AND/OR vào ô hội thoại • dùng ngoặc kép để thể hiện Từ khóa nhóm từ: "venture capital" • dùng + để đánh dấu những từ thiết yếu: +management 3-8 • dùng * để đánh đấu những từ quan trọng: *technology • dùng ? để chặt cụt từ: industr? • dùng ! để ngăn chặn từ: !computer Hình 3.6 Màn hình như Hình 3.7 minh họa cách tìm Từ khóa trong Nhan đề và Từ khóa trong Đề mục trong Hệ thống Online Catalog của Thư viện Quốc gia Anh. 3-9 Hình 3.7 Nếu ta chọn Từ khóa trong Đề mục thì vào ô hội thoại Subject (Đề mục). Ví dụ ta chọn Từ khóa economic. Những cuốn sách có Đề mục mang Từ khóa trên được phô hiện; giã sử ta chọn cuốn sách có biểu ghi như Hình 3.3 có tựa đề là "Polonia quo vadis?..." và có những Đề mục mang Từ khóa economic như sau: ECONOMIC FORECASTING--POLAND POLAND--ECONOMIC CONDITIONS--1990- POLAND--ECONOMIC POLICY--1990- Nếu ta chọn Từ khóa trong Nhan đề thì vào ô hội thoại Title (Nhan đề). Ví dụ ta chọn Từ khóa Vietnam. Màn hình như Hình 3.8 phô hiện những nhan đề sách có chứa Từ khóa Vietnam. 3-10 Hình 3.8 Hình 3.9 Hệ thống Online của Thư viện ĐH Simmons, Hoa kỳ như trong Hình 3.9 cho ta thấy độc giả có thể tìm tư liệu theo Tác giả (Author), Nhan đề (Title), Đề mục 3-11 (Subject), Từ Khóa tự do (Keyword), Ký hiệu xếp giá theo số Phân loại LC, Ký hiệu xếp giá không theo số Phân loại LC, số ISSN/ISBD. Tiêu đề đề mục với Từ khóa có kiểm soát: Cả hai đều là Thuật ngữø có kiểm soát (Controlled vocabulary) được tạo thành Trường độc lập trong Hệ thống Online Catalog. • Tiêu đề đề mục được dùng để mô tả nội dung tư liệu. Danh sách Tiêu đề đề mục (Subject heading list) chẳng hạn như "Library of Congress Subject Headings" và "Sear List of Subject Headings" được dùng trong Biên mục sách và đôi khi được dùng trong Chỉ mục Tạp chí. • Từ khóa có kiểm soát tập hợp những từ phản ánh một phần nội dung tư liệu, được kiểm soát để đồng nhất. Từ khóa nói chung không chú trọng đến cấu trúc và mô tả dữ liệu. Chỉ chú trọng đến việc kết hợp để tạo nên những biểu thức tìm nhằm định vị nhanh và chỉ điểm đúng thông tin trong CSDL. Danh sách những Từ khóa có kiểm soát được gọi là Thesaurus được dùng trong Chỉ mục tạp chí. 3.4 KẾT LUẬN Tiêu đề đề mục và Từ khóa là bộ phận không thể thiếu trong Bộ máy tra cứu tư liệu. Trong đó Tiêu đề đề mục là bộ phận chủ yếu nhất trong Biên mục học (Cataloging), hiện diện trong giáo trình Khoa học Thông tin và Thư viện kể từ khi Nghề Thư viện ra đời cách đây rất lâu và càng tỏ ra hữu hiệu trong Hệ thống Mục lục trực tuyến (Online catalog) ngày nay. Do vậy cần khuyến khích sử dụng và thành lập "Danh sách Tiêu đề đề mục Tiếng Việt" theo chuẩn quốc tế để hỗ trợ phát triển công tác biên mục thư viện đặc biệt là các thư viện điện tử nhằm hỗ trợ tiến trình tra cứu thông tin. 4-1 CHƯƠNG 4 XÂY DỰNG CÔNG CỤ TÌM KIẾM VÀ DOWNLOAD DỰA TRÊN TÁC NHÂN 4.1.TÁC NHÂN” PHẦN MỀM (SOFTWARE AGENT): 4.1.1. Các định nghĩa về “tác nhân” Stan Franklin và Art Graesser ở Viện các hệ thống thông minh ở đại học Memphis liệt kê ra một số định nghĩa về tác nhân như sau: • The MuBot Agent ( "Từ tác nhân được dùng cho hai nghĩa. Thứ nhất là khả năng tự động thi hành Thứ hai là khả năng định hướng hoạt động theo lĩnh vực" • The Hayes - Roth Agent (Hayes -Poth 1995) Các tác nhân thông minh biểu hiện 3 chức năng: cảm nhận về những trạng thái trong môi trường, hành động để tác động lên trạng thái trong môi trường đó. • The IBM Agent ( 'Tác nhân thông minh hoàn toàn là một phần mềm thực hiện một tập các hành động dựa trên cư xử của người sử dụng hay chương trình khác với môt vài mức độ độc lập hay tự hoạt động, và trong quá trình làm như thế, dùng một số tri thức về mục đích và mong muốn của người sử dụng • The Brustoloni Agent (Brustoloni 9991, Frankin 1995, trang 265) "Các tác nhân là các hệ thống có khả năng tự hoạt động, hành động có mục đích trong thế giới thực." . Theo những định nghĩa trên có thể làm chúng ta thấy rõ rằng các tác nhân phải có tính tự hoạt động (độc lập), tìm kiếm mục tiêu, kiên định, suy luận và khả năng giao tiếp. 4.1.2. Các thuộc tính của tác nhân Tác nhân về cơ bản hoàn toàn khác với các chương trình phần mềm và các chương trình, chúng phải có các đặc tính và thuộc tính đặc biệt. Một tác nhân phải có các đặc tính sau: 4-2 • Thích nghi: một tác nhân phải có khả năng làm việc thích nghi. Khi môi trường thay đổi, tác nhân phải tự động cảm nhận và có hành động thích nghi với những thay đổi của môi trường. • Tự khởi động: một tác nhân có thể tự kích hoạt hay dùng kích hoạt dựa trên tiêu chuẩn của chính bản thân nó và có khả năng quyết định thu gom thông tin sử dụng các ưu tiên của người dùng. Hoạt động thường xuyên theo giờ, ngày, tuần hay hàng tháng được đặt ra. Tác nhân cần có khả năng quyết định kích hoạt hay ngừng hoạt động. • Trong suốt: Người sử dụng sẽ không nhìn thấy hoạt động bên dưới của tác nhân trong hệ thống. . Mọi công việc trên đều trong suốt với người sử dụng. Người sử dụng hầu như không biết tác nhân đang chạy trong hệ thống của mình. 4.1.3. Sự tác động trực tiếp của Internet Nhiều người cho rằng "tác nhân" và Internet luôn gắn liền với nhau. Lý do là đầu tiên tác nhân được sử dụng cho các công việc trên môi trường Internet ( tác nhân tìm kiếm chẳng hạn). Tuy vậy, tác nhân có thể hành động trong bất kỳ môi trường nào. 4.1.4. Các loại tác nhân: Có thể tóm tắt đặc điểm của một số loại tác nhân như sau: • Tác nhân thông minh: là loại mang ý nghĩa tổng quát và phù hợp với các định nghĩa đã trình bày ở trên • Tác nhân học: là những tác nhân phần mềm mà cơ bản học từ người sử dụng hay người chủ của nó. Việc học chúng ta định nghĩa ở đây như là việc bổ sung hành vi thông qua kinh nghiệm hay sự phán đoán. Một khi các công việc được học, tác nhân có thể sau đó chỉ dẫn hay đề nghị các cách thức để cải tiến công việc nào đó. • Tác nhân niềm tin: đây là tác nhân mà có hình ảnh cử động hay có lẽ là có tính cách khiến chúng đáng tin cậy. Một phần của kỹ thuật tác nhân vẫn ở 4-3 trong nó. Trong tương lai các tác nhân này sẽ trở nên thông minh hơn. Tác nhân niềm tin hiện thời không thông minh chúng chỉ xuất hiện thân thiện để giao tiếp với người dùng. Chúng thường xuất hiện thân thiện để giao tiếp với người dùng. Chúng thường có mặt ở các trò chơi trẻ con như những con thú ảo,… • Tác nhân có khả năng chuyển tải: Những tác nhân này rất năng động, linh hoạt và có khả năng di chuyển đến nơi khác. Chúng có thể cư ngụ trên một máy chủ hay một máy trạm nào đó, và gặm nhấm thông tin từ máy tính, mạng Internet đã thực hiện công việc của nó. Nó thường được sử dụng để thu nhập dữ liệu, thông tin hay là những thay đổi. Tác nhân có khả năng vận tải có nhiều thuận lợi hơn so với mô hình client/server truyền thống. 4.1.5. Ứng dụng khái niệm “tác nhân” trong chương trình: Chương trình cần được thiết kế theo hướng tiếp cận tác nhân đảm bảo đáp ứng đúng mục tiêu đã đề ra ban đầu: xây dựng một chương trình nhằm giúp cho người quản trị thư viện có thể biên mục một cách nhanh chóng và hiệu quả nhằm tiết kiệm thời gian và công sức tìm kiếm thông tin trên Internet. Theo cách tiếp cận này, chương trình được thiết kế gồm 2 “tác nhân” chính: tác nhân tìm kiếm và tác nhân download. Khi chương trình được kích hoạt, hai tác nhân sẽ hoạt động liên tục để thực hiện nhiệm vụ của mình. Trong quá trình thực hiện các tác nhân có thể chuyển sang trạng thái chờ nếu không có việc và sẽ tự động hoạt động trở lại khi cần thiết. Các tác nhân sẽ có khả năng hoạt động độc lập và liên tục không đòi hỏi nhiều sự can thiệp của con người. Các tác nhân sẽ hoạt động dưới dạng một dịch vụ của hệ thống để đảm bảo tính trong suốt đối với người sử dụng. 4-4 4.2. GIỚI THIỆU VẤN ĐỀ: Ngày nay với sự bùng nổ thông tin, nhất là sự phát triển mạnh mẽ của Internet và World Wide Web. Việc tìm kiếm thông tin thật sự dễ dàng đối với người dùng Internet. Tuy nhiên, Internet như một xa lộ rộng lớn và rất dễ đưa người sử dụng đi lạc trong cái mênh mông của nó. Thật là dễ dàng vì bạn có thể dùng các trang tìm kiếm thông tin như yahoo hay google... để tìm kiếm một thứ gì đó. Nhưng giả sử chúng ta cần tìm kiếm một số luận văn nghiên cứu về máy học, và chúng ta bắt đầu tìm kiếm một cách bình thường, tức là vào google hay yahoo để search với từ khóa :”Machine learning”. Lúc này kết quả hiện ra là hàng ngàn các trang web nói về machine learning, bao gồm các trang web của các khoa máy tính của các đại học ,viện trên thế giới và các home page của các chuyên gia... Để tìm kiếm tiếp chúng ta lần lượt chọn các địa chỉ web và xem, rồi chọn lọc.... Đến khi nào thông tin của chúng ta thỏa mãn thì thôi. Việc tìm kiếm này đòi hỏi công sức và thời gian rất nhiều. Một câu hỏi đặt ra là trong một tổ chức như một viện hay một trường đại học, việc tìm kiếm thông tin như vậy sẽ rất không khoa học. Ví dụ cùng một mục đích nhưng anh A ở khoa này phải tốn cả buổi trời để tìm, rồi anh B cũng vậy, và còn nhiều người nữa. Thời gian cho việc tìm có thể là cấp số cộng. Nếu ta có thể xây dựng được một thư viện, tạm gọi là thư viện số. Tổ chức các thông tin và tài liệu tìm kiếm trên web một các khoa học và chính xác thì việc tìm kiếm thông tin hoàn toàn nhanh chóng và hiệu quả. Việc tìm kiếm chỉ thực hiện một lần, và có thể được cập nhật thông tin thường xuyên (vì web liên tục phát triển). Để xây dựng được thư viện số thì một trong thành phần quan trọng là tìm kiếm và lấy thông tin trên Internet. Trong phần báo cáo này chúng tôi xin trình bày hai cơ chế hỗ trợ xây dựng thư viện số là : search engine và download engine. 4-5 4.3. CHỨC NĂNG SEARCH ENGINE Thuật ngữ Search engine khá là thân thiện với chúng ta, những người sử dụng Internet thường xuyên. Ít nhất là một lần chúng ta sử dụng các trang web như Yahoo, Google hay Altavista để tìm kiếm một thông tin nào đó. Các trang web này lấy từ khóa mà người tìm kiếm hỏi rồi đưa vào một chức năng gọi search engine, search engine này thực chất là một chương trình máy tính, chương trình này sẽ truy lùng trong một cơ sở dữ liệu thông tin tìm kiếm (được tổ chức ở web server của các trang web tìm kiếm). Sau khi tìm xong thì web server sẽ trả về cho người dùng các kết quả tìm kiếm được. Đây là dạng tìm kiếm trực tiếp trên web. Ngoài ra còn có một dạng tìm kiếm client như sau: Một chương trình tìm kiếm chạy ở máy có kết nối cổng internet, cho phép người dùng tìm kiếm các thông tin trên các search engine khác nhau... Cách tìm kiếm này tiện lợi cho phép tìm kiếm thông tin đa dạng trên nhiều search engine và có thể lưu trữ lại các thông tin tìm kiếm theo nhiều định dạng tập tin khác nhau như text file, hoặc các sheet của excel... Chức năng Search Engine được cài đặt trong đề tài được phát triển theo hướng thứ hai. Chương trình cho phép chúng ta tận dụng sức mạnh của các Search Engine hiện có, đồng thời nâng cao hiệu quả của việc tìm kiếm dưói dạng thư viện số hóa. Ngoài ra, việc tìm kiếm sẽ được kích hoạt một cách tự động nhằm làm giảm tối đa sự can thiệp của con người vào quá trình tìm kiếm thông tin trên Internet vốn rất tốn thời gian. 4.4. CÀI ĐẶT SEARCH ENGINE TRONG THƯ VIỆN SỐ Hướng tiếp cận là xây dựng một chương trình tìm kiếm tự động dạng một chương trình search kết nối nhiều cơ sở dữ liệu thông tin của các search engine trên web như google và yahoo. Chương trình này sẽ hoạt động dạng một chương trình NT Service, nó sẽ hoạt động dưới dạng nền (deamon program), liên tục cập nhật thông tin mà người dùng cần tìm rồi thực hiện việc tìm kiếm trên Internet và lưu vào cơ sở dữ liệu của thư viện số. 4-6 Do luôn hoạt động dưới hình thức nền, nên khi có một yêu cầu do một người quản lý thư viện hay một người dùng cần tìm kiếm thông tin mới nào đó, thì chức năng tìm kiếm sẽ được kích hoạt. Các kết quả tìm đươc sẽ được lưu trữ vào thư viện và người dùng tìm kiếm sẽ được những thông tin cần tra cứu. Để thông tin được cập nhật liên tục thì thông thường theo định kỳ search engine phải cập nhật các thông tin đã tìm kiếm. Tức là thêm các thông tin mới và hủy bỏ những thông tin không còn tồn tại hay không còn giá trị trên Internet. Như chúng ta biết thì các trang web liên tục phát triển hàng ngày có hàng ngàn trang web ra đời và cũng có nhiều trang web không còn cung cấp hay không còn tồn tại nữa... Hình 4.1 Mô hình hoạt động của Search Engine Thông tin tìm kiếm Search Engine Internet - WWW Google Yahoo Altavista ..... Cơ sở dữ liệu thư viện số User- LAN Thông tin kết quả Thông tin mới cần tìm kiếm Chuyển từ khóa tìm kiếm cho search engine Thực hiện tìm kiếm trên Internet Lưu thông tin tìm kiếm mới vào CSDL Truy cập thư viện số ™ Mô hình hoạt động của Search Engine phục vụ cho thư viện số. 4-7 4.5. CHỨC NĂNG DOWNLOAD ENGINE Như chúng ta đã biết phần quan trọng của Internet & World Wide Web là cung cấp các tài liệu điện tử (e-book). Tài liệu này thường được lưu dưới rất nhiều định dạng tập tin khác nhau như pdf, ps, html, text file... Việc lấy các tài liệu dạng này về thư viện số cần phải có một chương trình tải về (download) từ Internet. Hiện tại có rất nhiều chương trình download thương mại trên thị trường cung cấp rất nhiều tiện ích tuỳ theo nhu cầu của người dùng. Tuy nhiên, do yêu cầu xây dựng thư viện số nên chúng ta cần phải xây dựng một chương trình download riêng để kết hợp với search engine. Tạo thành một khối kết hợp tự động, nhằm làm giảm sự can thiệp của người điều hành trực tiếp. Chức năng Download Engine sẽ đảm nhiệm công việc download các tài liệu điện tử tìm được về lưu vào cơ sở dữ liệu của thư viện số hóa. Công việc này cũng sẽ được kích hoạt tự động cùng với chức năng Search Engine. 4.6. CÀI ĐẶT DOWNLOAD ENGINE TRONG THƯ VIỆN SỐ Thành phần download engine này chịu trách nhiệm tải về các tập tin trên Internet bao gồm các tài liệu điện tử, các tập tin nguồn.... Cũng tương tự như search engine, chức năng downlaod engine cũng hoạt động dưới dạng NT Service. Tức là hoạt động nền bên dưới, khi nào có yêu cầu download thì nó sẽ tự động kết nối vào URL đã tìm được trong cơ sở dữ liệu và thực hiện việc download các tập tin về rồi lưu vào thư viện số. Chức năng này hoạt động dựa trên kết quả đạt được của chương trình Search Engine. Mỗi khi được kích hoạt, chương trình sẽ dò tìm trong cơ sở dữ liệu của thư viện để tiến hành download các tư liệu theo yêu cầu. Các tư liệu tải về sau khi được lưu lại sẽ được cập nhật thông tin trong cơ sở dữ liệu để phục vụ cho hoạt động của thư viện số. 4-8 Hình 4.2. Mô hình hoạt động của download engine 4.7. KẾT HỢP CƠ CHẾ SEARCH VÀ DOWNLOAD TRONG XÂY DỰNG THƯ VIỆN SỐ Việc kết hợp search engine và download engine vào việc xây dựng thư viện số là công việc thiết yếu. Hai chương trình này sẽ giúp cho người quản trị thư viện có thể biên mục thư viện số một cách nhanh chóng và hiệu quả. Việc kết hợp này sẽ đem lại nhiều lợi ích. Lúc này người biên mục không tốn nhiều thời gian, và công sức tìm kiếm thông tin trên Internet bằng các chương trình tìm kiếm khác nhau rồi sau đó chọn lọc và lưu giữ chúng. Và cuối cùng là chọn các tư liệu trên Internet để download về. Thông tin download Download Engine Internet - WWW Cơ sở dữ liệu thư viện số Quản trị thư viện số File Tư liệu, e-book Chuyển URL cần download cho chương trình Thực hiện download Lưu nội dung download vào CSDL ™ Mô hình hoạt động của Download Engine phục vụ cho thư viện số. URL User- LAN 4-9 Hình 4.3. Mô hình kết hợp hoạt động của search engine và download engine Cách thức hoạt động như sau: người quản trị hay biên mục thư viện trong quá trình xây dựng và duy trì thư viện số, họ sẽ đưa yêu cầu tìm kiếm thông tin trên Internet cho Search engine. Search engine sẽ thực hiện việc tìm kiếm trên Internet sau đó lưu kết quả tìm kiếm tức là địa chỉ của các trang web có nội dung liên quan. Những thông tin này được lưu vào cơ sở dữ liệu thư viện số nhằm cung cấp cho hai mục đích : cung cấp địa chỉ cho người tìm kiếm, và mục đích thứ hai là dùng các địa chỉ này để làm nguồn cho phần download engine lấy các tập tin và tài liệu liên quan từ nguồn này. Việc lấy các tài liệu từ các nguồn này rất cần thiết. Khi đó sẽ rất tiện lợi cho người dùng thư viện là họ không những tìm kiếm được trang web liên quan đến lĩnh vực mà còn xem được các tài liệu từ các nguồn này. Thông tin tìm kiếm Search Engine Internet - WWW Cơ sở dữ liệu thư viện số Quản trị thư viện số Chuyển thông tin tìm kiếm cho search engine Thực hiện Tìm kiếm URL Download Engine Google Yahoo .... Thông tin download Lưu kết quả tìm kiếm vào CSDL Chuyển thông tin cần download Chuyển thông tin cần download Lưu nội dung download về CSDL 4-10 Toàn bộ các công việc trên được cài đặt sử dụng hướng tiếp cận mới gọi là tác nhân thông minh (Intelligent Agent). Hướng tiếp cận mới này cho phép xây dựng những phần mềm có khả năng thay thế cho con người, ở đây là thay thế cho vị trí người quản thủ thư viện trong mô hình thư viện số. 4.8. KẾT QUẢ XÂY DỰNG CHƯƠNG TRÌNH 4.8.1. Gíơi thiệu Trong thời gian qua nhóm phát triển phần mềm đã xây dựng xong search engine. Chương trình này được gọi là Search Agent. Search Agent là một chương trình application dạng NT Service chạy trên nền Windows NT hay Windows 2000, Windows XP. Chương trình Search Agent hoạt động với đầu vào input và xuất dữ liệu output thông qua cơ sở dữ liệu là SQL Server. Tức là thông tin cần tìm sẽ được một chương trình nhập vào thông qua một client program hay một form từ một trang web. Thông tin cần tìm này hay còn gọi là khóa cần tìm sẽ được lưu vào một bảng tạm để chuẩn bị cho Search Agent thực hiện việc tìm kiếm. Search Agent luôn luôn truy cập vào bảng tạm này để lấy các thông tin mới cần tìm theo một khoảng thời gian nhất định cho trước. Các thông tin lấy về tức là các địa chỉ các trang web hay còn gọi là URL sẽ được lưu vào một bảng khác. Các thông tin này được chỉ mục với các từ khóa để tiện cho việc tìm kiếm của người dùng trong thư viện. Hình 4.4: Quá trình vận động của Search Agent Internet - WWW URL Google Yahoo .... Search agents yêu cầu tìm kiếm URLs kết quả Tự làm giàu tri thức từ các URLs kết quả 4-11 Search agent sẽ tiến hành lấy các kết quả tìm kiếm dựa trên kết quả có được từ các search engine khác. Tự động dò tìm các trang web ứng với từ khóa bằng cách tự tạo cho mình tri thức từ những trang web mà agent đi qua. Các thông tin lấy về tức là các địa chỉ các trang web hay còn gọi là URL sẽ được lưu vào một bảng khác. Các thông tin này được chỉ mục với các từ khóa để tiện cho việc tìm kiếm của người dùng trong thư viện.Giới thiệu chương trình Search Agent: Giới thiệu chương trình Search Agent: o Tên chương trình: Search Agent o Công cụ phát triển : Visual Studio 6. o Môi trường sử dụng : Windows NT, Windows 2K, Windows XP. o Cơ sở dữ liệu : SQL Server. o Yêu cầu kĩ thuật: cấu hình máy tính CPU Pentium II, 64MB RAM, 4GB HDD trở lên và phải có kết nổi với Internet. o Kết nối với cơ sở dữ liệu tìm kiếm trên Internet : Google và Yahoo. 4.8.2.Phân tích yêu cầu xây dựng Search Agent: o Xây dựng một ứng dụng Search engine thực hiện việc truy tìm thông tin trên Internet thông qua một từ khóa (keyword) hay cụm từ khóa (multiword). o Search engine thực hiện việc tìm kiếm thông qua cơ chế tự động kết nối với các cơ sở dữ liệu tìm kiếm trên Internet như Google, Yahoo, Hotbot, Altav ista... Để lấy các thông tin về các trang web liên quan cần tìm kiếm. o Việc thực hiện tìm kiếm phải đảm bảo tốc độ tốt nhất và tìm kiếm được nhiều thông tin nhất. Tức là kết nối với cơ sở dữ liệu tìm kiếm nhanh và chất lượng, điển hình là Google và Yahoo là hai trang tìm kiếm nhanh và hiệu quả ở thời điểm hiện tại. o Xây dựng chương trình kết nối với cơ sở dữ liệu lớn như SQL Server hay Oracle để các thông tin kết quả tìm kiếm được (có thể rất nhiều) 4-12 được lưu trữ tốt nhằm phục vụ cho mục đích tra cứu sau này hay là download tài liệu cho thư viện. o Xây dựng Search engine thành một module hoàn chỉnh dưới dạng một chương trình NT Services của Windows NT. Chương trình này là một dạng chương trình thực hiện nền (background) tức là không xuất hiện kiểu application bình thường mà dưới dạng Service. o Kết hợp với việc xây dựng download engine cho việc tích hợp hai cơ chế search – download ứng dụng trong thư viện số. 4.8.3.Phần thiết kế Search Agent: Thành phần Search Agent chia thành hai nhóm xử lý chính: Xử lý thông tin vào - ra (input - output) và thực hiện kết nối với cơ sở dữ liệu tìm kiếm trên Web để lấy thông tin. Trong đó phần xử lý thông tin hay dữ liệu có kết nối với cơ sở dữ liệu quan hệ như SQL Server hay Oracle. Phần thực hiện kết nối với cơ sở dữ lịêu tìm kiếm trên Web, sẽ thực hiện việc kết nối với Internet thông qua kỹ thuật WinInet trong lập trình Internet của Windows để kết nối với các host Google hay Yahoo. ‰ Sơ đồ hoạt động chung của Search Engine CSDL Search Engine Internet - WWW Google Yahoo CSDL ... Thông tin tìm kiếm được lưu trong CSDL, sẽ được đưa vào phần module tìm Truy cập vào Internet để lấy thông tin Kết quả tìm kiếm sẽ được lưu vào CSDL Hình 4.5a Sơ đồ hoạt động của 4-13 ‰ Sơ đồ xử lý của Search engine Như yêu cầu trong phần phân tích, quá trình xử lý của Search engine là một chu trình kép kín xử lý từ giai đoạn lấy thông tin từ cơ sở dữ liệu rồi thực hiện truy cập Internet để truy lùng thông tin. Sau khi hoàn tất việc lấy thông tin thì chu trình tiếp tục thực hiện quá trình lại từ đầu. Để tận dụng thời gian xử lý và tránh lãng phí tài nguyên mạng: Search engine cho phép tạo ra n số các thể hiện (instance) để thực hiện đồng thời tác vụ tìm kiếm đồng thời với nhau. Việc cho phép tạo ra nhiều các thể hiện để thực hiện một công việc với các tham số khác nhau cho phép tăng tốc độ việc tìm kiếm và hiệu quả của chương trình lên rất nhiều. Trong sơ đồ ở hình 4.5a trình bày mô hình hoạt động của một module Search engine. Như chúng ta đã phân tích thì khi Search engine thực sự hoạt động thì không phải chỉ có một thể hiện làm việc mà có n module search engine nhỏ được tạo ra. Sai Bảng CSDL lưu trữ từ khóa tìm kiếm Xử lý từ khóa Từ khóa hợp lệ / hay tồn tại từ khóa Thực hiện kết nối Internet và tìm kiếm Kết quả tìm kiếm hợp lệ Xử lý kết quả tìm kiếm được Lưu vào bảng kết quả tìm kiếm trong CSDL Tiếp tục lấy thông tin để tìm kiếm tiếp. Bảng kết quả tìm kiếm Đúng Sai Hình 4.5b Sơ đồ hoạt động của một thể hiện tạo ra từ Search engine 4-14 Tiếp sau là mô hình xử lý của toàn bộ Search engine khi làm việc. Trong sơ đồ này chúng tôi không mô tả chi tiết các xử lý của từng module vì đã mô tả trong sơ đồ xử lý từng module riêng lẻ hình 4.5b. ‰ Thiết kế CSDL sử dụng trong Search engine Theo yêu cầu của việc xây dựng thì chương trình Search engine sẽ truy cập vào cơ sở liệu quan hệ là SQL Server hay Oracle để lấy các thông tin yêu cầu (từ khóa hay cụm từ khóa cần tra cứu). Do đó trong phần này chúng tôi giới thiệu các bảng cơ sở dữ liệu được xây dựng để lưu trữ thông tin cung cấp cho các hoạt động của Search engine. Bao gồm hai bảng chính: o Bảng Request Table: Lưu trữ các từ khóa hay cụm từ khóa cần tìm kiếm và trạng thái của từ khóa. Tức là đã thực hiện việc tìm kiếm hay chưa. o Bảng Result Table: Chứa các thông tin về các địa chỉ trang web (URL) mà Search Engine đã tìm kiếm được. CSDL Instance 1 Search Engine Instance 2 Search Engine Instance 3 Search Engine Instance n Search Engine CSDL Khối Search engine được tạo ra với n instance. Cho phép đồng thời thực hiện n tác vụ tìm kiếm thông tin trên Internet Hình 4.5c: Sơ đồ hoạt động toàn bộ Search engine khi tạo ra n instance tìm kiếm. 4-15 Request Table ID_Wordterm long Wordterm Varchar(256) MaxResult Int SearchEngine Byte Finished bit + ID_Wordterm: là trường khoá + Wordterm: chứa nội dung từ khóa cần tìm tối đa là 256 ký tự. Nhưng hầu hết không bao giờ dùng nhiều, vì nếu ta dùng càng nhiều từ khóa để tìm thì rất hạn chế kết quả tìm kiếm. + MaxResult: Chỉ cho phép tìm tối đa là n kết quả mà thôi. Vì nếu không chặn trước thì rất có thể sẽ xử lý quá nhiều kết quả. + SearchEngine: Đây là trường kiểu nguyên xác định search engine đề thực hiện việc tìm kiếm. Qui định giá trị 0 là dùng toàn bộ search engine có cài đặt kết nối để tìm kiếm; giá trị 1 dùng Google; giá trị 2 dùng Yahoo; giá trị 3 là Hotbot; giá trị 4 là Altavista... + Finished: là trường trạng thái, nhằm xác định trạng thái của từ khóa là đang có một module search engine thực hiện tìm kiếm (có thể là hoàn thành rồi) hay chưa có module nào thực hiện, đây chính là thông tin mới cần tìm kiếm. Chúng ta phải tạo ra trường này vì do Search engine có tạo ra nhiều thể hiện để tìm kiếm nếu không quản lý trạng thái của từng record thì sẽ có nhiều module tìm kiếm trùng lắp và không quản lý được. Result Table ID_Url Long ID_Wordterm long Url Varchar(256) Abstract Varchar(255) Location Varchar(256) + ID_Url : trường khóa của bảng Result table. + ID_Wordterm : ID của từ khóa xác định. Đây là khóa ngoại của bảng Request Table. + Url : Chứa địa chỉ của trang web liên quan với từ khóa mà chương trình tìm kiếm được. Địa chỉ này có thể là dạng HTTP hay FPT. + Abstract : chứa abstract của trang web hay địa chỉ tìm được. + Location : Phần này dùng cho download engine. Nó chứa vị trí của tập tin được download về. 4-16 Một số minh họa dữ liệu mẫu của hai bảng Request Table ID_Wordterm Wordterm MaxResult SearchEngine Finished 1 Data Mining 50 0 0 2 Machine Learning 100 1 0 3 SOM 30 0 0 4 GIS 60 0 0 5 MS.NET 100 0 0 Result Table ID_Url ID_Wordterm URL Abstract Location 1 2 www.ics.uci.edu/~mlearn UCI Machine Learning Group 2 2 www.cs.utexas.edu UTCS Machine Learning Research Group 3 2 robotics.stanford.edu Introduction to Machine Learning ... ... ... ... 4.8.4.Cài đặt Search Agent: ‰ Mô tả các hàm chức năng chính: Trong phần này chúng tôi xin chỉ trình bày hai thủ tục được cài đặt chính trong Search Agent là CreateSearchModule(int) và PerformSearching(): ™ CreateSearchModule(int) : thực hiện chức năng tạo ra các thread để thực hiện chức năng tìm kiếm. Đây chính là phần tạo tiểu trình và gọi thủ tục PerformSearching() 4-17 CreateSearchModule(int) Begin While i=1 to n do Begin CreateThread( PerformSearching() ) StartThread( PerformSearching() ) End End ™ PerformSearching(): Thủ tục này là phần chính của chương trình Search Agent. Chức năng là truy cập CSDL lấy thông tin cần tìm kiếm, sau đó vào Internet tìm kiếm và cuối cùng lưu kết quả vào CSDL. Toàn bộ các lệnh này được nằm trong một vòng lặp. Được quản lý bởi một cờ, khi cờ còn hiệu lực thì vòng lặp còn thực hiện. Cờ hết hiệu lực khi chương trình Search Agent bị stop (dùng Service manager). PerformSearching() Begin While ( fContinue) Begin GetWordTerm(string wordterm) If ( InvalidWordTerm(wordterm)) Continue String content Content = SearchInternet( wordterm) FilterResult_SaveToDB( Content) End End + GetWordTerm( string) : lấy từ khóa cần tìm trong CSDL + InvalidWordTerm( string) : Kiểm tra xem từ khóa có hợp lệ hay không. 4-18 + string SearchInternet( string) : Thực hiện việc tìm kiếm trên Internet trả về một chuỗi chính là nội dung của kết quả cần tìm. Chuỗi này chính là nội dung của trang HTML chứa kết quả tìm được từ các search engine. ™ CAgentActs::ExecuteRequestEx: hàm này thực hiện việc tìm kiếm bằng cách dùng các hàm của WinInet. Đây là hàm quan trọng nhất trong chương trình ™ CAgentActs::SaveData: Phân tích và lưu kết quả tìm kiếm vào trong bảng SearchResult. ™ CClock::Wait: được kích hoạt một lầnkhi chương trình chính chạy. Nó có nhiệm vụ tái kích hoạt chương trình chính tại một thời điểm ấn định trước. While (1) { If (begin) Tính độ lệch n so với giờ thiết lập If (độ lệch n = 0) Tái kích hoạt lại dịch vụ Else { Tạm ngưng dịch vụ trong khoảng thời gian n Gán độ lệch n = 0 } } ‰ Miêu tả hoạt động của chương trình: ™ Khi chương trình bắt đầu thực hiện, tiểu trình chính sẽ đăng ký dịch vụ với hệ thống (CServiceModule::Start). ™ Tiếp theo, tiểu trình chính sẽ tạo ra 1 tiểu trình mới để thực thi dịch vụ chính của chương trình Search Agent (CServiceModule::ServiceMain). Đồng thời chương trình cũng tạo ra một tiểu trình chạy song song để tiến hành kích hoạt lại chương trình vào thời điểm ấn định trước để cập nhật lại nội dung khi cần thiết(CClock::Activate, CClock::Wait). ™ Khi chương trình Search Agent được kích hoạt (CFactoryAgent::StartAgents), nó sẽ tạo ra các tiểu trình khác để 4-19 thực thi các chức năng tìm kiếm (CFactoryAgent::StartSearchProc) và download (FactoryAgent::StartDownloadProc) tự động. ™ Toàn bộ kết quả tìm kiếm được ghi xuống cơ sở dữ liệu (CAgentActs::SaveData) trước khi dịch vụ chuyển sang trạng thái tạm dừng. ™ Sau khi chuyển sang trạng thái chờ, dịch vụ sẽ được kích hoạt trở lại vào thời điểm đã định trước. Nếu không có công việc mới chương trình lại tiếp tục chuyển sang trạng thái chờ và lại dược tái kích hoạt khi đến giờ. 4.8.5.Kiểm thử: Trong phần này nhóm làm phần mềm xin được báo cáo qua kết quả chạy thử chương trình với dữ liệu thực để kiểm tra khả năng thực thi của chương trình. Chương trình bắt đầu chạy lúc 16h với những số liệu ban đầu như sau: Bảng 4.1: Dữ liệu đầu vào Với dữ liệu đầu vào như Bảng 4.1, kết quả sau khi hoàn tất phải là 150 tập tin *.html có nội dung chứa các từ khóa cần tìm. Tuy nhiên trên thực tế, chương trình có thể không hoàn tất công việc ngay lần thực hiện đầu tiên mà chỉ thực hiện một phần công việc sau đó chuyển sang trạng thái chờ đến thời điểm thích hợp để tiếp 4-20 tục thực hiện. Việc chương trình chuyển sang trạng thái tạm dừng có 2 nguyên nhân như sau: đang kẹt mạng không thể kết nối vào Internet hoặc công việc đã hoàn tất. Trong kết quả thử nghiệm đang trình bày, chương trình tạm dừng do không thể kết nối vào Internet với kết quả thực hiện được thể hiện trong các bảng sau: Bảng 4.2: Kết quả tìm kiếm khi chương trình tạm dừng Bảng 4.3: Kết quả download khi chương trình tạm dừng 4-21 Theo số liệu trong Bảng 4.2 và Bảng 4.3, chương trình tạm dừng vào lúc 18h58 với kết quả: đã hoàn tất việc tìm kiếm các từ khóa theo yêu cầu và download được 62 trang HTML. Như vậy chương trình tạm dừng khi chưa hoàn tất công việc. Theo như cấu hình ban đầu, chương trình sẽ hoạt động trở lại vào lúc 2 giờ hàng ngày. Sau khi chương trình tái kích hoạt, kết quả ghi nhận được như sau: Bảng 4.4: Kết quả khi hoàn tất công việc Như vậy, sau khi thực hiện lại chương trình đã có thể hoàn tất việc download với kết quả download được 145 tập tin *.html (thêm 83 tập tin) so với yêu cầu ban đầu là 150. Kết quả trên là chấp nhận được so với hiện trạng Internet của ta hiện nay và hoàn toàn đáp ứng được cho nhu cầu cài đặt phục vụ thư viện số. Trong Bảng 4.5 bên dưới là một phần của kết quả được lưu lại trong cơ sở dữ liệu dùng để phục vụ cho hoạt động của thư viện số. (những vị trí có giá trị 1 trong trường filespec có nghĩa là đã tiến hành dowload nhưng không thể hoàn tất được) 4-22 Bảng 4.5: Kết quả mẫu trong cơ sở dữ liệu Trong Hình 4.6 và 4.7 bên dưới là một phần nội dung của hai trang Web đã download được liên quan đến từ khóa “AOP”. 4-23 Hình 4.6 Hình 4.7 4-24 Trong phần kết của chương, nhóm phần mềm xin trình bày biểu đồ thống kê sự hoạt động của Search Agent theo những số liệu mà chúng tôi thu thập được trong quá trình chạy thử chương trình. Mỗi đường trong biểu đồ cho biết khả năng làm việc của chương trình theo từng thời điểm trong ngày ( số tập tin mà chương trình đã download được trong một giờ ). Từ kết quả thống kê, chúng ta nhận thấy, chương trình download làm việc tốt nhất trong khoảng từ 1 đến 2 giờ sáng. Kết quả này đã giúp chúng tôi ấn định giờ kích hoạt cho hệ thống. 5-1 CHƯƠNG 5 TÌM DÃY TỪ PHỔ BIẾN ĐỂ ĐẶC TRƯNG VĂN BẢN VÀ HỖ TRỢ BIÊN MỤC TỰ ĐỘNG 5.1 CÂY HẬU TỐ MỞ RỘNG Cây hậu tố T là một cây có hướng có gốc, biểu diễn một chuỗi s bất kỳ có chiều dài m với đúng m nút lá. Mỗi cạnh trên cây hậu tố đều được gán nhãn bằng một chuỗi con khác rỗng của chuỗi s . Các nhãn của hai cạnh bất kỳ xuất phát từ một nút chung phải bắt đầu bằng các ký tự khác nhau. Đối với nút lá của cây hậu tố, việc kết các nhãn của các nút nằm trên con đường đi từ gốc đến nút lá đó sẽ tạo thành một hậu tố của chuỗi s. Cây hậu tố mở rộng là một cây hậu tố nhằm kết tất cả các hậu tố của các trình tự trong tập chuỗi S. Ví dụ : Hình 5.1 là cây hậu tố ứng với chuỗi ACGACT. Các hậu tố của chuỗi trên là: ACGACT; CGACT; GACT; ACT;CT;T. Hình 5.1: Cây hậu tố 5.1.1 Lý do sử dụng cây hậu tố mở rộng Thao tác đầu tiên hệ thống phải thực hiện là phải tìm và lưu trữ tất cả các dãy từ ( tập các từ liền nhau) trong một văn bản, tập văn bản và toàn bộ thông tin cần thiết của chúng. Điều này dẫn đến khó khăn rất lớn cho hệ thống vì số lượng các dãy từ trong mỗi văn bản có kích thước, cấu trúc câu, cách viết câu khác nhau rất lớn. Điều này có thể được chứng minh như sau: 5-2 -Số dãy từ trong câu có thể tăng theo bình phương số từ của câu đó: Giả sử câu S gồm n từ W1 W2…Wn.Khi đó,các dãy từ của S sẽ gồm: o Bắt đầu bằng W1 có n dãy từ: W1,W1W2,……,W1W2…Wn o Bắt đầu bằng W2 có n-1 dãy từ: W2,W2W3,……,W2W3…Wn ........................................................................................................ o Bắt đầu bằng Wn có 1 dãy từ: Wn Nếu các từ trong câu S là khác nhau từng đôi một thì số dãy từ tối đa của S sẽ là : ∑ = n i i 1 = n*(n+1)/2 ≈ n2/2 dãy từ - Số dãy từ trong văn bản tăng theo bình phương kích thước của nó: Giả sử văn bản d gồm k câu: o S1 có n1 từ (có tối đa n12/2 dãy từ) o S2 có n2 từ (có tối đa n22/2 dãy từ) o ………………… o Sk có nk từ (có tối đa nk2/2 dãy từ) Khi đó, số dãy từ tối đa của văn bản d sẽ là: ∑ = k i 1 ni2/2 ≤ (∑ = k i 1 ni)2/2 = n2/2 với n là số từ trong văn bản d. Trong trường hợp xấu nhất, văn bản d chỉ có một câu, mỗi từ là một kí tự thì khi đó n = Kích thước (d)/2. Khi đó, số dãy từ tối đa của d có thể sẽ là : Kích thước(d)2/8. Qua chứng minh trên , ta nhận xét rằng, số lượng dãy từ phải xử lý trong các văn bản là rất lớn.Vì vậy việc ghi nhận và xử lý chúng mất rất nhiều thời gian và không gian lưu trữ. Điều này bắt buộc hệ thống phải thỏa mãn các yêu cầu chính về mặt tìm kiếm và lưu trữ, hệ thống phải thỏa mãn một số yêu cầu sau: • Tính hiệu quả:việc tìm kiếm phải tiến hành với tốc độ chấp nhận, lưu trữ thuận lợi cho việc rút trích các đặc trưng của các văn bản với không gian lưu trữ tối ưu. 5-3 • Tính dễ mở rộng (Tính tăng cường): Trên thực tế, các văn bản trong tập văn bản không phải cố định mà càng ngày càng được tăng cường mở rộng theo nhu cầu và tính chất công việc của người sử dụng.Lấy ví dụ:Giả sử ban đầu tập văn bản chỉ có 10 văn bản nhưng sau đó cần phải xử lý trên tập văn bản mới gồm 20 văn bản trong đó có 10 văn bản của tập ban đầu. Việc xử lý lại từ đầu 20 văn bản này là rất khó khăn và tốn kém về mặt thời gian và chi phí. Do vậy, hệ thống phải được xây dựng sao cho có thể kế thừa các kết quả phân tích và xử lý của tập văn bản ban đầu. Nói cách khác, hệ thống phải có khả năng tăng cường tức là từ tập D={d1,d2,,dn} có thể dễ dàng phát triển với tập D’ với D⊂D’ 5.1.2 Các đặc điểm nổi bật của cây hậu tố Cây hậu tố là cấu trúc dữ liệu thích hợp để giải quyết bài toán tìm kiếm và lưu trữ các cụm từ cũng như các thông tin liên quan của nó trong từng văn bản và tập văn bản. Các đặc điểm chính của cây hậu tố có thể tóm lược là: - Dễ mở rộng (tính tăng cường): đây là một trong những đặc điểm chính của cây hậu tố. Cây hậu tố có thể được tăng cường vào thêm 1 hoặc nhiều văn bản mà không cần phải thực hiện việc tìm kiếm các dãy từ lại từ đầu. Đặc điểm này cho phép hệ thống dễ dàng “học” mở rộng với tập văn bản lớn với nhiều loại văn bản khác nhau và đồng thời giảm rất nhiều thời gian xử lý. Đặc điểm này giúp hệ thống không bị giới hạn về không gian làm việc cũng như khối lượng dữ liệu. - Các dãy từ không bị giới hạn về chiều dài vì chiều cao của cây hậu tố không bị giới hạn.Đặc điểm này cho phép hệ thống có khả năng xử lý được nhiều loại văn bản có các câu rất dài (nhiều từ). -Việc rút trích các thông tin về các dãy từ phục vụ cho việc rút trích các đặc trưng văn bản rất dễ dàng và nhanh chóng. 5-4 5.1.3 Các thành phần của cây hậu tố Cây hậu tố được tổ chức thành cây gồm nhiều nút. Mỗi nút sẽ lưu trữ tất cả các thông tin về các cụm từ ( tần số xuất hiện trong tập văn bản, tần số xuất hiện trong từng văn bản) trong khi quan hệ giữa chúng lại nói lên sự tồn tại của các cụm từ.Thành phần mỗi nút như sau: key count listid child next Mô tả chi tiết: Mỗi nút của cây hậu tố gồm có 2 thành phần key, count lưu trữ dữ liệu thật sự của mỗi nút và 3 thành phần listid , child , next là các con trỏ cho biết mối quan hệ giữa các nút với nhau. Có 2 loại quan hệ giữa các nút. Đó là: -Quan hệ“anh em”:Hai nút m, n được gọi là 2 nút anh em nếu: (i) Thành phần next của m trỏ đến nút n (ii) Thành phần next của n trỏ đến nút m (iii)Tồn tại nút k sao cho: (m,k),(n,k) là 2 cặp nút anh em -Quan hệ “cha con”:Nút m là nút cha của n nếu: (i) Thành phần child của m trỏ đến nút n (ii)Tồn tại nút k sao cho:m là cha của k,k là anh em với n Chi tiết các thành phần của mỗi nút được qui ước như sau: • Child: Đây là con trỏ trỏ đến nút con của nút hiện hành. Con trỏ này cũng nói lên sự tồn tại của các cụm từ. Giả sử có cụm từ W1 W2 … Wn khi đó để lưu trữ cụm từ này, cây hậu tố phải được tổ chức sao cho tồn tại đường đi từ nút gốc đến các nút N1, N2, …, Nn ( Ni.Key = Wi ∀ i∈{1,…,n}) nghĩa là: (i)Nút gốc là nút cha của N1 (ii)Nút Ni là nút cha của Ni+1 ∀ i∈{1,…,n-1} (Trong đó nút gốc có trường Key là rỗng) 5-5 Bên cạnh đó, việc sử dụng con trỏ này cho phép ta xây dựng cây hậu tố có chiều cao không bị giới hạn và điều đó cho phép hệ thống của chúng ta có thể xử lý được nhiều câu rất dài. • Next:Trỏ đến nút anh em kế tiếp của nút hiện hành. Con trỏ này nói lên quan hệ anh em giữa nút hiện hành và nút mà nó trỏ đến. Việc sử dụng con trỏ này làm giảm đáng kể không gian lưu trữ. Giả sử ta có 2 dãy từ như sau: Dãy từ 1:W1 W2…Wi Wi+1..Wn Dãy từ 2:W1 W2…Wi W’i+1 … W’m Hai dãy từ trên có i từ đầu giống nhau và Wi+1 ≠ W’i+1. Giả sử đã tồn tại một đường đi từ nút gốc đến N1,N2,…,Nn(Ni.Key=Wi∀ i∈{1,…,n}) . Khi đó, để lưu trữ dãy từ 2 ta phải tạo các nút Mi+1,…,Mm (Mj.Key = W’j ∀ j ∈{i+1,…,m} và Mj là nút cha của Mj+1∀ j∈ {i+1,…,m-1}) và được nối với cụm từ 1 thông qua việc gán Ni+1.Next = Địa chỉ nút (Mi+1). Rõ ràng chúng ta chỉ cần n+(m-(i+1)+1) = n+m-i nút để lưu trữ 2 dãy từ này. Điều này làm giảm đáng kể không gian lưu trữ. Bằng việc dùng các con trỏ Child và Next, hệ thống có khả năng mở rộng với tập văn bản lớn hơn. • Key: Lưu trữ một từ. Gọi nút hiện hành này là N và giả sử con đường đi từ nút gốc đến nút hiện hành có dạng như sau:N1, N2, …,Nn, N. Điều này có nghĩa là ta đã lưu dãy từ N1.key … Nn.key N.key trên cây hậu tố. Nói cách khác,thành phần này lưu trữ từ cuối cùng của dãy từ có các từ là giá trị khoá của các nút trong đường đi từ nút gốc đến nút hiện hành. • Listid: Đây là con trỏ trỏ đến danh sách các văn bản chứa cụm từ kể từ nút gốc đến nút hiện hành như đã mô tả trong phần trên. Mỗi phần tử trong danh sách gồm có các thành phần sau: id count next 5-6 Ý nghĩa các thành phần như sau: STT THÀNH PHẦN Ý NGHĨA 1 id Mã số văn bản chứa cụm từ đang xét 2 count Số lần (tần xuất) xuất hiện của cụm từ đang xét trong văn bản Id 3 next Trỏ đến phần tử kế tiếp • Count: Cho biết số lần xuất hiện (tần xuất) của cụm từ kể từ nút gốc đến nút hiện hành trong tập văn bản ( hay số văn bản có chứa cụm từ đang xét).Như vậy, số phần tử trong danh sách liên kết trỏ bởi thành phần listid phải đúng bằng count. Ví dụ: Chúng ta có 3 văn bản như sau: Văn bản 1: Cat ate cheese; Văn bản 2: Mouse ate cheese too. Văn bản 3: Cat ate mouse too. Khi đó, cây hậu tố của tập D = {văn bản 1, văn bản 2, văn bản3} sẽ có dạng như hình vẽ 5.2. Con số trên mỗi nút cho biết số văn bản chứa cụm từ(tính từ gốc).Các con số trong dấu ngoặc [] cho biết mã của các văn bản có chứa những cụm từ này. Hình 5.2: Cây hậu tố của tập văn bản {d1,d2,d3} cat root Che mo too ate ches mo too mo too too ate too che too 2 [1 3] 2 [1 2] 2 [2 3] 2 [2 3] 2 [1 3] 1 [1] 1 [3] 1 [3] 1 [3] 1 [2] 1 [2] 1 [2] 1 [2] 1 [3] ate Ch 3 [1,2,3] 2[1 2] 5-7 Trong caây haäu toá, caùc nuùt caøng naèm ôû möùc cao (gaàn nuùt goác) caøng chöùa ít vaên baûn. Ñieàu naøy phuø hôïp vôùi thöïc teá vì nhöõng cuïm töø caøng daøi (coù nhieàu chöõ ) thì caøng hieám xuaát hieän trong taäp vaên baûn thaäm chí ngay caû trong töøng vaên baûn thaønh phaàn. Ñaây cuõng laø nhöõng ñaëc ñieåm noåi baät cuûa caây haäu toá. Ñaëc ñieåm naøy cho pheùp ngöôøi söû duïng coù theå tìm kieám caùc cuïm töø phoå bieán nhanh choùng hôn so vôùi caùc phöông phaùp khaùc vì khi duyeät caây neáu nuùt cha coù soá löôïng caùc vaên baûn nhoû hôn ngöôõng truy vaán cho tröôùc thì taát caû caùc nuùt con cuûa noù khoâng caàn phaûi xem xeùt. 5.1.4 Löu tröõ caây haäu toá Caâyhaäu toá laø moät caáu truùc döõ lieäu phöùc taïp vaø khoâng ngöøng phaùt trieån môû roäng theo soá löôïng caùc vaên baûn trong caùc taäp vaên baûn maø chuùng ta caàn phaân cuïm. Do ñoù, heä thoáng khoâng theå löu tröõ caây haäu toá treân boä nhôù maø phaûi löu tröõ treân ñóa.Vieäc löu tröõ caây haäu toá treân ñóa ngoaøi yeâu caàu baûo ñaûm söï chính xaùc vaø toaøn veïn döõ lieäu coøn phaûi baûo ñaûm ñöôïc caùc tính chaát quan troïng khaùc cuûa caây haäu toá nhaát laø tính taêng cöôøng. Löu tröõ caây haäu toá chính laø löu tröõ caùc nuùt vaø moái quan heä giöõa caùc nuùt cuûa chuùng. Caùc nuùt cuûa caây haäu toá ñöôïc löu tröõ treân ñóa döôùi daïng caùc Record. Caùc Record naøy seõ löu tröõ caùc thoâng tin cuûa nuùt cuõng nhö moái quan heä giöõa caùc nuùt vôùi nhau. Caáu truùc naøy ñöôïc ñònh nghóa trong ngoân ngöõ C nhö sau: typedef struct { char key[20]; DWORD count; DWORD listid; DWORD child; DWORD next; }NODE; 5-8 Moâ taû chi tieát caùc tröôøng cuûa caáu truùc NODE: STT Tröôøng YÙ nghóa Kieåu Raøng buoäc 1 Key Löu tröõ khoùa cuûa nuùt ñang xeùt trong caây haäu toá Chuoãi Chieàu daøi khoâng quaù 20 bytes 2 count Löu tröõ soá löôïng vaên baûn cuûa nuùt ñang xeùt Soá nguyeân Khoâng aâm 3 listid Vò trí cuûa danh saùch maõ soá caùc vaên baûn treân ñóa Soá nguyeân Khoâng aâm 4 child Vò trí nuùt con ñaàu tieân cuûa nuùt ñang xeùt treân ñóa Soá nguyeân Khoâng aâm 5 next Vò trí nuùt anh em ñaàu tieân cuûa nuùt ñang xeùt treân ñóa Soá nguyeân Khoâng aâm Tuy nhieân ñeå giaûm kích thöôùc file löu tröõ caây haäu toá, ta coù theå löu tröõ maõ soá caùc vaên baûn taïi moãi nuùt leân moät file döõ lieäu khaùc nhaèm giaûm thôøi gian ñoïc vaø di dôøi ñaàu ñoïc cuûa ñóa. File naøy cuõng ñöôïc toå chöùc döôùi daïng caùc Record lieân tieáp nhau vôùi caáu truùc ñöôïc ñònh nghóa nhö sau: typedef struct { DWORD id; DWORD count; DWORD next; } LISTID; Moâ taû chi tieát caùc tröôøng cuûa caáu truùc LISTID: STT Tröôøng YÙ nghóa Kieåu Raøng buoäc 1 Id Maõ soá cuûa vaên baûn chöùa cuïm töø ñang xeùt Soá nguyeân Khoâng aâm 2 count Soá laàn xuaát hieän cuïm töø ñang xeùt trong vaên baûn coù maõ soá laø id Soá nguyeân Khoâng aâm 3 next Vò trí cuûa phaàn töû khaùc treân ñóa Soá nguyeân Khoâng aâm 5-9 5.2 CÁC THUẬT GIẢI TRÊN CÂY HẬU TỐ 5.2.1 Thuật giải tăng cường “Thuật giải tăng cường” là một loại thuật giải quan trọng trong việc giải quyết bài toán tăng cường được sử dụng trong các lĩnh vực khai thác dữ liệu. Mục đích của việc tăng cường là cho phép người sử dụng có thể tận dụng lại các kết quả đã được xây dựng trước và làm giảm tối thiểu thời gian, chi phí xử lý của hệ thống. Thuật giải tăng cường chủ yếu nhằm để lưu trữ các dãy từ trong tập văn bản cũng như tần số xuất hiện của nó trong từng văn bản và toàn tập văn bản. Khi ta tăng cường thêm một số văn bản vào tập văn bản ban đầu, hệ thống sẽ tự động thêm và cập nhật lại các thông tin về các dãy từ trong hệ thống. Để tăng cường các văn bản vào cây hậu tố, các văn bản trước hết sẽ được qua bước tiền xử lý để lọc những thông tin không cần thiết. Sau đó, hệ thống sẽ lấy các câu trong từng văn bản và các hậu tố của các câu này sẽ được thêm và cập nhật vào cây hậu tố. Hậu tố của một câu là tất cả các từ nằm liên tiếp nhau trong câu đó. Ví dụ: Câu “cat ate cheese” có các hậu tố là: ƒ cat ate cheese, cat ate, cat ƒ ate cheese,ate ƒ cheese Giả sử trong văn bản d có câu S = T0 T1 … Tm-1 với m là số chữ của S và Ti (i ∈ {0,1,..,m-1}) là các chữ của nó. S có thể có nhiều hậu tố khác nhau. Gọi các hậu tố của câu S là Suffix(S). Thuật giải tăng cường câu S trong văn bản d sẽ được thực hiện thông qua việc tăng cường từng hậu tố của nó S vào trong cây. Việc tăng cường hậu tố sf ∈ Suffix(S) trong đó sf = W0 W1 …Wn-1 với n là số chữ của sf được tiến hành như sau: -Tìm số nguyên j lớn nhất (0 ≤ j ≤ n) sao cho W0 W1…Wj-1 là một nhánh trong cây hậu tố. Gọi nhánh vừa tìm được là N0 N1 … Nj-1 với Ni là 5-10 nút cha của Ni+1 ∀ i ∈{0,1,…,j-2}. Gọi d(N) là danh sách phần tử LISTID tại nút N. Khi đó, tại mỗi nút Ni ta kiểm tra xem có phần tử nào trong d(Ni) có thành phần mã id là d hay không? Có hai trường hợp xảy ra: (i) Nếu phần tử k trong d(Ni) có mã văn bản id thì ta phải tăng giá trị k.count lên 1 đơn vị nghĩa là tăng số lần xuất hiện của hậu tố sf trong văn bản d lên 1. (ii)Nếu không có phần tử nào trong d(Ni) có thành phần mã văn bản bằng d thì ta phải thêm phần tử LISTID mới vào trong d(Ni) với thành phần mã văn bản id là d và thành phần count của nó là 1. Điều này có nghĩa là hệ thống ghi nhận sự xuất hiện của dãy từ đang xét trong văn bản d và số lần xuất hiện của sf trong d tạm thời là 1. Cuối cùng tăng trường count của nút hiện hành lên 1 để cập nhật lại tần số xuất hiện của dãy từ sf trong tập văn bản. -Gọi C là tập hợp các nút con của nút Nj-1.Giả sử C gồm t phần tử là C0, C1, …, Ct-1. Trong đó thành phần con trỏ next của Ci trỏ đến Ci+1 ( i = {0,1,..,t-1}). Tạo nhánh mới Nj, Nj+1, …,Nn-1 mà mỗi nút trong danh sách này là nút cha của nút đứng phía sau nó và thành phần khóa của mỗi nút Ni (i = {j,…...,n-1}) chính là Wi và thành phần listid của Ni chỉ có đơn giản có một phần tử có mã văn bản là d và tần số xuất hiện trong d là 1. Sau đó, để gắn nhánh mới này vào cây hậu tố ta chỉ việc cho con trỏ next của nút Ck (với Ck.Key 0), con trỏ next của Nj trỏ đến nút Ck+1 (nếu k+1<t) . Trong trường hợp t=0 ( nút Nj-1 không có nút con) ta cho con trỏ child của nút Nj-1 trỏ đến Nj. Chi tiết thuật giải tăng cường trên cây hậu tố: Input: (i) Câu S = W0 W1 Wn-1 , n : số chữ trong S (ii) Văn bản d chứa câu S (iii)Cây hậu tố đã xây dựng sẵn Output: Cây hậu tố sau khi tăng cường với các cụm từ được sắp xếp 5-11 Bước 1: j = 0 m = 1 Xét nút gốc N Bước 2: Nếu N.key = Wj thì { j = j + 1 Nếu N.child khác NULL thì làm { m = 1 N = N.child Trở lại bước 2 } Ngược lại:Qua bước 4 } Ngược lại qua bước 3 Bước 3: Nếu N.next khác NULL thì { N = N.next m = m + 1 Trở lại bước 2 } Qua bước 4 Bước 4: Tạo nhánh Nj Nj+1 … Nn-1 bằng cách For i=j to n-1 do { 5-12 Ni.key = Wi Ni.listid = (d, 1) } for i=j+1 to n-1 do { Ni-1.child = Ni } Bước 5: • Nếu m > 0 thì Nj-1.next = Nj • Ngược lại Nj-1.child = Nj Bước 6: • Loại chữ đầu tiên ra khỏi câu S để xét các hậu tố khác • n = n-1 • Nếu n=0:dừng thuật toán • Ngược lại:trở lại Bước 1 xử lý cho hậu tố S Quá trình này sẽ kết thúc khi n = 0 nghĩa là khi đã cập nhật toàn bộ các hậu tố của câu S ban đầu vào cây hậu tố. 5.2.2 Thuật giải duyệt cây hậu tố Mục đích của việc duyệt cây hậu tố nhằm cho phép người sử dụng có thể xem toàn bộ các thông tin về các dãy từ trong toàn tập văn bản. Số lượng các dãy từ trong toàn tập văn bản cũng như trong các văn bản thành phần là rất lớn nên kích thước cây hậu tố cũng rất lớn. Điều này không cho phép sử dụng các thuật giải duyệt cây đệ quy truyền thống để duyệt toàn bộ nội dung của nó. Thuật giải duyệt cây hậu tố được xây dựng trong đề tài này là thuật toán không dùng phương pháp đệ quy, có khả năng hiển thị toàn bộ các thông tin về các cụm từ trong toàn tập văn bản với cây hậu tố có kích thước lớn. 5-13 Trong đề tài này, phương pháp duyệt theo chiều sâu được áp dụng để duyệt toàn bộ nội dung của cây hậu tố. Đầu tiên ta xem xét nút gốc. Sau khi xem xét xong nút hiện hành, ta lại xét các nút con của nó cho đến khi gặp nút lá. Tại nút này ta tiến hành quay ngược lên các nút cha của nó. Quá trình quay ngược sẽ dừng khi ta gặp nút gốc thì chấm dứt quá trình duyệt hoặc đến nút cha nào đó mà tại nút này vẫn còn những nút “anh em” chưa được duyệt và ta lại duyệt tiếp nút kế nó.Vì số nút trong cây hậu tố là hữu hạn nên quá trình này sẽ kết thúc sau một thời gian cụ thể. Thuật giải duyệt cây được tiến hành qua các bước : Input: Cây hậu tố Output: Thông tin của cây hậu tố Bước 1: k = 0 N0=nút gốc Bước 2:(duyệt theo chiều sâu) Duyệt Nk Nếu Nk.child khác NULL thì { k = k + 1 Nk+1 = Nk.child Trở lại Bước 2 } Ngược lại qua bước 3 Bước 3:(Quay lui) k = k – 1 Nếu k < 0:(đến nút gốc) dừng thuật toán Ngược lại: Nếu Nk.next khác NULL thì { Nk = Nk.next 5-14 Quay lại bước 2 } Ngược lại:quay lại Bước 3 Ví dụ: Với tập văn bản gồm 3 văn bản sau: d1:cat ate cheese d2:mouse ate cheese too d3:cat ate mouse too thì các dãy từ của tập văn bản này là: ate [3]( 1 2 3) ate cheese [2]( 2 3) ate cheese too [1]( 2) ate mouse [1]( 1) ate mouse too [1]( 1) cat [2]( 1 3) cat ate [2]( 1 3) cat ate cheese [1]( 3) cat ate mouse [1]( 1) cat ate mouse too [1]( 1) cheese [2]( 2 3) cheese too [1]( 2) mouse [2]( 1 2) mouse ate [1]( 2) mouse ate cheese [1]( 2) mouse ate cheese too [1]( 2) mouse too [1]( 1) too [2]( 1 2) 5-15 5.2.3 Thuật giải tìm dãy từ phổ biến Dãy từ là tập hợp nhiều từ đứng cạnh nhau, có thể không có ý nghĩa về mặt cú pháp và ngữ nghĩa. Dãy từ phổ biến là dãy từ có số lần xuất hiện trong tập văn bản lớn hơn một ngưỡng cho trước. Thuật giải tìm kiếm các dãy từ phổ biến theo ngưỡng phổ biến τ được tiến hành qua các bước sau: Input: Cây hậu tố Ngưỡng τ Output: Tập các dãy từ phổ biến Bước 1: k = 0 N0= nút gốc T = φ Bước 2:(duyệt theo chiều sâu) Nếu Nk.count >=τ thì { T = T ∪ {Nk.key} Nếu Nk.child khác NULL thì { k = k + 1 Nk+1 = Nk.child Trở lại Bước 2 } Ngược lại qua bước 3 } Ngược lại: { 5-16 Thông báo T là dãy từ phổ biến Qua bước 3 } Bước 3:(Quay lui) T = T \ {Nk.key} k = k – 1 Nếu k < 0:(đến nút gốc) dừng thuật giải Ngược lại: Nếu Nk.next khác NULL thì { Nk = Nk.next Quay lại bước 2 } Ngược lại:quay lại Bước 3 Ví dụ: Một số dãy từ phổ biến được phát hiện từ việc phân tích khối ngữ liệu văn bản các tóm tắt báo cáo khoa học, với ngưỡng được chọn là 2 (văn bản): text, retrieval, using, map, documents, organized, model, space, of*a, document, k, able to, algorithm, as the feature vectors, som, of the about, the mapping, documents, million, patent, search, keyword selection method,characterizing, of data the clusters, the method, order, websom, textual data, and filtering, information, a tool, text documents, document maps, maps, method, on the, encoded,word,self-organizing, dimensionality reduction is,random, the data, the original dimensionality, vectors. 5-17 5.3 TẠO VECTOR ĐẶC TRƯNG VĂN BẢN 5.3.1.Mô hình không gian vector các dãy từ phổ biến trong khối ngữ liệu Trong mô hình không gian vector có thành phần là các dãy từ (các từ liền nhau) xuất hiện phổ biến trong ít nhất là hai văn bản, mỗi văn bản được đại diện bằng vector các dãy từ phổ biến. Một tập các văn bản (khối ngữ liệu) được đại diện bằng một ma trận A có dòng là văn bản và cột là các dãy từ phổ biến. Mỗi phần tử aik của ma trận A cho biết trọng số của dãy từ k trong văn bản thứ i. Gọi M là số dòng của ma trận (số văn bản) trong khối ngữ liệu, gọi N số cột (số dãy từ phổ biến) của khối dữ liệu, fik là tần số xuất hiện của dãy từ phổ biến thứ k trong văn bản i, nk là số văn bản có chứa dãy từ phổ biến thứ k trong khối ngữ liệu. Có nhiều cách để ấn định trọng số aik. Một số cách tiêu biểu như: a) Trị nhị phân aik = 1 nếu fik ≥ 0 và aik = 0 nếu ngược lại b) Tần số của dãy từ aik = fik c) Hệ số tfidf Các cách trên không tính đến tần số của dãy từ phổ biến trong tất cả các văn bản trong khối ngữ liệu. Một tiếp cận khác để tính trọng của dãy từ là sử dụng hệ số tfidf ( term frequency. Inversed document frequency) để gán trọng cho dãy từ k trong văn bản i là aik = fik x log( M/nk ) 5.3.2. Rút gọn chiều Như đã trình bày ở trên mỗi dãy từ phổ biến sẽ ứng với một chiều trong không gian vector đặc trưng cho văn bản. Trong khối ngữ liệu lớn với hàng ngàn văn bản, số dãy từ phổ biến có thể lên đến hàng chục ngàn. Do vậy cần các phương pháp để rút gọn chiều của không gian vector đại diện văn bản. Mục đích của bước rút gọn chiều là loại bỏ các từ hoặc dãy từ không chứa thông tin để cải thiện khả năng đặc trưng của vector cho văn bản. Một số phương pháp rút gọn chiều tiêu biểu có thể liệt kê như sau: 5-18 a)Ngưỡng tần số văn bản Tần số văn bản của một dãy từ là số lượng văn bản có chứa dãy từ đó. Các từ hoặc dãy từ có tần số văn bản nhỏ hơn hoặc bằng một ngưỡng cho trước (ngưỡng tần số văn bản) sẽ bị loại bỏ. b)Các hư từ hoặc từ kết thúc Các hư từ là các từ xuất hiện phổ biến nhưng không mang thông tin nào cả. Trong các văn bản tiếng Anh các hư từ thường là giới từ, đại từ, liên từ như: a, an, i , of, about, where, that, when. . . 5.3.3. Tạo vector đặc trưng văn bản 5.3.3.1. Tiếp cận truyền thống Khối ngữ liệu văn bản được phân tích để tìm các dãy từ phổ biến. Sau khi rút gọn đặc trưng, các vector nhị phân đặc trưng cho văn bản sẽ được tạo theo cơ chế trị nhị phân. Thành phần thứ aik =1 nếu văn bản i có chứa dãy từ k và aik=0 nếu ngược lại. Một văn bản bản được đại diện bởi một điểm trong không gian n chiều (n là số dãy từ phổ biến trong khối ngữ liệu nhiều văn bản), trong đó mỗi thành phần của véc tơ có giá trị 1 hay 0 tùy thuộc vào sự có mặt hay không của cụm từ đó trong văn bản hiện hành ta đang xét. Goi T = {T1, T2,…,Tm} là tập các dãy từ phổ biến với ngưỡng τ Mỗi văn bản di ∈ D sẽ được đặc trưng thành vector vi m chiều Trong đó: vi = với 0 nếu Tj không xuất hiện trong di vij = 1 nếu Tj xuất hiện trong di Ví dụ: Giả sử ta có 3 văn bản: 5-19 d1:“cat ate cheese” d2: “mouse ate cheese too” d3: “cat ate mouse too” Với ngưỡng τ = 2, ta có 7 cụm từ phổ biến là: T ={cat, cat ate, ate, ate cheese, cheese, mouse, too} Khi đó: d1 đặc trưng thành v1(1, 1, 1, 1, 1, 0, 0) d2 đặc trưng thành v2(0, 0, 1, 1, 1, 1, 1) d3 đặc trưng thành v3(1, 1, 1, 0, 0, 1, 1) 5.3.3.2. Tiếp cận cải tiến có sử dụng từ gần nghĩa Trong tâp các dãy từ phổ biến này có thể có các từ đồng nghĩa hoặc gần nghĩa với nhau. Ví dụ tập các dãy từ phổ biến có chứa từ "man" và "person". Giả sử trong văn bản thứ nhất có chứa từ "man" và không có chứa từ "person", trong văn bản thứ hai có chứa từ "person" nhưng không có chứa từ "man". Theo cách truyền thống vector đặc trưng cho văn bản thứ nhất sẽ có trị 1 ứng với thành phần "man" và có trị 0 ứng với từ "person"; vector đặc trưng cho văn bản hai sẽ có trị 0 ứng với thành phần "man" và có trị 1 ứng với từ "person". Tuy vậy, giữa từ "person" và từ "man" có liên hệ về nghĩa với nhau vì man (người đàn ông, nhân loại) và person( người) nhưng trong tiếp cận truyền thống không xem xét khả năng này. Gần đây một số tác giả như Elle M. Voorhees (1998), Darin Brezeale(1999) đã quan tâm đến từ đồng nghĩa trong mô hình vector đặc trưng cho văn bản nhằm nâng cao khả năng phân lớp hoặc gom cụm văn bản trong đó quan hệ giữa các văn bản được bổ sung thêm quan hệ gần nghĩa giữa các từ. Sau khi đã phát hiện được các từ gần nghĩa nhau, Darin Brezeale đã điều chỉnh các thành phần của vector nhị phân đặc trưng cho văn bản. Trong ví dụ trên, văn bản thứ nhất có chứa từ "man" và không có chứa từ "person" nhưng do từ "man" và "person" có quan hệ gần nghĩa nên thành phần "person" trong vector đặc trưng cho văn bản thứ nhất sẽ được điều chỉnh thành trị 1. Vấn đề đặt ra là làm thế 5-20 nào để đo đạc mức độ đồng nghĩa giữa hai từ? Darin Bre.zeale(1999) đã sử dụng WordNet được cung cấp miễn phí trên Internet để thực hiện vần đề này. WordNet là tên của một dự án được khởi động từ năm 1985 do George Miller đề xướng nhằm thiết kế hệ thống cho phép tra cứu từ điển tiếng Anh theo khái niệm của từ. WordNet hiện đang được lưu trên Internet và có thể mang về sử dụng trên máy tính cá nhân. Wordnet tổ chức thông tin theo nghĩa của từ thay vì dạng từ. Như trong các từ điển tiếng Anh truyền thống, Wordnet chứa các thông tin cơ bản về từ. Bên cạnh đó, WordNet còn chứa một thông tin hữu ích là các quan hệ giữa các từ trong đó có quan hệ đồng nghĩa và quan hệ hypernym. Quan hệ hypernym của một từ là một từ tổng quát hơn thỏa phát biểu " là một loại của ". Ví dụ tree "là một loại của" plant, plant "là một loại của" organism". Hình 5.3 là một đồ thị biểu diễn quan hệ " là một loại của" của các từ organism, plant, flora, tree, bush, aralia. Hình 5.3. Ñoà thò quan heä hypernym giöõa caùc danh töø WordNet lưu trữ các danh từ, động từ, tính từ, trạng tự. Trong tiếp cận của Darin Brezeale, chỉ sử dụng danh từ làm cơ sở phát triển thuật giải. Theo G.Miller, WordNet có 25 nhóm danh từ như sau: Organism Plant Flora Tree Bush Aralia 5-21 {act, activity} {animal,fauna} {artifact} {attribute} {body} {cognition,knowledge} {communication} {event, happening} {feeeling, emotion} {food} {group, grouping} {location} {motivation, motive} {natural object} {natural phenomenon} {person, human being} {plant, flora} {possesion} {process} {quantity, amount} {relation} {shape} {state} {substance} {time} WordNet cung cấp nhiều cách để xác định các từ có quan hệ ngữ nghĩa với nhau. Tiếp cận của Darin Brezeale đã sử dụng cấu trúc cây hypernym của một từ nhằm phát hiện quan hệ gần nghĩa của hai từ. Sau khi đã xác lập được cây chứa hai từ cần xét, sẽ duyệt cây để xem hai từ này có chung tổ tiên hay không và tính số nút từ nút ứng với từ cần xét đến nút tổ tiên chung. Khoảng cách ngữ nghĩa giữa hai từ bằng tổng khoảng cách của con đường đi từ hai từ đến nút tổ tiên chung. Khoảng cách này càng ngắn thì hai từ càng gần nghĩa. Ví dụ với cây hypernym trong hình 5.3, khoảng cách giữa từ "tree" và từ "flora" là 3, khoảng cách giữa từ "plant" và "flora" là 2. Để điều chỉnh các thành phần của vector nhị phân đặc trưng văn bản ừng với các từ gần nghĩa, Darin Brezeale đã sử dụng ngưỡng gần nghĩa. Chỉ có các căp từ có mức độ gần nghĩa nhỏ hơn hoặc bằng ngưỡng này thì các thành phần tương ứng trong vector đặc trưng mới bị điều chỉnh. Ngưỡng này thuờng được chọn là 3, do vậy từ "tree" và "flora" trong cây hypernym ở hình 5.3 được xem là đồng nghĩa và các thành phần tương ứng với các từ này trong vector đặc trưng đều bị điều chỉnh. 5-22 5.4. DÙNG CÂY HẬU TỐ HỖ TRỢ TẠO TIÊU ĐỀ ĐỀ MỤC Phần này trình bày các buớc sử dụng cây hậu tố đề tìm các dãy từ phổ biến tối đại trong một khối ngữ liệu gồm nhiều văn bản. Sau đó sử dụng tập hợp các từ phổ biến nhằm tiền xử lý dữ liệu (biên mục tài liệu) . Qui trình gồm các bước sau: Buớc 1: Sử dụng cây hậu tố để tìm danh sách các dãy từ phổ biến trong một khối ngữ liệu gồm nhiều văn bản Buớc 2: Sử dụng danh sách các dãy từ phổ biến để biên mục các tập tin trong khối ngữ liệu và tạo danh sách tiền kết hợp tập văn bản vào danh sách các dãy từ phổ biến. Bước 3:Tra cứu thư viện thông qua danh sách tiền kết hợp Kết quả thử nghiệm: 1.Danh sách các dãy từ phổ biến được phát hiện từ các kho ngữ liệu thử nghiệm và số văn bản có chứa dãy từ phổ biến. STT Dãy từ phổ biến Số văn bản ================================================ 1 : annotated 2 2 : automatic 11 3 : bilingual corpus 3 4 : in the 15 5 : in this 2 6 : method 24 7 : model for 2 8 : natural language processing 3 9 : of information 2 10 : the accuracy of 2 11 : this problem 4 12 : to solve 4 13 : we will 4 14 : extract 5 15 : human 2 16 : in a 13 17 : is a 23 18 : languages 5 19 : meaning 3 20 : on the 15 21 : organized 6 22 : part 32 23 : some 10 24 : the similar 3 25 : better 3 5-23 26 : is used 6 27 : machine translation 3 28 : natural 4 29 : optimized 2 30 : processing 8 31 : result 16 32 : we describe 4 33 : access 3 34 : application 11 35 : develop 10 36 : information 12 37 : on computer 2 38 : or to 2 39 : such as 7 40 : technology 3 41 : user 6 42 : course 2 43 : making 2 44 : student's 2 45 : network 5 46 : paper 27 47 : the document 8 48 : an overview 5 49 : applications 8 50 : geometric 2 51 : technique 4 52 : model 11 53 : algorithms 4 54 : approaches 4 55 : association rules 2 56 : data 14 57 : large set of 2 58 : mining 7 59 : problem 13 60 : way 5 61 : based 17 62 : can be 18 63 : cases 2 64 : complex 2 65 : knowledge 7 66 : problems 3 Tiền kết hợp các tập tin vào các danh sách dãy từ phổ biến: STT Dãy từ phổ biến Mã văn bản ================================================ 1 : (approx p1 2 : - sentence p1 3 : annotated p1 4 : annotated p22 5 : automatic p1 6 : automatic p2 7 : automatic p5 8 : automatic p15 9 : automatic p17 5-24 10 : automatic P25 11 : automatic P28 12 : automatic p32 13 : automatic p39 14 : automatic p40 15 : automatic p44 16 : been solved p1 17 : bilingual corpus p1 18 : bilingual corpus p20 19 : bilingual corpus P25 20 : but in p1 609 : page segmentation p18 610 : page segmentation P27 611 : using recursive morphological p18 612 : association rules are p19 613 : attributes p19 614 : dynamic programming p19 615 : numeric p19 616 : optimized association rules p19 617 : optimized support p19 Tra cứu thư viện thông qua danh sách tiền kết hợp Chi tiết thuật giải kết hợp tập văn bản vào danh sách các dãy từ phổ biến: Input: − Tập các văn bản mới NP 5-25 − Tập các dãy từ phổ biến mới NS − Tập các dãy từ phổ biến được đánh dấu là đã được kết hợp với các văn bản hiện có S − Tập các văn bản được đánh dấu là đã kết hợp với các dãy từ phổ biến hiện có P − Tập kết hợp tập văn bản vào danh sách các dãy từ phổ biến SP{(px, sy), …}, px ∈ P, sy ∈ S − Tập các dãy từ phổ biến và số văn bản có chứa dãy từ phổ biến SR{(sx, n), …}, sx ∈ S, n ∈ N Output: − Tập kết hợp tập văn bản vào danh sách các dãy từ phổ biến SP{(px, sy), …}, px ∈ P, sy ∈ S − Tập các dãy từ phổ biến được đánh dấu là đã được kết hợp với các văn bản hiện có S − Tập các văn bản được đánh dấu là đã kết hợp với các dãy từ phổ biến P − Tập các dãy từ phổ biến và số văn bản có chứa dãy từ phổ biến SR{(sx, n), …}, sx ∈ S, n ∈ N Bước 1: tP = ∅ tS = ∅ pc = 0 Bước 2: Nếu NS.count >0 thì { For i=1 to NS.count do { pc = 0 For j=1 to P.count do { 5-26 tSubS = {tập các tiêu đề con của NS[i]} T = True For k=1 to tSubS.count do { Nếu trong văn bản P[j] không chứa tSubS[k] thì { T = false ; break; } } Nếu T=True thì { SP = SP + {(P[j], NS[i])} pc = pc + 1 } } tS = tS + {NS[i]} Nếu NS[i] chưa có trong SR thì SR = SR + {(NS[i], pc)} Ngược lại Trong SR, sửa (NS[i], n) thành (NS[i], pc), n giá trị ban đầu sẵn có } S = S + tS } Bước 3: Nếu NP.count >0 thì { tP = NP P = P + tP For i=1 to S.count do { pc = 0 5-27 For j=1 to NP.count do { tSubS = {tập các tiêu đề con của S[i]} T = True For k=1 to tSubS.count do { Nếu trong văn bản P[j] không chứa tSubS[k] thì { T = false ; break; } } Nếu T=True thì { SP = SP + {(NP[j], S[i])} } } Nếu S[i] chưa có trong SR thì SR = SR + {(S[i], pc)} Ngược lại Trong SR, sửa (S[i], n) thành (S[i], pc), n giá trị ban đầu sẵn có } } 5-28 Các bảng dữ liệu liên quan đến thao tác kết hợp tập văn bản vào danh sách các dãy từ phổ biến: Mô hình vật lý: PAPER (PAPERID, PAPERNAME, TITLE, ABSTRACT, KEYWORDS, PAPERFILENAME, PAPERFILEPATH) NEWPAPER (PAPERID, PAPERNAME, TITLE, ABSTRACT, KEYWORDS, PAPERFILENAME, PAPERFILEPATH) SUBJECTHEADINGS (SHID, SUBJECTHEADINGS) NEWSUBJECTHEADINGS (SHID, SUBJECTHEADINGS) SUBJECTHEADINGPAPER (SHID, PAPERID) SEARCHRESULT (SHID, SUBJECTHEADINGS, ITEMSCOUNT) 5-29 Mô tả các bảng dữ liệu: PAPER: chứa các văn bản hiện có đã được kết hợp vào danh sách các dãy từ phổ biến (chứa tập P trong giải thuật trên) Thuộc Tính Diễn giải PAPERID Mã số bài báo. Mỗi bài báo có một mã số duy nhất để phân biệt với các bài báo khác PAPERNAME Tựa đề của bài báo TITLE Chủ đề của bài báo ABTRACT Trích yếu của bài báo, tóm lược của bài báo KEYWORDS Các từ khóa chính trong bài báo. Các từ khóa này có sẵn hoặc sẽ được trích rút đặc trưng từ các trích yếu của bài báo PAPERFILENAME Tên tập tin toàn văn của bài báo PAPERFILEPATH Đường dẫn nơi chứa tập tin toàn văn của bài báo. NEWPAPER: chứa các văn bản mới, chưa được kết hợp vào danh sách các dãy từ phổ biến (chứa tập NP trong giải thuật trên). Thuộc Tính Diễn giải PAPERID Mã số bài báo. Mỗi bài báo có một mã số duy nhất để phân biệt với các bài báo khác PAPERNAME Tựa đề của bài báo TITLE Chủ đề của bài báo ABTRACT Trích yếu của bài báo, tóm lược của bài báo KEYWORDS Các từ khóa chính trong bài báo. Các từ khóa này có sẵn hoặc sẽ được trích rút đặc trưng từ các trích yếu của bài báo PAPERFILENAME Tên tập tin toàn văn của bài báo PAPERFILEPATH Đường dẫn nơi chứa tập tin toàn văn của bài 5-30 báo. SUBJECTHEADINGS: Tiêu đề đề mục. Chứa danh sách các dãy từ phổ biến hiện có đã được kết hợp vào danh sách các văn bản (chứa tập S trong giải thuật trên). Thuộc Tính Diễn giải SHID Mã số một tiêu đề đề mục. SUBJECTHEADINGS Dãy các từ phổ biến được ngăn cáhch bằng một ký tự ngăn cách “&&” NEWJECTHEADINGS: Tiêu đề đề mục. Chứa danh sách các dãy từ phổ biến mới, chưa được kết hợp vào danh sách các văn bản (chứa tập NS trong giải thuật trên). Thuộc Tính Diễn giải SHID Mã số một tiêu đề đề mục. SUBJECTHEADINGS Dãy các từ phổ biến được ngăn cáhch bằng một ký tự ngăn cách “&&” SUBJECTHEADINGPAPER: Tập kết hợp tập văn bản vào danh sách các dãy từ phổ biến (chứa tập SP trong giải thuật trên). Thuộc Tính Diễn giải SHID Mã số một tiêu đề đề mục. PAPERID Tương ứng với một mã số của tiêu đề đề mục sẽ có một hay nhiều mã số của bài báo đã được tìm thấy trong thư viện bài báo 5-31 SEARCHRESULT: Tập các dãy từ phổ biến và số văn bản có chứa dãy từ phổ biến (chứa tập SR trong giải thuật trên). Thuộc Tính Diễn giải SHID Mã số một tiêu đề đề mục. THEADINGS Tên của một tiêu đề đề mục cùng từ đồng hiện của tiêu đề đề mục đó, hay dãy từ phổ biến. ItemsCount Số các bài báo được tìm thấy theo tiêu đề đề mục có trong thư viện bài báo 5.5. SỬ DỤNG DÃY TỪ PHỔ BIẾN HỖ TRỢ BIÊN MỤC TỰ ĐỘNG Như đã trình bày trong chương 3 mỗi tiêu đề đề mục được xác định bằng một tập hợp các từ. Có thể biểu diễn cấu trúc của tiêu đề đề mục dưới dạng cấu trúc cây như trong hình sau Việt Nam DakLak Điểm truy cập 1 Đồng Nai Điểm truy cập 2 An Giang Điểm truy cập 3 Vật lý Hiện đại Điểm truy cập 4 Hạt nhân Điểm truy cập 5 Lượng tử Điểm truy cập 6 . . . . . Một điểm truy cập được xác định bằng nhãn chứa các cụm từ trên các cạnh nối từ gốc đến nút lá ứng với điểm truy cập đó. Ví dụ điểm truy cập 1 sẽ 5-32 ứng với nhãn Việt Nam – DakLak, Điểm truy cập 2 ứng với nhãn Việt Nam - Đồng nai. Sử dụng cây hậu tố mở rộng có thề xác định được một cách từ động các dãy từ phổ biến trong văn bản. Sau đó tra cứu trên cấu trúc cây hậu tố để gắn văn bản vào các điểm truy cập có nhãn là tập con của tập các dãy từ phổ biến được phát hiện từ việc phân tích văn bản. Với phương pháp này có thể hỗ trợ công tác biên mục tư liệu. Cũng cần lưu ý là một văn bản có thể được gắn vào nhiều điểm truy cập. Ví dụ văn bản có chứa dãy từ Vật Lý- Hiện đại- Hạt nhân sẽ được gắn vào hai điểm truy cập là điểm truy cập 4 và điểm truy cập 5. Do vậy có thể truy cập văn bản từ nhiều điểm truy cập khác nhau. 6-1 CHƯƠNG 6 GOM CỤM THÔNG VĂN BẢN BẰNG MẠNG KOHONEN 6.1 KIẾN TRÚC CỤM PHẲNG Cho tập đối tượng O, gom cụm phẳng là tiến trình gom các đối tượng thành các cụm ( tập con của O) sao cho các đối tượng trong cụm có mức độ tương tự cao và các đối tượng trong các cụm khác nhau có mức độ tương tự thấp. Kết qủa gom cụm phẳng sẽ tạo ra một phân hoạch tập đối tượng. Gọi C1,C2,...,Ck là một kiến trúc cụm phẳng, các cụm thỏa các tính chất sau: i) ∀i,j ∈[1,...,k] , Ci ∩ Cj = ∅ ii) Υk i iC 1= = O 6.1. MẠNG KOHONEN Mạng Kohonen là một mạng nơron làm việc theo lối tự tổ chức nhằm tạo ra một ánh xạ từ tập các mẫu học có số chiều lớn thành các cụm có số chiều thấp hơn [3],[4]. Mạng Kohonen hai chiều thường được sử dụng để gom cụm văn bản vì kết quả gom cụm được thể hiện trực quan trên một lưới hai chiều. Trong mạng Kohonen hai chiều, các nơron của lớp ra được sắp xếp trên một mảng hai chiều. Mảng này được gọi là lớp ra Kohonen. Tất cả các nơron của lớp vào đều được nối với các nơron trên lớp ra Kohonen. Hình 6.1 là cấu trúc của mạng Kohonen hai chiều. Hình 6.1: Cấu trúc của mạng Kohonen hai chiều 6-2 6.3. GOM CỤM TỪ LỚP RA KOHONEN Mỗi liên kết giữa đầu vào và đầu ra của mạng Kohonen tương ứng với một trọng số. Tổng đầu vào của mỗi nơron trong lớp Kohonen bằng tổng các trọng của các đầu vào nơron đó. Tiến trình huấn luyện sẽ điều chỉnh các trọng số dần dần theo mẩu học. Kết quả của tiến trình huấn luyện sẽ tạo trên lớp ra Kohonen các cụm dữ liệu ứng với nhóm các nút gần nhau trên lớp ra Kohonen. Các mẫu học sẽ thuộc về cụm có khoảng cách gần nhất từ nó đến nơron trong cụm. Theo tính chất của thuật giải huấn luyện trên mạng Kohonen, các cụm có vị trí gần nhau trên mạng Kohonen sẽ chứa các đối tượng có mức độ tương tự cao. Tính chất này được sử dụng để truy cập thông tin tương tự trong thư viện số nhờ lớp ra Kohonen được hiển thị trên màn hình. 6.4. THUẬT GIẢI HUẤN LUYỆN MẠNG KOHONEN Chức năng cơ bản của thuật giải huấn luyện mạng Kohonen là gom các vector trọng của các nơron trên lớp ra Kohonen thành các cụm rời nhau. Thuật giải huấn luyện mạng Kohonen Bước 1: Khởi tạo ngẫu nhiên các trọng số trên lớp ra Kohonen và gán Nc(t) là bán kính của vùng láng giềng. Khởi gán biến chu kỳ t=1 Bước 2: Đưa vào một mẫu học v(t) và chuẩn hóa vector nhập v(t) Tính khoảng cách Euclide từ vector nhập v(t) đến tất cả các vector trọng của tất cả các nơron trên lớp ra Kohonen và chọn nơron có khoảng cách Euclide dE nhỏ nhất từ vector học v(t) đến trọng ứng với nút đó. dE(v,wic jc) = min (dE(vi,wij)) Trong đó i,j là c