Luận Văn Xây dựng mục lục cho văn bản

MỤC LỤC

LỜI CẢM ƠN i

LỜI CAM ĐOAN ii

MỤC LỤC iii

DANH MỤC CÁC KÍ HIỆU, CÁC CHỮ VIẾT TẮT . v

DANH MỤC CÁC BẢNG . vi

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ .vii

MỞ ĐẦU . 1

Chương 1. GIỚI THIỆU BÀI TOÁN . 3

1.1. Bài toán tóm tắt văn bản . 3

1.2. Bài toán xây dựng mục lục cho văn bản 5

1.3. Phương hướng giải quyết bài toán . 5

1.4. Các công trình liên quan 6

Chương 2. PHÂN ĐOẠN VĂN BẢN VÀ SINH TIÊU ĐỀ 8

2.1. Phân đoạn văn bản 8

2.2. Các phương pháp phân đoạn văn bản 9

2.2.1. Sử dụng mối liên kết từ vựng 9

2.2.2. Sử dụng mô hình nhát cắt cực tiểu 13

2.3. Sinh tiêu đề cho văn bản 17

2.4. Các phương pháp sinh tiêu đề cho văn bản 18

2.4.1. Phương pháp trích chọn cụm từ 18

2.4.2. Phương pháp hai pha . 19

2.5. Tóm tắt chương hai 20

Chương 3. XÂY DỰNG MỤC LỤC CHO VĂN BẢN 21

3.1. Mô hình tích hợp thuật toán . 21

3.2. Đảm bảo tính hợp lí của mục lục . 22

3.3. Các phương pháp đánh giá . 23

3.3.1. Đánh giá thuật toán phân đoạn 23

Độ đo Pk . 24

Độ đo WindowDiff . 26

3.3.2. Đánh giá thuật toán sinh tiêu đề 26

3.4. Tóm tắt chương ba . 27 iv

Chương 4. THỬ NGHIỆM VÀ ĐÁNH GIÁ 28

4.1. Môi trường thử nghiệm 28

4.2. Dữ liệu thử nghiệm . 29

4.3. Quá trình thử nghiệm . 32

4.4. Kết quả thử nghiệm 32

4.4.1. Kết quả phân đoạn văn bản . 32

4.4.2. Kết quả sinh tiêu đề . 33

4.5. Đánh giá thử nghiệm 34

4.5. Phương hướng cải tiến . 35

4.6. Tóm tắt chương bốn . 35

KẾT LUẬN . 37

TÀI LIỆU THAM KHẢO . 38



DANH MỤC CÁC BẢNG

Bảng 1. Ví dụ về độ tương tự giữa 2 khối văn bản . 11

Bảng 2. Danh sách các công cụ phần mềm sử dụng để thử nghiệm . 28

Bảng 3. Cấu trúc văn bản thử nghiệm . 29

Bảng 4. Danh sách từ dừng . 30

Bảng 5. Tập nhãn từ loại (tập mở) 30

Bảng 6. Tập nhãn từ loại (tập đóng) . 31

Bảng 7. Kết quả phân đoạn văn bản 32

Bảng 8. Sinh tiêu đề cho phân đoạn gốc . 33

Bảng 9. Sinh tiêu đề cho phân đoạn của C99 33

Bảng 10. Sinh tiêu đề cho phân đoạn của TextTiling . 34


DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ

Hình 1. Đồ thị dotplotting cho một văn bản . 13

Hình 2. Phân bố độ dài tiêu đề văn bản theo Reuters-1997 17

Hình 3. Ví dụ đánh giá thuật toán phân đoạn 24

Hình 4. Cách xác định tham số cho độ đo Pk 25

Hình 5. Kết quả phân đoạn văn bản 33



MỞ ĐẦU

Trong vài thập kỉ qua, lượng thông tin được số hoá ngày càng nhiều. Ban

đầu là các thư viện với các cuốn sách được lưu trữ số hoá, tiếp đến là các nội

dung thông tin được đưa lên Internet dưới nhiều hình thức khác nhau. Hơn thế

nữa, với sự ra đời của World Wide Web thì thông tin đã thực sự bùng nổ, con

người ngày càng muốn có nhiều thông tin hơn và muốn tìm cách để có thể nắm

bắt được thông tin nhanh, chính xác và cô đọng.

Rất nhiều bài toán trong xử lí ngôn ngữ tự nhiên đã được đặt ra và giải

quyết nhằm giúp máy tính có thể hiểu được phần nào các văn bản số hoá rồi từ

đó trình bày lại theo một hình thức nào đó để giúp con người tìm kiếm và thu

thập thông tin nhanh hơn. Các bài toán có thể kể đến như: thu nhận thông tin,

phân cụm văn bản, phân lớp văn bản, rút trích thông tin, hệ thống hỏi đáp, tóm

tắt văn bản, Những bài toán này đã phần nào được giải quyết và đã thể hiện

phần nào ý nghĩa đối với người sử dụng. Ví dụ như các hệ thống máy tìm kiếm

Yahoo!, Google, đã có thể giúp người dùng thu thập thông tin theo truy vấn,

trả lại trang thông tin và tóm tắt nội dung của trang thông tin để giúp con người

có thể nhanh chóng tìm ra được thông tin mình cần.

Bài toán tóm tắt văn bản ra đời với vai trò giúp người truy cập thông tin

có thể dễ dàng nắm bắt được những nội dung chính của văn bản ở một dạng cô

đọng hơn. Một ví dụ điển hình là tủ chứa các thẻ trình bày tóm tắt thông tin về

cuốn sách ở các thư viện, nó giúp người đọc có thể tìm kiếm nhanh tới cuốn

sách mình cần. Hay trong thời đại thông tin được số hoá hiện nay, ở đầu mỗi bài

báo hay một bài trình bày hoặc một bài viết dài về một vấn đề nào đó, người ta

thường đưa thêm vào một đoạn tóm tắt ngắn của toàn bộ nội dung. Tuy nhiên,

không phải lúc nào thông tin tóm tắt đó cũng có sẵn, một phần vì các tóm tắt đó

được thực hiện theo phương pháp thủ công và đôi khi không phải do chính tác

giả viết ra. Từ đó đặt ra vấn đề là làm sao để có thể tự động hoá quá trình tóm tắt

văn bản dựa trên nội dung sẵn có.

Trên thế giới đã có rất nhiều công trình nghiên cứu về vấn đề này và cũng

nghiên cứu cách thức tóm tắt theo nhiều hướng khác nhau, từ rút trích một đoạn

văn, rút trích một vài câu quan trọng cho tới rút trích các cụm từ có ý nghĩa; rồi

từ tóm tắt trên một văn bản tới tóm tắt trên phạm vi nhiều văn bản; Tuy nhiên

hầu hết các phương pháp hiện tại đều áp dụng cho các văn bản tương đối ngắn

như tin tức, bài hướng dẫn, bài trình bày, và không có tính chất định vị thông

tin. Đối với các văn bản cỡ lớn hơn như tài liệu nghiên cứu, sách, thì có rất ít 2

các công trình nghiên cứu. Trong số đó có một bài toán được quan tâm đặc biệt

trong thời gian gần đây, đó là bài toán xây dựng mục lục cho văn bản. Cơ sở của

bài toán này là bản thân mục lục của một tài liệu dài không những chứa một

lượng lớn thông tin về nội dung của văn bản mà còn có khả năng định vị thông

tin bên trong văn bản. Ngoài ra các tiêu đề nằm ở mục lục còn manh tính súc

tích cao.

Với thực tế như đã trình bày ở trên, luận văn tiến hành nghiên cứu và đề

xuất phương pháp xây dựng mục lục cho văn bản thông qua đề tài “Xây dựng

mục lục cho văn bản”. Mục tiêu của luận văn là nghiên cứu, giải quyết và đề

xuất phương pháp giải quyết bài toán xây dựng mục lục cho văn bản cỡ trung

bình và lớn thông qua các công trình nghiên cứu hiện tại trên thế giới. Cơ sở của

đề tài là các kết quả nghiên cứu đã được công bố trên thế giới về bài toán phân

đoạn văn bản và bài toán sinh tiêu đề cho văn bản. Luận văn cũng tiến hành thử

nghiệm trên một vài văn bản với sự đánh giá của các chuyên gia là các nhà ngôn

ngữ học để đánh giá về tính chính xác của kết quả đạt được. Các kết quả bước

đầu đạt được cho thấy hướng nghiên cứu của luận văn là có triển vọng và có khả

năng phát triển tiếp thành một bài toán tổng thể cỡ lớn hơn.

Ngoài phần mở đầu và kết luận, kết cấu của luận văn bao gồm 4 chương:

- Chương 1 “Giới thiệu bài toán” tóm tắt một số bài toán trong lĩnh vực

tóm tắt văn bản, phát biểu bài toán xây dựng mục cho văn bản, đồng

thời phần tích các công trình có liên quan và đưa ra phương hướng giải

quyết.

- Chương 2 “Các phương pháp giải quyết bài toán” trình bày các

phương pháp dùng trong quá trình xây dựng mục lục, phân tích điểm

mạnh và yếu của mỗi phương pháp.

- Chương 3 “Xây dựng mục lục cho văn bản” sẽ đi sâu vào việc tích

hợp các thuật toán để giải quyết bài toán chính của luận văn, đồng thời

đề xuất một số hướng cải tiến và cơ sở lí luận của các cải tiến đó.

- Chương 4 “Thử nghiệm và đánh giá” sẽ trình bày quá trình thử

nghiệm của luận văn và các kết quả đạt được trong quá trình thử

nghiệm. Đồng thời cũng đưa ra các phân tích và đánh giá về kết quả

đạt được.



3

Chương 1

GIỚI THIỆU BÀI TOÁN

1.1. Bài toán tóm tắt văn bản

Lượng thông tin trên Internet, trong các tài liệu và trong các cơ sở dữ liệu

đang không từng tăng lên dẫn đến nhu cầu tìm kiếm và biểu diễn thông tin hiệu

quả. Các hệ thống thu nhận thông tin (Information Retrieval) đã cho phép tìm

kiếm và sắp xếp thông tin nhận được theo mức độ liên quan đến câu hỏi truy vấn

của người dùng []. Gần đây, các hệ thu nhận thông tin còn đưa ra các đoạn tóm

tắt của thông tin trả về để giúp người dùng dễ dàng chọn lựa có xem thông tin đó

hay không, các đoạn tóm tắt này thường đưa ra các ý chính trong văn bản tương

ứng và một đoạn tóm tắt lí tưởng là đoạn tóm tắt đưa ra được tất cả các ý chính

của văn bản, đặc biệt là đưa ra được những ý mà người dùng mong muốn. Điều

này thực sự có ý nghĩa khi số lượng tài liệu có liên quan đến câu truy vấn là rất

lớn trong khi ta chỉ có đủ thời gian để xem những tài liệu liên quan nhiều đến

vấn đề cần tìm hiểu.

Bài toán tóm tắt văn bản đã có lịch sử từ lâu đời, ví dụ như công việc của

một người thư kí, có trách nhiệm tóm tắt lại những ý chính của tài liệu (tóm tắt

đơn văn bản) hoặc tổng hợp thông tin trên nhiều tài liệu (tóm tắt đa văn bản).

Hay trong các thư viện, người thủ thư phải đọc qua tài liệu để tóm tắt ý chính

hoặc đưa ra các từ khoá trên các thẻ bài để người đọc có thể tìm thấy tài liệu dễ

dàng. Trong thời kì thông tin được số hoá, bài toán tóm tắt văn bản số (sau đây

gọi chung là văn bản) được giải quyết lần đầu tiên trong bài báo của Luhn năm

1958. Trong bài báo này, Luhn giải quyết bài toán tạo ra một đoạn tóm tắt

(abstract) cho các tài liệu kĩ thuật. Những năm sau đó, bài toán được tiếp tục

phát triển với nhiều cải tiến mới