Đại Học Quốc Gia Thành Phố Hồ Chí Minh
Trường Đại Học Bách Khoa

BÙI QUỐC NAM

XÂY DỰNG CHƯƠNG TRÌNH
TĨM TẮT VĂN BẢN TIẾNG VIỆT
Chuyên ngành: Khoa học Máy tính

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, tháng 11 năm 2008


ĐẠI HỌC QUỐC GIA TP. HCM
TRƯỜNG ĐẠI HỌC BÁCH KHOA
----------------

CỘNG HOÀ XÃ HỘI CHỦ NGHIÃ VIỆT NAM
Độc Lập - Tự Do - Hạnh Phúc
---oOo---

Tp. HCM, ngày . 30. . tháng . .11. . năm .2008.

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ và tên học viên : Bùi Quốc Nam

Giới tính : Nam / Nữ 

Ngày, tháng, năm sinh : 18/04/1982

Nơi sinh : Đồng Tháp

Chun ngành : Khoa học Máy tính
Khố : 2005
1- TÊN ĐỀ TÀI :
Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt
2- NHIỆM VỤ LUẬN VĂN :
Nghiên cứu các phương pháp tóm tắt văn bản, từ đó quyết định hướng
nghiên cứu của luận văn.
Nghiên cứu các đặc tính ngơn ngữ tiếng việt.
Xây dựng chương trình tóm tắt văn bản tiếng việt dựa trên lưới ý niệm
(chú ý đến đặc tính tiếng việt).
3- NGÀY GIAO NHIỆM VỤ : 15/06/2008
4- NGÀY HOÀN THÀNH NHIỆM VỤ : 30/11/2008
5- HỌ VÀ TÊN CÁN BỘ HƯỚNG DẪN : PGS.TS Phan Thị Tươi
Nội dung và đề cương Luận văn thạc sĩ đã được Hội Đồng Chun Ngành thơng
qua.
CÁN BỘ HƯỚNG DẪN

CHỦ NHIỆM BỘ MƠN
QUẢN LÝ CHUYÊN NGÀNH

PGS.TS Phan Thị Tươi


CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH

Cán bộ hướng dẫn khoa học : PGS.TS Phan Thị Tươi


Cán bộ chấm nhận xét 1 : PGS.TS Đỗ Phúc

Cán bộ chấm nhận xét 2 : TS Nguyễn Đức Cường
Luận văn thạc sĩ được bảo vệ tại Trường Đại học Bách Khoa, ĐHQG Tp.HCM
ngày 19 tháng 02 năm 2009.
Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm:
1. PGS.TS Phan Thị Tươi
2. PGS.TS Cao Hoàng Trụ
3. PGS.TS Đỗ Phúc
4. TS Quản Thành Thơ
5. TS Nguyễn Đức Cường

Chủ tịch Hội đồng đánh giá LV

Bộ môn quản lý chuyên ngành


4

Lời cảm ơn
*****

Tôi xin gởi lời cảm ơn chân thành và sâu sắc nhất đến PGS.TS Phan Thị Tươi,
người Cô đã tận tình hướng dẫn tơi trong suốt q trình thực hiện luận văn và tạo
mọi điều kiện để tôi có thể hồn thành luận văn này.
Tơi cũng xin chân thành cảm ơn các thầy cô tại khoa Công nghệ Thông tin,
Trường ĐH Bách Khoa Tp.HCM, những người đã tận tình giảng dạy, hướng dẫn và
truyền đạt những kinh nghiệm thực tế, qua đó tạo ra trong tơi những kiến thức nền
tảng q báu để tơi có thể hồn thành luận văn này.

Tơi cũng xin cảm ơn gia đình và bạn bè đã động viên và tạo mọi điều kiện tốt
nhất để tơi có thể tiếp tục theo đuổi việc học tập nghiên cứu.
Tôi xin hứa sẽ tiếp tục cố gắng phấn đấu để vươn cao hơn nữa.

Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt


5

Tóm tắt

Trong thời đại ngày này, internet được xem là một nguồn thơng tin vơ cùng
rộng lớn và nó càng ngày càng mở rộng thêm. Đặc biệt trong công việc học tập và
nghiên cứu thì internet chính là nguồn tài liệu cập nhật và phù hợp nhất. Trong vô
số tài liệu có được từ nhiều nguồn khác nhau, người ta sẽ mất rất nhiều thời gian
nếu đọc toàn bộ nội dung của tài liệu đó rồi mới quyết định sử dụng nó hay khơng.
Khi đó, đọc bản tóm tắt (abstract) là cách nhanh nhất để nắm tổng quát nội dung của
tài liệu.
Vấn đề tự động tạo ra bản tóm tắt cho một tài liệu vẫn đang được tìm hiểu và
phát triển trên thế giới. Ngôn ngữ tự nhiên luôn chứa đựng nhiều hàm ý. Bản tóm
tắt hiệu quả phải mang nhiều nội dung cốt lõi của văn bản gốc, do đó việc tạo bản
tóm tắt khơng chỉ đơn thuần dựa trên tần suất xuất hiện của các từ trong văn bản mà
cịn phải tính đến mối quan hệ ý nghĩa giữa các từ với nhau. Hiện nay, việc xây
dựng chương trình tóm tắt văn bản tiếng việt bắt đầu được quan tâm và nghiên cứu
nhiều hơn. Luận văn này giới thiệu mơ hình tóm tắt văn bản tiếng việt dựa trên Lưới
ý niệm như là một phương pháp tóm tắt sử dụng trong tiếng việt, trong đó có giải
quyết mối quan hệ ngữ nghĩa giữa các từ và các câu với nhau. Mơ hình này xây
dựng tập các ý niệm và tạo ra mối quan hệ ngữ nghĩa giữa các câu thơng qua các ý
niệm trong câu, sau đó chạy giải thuật dựa trên lưới ý niệm để chọn ra các câu cho
bản tóm tắt. Kết quả thực nghiệm cho thấy mơ hình giới thiệu có hiệu quả tốt khi áp

dụng vào tiếng việt. Vì thế, mơ hình này có thể được xem là cơ sở cho các nghiên
cứu tiếp theo để tiếp tục hồn thiện việc tóm tắt văn bản trong tiếng việt.

Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt


6

Mục lục

trang
Danh mục hình .....................................................................................................8
Danh mục bảng ....................................................................................................9
CHƯƠNG 1: GIỚI THIỆU VẤN ĐỀ.................................................................10
1.1. Mục tiêu của đề tài ...............................................................................11
1.2. Đóng góp của đề tài..............................................................................12
CHƯƠNG 2: TỔNG QUAN CÁC CƠNG TRÌNH NGHIÊN CỨU LIÊN
QUAN ...........................................................................................13
2.1. Các cơng trình nghiên cứu ở nước ngồi. .............................................13
2.1.1. Phương pháp Tóm tắt Văn bản tiếng Trung Quốc dựa trên
phương thức “Xác định các vùng chủ đề”........................................13
2.1.2. Giải thuật học áp dụng cho việc rút trích cụm từ đặc trưng ............16
2.1.3. Sử dụng Lưới ý niệm của Tài liệu phục vụ cho việc tóm tắt ...........19
2.2. Các cơng trình nghiên cứu ở trong nước...............................................22
Phương pháp Rút trích và tóm tắt nội dung trang web tiếng việt. ........22
CHƯƠNG 3: CƠ SỞ LÝ THUYẾT ..................................................................26
3.1. Ngôn ngữ Tiếng Việt..............................................................................26
3.1.1. Hiện tượng đồng nghĩa. ................................................................26
3.1.2. Hệ thống từ loại tiếng Việt............................................................28
3.2. Phương pháp Xây dựng Lưới ý niệm.....................................................29

3.2.1. Nền tảng của vấn đề tóm tắt văn bản ............................................29
3.2.2. Định nghĩa ý niệm.........................................................................30
3.2.3. Lưới ý niệm...................................................................................33
3.3. Tóm tắt Văn bản dựa trên Lưới ý niệm..................................................37
3.3.1. Trọng số biểu diễn câu..................................................................37
3.3.2. Giải thuật tóm tắt văn bản dựa trên lưới ý niệm ...........................38
Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt


7
3.4. Phương pháp tiến hành thực nghiệm......................................................41
3.4.1. Phạm vi thực nghiệm ......................................................................41
3.4.2. Thực nghiệm ...................................................................................41
CHƯƠNG 4: MƠ HÌNH TĨM TẮT VĂN BẢN TIẾNG VIỆT DỰA
TRÊN ĐỒ THỊ Ý NIỆM...............................................................43
4.1. Mô hình đề xuất......................................................................................43
4.2. Hiện thực Giải thuật (với dữ liệu ở bảng 3.1). .......................................46
4.3. Giải thuật với dữ liệu Tiếng Việt ...........................................................49
4.4. Giải thuật với một số điều chỉnh. ...........................................................59
4.4.1. Điều chỉnh cơng thức tính trọng số.................................................59
4.4.2. Điều chỉnh giải thuật.......................................................................62
4.5. Đánh giá và bàn luận kết quả đạt được sau khi điều chỉnh....................64
CHƯƠNG 5: KẾT LUẬN ..................................................................................66
TÀI LIỆU THAM KHẢO...................................................................................69
Phụ lục A.............................................................................................................71

Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt


8


Danh mục hình

trang
Hình 2.1: các bước của giai đoạn dị tìm các vùng chủ đề............................ 14
Hình 2.2: quy trình của Giải thuật Học áp dụng cho việc rút trích
cụm từ đặc trưng........................................................................... 17
Hình 2.3: sơ đồ lọc các cụm từ dự tuyển ...................................................... 18
Hình 2.4: quy trình đánh điểm cho các cụm từ dự tuyển để hình
thành cụm từ đặc trưng................................................................. 19
Hình 2.5: tiến trình tóm tắt văn bản dựa trên lưới ý niệm ............................ 20
Hình 2.6: quy trình Rút trích và Tóm tắt văn bản tiếng Việt ........................ 23
Hình 3.1: các câu thí dụ từ hội thảo DUC 2005............................................ 31
Hình 3.2: lưới ý niệm được dẫn xuất ra từ các từ tồn tại trong các câu
ở hình 3.1 ...................................................................................... 34
Hình 4.1: mơ hình đề xuất cho phương pháp tóm tắt văn bản tiếng
việt dựa trên lưới ý niệm .............................................................. 44
Hình 4.2: Lưới ý niệm của bộ dữ liệu thứ nhất............................................. 51

Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt


9

Danh mục bảng

trang
Bảng 3.1: bảng phân nhóm các từ loại trong Tiếng Việt .............................. 29
Bảng 3.2: bảng các ý niệm của bộ dữ liệu gốc của phương pháp................. 33
Bảng 4.1: bảng các ý niệm của bộ dữ liệu tiếng việt thứ nhất ...................... 50

Bảng 4.2: Kết quả chạy chương trình trên mẫu dữ liệu Tiếng Việt
thứ nhất ......................................................................................... 51
Bảng 4.3: tập các ý niệm của mẫu dữ liệu Tiếng Việt thứ hai...................... 56
Bảng 4.4: kết quả chạy chương trình trên mẫu dữ liệu Tiếng Việt thứ
hai ................................................................................................. 57
Bảng 4.5: kết quả chạy thử nghiệm việc cải tiến cơng thức tính trọng
số trên bộ dữ liệu gốc của phương pháp....................................... 60
Bảng 4.6: kết quả chạy thử nghiệm việc cải tiến công thức tính trọng
số trên bộ dữ liệu Tiếng Việt thứ nhất.......................................... 60
Bảng 4.7: kết quả chạy thử nghiệm việc cải tiến cơng thức tính trọng
số trên bộ dữ liệu Tiếng Việt thứ hai............................................ 61
Bảng 4.8: kết quả chạy thử nghiệm việc cải tiến giải thuật trên bộ dữ
liệu tiếng việt thứ hai .................................................................... 63

Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt


10

Chương 1:
Giới thiệu vấn đề

Trong thời đại ngày nay, cùng với sự phát triển của cơng nghệ thơng tin thì
internet được xem là một kho tư liệu vô cùng lớn và phong phú. Đặc biệt trong các
lĩnh vực mà công nghệ thay đổi liên tục thì tài liệu điện tử trên mạng internet chính
là nguồn tài liệu cập nhật và phù hợp nhất cho việc tham khảo nghiên cứu. Tuy
nhiên, cũng chính do đặc điểm vơ cùng rộng lớn của kho dữ liệu internet nên sẽ rất
khó khăn trong việc xác định tính đúng đắn và phù hợp của tài liệu tương ứng với
vấn đề cần nghiên cứu. Với số lượng vô cùng lớn tài liệu, người nghiên cứu không
thể có đủ thời gian để đọc hết tài liệu rồi sau đó mới lọc lại những tài liệu phù hợp

với vấn đề.
Do đó, thơng thường thì người nghiên cứu sẽ đọc phần Abstract của những
tài liệu lấy từ internet, và thông qua nội dung của phần Abstract, người nghiên cứu
quyết định sẽ xem tiếp phần nội dung của tài liệu hay khơng. Qua đó có thể thấy nội
dung của phần Abstract rất quan trọng trong việc tác động đến mức độ quan tâm
của người đọc đối với tài liệu đó.
Đối với những người làm công tác lưu trữ tài liệu, đặc biệt là tài liệu điện tử,
với số lượng tài liệu rất lớn sẽ rất khó khăn cho họ trong việc tạo ra phần dữ liệu
tóm tắt từ văn bản gốc (đối với những văn bản chưa có phần Abstract).
Trên thế giới, vấn đề tóm tắt văn bản dù đã được quan tâm và nghiên cứu từ
năm 1958 (theo [9]) nhưng đến hiện nay nó vẫn cịn là vấn đề đang được quan tâm
thảo luận trong các cuộc hội thảo (chẳng hạn như hội thảo Document Understanding
Conference [16]). Điều này nói lên sự cần thiết của sự phát triển các giải thuật và
các chương trình tóm tắt văn bản.
Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt


11
Đã có nhiều phương pháp tóm tắt được giới thiệu tại các cuộc hội thảo
([1],[2],[3],[9],[11],[12],[16]). Đa phần các phương pháp đều thực hiện tóm tắt theo
cách thức: gom cụm các câu dựa trên một số đặc điểm chung nào đó, sau đó mỗi
cụm sẽ chọn ra một hoặc một số câu đại diện và đưa vào bản tóm tắt. Ngồi ra, một
số phương pháp ([2],[5]) thực hiện theo cách: rút trích ra các cụm từ đặc trưng, sau
đó sinh ra câu (abstract – ít khi dùng) hoặc rút ra câu (extract – thường hay dùng)
dựa trên tập các cụm từ đặc trưng.
Trong phạm vi của ngôn ngữ tiếng việt cùng với sự phát triển của thế giới, số
lượng các bài báo, bài viết sử dụng ngôn ngữ tiếng việt vô cùng lớn. Do đó, nhu
cầu về chương trình tóm tắt văn bản tiếng việt cũng rất lớn. Tuy nhiên, các giải
thuật phục vụ cho việc tóm tắt văn bản tiếng việt và các chương trình tự động tóm
tắt văn bản cịn rất ít. Đã có phương pháp tóm tắt văn bản tiếng việt ([9]) trình bày

trong tạp chí khoa học ([18]), phương pháp này dựa trên cách thức gom cụm các
câu. Nhược điểm của cách thức gom cụm các câu là trong mỗi cụm chỉ chọn ra một
câu trội cho bản tóm tắt, khi đó các câu khơng trội nhất trong cụm nhưng mang
nhiều ngữ nghĩa hơn các câu trội của cụm khác mà vẫn bị bỏ qua.
1.1. Mục tiêu của đề tài.
Chúng tôi quyết định chọn đề tài Xây dựng chương trình tóm tắt văn bản tiếng
việt với mong muốn tìm hiểu một số phương pháp tóm tắt văn bản, các khuynh
hướng tóm tắt văn bản đang được phát triển trên thế giới và đưa ra một mơ hình tóm
tắt văn bản phù hợp với tiếng việt. Mục tiêu của luận văn nhằm đánh giá hiệu quả
của việc ứng dụng lưới ý niệm vào tóm tắt văn bản tiếng việt. Xây dựng bộ từ điển
đồng nghĩa tiếng việt và giải quyết mối quan hệ ngữ nghĩa giữa các từ hoặc cụm từ
trong câu. Trên cơ sở các đặc thù riêng của ngôn ngữ tiếng việt, thực hiện một số
điều chỉnh sao cho mơ hình tóm tắt văn bản tiếng việt được phù hợp hơn và tốt hơn,
tạo tiền đề cho việc nghiên cứu và phát triển các phương pháp tóm tắt văn bản tiếng
việt sau này.

Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt


12
1.2. Đóng góp của đề tài:
Trong luận văn này, chúng tơi đã giới thiệu hướng tiếp cận mới, tóm tắt văn
bản dựa trên lưới ý niệm, từ đó giới thiệu mơ hình tóm tắt văn bản tiếng việt, khai
thác mối quan hệ ngữ nghĩa giữa các từ trong câu khi thực hiện tóm tắt. Thực
nghiệm đã cho thấy hiệu suất của mơ hình giới thiệu tương đối tốt. Các điều chỉnh
về cơng thức tính trọng số và giải thuật cũng đã được chứng minh qua thực nghiệm
và đã cho kết quả tốt hơn so với trước khi điều chỉnh, điều này cho thấy việc xem
xét các đặc thù của ngôn ngữ tiếng việt khi tính số từ trong câu là hồn tồn hợp lý.
Đối với việc tính mỗi cụm từ tiếng việt là một đơn vị trong cơng thức tính số từ
trong câu, thực nghiệm cho thấy các câu trong bảng tóm tắt tương tự như phương

pháp trước khi điều chỉnh, tuy nhiên trong một số trường hợp kết quả tóm tắt có độ
bao phủ ngữ nghĩa rộng hơn so với lúc đầu.
Qua việc khảo sát và phân tích về mặt lý thuyết, cũng như kết quả tương đối
tốt về mặt thực nghiệm, mơ hình tóm tắt văn bản tiếng việt dựa trên lưới ý niệm và
các điều chỉnh có thể tiếp tục được nghiên cứu và phát triển thêm.

Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt


13

Chương 2:
Tổng quan các cơng trình nghiên cứu liên quan

Trên thế giới, các phương pháp tự động tóm tắt văn bản truyền thống đã được
hình thành từ rất lâu. Tuy nhiên, việc tóm tắt văn bản ban đầu chỉ dựa vào tần suất
xuất hiện của các từ trong câu, xét về mặt ngữ nghĩa thì chúng khơng thể đạt được
như phương pháp thủ cơng. Gần đây, hiệu quả tóm tắt văn bản đã được nâng cao
hơn thông qua các cải tiến như: nhận dạng cụm từ, xét mối quan hệ ngữ nghĩa giữa
các từ trong câu,… được trình bày trong một số tạp chí và các cuộc hội thảo. Chúng
tơi xin giới thiệu một số phương pháp tiêu biểu được đưa ra cho các ngơn ngữ khác
nhau.

2.1.

Các cơng trình nghiên cứu ở nước ngồi.

Ngơn ngữ tự nhiên rất đa dạng, trong đó ngơn ngữ của mỗi quốc gia lại có đặc
thù riêng, vì vậy đa số các phương pháp tóm tắt giới thiệu cho một ngôn ngữ cụ thể.
Trong số các ngơn ngữ nước ngồi, tiếng trung quốc là ngơn ngữ gần gũi với tiếng

việt (về cú pháp, từ vựng, …), trong khi tiếng anh được xem là ngôn ngữ giao tiếp
quốc tế. Trong phạm vi đề tài này, chúng tơi xin được giới thiệu các phương pháp
tóm tắt dành cho tiếng trung quốc và tiếng anh.
2.1.1. Phương pháp tóm tắt văn bản tiếng Trung Quốc dựa trên phương
pháp “Xác định các vùng chủ đề”.[1]
(Chinese Text Summarization Based on Thematic Area Detection)

Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt


14
Ý tưởng chính của phương pháp:
Dị tìm các vùng chủ đề khác nhau trong văn bản. Sau đó, ở mỗi vùng chủ đề
sẽ chọn ra một câu làm đại diện. Cuối cùng, phương pháp tạo ra bảng tóm tắt từ các
câu đại diện được chọn.
Tóm lược phương pháp:
Phương pháp tóm tắt văn bản tiếng Trung Quốc dựa trên phương pháp “Xác
định các vùng chủ đề” gồm có ba giai đoạn chính:
 Dị tìm các vùng chủ đề (Thematic Area Detection).
 Chọn câu đại diện của từng vùng chủ đề (Selection of the Thematic
Representative Sentences).
 Tạo ra bảng tóm tắt từ các câu đại diện (The Creation of the summary).
 Dò tìm các vùng chủ đề:
Trong giai đoạn dị tìm các vùng chủ đề, đầu vào là văn bản gốc, sau khi trải
qua bốn bước sẽ cho ra các vùng chủ đề khác nhau (hình 2.1).
Văn bản gốc
Tách từ
Biểu diễn vector và Tính trọng số
của đoạn văn bản
Gom cụm các đoạn văn bản

Phân tích các cụm
Xác định các vùng chủ đề

Thơng tin về các vùng
chủ đề
Hình 2.1: Các bước của giai đoạn dị tìm các vùng chủ đề.
Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt


15
Như hình 2.1, chúng ta thấy bước đầu tiên là bước tách từ, tác giả đã sử dụng
phương pháp của [5] để sinh ra các từ.
Trong bước biểu diễn vector và tính trọng số của đoạn văn bản, tác giả đã sử
dụng công thức của [3]:
VPi = (WPi1, WPi2,…, WPiN)
WPij = log(1+TF(Tij))*log(M/Mj)
n

WP

ij

W(Pi) =

j 1

n

Ở bước gom cụm các đoạn văn bản và phân tích cụm, trên cở sở các vector của
đoạn văn bản, tác giả đã sử dụng giải thuật K-medoids của Kaufmann và

Rousseeuw [4] để gom các đoạn trong văn bản thành các cụm.
Giải thuật K-medoids:
Nhập: ma trận các paragraph vector và số bó K (từ 2 đến M).
Xuất: thơng tin của K bó đã được gom cụm.
Phương pháp:
1) Chọn ngẫu nhiên K paragraph vector đưa vào Medoid của các bó (medoid
cho biết các paragraph của bó).
2) Xét tất cả các paragraph vector, với mỗi paragraph vector thì gán nó vào
medoid gần nó nhất.
3) Tính khoảng cách Euclic của các paragraph vector đến medoid gần nó
nhất.
4) Chọn ngẫu nhiên 1 paragraph vector Y.
Nếu hoán đổi Y và X bất kỳ (X trong số các paragraph vector cịn lại) mà
có thể rút gọn được tổng khoảng cách Euclic thì thay đổi vị trí X và Y.
Quay về bước 2 cho đến khi không thể thay đổi được nữa.

Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt


16
Tuy nhiên, để lựa chọn thông số K cho giải thuật K-medoids phù hợp nhất với
văn bản, phải sử dụng hàm:
K

W ( P )
j

objf(K) =

j 1


K

Khi đó phương pháp sẽ chọn ra giá trị K nào có hàm objf(K) lớn nhất.
Sau khi gom cụm các đoạn văn bản xong thì sang bước cuối cùng xác định các
vùng chủ đề, trong đó bao gồm thơng tin về số vùng chủ đề và các đoạn văn bản có
trong mỗi vùng chủ đề đó.
 Chọn câu đại diện của từng vùng chủ đề:
Sau khi xác định được từng vùng chủ đề thì phương pháp sẽ chuyển qua giai
đoạn chọn câu đại diện của từng vùng chủ đề.
Nhiệm vụ chính của giai đoạn này là chọn ra câu tương đồng nhất về mặt ngữ
nghĩa với từng vùng chủ đề. Để làm việc này, tác giả đã đưa ra công thức biểu diễn
vector của từng câu: VSj = (WSj1, WSj2,…, WSjN), cho từng vùng:
VAj=(WAj1,WAj2,…,WAjN), và cơng thức tính khoảng cách giữa từng câu và từng
vùng:
N

Cos(VSj,VAk) =

 (WSjixWAki)
i 1

 N
  N

  WSji 2     WAki 2 
 i 1
  i1



Cuối cùng những câu nào gần vùng chủ đề nhất được chọn làm đại diện cho
vùng chủ đề đó.
 Ở giai đoạn cuối cùng, công việc đơn giản chỉ là lấy ra những câu đại diện
làm kết quả tóm tắt văn bản sau cùng.
2.1.2. Giải thuật học áp dụng cho việc rút trích cụm từ đặc trưng [2]
(LAKE system at DUC 2004).

Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt


17
Trong giải thuật này, các tác giả đã đưa ra ý tưởng: xem xét các đặc điểm của
ngôn ngữ (cụ thể xem xét các đặc điểm của ngôn ngữ tiếng Anh) để rút ra một danh
sách các cụm từ đặc trưng (Keyphrase) dự tuyển có tiềm năng tốt. Sau đó, sử dụng
cơ chế học máy (machine learning framework) để chọn ra các cụm từ đặc trưng
chính thức.
Ưu điểm của giải thuật này là làm tăng công dụng của việc xử lý ngôn ngữ
(chẳng hạn như nhận dạng được các thực thể có tên hoặc thực thể có nhiều từ).
Các tác giả đã đưa ra giải thuật học máy áp dụng cho việc rút trích cụm từ đặc
trưng.
Văn bản gốc

Tiền xử lý ngơn ngữ

Rút trích ra các cụm từ dự tuyển

Tính điểm cho các cụm từ dự
tuyển

Cụm từ đặc trưng

Hình 2.2: giải thuật học máy áp dụng cho việc rút trích cụm từ đặc trưng.
Ở giai đoạn tiền xử lý ngôn ngữ, giải thuật đã tiến hành các thao tác để chuẩn
bị dữ liệu phục vụ cho việc rút trích bao gồm:
o Tách từ (sử dụng phương pháp Tree tagger [6]).

Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt


18
o Nhận dạng cụm từ (sử dụng từ điển WordNet [7]).
o Nhận dạng thực thể tên (sử dụng phương pháp NERD [8]).
Ở giai đoạn rút trích cụm từ dự tuyển, văn bản được tiến hành lọc thông qua
các mẫu cú pháp được định nghĩa trước theo sơ đồ ở hình 2.3.
Các mẫu cú pháp
định nghĩa trước

Văn bản sau khi tiền xử lý
Lọc qua các mẫu cú pháp

Các cụm từ dự tuyển
Hình 2.3: sơ đồ lọc các cụm từ dự tuyển
Trước đây, khi lựa chọn những mẫu cú pháp để đặc tả các thực thể được định
nghĩa trước, người ta thường quan tâm đến từ đơn hoặc từ ghép (danh từ, thực thể
tên, tính từ + danh từ…). Ngày nay, người ta xem xét đến những mẫu dài hơn,
thông thường bao gồm cả động từ, như một cụm từ có danh từ + động từ + tính từ +
danh từ. Việc lựa chọn những mẫu để xem xét còn dựa vào cấu trúc của ngơn ngữ,
ví dụ cụm từ: ‘danh từ + tính từ’ là khơng có trong cú pháp của tiếng Anh, do đó sẽ
khơng được đưa vào để xem xét.
Các tác giả đã đưa ra ba loại mẫu lọc khác nhau:
o Loại khơng có động từ có 121 mẫu.

o Loại một số ít mẫu có động từ có 223 mẫu.
o Loại có động từ, trạng từ và giới từ có 654 mẫu.
Từ các từ và cụm từ đã được tách sẽ được đưa vào bộ mẫu lọc để lọc ra cụm
từ dự tuyển.
Trong giai đoạn tính điểm cho các cụm từ dự tuyển, tác giả thực hiện việc tính
điểm dựa vào lập luận: các từ chủ đạo (head) của cụm từ thường xuất hiện nhiều lần
trong văn bản và xuất hiện trước các từ khơng chủ đạo. Do đó, tác giả đã đưa ra quy
trình tính điểm dựa trên hai đặc điểm:

Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt


19
o Tần suất xuất hiện (số lần từ chủ đạo xuất hiện trong văn bản).
o Xuất hiện đầu tiên (thứ tự xuất hiện của cụm từ đang xét so với các cụm
từ khác trong văn bản).
Cụm từ dự tuyển

Tìm từ chủ đạo trong cụm từ dự tuyển

Tính điểm dựa trên hai đặc điểm của
từ chủ đạo

Cụm từ đặc trưng
Hình 2.4: quy trình tính điểm cho các cụm từ dự tuyển để hình thành cụm từ đặc
trưng
Người ta chỉ tính điểm đối với từ chủ đạo của mỗi cụm từ chứ khơng phải cả
cụm từ bởi vì cả cụm từ ít khi lặp lại trong văn bản, còn từ chủ đạo có thể lặp lại
nhiều lần.
Sau khi tính điểm cho các từ chủ đạo xong thì điểm của mỗi từ chủ đạo sẽ

được gán lại cho các cụm từ tương ứng. Sau đó chọn ra những cụm từ có điểm cao
nhất làm cụm từ đặc trưng.

2.1.3.

Sử dụng Lưới ý niệm của Tài liệu phục vụ cho việc tóm tắt [12]

(Document Concept Lattice for Summarization)
Ý tưởng của phương pháp là:
Trên cơ sở đã biết các từ và cụm từ trong câu, tiến hành xây dựng Lưới ý
niệm.
Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt


20
Sau đó, dựa trên Lưới ý niệm, phương pháp này lựa chọn ra 1 tập con các câu
để biểu diễn cho tồn bộ văn bản, trong đó có sử dụng kỹ thuật sắp xếp và gom cụm
các câu.
Ngoài ra, phương pháp này cũng dựa trên lập luận của mơ hình Katz’s G [13]
rằng các câu được lựa chọn để tóm tắt phải đảm bảo được hai thuộc tính: tính lặp
(có nghĩa là ý niệm hay nội dung nào đó được nhắc đến thường xuyên trong văn
bản) và tính đa dạng (có nghĩa là độ bao phủ của ý niệm).
Tiến trình tóm tắt văn bản dựa trên Lưới ý niệm được thể hiện ở hình 2.5.
Tài liệu gốc
Tách từ, nhận dạng cụm từ và từ loại

Tập các câu (dưới dạng từ và cụm từ)

Nhận dạng các ý niệm


Tập các câu (dưới dạng các ý niệm)

Xây dựng lưới các ý niệm

Lưới ý niệm

Áp dụng giải thuật tóm tắt văn bản

Bản tóm tắt
Hình 2.5: tiến trình tóm tắt văn bản dựa trên lưới ý niệm

Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt


21
Trong phương pháp này, giai đoạn Tách từ, nhận dạng từ loại và cụm từ cũng
tương tự như các phương pháp khác.
Giai đoạn Nhận dạng ý niệm, các từ loại thuộc lớp mở (danh từ, động từ, tính
từ, trạng từ,…) được xem là ý niệm. Các từ loại thuộc lớp đóng (giới từ, liên từ,…)
sẽ bị bỏ đi.
Sau khi đã nhận dạng được các ý niệm, phương pháp tiến hành xây dựng lưới
ý niệm dựa trên hai bước:
a) Mỗi câu được gán cho một nút nền.
b) Hai nút có chứa một vài ý niệm giống nhau sẽ được giao lại thành một nút
cấp cao hơn (chứa các ý niệm giao nhau).
Sau khi đã có Lưới ý niệm, phương pháp tiến hành tóm tắt tài liệu qua hai giai
đoạn:
Tính độ quan trọng và trọng số cho từng câu bằng hàm Sig (Significance),
dùng cơng thức:
Sig(s) = ∑{Freq(c) log(N/dfc)}

Trong đó,
Freq(c): là số lần xuất hiện của ý niệm c trong câu s.
N: là tổng số câu.
dfc: là số câu có chứa ý niệm c.
Tính trọng số biểu diễn của câu s:
RP(s) = Sig(s)/word_num(s)
Trong đó word_num(s) là số tổng số từ trong câu s.
Sau khi các câu đã được tính trọng số sẽ tiến hành giải thuật tóm tắt văn bản:
Giải thuật tóm tắt văn bản
Input: DCL, n0,nstep
Output: summary sum
1: sort all derived nút by their significance
2: for i  n0, |DCL| step nstep do
3:
  { top i núts in DCL}
4:
  {M|M  , M has no successor in }
5:
summary  

Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt


22
6:
7:
8:
9:
10:
11:

12:
13:

repeated
add sentence with maximal RP whose base nút Ncur is covered by
any nút in  into sum
remove all núts in  that cover Ncur
until sum’s length is OK or  = 
if sum’s length is OK then
return sum
end if
end for
Với n0 là số nút cơ bản ít nhất (mà chương trình sẽ bắt đầu tìm thử) được gán

vào.
Nstep là số nút tăng thêm ở mỗi lần dò (nếu lần dò trước với n0 nút bị thất
bại).

2.2. Các cơng trình nghiên cứu ở trong nước.
Hiện nay, nhu cầu về các chương trình tóm tắt văn bản tiếng việt ngày càng
lớn, các cơng trình trong nước liên quan đến tóm tắt tiếng việt này đã bắt đầu được
quan tâm và phát triển nhiều hơn. Tuy nhiên, số lượng phương pháp tóm tắt cho văn
bản tiếng việt được giới thiệu vẫn còn rất hạn chế, vì thế trong phạm vi của luận văn
này, chúng tôi xin được giới thiệu một phương pháp đã được đăng trên tạp chí khoa
học và cơng nghệ [18].
Phương pháp Rút trích và tóm tắt nội dung trang web tiếng việt: [9]
Trong phương pháp này, cả quy trình Rút trích và tóm tắt văn bản được thể
hiện ở hình 2.6

Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt



23

Văn bản gốc

Tiền xử lý

Tài liệu sau khi tách câu

Biểu diễn câu vào không gian

Các câu ở dạng không gian vector

Gom cụm các câu

Cụm các câu

Rút câu trội

Tập các câu trội

Bổ sung tham số ưu tiên

Tập các câu trội sau khi bổ sung
tham số ưu tiên
Hình 2.6: quy trình Rút trích và Tóm tắt văn bản tiếng Việt

Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt



24
Trong môđun tiền xử lý, văn bản được tiến hành xử lý qua các bước cơ bản:
loại bỏ các phần không cần thiết, tách đoạn, tách câu.
Qua môđun tiền xử lý, các câu được biểu diễn vào không gian vector dựa trên
hàm:

tfi , j

 tf

wi,j =

i, j

2

j

tfi,j: tần số xuất hiện của mục từ i trong câu j.
Sau đó các câu trong văn bản sẽ được gom thành các cụm câu dựa vào độ
tương tự giữa từng cặp câu thông qua cơng thức tính độ tương tự giữa hai câu trong
công thức và giải thuật sau:


Sim(Si,Sk) =

t
j 1


w ij .w kj

 w  . w 
t

j 1

i 2
j

t

j 1

k 2
j

Giải thuật gom cụm các câu:
Bước 1: Gán cho mỗi câu là 1 cụm. Xác định độ tương tự giữa từng cặp cụm
{Si} và {Sk} bằng giá trị độ tương tự là Sim(Si,Sk)
Bước 2: Tìm cặp cụm gần nhất (có giá trị độ tương tự cao nhất) và trộn thành
một cụm, do đó giảm bớt một cụm.
Bước 3: Tính độ tương tự giữa cụm mới với mỗi cụm cũ.
Bước 4: Lặp lại bước 2 và 3 cho đến khi tất cả cụm được trộn lại thành một
cụm, hoặc giá trị độ tương tự của cặp tương tự nhất phải nhỏ hơn
ngưỡng α cho trước (0<=α<=1).
Ở môđun rút câu trội, các tác giả đã dùng cơng thức tính hàm trội f(Si) của
từng câu trong cụm như sau:
f(Si) = R1[Si] x


R 2[ Si ]

Trong đó Rx[Si] là thứ tự ưu tiên của câu Si theo x.
Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt


25
Ngoài ra, theo tác giả Loxeva (1980) trong [10] và theo chứng minh của Zhang
[11] thì đa số câu mở đầu đoạn văn bản là câu có thể cho nội dung cơ bản của cả
đoạn. Do vậy, các tác giả đã bổ sung thêm tham số ưu tiên câu mở đầu đoạn văn
bản bằng công thức:
f1(Si) = (1+a(fmax-favg))f(Si) nếu là câu mở đầu đoạn văn bản và f(Si)≥favg
Ngược lại f1(Si)=f(Si)
Với a là hệ số điều chỉnh ưu tiên câu mở đầu đoạn văn bản và 0 ≤ a ≤ 1.

Đề tài: Xây dựng chương trình Tóm tắt Văn bản Tiếng Việt