Đồ án Xây dựng hệ thống Tóm tắt văn bản tiếng Việt sử dụng các kỹ thuật lượng giá, thống kê

t vector gồm n thuật ngữ T = {t1, t2,…, tn}. Gọi W = {wij}là ma trận trọng số, trong đó wij là giá trị trọng số của thuật ngữ ti trong văn bản dj. 1 nếu ti có mặt trong dj wij = 0 nếu ngược lại 3.1.2 Mô hình tần suất TF Các giá trị wij được tính dựa trên tần số xuất hiện của thuật ngữ trong văn bản. Gọi fij là số lần xuất hiện của thuật ngữ ti trong văn bản dj, khi đó wij được tính bởi một trong các công thức : wij = fij wij = 1 + log(fij) wij = Trọng số wij tỷ lệ thuận với số lần xuất hiện của thuật ngữ ti trong văn bản dj. Khi số lần xuất hiện thuật ngữ ti trong văn bản dj càng lớn thì điều đó có nghĩa là văn bản dj càng phụ thuộc vào thuật ngữ ti, thuật ngữ ti mang nhiều thông tin trong văn bản dj. 3.1.3 Mô hình nghịch đảo tần số văn bản – IDF Giá trị wij được tính như sau: log m/hi = log(m) – log(hi) nếu thuật ngữ ti xuất hiện trong tài liệu dj wij = 0 nếu ngược lại. Trong đó m là số lượng văn bản và hi là số văn bản mà thuật ngữ ti xuất hiện. Như vậy với trọng số wij tỷ lệ nghịch với hi. Càng có ít văn bản có chứa ti thì wij càng cao. Trọng số wij có ý nghĩa phân biệt với các văn bản khác. 3.1.4 Mô hình kết hợp TF-IDF Mô hình này là sự kết hợp của 2 mô hình trên, giá trị của ma trận trọng số được tính như sau: [1+log(fij)]log (m/hi) nếu hij ≥ 1 wij = 0 nếu ngược lại. Với mô hình TF-IDF, trọng số wij có ý nghĩa kết hợp sự quan trọng của ti trong văn bản dj với giá trị phân biệt bởi ti giữa văn bản d với các văn bản khác. 3.1.5 Mô hình véc tơ thưa Trọng số wij được tính bằng tần số xuất hiện của thuật ngữ ti trong văn bản dj và độ hiếm của thuật ngữ ti trong toàn bộ cơ sở dữ liệu. Trong mô hình biểu diễn trên thì việc tính toán sẽ trở nên rất phức tạp và cồng kềnh. Lý do là các văn bản thường có nhiều thuật ngữ và do vậy các vector sẽ có số chiều rất lớn. Hiển nhiêu, lưu trữ các vector cũng tốn rất nhiều bộ nhớ. Khắc phục điều đó, người ta dùng mô hình biểu diễn bằng vector thưa. Điểm cơ bản của mô hình này là thay vì biểu diễn toàn bộ thuật ngữ có trong từ điển thì chúng ta đi biểu diễn chỉ các thuật ngữ có trong hệ cơ sở dữ liệu. Tuy vậy khi sử dụng mô hình véc tơ thưa đặc biệt phải lưu ý tính chính xác của lời giải khi đã loại bỏ bớt thông tin. 3.1.6 Các công thức tính toán trên mô hình không gian véc tơ Đặc điểm quan trọng nhất của biểu diễn văn bản theo không gian véc tơ là có thể tính toán, cộng trừ hai văn bản dựa trên tính toán hai véc tơ biểu diễn của chúng. Qua đó, dữ liệu văn bản trừu tượng có thể được lượng giá một cách chính xác. Các công thức quan trọng cho biểu diễn văn bản theo mô hình không gian véc tơ: *) Độ tương tự giữa hai véc tơ Giả sử hai văn bản X, Y được biểu diễn dưới dạng mô hình tần suất bằng hai véc tơ {x1, x2, …, xn} và {y1, y2, …, yn}. Khi đó, độ tương tự giữa hai văn bản được tính theo công thức Cosin: *) Véc tơ trọng tâm của nhóm Giả sử có một nhóm văn bản D = {d1, d2, …, dm} có lần lượt các véc tơ biểu diễn là v1, v2, …, vn. Khi đó, véc tơ trọng tâm của nhóm văn bản được tính theo công thức: *) Độ tương tự giữa hai nhóm Giả sử có hai nhóm văn bản D1,D2. Khi đó, độ tương tự giữa hai nhóm được tính theo bằng độ tương tự giữa hai véc tơ trọng tâm của nhóm: Sim(D1,D2) = Sim(Vcent1,Vcent2) CHƯƠNG IV THIẾT KẾ VÀ XÂY DỰNG HỆ THỐNG Các chương trước trình bày tổng quan và cơ sở lý thuyết của bài toán TTVB. Trong chương này, xin trình bày về việc thiết kế xây dựng một hệ thống cụ thể thực hiện TTVB tiếng Việt. Mục tiêu xây dựng hệ thống: - Hoạt động trên văn bản bằng ngôn ngữ tiếng Việt. - Tóm tắt đơn lẻ một văn bản (Single Document Summarization). Văn bản có độ dài vừa phải (30 - 50 câu), có hoặc không có tiêu đề. - Có khả năng thực hiện tính toán đối với tập văn bản vào lớn. 4.1 Mô hình hệ thống Hệ thống TTVB được xây dựng áp dụng các kỹ thuật lượng giá và thống kê đã trình bày trong chương II. Để có thể đánh giá kết quả dựa trên độ phức tạp của giải thuật, tác giả thực hiện cả 3 phương án đã giới thiệu đối với hệ thống: Giải thuật tóm tắt dựa vào trọng số các câu. Giải thuật tóm tắt dựa vào phân nhóm các đoạn văn. Giải thuật tóm tắt có áp dụng thuật toán học máy trên các đặc trưng đơn giản. Mô hình hệ thống như sau: Hình 19: Mô hình hệ thống 4.2 Module xử lý văn bản 4.2.1 Nhiệm vụ Đây là bước xử lý thô dữ liệu, chuẩn hoá dữ liệu văn bản sang dạng dữ liệu mong muốn. Như vậy: Đầu vào: Văn bản/tập văn bản ở dạng text file, được lưu dưới dạng chuẩn Unicode (UNI16_LE). Đầu ra: Dạng dữ liệu của văn bản được tổ chức có cấu trúc. Mỗi văn bản được biểu diễn thành một danh sách kề các đoạn văn. Mỗi đoạn văn được biểu diễn thành một danh sách kề các câu. Mỗi câu được biểu diễn thành một danh sách kề các thuật ngữ xuất hiện trong câu cùng với tần suất của chúng. 4.2.2 Mô hình chức năng Sơ đồ chức năng của module được thể hiện như sau: Hình 20: Module Tiền xử lý 4.3.2 Thực hiện Các bước tiền xử lý văn bản được thực hiện như sau: 4.3.2.1 Chuẩn hoá văn bản Đầu vào: Văn bản ở dạng thô (có thể được lấy về từ nhiều nguồn thông tin như báo điện tử, sách,..) với định dạng Unicode Đầu ra: Văn bản ở dạng chuẩn chỉ gồm các ký tự tiếng Việt, các dấu chấm (“.”), dấu cách (“ ”) và ký tự xuống dòng. Thực hiện: Văn bản đầu ra phải có dạng gồm các chuỗi được ngăn cách bởi dấu xuống dòng. Mỗi chuỗi gồm các xâu con được ngăn bởi dấu chấm. Cách tiến hành như sau: + Đọc văn bản, với mỗi ký tự không phải là ký tự tiếng Việt hoặc dấu chấm, dấu cách thì xoá bỏ chúng. + Duyệt mỗi ký tự với các ký tự liền kề nó: Nếu chúng là một chuỗi dấu cách thì xoá đi và thay bằng một dấu cách. Nếu một dấu chấm đi cạnh một dấu cách thì xoá bỏ dấu cách đó. Nếu chúng là một chuỗi dấu chấm (mang ý nghĩa liệt kê, ví dụ: “bàn, ghế, tủ, …” thì tuỳ thuộc vào ký tự sau chuỗi dấu chấm này là ký tự hoa hay thường để thay chuỗi bằng một dấu chấm hoặc một dấu cách. + Lập một bảng gồm tất cả các ký tự tiếng Việt bằng chữ hoa (103 phần tử) và một bảng khác gồm tất cả các ký tự tiếng Việt bằng chữ thường tương ứng. Khi thực hiện, so sánh các ký tự đọc được trong văn bản với bảng chữ hoa để chuyển về dạng ký tự thường. 4.3.2.2 Tách thuật ngữ Đầu vào: Văn bản ở dạng chuẩn. Đầu ra: Văn bản ở dạng số hoá bao gồm các dãy ID của thuật ngữ trong văn bản. Mỗi dãy là một danh sách kề các ID này biểu diễn cho một câu. Thực hiện: Sử dụng thuật toán tách thuật ngữ số 1 - thuật toán tách thuật ngữ cho thuật ngữ có độ dài lớn nhất (trình bày trong 3.1). Phương pháp này có thể có sai số (thiếu thuật ngữ) nhưng có ưu điểm thực hiện nhanh, không tạo thuật ngữ lồng nhau và không cần dựa vào từ điển đồng nghĩa. a. Tổ chức từ điển: Từ điển thuật ngữ tiếng Việt mà hệ thống sử dụng có 70.266 thuật ngữ. Từ điển được hệ thống đọc vào thông qua một file văn bản lưu dưới dạng Unicode, mỗi thuật ngữ nằm trên một dòng. Tổ chức từ điển là phần quan trọng nhất đối với module Tiền xử lý. Với kích thước số thuật ngữ lớn như vậy, tổ chức từ điển quyết định tốc độ của chức năng tách thuật ngữ. Việc tổ chức từ điển bao gồm 2 vấn đề: lưu trữ bản ghi và tổ chức cấu trúc tìm kiếm. Về lưu trữ, có thể lưu trữ mỗi thuật ngữ theo một trong hai cách: - Lưu dưới dạng một xâu có độ dài n ký tự. Như vậy mỗi thuật ngữ được lưu trữ sẽ chiếm n*2 byte. - Lưu dưới dạng mã hoá các tiếng (đã trình bày trong chương trước): mỗi từ trong thuật ngữ được lưu bằng 3 byte (trong đó chỉ sử dụng 17 bit). Như vậy một thuật ngữ có độ dài m tiếng sẽ chiếm m*3 byte. Qua khảo sát, với phương pháp lưu trữ thứ nhất, hệ thống đọc và lưu các thuật ngữ với thời gian không đáng kể. Bộ nhớ phải sử dụng là hơn 1900K, chấp nhận được. Với phương pháp thứ hai, bộ nhớ phải sử dụng giảm đi còn 700K xong thời gian thực hiện tăng lên do các hàm thực hiện mã hoá và giải mã phải thực hiện nhiều phép so sánh. Như vậy phương pháp thứ nhất hỗ trợ tìm kiếm nhanh trong khi phương pháp thứ hai hỗ trợ tốt cho công tác lưu trữ. Do đặc điểm của hệ thống tác giả quyết định sử dụng phương pháp thứ hai bởi tính đơn giản và tốc độ, đồng thời bộ nhớ cần thiết 1900K là chấp nhận được. Về tổ chức tìm kiếm, cách tổ chức thông dụng nhất là cây tìm kiếm nhị phân. Theo đó, mỗi một lần tìm kiếm thuật ngữ cần so sánh với các mốc nhị phân trong từ điển. Như vậy, mỗi một lần tìm kiếm một thuật ngữ phải thực hiện log2(70.266) = 16 lần so sánh. Đây là con số nhỏ. Phương pháp này dễ sử dụng nhất xong có nhược điểm là danh mục thuật ngữ cần phải được sắp xếp theo thứ tự so sánh. Danh sách các thuật ngữ đọc vào đã được sắp xếp theo thứ tự từ điển đối với con người, xong không phải đối với máy. Cụ thể trong ví dụ sau, xét một danh sách các thuật ngữ đã sắp xếp từ điển: tây ba lô tây bắc tay bài tẩy bỏ tay búp măng tay cầm tay cày tay súng tay chân tẩy chay Hình 21: Một đoạn các thuật ngữ trong từ điển Các ký tự “a”,”â”,”ẩ” đều được coi là ký tự “a” và không được sắp xếp trước - sau. Thế nhưng khi lưu trữ trong máy, chúng là các ký tự có mã khác nhau. Bởi vậy nếu muốn áp dụng phương pháp tìm kiếm nhị phân thì buộc phải sắp xếp lại các thuật ngữ khi chúng được nhập vào. Điều này là phi thực tế đối với mọi phương pháp sắp xếp cho 70.266 thuật ngữ. Do vậy, tác giả sử dụng phương pháp tổ chức tìm kiếm theo bảng băm cho hệ thống. Đối với phương pháp sử dụng bảng băm, tính chất của hàm băm quyết định hiệu quả của bảng. Có rất nhiều cách xây dựng hàm băm, chủ yếu nhằm giảm bớt xung đột cho các phần tử trong bảng. Để áp dụng cho hệ thống, tác giả sử dụng phương pháp băm kép (Double Hashing Method) với việc sử dụng hai hàm băm để tìm vị trí của phần tử trên bảng. Bảng băm được xây dựng như sau: Bước 1: Ban đầu, bảng băm được khởi tạo là một danh sách kề có M nút. Mỗi nút của bảng băm sẽ có một trường chứa thuật ngữ (sẽ được sử dụng như là khoá của phần tử dữ liệu). Trường này được đặt giá trị NULL. Bước 2: Với mỗi thuật ngữ nhập vào có khoá K chính là xâu chứa thuật ngữ đó, dùng hai hàm băm để tính f(K) = i và g(K) = j. i,j là số nguyên và i,j<M. + Xét địa chỉ i trong danh sách, nếu trống (khoá của nó là NULL) chèn thuật ngữ vào vị trí này. + Nếu không phải, xét tiếp địa chỉ (i+j) mod M. Nếu trống, chèn thuật ngữ vào vị trí này. Nếu không lại xét tiếp địa chỉ (i+2j) mod M…. tiếp tục cho đến khi tìm được vị trí trống. Mỗi khi tìm kiếm một thuật ngữ, quá trình tìm kiếm cũng thực hiện tương tự. Giả sử thuật ngữ có khoá K’, dùng hai hàm băm f và g để tính i’ = f(K’) và j’ = g(K’). Xét địa chỉ i’ trong danh sách, nếu i’ không rỗng tiến hành so sánh K và K’. Nếu chúng bằng nhau => tìm được thuật ngữ. Nếu không lại xét tiếp địa chỉ (i+j) mod M, (i+2j) mod M, …. Nếu một vị trí nào đó trống => không có thuật ngữ này trong từ điển. Hệ thống sử dụng hai hàm băm đã được tác giả Phan Thanh Liêm[2] trình bày trước đây: Hàm f: Giả sử khoá K là một chuỗi các ký tự K = [c1,c2,..,cn] Hàm g: Trong đó code(c) là mã của ký tự c trong bảng mã Unicode. b. Tách thuật ngữ. Các bước tách thuật ngữ từ văn bản gốc được thực hiện như sau: Bước 1: Rút một câu từ văn bản ở dạng chuẩn. Một câu là một xâu các ký tự và kết thúc bằng dấu chấm. Khởi tạo một danh sách kề lưu ID các thuật ngữ trong câu. Danh sách này ban đầu rỗng. Bước 2: Tách lấy một chuỗi chứa nhiều nhất các từ đơn đồng thời có độ dài nhỏ hơn độ dài của thuật ngữ dài nhất trong từ điển. Nếu chuỗi thu được rỗng, kết thúc. Nếu không, sang bước 3. Bước 3: Tìm kiếm xem chuỗi đó đó có phải là thuật ngữ trong từ điển không. Nếu đúng, tách chuỗi này khỏi xâu và lấy ID của chuỗi này (chính là vị trí của thuật ngữ tìm được trong bảng băm) thêm vào danh sách kề. Nếu không sang bước 4. Bước 4: Rút ngắn chuỗi trong bước 2 đi một từ cuối cùng. Nếu chuỗi khác rỗng thực hiện lại bước 3. Nếu chuỗi rỗng, cắt bỏ đi từ đầu của xâu và thực hiện lại bước 2. 4.3.2.3 Loại bỏ từ dừng Đầu vào: Danh sách kề ID của các thuật ngữ trong văn bản. Đầu ra: Danh sách kề ID của các thuật ngữ trong văn bản trong đó không có ID nào thuộc danh sách từ dừng. Thực hiện: Lập một danh sách các từ dừng để so sánh mỗi thuật ngữ trong văn bản có thuộc danh sách này hay không. Để tăng tốc độ thực hiện, danh sách này lưu các từ dừng dưới dạng ID của chúng trong từ điển. Danh sách này (khoảng 200 đến 300 từ) được sắp xếp lại theo thứ tự của ID để có thể áp dụng tìm kiếm nhị phân. Cách xây dựng danh sách từ dừng: Duyệt một tập văn bản mẫu, chọn lọc các thuật ngữ có tần suất vượt quá một ngưỡng nào đó. 4.3.2.4 Thống kê từ khoá, tạo kết quả Đầu vào: Các dãy ID của thuật ngữ xuất hiện trong văn bản Đầu ra: Tổ chức dữ liệu có cấu trúc cho văn bản. Dữ liệu đầu ra được tổ chức theo hướng đối tượng. Mỗi văn bản được tổ chức theo cấu trúc như sau: Hình 22: Tổ chức dữ liệu có cấu trúc cho văn bản Các lớp cho mỗi phần tử được viết thêm các hàm chức năng như hàm tính tần suất, hàm tìm kiếm, hàm so sánh,.. 4.3 Module thực hiện giải thuật 1 Giải thuật 1 là giải thuật đơn giản nhất của hệ thống. Mục đích của nó là tạo ra TTVB bằng cách xây dựng hệ thống ghi điểm cho mỗi câu của văn bản. Sau đó dựa vào hệ số rút gọn để rút ra những câu có điểm cao nhất. Đầu vào: Văn bản được tổ chức theo dữ liệu có cấu trúc. Đầu ra: Danh sách các giá trị trọng số tương ứng với mỗi câu. 4.3.1 Một số nhận định quan trọng. Trước khi mô tả việc xây dựng giải thuật, có thể đưa ra một số nhận xét sau: Các từ xuất hiện trong tiêu đề thường là các từ rất quan trọng trong văn bản, tuy không thể chỉ dùng chúng để quyết định độ quan trọng của các câu trong văn bản. Có thể áp dụng cho giải thuật bằng cách tăng trọng số của các từ này theo một hệ số nào đó. Thông tin đưa ra trong một vài câu đầu (nhiều khi là một đoạn văn đầu) của văn bản trong hầu hết trường hợp có tính biểu lộ cao ý nghĩa của văn bản. Các câu quan trọng cũng có thể xuất hiện ở cuối văn bản, nhưng ít hơn so với đầu văn bản. Vì vậy, với mỗi câu thuộc các vị trí đầu hoặc cuối văn bản, tăng trọng số của chúng theo một hệ số nào đó. Bởi vì trọng số của mỗi câu được tính toán không phải trên tổng các trọng số của các thuật ngữ trong câu mà là tính trên độ trung bình các giá trị trọng số thuật ngữ này. Do vậy, sẽ có khả năng một số câu rất ngắn không mang nội dung nhưng chứa những thuật ngữ có trọng số cao vẫn sẽ được đưa vào trong tóm tắt. Có thể hạn chế sai sót này bằng cách chỉ xét những câu có số lượng thuật ngữ lớn hơn một độ dài nhất định nào đó. Với những văn bản có mật độ thông tin dày đặc, đặc biệt đối với những văn bản về lĩnh vực thương mại hay tài chính, sẽ rất khó khăn cho hệ thống khi trích rút. Do vậy độ chính xác của tóm tắt sẽ thấp hơn, có nghĩa là hệ thống có thể sẽ bỏ qua nhiều thông tin quan trọng. Điều này hiển nhiên sẽ giới hạn các lĩnh vực nội dung văn bản mà hệ thống có thể thực hiện. Tuy nhiên, cũng phải thừa nhận rằng chính con người khi tóm tắt các văn bản thuộc loại này cũng gặp rất nhiều khó khăn. Hệ thống chắc chắn cũng sẽ gặp nhiều khó khăn khi thực hiện tóm tắt các văn bản nhiều nội dung. 4.3.2 Mô hình chức năng Hình 23: Module giải thuật 1. 4.3.3 Thực hiện Các bước trong module ghi điểm được thực hiện như sau: 4.3.3.1 Hệ số ghi điểm Các hệ số này phục vụ cho việc tính toán trọng số câu ở bước sau. Chúng được sử dụng để tăng tính chính xác của giải thuật khi tạo tóm tắt. Các hệ số này cung cấp trước cho hệ thống là các hằng số. Tuy nhiên đạt hiệu quả cao nhất khi sử dụng các hệ số này, đòi hỏi phải trải qua quá trình thực nghiệm với kết quả của giải thuật hoặc áp dụng các thuật toán học máy để quyết định giá trị phù hợp cho chúng. Ở đây tạm coi là chúng đã có giá trị phù hợp nhất. Các hệ số ghi điểm bao gồm: Hệ số tiêu đề htd: quyết định trọng số của một thuật ngữ xuất hiện trong tiêu đề được nhân lên bao nhiêu lần. Nó được trả giá trị 1 khi văn bản không có tiêu đề. Hệ số vị trí câu: bao gồm các hệ số: + Hệ số hvt1: trọng số một câu được nhân lên bao nhiêu lần khi câu đó ở đầu văn bản. + Hệ số hvt2: áp dụng với 2 câu tiếp theo. + Hệ số hvt3: áp dụng với 2 câu áp chót văn bản. Thông thường hvt1>hvt2>hvt3 + Hệ số hdv1: áp dụng đối với mỗi câu nằm ở đầu đoạn văn. + Hệ số hdv2: áp dụng đối với mỗi câu nằm thứ hai hoặc áp chót đoạn văn. Hệ số độ dài câu hlen: quyết định những câu không có số thuật ngữ vượt quá con số này không được đưa vào tóm tắt. 4.3.3.2 Tính trọng số các câu Đầu vào: Dữ liệu có cấu trúc của văn bản và các hệ số ghi điểm Đầu ra: Điểm của các câu. Quá trình thực hiện gồm các bước: Bước 1. Duyệt toàn bộ văn bản, với mỗi thuật ngữ t trong câu s tính: + fts là số lần xuất hiện thuật ngữ t trong câu s. + ht là số lượng các câu có chứa thuật ngữ t. Bước 2. Duyệt lại văn bản, với mỗi câu s, thực hiện: Tính trọng số cho mỗi thuật ngữ t trong câu s: nếu t xuất hiện trong tiêu đề văn bản. nếu ngược lại. Trong đó: m là số lượng câu trong văn bản. htd là hệ số tiêu đề Tính điểm của câu: Trong đó: T(s) là số thuật ngữ có trong câu s. hvt(s) là hệ số vị trí của câu s trong văn bản. 4.3.3.3 Sắp xếp, tính ngưỡng và đưa ra kết quả Bước cuối cùng trước khi đưa ra kết quả là danh sách các câu được tóm tắt. Các bước: Bước 1. Duyệt toàn bộ các câu, nếu câu nào có T(s) nhỏ hơn hleng thì đặt lại trọng số cho câu: Score(s) = 0. Bước 2. Sắp xếp các Score(s) Bước 3. Theo danh sách đã tóm tắt chọn vị trí i trên danh sách để: với hco là tỷ lệ rút gọn tóm tắt. Bước 4. Kiểm tra dịch i lên/xuống 1 vị trí nếu i là vị trí mà tại đó có sự thay đổi đột ngột về độ lớn trọng số của câu. Ví dụ: Hình 24: Đồ thị trọng số câu Trong ví dụ trên, tại các vị trí i=3, i=4 có sự thay đổi đột ngột về giá trị trọng số của câu. Vai trò của bước cuối cùng này nhằm tăng độ chính xác cho giải thuật khi được kiểm thử. 4.4 Module thực hiện giải thuật 2 Giải thuật 2 áp dụng phương pháp phân nhóm để nhóm các câu có cùng nội dung vào một nhóm. Sau đó đưa ra tóm tắt bằng cách chọn ở mỗi nhóm một câu đại diện tốt nhất. Đầu vào: Văn bản được biểu diễn dưới dạng dữ liệu có cấu trúc Đầu ra: Danh sách nhóm các câu trong văn bản. 4.4.1 Mô hình của giải thuật Hình 25: Module thực hiện giải thuật 2 4.4.2 Tách thuật ngữ đại diện Ý tưởng cơ bản của giải thuật 2 là biểu diễn mỗi đoạn văn trong văn bản bằng một véc tơ (tương tự với cách biểu diễn mỗi văn bản bằng một véc tơ) chứa tần suất của các thuật ngữ xuất hiện trong đoạn văn. Tuy vậy, với một văn bản có nhiều các thuật ngữ khác nhau xuất hiện thì độ phức tạp tính toán sẽ cao, đồng thời độ chính xác khi phân nhóm cũng thấp. Bởi vậy, hướng giải quyết là chỉ chọn lọc các thuật ngữ có giá trị nội dung cao trong văn bản, gọi là các thuật ngữ đại diện của văn bản. Đầu vào: Văn bản được biểu diễn dưới dạng dữ liệu có cấu trúc với đầy đủ thuật ngữ. Đầu ra: Danh sách các thuật ngữ đại diện cho mỗi đoạn văn. Các bước thực hiện như sau : Bước 1. Duyệt toàn bộ văn bản, với mỗi thuật ngữ t trong đoạn văn p tính: + ftp là số lần xuất hiện thuật ngữ t trong đoạn văn p. + ht là số lượng các đoạn văn có chứa thuật ngữ t. Bước 2. Duyệt lại văn bản, với mỗi đoạn văn p, thực hiện: Tính trọng số cho mỗi thuật ngữ t trong đoạn văn p: Trong đó: m là số lượng các đoạn văn trong văn bản. Chuẩn hoá các trọng số này theo công thức: Trong đó: wtp = TF-IPF(t,p) Chọn ra các thuật ngữ có trọng số lớn hơn một ngưỡng cho trước và coi chúng là các thuật ngữ đại diện cho đoạn văn. 4.4.3 Véc tơ hoá đoạn văn. Phân nhóm đoạn văn cũng tức là gom các đoạn văn có sự tương tự về nội dung lại chung một nhóm với nhau. Như vậy cần có công thức đánh giá độ tương tự về nội dung giữa các đoạn văn. Độ tương tự này có thể được tính bằng công thức Cosine đã đề cập trong chương III. Đầu vào: Văn bản cùng danh sách các thuật ngữ đại diện cho mỗi đoạn văn. Đầu ra: Danh sách các véc tơ có cùng số chiều (nằm trong cùng một hệ toạ độ), mỗi véc tơ biểu diễn một đoạn văn. Thực hiện: Bước 1. Duyệt toàn bộ văn bản, xây dựng một tập thuật ngữ đại diện cho văn bản là hợp của tất cả các tập thuật ngữ đại diện cho từng đoạn văn trong văn bản. Trong đó: m là số đoạn văn. t(pi) là tập các thuật ngữ đại diện cho đoạn văn i. Giả sử T có n thành phần: T = {t1,t2,…,tn} Bước 2. Duyệt lại văn bản, với mỗi đoạn văn p xây dựng véc tơ biểu diễn: Vp = (w1,,w2, ... , wn) Trong đó, wi bằng trọng số của thuật ngữ ti trong đoạn văn p nếu nó là thuật ngữ đại diện cho p và bằng 0 nếu không phải. 4.4.4 Phân nhóm đoạn văn Tác giả sử dụng thuật toán lập nhóm theo cây phân cấp (HC) để phân nhóm các đoạn văn trong văn bản. Đầu vào: Danh sách các đoạn văn cùng với véc tơ biểu diễn. Đầu ra: Cây phân cấp dưới lên phân nhóm các đoạn văn. Các bước thực hiện: Bước 1: Lập danh sách m nhóm, mỗi nhóm chứa 1 đoạn văn thuộc văn bản. Véc tơ trọng tâm của nhóm chính là véc tơ biểu diễn cho mỗi đoạn văn đó. Bước 2: Tính độ tương tự giữa các nhóm với nhau theo công thức Cosin: Trong đó: n là số chiều của các véc tơ. (x1,x2,…,xn) là véc tơ trọng tâm của nhóm X. (y1,y2,…,yn) là véc tơ trọng tâm của nhóm Y. Bước 3: Chọn 2 nhóm có độ tương tự lớn nhất, gộp chung lại một nhóm và tính lại véc tơ trọng tâm theo công thức: với k là số phần tử có trong một nhóm. Bước 4: Lặp lại các bước 2 và 3 cho đến khi chỉ còn một nhóm. 4.4.5 Trích rút Tóm tắt. Đầu vào: Cây phân cấp xây dựng được từ giai đoạn trước. Đầu ra: Danh sách các câu được trích rút để sử dụng cho tóm tắt. Đây là bước quan trọng để tạo ra kết quả và nó quyết định độ chính xác khi thực hiện tóm tắt. Nội dung của nó thực hiện hai mục đích quan trọng: Quyết định số nhóm sẽ phân chia các đoạn văn (quyết định tầng kết quả của cây phân cấp) Quyết định lựa chọn câu/các câu nào trong mỗi nhóm. Hình 26: Ví dụ cây phân cấp theo giải thuật phân cấp dưới lên * Quyết định số nhóm: Thông thường đối với các bài toán phân nhóm văn bản, nhiệm vụ phân nhóm được cho là tối ưu khi sự giống nhau giữa các văn bản cùng một nhóm được cực đại hoá và sự giống nhau giữa các văn bản không cùng nhóm được cực tiểu hoá. Chính vì lẽ đó, để quyết định số nhóm được phân chia trong bài toán phân nhóm đoạn văn, có thể được quyết định thông qua việc tối ưu hoá để tìm giá trị nhỏ nhất của hàm mục tiêu f : trong đó: D là đại diện cho sự giống nhau giữa các đoạn văn không cùng nhóm, được tính bằng: D = max Sim(x,y) với x,y là 2 đoạn văn bất kỳ không thuộc cùng một nhóm với nhau S là đại diện cho sự giống nhau giữa các đoạn văn cùng nhóm, được tính bằng: S = min Sim(x,y) với x,y là 2 đoạn văn bất kỳ thuộc cùng một nhóm với nhau Cách thực hiện: với mỗi một bước lặp k (k = 0..n-1) trong giải thuật phân nhóm ở trên (tương ứng với tầng k trong cây phân cấp), sau khi gom hai nhóm có độ tương tự lớn nhất lại với nhau, tính và lưu giá trị fk tương ứng. Tìm giá trị fk nhỏ nhất, tương ứng có số nhóm cần phân chia là: c = n - k Quyết định số nhóm được phân chia trong bài toán TTVB tuy vậy còn liên quan vào một yếu tố khác: số lượng các câu tóm tắt phải có (hay hệ số rút gọn tóm tắt). Cụ thể, sự liên quan được trình bày dưới đây. * Lựa chọn câu trong nhóm: Lựa chọn câu trong nhóm có nghĩa là đối với mỗi nhóm đoạn văn được phân chia, phải rút ra một hoặc hơn một câu có giá trị nội dung cao nhất trong nhóm để đưa vào tóm tắt. Tỷ lệ tốt nhất là 1/1, có nghĩa là cứ 1 nhóm đoạn văn thì rút ra 1 câu. Tuy vậy, có thể số câu cần trích rút tạo tóm tắt lớn hơn hoặc nhỏ hơn nhiều lần so với số nhóm đã quyết định ở mục trên. Bước 1: Nếu ký hiệu số câu cần trích rút là a, số đoạn văn là n và số nhóm quyết định ở mục trên là c, trong trường hợp: - a<c : đặt lại số nhóm được phân chia c = a. - c<a<n: đặt lại số nhóm được phân chia c = a. - n<a: tìm giá trị l nhỏ nhất sao cho Khi đó, đặt lại số nhóm được phân chia c = a.2-l đồng thời ở mỗi nhóm thay vì trích rút 1 câu, thực hiện rút l+1 câu. Đây là trường hợp không mong muốn bởi các câu được rút nằm trong một nhóm, có thể trùng nhau về nội dung. Bước 2: Đây là bước cuối cùng của giải thuật: Duyệt toàn bộ các nhóm, với mỗi nhóm rút l câu có giá trị nội dung cao nhất. Có rất nhiều cách để lấy ra các câu văn từ mỗi nhóm này, có thể chỉ đơn giản bằng cách lấy ra l câu đầu tiên hoặc l câu dài nhất, hoặc áp dụng giải thuật 1 để ghi điểm cho từng câu trong mỗi nhóm đoạn văn và rút ra câu có điểm cao nhất. Khi phân tích khả năng bao chứa nội dung của các câu trong mỗi đoạn văn sau khi được phân nhóm, có thể đưa ra nhận xét sau: Hệ thống ghi điểm ở giải thuật 1 dựa trên tính toán giá trị nội dung của tất cả các thuật ngữ có trong văn bản. Việc trích rút các câu trong mỗi nhóm đoạn văn cần rút ra các câu có nội dung đại diện cho nhóm đoạn văn đó nhất chứ không phải cho toàn bộ văn bản. Giá trị nội dung của mỗi câu khi đó cũng không tính trên trung bình các thuật ngữ xuất hiện trong câu mà tính theo tổng các thuật ngữ đại diện của nhóm đoạn văn có trong câu. Vì vậy, hệ thống ghi điểm cho mỗi câu trong nhóm đoạn văn sẽ chỉ xét trên các thuật ngữ đại diện cho nhóm đoạn văn đó. Công thức ghi điểm được trinh bày đơn giản như sau (các bước thực hiện cũng giống như ở giải thuật 1): trong đó hvt là hệ số vị trí của câu s trong đoạn văn p, hoặc trong văn bản gốc. 4.5 Module thực hiện giải thuật 3 Giải thuật 3 là giải thuật thực hiện TTVB có độ phức tạp cao nhất được xây dựng trong hệ thống. Nội dung cơ bản của giải thuật là áp dụng các đặc trưng để tạo tóm tắt. Với mỗi đặc trưng, sẽ có một tóm tắt cho văn bản được tạo ra bằng cách sử dụng đặc trưng đó. Các đặc trưng này sau đó được kết hợp với nhau và dựa vào thực nghiệm trên các tập CSDL mẫu để tìm ra sự kết hợp cho kết quả tốt nhất. Có thể nói đây là một mô hình tổng quát để giải quyết bài toán tạo tóm tắt bằng cách trích rút câu. Bởi bất cứ một kỹ thuật để tạo tóm tắt nào từ đơn giản đến phức tạp nhất cuối cùng cũng đều cho ra một tóm tắt cho văn bản, và như vậy đều có thể coi là một “đặc trưng tóm tắt”. Giải thuật 3 được xây dựng ở đây sử dụng các đặc trưng tóm tắt đơn giản nhất, bởi vì quá trình tối ưu hoá trên tập CSDL mẫu có độ phức tạp tính toán cao. Do vậy, nếu lại sử dụng các đặc trưng phức tạp, hiệu quả về chất lượng có thể được nâng lên nhưng hiệu quả thời gian tính toán rất thấp. Mô tả giải thuật: Đầu vào: Văn bản ở dạng biểu diễn có cấu trúc. Đầu ra: Danh sách các câu được tóm tắt. 4.5.1 Mô hình giải thuật. Hình 27: Module thực hiện giải thuật 3. Module thực hiện giải thuật 3 lại được chia thành 2 module con: - Module áp dụng giải thuật học máy để tìm luật kết hợp các đặc trưng tóm tắt. - Module sử dụng luật kết hợp để xây dựng tóm tắt. Trong 2 module này đều sử dụng chức năng “Trích rút theo đặc trưng” để tạo ra tóm tắt từ văn bản gốc theo các đặc trưng định trước. 4.5.2 Trích rút theo đặc trưng Chức năng này có thể coi như là một hệ thống TTVB “con”, có nghĩa là nó có khả năng đưa ra một tóm tắt cụ thể. Tuy vậy, mục đích chính của nó để tạo ra các véc tơ đặc trưng cho mỗi một thành phần văn bản (trong trường hợp này là một câu). Đầu vào: Văn bản ở dạng dữ liệu có cấu trúc cùng với k đặc trưng tóm tắt. Đầu ra: Các véc tơ k chiều đặc trưng cho mỗi câu trong văn bản ban đầu. Giả sử có k đặc trưng: F1, F2, F3, …, Fk và văn bản gốc có n câu. => đầu ra của chức năng là n véc tơ: vi = (wi1, wi2, wi3, …, wik) (i = 1..n) Véc tơ đặc trưng cho câu chính là một dãy các trọng số của câu ứng với các đặc trưng để TTVB (để đơn giản hoá hệ thống, ta sử dụng mô hình Boolean: các trọng số này chỉ là 0 hoặc 1 có nghĩa wij chỉ có giá trị 0,1). Ví dụ: Với đặc trưng “Các câu có chứa tiêu đề sẽ được rút ra để xây dựng Tóm tắt”, nếu câu có chứa tiêu đề giá trị trọng số ứng với đặc trưng này sẽ bằng 1, ngược lại bằng 0. Các đặc trưng tóm tắt được phân tích để áp dụng trong giải thuật này: Đánh giá trị trọng số và ghi điểm cho mỗi câu trong văn bản gốc. Đây là đặc trưng được sử dụng trong giải thuật 1, tuy nhiên trong trường hợp này công thức ghi điểm cho câu được đưa về công thức nguyên bản: Trong đó: T(s) là số thuật ngữ có trong câu s. Các câu có điểm cao nhất theo một ngưỡng cho trước (phụ thuộc vào hệ số rút gọn tóm tắt) sẽ có giá trị trọng số 1 đối với đặc trưng này. Độ dài câu. Tương tự đặc trưng trên, sử dụng độ dài câu lớn hơn một hằng số cho trước cũng đã được sử dụng trong giải thuật 1. 1 nếu câu i có số thuật ngữ lớn hơn hằng số cho trước wi = 0 nếu ngược lại Vị trí câu. Có rất nhiều phương pháp khác nhau khai thác vị trí của câu trong văn bản để thực hiện tóm tắt. Trong giải thuật 1, một cách khai thác vị trí câu cũng đã được sử dụng: đó là sử dụng các hệ số nhân điểm cho câu theo vị trí trong văn bản. Ở đây, đặc trưng vị trí câu được thực hiện bằng cách trước hết ghi điểm khởi đầu cho mỗi câu. Cụ thể: - Ba câu đầu và hai câu áp chót văn bản có điểm là a . - Câu đầu mỗi đoạn văn có điểm là b - Câu thứ hai và câu cuối mỗi đoạn văn có điểm c Các câu còn lại có điểm là 1. Trong đó a>b>c>1. (Các hệ số này được quyết định bằng thực nghiệm khi chỉ sử dụng riêng một đặc trưng vị trí) Sau đó, điểm cho mỗi câu được đặt lại: trong đó mark(i) là điểm của câu thứ i trong văn bản n là số câu trong văn bản h là hằng số được quyết định bằng thực nghiệm Cuối cùng, các câu được sắp xếp theo điểm vị trí của chúng, các câu có điểm vượt quá ngưỡng cho trước được xem như thoả mãn đặc trưng vị trí câu. Độ tương tự với tiêu đề. Các câu có chứa thông tin liên quan đến tiêu đề hiển nhiên mang giá trị nội dung cao. Để tính toán độ tương tự với tiêu đề, có thể sử dụng nhiều cách. Ở đây, tác giả sử dụng công thức tính độ tương tự Cosin, coi tiêu đề như một truy vấn và tính độ tương tự của mỗi câu với truy vấn này (phương pháp thường được sử dụng trong các hệ tìm kiếm thông tin - IR). Các câu có độ tương tự với tiêu đề vượt một ngưỡng cho trước được xem như thoả mãn đặc trưng này. Độ tương tự với từ khoá. Từ khoá (key word) là các từ đặc trưng về nội dung cho văn bản. Bởi vậy chúng cũng có giá trị nội dung tương đương với các thuật ngữ xuất hiện trong tiêu đề. Độ tương tự của mỗi câu với dãy các từ khoá cũng được tính theo công thức như trên. Các từ khoá được phát hiện sử dụng phương pháp đánh giá trọng số. Các thuật ngữ có tần số IF-TDF cao nhất vượt quá ngưỡng cho trước chính là các từ khoá của một văn bản. Độ tương tự với các câu khác trong văn bản. Các câu trong văn bản có nội dung liên kết nhiều nhất với các câu khác có thể coi là câu đại diện cho văn bản, vì vậy cũng có khả năng tham gia tóm tắt cao. Độ tương tự này được tính bằng cách: trong đó sim(s,s’) là độ tương tự giữa hai câu trong văn bản được tính theo công thức Cosin (đã trình bày trong giải thuật 2). Các giá trị này được sắp xếp và chọn ra các câu cao nhất vượt quá ngưỡng. Độ tương tự với véc tơ trọng tâm của văn bản. Để tính giá trị đặc trưng này cho mỗi câu, trước hết tính véc tơ trọng tâm của văn bản: trong đó vi là các véc tơ biểu diễn câu theo tần suất TS-ISF. Sau khi xây dựng véc tơ trọng tâm, các véc tơ biểu diễn câu nào trong văn bản có độ tương tự với véc tơ trọng tâm lớn nhất sẽ được chọn để thoả mãn đặc trưng này. Phân nhóm các câu có cùng nội dung trong văn bản. Đặc trưng tóm tắt này tương tự với giải thuật 2 đã thực hiện. Xong các thành phần được phân nhóm không phải là các đoạn văn mà là các câu. Do vậy khả năng áp dụng là lớn hơn so với giải thuật 2 (chỉ áp dụng đối với các văn bản được phân chia ra thành các đoạn văn). Xuất hiện tên riêng trong câu. Đặc trưng này đã được trình bày trong chương II, phần giới thiệu các phương pháp TTVB. Nó chỉ ra rằng các câu có xuất hiện tên riêng (thường viết tắt bằng chữ hoa) có giá trị tóm tắt cao. Xuất hiện các thuật ngữ đặc biệt. Các câu có chứa các thuật ngữ như “tổng quát”, “tóm tắt”, “nói chung”, “cụ thể”, …. có nhiều khả năng được sử dụng để tạo tóm tắt. Xây dựng danh sách các thuật ngữ đặc biệt, sau đó duyệt toàn bộ văn bản, những câu có chứa thuật ngữ đực biệt này xem như thoả mãn đặc trưng. Vị trí của câu trong cây nhị phân. Cây nhị phân được xây dựng cho mỗi văn bản để đánh giá sự liên kết về nội dung giữa các thành phần văn bản liền kề (ở đây là câu). Giải thuật xây dựng cây nhị phân tương tự với giải thuật gom cụm để tạo cây phân cấp. Điểm khác nhau duy nhất là các thành phần được gộp lại với nhau phải là các thành phần liền kề. Có thể trình bày đơn giản giải thuật như sau: Bước 1: Ban đầu coi mỗi câu như một nhóm Bước 2: Tính độ tương tự giữa tất cả các cặp 2 nhóm liền kề với nhau Bước 3: Chọn ra 2 nhóm có độ tương tự cao nhất, kết hợp chúng lại thành một nhóm mới thay vào vị trí 2 nhóm đó Bước 4: Lặp lại bước 2 và bước 3 cho đến khi chỉ còn 1 nhóm duy nhất chứa toàn bộ các câu trong văn bản Hình 28: Giải thuật tạo cây nhị phân Từ cây nhị phân được tạo thành, có thể rút ra các đặc trưng nhỏ: + Các câu gần với gốc (chỉ qua từ 1 đến 4 nút) không mang nhiều giá trị nội dung cho văn bản. + Mỗi nhóm các câu xa gốc nhất thường có chung một giá trị nội dung và có thể trích rút một trong chúng để xây dựng tóm tắt. Đặc trưng nhỏ thứ nhất phù hợp bởi các tính chất không mang nội dung được chứng minh, trong khi đặc trưng thứ nhỏ thứ hai có giá trị tương tự với đặc trưng (h). 4.5.3 Giải thuật học máy Mục đích của chức năng này nhằm đưa ra một sự kết hợp các đặc trưng tốt nhất có thể để xây dựng tóm tắt. Như đã trình bày trong chương II, mục đích của giải thuật là tìm ra các hệ số thực hiện ki cho mỗi đặc trưng Fi. Để đơn giản hệ thống, các hệ số ki được coi là chỉ có giá trị 0 hoặc 1. Với mỗi đặc trưng F, hệ số k=0 có nghĩa là nó không được sử dụng để tạo tóm tắt và k=1 có nghĩa là nó được sử dụng trong kết hợp. Đầu vào: Tập các đặc trưng F1,F2,..,Fk và tập văn bản mẫu đã được véc tơ đặc trưng hoá. Đầu ra: Một kết hợp các đặc trưng F1’,F2’,..,Fm’ cho kết quả tóm tắt tốt nhất. Thực hiện: Nhắc lại về luật xác suất Bayes đã trình bày trong phần trước: Xác suất một câu s thuộc văn bản gốc có nằm trong tóm tắt S của văn bản sử dụng các đặc trưng F1,F2,..,Fk đó hay không là: Giá trị P(sÎS) là một hằng số (bằng hệ số rút gọn). Giá trị P(Fj| sÎS) và P(Fj) có thể được tính theo các tập mẫu văn bản đã được tóm tắt. = > với bất cứ một tập hợp u đặc trưng bất kỳ, đều có thể tính toán xác suất một câu s trong văn bản d đã thoả mãn u đặc trưng đó có nằm trong tóm tắt hay không. Nếu áp dụng các luật Bayes với một tập hợp nhiều đặc trưng, độ phức tạp tính toán sẽ tỷ lệ với tổ hợp của tất cả các đặc trưng đó. Hệ thống khi đó có hiệu suất thời gian rất thấp. Bởi vậy trong giải thuật này, tác giả đề xuất phương hướng như sau: - Chỉ áp dụng luật Bayes với tổ hợp chập 3 hoặc 4 phần tử đặc trưng trở xuống. - Không thực hiện trên toàn bộ các tổ hợp mà phân tích mối liên kết giữa các đặc trưng để xét các tổ hợp hợp lý. 4.5.4 Áp dụng kết hợp Đầu vào: Các véc tơ đặc trưng cho mỗi câu của văn bản cần tóm tắt. Luật kết hợp các đặc trưng tối ưu. Đầu ra: Danh sách các câu được tóm tắt. Đây là bước cuối cùng đơn giản nhất của giải thuật. Thực hiện: Duyệt toàn bộ các câu trong văn bản. Nếu véc tơ đặc trưng của câu thoả mãn toàn bộ các đặc trưng tối ưu, đưa câu và danh sách các câu được tóm tắt. 4.6 Module tạo kết quả. Đầu vào: Danh sách các câu cùng đã được sắp xếp thự tự để thực hiện tóm tắt cho từng giải thuật. Đầu ra: Tạo văn bản tóm tắt. Đây là chức năng thực hiện tạo kết quả tóm tắt cuối cùng để cung cấp cho người sử dụng. Đối với hệ thống, đây là chức năng rất đơn giản và tác giả cũng không đề cập chi tiết. Tuy rất đơn giản, nhưng tác giả cũng thiết kế nó như một module riêng để có thể phát triển hệ thống lên cao nữa sau này (ví dụ tạo tóm tắt abstract). 4.7 Cài đặt hệ thống. 4.7.1 Môi trường và công cụ cài đặt. * Môi trường cài đặt: Hệ thống được cài đặt trong môi trường hệ điều hành Windows XP (có thể hoạt động trong các hệ điều hành Windows 9x trở lên có hỗ trợ Unicode). Bộ nhớ trong : 25 MB hoặc hơn. Bộ nhớ ngoài: 25 MB hoặc hơn. (Qua thử nghiệm khi chương trình đang hoạt động, bộ nhớ hệ điều hành cung cấp cho chương trình lúc lớn nhất là khoảng 17MB) * Công cụ cài đặt: Hệ thống được cài đặt bằng ngôn ngữ Visual C++ 6.0. Đặc điểm của hệ thống là hoạt động dựa trên các giải thuật tính toán phức tạp và sử dụng nhiều bộ nhớ. Giao diện của hệ thống không quá phức tạp. Do vậy VC++ có khả năng hỗ trợ rất tốt tốc độ tính toán xử lý dữ liệu. Đồng thời thư viện MFC của VC++ có rất nhiều lớp phục vụ tính toán trên các xâu (đối tượng xử lý chính đối với mỗi bài toán trong Khai thác văn bản) 4.7.2 Mô tả chương trình. Chương trình được đặt tên là VietSum. 4.7.2.1 Các lớp chính được thiết cho chương trình: Các lớp quản lý dữ liệu. + lớp CVNDocument lưu trữ dữ liệu có cấu trúc của một văn bản. + lớp CVNParagraph lưu trữ dữ liệu có cấu trúc của một đoạn văn trong văn bản. Nó là lớp con của lớp CVNDocument. + lớp CVNSentence lưu trữ dữ liệu của một câu trong văn bản. Nó là lớp con của lớp CVNParagraph. Các lớp quản lý giao diện. + lớp CVietSumDlg quản lý giao diện chính. + lớp CAlgo1Dlg, CAlgo2Dlg, Cdlgo3Dlg quản lý giao diện các chức năng tóm tắt theo từng giải thuật. + lớp CVietSumApp quản lý ứng dụng, tức là phần khung của chương trình. Các lớp thực hiện giải thuật + lớp CAlgorithm1, CAlgorithm2, CAlgorithm3 chứa các hàm thực hiện giải thuật. + Lớp CTextFile quản lý việc tương tác với các file văn bản: đọc, ghi, nhận dạng mã ký tự. + lớp CTextPreprocessing thực hiện các bước tiền xử lý văn bản. 4.7.2.2 Giao diện chính chương trình Hình 29: Giao diện chính của chương trình. Trong đó: Vùng 1 thực hiện chọn một văn bản để tóm tắt. Hệ thống chỉ được nghiên cứu thiết kế để tóm tắt các văn bản đơn lẻ (Single Document Sumarization - SDS) chứ không phải các tập văn bản (Multi Documents Summarization - MDS). Tất nhiên có thể tóm tắt một tập văn bản bằng cách tóm tắt từng văn bản trong chúng. Tuy nhiên về tính chất đây cũng chỉ là tóm tắt SDS bởi hệ MDS cần phải thực hiện tóm tắt dựa trên cả sự liên kết về nội dung, tính chất của các văn bản trong cùng một tập dữ liệu kết hợp với các giải thuật khác. Vùng 2 cung cấp nội dung của văn bản cần tóm tắt. Trong đó, cửa sổ phía trên chứa văn bản gốc và phía dưới là các con số thống kê nội dung của văn bản cùng danh sách thuật ngữ xuất hiện trong văn bản. Vùng 3 chứa kết quả của hệ thống. Một văn bản cần tóm tắt có thể được tóm tắt nhanh sử dụng một trong ba giải thuật với các hệ số và tuỳ chọn mặc định. Kết quả tóm tắt thể hiện trong cửa sổ bên trái của vùng. Cũng có thể thực hiện tóm tắt cho một văn bản bằng cách áp dụng cụ thể từng giải thuật với các hệ số do người dùng đưa ra. 4.7.2.3 Giao diện giải thuật 1 Chức năng này được kích hoạt bằng cách chọn Công cụ/Giải thuật 1 trên giao diện chính. Hình 30: Giao diện giải thuật 1. Trong đó, vùng 1 để tạo kết quả tóm tắt ghi ra tệp văn bản. Vùng 2 để người dùng có thể nhập các hằng số tóm tắt để có thể tối ưu hoá tóm tắt. Vùng 3 đưa ra kết quả tóm tắt, danh sách các câu trong văn bản gốc cùng với điểm của chúng để minh hoạ cụ thể cho kết quả. 4.7.2.4 Giao diện giải thuật 2 Giải thuật 2 được kích hoạt bằng cách chọn Công cụ/Giải thuật 2 từ giao diện chính. Hình 31: Giao diện giải thuật 2 Trong đó, vùng 1 và cùng 2 cũng có chức năng tương tự như giao diện giải thuật 1. Ở vùng 3.1, minh hoạ cho kết quả tóm tắt là danh sách các nhóm đoạn văn/câu văn đã được phân nhóm. 3.2 là kết quả ghi điểm cho mỗi câu trong văn bản và 3.3 thể hiện kết quả TTVB. 4.7.2.5 Giao diện giải thuật 3 Giải thuật 3 được kích hoạt bằng cách chọn Công cụ/Giải thuật 3 từ giao diện chính. Hình 32: Giao diện giải thuật 3 Trong đó vùng 2.1 để lựa chọn các đặ trưng tóm tắt sẽ dùng trong giải thuật. Bởi vì không phải nhiều đặc trưng cùng kết hợp sẽ làm cho hiệu quả của giải thuật tốt hơn. Vùng 2.2 cho người dùng hai lựa chọn có/không sử dụng giải thuật học máy. Giải thuật học máy được dùng để tìm ra luật kết hợp tốt nhất các đặc trưng tóm tắt. Nếu chọn áp dụng giải thuật học máy, người dùng phải cung cấp đường dẫn đến tập Tóm tắt mẫu cho chương trình. Mỗi một cặp văn bản - tóm tắt trong tập mẫu được lưu dưới dạng văn bản gốc - danh sách các câu tóm tắt của văn bản. Vùng 3 thể hiện kết quả tóm tắt và danh sách các câu thoả mãn đặc trưng. 4.8 Minh hoạ một số thực nghiệm và đánh giá 4.8.1 Đại lượng đánh giá độ chính xác. Để đánh giá sự chính xác của của quá trình thực hiện TTVB, hai giá trị sau được sử dụng: độ chính xác (precision) và độ bao (recall). Hình 33: Precision và Recall Giả sử một văn bản cần tóm tắt trong đó có a câu đúng (dựa theo tập tóm tắt mẫu), b câu mà hệ thống tìm kiếm được và c là giao của a và b. * Độ chính xác (Precision). Độ chính xác hay giá trị Precision được tính bằng: * Độ bao (Recall) Độ bao hay giá trị Recall được tính bằng: Ví dụ: Một văn bản có 40 câu. Tóm tắt được cho là chính xác tuyệt đối do tác giả tạo ra bao gồm 15 câu. Văn bản này được đưa vào hệ thống tóm tắt tự động và cho ra kết quả sau (tương ứng với kết quả tìm được là 6 / 10 / 20 câu): Kết quả tìm được Kết quả đúng tìm được Precision Recall 6 4 0.27 (4/15) 0.67 (4/6) 10 6 0.40 (6/15) 0.60 (6/10) 20 9 0.60 (9/15) 0.45 (9/20) Bảng 5: Minh hoạ các giá trị Precision và Recall Có thể thấy nếu giá trị Precision càng cao thì giá trị Recall càng thấp và ngược lại Recall càng cao thì Precision càng thấp. Để đánh giá chính xác kết quả của một hệ thống không thể chỉ dựa vào một trong hai giá trị này mà phải kết hợp cả 2. Giá trị precision = recall khi kích thước tập kết quả tìm được bằng với kích thước tập kết quả mong muốn. 4.8.2 Cơ sở dữ liệu thực nghiệm Các văn bản mẫu là các bài báo được lấy từ địa chỉ trang web của báo điện tử VnExpress: Các thông số của tập dữ liệu văn bản: Số văn bản: 594 văn bản. Tổng dung lượng: 2.6 MB. Kích thước văn bản lớn nhất: 15 KB. Kích thước văn bản nhỏ nhất: 2 KB. Kích thước trung bình một văn bản: 4.5 KB. Tập văn bản - tóm tắt mẫu cũng được lấy trong CSDL này, có 20 văn bản cùng với tóm tắt mẫu: STT Tiêu đề Kích thước Số câu tóm tắt 1 Bệnh nhân SARS dễ mắc lao phổi 4KB 8 2 Bibica thay đổi nhân sự cao cấp 2KB 6 3 Chỉ số giá tiêu dùng tháng 7 sẽ tiếp tục tăng 3KB 9 4 Chuẩn bị ban hành khung giá đất mới 2KB 6 5 Cổ phiếu Bảo Minh đắt giá 4KB 10 6 Đua khuyến mại điện thoại VoIP 8KB 18 7 Sắp có thêm hạn ngạch dệt may đi EU 4KB 8 8 IncomBank tung ra thẻ chip vô danh đầu tiên 3KB 8 9 Vụ kiện tôm đe doạ tới xuất khẩu của Mỹ 5KB 12 10 Khiển trách phó chủ nhiệm đoàn luật sư Hà Nội 4KB 9 11 Vàng Trung Quốc giá rẻ xâm lấn thị trường 2KB 6 12 Vinafood2 trúng thầu xuất khẩu 150.000 tấn gạo 2KB 8 13 Yukos vỡ nợ, có ngu cơ phá sản 4KB 10 14 Công ty Việt đầu tư xây nhà ở Mỹ 3KB 8 15 Cổ phần hoá cần dứt khoát hơn 4KB 10 16 Chiến dịch săn lùng Rooney sôi sục khắp châu Âu 6KB 15 17 Lỗi nghiêm trọng trong game Unreal 3KB 8 18 Bán dẫn châu Á-Thái Bình Dương sẽ tăng trưởng 27,4% 3KB 7 19 Giới nữ trong thời đại công nghệ 4KB 9 20 Bảo vệ rùa bằng cá mập giả 5KB 12 Bảng 6: Tập tóm tắt mẫu Tất cả dữ liệu được thử nghiệm trên máy Pentium III 866 Mhz với 256 MB bộ nhớ. 4.8.3 Thực nghiệm trên modul Tiền xử lý văn bản. Để thử nghiệm hiệu quả của module Tiền xử lý văn bản, cần đánh giá tốc độ và độ chính xác của thuật ngữ được tách. Tốc độ của quá trình tách thuật ngữ và chuyển chúng về dạng dữ liệu chuẩn được kiểm tra có số liệu sau: Kích thước tập văn bản (KB) Chiều dài thuật ngữ lớn nhất (ký tự) Thời gian tách (s) Tốc độ theo dung lượng (KB/s) Tốc độ theo văn bản (văn bản/s) 607 30 6 101 19 607 15 4 152 28 1253 30 13 96 18 1253 15 8 157 30 Bảng 7: Kết quả tách thuật ngữ. Đánh giá: Có thể thấy tốc độ tách thuật ngữ không phụ thuộc vào dung lượng của văn bản. Nhưng khi chiều dài của thuật ngữ lớn nhất thay đổi ảnh hưởng đáng kể đến tốc độ phân tách. Nhận xét rằng trong từ điển thuật ngữ tiếng Việt, phần lớn các thuật ngữ đều có độ dài là 2 từ và rất ít thuật ngữ có độ dài 4 từ trở lên. Do vậy nếu cần tăng tốc độ tách thuật ngữ, có thể giảm chiều dài của thuật ngữ lớn nhất phải xét bằng chiều dài lớn nhất của một thuật ngữ có 2 từ trong từ điển. Hệ thống khi đó vẫn cho kết quả tốt trong khi tốc độ tách thuật ngữ giảm đáng kể. 4.8.4 Thực nghiệm trên các module Tóm tắt. Việc đánh giá độ chính xác của các giải thuật tóm tắt tiếng Việt gặp nhiều khó khăn do hạn chế về nguồn dữ liệu mẫu chuẩn. Chưa có một đơn vị nào xây dựng các tóm tắt mẫu với số lượng lớn và công bố chúng rộng rãi. Điều này gây ra nhiều trở ngại đối với tác giả trong quá trình xây dựng hệ thống, không chỉ bởi việc không đánh giá được kết quả chương trình mà còn bởi giải thuật 3 được xây dựng trong hệ thống phụ thuộc rất nhiều vào tập dữ liệu mẫu này. Để giải quyết trước mắt vấn đề này, tác giả đề xuất phương án tự xây dựng tập tóm tắt mẫu bằng cách tận dụng kinh nghiệm đọc - hiểu - lượng giá thông tin của một số chuyên gia - con người tiếp xúc nhiều với dữ liệu văn bản (nhà báo, sinh viên, học sinh,…). Mỗi chuyên gia sẽ đọc một số văn bản sau đó tự đưa ra tóm tắt dựa trên kinh nghiệm của mình. Kết quả tuy chưa tạo nên các tóm tắt chính xác tuyệt đối xong đối với hệ thống tóm tắt tự động, đây cũng là những tập mẫu mong muốn. Tuy vậy do thời gian có hạn, số lượng các tóm tắt mẫu này không lớn (20 - như trên đã liệt kê). Vì vậy tác giả hy vọng có thể tiếp tục mở rộng thêm tập dữ liệu mẫu này trong thời gian tới để có thể đánh giá cũng như nâng cao chất lượng của hệ thống. Dưới đây là số liệu thống kê kết quả của ba giải thuật tóm tắt được sử dụng trong hệ thống, độ rút gọn thông tin là 50%: Giải thuật 1 Giải thuật 2 Giải thuật 3 Kết quả (Precision, Recall) 60.07% 72.45% 70.42% Bảng 8. Đánh giá độ chính xác các giải thuật Đánh giá: Hệ thống cho kết quả thấp đi khi hệ số rút gọn thông tin giảm. Bởi vì việc lựa chọn một câu làm tóm tắt sẽ khó hơn nếu như tỷ lệ câu đó nằm trong tóm tắt nhỏ hơn. Tác giả đã thực hiện đánh giá về ngữ nghĩa qua các tóm tắt được tạo bởi hệ thống. Với 20 tóm tắt, đa phần đã mang đủ hết nội dung quan trọng của văn bản gốc. Sai số về sự chính xác được cảm nhận là không đáng kể. Bởi vậy tính thực tế của hệ thống lớn. Việc thu thập tập dữ liệu mẫu mất khá nhiều thoài gian nên kích thước của tập mẫu vẫn còn nhỏ. Chính vì vậy hệ thống chưa có nhiều điều kiện để thử nghiệm với dữ liệu lớn. Tác giả vẫn đang thu thập thêm các mẫu tóm tắt để có thể đưa đánh giá đúng hơn về tính chính xác của hệ thống bằng thực nghiệm. TỔNG KẾT Có thể thấy bài toán TTVB là bài toán có giá trị ứng dụng rất lớn. Với sự phát triển của các kho dữ liệu khổng lồ và các kỹ thuật nâng cao khả năng tính toán của máy móc, các ứng dụng của TTVB sẽ được thực hiện ngày càng nhiều hơn theo nhu cầu của con người. Các kỹ thuật TTVB nói chung và TTVB tiếng Việt nói riêng sẽ còn còn được nghiên cứu và phát triển thêm trong khoảng thời gian tới. Qua việc nghiên cứu và thực hiện đề tài này, tác giả đưa ra một số tổng kết sau: (*) Các vấn đề đã giải quyết: Trong phạm vi đồ án, tác giả đã thực hiện giải quyết được những vấn đề: Nghiên cứu lý thuyết tổng quan về bài toán TTVB, các phương pháp và xu hướng giải quyết bài toán. Phân tích các phương pháp có thể áp dụng cho bài toán TTVB tiếng Việt. Cụ thể là các phương pháp sử dụng kỹ thuật lượng giá, thống kê. Xây dựng một hệ thống TTVB cho tiếng Việt dựa trên các các kỹ thuật đã phân tích. (*) Hướng phát triển: Trong thời gian tới tác giả hy vọng sẽ phát triển đề tài theo các hướng: Phát triển các kỹ thuật lượng giá để tăng thêm tính hiệu quả cho hệ thống. Tìm kiếm một số đặc trưng Tóm tắt cho kết quả cao đối với tiếng Việt. Xây dựng từ điển đồng nghĩa phục vụ cho hệ thống, từ điển WordNet tiếng Việt để có thể mở rộng hệ thống với các kỹ thuật dựa trên độ liên kết ngữ nghĩa trong văn bản. Đặc biệt kỹ thuật áp dụng các chuỗi từ vựng (Lexical Chains) rất có tính khả thi. Nghiên cứu các phương pháp làm “mượt” (smoothing) kết quả để có thể từ tóm tắt Extract tạo nên tóm tắt Abstract. Phát triển hệ thống kết hợp với các hệ thống tìm kiếm bằng tiếng Việt trên Internet. TÀI LIỆU THAM KHẢO Tiếng Việt: [1] H. Kiếm, Đ. Phúc, “Rút trích ý chính từ văn bản tiếng Việt hỗ trợ tạo nội dung”, Trường Đại học Khoa học Tự Nhiên Tp. HCM, Việt nam. [2] P. Liêm, “Ứng dụng mô hình tập thô dung sai trong xử lý văn bản”, Trường Đại học Bách Khoa Hà Nội, (2004). [3] C. Trang, “Bài toán phân nhóm văn bản tiếng Việt”, Trường Đại học Bách Khoa Hà Nội, (2004). Tiếng Anh: [4] J Larocca Neto, AD Santos, CAA Kaestner, and AA Freitas, “Document Clustering and Text Summarization”. In N Mackin, editor, Proc 4th International Conference Practical Applications of Knowledge Discovery and Data Mining (PADD-2000), (2000). [5] M. Mitra, A. Singhal, and C. Buckley. “Automatic text summarization by paragraph extraction”. In ACL’97/EACL’97 Workshop on Intelligent Scalable Text Summarization, (1997). [6] H. P. Luhn, “The Automatic Creation of Literature Abstracts”, IBM Journal of Research Development, (1959). [7] R. Barzilay and M. Elhadad. “Using lexical chains for text summarization”, (1997). [8] Chinatsu Aone, Mary Ellen Okurowski, James Gorlinsky, and Bjornar Larsen. “A Scalable Summarization System Using Robust NLP”, (1997). [9] Jaime Carbonell and Jade Goldstein. “The use of MMR, diversity-based reranking for reordering documents and producing summaries”. In Pro- ceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, (1998). [10] D. Radev, H. Jing, and M. Budzikowska. “Centroid-based summarization of multiple documents: sentence extraction, utility-based evaluation and user studies”, (2000). [11] Karen Sparck-Jones and Tetsuya Sakai. “Generic summaries for indexing in IR”, New Orleans, LA, (2001). [12] K. Zechner. “Fast generation of abstracts from general domain text corpora by extracting relevant sentences”, (1996). [13] J. Kupiec, J. Pedersen, F. Chen, “A Trainable Document Summarizer”, Xerox Research Center, (1995). [14] AI Berger and Mittal, “A system for summarization web pages”, In Proc ACM SIGIR, (2000). [15] Darin Brezeale, “The Organization of Internet Web pages Using Wordnet and Self-Organizing maps”, MSC Thesis, The University of Texas at Arlington, USA, (1999). [16] Daniel Mallett, “Text summarization-an annotated bibliography”, (2003). [17] Smaranda Muresean, “Combining Linguistic and machine learning techniques for eamil summarization”, Columbia University, (2001).