Ứng dụng cây hậu tố để so khớp độ giống nhau giữa các tài liệu

Abstract

Cây hậu tố là một cấu trúc dữ liệu quan trọng được sử dụng trong rất nhiều thuật toán xử lý xâu. Sức mạnh của cây hậu tố nằm ở khả năng biểu diễn tất cả các hậu tố của một xâu và cung cấp nhiều phép toán quan trọng giúp nâng cao tính hiệu quả của những thuật toán. Chính nhờ những tính chất đó mà cây hậu tố được sử dụng rất nhiều trong các lĩnh vực khác nhau như: xử lý văn bản, trích chọn và tìm kiếm thông tin, phân tích dữ liệu sinh học, đối sánh mẫu, nén dữ liệu… Để đánh giá mức độ giống nhau của văn bản, thường sử dụng các phép đo độ tương tự giữa các văn bản. Sự tương đồng giữa hai văn bản là sự giống nhau về nội dung giữa hai văn bản đó. Do đó, hai văn bản là bản sao hoặc gần giống nhau thì sẽ có nội dung giống nhau nhiều, hay độ tương đồng giữa hai văn bản là cao. Luận văn tập trung nghiên cứu, đề xuất phương pháp so sánh văn bản dựa trên cây hậu tố để ứng dụng trong bài toán tính độ tương đồng văn bản, cụ thể là đánh giá mức độ giống nhau của hai văn bản và của một văn bản truy vấn so với tập văn bản mẫu trong kho dữ liệu.