Bộ công cụ tìm kiếm thông tin trên mạng

ật toán HITS. Thuật toán HITS: Ý tưởng cơ bản của thuật toán HITS là xác định một đồ thị con của Web và áp dụng sự phân tích liên kết trên đồ thị con này để xác định các Authority và các Hub đối với truy vấn đã cho. Đồ thị con này phụ thuộc vào truy vấn của người sử dụng. Sự chọn lựa đồ thị con (cụ thể là vài nghìn trang ) không chỉ tập chung vào việc phân tích liên kết trên hầu hết các phần liên quan trong Web, mà đồng thời cũng giảm số lượng công việc cho pha tiếp theo (do việc chọn lựa đồ thị con và phân tích nó đều được thực hiện trong thời gian truy vấn nên nó rất quan trọng để hoàn thành chúng trong một thời gian ngắn). * Xác định đồ thị con tập trung : Đồ thị con tập chung được sinh ra từ tập gốc R. Một tập ngẫu nhiên các trang chứa đựng xâu truy vấn đã cho và mở rộng tập gốc tới các trang là hàng xóm của R. Bảng chỉ mục văn bản có thể được sử dụng để tìm kiếm tập gốc. Thuật toán tính toán đồ thị tập trung được như sau: 1. R<- tập t trang chứa đựng từ truy vấn (sử dụng bảng chỉ mục văn bản) 2. S<- R 3. for mỗi trang p Î R (a) Gộp tất cả các trang mà p trỏ tới vào trang S (b)gộp (cho tới giá trị lớn nhất d trang) tất cả các trang trỏ tới p vào trong S 4. Đồ thị đem lại từ S là đồ thị con tập chung Thuật toán có đầu vào là trang truy vấn và hai tham số t và d. Tham số t giới hạn kích thước tập gốc, tham số d giới hạn số lượng các trang được thêm vào đồ thị con tập chung. (các điều khiển này giới hạn sự ảnh hưởng của một trang vô cùng phổ biến như WWW.yahoo.com khi nó xuất hiện trong tập gốc). Một tập mở rộng S sẽ chứa nhiều Authority vì rằng một Authority được trỏ bởi ít nhất một vài trang trong tập gốc. Tương tự như vậy, cũng có nhiều Hub tốt nằm trong S. * Phân tích liên kết: Thuật toán HITS lợi dụng thuộc tính tăng cường lẫn nhau để xác định các Hub và các Authority từ tập mở rộng S (pha này không cần biết nội dung được truy vấn ). Tập các trang trong đồ thị con tập trung S được định nghĩa là 1,2,...n. B(i) là tập các trang trỏ tới trang i, F(i) là tập các trang mà trang i trỏ tới. Thuật toán phân tích liên kết đưa ra tỷ lệ Authority và hub hi và tỷ lệ Hub hi cho mỗi trang trong tập S. Để bắt đầu, các tỷ lệ của Authority và Hub được khởi tạo với các giá trị tùy ý. Thuật toán có tính chất lặp và nó thực hiện hai loại hoạt động trong mỗi bước lặp, gọi là I và O. trong hoạt động I, tỷ lệ Authority của mỗi trang cập nhật tổng các tỷ lệ Hub của các trang trỏ tới nó. Trong hoạt động O, tỷ lệ Hub của mỗi trang cập nhật tổng các tỷ lệ Authority của các trang nó trỏ tới. Có nghĩ là: Bước I: Bước O: Các bước I và O chỉ ra rằng một Authority tốt sẽ được trỏ tới nhiều Hub tốt và nhiều hub tốt sẽ trỏ tới nhiều Authority tốt. Cũng chú ý rằng một trang có thể là (và cũng thường là) một trang hub đồng thời là trang authority. Thuật toán Hub chỉ tính toán hai tỷ lệ cho mỗi trang, tỷ lệ Hub và tỷ lệ Authority. Thuật toán lặp đi lặp lại các bước I và O, với một sự chuẩn hóa, cho đến khi các tỷ lệ hub và authority hội tụ: 1. Khëi t¹o víi c¸c gi¸ trÞ tuú ý 2. LÆp cho tíi khi héi tô (a) ¸p dông ho¹t ®éng I (b) ¸p dông ho¹t ®éng O (c) chuÈn ho¸ vµ 3.KÕt thóc Một ví dụ của việc tính toán Hub và Authority được chỉ ra trong hình 13. Tỷ lệ Authority của nút 5 có thể thu được bằng việc thêm vào các tỷ lệ Hub của các nút trỏ tới nút 5( ví dụ 0.408 +0.816 + 0.408) và chuẩn hóa giá trị này bởi các tỷ lệ Hub kết hợp ( ví dụ (0.408)2 + (0.816)2 +(0.408)2). h= 0 a= 0.408 4 h= 0 a= 0.816 5 1 h= 0.408 a= 0 2 h= 0.816 a= 0 3 h= 0.408 a= 0 h= 0 a= 0.408 6 Hình 13: Thuật toán HITS Các giá trị Hub và Authority có những thuộc tính toán học thú vị giống như trong trường hợp của PageRank. Với Am x m là ma trận liền kề của đồ thị con tập chung. Phần tử thứ (ij) của A bằng 1 nếu trang i trỏ tới trang j và bằng 0 nếu ngược lại. Với A là các vector fias trị Authority [a1,a2,........an] và h là vector các giá trị [h1,h2,.........,hn ]. Các hoạt đọng I và O có thể biểu diễn a = Ah và h = AT a, sự biến đổi đơn giản đó chỉ ra rằng các tỷ lệ hội tụ cuối cùng của Hub và Authority thõa mãn a = c1A ATa và h = c2 AT Ah ( hằng số thêm vào giải thích cho bước chuẩn hóa ). Vì thế vector tỷ lệ authority và vector tỷ lệ Hub tương ứng là các eigenvector của các ma trận AAT và ATA. Thuật toán phân tích liên kết diễn tả ở trên là một bước lặp lũy thừa đơn giản nhân vector a và h là các eigenvector chính của AAT và ATA. Chỉ trong trường hợp của PageRank tỷ lệ hội tụ của các giá trị Hub và Authority mới phụ thuộc vào eigenvalue gap. Thứ tự của các trang Hub và Authority đưa ra bởi độ hội tụ của tỷ lệ hub và tỷ lệ Authority nhanh hơn việc tính chính xác các giá trị thực của chúng (khoảng 10 bước lặp). * Tìm kiếm các trang liên quan: Một vấn đề được đặt ra trong tìm kiếm từ khóa là khi một người đưa vào một số từ khóa, nhưng nó rất khó khăn cho họ khi chọn một số từ khóa diễn tả đúng nội dung đang quan tâm. Do đó các bộ công cụ đang tìm kiếm có thể hỗ trợ một kiểu truy vấn khác được gọi là tìm kiếm các trang liên quan, hoặc tìm kiếm bởi ví dụ. Trong kiểu truy vấn này, người tìm kiếm đưa vào một ví dụ mà cụ thể là một trang Web diễn tả phần nào đó thông tin mà anh ta đang tìm kiếm. Công cụ tìm kiếm sẽ thu hồi các trang Web tương đương với trang Web đã cho. Một truy vấn tìm kiếm liên quan có thể được đáp ứng với các kỹ thuật IR dựa trên độ tương quan văn bản. Tuy nhiên trên môi trường Web chúng ta có thể khai thác cấu trúc liên kết của chúng. Nếu một trang A trỏ đến hai trang B và C thì nó cho biết rằng B và C có liên quan. Lưu ý rằng thuật toán HITS hoàn toàn sử dụng thông tin Cocitation. Kleinberg đã gợi ý rằng một sự biến đổi đơn giản của thuật toán HITS có thể được sử dụng để hỗ trợ các truy vấn tìm kiếm liên quan. Dean và Henzing đưa ra hai thuật toán tìm kiếm liên quan, được đặt tên là thuật toán Companion là sự mở rộng ý tưởng của Kleinberg, và thuật toán Cocitation sử dụng việc đếm cocitation để xác minh các trang liên quan. Họ nhận thấy rằng cả hai thuật toán này thực hiện tốt hơn dịch vụ Nescape và thuật toán Conpanion là tốt nhất. * Phân lớp và biên soạn nguồn tài nguyên: Rất nhiều các công cụ tìm kiếm giống như Altavista và Yahoo có sự phân lớp kiến trúc của các trang Web. Người sử dụng có thể duyệt kiến trúc đó để xác định thông tin họ quan tâm. Các kiến trúc này được dịch bằng tay, các vấn đề về phân lớp tài liệu tự động dựa trên một vài ví dụ phân lớp đã được nghiên cứu IR. Chakrabarti, Dom và Indyk đã mở rộng các kỹ thuật IR để đưa thông tin ra siêu văn bản. Ý tưởng cơ bản là không chỉ sử dụng các từ trong tài liệu mà còn cả các phạm trù của các trang lân cận để phân loại. Họ đã chỉ ra một cách thực nghiệm rằng kỹ thuật của họ nâng cao độ chính xác của sự phân lớp. Một bài toán liên quan đã được nghiên cứu đó là quá trình biên dịch tài nguyên một cách tự động. Sự quan trọng trong trường hợp này đó là xác định các trang có chất lượng cao cho một phạm trù hay một chủ đề cụ thể nào đó. Thuật toán được gợi ý đó là sự biến đổi của thuật toán HITS sử dụng thông tin từ nội dung cộng với các mối liên kết. Tóm lại Cấu trúc liên kết của các trang Web chứa đựng rất nhiều thông tin hữu ích có thể được khai thác để hỗ trợ việc tìm kiếm theo từ khóa hay các công việc thu hồi thông tin khác trên Web. Chúng ta đã tham khảo hai kỹ thuật phân tích liên kết thú vị trong mục này. PageRank là một mô hình sắp xếp toàn cục được sử dụng để sắp xếp các kết quả tìm kiếm. Còn thuật toán HITS thì xác định một tập các trang Hub và các trang Authority đối với một truy vấn đã cho. Có rất nhiều hướng thú vị được đưa ra. Một trong những chiều hướng có triển vọng đó là nghiên cứu các nguồn thông tin khác như thế nào, ví dụ như các truy vấn bản ghi. Những chiều hướng nghiên cứu quan trọng khác đó là nghiên cứu các kỹ thuật phân tích văn bản xã hội và nâng cao nó cho tập dữ liệu siêu văn bản. Vậy, Để tìm kiếm thành công trên WWW là một trong những công việc cơ bản trong môi trường công nghệ thông tin ngày nay. Vì thế các bộ công cụ tìm kiếm ngày càng nâng cao khả năng trích dẫn các nguồn thông tin liên quan từ một số lượng tài liệu rất lớn. Và các bộ công cụ thực hiện điều này với một lượng dữ liệu đầu vào rất nhỏ thường chỉ là một hoặc hai từ khóa truy vấn. Trong hình 3 chúng ta đã được tham khảo các công cụ được đặt cùng nhau như thế nào. Các khối chức năng chính hình thành nên một kiến trúc cụ thể: Crawler lướt trên mạng để thu hồi các trang. Các trang này được lưu trữ một cách cục bộ, ít nhất cho đến khi chúng lập chỉ mục và phân tích. Công cụ truy vấn thu hồi các giá trị URL mà nhường như là liên quan tới truy vấn của người sử dụng. Một môđun Ranking cố gắng sắp xếp các giá trị URL sao cho những kết quả triển vọng nhất được đặt ở đầu. Nhóm các kỹ thuật này vẫn đòi hỏi một sự cố gắng trong thiết kế. Phần lớn sự phức tạp trong thiết kế và thực hiện bắt nguồn từ phạm vi rộng của Web. CHƯƠNG III THIẾT KẾ CÁC CÔNG CỤ HỖ TRỢ TÌM KIẾM THÔNG TIN TRÊN MẠNG Môđul lập chỉ mục là bước tiền xử lí trong bộ công cụ tìm kiếm thông tin, nó có thể lập chỉ mục cho hai dạng nguồn dữ liệu. thứ nhất, đó là file-system với đầu vào cho môđul là các file hoặc các thư mục chứa các file với đuôi mở rộng là: .html, .xml, .txt. Thứ hai, đó là một cơ sở dữ liệu WebBase với đầu vào cho môđul là một giá trị địa chỉ URL. Sau khi lập chỉ mục ta thu được một cơ sở dữ liệu bao gồm các bảng chỉ mục (Inverted File) chứa đựng từ đó và nhiều thông tin khác hỗ trợ cho quá trình tìm kiếm. Môđul tìm kiếm phân tích cú pháp truy vấn của người sử dụng và thực hiện tìm kiếm trên các bảng chỉ mục (là đầu ra của môđul trên) để đưa ra các tài liệu có liên quan tới truy vấn. Trong chương trình này em có đưa ra các giải pháp cũng như cấu trúc giữ liệu để giải quyết các dạng truy vấn: truy vấn một cụm từ, truy vấn Boolean, truy vấn meta, truy vấn với kí tự đại diện ( Wildcat ).Do truy vấn thường là rất ngắn nên số lượng tài liệu liên quan là rất lớn, do đó phải có một môđul thực hiện việc sắp xếp kết quả, sao cho tập kết quả đầu ra có độ liên quan giảm dần đối với truy vấn. Môđul sắp xếp này sử dụng các giá trị thống kê của các từ nằm trong bảng chỉ mục để tính toán độ liên quan của tài liệu. Trong chương này em cũng đưa ra các giải pháp và sự chọn lựa thuật toán cũng như cấu trúc dữ liệu để có được thời gian lập chỉ mục và tìm kiếm nhanh nhất, tài liệu đưa ra có mức độ liên quan tới truy vấn cao nhất đồng thời đáp ứng đựơc nhiều dạng của truy vấn. 3.1 MÔ ĐUN LẬP CHỈ MỤC 3.1.1 Khái niệm chỉ mục Đầu tiên, chúng ta tập trung tìm kiếm các truy vấn và thông báo các tài liệu chứa các từ trong truy vấn, số lần xuất hiện truy vấn trong mỗi tài liệu và thậm chí các vị trí chính xác trong mỗi văn bản. Cách tìm kiếm một truy vấn đơn giản nhất là quét liên tiếp văn bản. Việc tìm kiếm liên tiếp hoặc online là tìm sự xuất hiện của một mẫu trong văn bản khi văn bản không được tiền xử lý. Tìm kiếm online chỉ phù hợp với các văn bản nhỏ. Cách lựa chọn tìm kiếm thứ hai là xây dựng các cấu trúc dữ liệu cho văn bản ( gọi là bảng chỉ mục - index ) để tăng tốc độ tìm kiếm, phù hợp với việc xây dựng và duy trì các chỉ số khi tập văn bản là lớn và nửa tĩnh (semi- static).Trong phần này, em sẽ đưa ra hai kỹ thuật đánh chỉ số chính: Inverted File và Signature Files - đó là các kỹ thuật tìm kiếm dựa vào từ khác trong đó nhấn mạnh kỹ thuật Inverted Files - là sự lựa chọn hợp lý và có nhiều ứng dụng nhất hiện nay. 3.1.2. Các cấu trúc lưu chỉ mục 1/ Signature files Signature files sử dụng phương pháp mã hóa chồng nhau để tạo ra nhãn (signature) cho nhập tài liệu sẽ được chia thành khối logic, mỗi khối chứa đựng D từ phân biệt (đây là các từ không nằm trong StopList ). Mỗi từ cho ta một nhãn từ - kích thước F bít với m bít được thiết lập là 1 còn những bít còn lại là 0. Các nhãn từ được “OR” cùng nhau hình thành nền nhãn khối. Các nhãn khối nối với nhau tạo ra nhãn tài liệu. Vị trí của m bít được thiết lập là “1’’ được quyết định bởi các hàm băm. Ta có một ví dụ tạo nhãn: Từ Nhãn ------------------------------------------------------------ Free 001 000 110 010 Text 000 010 101 001 ------------------------------------------------------------ Free text 001 010 111 011 Hình 14: Một ví dụ tạo nhãn với mỗi khối logic có D= 2 từ, kích thước nhãn F = 12 bit, m= 4 bit Giả sử nhãn của một khối là B. để kiểm tra một từ có nằm trong tài liệu không, ta tiến hành xác định nhãn của từ đó, giả sử là W, sau đó thực hiện phép toán logic (W & B)đối với các khối trong tài liệu, nếu(W&B = W) thì từ có thể nằm trong khối đó. Một khái niệm quan trọng trong Signature Files là xác xuất “false drop’’ Fd , đó là xác suất mà phương pháp Signature cho ta những báo động có lỗi có nghĩa là từ không nằm trong văn bản. do đó xác suất False drop Fd là xác suất mà một khối được phương pháp Signature báo là chứa đựng từ tìm kiếm chia cho khối đó hiện thực không chứa tìm tìm kiếm. Signture Files là một ma trận nhị phân F x N, theo Stiassny, theo 1960 thì để xác suất False drop là nhỏ nhất thì mỗi hàng trong ma trận này sẽ chứa đụng khoảng 50% bít 1, và khi đó Fd = 2-m Trong hầu hết các trường hợp ma trận Signature được lưu một cách tuần tự theo các hàng, và được gọi là cấu trúc SSF (Sequential Sinature File) File v¨n b¶n Con trá File 0 1 ….. 0 1 1 …………….. 1 Nh·n F bit N Khèi Logic Hình 15: Cấu trúc file dang SSF Ta nhận thấy rằng thời gian xử lí đối với phương pháp này là tuyến tính với số lượng khoản tin N nằm trong cơ sở dữ liệu do đó nó sẽ trở nên chậm chạp đối với cơ sở dữ liệu lớn. vì thế phương pháp Signature chỉ sử dụng tốt trong một số môi trường như: - Trên PC nhưng với kích thước dữ liệu trung bình - Trên WORM (Write-Read-Only) - Các máy song song Sau đây em xin đưa ra một phương pháp khác để tổ chức bảng chỉ mục, đó là phương pháp Inverted File. 2/ Tập tin đảo (Inverted Files) Signature file cho phép thu hẹp không gian tìm kiếm nhưng để khẳng định chính xác văn bản nào có chứa truy vấn thì ta vẫn phải thực hiện giải thuật tìm kiếm trực tiếp. Nếu đặt hệ tìm kiếm vào tình huống phải xử lý trên khối lượng dữ liệu lớn, đồng thời nằm trong một hệ khôi phục thông tin thì thời gian truy tìm trên cấu trúc dữ liệu Signature file sẽ quá lớn, không phù hợp với hoàn cảnh thực tế. Inverted File là giải pháp trọn vẹn hơn, những kết quả của Moffat cho thấy: trong hầu hết các ứng dụng, Inverted file đạt hiệu quả hơn Signature file cả kích thức kho chỉ mục lẫn tốc độ tìm kiếm. Cấu trúc Inverted files (Inverted index ) là một cơ chế đánh chỉ số cho một tập văn bản theo thứ tự để tăng tốc độ tìm kiếm. Cấu trúc Inverted files (IF) gồm 2 thành phần :Từ vựng và tham số kèm theo : - Từ vựng là tập hợp toàn bộ các từ khác nhau trong văn bản. Mỗi từ lưu trữ một danh sách tất cả các vị trí văn bản mà từ đó xuất hiện cùng nhưng thông tin khác. - Tập hợp tất cả các danh sách đó gọi là sự xuất hiện (occurrences). Cấu trúc của Inverted files (IF) khá đơn giản, gồm các inverled list (IL) đặt liên tiếp nhau. Trong một IF mỗi phần tử của một danh sách chỉ tới một tài liệu hoặc một tên file. Không gian cần thiết cho bảng từ vựng là khá nhỏ. Theo luật Heap, từ vựng tăng với tộc độ O(nβ ), với β là một hằng số nhận giá trị giữa 0 và 1 phụ thuộc vào văn bản, trong thực tế từ 0.4 đến 0.6. Chẳng hạn, cho 1 Gb tập hợp dữ liệu TREC-2 thì bẳng từ vựng có kích thước chỉ 5Mb. Việc giảm kích thước này có thể thực hiện được bằng cách lược từ (stemming) hoặc một số kỹ thuật chuẩn hoá khác. Các vị trí xuất hiện yêu cầu không gian lớn hơn. Vì mỗi từ xuất hiện trong văn bản đòi hỏi một cấu trúc như vậy, không gian cần bổ sung là O(n). Ngay cả khi bỏ qua các từ kết thúc (trong thực tế là ngầm định khi đánh chỉ số các từ), trong thực tế toàn bộ không gian của các vị trí xuất hiện của các từ này chiếm khoảng 30% đến 40%kích thước văn bản. để giảm không gian yêu cầu, người ta đưa ra kỹ thuật đánh địa chỉ khối (block addressing): chia văn bản thành các block và các occurrence chỉ đến các block- nơi mà từ xuất hiện ( gồm các vị trí chính xác ). Các lớp index chỉ đến các vị trí xuất hiện chính xác gọi là “full invenrted index’’. Kỹ thuật này không chỉ giảm khối lượng con trỏ ( số các block ít hơn các vị trí ) mà tất cả occurrence của một từ trong một block riêng lẻ được giảm tương ứng đến 1. Với kỹ thuật này, indices chỉ chiếm 5% toàn bộ kích thước văn bản. Các block có thể được cố định về kích thước hoặc có thể xác định bằng cách chia văn bản thành files,các tài liệu, các trang Web… việc chia văn bản thành các block làm tăng hiệu quả về thời gian và chất lượng tìm kiếm.Trong phần thiết kế chương trình do được thực hiện trên nguồn dữ liệu là các file HTML, XML, TXT nên em đã chia tập tài liệu thành các block lớn là các File ( hoặc trang Web ), và trong mỗi block lớn được chia thành các Block nhỏ hơn dựa theo cấu trúc của đoạn văn bản nằm trong File (ví dụ Meta, Comment, Header, Title,…) 3/ Cấu trúc dữ liệu trong Inverted File Có ba câú trúc dữ liệu có thể được tổ chức một cách hiệu quả cho Inverted File: bảng băm, mảng sắp xếp, và cây B-tree. Một trong cấu trúc dữ liệu được sử dụng phổ biến trong hầu hết các bộ công cụ tìm kiếm trên bảng băm rất dễ dàng với độ phức tạp chỉ là hằng số. Sau đây em xin trình bày một cách tổng quan về cấu trúc dữ liệu này. Cấu trúc bảng băm Hàm băm h(x) ánh xạ khoá x sang một số nguyên trong pham vi đã cho (ví dụ từ 0 tới m-1). Và trong ứng dụng hàm băm được dùng để ánh xạ một từ khoá tới một vị trí trong bảng băm. Tuy nhiên hàm băm có thể cho ta cùng một vị trí trong bảng băm cho hai khoá khác nhau, khi đó ta có một xung đột. trong chương trình giới thiệu bộ công cụ em đã trình bày cách giải quyết xung đột này. Với hai phương pháp giải quyết xung đột ta thấy phương pháp Open Addressing chỉ có thể làm việc với một số lượng khoá nhất định và hiển nhiên rằng số lượng khoá không thể lớn hơn số phần tử của bảng băm. Trong khi đó bộ đệm gói có số lượng từ lưu trữ là không biết trước, ngoài ra cấu trúc từ điển cho phép người sử dụng thêm các từ mới nên phương pháp này không phù hợp. Phương pháp Chaining khắc phục được những điểm trên. Cấu trúc bảng băm có thể cho ta độ phức tạp trong việc xoá, chèn và tìm kiếm một khoá là tối ưu, tuy nhiên cấu trúc này không thể giải quyết cá truy vấn với kí tự đại diện ( ví dụ như Search Libra *) với truy vấn dạng này ta phải có một cấu trúc dữ liệu cho phép tìm kiếm theo phạm vi, cấu trúc đơn giản nhất có thể là một mảng sắp xếp. Mảng sắp xếp . . . Doc.# Link TËp tµi liÖu Doc.#1 1 2 Comput Tõ kho¸ Thuéc tÝnh File chØ môc Doc.#2 Posting File Với cấu trúc này Inverted File sẽ lưu một danh sách từ khoá trong mảng sắp xếp cùng với thông tin vị trí mà từ khoá nằm trong. Giải thuật tìm kiếm trên cơ sở dữ liệu này là phương pháp tìm kiếm nhị phân truyền thống. Hình 16: Inverted File sử dụng mảng sắp xếp Ta nhận thấy rằng mô hình cấu trúc này dễ hiểu, và nó sẽ thực hiện tốt trên bộ nhớ thứ cấp, tuy nhiên bất lợi chính của cấu trúc này đó là khả năng cập nhập bảng chỉ mục (ví dụ như ta thêm một từ khóa mới ) hơn nữa với độ phức tạp tìm kiếm log (N) trong đó N là số lượng từ khóa chỉ mục thì chưa phải là tối ưu. Sau đây em xin đưa ra một cấu trúc vẫn đáp ứng được khả năng tìm kiếm theo phạm vi mà thời gian tìm kiếm của nó nhỏ hơn nhiều so với cấu trúc mảng sắp xếp. Cấu trúc cây B-Tree Với cấu trúc của cây B- Tree đã được trình bày trong chương trình giới thiệu ta có thể nhận thấy rằng đây là một cấu trúc tốt đủ để đáp ứng mọi dạng truy vấn, các thuộc tính mong muốn dễ nhận thấy ở cây B-Tree đó là: - Khả năng tìm kiếm nhanh - Có khả năng tìm kiếm với các từ khóa kí tự đại diện ( ví dụ : comput* ) - Khả năng lập chỉ mục nhanh - Thực hiện chèn xóa rất dễ dàng - Thuật toán đơn giản Với những đánh giá trên em xin lựa chọn cài đặt cấu trúc dữ liệu từ điển trong chương trình: Sử dụng mảng băm để lưu từ điển nằm trong bộ đệm, còn từ điển nằm trong bộ nhớ thứ cấp được lưu dưới hai dạng: bảng băm và cây B - Tree 3.1.3 Các bước xây dựng chỉ mục theo phương pháp Inverted files Quá trình lập chỉ mục đòi hỏi một số lượng các thao tác vào ra đĩa cứng trên nguyên tắc thời gian thực hiện những thao tác này sẽ chiếm tỷ lệ quan trọng trong tổng thể thời gian thực hiện chung. Trên cơ sở hạn chế tối đa chi phí truy cập bộ nhớ ngoài, việc thiết kế cấu trúc Inverted File nhằm tới hai mục tiêu: thứ nhất là giảm thiểu các thao tác truy xuất, thứ hai cố gắng sắp xếp dữ liệu sao cho việc truy xuất được thực hiện tuần tự hơn là truy cập ngẫu nhiên. C¸c Inverted File nhá Tµi liÖu nguån Bé hîp nhÊt Inverted File lín Bé ph©n tÝch Với sự mô tả các bước thực hiện ở trên ta có thể thấy được phần nào thứ tự thực hiện quá trình lập chỉ mục. Tuy nhiên để có cái nhìn trực quan hơn về các bước tiến hành, em xin trình bày khái quát mô hình lập chỉ mục theo sơ đồ sau : Hình 17 Khái quát mô hình lập chỉ mục 1/ Bộ phân tích Quá trình phân tích bắt đầu bằng việc phân tích từng văn bản để nhận dạng các từ sau đó chuẩn hóa chúng và lưu vào bộ đệm trong bộ nhớ chính, sau khi toàn bộ tài liệu đã được lập chỉ mục và lưu vào trong bộ đệm ta đi bộ trên bộ đệm đó để loại bỏ các từ không cần thiết - đó là những từ xảy ra quá thường xuyên trong tập tài liệu. Quá trình này có thể được mô hình hóa như sau: Hình 18: Mô hình bộ phân tích NhËn d¹ng tõ ChuÈn ho¸ tõ V¨n B¶n L­u bé ®Öm Lo¹i tõ kh«ng cÇn thiÕt Nhận dạng từ Trước hết, chúng ta xem xét một ví dụ về văn bản gốc sau: CHAPTER 1 Preamble 1.1 humannity stands at a defining moment history. We are confronted with a perpetuation of disparities between and within nations, a worsening of poverty, hunger, ill health and illiteracy, and the continuing deterioration of the ecosystem on chapter 1 preamble 1 1 humanity stands at a defining moment history we are confronted with a perpetuation of disparities between and within nations a worsening of poverty hunger ill health and illiteracy and the continuing deterioration of the ecosystem on which we depend for out well being Bước đầu tiên trong quá trình xử lý một tài liệu hoặc truy vấn là xác định các từ tố. Một trong những phương pháp đơn giản nhất là xác định các ký hiệu trong một từ và ký hiệu nối giữa các từ (inter word). Trong ví dụ ở hình 10 tất cả các ký hiệu không phải ký tự hoặc chữ số đều là các ký hiệu inter - word. Các kí hiệu inter - word được loại bỏ trong giai đoạn này và các dãy ký hiệu còn lai là các từ tố xử lý. Kết quả là loại bỏ tất cả các dấu chấm, các dấu nối và dấu chấm hỏi . Văn bản sau khi đã thực hiện xử lý từ tố ( tokenisation ) Ta có thể áp dụng một số luật Heuristic sau để nhận dạng một từ không được lập chỉ mục: Có số kí tự nhỏ hơn 4 Có ít hơn một nguyên âm - Có nhiều hơn hai kí tự giống nhau liên tiếp - Có nhiều hơn 5 phụ âm liên tiếp - Có nhiều hơn 4 nguyên âm liên tiếp - Có nhiều hơn một dấu kết thúc liên tiếp - Từ nằm trong danh sách StopList Sau khi một từ được nhận dạng là có khả năng lập chỉ mục, nó sẽ được chuẩn hóa, quá trình đó thực hiện như sau: Chuẩn hóa hình thái từ Chuẩn hóa về hình thái của các từ trong tài liệu và các truy vấn được sử dụng để tìm các tài liệu chứa các dạng hình thái khác nhau của truy vấn ban đầu. Vấn đề này có thể được thực hiện hoặc bằng cách sử dụng bộ lược từ (stemmer) hoặc từ điển tìm kiếm. một bộ lược từ đã phát triển từ những năm 60 khi các hệ thống tìm kiếm đầu tiên được thực hiện. Các bộ lược từ nổi tiếng như của Lovins (1968) và Porter (1980) , sau đó nó đã trở thành giải thuật được chấp nhận rất phổ biến. Tuy nhiên, hiệu quả của phương pháp tìm kiếm này có những hạn chế nhất định. Đôi khi các giải thuật lược bỏ từ có thể đúc kết từ có nghĩa hoàn toàn khác nhau thành một gốc từ, chẳng hạn các từ “skies’’ (trời, khí hậu ) và “ski ”đều lược thành“ski”. Trong các trường hợp như vậy người dùng có thể không hiểu tại sao một tài liệu cụ thể được tìm kiếm và có thể bắt đầu với một câu hỏi chung chung cho toàn bộ hệ thống. Mặc dù vậy các bộ lược từ vẫn thường được sử dụng trong nhiều hệ thống nghiên cứu như Smart, Okapi và Twenty- One. Chapter I preamb 1 1 human stand defin moment histori confront perpetu dispar nation worsen poverti hunger ill health ang illiteraci continu deterior ecosystem dependwell be Văn bản sau khi lược bỏ từ Từ điển tìm kiếm sẽ cho kết quả các từ gốc chính xác về ngôn ngữ, thường được gọi là lemmas. Tuy nhiên, có một số từ điển hình thái đầy đủ chưa chắc đã đủ để xây dựng một lemmatiser. Một số từ sẽ có nhiều mục từ, có thể với các lemma khác nhau. Chẳng hạn, từ “saw” có thể là thì quá khứ của một động từ, lemma của nó là“see”và có thể một danh từ, trong trường hợp này lemma tương đương với hình thái đầy đủ.Ví dụ khác là từ“number ” có thể được so sánh với “numb” (dạng tính từ có nghĩa là “tê cứng” hoặc dạng động từ là “ làm tê cứng ”). Trong các trường hợp này, một lemmatiser phải xác định từ loại của từ trước khi chọn lemma chính xác. Các giải thuật huấn luyện thống kê dựa trên tài liệu có thể được sử dụng một cách hiệu quả để tìm các từ loại chính xác và do vật đưa ra các lemma chính xác. Một từ trong văn bản sau khi đã được nhận dạng và chuẩn hóa sẽ được lưu vào trong bộ đệm chỉ mục nằm trong bộ nhớ. 2/ Lưu từ vào trong bộ đệm Như đã trình bày ở trên, cấu trúc tối ưu nhất cho bộ đệm đó là bảng băm và được tổ chức như sau: Hình 19: Câú trúc bộ đệm chỉ mục 1 5 10 Tõ Position B¶ng B¨m Filenum LOCATION = MetaID Một từ trước khi muốn lưu vào bộ đệm phải được tính giá trị băm để tìm vị trí của từ trên bảng băm, nếu không tìm thấy từ trong bảng băm ta tạo ra một phần tử mới (Entry) chứa từ và những thông tin liên quan tới từ đó. Nếu tìm thấy từ trong bảng băm, ta đi tới danh sách LOCATION của từ và so sánh từng cặp (filenum, metaID ) trong danh sách với cặp(filenum, metaID) của từ cần chèn. Nếu không có một cặp nào phù hợp ta tạo ra một nút LOCATION mới với vị trí của từ là 1(Position [1] = 1) và nối vào danh sách, còn nếu tìm thấy thì ta thêm vị trí của từ vào mảng Position. 3/ Loại bỏ stopword Các stopword là các từ xuất hiện nhiều lần trong các văn bản nhưng mang rất ít ý nghĩa, do vậy nó sẽ được loại bỏ trong quá trình chỉ số hóa văn bản và truy vấn. Bằng cách loại bỏ các stopword không làm ảnh hưởng đến ngữ nghĩa của các văn bản, đồng thời làm giảm số lượng các từ trong văn bản khoảng từ 30-50% (Schauble 1997) Các từ mang ý nghĩa theo quan điểm của các nhà ngôn ngữ học sẽ có thể bị loại bỏ dù sự xuất hiện của chúng trong tập hợp các văn bản là cao hay thấp. Loại bỏ các stopword có thể được thực hiện bằng cách sử dụng danh sách liệt kê tất cả các từ mang ý nghĩa như “the”, “it”, “a”…các từ này có tần suất rất cao trong tiếng Anh nhưng chúng được đưa ra theo quan điểm của các nhà ngôn ngữ học. Các stop list được sử dụng trong nhiều hệ thống nhưng số lượng các từ trong danh sách là khác nhau. Chẳng hạn, hệ thống Smart gồm 571 từ ( Smart 1994 ), hệ thống Okapi khoảng 220 từ. chapter 1 preamble 1 1 humanity stands defining moment history confronted perpetuation disparities nations worsening poverty hunger ill health illiteracy continuing deterioration ecosystem depend well being Quá trình loại bỏ StopWord có thể được chia thành hai loại: + Từ cần loại bỏ nằm trong StopList, quá trình này sẽ được thực hiện trong phần nhận dạng từ, có nghĩa là từ này sẽ không thể đi qua bộ nhận dạng từ và vì thế chúng không được lập chỉ mục. + Từ cần loại bỏ không nằm trong StopList nhưng nó xảy ra quá thường xuyên trong tập tài liệu của ta ( từ quá thường xuyên ở đây có nghĩa là nó xuất hiện vượt quá một ngưỡng cửa qui định của ta, ví dụ như có mặt trên 80% số lượng File, hoặc trên 200 File ), quá trình này được thực hiện sau khi ta lập chỉ mục song toàn bộ tài liệu và bảng chỉ mục đang được lưu trong bộ đệm. Khi đó ta thực hiện việc đi bộ trên bảng băm để tìm các từ các từ StopWord, thêm chúng vào danh sách StopList và loại phần tử chứa từ đó khỏi bảng băm. Bộ đệm sau khi loại bỏ những từ không cần thiết sẽ được lưu vào trong file chỉ mục ( Iverted file nhỏ ) nằm trong bộ nhớ thứ cấp. Tuy nhiên để tạo điều kiện thuận lợi cho việc lưu chỉ mục dưới dạng cây B-Tree, ta sử dụng một mảng trỏ tới các phần tử nằm trong bảng băm và thực hiện sắp xếp chúng theo thứ tự Anpha của các từ khóa. Cấu trúc chỉ mục trong bộ nhớ thứ cấp được lưu dưới hai dạng, dạnh bảng băm và cây B-Tree. Cài đặt cây B-Tree trong chương trình Với những đặc điểm rất phù hợp với một cấu trúc từ điển của cây B+- Tree, nên em xin chọn lựa cấu trúc này để cài đặt Inverted File. Một cây B-Tree lưu trữ gồm hai phần : Phần thứ nhất lưu các trang của cây B - Tree ( mỗi trang tương ứng với một nút lớn của cây B-Tree ), các trang được lưu liền nhau theo theo thự tự số trang trên đĩa cứng. Phần thứ hai lưu trữ các bản ghi dữ liệu của một từ xuất hiện trên cây và liên quan tới văn bản tìm kiếm. Next Prev PageNum …… KeyWord Data_pointer ………… Header Data Entry1 EntryN Mỗi trang B-Tree có cấu trúc như sau : Next: số trang ngay liền sau trang hiện thời ( tính trên vị trí của cây ) được sử dụng trong tìm kiếm phạm vi. Prev : cha của trang hiện thời ( tính trên vị trí của cây ) được sử dụng khi một nút bị đầy, ta phải tách nút đó ra thành hai và khóa đầu tiên trong nút thứ hai sẽ được chèn lên nút cha. PageNum: số trang hiện thời KeyWord: nội dung từ khóa Data_ pointer : chứa số trang mà từ khóa này trỏ tới nếu đây không phải là nút lá, còn nếu là nút lá thì nó chứa số thứ tự bản ghi dữ liệu của từ khóa này trong file lưu trữ dữ liệu từ ( phần thứ hai ). File lưu trữ dữ liệu từ bao gồm các thông tin về từ như: metaID, filenum, frequency, posdata (chứa các vị trí của từ xuất hiện trong văn bản ) 4. Bộ hợp nhất Các Inverted File nhỏ nằm trong bộ nhớ thứ cấp có thể được hợp nhất lại thành Inverted File lớn hơn. Ví dụ: Merge index1 .input index2.input……indexN.input index.output. Các bước xử lí của bộ hợp nhất là: + Kiểm tra sự phù hợp các Header của các Inverted File đầu vào và lưu chúng vào trong Header của Inverted File đầu ra. Tạo ra một mảng các phần tử meta mới trong Inverted File đầu ra và thiết lập mảng ánh xạ từ MetaID cũ tới MetaID mới. + Đọc thuộc tính cá File nằm trong các bảng chỉ mục đầu vào, thiết lập lại chỉ số file và lưu chúng vào trong bảng chỉ mục dầu ra đồng thời tạo ra mảng ánh xạ từ chỉ số File cũ tới chỉ số File mới. |+ Duyệt từng bảng chỉ mục đầu vào đọc dữ liệu từ và kết hợp với mảng ánh xạ MetaID và mảng ánh xạ chỉ số File để lưu dữ liệu từ vào bảng chỉ mục đầu ra. 3.1.4 Lập chỉ mục với các nguồn dữ liệu đầu vào Trong phần trên em đã trình bày cách thức để lập chỉ mục một File (hoặc là nội dung một trang Web), nhưng với nguồn dữ liệu đầu vào là một thư mục hay một địa chỉ URL thì ta sẽ thực hiện như thế nào? Sau đây em xin trình bày chi tiết về vấn đề này. Các bước lập chỉ mục cho một thư mục: Lập chỉ mục cho một thư mục được thực hiện một cách đệ qui và bao gồm những bước như sau: + Lưu tất cả các thư mục con của thư mục hiện thời vào danh sách thư mục (SortDirList) + Tất cả các file nằm trong thư mục hiện thời vào danh sách file (SortFileList) + Lập chỉ mục tất cả các file nằm trong SortFileList + Gọi hàm lập chỉ mục thư mục cho các thư mục nằm trong SortDirList Các bước lập chỉ mục cho một địa chỉ URL: Trong chương trình em đã sử dụng 3 môđul trong Perl : ( LWP::UserAgent, HTTP::status, HTML::LinkExtor ) để xây dựng một môđul có nhiệm vụ thu hồi nội dung của trang Web ứng với giá trị URL đó và trích các giá trị URL nằm trong trang Web đó. 3.2 Môđul tìm kiếm 3.2.1 Các dạng truy vấn *Truy vấn theo từ Chúng ta có thể sử dụng các hoạt động “and”, “or”, “not” trong truy vấn, nếu không có phép toán logic thì sẽ được mặc định là”and " các từ liền nhau. Sự đánh giá được tính từ trái qua phải, tuy nhiên chúng có thể sử dụng dấu “ ( ) ”để thay đổi mức ưu tiên. Ví dụ 1 : Search “ computer Not mouse AND keyboart ” Thu hồi các file chứa đựng từ Computer và Keyboart nhưng không chứa đựng Mouse. Ví dụ 2: Search “ Computer NOT (Mouse and Keyboard ) ” Thu hồi các file chứa đựng từ Computer nhưng không chứa đựng Mouse và Keyboard *Truy vấn với kí tự đại diện Ví dụ: Search “ Librarian* ” Thu hồi các File chứa đựng: Librarian, Librarians, Librarianship,…Tuy nhiên tìm kiếm theo phưong pháp này khi kết hộ với Stemming có thể cho ta những kết quả không mong muốn. nếu Stemming được cho phép, một từ tìm kiếm với kí tự đại diện sẽ được Stemming trước khi tìm kiếm, vì thế nếu ta tìm kiếm “running* ” sẽ trở thành tìm kiếm“run” và kết quả trả về có thể chứa đựng từ “ runway ”. Tương tự như vậy, tìm kiếm “ run* ” sẽ không tìm được running như mong đợi, bởi vì running được lưu trong bảng chỉ mục dưới dạng stemming là run. * Truy vấn theo Meta Đây là phương pháp tìm kiếm theo chủ đề, cung cấp cách tìm kiếm chỉ trong một số của phần tử tài liệu. Ví dụ 1: Search “ author = John ” Chỉ tìm các tài liệu có tác giả ( author ) là John Truy vấn một cụm từ ví dụ 2: Search \ “Computer Science ” trả lại các tài liệu có chứa cụm từ Computer Science 3.2.2 Phân tích cú pháp truy vấn Ta sẽ sử dụng phép đệ qui Top - Down để phân tích một truy vấn. Cú pháp chuẩn của truy vấn có dạng: query: query optional_relop meta | meta meta: meta_name = primary | primary meta_name: word primary: '(' query ')' | 'not' meta | word | word* optional_relop: 'and' | 'or' | (empty) Tuy nhiên, ta nhận thấy rằng sản xuất của truy vấn này là đệ qui trái và sẽ không làm việc tốt trên phương pháp phân tích Top - Down, do đó ta phải viết nó dưới dạng đệ qui phải như sau: query: meta rest rest: optional_relop meta rest | ( empty ) Do người sử dụng luôn luôn đưa và truy vấn dưới dạng ngôn ngữ tự nhiên, điều đó có thể làm cho chương trình của chúng ta lặp vô hạn hoặc đưa ra kết quả không mong muốn, do đó trước khi phân tích cú pháp của truy vấn ta phải chuẩn hóa xâu truy vấn đề dạng chuẩn. Các bước đó có thể được tiến hành như sau: * Phân tích từ tố xâu truy vấn: + Nhận dạng các từ tố bởi dấu cách hoặc các kí tự đặc biệt (ví dụ như“ ( )= ”, riêng đối với cụm từ thì các từ chỉ cách nhau bởi dấu cách. + Nếu từ tố là tên Meta thì kiểm tra xem Meta đó có nằm trong bảng Meta không. + Chuyển cụm phép toán logic “ (and)n not ” trở thành “not”, ví dụ như ( mouse and not computer ) sẽ trở thành ( mouse not computer ). + Chuẩn hóa các từ trong truy vấn, có nghĩa là ta thực hiện stemming, bỏ qua các kí tự vô nghĩa ở đầu hoặc ở cuối, …v…v. + Loại bỏ một số từ vô nghĩa trong truy vấn ( những từ nằm trong Stopword ). + Xử lí các cụm từ nằm trong truy vấn, ví dụ như : / “ Computer Science / ” sẽ trở thành ( Computer Science ), dấu gạch chéo được dùng để nhận ra đây là một cụm từ cần tìm. + Đặt thêm dấu ngoặc vào vị trí thích hợp xung quanh một truy vấn Meta, ví dị như “Author = Red and Computer” sẽ trở thành( Author = Red ) and Com puter. Xử lí phép toán logic “ Not ”, có hai trường hợp xảy ra với toán hạng này. + Trường hợp 1: (Word1 Not Word2) sẽ được chuẩn hóa thành (Word1 And_ Not Word2). Với cách phân cũ, ta có phân tích truy vấn như sau: Có kết quả chứa Word1 Có kết quả chứa Word2 Phủ định kết quả chứa từ Word2, và giao hai danh sách kết quả với nhau (nếu chúng ta có 100 000 tài liệu mà Word2 chỉ nằm trong 3 tài liệu thì điều này đòi hỏi chúng ta phải đọc qua 99997 tài liệu) Với cách mới ta chỉ việc thực hiện như sau: Có kết quả chứa Word1 Có kết quả chứa Word2 Giao hai danh sách kết quả với luật And_Not +Trường hợp 2: “color = Not Black White” trở thành “( color =(Not Black)) White ”, việc chuẩn hóa sau này sẽ làm cho việc thực hiện toán hạng Not không rơi vào tình trạng lặp vô hạn. Sau khi thu được xâu truy vấn có dạng chuẩn hóa ta tiến hành phân tích truy vấn đó, tuy nhiên vẫn còn một một vấn đề lớn trong việc phân tích này, đó là ta sẽ thực hiện các phép toán logic trong truy vấn như thế nào, và như thế nào để ta thực hiện được các phép truy vấn với kí tự đại diện. 3.2.3 Các phương pháp giải quyết vấn đề trong phân tích truy vấn Sau mỗi truy vấn ta có một danh sách kết quả, mà mỗi phần tử trong danh sách đó có dạng : Typedef struct Result { Struct Result * next int filenum int rank; int frequently; int tfrequently; Và một số thông tin trỏ tới nơi lưu trữ thuộc tính của file này } - Thực hiện phép toán “ And ”2 danh sách kết quả Ví dụ ta có Search “ Word1 And Word2 ” Khi đó ta có R1 là danh sách kết quả các File chứa đựng từ Word1, R2 là danh sách kết quả các File chứa đựng từ Word2, các File nằm trong R1 và R2 đều được sắp xếp theo Filenum, khi đó ta tiến hành duyệt hai danh sách từ đầu tới cuối và thực hiện trộn hai danh sách này, nhưng sự kiện trộn chỉ được thực hiện khi R1 -> filenum = R2 ->filenum (có nghĩa là hai từ này đều được nằm trong một file ), khi đó tần số sẽ là tổng hai tần số. - Thực hiện phép toán “ OR ” hai danh sách kết quả Ví dụ Search “Black OR White ” Tương tự như trên ta cũng có hai danh sách kết quả R1 và R2, Rp một phần tử nằm trong danh sách kết quả cuối cùng của phép OR hai danh sách R1 và R2. Thì ta có phương pháp xác định Rp như sau: + Nếu R1-> filenum filenum thì Rp = R1-> Entry + Nếu R1->filenum > R2 ->filenum thì Rp = R2->Entry + Nếu R1->filenum =R2->filenum thì Rp là một nút mới với tần số bằng tổng của hai tần số trên. - Thực hiện phép toán “ And_Not ” hai danh sách kết quả Ví dụ: Search “ Mouse Not Computer ” Tương tự ta có R1, R2, Rp như định nghĩa ở trên. Khi đó ta duyệt hai danh sách R1, R2 từ đầu tới cuối. Res =R1->filenum – R2->filenum + Nếu Res Entry vào danh sách kết quả cuối cùng và tăng chỉ số của R1 + Nếu Res > 0 thì tăng chỉ số của R2 và không làm gì cả. + Nếu Res = 0 thì tăng chỉ số của cả hai danh sách và không làm gì cả. - Thực hiện phép toán “ Not ” danh sách kết quả Ví dụ Search “ Not Computer ” - Thực hiện tìm kiếm một cụm từ Ví dụ Search / “ Computer Science / ” Ta thực hiện như phép toán “And ” nhưng phải thỏa mãn thêm điều kiện là vị trí của hai từ này phải liền nhau. - Thực hiện tìm kiếm theo kí tự đại diện Khi gặp một từ tìm kiếm dưới dạng kí tự đại diện, ví dụ ( Comput* )khi đó ta có loại kí từ “*” nằm ở cuối thu được từ khóa “ Comput ” và thực hiện một phép tìm kiếm phạm vi trên cây B-Tree ( Có nghĩa là tìm kiếm trên cây B- Tree các từ khóa có phần đầu trùng với từ khóa tìm kiếm ) 3.3 Môđul sắp xếp * Các mô hình sắp xếp và đánh giá 1/ Mô hình Boolean Trong mô hình Boolean, các tài liệu và truy vấn được biểu diễn là tập hợp các term chỉ số, trọng số của term chỉ số được xem như chỉ nhận các giá trị 1 và 0 tương ứng với sự có mặt hoặc không có mặt. Một truy vấn q gồm các term chỉ số liên kết với nhau bởi 3 phép toán logic And, Or, Not ( tương ứng với các kí hiệu Ù,Ú vµ Ø) vµ cã thÓ chuyÓn vÒ d¹ng chuÈn DNF. VÝ dô, truy vÊn q = kaÙ(kbÚØkc) cã thÓ chuyÓn thµnh [=(1,1,1)Ú(1,1,0)Ú(1,0,0)], trong đó mỗi thành phần là một vector nhị phân liên kết với một bộ phận ( ka, kb, kc ), các vecter nhị phân này gọi là các thành phần liên kết của qdnf . Định nghĩa: Cho một mô hình Boolean, các term chỉ số đều được biểu diễn bởi các giá trị nhị phân w1j Є{ 0;1 }. Một truy vấn q là một biểu thức Boolean theo qui ước. Cho qdnf là vector liên kết DNF với truy vấn q, lấy qcc là thành phần liên kết nào đó của qdnf . độ tương tự của tài liệu dj với truy vấn q được xác định: 1, nÕu $ | (Î)Ù("ki, sim(dj,q) = (2.1) 0, cßn l¹i Nếu sim(dj, q)=1 thì mô hình Boolean dự đoán rằng tài liệu d1 là phù hợp với truy vấn q ( có thể là không ). Còn lại, là không phù hợp. Mô hình Boolean dự đoán rằng mỗi tài liệu hoặc phù hợp hoặc không phù hợp. chẳng hạn, cho tài liệu d1 với dj = ( 0,1,0 ). Tài liệu d chứa tem chỉ số kb nhưng được xem là không phù hợp với truy vấn [q=ka^(kb ¬kc)]. Mô hình Boolean cung cấp một cách nìn khá trực quan, đơn giản và dễ hiểu cho người sử dụng một hệ thống IR. Tuy nhiên, mô hình Boolean cũng có một số mặt hạn chế. Bởi chiến lược tìm kiếm của chúng dựa trên tiêu chuẩn quyết định nhị thức (một tài liệu được dự đoán chỉ trong hai khả năng là phù hợp hoặc không phù hợp) mà không có bất kỳ một khái niệm chia mức độ nào lựa chọn. Do vậy, mô hình Boolean không đưa ra danh sách các văn bản được sắp xếp theo mức độ liên quan đến yêu cầu của người dùng, dẫn đến việc mô hình này không thỏa mãn các yêu cầu trong các hệ thống tìm kiếm văn bản hiện nay như các công cụ tìm kiếm Web. do đó sau đây em xin đưa ra mô hình không gian vector- nó không chỉ nhận ra những tài liệu thỏa mãn truy vấn mà còn đưa ra được những mức độ liên quan đến truy vấn. 2/ Mô hình không gian vector Ta nhận thấy rằng, khi biểu diễn văn bản và truy vấn dưới dạng các vecter thì tích vô hướng của hai vecter đó có thể được xem như là độ liên quan giữa văn bản và truy vấn mà chúng ta biểu diễn. Cụ thể, giả thiết lập tài liệu bao gồm n Term khác nhau. Khi đó văn bản và truy vấn sẽ đượcbiểu diễn thành các vecter n chiều. Giả sử truy vấn và tài liệu lần lượt được biểu diễn thành các vector Q và Dd như sau: Một cách đơn giản nhất là gán xi (yi) bằng 1 nếu term thứ i trong từ điển có mặt trong truy vấn(hoặc là tài liệu) và bằng không trong trường hợp còn lại. Độ liên quan giữa truy vấn và văn bản được tính theo công thức: Mặc dù đã ước lượng được mức độ liên quan giữa truy vấn và tài liệu, nhưng với công thức trên vẫn còn một số hạn chế sau: Không thể hiện được các tần suất xuất hiện của các Term trong mỗi văn bản Không thể hiện được thuộc tính khan hiếm của một Term khi nó xuất hiện chỉ trong một số ít văn bản. Có sự phân biệt giữa các độ dài văn bản, cụ thể là những văn bản dài, chứa nhiều Term khác nhau được ưu tiên khi tính toán độ liên quan Hạn chế thứ nhất có thể khắc phục bằng cách thau thế các giá trị 0 và 1 bằng số lần xuất hiện của Term trong văn bản – fd,t. Tuy nhiên, để thỏa mãn một số hạn chế sau thì các thành phần này có thể thay bằng trọng số của từ đối với văn bản (hoặc truy vấn) và có ký hiệu tương ứng là wdj (wqj). Khi đó độ liên quan giữa văn bản và truy vấn được tính theo công thức sau: Hạn chế thứ hai có thể được khắc phục bằng cách giảm trọng số của những từ xuất hiện trong nhiều văn bản. Một trong những giải pháp là tính trọng số của từ theo nghịch đảo của số lượng các văn bản chứa từ đó. Cụ thể là nếu gọi wt là trọng số của từ t đối với toàn bộ tập văn bản thì ta có: Trong đó là số lần văn bản chứaTerm t. Trọng số của Term đối với tập văn bản được sử dụng để tạo ra trọng số của Term đó cũng với từng văn bản cũng như đối với truy vấn. Kí hiệu rd,t và rq,t lần lượt là các giá trị chỉ mức độ liên quan giữa term và văn bản, term và truy vấn theo tần suất xuất hiện của hai term đó thì hai giá trị này cùng với wt ở trên tạo ra rd,t và rq,t . ngoài ra chúng ta còn có một số công thức để tính wt như sau: Trong đó N là số văn bản trong toàn tập tài liệu. là số lớn nhất trong số những giá trị chỉ số lần xuất hieenjcuar một Term trong một văn bản. Mặt khác ta nhận thấy rằng mối quan hệ giữa một Term và một văn bản càng cao khi số lần xuất hiện của Term đó trong văn bản càng nhiều nên có thể tính theo công thức : Phép tính Logarith trong các công thức trên nhằm tránh sự phụ thuộc tuyến tính giữa số lần xuất hiện và độ liên quan. cũng được tính một cách tương tự trong đó được thay bằng . Sau đó trọng số của Term đối với văn bản () và truy vấn () có thể được tính theo luật . Theo luật này trọng số của Term tỉ lệ thuận với số lần xuất hiện của nó trong văn bản (hoặc truy vấn) và tỉ lệ nghịch với văn bản chứa Term đó. Hạn chế thứ ba (về sự phân biệt giữa văn bản dài và văn bản ngắn) có thể khắc phục bằng cách chia độ liên quan thu được ở trên cho độ dài của văn bản ().Độ dài của một văn bản được xác định theo số lượng Term và số lần xuất hiện của nó trong văn bản đó. Ngoài ra bằng cách đặt wq,t = 0 khi Term t không xuất hiện trong truy vấn thì độ liên quan giữa văn bản và truy vấn được tính như sau: Các vấn đề ở trên đã từng bước đề xuất các giải pháp cho các hạn chế nêu trên. Tuy nhiên hầu hết các truy vấn có chiều dài ngắn hơn rất nhiều so với các văn bản, để khắc phục vấn đề này người ta dùng khái niệm hướng của hai vector và khi đó góc tạo bởi hai vector thể hiện sự khác biệt giữa chúng. Văn bản mà góc giữa vector biểu diễn của nó và vector biểu diễn yêu cầu tìm kiếm càng nhỏ thì được coi là có độ liên quan càng cao. Gọi (Q,D) là góc giữa truy vấn và văn bản thì Cosine của nó được tính theo công thức sau: Trong đó : Là trọng số của văn bản Dd và truy vấn Q tính theo khoảng cách Euclidean. Giả sử lựa chọn một trong các công thức đã nêu ở trên để tính các trọng số, Chẳng hạn: Thì giá trị Cosine được tính theo công thức sau : Áp dụng các công thức của mô hình không gian vector có thể cho ta một sắp xếp về độ liên quan của các văn bản tới truy vấn là chuẩn xác nhất, tuy nhiên ta chỉ có thể áp dụng được công thức này khi truy vấn của ta ở dưới dạng một cụm từ (một đoạn văn bản ngắn). Còn đối với các dạng khác của truy vấn thì ta không thể áp dụng được công thức này. Lúc này em xin đưa ra một cách thức tính mức độ liên quan của văn bản tới cho một số dạng truy vấn như sau: Công thức tính độ liên quancuar một tài liệu đối với Term truy vấn là: Rank = ( log (freq)*factor ) / log10 (Word - count) Và công thức tính Rank trong một biểu thức truy vấn có các dạng sau: - Đối với phép And : “Word1 And Word2” Chỉ được tính khi hai từ cùng mằn trong một File, và giá trị sắp xếp New_Rank = (R1->Rank +R2 -> Rank ) / 2. Tuy nhiên đây là trường hợp đơn giản bởi chỉ có hai từ được And cùng nhau, nếu ta vẫn áp dụng công thức này khi số lượng từ lớn hơn 3, ví dụ như “Word1 And Word2 And Word3” khi đó trọng lượng của Word3 là 50%, trọng lượng của Word 1 và Word2 là 25%, để thu được một kết quả cân bằng hơn ta phải thêm vào một nhân tử AndLevel. Khi đó ta có công thức tính giá trị sắp xếp mới là: Rank = ((R1 -> Rank *AndLevel) + R2 -> Rank) / (AndLevel + 1) - Đối với phép Or : “Word1 Or Word2 ” New_Rank = Rank1 hoặc Rank2 nếu hai từ không cùng nằm trong một File, còn ngược lại thì: New_Rank = Rank1 + Rank2 - Đối với phép Not hai toán tử : Word1 NOT Word2 New_Rank = Rank1 - Đối với phép Not một toán tử : Not Word Ta tăng toàn bộ giá trị Rank của danh sách kết quả tìm được lên 1000. PHẦN III: KẾT LUẬN 1. Kết quả đạt được trong luận văn Luận văn đã bước đầu nghiên cứu, tổng hợp các vấn đề lý thuyết trong bài toán “Tìm kiếm thông tin” đặc biệt là tìm kiếm thông tin trên mạng. Em cũng đã đưa ra các chiến lược tốt nhất cho một bộ công cụ tìm kiếm trên mạng. Dựa vào mô hình lý thuyết, em đã tiến hành cài đặt một số chức năng hỗ trợ cho việc thiết kế bộ công cụ tìm kiếm trên mạng. Các chức năng này có những đặc tính tối ưu như: * Thời gian lập chỉ mục nhanh và đầy đủ, hỗ trợ một cách tốt nhất cho quá trình tìm kiếm. * Lựa chọn thuật toán và cấu trúc dữ liệu tối ưu, đảm bảo đáp ứng hầu như tất cả các dạng truy vấn với thời gian ngắn nhất. * Đưa ra tập kết quả theo thứ tự độ liên quan tới truy vấn cao. Bên cạnh những gì đã đạt được, do thời gian có hạn và còn thiếu rất nhiều kinh nghiệm nên có những vấn đề em vẫn chưa giải quyết được như: *Hệ thống chưa có các chức năng xử lý tìm kiếm trên văn bản tiếng việt do chưa có bộ từ điển tiếng Việt chuẩn và chưa có điều kiện tìm hiểu sâu về cách xử lý với ngôn ngữ tiếng Việt. Đây là vấn đề mà em mong muốn sẽ thự hiện trong tương lai. Do hạn chế về thời gian và kinh nghiệm nên em chưa có điều kiện thử nghiệm một số thuật toán được đưa ra trong phần lý thuyết. Ví dụ như: Các thuật toán PageRank, HIST để tính toán độ liên quan của tài liệu tới truy vấn dựa vào mối liên kết giữa các trang trên Web. Đây có thể là những hướng nghiên cứu trong tương lai của đề tài này. Trong quá trình thực hiện luận văn này, tôi đã cố gắng tập trung tìm hiểu và tham khảo nhiều tài liệu có liên quan. Tuy nhiên, với thời gian và trình độ có hạn nên luận văn không tránh khỏi những hạn chế và thiếu sót. Tôi rất mong được sự góp ý của quí thầy, cô và các bạn đồng nghiệp để hoàn thiện hơn kết quả nghiên cứu của mình. 2. Hướng phát triển tiếp theo của luận văn Thực hiện tìm kiếm với tài liệu tiếng việt Thực hiện tìm kiếm dữ liệu ảnh Một vấn đề cũng rất quan trọng và phức tạp trong tìm kiếm thông tin đó là làm như thế nào ta có thể tóm tắt nội dung của một tài liệu tìm kiếm được, bởi số lượng tài liệu tìm được là rất lớn mà nội dung của mỗi tài liệu thì rất dài nên người sử dụng không thể duyệt qua tất cả được. TÀI LIỆU THAM KHẢO [1] William B. Frakes and Ricardo Baeza-Yates. Information Retrieval : Data Structures & Algorithms. [2] S.Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. In proceedings of 7th World Wide Web Conference, 1998 [3] Sergey Brin. Etracting patterns and relations from the world wide web. In WebDB Workshop at 6th Internation Conference on Extending Database Technology, EDBT’98, 1998. Available at [4] Sergey Brin and Lawrence Page. The anatomy of a large-scale hypertextual web search engine. In proceedings of the seventh international World-Wide Web Conference, 1998 [5] Junghoo Cho and Hector Garcia-Molina. The evolution of the web and implications for an incremental crawler. In Proceedings of the Twenty-sixth international conference on Very Large Databases,2000. Available at : [6] Junghoo Cho, Hector Garcia-Molina, and Lawrence Page. Efficient crawling though url ordering. In proceedings of the Seventh International World-Wide Web Conference, 1998. Available at : [7] Taher Haveliwala. Efficient computation of pagerank. Technical Report 1999-31, Database Group, Computer Science Department, Stanford University, February 1999 Available at : [8] Jun Hirai, Sriram Raghavan, Hector Garcia-Molina, and Andreas Paepcke. Webbase : A repository of web pages. In Proceedings of the Ninth International World-Wide Web Conference, pages 277-293, may 2000. Available at : [9] Udi manber and gene Myers. Suffix arrays : A new method for on-line string searches. In proc. Of the 1st ACM-SIAM Symposium on Discrete Algorithms, trang 319-327, 1990 [10] Một số tài liệu cho HTML và XML trong các Site : [11] Tatu Ylonen. An Algorithm for Full Text Indexing, 1992.