Chương 1. Hệ tìm kiếm thông tin trên Internet Nhận dạng từ 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 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 từ nối (inter-word). Để minh hoạ, chúng ta xem xét một ví dụ về văn bản gốc như sau: 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. Trong ví dụ trên, tất cả ký hiệu không phải ký tự hoặc chữ số đều là các ký hiệu từ nối. Các ký hiệu từ nối được loại bỏ trong giai đoạn này và các dãy ký hiệu còn lại là các từ tố xử lý. Ngoài ra, có một số luật heuristic thông dụng để nhận dạng một từ không được lập chỉ mục là: 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 từ dừng Luận văn Cao học ngành Công nghệ Thông tin – ĐH Bách Khoa Hà Nội 20 Chương 1.
Hệ tìm kiếm thông tin trên Internet Áp dụng các kỹ thuật nhận dạng từ nối và luật heuristic, tài liệu sau khi loại bỏ tất cả các dấu chấm, dấu nối và dấu chấm hỏi có dạng: chapter 1 preamble 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 Loại các từ dừng (stopword) Từ dừng là từ xuất hiện trong tài liệu nhưng không mang nhiều ý nghĩa thông tin. Thông thường, những từ này là giới từ của Tiếng Anh hay từ đệm mang tính địa phương của Tiếng Việt. Trong quá trình lập chỉ mục, các từ này đã được chứa trong một danh sách từ dừng. Môđun lập chỉ mục sẽ căn cứ vào đó để loại chúng ra khỏi tài liệu.
Với ví dụ ở trên, tài liệu sau khi được loại bỏ các từ dừng sẽ là: chapter 1 preamble humanity stands defining moment history we confronted perpetuation disparities nations worsening poverty hunger ill health illiteracy continuing deterioration ecosystem we depend well Chuẩn hoá hình thái từ Các từ trong một tài liệu sau khi được xác định là có khả năng lập chỉ mục thì chúng sẽ được chuẩn hoá. Chuẩn hoá hình thái từ trong tài liệu và truy vấn được sử dụng để tìm các dạng hình thái khác nhau của từ ban đầu. Công việc này có thể được thực hiện bằng cách sử dụng môđun lược từ (Stemmer) hoặc từ điển tìm kiếm. Môđun lược từ áp dụng các luật để chuẩn hoá từ.
Một số môđun lược từ đã phát triển từ những năm 60 khi các hệ tìm kiếm đầu tiên được thực hiện. Các môđun lược từ nổi tiếng như của Lovins [1] và Porter [2], sau đó đã trở thành giải thuật được chấp nhận rất phổ biến. Luận văn Cao học ngành Công nghệ Thông tin – ĐH Bách Khoa Hà Nội 21 Chương 1. Hệ tìm kiếm thông tin trên Internet 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 hai từ có nghĩa hoàn toàn khác nhau thành một từ gốc, chẳng hạn các từ “skies” (trời, khí hậu) và “ski” đều lược thành “ski”. Trong trường hợp như vậy người sử 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à 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 môđun 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. Trở lại ví dụ đã đưa ra ở trên, văn bản sau khi chuẩn hoá từ sẽ như sau: chapter 1 preambl human stand defin moment histori confront perpetu dispar nation worsen poverti hunger ill health and illiteraci continu deterior ecosystem depend well be Từ điển tìm kiếm sẽ cho kết quả với 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 từ điển hình thái 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ời quá khứ của một động từ, lemma của nó là “see” và có thể là 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 từ loại chính xác và do vậy đưa ra những lemma chính xác. Luận văn Cao học ngành Công nghệ Thông tin – ĐH Bách Khoa Hà Nội 22 Chương 1. Hệ tìm kiếm thông tin trên Internet 1.
Xây dựng chỉ mục tài liệu Sau khi từ đã được chuẩn hoá, môđun này sẽ sử dụng các thuật toán và cấu trúc dữ liệu để lưu trữ các từ cùng với thông tin về tài liệu và vị trí của từ trong tài liệu đó. Mục tiêu là xây dựng được một chỉ mục tài liệu tiết kiệm chi phí lưu trữ và tăng hiệu quả khi tìm kiếm. Lập chỉ mục tài liệu trong hệ tìm kiếm thông tin Google Hiện nay chúng ta có thể thấy rằng, hệ tìm kiếm Google đang giữ vị trí thống trị trong các hệ tìm kiếm thông tin. Thậm chí nếu MSN đang cố gắng hết sức để đuổi theo một cách mạnh mẽ bằng các công cụ tìm kiếm mới, thì với một ngân quỹ quảng cáo to lớn và phương pháp sắp xếp mới, Google vẫn vượt trội hơn.
Yahoo và Ask Jeeves vẫn còn đang ở dạng tiềm năng, trong khi từ thập niên 90, các lỗi lớn của AltaVista và Webcrawler đã làm cho chúng có những bước thụt lùi nghiêm trọng. Với các lý do trên, Luận văn sẽ trình bày phương pháp mà Google lập chỉ mục tài liệu, từ đó tìm cách đánh giá hiệu năng của phương pháp này.6 sau đây là mô hình kiến trúc tổng quan của Google. Google được viết bằng ngôn ngữ lập trình C\C++ và chạy trên Solaris hoặc Linux.6: Kiến trúc tổng quan của hệ tìm kiếm thông tin Google Luận văn Cao học ngành Công nghệ Thông tin – ĐH Bách Khoa Hà Nội 23 Chương 1. Hệ tìm kiếm thông tin trên Internet Theo Sergey Brin và Lawrence Page [3], trong Google, việc thu hồi các trang web được thực hiện bởi môđun thu hồi.
Môđun này nhận danh sách URL do URLserver tìm được gửi đến. Các trang web đã thu hồi sẽ được cho vào server lưu trữ (Store Server). Server này sau đó sẽ nén và lưu trữ các web này vào trong một kho. Mỗi trang đều được gán bằng một số gọi là docID khi có một URL mới được đưa vào phân tích.
Môđun lập chỉ mục (Indexer) thực hiện các chức năng đọc kho chứa các tài liệu, giải nén và phân tích chúng. Mỗi tài liệu được chuyển thành một tập từ xuất hiện (word occurrence) gọi là các hit. Một hit bao gồm nội dung và vị trí của từ trong tài liệu. Môđun lập chỉ mục phân loại các hit này vào trong một tập của các barrel, nơi tạo ra một phần chỉ mục tài liệu đã được sắp xếp.
Ngoài ra môđun lập chỉ mục cũng thực hiện một số chức năng quan trọng khác. Nó phân tích các đường liên kết vào ra của mọi trang web và lưu trữ thông tin quan trọng của chúng vào trong một file mấu neo (anchor file). File này chứa đầy đủ thông tin để xác định các điểm liên kết đến và đi, và văn bản được liên kết trỏ đến. Môđun phân tích URL (URLresolver) đọc các file mấu neo và chuyển đổi các URL tương đối sang URL tuyệt đối và đổi thành các docID.
Nó để file mấu neo vào trong chỉ mục forward, liên kết với docID mà các mấu neo trỏ đến. Nó cũng sinh ra một cơ sở dữ liệu của các liên kết dùng để tính toán PageRank cho tất cả tài liệu. Môđun sắp xếp (Sorter) lấy các barrel đã được sắp xếp bởi docID, và sắp xếp lại chúng bằng wordID để tạo ra chỉ mục inverted. Cần có một không gian tạm để thực hiện việc này.
Môđun sắp xếp cũng tạo ra một danh sách của wordID và đặt nó vào trong chỉ mục inverted. Một chương trình được gọi là DumpLexicon lấy một danh sách lexicon được tạo bởi môđun lập chỉ mục để tạo ra một lexicon mới sử dụng cho môđun tìm kiếm (Searcher). Môđun tìm kiếm chạy bởi một web server và sử dụng Luận văn Cao học ngành Công nghệ Thông tin – ĐH Bách Khoa Hà Nội 24 Chương 1. Hệ tìm kiếm thông tin trên Internet lexicon được xây dựng bởi DumpLexicon cùng với chỉ mục inverted và PageRank để trả lời cho các câu truy vấn.
Cấu trúc dữ liệu của Google được tối ưu hoá do đó một số lượng lớn tài liệu có thể được thu hồi, lập chỉ mục và tìm kiếm với chi phí rất nhỏ. Mặc dù khả năng của bộ xử lý và tốc độ vào ra đã thay đổi nhanh chóng trong thời gian gần đây, cho nên sự truy suất trên ổ đĩa bây giờ chỉ cần tối đa 10 giây để hoàn thành, tuy nhiên, cấu trúc dữ liệu của Google vẫn được thiết kế để tránh truy suất trên ổ đĩa ít nhất có thể. Kho chứa (repository) Kho chứa lưu trữ đầy đủ nội dung HTML (HyperText Markup Language) của mọi trang. Mỗi trang được nén lại bằng cách sử dụng zlib.
Việc lựa chọn kỹ thuật nén là một sự thoả hiệp giữa tốc độ và tỉ lệ nén. Google chọn tốc độ của zlib trên mặc dù biết đến sự phát triển đáng ghi nhận về tỷ lệ nén của bzip. Tỷ lện nén của bzip xấp xỉ 4/1 so với zlib là 3/1. Trong kho chứa, các tài liệu được sắp xếp lần lượt theo thứ tự docID, kích thước tài liệu, URL như trong hình 1.
sync length compressed packet sync length compressed packet Hình 1.7: Cấu trúc trong dữ liệu kho chứa của Google Chỉ mục tài liệu Chỉ mục tài liệu chứa thông tin của các tài liệu, được sắp xếp bởi docID. Thông tin được lưu trữ bao gồm trạng thái của tài liệu hiện tại, một con trỏ trỏ Luận văn Cao học ngành Công nghệ Thông tin – ĐH Bách Khoa Hà Nội 25 Chương 1.