chương 1 của luận văn. Nội dung chương 2 giới thiệu cấu trúc chỉ mục ngược và cấu trúc hỗ trợ lưu trữ và tìm kiếm thuật ngữ trong từ điển của chỉ mục ngược một cách hiệu quả, dựa trên những cấu trúc này các giải pháp tìm kiếm theo ký tự đại diện được trình bày bao gồm: chỉ mục quay, chỉ mục k-gram, và các giải pháp dựa trên otomat.1 Giới thiệu cấu trúc chỉ mục ngƣợc Chỉ mục (index) là một cách bố trí có hệ thống của các chủ đề hay các mô tả của các tài liệu để tạo điều kiện thuận lợi cho tìm kiếm tài liệu hay một phần của tài liệu. Chỉ mục bao gồm các thành phần chính: (a) các thuật ngữ (term) đại diện cho các chủ đề hay các mô tả của các đơn vị tài liệu; (b) một cú pháp (syntax) kết hợp các thuật ngữ trong các tiêu đề hay các mệnh đề tìm kiếm để đại diện cho các chủ đề, các mô tả hay các truy vấn phức tạp; (c) các tham chiếu chéo (cross-reference) hay các phương thức liên kết giữa các thuật ngữ đồng nghĩa, tương đương, mở rộng, các thuật ngữ có nghĩa hẹp hơn hay các thuật ngữ có liên quan khác; (d) một thủ tục liên kết phần tiêu đềhay các mệnh đề tìm kiếm với các đơn vị tài liệu cụ thể hay các đại diện tài liệu; và (e) một thứ tự hệ thống của các tiêu đề hay một thủ tục tìm kiếm. Chỉ mục ngược (inverted index) là chỉ mục trong đó các thuật ngữ có liên kết với các phần tài liệu chứa nó.
Ý tưởng chính của chỉ mục ngược được giới thiệu trong hình 2. Một từ điển (dictionary) là một cấu trúc dữ liệu được sử dụng để lưu các thuật ngữ. Mỗi thuật ngữ sẽ có một danh sách để lưu lại các tài liệu (thường là định danh Identification(ID) của tài liệu) có chứa thuật ngữ đó gọi là danh sách các posting (postings list). Mỗi phần tử trong danh sách được gọi là một posting.Từ điển cho chỉ mục ngược thường được lưu trong bộ nhớ trong, gồm một số thông tin quan trọng như: các thuật ngữ, số lượng tài liệu chứa thuật ngữ và danh sách các posting…, với các con trỏ trỏ đến các danh sách posting được lưu trên ổ đĩa.1 được sắp xếp theo thứ tự từ điển và mỗi danh sách các posting được sắp xếp theo ID của tài liệu.
Bởi vì có nhiều biến thể của các chỉ mục ngược sẽ phát triển trong chương này, nêncụm từ chỉ mục ngược tiêu chuẩn được dùng để chỉ cấu trúc chỉ mục được đề cập trong mục 2. Chi tiết về chỉ mục ngược và các biến thể của chỉ mục ngược được trình bày trong [3,12]. TIEU LUAN MOI download : skknchat@gmail.com 7 brutus 1 2 4 11 31 45 173 174 caesar 1 2 4 5 6 16 57 132 … 2 31 54 101 calpurina. Dictionary Postings Hình 2.1 Cấu trúc của chỉ mục ngược.
Với một chỉ mục ngược và một truy vấn cho trước,nhiệm vụ đầu tiên là xác định xem mỗi thuật ngữ truy vấn có tồn tại trong từ điển hay không, nếu có xác định các con trỏ đến các posting tương ứng. Một giải phápcho phép lưu trữ và tìm kiếm các thuật ngữ trong từ điển hiệu quả sẽ góp phần cải thiện hiệu quả tìm kiếm nói chung. Có hai lớp giải pháp mở rộng được đề xuất là bảng băm và cây tìm kiếm, tuy nhiên nếu số lượng các thuật ngữkhông ngừng tăng lên thì kích thước của bảng băm là một hạn chế, do đó cây tìm kiếm là một giải pháp tối ưu hơn khi tìm kiếm các thuật ngữ trong từ điển. Root a-m n-z a-hu hy-m n-sh si-z .2 Một cây tìm kiếm nhị phân.Trong ví dụ này nhánh tại gốc phân chia từ vựng thành hai cây con, cây con thứ nhất gồm các chữ cái từ a đến m, cây con thứ hai là phần còn lại.
Cây tìm kiếm được dùng phổ biến nhất là cây nhị phân, trong đó mỗi nút bên trong của cây có hai con. Việc tìm kiếm một thuật ngữ bắt đầu ở gốc của cây. Mỗi nút bên trong (bao gồm cả gốc) đại diện cho một điều kiện nhị phân, TIEU LUAN MOI download : skknchat@gmail.com 8 tùy theo kết quả trả về mà việc tìm kiếm được tiếp tục thực hiện đối với một trong hai cây con bên dưới nút đó.2 đưa ra ví dụ về một cây tìm kiếm nhị phân được sử dụng cho một từ điển. Một tìm kiếm được đánh giá là hiệu quả (có độ phức tạp về thời gian là O(log M)) khi cây được duy trì cân bằng trong suốt quá trình tìm kiếm.
Một cây nhị phân được gọi là cân bằng khi số các nút dưới hai cây con của nút bất kỳ hoặc là bằng nhau hoặc chỉ sai khác nhau một. Vấn đề chính ở đây là việc tái cân bằng: khi các thuật ngữ được chèn vào hoặc bị xóa từ các câytìm kiếm nhị phân, nó cần phải được tái cân bằng để duy trì độ cân bằng thích hợp. Một giải pháp để giảm thiểu sự tái cân bằng là cho phép số lượng cây con dưới một nút trong thay đổi trong một khoảng cố định. Một cây tìm kiếm thường được sử dụng cho một từ điển là B-tree–là cây tìm kiếm trong đó mỗi nút trongcó số cây con nằm trong khoảng [a, b], trong đó a và b là các số nguyên dương thích hợp; Hình 2.3 cho thấy một ví dụ với a = 2 và b = 4.
Mỗi nhánh của một nút trong đại diện cho một dãy các chuỗi ký tự, như trong ví dụ cây nhị phân của hình 2. Một B-tree có thể được xem như là sự "thu gọn" nhiều mức của cây nhị phân thành một mức; Trong trường hợp các từ điển được lưu trên đĩa thìviệc thu gọncây nhị phân sẽ giúp tìm nạp trước các điều kiện nhị phân sắp xảy ra. Trong trường hợp như vậy, các số nguyên a và b được xác định bởi kích thước của các khối đĩa. Trong ví dụ này mỗi nút trong có từ 2 đến 4 con.
Tìm kiếm thuật ngữ trong từ điển là hoạt động tất yếu trong quá trình tìm kiếm, trong phần tiếp theo, cây tìm kiếm trình bày ở trên sẽ làcấu trúc hiệu quả giúp tìm kiếm các thuật ngữ truy vấn khác nhau tương ứng với truy vấn chứa ký tự đại diện ban đầu trong từ điển. Sau đó, quá trình tìm kiếm trên cấu trúc chỉ mục ngược tiêu chuẩn mới được thực hiện. TIEU LUAN MOI download : skknchat@gmail.2Tìm kiếm theo ký tự đại diện Phần này nghiên cứu các ý tưởng của một truy vấn theo ký tự đại diện: một truy vấn như * a * e * i * o * u *, tìm các tài liệu có chứa tất cả năm nguyên âm theo thứ tự như trên. Các dấu * thể hiện cho các chuỗi ký tự bất kỳ (bao gồm chuỗi có độ dài bằng 0).
Người dùngđưa ra các câu truy vấntheo ký tự đại diện khi họ không chắc chắn về cách đánh vần một thuật ngữ truy vấn, hoặc tìm kiếm các tài liệu có chứa các biến thể của một thuật ngữ truy vấn; Ví dụ, truy vấn automat* sẽ tìm kiếm các tài liệu có chứa bất kỳ các thuật ngữ, automatic, automation and automated. Trong tìm kiếm theo ký tự đại diện, ký tự đại diện có thể nằm ở cuối truy vấn (trailing wildcard query), có thể nằm đầu truy vấn (leading wildcard query), và trong trường hợp tổng quát, ký tự đại diện có thể nằm ở vị trí bất kỳ trong truy vấn. Tùy theo vị trí của ký tự đại diện, các kỹ thuật xử lý sẽ được giới thiệu trong các nội dung tiếp theo. Truy vấn mon*, ký tự * xuất hiện chỉ một lần, ở cuối truy vấn.
Một cây tìm kiếm trên từ điển là một cách hiệu quả để xử lý các truy vấn có ký tự đại diện theo sau: thực hiện duyệt cây từ gốc lần lượt theo các ký tự m, o và n, để có thể liệt kê tập Wchứa các thuật ngữ trong từ điển có tiền tố là mon. Cuối cùng, | W | được sử dụng để tìm kiếm trên chỉ mục ngược tiêu chuẩn giúptìm được tất cả các tài liệu có chứa bất kỳ thuật ngữ nào trong W. Đối với các truy vấn có ký tự đại diệnnằm đầu truy vấn, ví dụ *mon. Một B-tree ngược (reverse B-tree) với từ điểnlà cây trong đó mỗi đường đi từ gốc tới lá của B-tree tương ứng với một thuật ngữ trong từ điển được viết ngược.
Theo đó, thuật ngữ lemon, trong B-tree, được đại diện bởi đường đi: gốc-n-o-m-e-l. Để liệt kê tất cả các thuật ngữR trong từ vựng với một tiền tố đã cho cần thực hiện duyệt cây B-tree ngượcbắt đầu từ gốc. Trong thực tế, ta có thể xử lý các truy vấn theo ký tự đại diện tổng quát, có một ký tự * duy nhất, như se*monbằng việc sử dụng kết hợp một B-tree thường với một B-tree ngược. Trong trường hợp tổng quát này, một B-tree thường được sử dụng để liệt kê tập Wcác thuật ngữ của từ điển bắt đầu với tiền tố se, sau đó, một B-tree ngược sẽ được sử dụng để liệt kê tập R các thuật ngữ kết thúc với hậu tốmon.
Tiếp theo, lấy kết quả phép giao W ∩ Rcủa hai tập hợp, để thu được tập các thuật ngữ bắt đầu với tiền tố sevà kết thúc với hậu tốmon. Cuối cùng, một chỉ mục ngược tiêu chuẩn được sử dụng để tìm tất cả các tài liệu có chứa các thuật ngữ trong tập hợp là kết quả của phép giao này. TIEU LUAN MOI download : skknchat@gmail.com 10 Ngoài cách sử dụng kết hợp một B-tree thường và một B-tree ngược để xử lý các truy vấn theo ký tự đại diện tổng quát, còn có những kỹ thuật xử lý các truy vấn theo ký tự đại diện tổng quát hiệu quả khác như sử dụng cấu trúc chỉ mục quay và chỉ mục k-gram. Cả hai kỹ thuật này đều chia sẻ một chiến lược chung: biểu diễn truy vấn theo ký tự đại diện đã cho qw như một truy vấn logic (Boolean query) Q trên một chỉ mục có cấu tạo đặc biệt, vì thế mà câu trả lời cho Q là một tập bao gồm cả tập các thuật ngữ là kết quả của truy vấn qw, sau đó, thực hiện kiểm tra từng thuật ngữ trong câu trả lời của Qđể loại bỏ các thuật ngữ không phù hợp với qw.
Khi đó, thu được các thuật ngữ phù hợp với qwđể có thể tìm kiếm với chỉ mục ngược tiêu chuẩn.1 Chỉ mục quay Chỉ mục đặc biệt đầu tiên cho các truy vấn theo ký tự đại diện tổng quát là chỉ mụcquay (permuterm index), một dạng của chỉ mục ngược [3]. Đầu tiên, một ký tự đặc biệt $ được thêm vào cuối truy vấn, để đánh dấu sự kết thúc của một thuật ngữ. Ví dụthuật ngữ hellosẽ thànhhello$.