Kỹ thuật tìm kiếm dựa trên từ khóa trong cơ sở dữ liệu và ứng dụng

- Trần Công Cẩn CHUYÊN NGÀNH CÔNG NGHỆ THÔNG TIN KỸ THUẬT TÌM KIẾM DỰA TRÊN TỪ KHÓA TRONG CƠ SỞ DỮ LIỆU VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ KHOA HỌC CHUYÊN NGÀNH CÔNG NGHỆ THÔNG TIN KHÓA 2009 Hà Nội – Năm 2012 1 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI.
- Trần Công Cẩn KỸ THUẬT TÌM KIẾM DỰA TRÊN TỪ KHÓA TRONG CƠ SỞ DỮ LIỆU VÀ ỨNG DỤNG Chuyên ngành: Công nghệ thông tin LUẬN VĂN THẠC SĨ KHOA HỌC CHUYÊN NGÀNH CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: Tiến sĩ Vũ Tuyết Trinh.
- 3 LỜI CẢM ƠN Đầu tiên, em xin trân trọng cảm ơn quý Thầy giáo, Cô giáo Viện Công nghệ thông tin và Truyền thông trường Đại học Bách khoa Hà Nội đã tận tình dạy dỗ và giúp đỡ em trong quá trình học cao học.
- Xin trân trọng cám ơn tiến sĩ Lê Hồng Phương đã cung cấp các thông tin liên quan về bộ phân tách từ tiếng Việt vnTokenizer.
- Xin cám ơn Ban Giám đốc Sở Thông tin và Truyền thông tỉnh Khánh Hòa đã quan tâm tạo điều kiện về thời gian để bản thân tôi có điều kiện tham gia học tập và hoàn thành luận văn tốt nghiệp.
- 10 Chương 2 – CƠ SỞ LÝ THUYẾT HỆ TÌM KIẾM.
- Hệ tìm kiếm thông tin 12 2.1.1.
- Mô hình hệ tìm kiếm thông tin.
- Thành phần cơ bản của hệ tìm kiếm thông tin.
- Hệ tìm kiếm toàn văn trong hệ quản trị cơ sở dữ liệu quan hệ.
- Kiến trúc hệ tìm kiếm toàn văn.
- Một số hạn chế của hệ tìm kiếm toàn văn.
- 23 Chương 3 – KỸ THUẬT TÌM KIẾM DỰA TRÊN TỪ KHÓA TRONG CƠ SỞ DỮ LIỆU QUAN HỆ.
- Phân tích truy vấn 25 3.2.1.
- Bộ Gán nhãn từ khóa 27 3.3.
- Sinh theo nhãn từ khóa 30 3.3.2.
- Thiết kế cơ sở dữ liệu.
- Tổ chức tìm kiếm.
- 41 5 Danh mục các ký hiệu, các chữ viết tắt Ký hiệu Viết đầy đủ và diễn giải CSDL Cơ sở dữ liệu CSDLQH Cơ sở dữ liệu quan hệ FTS Full text search: tìm kiếm toàn văn HQTCSDLQH Hệ quản trị cơ sở dữ liệu quan hệ IRS Information retrieval system: Hệ tìm kiếm thông tin SQL Structured query language: ngôn ngữ truy vấn có cấu trúc Danh mục các thuật ngữ Ký hiệu Diễn giải FTS Engine Mô-tơ tìm kiếm toàn văn trong HQTCSDLQH FTS Index Chỉ mục tài liệu của hệ tìm kiếm toàn văn trong CSDLQH Index terms Các từ khóa biểu diễn nội dung tài liệu trong hệ tìm kiếm thông tin truy vấn freetext Là kiểu tìm kiếm mà người dùng tự do nhập vào các từ khóa cần tìm, không cần biết thông tin về lược đồ cơ sở dữ liêu.
- còn được gọi là truy vấn từ khóa kiểu tự do (free form keyword).
- Hệ tìm kiếm tự chuyển câu truy vấn của người dùng sang câu truy vấn SQL để thực hiện tìm kiếm và trả kết quả về người dùng 6 Danh mục các hình vẽ, đồ thị Trang Hình 2.1.1.
- Tìm kiếm thông tin.
- Quá trình biểu diễn câu truy vấn.
- Quá trình biểu diễn tài liệu.
- Kiến trúc hệ tìm kiếm dựa trên từ khóa trong CSDLQH.
- 35 7 MỞ ĐẦU Để phát triển đất nước cần tăng cường cải cách nền hành chính Nhà nước một cách sâu rộng và toàn diện, trong đó, lấy qui trình quản lý chất lượng theo tiêu chuẩn ISO9001:2008 và ứng dụng công nghệ thông tin là hai công cụ mạnh để phục vụ công tác cải cách hành chính.
- Từ đó, đẩy mạnh ứng dụng công nghệ thông tin ở các cấp chính quyền tiến tới xây dựng Chính phủ điện tử đã trở thành một nhiệm vụ cấp thiết trong các cơ quan quản lý Nhà nước hiện nay.
- Quá trình đẩy mạnh ứng dụng công nghệ thông tin ở các cơ quan quản lý Nhà nước đã xuất hiện rất nhiều hệ thống thông tin phục vụ công tác quản lý với số lượng rất lớn các văn bản, tài liệu quản lý liên quan gắn kết với các ứng dụng quản lý được xây dựng dựa trên các hệ quản trị cơ sở dữ liệu quan hệ.
- Từ thực tế đó, tìm kiếm thông tin trong các trường dữ liệu text (dữ liệu dạng văn bản) trong cơ sở dữ liệu quan hệ (gọi là Tìm kiếm toàn văn – Full text search) là yêu cầu bức thiết mà các hệ thống thông tin quản lý cần phải có.
- Qua hoạt động thực tế trong công tác quản lý Nhà nước ở lĩnh vực “công nghệ thông tin – điện tử” tại Sở Thông tin và Truyền thông tỉnh Khánh Hòa tôi nhận thấy một số ứng dụng đã được xây dựng và triển khai nhưng chưa hỗ trợ tìm kiếm toàn văn trong cơ sở dữ liệu quan hệ, gây khó khăn cho người dùng trong công tác tìm kiếm thông tin, tra cứu văn bản.
- Vì vậy, khi bắt đầu theo học chương trình cao học công nghệ thông tin khóa CH2009B do trường Đại học Bách khoa Hà Nội tổ chức tại Đại học Nha Trang, tôi đã đăng ký thực hiện luận văn tốt nghiệp với đề tài “Kỹ thuật tìm kiếm dựa trên từ khóa trong cơ sở dữ liệu và ứng dụng” Do thời gian thực hiện luận văn có hạn nên bản thân không sao tránh khỏi những hạn chế, thiếu sót trong nội dung thực hiện, kính mong sự quan tâm chỉ bảo của quý Thầy giáo, Cô giáo và các bạn đồng nghiệp.
- Đặt vấn đề Trong những năm gần đây, cùng với sự phát triển nhanh chóng của các ứng dụng công nghệ thông tin, lượng dữ liệu lưu trữ trong các hệ thống máy tính ngày càng lớn và nhu cầu tra cứu, tìm kiếm thông tin lưu trữ trên máy tính ngày càng đa dạng.
- Các hệ quản trị cơ sở dữ liệu quan hệ (HQTCSDLQH) được xem là công cụ phổ biến để quản lý và truy vấn dữ liệu có cấu trúc một cách hiệu quả.
- Để phát biểu yêu cầu truy vấn, người dùng phải có hiểu biết đầy đủ về lược đồ CSDL cần truy vấn.
- Bộ xử lý truy vấn trong CSDL cho phép trả lại kết quả chính xác, đầy đủ (vét cạn), không có thứ tự (không phân biệt mức độ quan trọng của các bản ghi).
- Các kỹ thuật xử lý truy vấn được thiết kế hiệu quả với các kiểu dữ liệu cơ bản (text ngắn, số, ngày tháng.
- Hơn nữa, việc phát biểu điều kiện tìm kiếm trên một trường dữ liệu văn bản là khá khó khăn và thường không hiệu quả.
- Trong một cách tiếp cận khác, các hệ tìm kiếm thông tin (information retrieval systems) và các mô-tơ tìm kiếm trên web như Google, Yahoo.
- cho phép tìm kiếm hiệu quả trên dữ liệu phi cấu trúc là các văn bản, các tài liệu.
- Người dùng phát biểu yêu cầu truy vấn dưới dạng các từ khóa tìm kiếm, hệ thống thực hiện đối sánh từ khóa tìm kiếm với nội dung văn bản, tài liệu lưu trữ để trả về những tài liệu liên quan đến câu truy vấn và hiển thị kết quả được sắp xếp theo mức độ “liên quan” của tài liệu với câu truy vấn.
- Tích hợp các tính năng cơ bản của hệ tìm kiếm thông tin, một số HQTCSDLQH đã cho phép thực hiện tìm kiếm toàn văn trên các trường dữ liệu văn bản.
- Tuy nhiên người dùng vẫn phải có hiểu biết về lược đồ CSDL để phát biểu yêu cầu tìm kiếm toàn văn trên từng trường dữ liệu của lược đồ.
- Ví dụ về sử dụng câu truy vấn SQL (structured query language) thực hiện tìm kiếm toàn văn trong Microsoft SQL Server 2008 để hiển thị những quyển sách (book) mà nội dung của 9 nó (nằm trong trường dữ liệu text có tên là book_content) có chứa từ khóa ‘gift’ với ngôn ngữ thể nội dung là tiếng Anh như sau: SELECT * FROM dbo.Book b WHERE CONTAINS (b.Book_Content, 'gift', LANGUAGE 1033).
- Tích hợp cách tiếp cận tìm kiếm từ khóa trong các hệ tìm kiếm thông tin vào các HQTCSDLQH cho phép thao tác với các dữ liệu có cấu trúc và các dữ liệu văn bản một cách hiệu quả và thân thiện hơn.
- Người dùng có thể biểu diễn yêu cầu tìm kiếm dưới dạng chuỗi từ khóa tìm kiếm mà không cần biết tới tổ chức dữ liệu (lược đồ dữ liệu).
- Hệ thống sẽ tìm kiếm trong cơ sở dữ liệu quan hệ (CSDLQH) và đặc biệt trong các trường dữ liệu văn bản để trả về các bản ghi phù hợp với yêu cầu tìm kiếm theo một thứ tự xác định.
- Trên thực tế, các hệ thống thông tin được triển khai tại các cơ quan Nhà nước hiện nay đa phần dựa trên HQTCSDLQH mà phần lớn là dùng Microsoft SQL Server.
- Đặc điểm của hai ứng dụng này là chưa hỗ trợ tìm kiếm toàn văn.
- Một số ứng dụng khác, như “Phần mềm Kiểm tra Đảng” của Công ty CMC, đã hỗ trợ tìm kiếm toàn văn nhưng vẫn đòi hỏi người dùng biết thông tin về lược đồ CSDL để nhập nội dung cần tìm.
- Từ những phân tích và thực tế ứng dụng nêu trên, chúng ta cần xây dựng hệ tìm kiếm trong CSDLQH hỗ trợ người dùng tìm kiếm thuận tiện và dễ dàng như khi sử dụng hệ tìm kiếm thông tin, nghĩa là không yêu cầu người dùng phải biết thông tin về lược đồ CSDL.
- Người dùng tự do nhập các từ khóa cần tìm kiếm mà không cần quan tâm từ khóa đó sẽ phải tìm kiếm ở đâu, nghĩa là việc tìm kiếm chỉ cần “dựa trên từ khóa”.
- Trong tài liệu này, chúng ta thống nhất gọi kiểu tìm kiếm này là “tìm kiếm dựa trên từ khóa trong cơ sở dữ liệu quan hệ”.
- Mục đích và cách tiếp cận Mục đích của luận văn là tìm hiểu, triển khai các kỹ thuật về tìm kiếm thông tin, tìm kiếm từ khóa trong CSDLQH và ứng dụng các kỹ thuật liên quan trong hệ thống quản lý văn bản của các cơ quan quản lý Nhà nước ở tỉnh Khánh Hòa.
- Cách tiếp cận của luận văn là sử dụng HQTCSDLQH thương mại (như Microsoft SQL Server 2008) và xây dựng một phần mềm trung gian (middleware) để cung cấp khả năng tìm kiếm dựa trên từ khóa trong CSDLQH.
- Người dùng phát biểu câu truy vấn dưới dạng chuỗi từ khóa.
- Middleware nhận câu truy vấn và viết lại thành câu lệnh SQL, gửi đến HQTCSDLQH để thực thi và nhận kết quả truy vấn trả về từ HQTCSDLQH, thực hiện các xử lý trên kết quả trước khi trả về người dùng.
- Nhiệm vụ cụ thể Từ mục đích và cách tiếp cận nêu trên, luận văn có những nhiệm vụ sau: a) Tìm hiểu hệ tìm kiếm thông tin.
- b) Tìm hiểu hệ tìm kiếm toàn văn.
- c) Đề xuất kiến trúc hệ thống tìm kiếm dựa trên từ khóa trong CSDLQH dựa trên cách tiếp cận đã lựa chọn.
- Bố cục của luận văn Phần tiếp theo của luận văn gồm các nội dung: Chương 2 – Cơ sở lý thuyết hệ tìm kiếm.
- Chương này trình bày cơ sở lý thuyết về tìm kiếm dựa trên từ khóa cho các tài liệu và trong cơ sở dữ liệu quan hệ.
- Chương 3 – Kỹ thuật tìm kiếm dựa trên từ khóa trong cơ sở dữ liệu quan hệ.
- Trong chương này, chúng tôi trình bày kiến trúc hệ thống và các kỹ thuật để middleware thực hiện nhiệm vụ viết lại câu truy vấn của người dùng thành câu lệnh SQL, gửi câu lệnh SQL cho HQTCSDLQH thực hiện tìm kiếm, nhận kết quả tìm 11 kiếm trả về từ HQTCSDLQH, thực hiện xếp hạng kết quả và trả kết quả tìm kiếm về người dùng.
- 12 Chương 2 CƠ SỞ LÝ THUYẾT HỆ TÌM KIẾM Chương này trình bày cơ sở lý thuyết về tìm kiếm dựa trên từ khóa cho các tài liệu và trong cơ sở dữ liệu quan hệ.
- Hệ tìm kiếm thông tin Trong lĩnh vực công nghệ thông tin, tìm kiếm thông tin có thể là tìm kiếm tài liệu web, music, hình ảnh hay video… Tùy từng loại tài liệu tìm kiếm, chúng ta có thể sử dụng các kỹ thuật tìm kiếm liên quan đến xử lý tiếng nói, xử lý hình ảnh hay xử lý văn bản… Nội dung phần này chỉ tập trung vào tìm kiếm thông tin trên các tài liệu phi cấu trúc được hình thành từ các văn bản ngôn ngữ tự nhiên phi hình thức.
- Tìm kiếm thông tin Hình 2.1.1 trình bày bản chất của vấn đề tìm kiếm thông tin, trong đó có hai bên tham gia là người dùng và nhà cung cấp dịch vụ tìm kiếm.
- Nhà cung cấp dịch vụ tìm kiếm trước hết phải lưu trữ các thông tin về tài liệu.
- Số lượng tài liệu là rất lớn nên không thể lưu trữ toàn bộ nội dung của tài liệu mà chỉ có thể lưu lại những thông tin quan trọng để phục vụ tìm kiếm.
- Các thông tin này có thể là tiêu đề, đoạn tóm tắt, các đường link, hay thậm chí chỉ là một vài từ khóa.
- Để thực hiện tìm kiếm, người dùng đưa vào các từ khóa đặc trưng cho tài liệu cần tìm.
- Hệ thống sẽ thực hiện đối sánh các từ khóa này với các thông tin phục vụ tìm kiếm của tài liệu.
- Những tài liệu nào có kết quả đối sánh tốt nhất sẽ được trả về như là kết quả cho người tìm kiếm.
- Người tìm kiếm Các tác giả tài liệu Các nội dung Các nội dung Các từ truy vấn Các từ mô tả tài liệu Đối sánh Có biểu diễn cùng một nội dung ? 13 Như vậy, bản chất của tìm kiếm thông tin là dựa trên cơ chế “đối sánh” giữa các tài liệu lưu trữ trong hệ thống với yêu cầu tìm kiếm của người dùng để tìm ra các tài liệu phù hợp với người dùng.
- Mô hình hệ tìm kiếm thông tin Hình 2.1.2.
- Mô hình hệ tìm kiếm thông tin Hình 2.1.2 trình bày mô hình tổng quát của một hệ tìm kiếm thông tin, gồm các thành phần cơ bản như sau: a) Đầu vào Đầu vào gồm các câu truy vấn và tập các tài liệu.
- Câu truy vấn bao gồm các từ khóa (keywords).
- Từ khóa được hiểu như là một tổ hợp các từ của một ngôn ngữ nhất định được sắp xếp hay quan hệ với nhau thông qua các biểu thức logic mà công cụ tìm kiếm hỗ trợ.
- b) Đầu ra Đầu ra là tập hợp các đoạn trích hay tài liệu được hệ thống đánh giá là phù hợp với yêu cầu truy vấn của người dùng.
- Chỉ mục Câu truy vấn Tập các tài liệu Đầu vào Bộ xử lý Đầu ra Bộ Biểu diễn câu truy vấn Bộ Đối sánh Tập các tài liệu phù hợp Bộ Biểu diễn tài liệu.
- 14 c) Bộ xử lý Bộ xử lý có nhiệm vụ biểu diễn và lưu trữ các thông tin về các tài liệu lưu trữ trong hệ thống và thực hiện tìm kiếm.
- Bộ biểu diễn câu truy vấn: biểu diễn câu truy vấn của người dùng dưới dạng thích hợp để xử lý.
- Bộ biểu diễn tài liệu: biểu diễn các thông tin về tài liệu phục vụ tìm kiếm, dựa vào các thông tin biểu diễn tài liệu lập chỉ mục để dễ dàng thực hiện tìm kiếm.
- Bộ đối sánh: thực hiện chức năng đối sánh giữa câu truy vấn và thông tin tài liệu để xem xét tài liệu đó có phù hợp hay không.
- Hoạt động của bộ xử lý: Bộ biểu diễn tài liệu phân tích các tài liệu, đánh chỉ mục và lưu trữ vào kho dữ liệu.
- Khi nhận được một câu truy vấn, Bộ biểu diễn câu truy vấn sẽ phân tích câu truy vấn thành các từ khóa và các toán tử tìm kiếm.
- Bộ đối sánh sẽ lấy thông tin về các tài liệu trong kho dữ liệu, thực hiện đối sánh với các từ khóa và các toán tử tìm kiếm để tìm ra những tài liệu thỏa mãn câu truy vấn của người dùng.
- Ngoài ra, một hệ tìm kiếm thông tin còn có các bộ phận phục vụ các chức năng nâng cao khác như phân cụm, phân lớp… 2.1.2.
- Thành phần cơ bản của hệ tìm kiếm thông tin Như đã trình bày ở trên, các thành phần cơ bản của một hệ tìm kiếm thông tin bao gồm: Bộ biểu diễn câu truy vấn, Bộ biểu diễn tài liệu và Bộ đối sánh.
- a) Bộ biểu diễn câu truy vấn Một câu truy vấn được tạo thành từ các từ khóa và các toán tử tìm kiếm liên kết các từ khóa.
- Nhiệm vụ của bộ biểu diễn câu truy vấn là phân tích câu truy vấn thành các từ khóa và toán tử tìm kiếm.
- Các toán tử tìm kiếm cơ bản - Toán tử AND: Có cú pháp dạng (Toán hạng 1) AND (Toán hạng 2).
- Toán tử AND yêu cầu hệ thống tìm kiếm các tài liệu có sự hiện diện của tất cả toán hạng.
- Ví dụ: câu truy vấn nanotechology AND health sẽ giúp truy tìm các tài liệu có mặt đồng thời chữ health và chữ nanotechnology.
- Toán tử OR cho phép tìm những tài liệu có chứa một trong các toán hạng của toán tử OR.
- Toán tử NOT: Việc tìm kiếm sẽ loại bỏ những tài liệu mà nội dung có chứa toán hạng đứng ngay sau toán tử NOT.
- Trong nhiều hệ tìm kiếm thông tin có hỗ trợ toán tử NOT thì toán tử này chỉ được dùng một lần cho một bộ từ khoá.
- Ví dụ: để tìm tài liệu hướng dẫn về ngôn ngữ lập trình C/C++ có thể tra cứu trên Altavista với câu truy vấn "C/C++ tutor" NOT book.
- dùng dấu ngoặc kép để tìm nguyên văn của cụm từ, khi đó, Bộ đối sánh phải tìm kiếm các tài liệu có cả cụm từ ấy trong nội dung văn bản.
- Quá trình biểu diễn câu truy vấn Hình 2.1.3.
- Quá trình biểu diễn câu truy vấn Câu truy vấn Phân tích thành các token Phân tích thành các từ khóa và các toán tử tìm kiếm Loại bỏ các từ dừng, tiền tố, hậu tố, từ tương đương Đánh giá trọng số cho các từ khóa Tập các (từ khóa, trọng số) và các toán tử liên kết giữa chúng Java OR Programing Java OR Programing Java (từ khóa) OR (toán tử) Programing (từ khóa) Java (từ khóa) OR (toán tử) Program (từ khóa) Java (Trọng số w1) Program (Trọng số w2) (Java, w1) (từ khóa) OR (toán tử) (Program, w2) (từ khóa)

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt