LUẬN VĂN:XỬ LÝ CÁC CÂU TRUY VẤN VÀ TÌM KIẾM TRÊN KHO TÀI LIỆU CÓ CHÚ THÍCH NGỮ NGHĨA BẰNG TIẾNG ANH

Cũng d

Đại Học Quốc Gia TP. Hồ Chí Minh

TRƯỜNG ĐẠI HỌC BÁCH KHOA

---------o0o----------

LUẬN VĂN ĐẠI HỌC

XỬ LÝ CÁC CÂU TRUY VẤN VÀ TÌM KIẾM TRÊN KHO TÀI LIỆU CÓ CHÚ THÍCH NGỮ NGHĨA BẰNG TIẾNG ANH

Chuyên ngành: Khoa Học Máy Tính

GVHD

: Pgs.Ts. Cao Hoàng Trụ

Sinh viên : Nguyễn Trần Đăng Khoa

(50601130)

Tạ Tất Tài (50602084)

TP. Hồ Chí Minh, tháng 12 – 2010

CÔNG TRÌNH ĐƯỢC HOÀ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. CAO HOÀNG TRỤ

Cán bộ chấm nhận xét 1 : .........................................................................................

Cán bộ chấm nhận xét 2 : .........................................................................................

Luận văn đại học được bảo vệ tại HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN ĐẠI HỌC

TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày . . . . . tháng . . . . năm . . . . .

LỜI CAM ĐOAN

Tôi cam đoan rằng ngoại trừ các kết quả tham khảo từ các công trình khác như đã ghi rõ trong luận

văn, các công việc trình bày trong luận văn này là do chính tôi thực hiện và chưa có phần nội dung

nào của luận văn này được nộp để lấy một bằng cấp ở trường đại học nào khác.

Ngày ................ Tháng ............ Năm ..........

Ký tên

LỜI CẢM ƠN

Trước hết, chúng tôi xin gởi lời cảm ơn chân thành và sâu sắc đến Pgs.Ts. Cao Hoàng Trụ, và

kỹ sư Châu Kim Cường, những người đã trực tiếp hướng dẫn tôi trong quá trình làm luận văn này.

Sự hướng dẫn chu đáo, tận tình, cùng với những tài liệu và lời khuyên quý giá của thầy và anh trong

hơn 3 tháng qua là nhân tố không thể thiếu để chúng tôi có thể hoàn thành nhiệm vụ.

Chúng tôi xin gửi lời cảm ơn đến gia đình và bạn bè, những người luôn sát cánh, động viên, và

tạo mọi điều kiện tốt nhất để chúng tôi có thể học tập và hoàn tất được luận văn tốt nghiệp này.

Chúng tôi chân thành biết ơn sự tận tình dạy dỗ và sự giúp đỡ của tất cả quý thầy cô khoa Khoa

học và Kỹ thuật Máy tính trường Đại học Bách khoa.

Luận văn này khó tránh khỏi còn thiếu sót do tầm nhìn của chúng tôi còn hạn hẹp, rất mong

nhận được sự góp ý của quý thầy cô cùng các bạn.

TÓM TẮT

Từ khi ra đời đến nay, World Wide Web đã trở thành một công cụ quan trọng để lưu trữ và chia

sẻ nguồn tri thức khổng lồ. Tuy nhiên, các công cụ phần mềm hiện nay chưa hỗ trợ thật hiểu quả

cho con người trong quá trình khai thác kho tri thức ấy. Với mong muốn làm hiệu quả hơn quá trình

đó, luận văn này xây dựng một công cụ tìm kiếm có thể “hiểu” được nội dung của câu truy vấn bằng

tiếng Anh và trả về kết quả.

Để biên dịch câu truy vấn ngôn ngữ tự nhiên, luận văn này dựa trên nền tảng web ngữ nghĩa,

kết hợp với phương pháp dịch ít phụ thuộc vào cú pháp của nhóm VN-KIM. Để thể hiện nội dung

biên dịch được, luận văn biểu diễn bằng đồ thị ý niệm. Cuối cùng, câu truy vấn SeRQL được dùng

để tìm kiếm kết quả.

Hiệu quả của hệ thống được đánh giá trên tập câu truy vấn mẫu “TREC 2002”.

MỤC LỤC

CHƯƠNG 1 TỔNG QUAN ............................................................ Error! Bookmark not defined.

1.1 Giới thiệu....................................................................................................................... 1

1.2 Mục tiêu và phạm vi ...................................................................................................... 3

1.3 Cấu trúc luận văn ........................................................................................................... 5

CHƯƠNG 2 6

CÁC NGHIÊN CỨU VÀ HỆ THỐNG LIÊN QUAN ....................... Error! Bookmark not defined.

2.1 Rút trích quan hệ............................................................................................................ 6

2.2 Sơ lược về đồ thị ý niệm ................................................................................................ 7

2.2.1 Đồ thị ý niệm mở rộng ............................................................................................. 9

2.2.2 Các phương pháp chuyển đổi câu truy vấn sang đồ thị ý niệm . Error! Bookmark not

defined.

CHƯƠNG 3 12

PHƯƠNG PHÁP TIẾP CẬN .........................................................................................................12

3.1 Chuyển đổi câu truy vấn với từ để hỏi “How many” .................................................... 12

3.2 Chuyển đổi câu truy vấn có tính từ ............................................................................... 14

3.3 Chuyển đổi câu truy vấn có tính từ so sánh nhất ........................................................... 16

3.4 Chuyển đổi câu truy vấn có liên từ luận lý ................................................................... 17

CHƯƠNG 4 21

PHƯƠNG PHÁP BIÊN DỊCH ......................................................... Error! Bookmark not defined.

4.1 Các bước của giải thuật ................................................................................................ 21

4.1.1 Phân tách câu truy vấn ............................................................................................23

4.1.2 Nhận biết thực thể có tên .........................................................................................23

4.1.3 Nhận biết thực thể không tên ...................................................................................23

4.1.4 Nhận biết tính từ .....................................................................................................24

4.1.5 Nhận biết từ quan hệ ...............................................................................................24

4.1.6 Xác định lớp của thực thể ........................................................................................24

4.1.7 Gom các thực thể ....................................................................................................25

4.1.8 Xác định quan hệ ẩn ................................................................................................26

4.1.9 Xác định loại quan hệ giữa các thực thể ..................................................................26

4.1.10 Xoá bỏ quan hệ không phù hợp ...............................................................................29

4.1.11 Xác định quan hệ giữa tính từ và thực thể................................................................30

4.1.12 Xây dựng đồ thị ý niệm ...........................................................................................33

4.2 Tập luật ....................................................................................................................... 33

4.2.1 Cấu trúc của hệ thống luật .......................................................................................34

4.2.2 Cấu trúc thành phần điều kiện của luật ....................................................................35

4.2.3 Cấu trúc thành phần hành động của luật ..................................................................35

4.2.4 Xây dựng một số luật đặc biệt .................................................................................36

4.2.5 Xây dựng từ điển luật ..............................................................................................37

4.3 Kết quả thí nghiệm....................................................................................................... 39

CHƯƠNG 5 47

ĐỒ THỊ Ý NIỆM ............................................................................. Error! Bookmark not defined.

Lưu trữ đồ thị............................................................................................................... 55 5.1

Hiển thị đồ thị ................................................................ Error! Bookmark not defined. 5.2

CHƯƠNG 6 62

KẾT LUẬN 62

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

PHỤ LỤC A: TẬP CÂU MẪU TREC 2002 .............................................................................................68

PHỤ LỤC C: ĐỒ THỊ Ý NIỆM SINH ĐÚNG TỪ TREC 2002 TRƯỚC KHI LÀM GIÀU ONTOLOGY .............73

PHỤ LỤC D: ĐỒ THỊ Ý NIỆM SINH ĐÚNG TỪ TREC 2002 SAU KHI LÀM GIÀU ONTOLOGY ..................74

DANH MỤC HÌNH

Hình 2.1: Ví dụ về đồ thị ý niệm. ............................................... Error! Bookmark not defined.

Hình 2.2: Ví dụ về biểu diễn câu truy vấn sử dụng HA (Hypostatic abstraction). ...............Error! Bookmark not defined.

Hình 2.3: Ví dụ về biểu diễn câu truy vấn lồng nhau sử dụng đỉnh truy vấn con. ...............Error! Bookmark not defined.

Hình 3.1: Ví dụ về biểu diễn câu truy vấn "How many". ..........................................................13

Hình 3.2: Ví dụ về biểu diễn câu truy vấn "How many" ở dạng rút gọn. ...................................13

Hình 3.3: Ví dụ về biểu diễn tổng quát cho câu truy vấn "How many". ....................................13

Hình 4.1: Mô tả các bước dùng để xây dựng đồ thị ý niệm cho câu truy vấn. ............................22

Hình 4.2: Xác định loại quan hệ giữa hai thực thể ei và ej. ........................................................27

Hình 4.3: Lược đồ ánh xạ kiểu quan hệ của bộ ba truy vấn. ......................................................28

Hình 4.4: Xác định loại quan hệ giữa tính từ adj và thực thể. ....................................................31

Hình 4.5: Lược đồ ánh xạ kiểu quan hệ giữa tính từ và thực thể. ..............................................32

Hình 4.6: Cấu trúc tập thành phần TransformRules và rule. ......................................................34

Hình 4.7: Cấu trúc của thành phần điều kiện luật. .....................................................................36

Hình 4.8: Ví dụ về thành phần premise.....................................................................................36

Hình 4.9: Cấu trúc của thành phần hành động. .........................................................................37

Hình 4.10: Cấu trúc từ điển quan hệ. ..........................................................................................38

Hình 4.11: Ví dụ một luật hoàn chỉnh. ........................................................................................38

Hình 4.12: Ví dụ một số thành phần trong từ điển. .....................................................................38

Hình 4.13: Ví dụ về biểu diễn câu truy vấn “Queried relation”. ..................................................42

Hình 4.14: Ví dụ về biểu diễn câu truy vấn “Advert / Temporal”. ..............................................42

Cấu trúc dữ liệu sử dụng để lưu trữ đồ thị ý niệm kết quả. ........ Error! Bookmark not Hình 5.1: defined.

Cấu trúc dữ liệu sử dụng để hiển thị đồ thị ý niệm kết quả. ....... Error! Bookmark not Hình 5.2: defined.

Hình 5.3: Ví dụ về kết quả phương pháp lưu trữ và hiển thị đồ thị ý niệm.Error! Bookmark not defined.

DANH MỤC BẢNG

Bảng 4.1: Bảng thuộc tính thành phần premise. ........................................................................35

Bảng 4.2: Mô tả các thuộc tính của thành phần entry. ...............................................................38

Bảng 4.3: Kết quả thực nghiệm trên TREC 2002 khi chưa áp dụng phương pháp đề nghị. ........40

Bảng 4.4: Kết quả thực nghiệm trên TREC 2002 sau khi áp dụng phương pháp đề nghị. ..........40

Bảng 4.5: Kết quả thực nghiệm trên TREC 2002 sau khi làm giàu Ontology. ...........................41

Bảng 4.6: Bảng tổng kết kết quả cuối cùng đạt được trên tập TREC 2002. ................................43

Bảng 4.7: Kết quả thực nghiệm trên TREC 2007 khi chưa áp dụng phương pháp đề nghị. ........44

Bảng 4.8: Kết quả thực nghiệm trên TREC 2007 sau khi áp dụng phương pháp đề nghị. ..........44

Bảng 4.9: Kết quả thực nghiệm trên TREC 2007 sau khi làm giàu Ontology. ...........................45

Bảng 4.10: Bảng tổng kết kết quả cuối cùng đạt được trên tập TREC 2007. ................................46

CHƯƠNG 1

TỔNG QUAN

1.1 Giới thiệu

Kể từ khi ra đời đến nay, World Wide Web (WWW) đã làm thay đổi rất nhiều cách con người

trao đổi và tiếp cận với thông tin, tri thức. Và đối với nền kinh tế tri thức hiện nay, tầm quan trọng

của WWW càng lớn hơn. Điều đó đặt ra yêu cầu là: phải làm sao để quá trình khai thác tri thức từ

WWW đạt được hiệu suất tối ưu. Muốn vậy, một giải pháp là phải tự động hóa được quá trình đó;

nói cách khác, máy móc phải có khả năng khai thác thông tin trên WWW với một độ chính xác cao.

Hiện nay, đã có những công cụ phần mềm nhắm đến mục tiêu đó. Nổi bật nhất có lẽ là các động

cơ tìm kiếm dựa trên từ khóa (keyword – based search engine), như động cơ tìm kiếm của Google,

Yahoo,... Tuy đã đạt được những thành công nhất định, nhưng các hệ thống này còn có những

khuyết điểm làm cho người sử dụng chưa được hài lòng. Có thể nêu ra như:

 Kết quả trả về cho một truy vấn là nhiều, nhưng độ chính xác lại thấp. Người dùng phải tốn

nhiều thời gian với những kết quả không thích hợp.

 Kết quả trả về hoàn toàn phụ thuộc vào từ khóa được cung cấp. Trong khi, theo mong muốn

của con người, thì các truy vấn tương tự nhau về mặt ngữ nghĩa phải dẫn đến những kết quả

như nhau.

Do công cụ tìm kiếm chủ yếu chỉ so trùng, mà chưa “hiểu” được nội dung của thông tin chứa

trên WWW và nội dung của câu truy vấn, nên dẫn đến những hạn chế trên.

Như vậy, để làm tăng hiệu quả của quá trình tìm kiếm tự động, một hướng tiếp cận là làm cho

máy tính “hiểu” được nội dung của thông tin: thông tin được lưu trữ trên WWW và thông tin trong

câu truy vấn của người dùng.

1

Đề tài này quan tâm đến khía cạnh giúp cho máy tính hiểu được nội dung của câu truy vấn dùng

ngôn ngữ tự nhiên là tiếng Anh. Nhìn chung, việc hướng dẫn cho máy tính xử lý 1 câu truy vấn

bằng ngôn ngữ tự nhiên (bất kỳ) nhằm hiểu được ý nghĩa là khá phức tạp, có thể liệt kê ra một số

khó khăn:

 Ngữ pháp của ngôn ngữ tự nhiên rất đa dạng, cách sử dụng rất linh hoạt. Và một câu có thể

có nhiều ngữ pháp phù hợp (mặc dù đối với con người sẽ không có nghĩa). Dẫn đến không

thể chỉ dựa vào cấu trúc của câu để xác định ngữ nghĩa.

 Cùng một từ nhưng có thể ứng với nhiều từ loại (danh từ, động từ, ...). Muốn hiểu đúng phải

xác định đúng loại từ. Lấy ví dụ: “Time flies like an arrow”. “Time” và “flies” có ít nhất 2

cách hiểu có ý nghĩa: “Time” làm danh từ và “flies” làm động từ, hay “Time” làm động từ

và “flies” làm danh từ.

 Phải giải quyết sự đa hình của từ (morphology) nếu muốn nhận biết đầy đủ các thành phần

của câu. Ví dụ như động từ “fly” có thể có dạng “flies”, “flying”, “flew”.

 Việc xác định quan hệ ngữ nghĩa giữa các đối tượng trong câu đòi hỏi phải có tri thức về các

mối quan hệ phù hợp giữa các đối tượng. Và phải xem xét ngữ cảnh của câu để chọn ra quan

hệ phù hợp nhất.

 Câu có thể hàm chứa những mối quan hệ ngầm giữa các đối tượng, mà không được biểu

hiện ra bằng các từ ngữ biểu diễn quan hệ, vì các mối liên hệ này được con người ngầm thỏa

thuận trên một nền tảng kiến thức chung.

 Một cách thường xuyên, câu truy vấn bằng ngôn ngữ tự nhiên không chặt về ngữ pháp, mà

thường được dùng ở dạng thông dụng không “chuẩn” ngữ pháp.

Tuy có nhiều khó khăn như đã kể trên, nhưng hiện nay các nhóm nghiên cứu về lĩnh vực web

ngữ nghĩa đã đạt được những tiến bộ đáng kể. Và việc xây dựng một động cơ tìm kiếm theo ngữ

nghĩa là khả thi, có thể thành công với những câu truy vấn không quá phức tạp. Vì vậy, đề tài này sẽ

ứng dụng các thành tựu đó để xây dựng một động cơ tìm kiếm cho phép người dùng truy vấn bằng

ngôn ngữ tự nhiên, và trả về tài liệu chứa nội dung cần tìm.

2

1.2 Mục tiêu và phạm vi

Đề tài này sẽ xây dựng một hệ thống tìm kiếm dựa trên ngữ nghĩa. Dữ liệu đầu vào sẽ là một câu

truy vấn bằng tiếng Anh. Hệ thống, sau khi xử lý, sẽ trả về tài liệu chứa thông tin được tìm kiếm

hoặc trả về số liệu được yêu cầu (lúc này không sử dụng chức năng tìm kiếm mà chỉ đưa ra số liệu

trả lời). Đồng thời, để giúp người dùng kiểm tra liệu cách “hiểu” câu truy vấn của hệ thống có đúng

hay không, hệ thống cũng vẽ ra đồ thị ý niệm tương ứng với câu truy vấn đã nhận vào.

Một hệ thống như vậy nếu xây dựng mới hoàn toàn sẽ đòi hỏi rất nhiều thời gian và công sức.

Vì vậy, đề tài sẽ dựa trên hệ thống tìm kiếm ngữ nghĩa cho tiếng Việt (VN-KIM Search) có sẵn

[tham khảo anh Dũng], tái sử dụng nhiều mô-đun không phụ thuộc vào ngôn ngữ, như mô-dun chú

giả, đánh chỉ mục, gom cụm, truy xuất tài liệu, chỉ tập trung làm mới mô-dun xử lý câu truy vấn.

Hệ thống sẽ bảo đảm được khả năng xử lý những câu truy vấn tiếng Anh đơn giản, chỉ bao gồm

danh từ, động từ, từ để hỏi và giới từ. Ví dụ như câu truy vấn: “What actress starred in “The Lion in

Winter” ?”. Đây là khả năng mà hiện nay VN-KIM Search đã làm được cho tiếng Việt.

Luận văn không chỉ dừng lại ở những câu truy vấn đơn giản như ví dụ trên, mà còn nhắm đến

mục tiêu trả lời được những câu truy vấn phức tạp hơn. Đó là câu truy vấn có liên từ luận lý, tính từ

định tính, tính từ định lượng, tính từ so sánh nhất, và lượng từ. Lấy ví dụ như các câu truy vấn sau:

“Who was biographer and Samuel Johnsons's friend?” chứa liên từ luận lý.

“What famous model was married to Billy Joel?” chứa tính từ định tính.

“What is the oldest university in the US?” chứa tính từ định lượng.

“What is the highest dam in the U.S.?” và “What is the most common kind of skin cancer

in the U.S.?” chứa tính từ so sánh nhất.

“How many films did Ingmar Bergman make?” chứa lượng từ.

Hiện đã có nghiên cứu của nhóm VN-KIM để biên dịch những câu truy vấn dạng này từ ngôn

ngữ tự nhiên sang đồ thị ý niệm. Luận văn này sẽ ứng dụng thành quả nghiên cứu đó, đồng thời mở

3

rộng thêm một số khả năng khi xử lý những câu truy vấn dạng này. Đầu tiên là khả năng đề xuất đồ

thị ý niệm khả áp dụng ngay cả khi quan hệ với tính từ trong câu truy vấn không có trong cơ sơ tri

thức. Mục đích là làm ta có thể đánh giá tính chính xác của quá trình “hiểu” câu truy vấn của hệ

thống mà không bị quá lệ thuộc vào cơ sơ tri thức. Ví dụ như sau:

“What is the longest dam in the U.S.?” Mặc dù quan hệ giữ “dam” và “long” không có trong

cơ sơ tri thức, nhưng ta vẫn có thể cung cấp đồ thị ý niệm cho người dùng (với quan hệ “ảo” được

vẽ màu xanh lá).

Hình 1.1 Đồ thị có đề xuất quan hệ không tồn tại trong cơ sở tri thức

Ngoài ra, để truy xuất được tài liệu, thì chỉ ngừng lại ở đồ thị là chưa đủ, cần phải chuyển đồ thị

đó sang ngôn ngữ SeRQL, là ngôn ngữ dùng để truy xuất cơ sở tri thức ngữ nghĩa. Luận văn này sẽ

đề xuất cách thức chuyển từ đồ thị của những câu truy vấn dạng này sang truy vấn SeRQL để lấy về

thực thể (entity) cần tìm.

Luận văn cũng đề xuất cách xử lý câu truy vấn có chứa so sánh hơn của tính từ định lượng. Các

câu truy vấn có so sánh hơn với một hằng số, hoặc so sánh hơn với một thực thể, như “What dam in

the U.S. is higher than 1200 meters?”, “What dam is higher than Dworshak in the U.S.?” cũng sẽ

được chuyển sang đồ thị ý niệm, rồi chuyển sang câu truy vấn SeRQL tương ứng.

4

1.3 Cấu trúc luận văn

Chương 1 đã trình bày khái quát động cơ, mục đích, ý tưởng thực hiện đề tài. Tiếp theo sau

Chương 1 là phần trình bày chi tiết về ý tưởng và phương pháp của chúng tôi để đạt được mục đích

đã đề ra.

Chương 2 trình bày những nghiêu cứu và hệ thống liên quan đến việc chuyển đổi câu truy vấn

tiếng Anh sang đồ thị ý niệm. Mục 2.1 trình bày phương pháp rút trích quan hệ trong câu truy vấn.

Sơ lược giới thiệu về đồ thị ý niệm được trình bày ở Mục 2.2.

Chương 3 trình bày cách tiếp cận vấn đề với việc giải quyết câu truy vấn hỏi về số lượng được

trình bày tại Mục 3.1, giải quyết cho câu truy vấn có chứa tính từ được trình bày tại Mục 3.2, giải

quyết cho câu truy vấn có chứa tính từ so sánh nhất được trình bày tại Mục 3.3 và giải quyết cho

câu truy vấn có chứa liên từ luận lý sẽ được trình bày tại Mục 3.4.

Chương 4 trình bày phương pháp biên dịch câu truy vấn tiếng Anh sang đồ thị ý niệm. Mục 4.1

sẽ mô tả các bước trong giải thuật xây dựng đồ thị ý niệm cho câu truy vấn. Mục 4.2 trình bày chi

tiết về tập luật ánh xạ. Những kết quả đạt được của đề tài sẽ được tổng kết tại Mục 4.3.

Chương 5 trình bày chi tiết phương pháp lưu trữ và hiển thị đồ thị ý niệm.

Chương 6 đưa ra kết luận và đề nghị hướng phát triển cho tương lai. Phần phụ lục giới thiệu tập

câu hỏi mẫu TREC 2002, TREC 2007 cùng các đồ thị ý niệm đã được sinh đúng cho những câu truy

vấn rút ra từ hai tập câu hỏi mẫu này.

5

CHƯƠNG 2

KIẾN THỨC NỀN TẢNG

2.1 Rút trích quan hệ

Rút trích quan hệ là xác định mối quan hệ ngữ nghĩa giữa cặp các thành phần không có cấu trúc

hay bán cấu trúc trong văn bản ngôn ngữ tự nhiên. Rút trích quan hệ dựa vào Ontology liên quan tới

hai công việc chính: xác định mối quan hệ giữa hai thành phần đã biết chủ yếu dựa trên miền

Ontology và khám phá các mối quan hệ mới giữa hai ý niệm không có trên miền Ontology. Ví dụ

trong câu “Bill Gates is chairman and chief software architect of Microsoft Corporation”, tồn tại

quan hệ theo kiểu của ACE (Automatic Content Extraction) là EMPLOYMENT.exec giữa hai thực

thể có tên là “Bill Gates” thuộc lớp PERSON.Name và “Mircrosoft Corporation” thuộc lớp

ORGANIZATION.Commercial. Có nhiều kỹ thuật rút trích quan hệ, dựa trên luật (rule-based), dựa

trên đặc điểm (feature-based) và phương pháp kernel (kernel-based) dưới đây trình bày một số

nghiên cứu về rút trích quan hệ:

 Các phương pháp dựa trên luật sử dụng các luật của ngôn ngữ để nắm bắt các mẫu quan

hệ khác nhau. Hệ thống [8] rút trích quan hệ từ một quá trình phân tích cú pháp, do đó kết quả

của nó phụ thuộc hoàn toàn vào cây cú pháp.

 Các phương pháp rút trích dựa trên đặc điểm [21] sử dụng các đặc điểm của ngôn ngữ

như đặc điểm từ vựng, đặc điểm cú pháp và đặc điểm ngữ nghĩa. Những phương pháp này rất

hiệu quả cho việc rút trích quan hệ. Tuy nhiên, vấn đề gặp phải là các đặc điểm phải được mô

tả thủ công và cấu trúc thông tin trong cây cú pháp không được bảo toàn trong cây đặc điểm

(Là cây biểu diễn các đường nối không kết thúc giữa hai thực thể trong cây cú pháp).

 Các phương pháp dựa trên kernel chú trọng vào việc sử dụng các cây kernel riêng lẻ để

khai thác đặc điểm cấu trúc. Hệ thống [19] xây dựng một quan hệ kernel trên cây cú pháp cho

việc rút trích quan hệ. Kernel so trùng các node từ gốc cho tới lá một cách đệ quy theo từng lớp

từ trên xuống.

6

Tuy nhiên các nghiên cứu trên chỉ chú trọng vào rút trích quan hệ giữa các thực thể có tên đã

biết. Để xây dựng được đồ thị ý niệm, ngoài việc rút trích quan hệ giữa các thực thể có tên còn phải

rút trích quan hệ giữa các thực thể không tên với nhau, hay các quan hệ giữa các thực thể có tên với

thực thể không tên.

2.2 Đồ thị ý niệm (Conceptual Graph)

2.2.1 Sơ lược về đồ thị ý niệm

Đồ thị ý niệm là một hình thức biểu diễn logic (logical formalism) vừa có tính trực quan, vừa có

sự chính xác. Về hình thức, đây là một đồ thị tạo ra bởi các đỉnh và các cạnh (có thể có hướng hoặc

không có hướng). Nhờ sử dụng cách biểu diễn đồ họa trực quan đó, đồ thị cho phép con người

nhanh chóng có được một cái nhìn tổng quan, dễ nắm bắt ý nghĩa. Về nội dung, đồ thị ý niệm có thể

được ánh xạ trực tiếp sang logic vị từ (predicate logic). Nhờ đó, có thể biểu diễn ngữ nghĩa một cách

chính xác, giữ được tính chính xác về mặt logic. Với những đặc điểm đó, đồ thị ý niệm vừa dễ tiếp

cận đối với con người, vừa khả xử lý đối với máy tính.

Và đồ thị ý niệm đã được dùng như là một hình thức biểu diễn tri thức, là một ngôn ngữ trung

gian cho việc chuyển đổi qua lại giữa hình thức biểu diễn hướng máy tính và ngôn ngữ tự nhiên.

“Tim Berners Lee, người phát minh của WWW, kết luận rằng các CG có thể dễ dàng tích hợp với

Semantic Web. Nó cũng được chỉ ra trong là có một ánh xạ chặt giữa CG và ngôn ngữ RDF (ko

hiểu đoạn này >.<).” [tham khao HA].

“Trong bài báo đầu tiên công bố liên quan tới đồ thị ý niệm, Sowa đã định nghĩa đồ thị ý niệm

như sau: Chỗ này ta nghĩ chỉ cần nói: Sowa đã định nghĩa dtyn trong 1 bài báo của mình:… rồi trích

dẫn đoạn định nghĩa thôi

Đồ thị ý niệm là một đồ thị hữu hạn, liên thông, không có hướng, lưỡng phân với những nút

thuộc một loại được gọi là ý niệm (hoặc khái niệm – concepts) và những nút thuộc loại còn lại được

gọi là quan hệ khái niệm (conceptual relations).” [tham khao HA]

7

Như vậy, đồ thị ý niệm thuộc loại đồ thị phân đôi, và bao gồm 2 loại đỉnh: các đỉnh khái niệm và

các đỉnh quan hệ. Trong đó, các đỉnh khái niệm chỉ liên kết với các đỉnh quan hệ bởi các cạnh và

ngược lại.

Đỉnh khái niệm được biểu diễn bằng hình chữ nhật có nhãn là kiểu khái niệm kết hợp với tham

chiếu. Đỉnh quan hệ có hình oval với nhãn chính là kiểu quan hệ của nó. Mỗi đỉnh quan hệ có thể

liên kết với nhiều đỉnh khái niệm bằng các cạnh có hướng. Để ngắn gọn, chúng ta sẽ gọi đỉnh quan

FIELD: CS

IN

STUDENT: John

SUBJECT: *

STUDY

hệ, đỉnh khái niệm lần lượt là quan hệ, khái niệm.

[hình tham khảo CDT]

Hình trên là đồ thị ý niệm cho câu “John is a student. There is a subject. CS is a field of study.

The subject is in CS. John studies the subject”. Hoặc ngắn gọn hơn là “John studies a subject in

CS”. (Đoạn này nếu có thể ta nghĩ mình nên tìm một ví dụ khác tương tự, vì ngay cả ví dụ mà cũng

phải tham khảo có thể tạo cho người đọc cảm giác mình chưa hiểu kỹ về nó)

Trong định dạng văn bản, các khái niệm và các quan hệ có thể được biết trong dấu ngoặc vuông

và ngoặc tròn như sau:

[STUDENT: John]→(STUDY)→[SUBJECT: *]→(IN)→[FIELD: CS]

Trong ví dụ này, [STUDENT: John], [SUBJECT:*], [FIELD: CS] là các khái niệm với

STUDENT, SUBJECT và FIELD trở thành kiểu khái niệm, trong khi đó (STUDY) và (IN) là các

quan hệ với STUDY và IN là các kiểu quan hệ. Các tham khảo John và CS là các tham chiếu xác

định. Tham chiếu “*” là tham chiếu tổng quát ám chỉ tới một thực thể không xác định.

Đồ thị ý niệm được sử dụng để kiểm tra tính chính xác của quá trình dịch câu truy vấn trong đề

tài, bên cạnh các tham chiếu xác định và tham chiếu tổng quát, được bổ sung thêm tham chiếu nghi

vấn. Tham chiếu nghi vấn biểu diễn cho thực thể được truy vấn trong câu. Một đồ thị ý niệm truy

8

vấn là một đồ thị ý niệm mà các tham chiếu có thể là tham chiếu xác định, tham chiếu tổng quát

hoặc là tham chiếu nghi vấn được biểu diễn bằng dấu “?”.

2.2.2 Đồ thị ý niệm mở rộng

Đồ thị ý niệm mở rộng [tham khảo HA] là đồ thị ý niệm có sử dụng thêm một khái niệm đặc

biệt, gọi là đỉnh truy vấn con. Đó là một đỉnh khái niệm, nhưng có kiểu khái niệm riêng, và tham

chiếu đến thực thể của nó là một đồ thị ý niệm khác. Tức là, bên trong đỉnh truy vấn con là nội dung

một đồ thị ý niệm truy vấn tri thức. Đỉnh truy vấn con được biểu diễn bằng hình chữ nhật tròn góc

(Ta nghĩ chỗ này mình nên nói: trong tài liệu (hay luận văn) này, đỉnh truy vấn con được biểu diễn

bằng hình chữ nhật vát góc, vì các ví dụ sau này đâu phải tròn góc). Ta xét một ví dụ minh họa: ta

có câu truy vấn lồng nhau như sau: “Tìm tên của những giảng viên có tên trùng với tên của những

giảng viên tại trường Đại học Bách Khoa”. Câu truy vấn này sẽ được biểu diễn như sau:

[hình tham khảo HA]

Trong đề tài [tham khảo HA], đỉnh truy vấn con này được sử dụng phần lớn trong các phương

pháp đề xuất sẽ được bàn đến ở những phần tiếp theo.

9

2.3 Câu truy vấn SeRQL [tham khảo

http://www.openrdf.org/doc/sesame2/2.3.1/users/ch09.html #section-numerical-comparisons]

SeRQL (Sesame RDF Query Language) là một ngôn ngữ truy vấn cơ sở tri thức. Tương tự như

SQL được sử dụng làm ngôn ngữ truy vấn trên các cơ sở dữ liệu quan hệ, SeRQL được sử dụng trên

các cơ sở dữ liệu viết bằng ngôn ngữ RDF.

Trong SeRQL, có 2 loại câu truy vấn: một loại sẽ trả về một bảng các giá trị (một tập các ràng

buộc (binding) giữa biến với giá trị, tương tự như khi truy vấn với SQL), loại còn lại sẽ trả về một

đồ thị RDF (RDF graph). Trong đề tài này chỉ sử dụng loại thứ nhất, gọi là select queries (phiên bản

2.3.2), sẽ được trình bày sau đây.

Đối với 1 câu truy vấn thuộc loại select queries , sẽ có 8 mệnh đề có thể được sử dụng, đó là:

SELECT, FROM, FROM CONTEXT, WHERE, ORDER BY, LIMIT, OFFSET và USING

NAMESPACE. Chỉ có mệnh đề SELECT là bắt buộc, các mệnh đề còn lại có thể không có mặt

trong câu truy vấn. Các mệnh đề SELECT, FROM, WHERE và ORDER BY là những mệnh đề sẽ

được sử dụng để truy vấn trong đề tài này.

Mệnh đề SELECT ở SeRQL cũng tương tự như trong SQL, sẽ chỉ ra các biến mà ta cần trả về

giá trị. Nếu truy vấn thành công, tập kết quả trả về sẽ là các giá trị được ràng buộc với các biến liệt

kê trong mệnh đề SELECT. Ví dụ [tham khảo

SELECT O, S FROM {S} rdfs:label {O}

http://www.openrdf.org/doc/sesame2/2.3.1/users/ch09.html#section-numerical-comparisons]:

Mệnh đề FROM ở SeRQL cũng tương tự như trong SQL, nhưng, thay vì chỉ ra các bảng (table)

có chứa dữ liệu, người sẽ phải chỉ ra các biểu thức đường đi (path expression) có chứa dữ liệu trong

cơ sở tri thức RDF. Trong ví dụ trên, biểu thức đường đi là “{S} rdfs:label {O}” .

Mệnh đề WHERE, cũng tương tư như SQL, là nơi để người dùng đặc tả các ràng buộc mà các

biến phải thỏa mãn. Nếu có nhiều ràng buộc, chúng có thể được liên kết bằng các từ khóa AND,

OR, NOT, là các toán tử của đại số Bool.Trong mệnh đề WHERE, ta cũng có thể sử dụng câu truy

10

vấn lòng nhau (nested query) và sử dụng từ khóa ALL để biểu diễn ràng buộc đối với một tập giá

trị. Ví dụ [tham khảo http://www.openrdf.org/doc/sesame2/2.3.1/users/ch09.html#section-

SELECT highestValue FROM {node} ex:value {highestValue} WHERE highestValue >= ALL ( SELECT value

FROM {} ex:value {value}

)

numerical-comparisons]:

Để sắp xếp kết quả trả về theo một thứ tự nhất định, người dùng có thể sử dụng mệnh đề

ORDER BY, kết hợp các từ khóa DESC (giảm dần) và ASC (tăng dần – mặc định). Có thể kết hợp

sắp xếp trên nhiều biến trả về, cách nhau bởi dấu “,”. Ví dụ [tham khảo

SELECT Countr, Population FROM {Country} ex:population {Population} ORDER BY Population DESC

http://www.openrdf.org/doc/sesame2/2.3.1/users/ch09.html#section-numerical-comparisons]:

Ngoài ra, SeRQL cũng hỗ trợ 3 toán tử UNION, INTERSECT và MINUS để thực hiện kết hợp,

giao và loại trừ các tập kết quả. Ví dụ [tham khảo

SELECT title FROM {book} dc10:title {title}

UNION

SELECT title FROM {book} dc11:title {title}

http://www.openrdf.org/doc/sesame2/2.3.1/users/ch09.html#section-numerical-comparisons]:

Đề tài sẽ sử dụng các toán tử tập hợp này vào việc giải quyết các câu truy vấn có liên từ luận lý.

(Có nên nói thêm về Sesame, S-Lucene ko? Đề tài mình đụng đến mấy cái đó để lấy tài liệu,

nhưng mà mấy phần sau lại ko nhắc đến nên nói ở đây cũng hợp lý)

11

CHƯƠNG 3

PHÂN TÍCH VẤN ĐỀ VÀ PHƯƠNG PHÁP GIẢI

QUYẾT

3.1 Chuyển đổi câu truy vấn với từ để hỏi “How many”

Về cơ bản, chúng tôi thấy rằng việc biểu diễn các câu truy vấn hỏi về số lượng (Có từ hỏi là

“How many”) bằng đồ thị ý niệm đòi hỏi phải giải quyết được hai vấn đề sau:

 Thứ nhất, ta phải biểu diễn được phạm vi mà câu truy vấn muốn đề cập.

 Thứ hai, ta phải biểu diễn được đối tượng hay thuộc tính mà câu truy vấn muốn đề cập.

Thật vậy, lấy trường hợp của ví dụ trong Hình 2.2, nếu như PERSON có thêm thuộc tính về

salary, thì với biểu diễn như vậy ta không thể biết được câu truy vấn muốn hỏi độ trung bình về

tuổi, hay độ trung bình về lương.

Trong giải pháp đề nghị này, chúng tôi sẽ sử dụng đồ thị lồng nhau (nested CG), cụ thể là ở đây

chúng tôi sẽ sử dụng đỉnh truy vấn con để giải quyết vấn đề về biểu diễn phạm vi mà câu truy vấn

muốn bao phủ, và sử dụng liên kết đồng tham chiếu để biểu diễn đối tượng mà câu truy vấn muốn

đề cập.

Với giải pháp đề nghị, câu truy vấn “How many students are there in Computer Science

Department?” sẽ được biểu diễn như Hình 3.1.

12

Hình 3.0.1: Ví dụ về biểu diễn câu truy vấn "How many".

Để ngắn gọn, chúng tôi sẽ định nghĩa một đường liên kết mới thay thế đường liên kết đồng tham

chiếu cho việc biểu diễn đối tượng mà câu truy vấn muốn đề cập. Trong tài liệu này chúng tôi đề

xuất biểu diễn bằng đường liên kết nét đôi. Biểu diễn dạng ngắn gọn cho ví dụ trên như sau:

Hình 3.0.2: Ví dụ về biểu diễn câu truy vấn "How many" ở dạng rút gọn.

Sau đây là giải pháp đề xuất cho việc giải quyết mẫu câu truy vấn có từ để hỏi là “How many”.

Mẫu câu truy vấn này sẽ có dạng sau, với RW là từ quan hệ, S là chủ thể, O là khách thể:

How many S RW O

Đầu tiên, chúng ta sẽ xây dựng đỉnh truy vấn con để biểu diễn câu S RW O. Sau đó, chúng ta

định nghĩa quan hệ COUNT gắn với đỉnh truy vấn con vừa tạo. Một đường liên kết nét đôi sẽ được

nối từ quan hệ COUNT tới đỉnh khái niệm S trong đỉnh truy vấn con. Biểu diễn tổng quát cho mẫu

truy vấn “How many” như Hình 3.3

Hình 3.0.3: Ví dụ về biểu diễn tổng quát cho câu truy vấn "How many".

13

3.2 Chuyển đổi câu truy vấn có tính từ

Trong [16] đã đưa ra giải pháp sau để giải quyết vấn đề biểu diễn tính từ của thực thể. Ví dụ, để

trả lời câu truy vấn “What famous model was married to Billy Joel?” yêu cầu Ontology phải có khả

năng thể hiện thuộc tính famous của các người mẫu.

 Giải pháp 1: Định nghĩa lớp FAMOUSMODEL, ví dụ, đối với những người mẫu mà nổi

tiếng. Nó sẽ tạo ra nhiều lớp con của các người mẫu cho những độ khác nhau của thang đo độ

nổi tiếng.

 Giải pháp 2: Định nghĩa kiểu quan hệ FAMEPROPERTY có miền lớp là MODEL và

range lớp là STRING. Cách này gây ra vấn đề của việc so trùng các giá trị String sau đó.

Ở giải pháp thứ nhất nêu trên, ta thấy giải pháp này sẽ dẫn đến bùng nổ số lượng lớp mới phải

định nghĩa. Đặc biệt một vấn đề nảy sinh là việc đưa ra các thang đo để có thể định lượng được các

tính từ. Điều này chỉ có thể giải quyết được trong một số trường hợp đối với các tính từ như “tall”,

“high”… Ví dụ, ta có thể quy ước một ngôi nhà được gọi là cao khi kích thước chiều cao lớn hơn

100m. Tuy nhiên có những tính từ mà con người khó có thể định lượng được như là “good”,

“famous”… thì việc định nghĩa một thang đo cho những tính từ như vậy sẽ gặp nhiều khó khăn.

Ngoài ra, các tác giả trong [10], [11] đã nêu ra rằng các ý nghĩa của các tính từ còn phụ thuộc

vào ngữ cảnh. Ví dụ khi nói: “Peter is tall for a gymnast” thì ý nghĩa ở đây là Peter chỉ được xem là

cao trong ngữ cảnh so sánh với các vận động viên thể dục, còn đối với việc so sánh với người bình

thường thì điều này chưa hẳn đã đúng. Từ nhận xét này, các tác giả trong [10], [11] đã đề xuất giải

pháp khái niệm hóa các tính từ bằng phương pháp động. Các tác giả đề nghị xây dựng các lớp so

sánh để biểu diễn cho ngữ cảnh và sinh ra các quan hệ để biểu diễn độ tương quan về tính chất so

với lớp so sánh này.

Giải pháp thứ hai cho ta một cách mềm dẻo hơn khi biểu diễn các tính từ cho thuộc tính. Vấn đề

nảy sinh của cách thứ hai là việc so trùng giá trị String có thể được giải quyết bằng một từ điển các

từ đồng nghĩa, ví dụ như là WordNet. Tuy nhiên, với giải pháp này, ý nghĩa của các tính từ chỉ có

thể hiểu bởi con người, còn máy tính không thể suy luận được từ việc biểu diễn này. Ví dụ với cách

14

biểu diễn như vậy đối với những câu hỏi có dạng như: “Một ngôi nhà là cao hay không khi chiều

cao của nó lớn hơn 100m?” thì máy sẽ không đủ tri thức để đưa ra câu trả lời.

Từ việc phân tích trên ta thấy mỗi giải pháp đều có ưu, nhược điểm và khó có thể trả lời được

rằng giải pháp nào là tốt hơn giải pháp nào. Do đó trong tài liệu này, chúng tôi đề xuất cả hai giải

pháp để thể hiện các tính từ chỉ tính chất, thuộc tính của thực thể mà sẽ được trình bày ngay dưới

đây.

Mẫu câu chứa các tính từ chỉ tính chất, thuộc tính của thực thể sẽ có dạng sau, với S là chủ thể,

ADJ là tính từ, O là khách thể:

ADJ S RW O

Hoặc

S RW ADJ O

Phương pháp đề xuất cho mẫu câu truy vấn dạng này theo “Giải pháp 1” là định nghĩa kiểu

quan hệ HASPROPERTY gắn với thực thể ngay sau ADJ và range lớp là STRING. Các mẫu truy

vấn ở trên sẽ được biểu diễn thành:

[String: *] ← (HASPROPERTY) ← S → (RW) → O

Hoặc

S → (RW) → O → (HASPROPERTY) → [String: *]

Phương pháp đề xuất cho mẫu câu truy vấn dạng này theo “Giải pháp 2” là ứng với mỗi tính từ

ta sẽ định nghĩa lớp con của thực thể ngay sau ADJ mà có tính chất thỏa ADJ theo một độ đo nào

đó. Các mẫu truy vấn ở trên sẽ được biểu diễn thành:

S ← (SubclassOf) ←Sub_S → (RW) → O

Hoặc

S → (RW) → Sub_O → (SubclassOf) → O

Trong đề tài này, phương pháp tiếp cận đã sử dụng cả hai giải pháp nêu trên, trong đó “Giải

pháp 1” được sử dụng để biểu diễn các tính từ định lượng (tall, hight,…), còn “Giải pháp 2” được

sử dụng cho việc biểu diễn các tính từ định tính (famous, good,…).

15

Do đó, câu truy vấn với tính từ định tính “What famous model was married to Billy Joel” sẽ

được biển diễn như Hình 3.4 với lớp FAMOUS_MODEL là lớp con của lớp MODEL trong

Ontology.

Hình 3.4: Ví dụ về biểu diễn tính từ định tính.

Câu truy vấn với tính từ định lượng “How tall is Billy Joel” sẽ được biểu diễn tương ứng như

Hình 3.5.

Hình 3.5: Ví dụ về biểu diễn tính từ định lượng.

3.3 Chuyển đổi câu truy vấn có tính từ so sánh nhất

Đề tài sử dụng đồng thời hai phương pháp để biểu diễn tính từ. Việc chọn cách biểu diễn nào

trong từng trường hợp cụ thể tùy thuộc vào tính từ so sánh nhất cần được biểu diễn thuộc về tính từ

định tính hay định lượng.

Đối với tính từ so sánh nhất thuộc loại định lượng (Ví dụ: tallest, highest), việc giải quyết cho

câu truy vấn loại này cũng tương tự như hướng giải quyết cho loại truy vấn “How many” bằng việc

thay quan hệ COUNT thành quan hệ MIN, MAX tương ứng và đường liên kết sẽ chỉ tới tính từ định

lượng mà câu truy vấn cần đề cập.

Chúng tôi đề xuất giải pháp như sau: Mẫu câu truy vấn tổng quát cho dạng này sẽ có các trường

hợp như bên dưới, với ADJ_EST là cụm tính từ so sánh nhất (most adj, least adj, adjEST,…):

ADJ_EST S RW O

Hoặc

S RW ADJ_EST O

16

Đầu tiên, ta sẽ coi như không có mặt của ADJ_EST và biểu diễn câu S RW O thành một đỉnh

truy vấn con. Sau đó trong đỉnh truy vấn con vừa được tạo này, ta sẽ biểu diễn tính từ ở dạng

nguyên mẫu của ADJ_EST bằng phương pháp đã nêu trong Mục 3.1.2 của Chương 3.

Nhiệm vụ còn lại là định nghĩa quan hệ MIN, MAX chỉ tới đỉnh truy vấn con và một đường liên

kết nét đôi sẽ được nối từ quan hệ MIN, MAX tới biểu diễn tính từ nằm trong đỉnh truy vấn con.

Ví dụ câu truy vấn “What is the highest dam in the U.S.?” sẽ được biểu diễn như Hình 3.6:

Hình 3.6: Ví dụ về biểu diễn câu truy vấn có tính từ so sánh nhất định lượng.

Đối với tính từ so sánh nhất thuộc loại định tính, chúng tôi giải quyết tương tự như cho trường

hợp biểu diễn tính từ định lượng đã trình bày ở Mục 3.2, Chương 3. Theo đó, với câu truy vấn

“What the most famous model was married to Billy Joel?” sẽ được biểu diễn như Hình 3.7 với lớp

MOST_FAMOUS_MODEL là lớp con của lớp MODEL.

Hình 3.7: Ví dụ về biểu diễn câu truy vấn có tính từ so sánh nhất định tính.

3.4 Chuyển đổi câu truy vấn có tính từ

3.4.1 Trường hợp tính từ định tính

17

3.4.2 Trường hợp tính từ định lượng [tham khảo HA]

Với câu có “ADJ”, “S”, “O” lần lượt là tính từ định lượng, chủ từ và động từ, dạng :

ADJ S RW O

Hoặc

S RW ADJ O

Nghiên cứu [tham khảo HA] đề nghị thể hiện mối quan hệ giữa tính từ và thực thể như sau:

 Một quan hệ “hasProperty” sẽ biểu diễn cho tính từ “ADJ”.

 Miền (domain) chủ từ của quan hệ là lớp của thực thể đứng sau “ADJ”.

 Tầm vực (range) của quan hệ là lớp “String”.

Như vậy, khi đã xác định được tính từ và thực thể mà tính từ đi kèm, thì mối quan hệ giữa chúng

được biểu diễn dưới dạng:

[String: *] ← (hasProperty) ← S → (RW) → O

Hoặc

S → (RW) → O → (hasProperty) → [String: *]

Phương pháp này giúp ta có thể lưu trữ được “lượng” của một thuộc tính (định lượng) mà đối

tượng có, mà chưa cần quan tâm đến “độ đo” của thuộc tính đó. Thật vậy, công việc xác định độ

đo cho 1 tính từ khi áp dụng với từng loại thực thể có thể nói là phức tạp và khó làm chính xác.

Ví dụ: “What is the high dam in the U.S.?”, khó có thể xác định khi nào một “dam” là “high”,

chính xác nhất có lẽ là đi tìm chuẩn được quốc tế công nhận để một “dam” là “high”, nhưng

không phải đối tượng nào cũng có một chuẩn quốc tế khi xét đến tính chất “high”. Với phương

pháp trên, ta chỉ cần lưu trữ độ cao của các đối tượng “dam”, còn việc đặt ra chuẩn “high” sẽ là

do người dùng tự đưa ra để chọn những kết quả mong muốn. Nhờ vậy tiết kiệm được công sức,

và đơn giản được cách lưu trữ.

3.5 Chuyển đổi câu truy vấn có tính từ so sánh nhất

18

3.5.1 Trường hợp tính từ định tính

3.5.2 Trường hợp tính từ định lượng [tham khảo HA]

Với câu truy vấn có tính từ định lượng so sánh nhất (Ví dụ: tallest, highest), hướng giải quyết

tương tự như đã trình bày ở 3.3 (cho loại truy vấn “How many”), điểm khác biệt là thay quan hệ

“COUNT” thành quan hệ “MIN”, hoặc “MAX” tương ứng, và đường liên kết sẽ chỉ tới lớp “String”

trong quan hệ ứng với tính từ định lượng mà câu truy vấn cần đề cập.

Cụ thể như sau: xét dạng tổng quát cho câu truy vấn loại này như bên dưới, với “ADJ_EST” đại

diện cho cụm tính từ so sánh nhất (most adj, least adj, adjEST,…):

ADJ_EST S RW O

Hoặc

S RW ADJ_EST O

Đầu tiên, ta sẽ tìm dạng nguyên mẫu “ADJ” của “ADJ_EST” và biểu diễn câu truy vấn theo

phương pháp cho tính từ định lượng đã trình bày ở phần 3.4.2. Lúc này ta đã có được một đỉnh truy

vấn con.

Sau đó, ta xác định xem so sánh nhất của tính từ trong truy vấn là tương ứng với lấy “lượng” lớn

nhất hay lấy “lượng” nhỏ nhất. Ví dụ: “highest” tương ứng với lấy lượng lớn nhất, còn “lowest” sẽ

lấy lượng nhỏ nhất. Nếu là trường hợp đầu tiên thì quan hệ là “MAX”, ngược lại là “MIN”.

Nhiệm vụ còn lại là định nghĩa quan hệ “MAX”, “MIN” chỉ tới đỉnh truy vấn con và một đường

liên kết nét đôi sẽ được nối từ quan hệ này tới lớp “String” trong cách biểu diễn tính từ định lượng.

Ví dụ câu truy vấn “What is the highest dam in the U.S.?” sẽ được biểu diễn như sau:

[hình tham khảo HA]

19

3.6 Chuyển đổi câu truy vấn có tính từ định lượng so sánh hơn

Đề tài này mở rộng biểu diễn thêm một dạng nữa của tính từ định lượng, đó là dạng so sánh hơn.

Trong phần này sẽ đề xuất cách biểu diễn cho 2 dạng so sánh hơn: so sánh hơn với một hằng số, và

so sánh hơn với một thực thể có tên.

Đối với dạng so sánh hơn với một hằng số, mẫu câu tổng quát như sau, với “ADJ_ER” đại diện

cho cụm tính từ so sánh hơn (more adj than, less adj than, adjER than,…):

S RW ADJ_ER CONSTANT

Đầu tiên, ta sẽ biểu diễn mối quan hệ giữa “S” và “ADJ_ER” như 3.4.2. Phần “CONSTANTS”

sẽ được nhận biết như một giá trị thuộc lớp “String”. Sau đó, tùy theo tính từ nguyên gốc là gì, ta sẽ

xác định được quan hệ so sánh hơn là “isGreaterThan” hay “isSmallerThan” . Ví dụ: “higher” sẽ

tương ứng với “isGreaterThan”, còn “lower” sẽ tướng ứng với “isSmallerThan”. Cuối cùng là thêm

quan hệ này vào giữa lớp “String” trong mối quan hệ biểu diễn tính từ và hằng số. Biểu diễn có

dạng như sau:

S → (hasProperty) → [String: *] → (isGreaterThan) → [String: *]

Đối với dạng so sánh hơn với thực thể có tên, mẫu câu tổng quát như sau:

S RW ADJ_ER O

Để biểu diễn dạng này, ta sẽ tìm lần lượt 2 mối quan hệ thực thể - tính từ, đó là S – ADJ và O –

ADJ. Rồi biểu diễn 2 mối quan hệ này như ở 3.4.2. Sau đó, cũng xác định mối quan hệ so sánh là

“isGreaterThan” hay “isSmallerThan” tương tự như trên. Cuối cùng là liên kết 2 lớp “String” bằng

quan hệ này. Biểu diễn có dạng tổng quát sau:

S → (hasProperty) → [String: *] → (isGreaterThan)

↓

S → (hasProperty) → [String: *]

20

CHƯƠNG 4

THIẾT KẾ

4.1 Các bước của giải thuật

Kết quả nghiên cứu của tác giả [18] đã đưa ra một phương pháp dịch câu truy vấn sang đồ thị ý

niệm không dựa vào phân tích cú pháp của câu truy vấn mà dựa trên thực thể cùng các mối liên hệ

giữa chúng. Phương pháp này có các ưu điểm sau:

 Có thể xây dựng đồ thị ý niệm cho các câu truy vấn có hình thức là một câu đầy đủ, hoặc

một đoạn câu. Phương pháp này cũng có thể xây dựng được đồ thị ý niệm cho các câu truy vấn

không đúng cú pháp.

 Dễ dàng chuyển đổi để thực hiện cho các câu truy vấn bằng các ngôn ngữ khác nhau khi

có một Ontology tương ứng.

 Mặc khác phương pháp này cũng rút ngắn thời gian so với phương pháp phân tích cú

pháp câu truy vấn.

Quá trình chuyển đổi câu truy vấn sang đồ thị ý niệm thực chất là quá trình tìm kiếm các thực

thể trong câu truy vấn và xây dựng mối quan hệ giữa chúng dựa vào Ontology. Ta xét câu truy vấn:

“Who is Peter’s son”, ta có Peter là một thực thể có tên thuộc lớp PERSON, son biểu diễn cho một

thực thể thuộc lớp SON, chúng ta gọi là thực thể không tên, và trên Ontology tồn tại quan hệ giữa

hai thực thể này là .

Trong đề tài này, phần hiện thực chương trình đã kế thừa lại hạt nhân xử lý từ kết quả nghiên

cứu của tác giả [18], đồng thời hiệu chỉnh và giải quyết thêm cho những truy vấn hỏi về số lượng,

những truy vấn có chứa tính từ, tính từ so sánh nhất và liên từ luận lý. Một lược đồ tổng quát được

trình bày tại Hình 4.1 với những bổ sung như sau:

21

Để giải quyết truy vấn hỏi về số lượng (“How many”), phương pháp tiếp cận đã hiệu chỉnh Bước

12 (Xây dựng đồ thị ý niệm).

Để giải quyết truy vấn có chứa tính từ và tính từ so sánh nhất, phương pháp tiếp cận đã thêm

Bước 4 (Nhận diện tính từ) và Bước 11 (Xác định quan hệ giữa tính từ và thực thể), đồng thời hiệu

chỉnh Bước 12 (Xây dựng đồ thị ý niệm).

Để giải quyết truy vấn có chứa liên từ luận lý, phương pháp tiếp cận đã thêm Bước 1 (Phân tách

câu truy vấn) và đồng thời hiệu chỉnh Bước 12 (Xây dựng đồ thị ý niệm).

Hình 4.0.1: Mô tả các bước dùng để xây dựng đồ thị ý niệm cho câu truy vấn.

22

Tiếp theo đây, chúng ta sẽ đi vào chi tiết từng bước của giải thuật.

4.1.1 Phân tách câu truy vấn

Bước này được sử dụng nhằm phân tách câu truy vấn có chứa liên từ luận lý AND, OR, NOT

thành các câu truy vấn nguyên tử (là truy vấn mà không có chứa liên từ luận lý trong câu). Như

chúng tôi đã phân tích tại Mục 3.1.4, Chương 3, những câu truy vấn có liên từ luận lý mà ta đang

xem xét là những câu truy vấn có dạng cấu trúc song song. Quá trình phân tách sẽ sử dụng liên từ

luận lý AND, OR, NOT làm từ phân tách. Từ kết quả của bước phân tách này, ta sẽ được một tập

các câu truy vấn nguyên tử.

4.1.2 Nhận biết thực thể có tên

Đề tài sử dụng GATE để nhận diện thực thể có tên dựa trên Ontology PROTON. Các thực thể

có tên là các thực thể xác định. Trên Ontology, các thực thể có tên sẽ có một ID xác định, thuộc về

một lớp xác định, có thông tin về thuộc tính và quan hệ của chúng với các thực thể khác. Ví dụ trên

PROTON, http://www.ontotext.com/kim/2005/04/wkb#Country là lớp của thực thể “Viet Nam” và

thực thể có tên này có ID xác định là http://www.ontotext.com/kim/2005/04/wkb#Country_T.VM.

Quá trình chú thích ngữ nghĩa bằng GATE cho ta kết quả là một tập các thực thể có tên, với các

thông tin về lớp ID của thực thể, lớp của thực thể và các thuộc tính cũng như các mối quan hệ của

thực thể. Các thực thể có tên được ký hiệu là IE.

4.1.3 Nhận biết thực thể không tên

Để xây dựng được đồ thị ý niệm, ngoài việc nhận diện các thực thể có tên, các thực thể không

tên cũng phải được nhận diện một cách đầy đủ và chính xác. Các thực thể không tên là các thực thể

không xác định và không tồn tại trên Ontology, tuy nhiên về mặt ngữ nghĩa, chúng có thể thuộc về

một lớp xác định nào đó trong Ontology, ví dụ các từ “person”, “son”, “father”, “mother”,… là các

thực thể không tên, và trên PROTON, http://www.ontotext.com/kim/2005/04/wkb#Person là lớp

biểu diễn cho các thực thể không tên này.

Công cụ ANNIE trong GATE có thể thực hiện chính xác việc nhận dạng các thực thể không tên.

ANNIE giúp ta tất cả các bước trong quá trình tìm kiếm, công việc của chúng ta là xây dựng một

23

danh sách tên các lớp trong Ontology và lưu vào một tập tin; sau đó, ta sẽ định nghĩa tên tập tin này

vào tập tin chỉ mục có tên là lists.def trong thư mục Gazetteer.

ANNIE cho ta tập các thực thể không tên, và thông tin về lớp của các thực thể không tên đó.

Các thực thể không tên được ký hiệu UE.

4.1.4 Nhận biết tính từ

Bước này nhận biết các tính từ trong câu truy vấn. Các tính từ được chia làm 3 loại:

 Tính từ định tính: famous, beautiful, …

 Tính từ định lượng: tall, hight, …

 Tính từ so sánh nhất: smallest, longest, …

Việc nhận diện tính từ cũng được thực hiện bằng công cụ ANNIE của GATE, điểm khác biệt là

chúng ta cần xây dựng danh sách (lập từ điển) các tính từ định lượng, danh sách các tính từ định

tính và danh sách các tính từ so sánh nhất và ánh xạ chúng vào Gazetteer.

4.1.5 Nhận biết từ quan hệ

Các từ quan hệ được xem là chìa khóa để xác định mối quan hệ giữa các thực thể trong câu truy

vấn. Các từ quan hệ là các giới từ, động từ như: in, on, of, live in, located in, has, is, are, …

Tương tự như nhận diện các thực thể không tên, việc nhận diện từ quan hệ cũng được thực hiện

bằng công cụ ANNIE của GATE, điểm khác biệt là chúng ta cần xây dựng danh sách các từ quan hệ

và ánh xạ chúng vào Gazetteer. Kết quả nhận biết từ quan hệ là tập các từ quan hệ có trong câu truy

vấn. Các từ quan hệ được ký hiệu là RW.

4.1.6 Xác định lớp của thực thể

Trong các câu hỏi bắt đầu bằng What, Who, Where, các từ để hỏi này được xem là một từ biểu

diễn cho một thực thể không tên và chưa xác định được lớp. Nhiệm vụ của bước này là xác định

chính xác lớp thực thể cho các từ để hỏi nêu trên.

24

Đề tài đề xuất phương pháp xác định lớp cho thực thể What như sau:

 Nếu đứng sau What là một thực thể không tên, thì lớp của What được xác định cũng

chính là lớp của thực thể không tên đó. Ví dụ trong câu “What country are Godiva chocolates

from?”, sau What là country, mà ta có country là biểu diễn của thực thể không tên thuộc lớp

COUNTRY, do đó lớp của What được xác định là COUNTRY.

 Ngược lại, nếu sau What không phải là thực thể không tên thì lớp của What được xác

định bởi thực thể có tên đầu tiên sau What và từ quan hệ cuối cùng trong câu. Ví dụ trong câu

“What does CNN stand for?”, CNN là một thực thể có tên thuộc lớp ORGANIZATION và

stand for biểu diễn cho quan hệ HASALIAS, do đó What được xác định là thuộc lớp ALIAS.

Đối với các câu hỏi bắt đầu bằng Who thì từ hỏi Who có thể được hiểu là một thực thể thuộc lớp

PERSON hoặc lớp ORGANIZATION. Bước này xác định lớp của Who dựa vào từ quan hệ và thực

thể đứng sau Who. Ta xét một ví dụ như sau: “Who provides telephone service in Orange County,

California?”, lớp của Who trong trường hợp này được xác định là ORGANIZATION.

4.1.7 Gom các thực thể

Ta xét câu truy vấn “Who are members of the board of the IMG?”, sau Bước 4.1.6 (Xác định lớp

của thực thể), chúng ta được hai thực thể không tên: Who, member thuộc lớp PERSON và một thực

thể có tên IMG thuộc lớp COMPANY. Trong đó Who và member chỉ về cùng một PERSON, là

member của IMG. Do đó, Who và member được gom lại thành một thực thể duy nhất.

Quá trình gom thực thể được thực hiện dựa vào heuristic. Hai thực thể trong câu truy vấn chỉ

được gom lại khi chúng thỏa mãn đồng thời các đặc điểm sau:

 Trong hai thực thể có ít nhất một thực thể không tên.

 Lớp của thực thể không tên là lớp cha của lớp của thực thể còn lại, xét trên miền

Ontology.

 Giữa hai thực thể là dấu phẩy hoặc các từ quan hệ đặc biệt: “is”, “are”, “was”, “were”.

25

4.1.8 Xác định quan hệ ẩn

Một số thực thể trong câu truy vấn đứng liền kề nhau nhưng không xuất hiện từ quan hệ nào ở

giữa chúng. Trong câu “What county is Modesto, California in?”, giữa thực thể Modesto thuộc lớp

CITY và thực thể California thuộc lớp PROVINCE tồn tại mối quan hệ SUBREGIONOF, tuy nhiên

giữa chúng không xuất hiện từ quan hệ nào. Bước này thực hiện việc thêm từ quan hệ cho các thực

thể đứng liền kề nhau hoặc cách nhau bởi dấu phẩy. Việc xác định từ quan hệ dựa vào lớp giữa hai

thực thể và loại quan hệ giữa hai lớp đó trên Ontology. Tuy nhiên trên Ontology, giữa hai lớp có thể

tồn tại nhiều loại quan hệ. Đề tài sắp xếp các loại quan hệ dựa trên mức độ chi tiết về lớp của loại

quan hệ. Quá trình xác định quan hệ ẩn giữa hai thực thể sẽ được tiến hành theo heuristic sau: Ta

liệt kê tất cả quan hệ có thể có giữa hai thực thể đó trong Ontology và chọn ra quan hệ chi tiết nhất.

Ví dụ trong câu truy vấn trên, giữa hai lớp CITY và lớp PROVINCE có thể tồn tại các loại quan hệ

PARTOF, LOCATEDIN và SUBREGIONOF. Trên Ontology PROTON, các loại quan hệ này được

định nghĩa như sau:

 Quan hệ PARTOF được định nghĩa là (ENTITY, PARTOF, ENTITY).

 Quan hệ LOCATEDIN là (ENTITY, LOCATEDIN, LOCATION).

 Quan hệ SUBREGIONOF là (LOCATION, SUBREGIONOF, LOCATION).

Tương ứng trên Ontology PROTON, lớp LOCATION là lớp con của lớp ENTITY. Do đó quan

hệ SUBREGIONOF là quan giữa hai lớp chi tiết nhất nên quan hệ này được chọn.

4.1.9 Xác định loại quan hệ giữa các thực thể

Đây là bước mà các cặp thực thể sẽ được liên kết với nhau bằng từ quan hệ, được gọi là một bộ

ba truy vấn .

Xem xét câu truy vấn “Where is the location of the Orange Bowl?”, từ quan hệ of nằm giữa hai

thực thể là location và Orange Bowl. Đối với câu truy vấn “What state is the Filenes store located

in?”, từ quan hệ in biểu diễn mối quan hệ LOCATEDIN giữa thực thể state và thực thể Filenes

store nằm ở sau thực thể Filenes store. Trong câu “In what country is Angkor Wat?” từ quan hệ in

nằm ở trước thực thể country dùng để biểu diễn mối quan hệ LOCATEDIN giữa thực thể country và

26

thực thể Angkor Wat. Như vậy, từ quan hệ dùng để biểu diễn mối quan hệ giữa hai thực thể có thể

nằm ở giữa, nằm ở sau hoặc nằm ở trước hai thực thể. Khi xem xét trên tập mẫu, từ quan hệ xuất

hiện nhiều nhất là ở giữa hai thực thể. Do đó, để hình thành nên các bộ ba truy vấn

quan hệ, thực thể>, độ ưu tiên sẽ là vị trí của từ quan hệ đối với vị trí của hai thực thể. Ưu tiên thứ

nhất là từ quan hệ nằm giữa hai thực thể, kế tiếp là từ quan hệ nằm sau hai thực thể và cuối cùng là

từ quan hệ sẽ nằm phía trước hai thực thể. Các bộ ba này sau đó sẽ được so trùng với Ontology để

xác định kiểu quan hệ tương ứng có trong Ontology.

Dựa vào các phân tích trên, đề tài đưa ra giải thuật xác định kiểu quan hệ giữa hai thực thể trong

câu truy vấn như sau (Hình 4.2):

Hình 4.0.2: Xác định loại quan hệ giữa hai thực thể ei và ej.

 Bước 1: Xét các từ quan hệ nằm giữa ei và ej. Bằng việc sử dụng tập luật, nếu có từ quan

hệ nào khi kết hợp với ei và ej xác định được kiểu quan hệ giữa ei và ej thì quá trình dừng,

ngược lại qua Bước 2.

 Bước 2: Xét các từ quan hệ nằm ở sau ei và ej, tương tự như Bước 1, nếu không xác định

được kiểu quan hệ giữa ei và ej thì qua Bước 3.

 Bước 3: Xét các từ quan hệ nằm trước ei và ej.

Bằng giải thuật trên, chúng ta xác định được kiểu quan hệ giữa hai thực thể ei và ej, nếu hai thực

thể ei và ej có mối quan hệ với nhau trong ngữ cảnh của câu truy vấn. Quá trình được áp dụng tương

tự cho tất cả các cặp thực thể trong câu truy vấn. Các loại quan hệ tìm được sẽ được thêm vào danh

sách quan hệ RELATION.

Việc xác định kiểu quan hệ được làm bằng cách ứng với mỗi bộ ba

thể> ta sẽ ánh xạ thành . Việc ánh xạ này được thực hiện qua giải

27

pháp lập từ điển (Tập luật) và heuristic. Quá trình ánh xạ được khái quát bằng lược đồ như ở Hình

4.3.

Hình 4.0.3: Lược đồ ánh xạ kiểu quan hệ của bộ ba truy vấn.

Chi tiết cho lược đồ tại Hình 4.3 được diễn dịch như sau:

 Xét mối quan hệ có dạng [C1, S1] – RW – [C2, S2] với:

o RW là từ quan hệ,

o C1 và C2 lần lượt là lớp của thực thể thứ nhất và thứ hai,

o S1 và S2 lần lượt là giá trị chuỗi ban đầu của thực thể thứ nhất và thứ hai.

 Ta sẽ lần lượt xây dựng các ánh xạ sau đây:

o Ánh xạ từ quan hệ RW thành quan hệ R1 - tập những quan hệ có thể tương ứng với từ

quan hệ RW. Ví dụ từ quan hệ “’s” tương ứng với tập các quan hệ {HASWIFE,

HASSON, HASCAPITAL, …}

28

o Ánh xạ từ quan hệ (C1, C2) thành quan hệ R2 - tập những quan hệ có thể có giữa C1

và C2. Ví dụ giữa hai lớp (PERSON, PERSON) ta có tập các quan hệ sau:

{HASWIFE, HASFATHER, HASMOTHER, …}

o Ánh xạ (S1, RW) thành R3 - tập những quan hệ có thể có nếu biết từ quan hệ RW và

giá trị chuỗi ban đầu S1. Ví dụ với (wife, ’s) sẽ được ánh xạ thành tập quan hệ

{HASWIFE}.

o Ánh xạ (RW, S2) thành R4 - tập những quan hệ có thể có nếu biết từ quan hệ RW và

giá trị chuỗi ban đầu S2. Ví dụ với (has, mother) sẽ được ánh xạ thành tập quan hệ

{HASMOTHER}

 Ta có thể dễ dàng nhận thấy R3, R4 đều là tập con của R2. Gọi R là mối quan hệ thật sự

của từ quan hệ RW. Chắc chắn R  R1  R2. Ngoài ra, trong một số trường hợp, có thể R  R1

 R3 hoặc R  R1  R4 hoặc R sẽ thuộc giao của cả bốn tập hợp trên. Như vậy, về lý thuyết ta

có thể xác định được quan hệ R nếu xây dựng đầy đủ cả bốn tập hợp trên.

 Việc xây dựng tập ánh xạ R3 và R4 được thực hiện bằng hệ thống luật. Chi tiết về hệ

thống luật sẽ được trình bày ở phần sau.

4.1.10

Xoá bỏ quan hệ không phù hợp

Sau Bước 4.1.9 (Xác định loại quan hệ giữa các thực thể), có một số quan hệ được xác định

nhưng không phù hợp với ngữ cảnh của câu truy vấn, các loại quan hệ này sẽ được xóa bỏ. Bước

này sử dụng các heuristic sau để xóa bỏ các quan hệ không phù hợp:

 Nếu hai thực thể Ei và Ei+1 cách nhau bởi dấu phẩy, thì Ei+1 chỉ quan hệ với Ei, các mối

quan hệ của Ei+1 với các thực thể khác sẽ bị xóa bỏ. Ví dụ trong câu “What's the population of

[CITY:Biloxi](POPULATIONCOUNT)[STRING:?]

[PROVINCE:Mississippi](POPULATIONCOUNT)[STRING:?]

[CITY:Biloxi](SUBREGIONOF)[PROVINCE:Mississippi]

Biloxi, Mississippi?”, tồn tại các quan hệ:

29

Hai thực thể Biloxi và Mississippi cách nhau bởi dấu phẩy, do đó quan hệ thứ hai được

xóa bỏ.

 Nếu Ei và Ei+1 đứng liền kề nhau, hoặc cách nhau bằng từ quan hệ “’s”, thì các quan hệ

của Ei với các thực thể trước nó sẽ bị xóa bỏ. Ví dụ, trong câu “What is the name of Neil

[PERSON:Neil Armstrong]( HASLABEL)[LABEL:?]

[PERSON:*](HASLABEL)[LABEL:?]

[PERSON:Neil Armstrong](HASWIFE)[PERSON:*]

Armstrong’s wife?” có các quan hệ:

Vì thực thể wife có quan hệ với thực thể Neil Armstrong bằng từ quan hệ ‘s. Do đó quan

hệ đầu tiên được xóa bỏ.

 Trong trường hợp một thực thể có quan hệ với nhiều thực thể đứng trước nó, thì chỉ giữ

lại mối quan hệ với thực thể không xác định đứng trước, gần nó nhất. Ví dụ, trong câu truy vấn

[COMPANY:Sea World](LOCATEDIN)[CITY:?]

[CITY:?](LOCATEDIN)[PROVINCE:Florida]

[COMPANY:Sea Word](LOCATEDIN)[PROVINCE:Florida]

“What city in Florida is Sea World in?” có ba loại quan hệ:

Quan hệ thứ hai bị xóa bỏ.

4.1.11

Xác định quan hệ giữa tính từ và thực thể

Tại bước này, ta sẽ xét các liên kết giữa tính từ và thực thể, được gọi là một bộ hai

thể>.

Xem xét câu truy vấn “What famous model was married to Billy Joel?”, tính từ famous nằm

trước thực thể model. Đối với câu truy vấn “Name a tiger that is extinct?”, tính từ extinct nằm sau

thực thể tiger. Như vậy, tính từ liên kết với một thực thể có thể nằm trước, hoặc nằm sau thực thể

đó. Khi xem xét trên tập mẫu, tính từ xuất hiện nhiều nhất là ở trước thực thể. Do đó, để hình thành

nên các bộ hai truy vấn , độ ưu tiên sẽ được quyết định dựa vào vị trí của tính từ

30

đối với vị trí của thực thể. Ưu tiên nhất là tính từ nằm trước thực thể, cuối cùng là tính từ nằm sau

thực thể. Các bộ hai sau đó sẽ được so trùng với Ontology để xác định kiểu quan

hệ tương ứng có trong Ontology.

Dựa vào các phân tích trên, đề tài đưa ra giải thuật xác định kiểu quan hệ giữa tính từ và thực

thể trong câu truy vấn như sau (Hình 4.4):

Hình 4.0.4: Xác định loại quan hệ giữa tính từ adj và thực thể.

 Bước 1: Xét các thực thể nằm sau tính từ adj. Bằng việc sử dụng tập luật, nếu có thực thể

ej nào khi kết hợp với adj mà xác định được kiểu quan hệ giữa adj và ej thì quá trình dừng,

ngược lại qua Bước 2.

 Bước 2: Xét các thực thể ei nằm ở trước adj.

Bằng giải thuật trên, chúng ta xác định được kiểu quan hệ giữa tính từ adj và e nếu giữa chúng

có mối quan hệ với nhau trong ngữ cảnh của câu truy vấn. Quá trình được áp dụng tương tự cho tất

cả các cặp tính từ, thực thể trong câu truy vấn. Các kiểu quan hệ tìm được sẽ được thêm vào danh

sách quan hệ RELATION.

Việc xác định kiểu quan hệ được làm bằng cách ứng với mỗi bộ hai ta sẽ ánh

xạ thành . Việc ánh xạ này cũng được thực hiện bằng giải pháp

lập từ điển (Tập luật) và heuristic, tương tự quá trình ánh xạ bộ ba

thành đã được trình bày tại Bước 4.1.9. Quá trình ánh xạ được

khái quát bằng lược đồ Hình 4.5.

31

Hình 4.0.5: Lược đồ ánh xạ kiểu quan hệ giữa tính từ và thực thể.

Chi tiết cho lược đồ tại Hình 4.5 được diễn dịch như sau:

 Xét mối quan hệ có dạng: [ADJ] – [E, S] với:

o ADJ là tính từ,

o E là lớp của thực thể liên kết với tính từ được xem xét.

o S là giá trị chuỗi ban đầu của thực thể E.

 Ta sẽ lần lượt xây dựng các ánh xạ sau đây:

o Ánh xạ tính từ ADJ thành tập R1 các bộ ba quan hệ

thể>. Ví dụ, tính từ famous tương ứng với tập các bộ ba quan hệ

{,

SUBCLASSOF, PERSON>, ,}

o Ánh xạ (ADJ, E) thành tập R2 các bộ ba quan hệ

có thể biểu diễn tính từ ADJ đối với thực thể E. Ví dụ, giữa tính từ famous và lớp

32

PERSON, ta có thể có các bộ ba sau: {

MODEL>, }

o Ánh xạ (ADJ, S) thành R3 - tập các bộ ba có thể có nếu biết tính từ ADJ và giá trị

chuỗi ban đầu S. Ví dụ, (famous, model) sẽ được ánh xạ thành tập quan hệ

{}

 Ta có thể dễ dàng nhận thấy R2, R3 đều là tập con của R1. Gọi R là mối quan hệ thật sự

biểu diễn bộ hai . Chắc chắn R  R1  R2  R3. Như vậy, về lý thuyết ta có

thể xác định được quan hệ R nếu xây dựng đầy đủ cả ba tập hợp trên.

 Việc xây dựng tập ánh xạ R1, R2 và R3 được thực hiện bằng hệ thống luật. Chúng ta sẽ đi

vào chi tiết về hệ thống luật này ở phần sau.

4.1.12

Xây dựng đồ thị ý niệm

Sau khi đã xác định được tất cả các quan hệ có trong câu truy vấn, bước này sẽ xây dựng đồ thị

ý niệm mô tả câu truy vấn. Như ta đã phân tích ở trên, để mở rộng giải quyết cho những truy vấn hỏi

về số lượng, truy vấn có tính từ, tính từ so sánh nhất, liên từ luận lý yêu cầu phải mở rộng CG.

Phương pháp tiếp cận đã kế thừa và đồng thời hiệu chỉnh lại Bước 12 (Xây dựng đồ thị ý niệm)

trong kết quả nghiên cứu của tác giả [18] để biểu diễn được những thành phần mới bổ sung của đồ

thị ý niệm mở rộng. Chúng ta sẽ đi vào chi tiết về cách lưu trữ và hiển thị đồ thị ý niệm ở phần tiếp

theo sau.

4.2 Tập luật

Như Mục 4.2.9 của Chương 4 đã phân tích, để xây dựng tập luật ánh xạ R3 và R4 ta cần phải xây

dựng một hệ thống luật tổng quát, sao cho ta có thể dễ dàng mô tả thêm các luật mới nhưng vẫn

không ảnh hưởng tới hệ thống. Như vậy nó sẽ làm cho hệ thống có tính tổng quát hơn, không bị bó

buộc trên tập luật xác định nào đó. Để đạt được mục tiêu trên, ta sẽ xây dựng tập luật theo định dạng

XML.

Mỗi luật trong hệ thống luật sẽ có dạng như sau:

33

“Nếu [điều kiện] thì [hành động]”

Trong đó phần điều kiện có những đặc tính sau:

 Có ràng buộc về tên lớp thực thể, giá trị chuỗi ban đầu và kiểu thực thể.

 Có thể xét một quan hệ hoặc nhiều quan hệ đồng thời.

Phần hành động có những đặc tính sau:

 Cho phép thay đổi các giá trị về tên lớp, thay đổi định danh thực thể và xác định loại

quan hệ.

 Xóa thực thể hoặc quan hệ.

Phần này trình bày cấu trúc của tập luật dùng để ánh xạ bộ ba quan hệ thành quan hệ ngữ nghĩa.

4.2.1 Cấu trúc của hệ thống luật

Hệ thống luật được định nghĩa trong một tập tin XML, trong đó mỗi thành phần (Element) sẽ

được mô tả theo định dạng DTD (Document Type Definition) như sau:

Thành phần root của tập tin là TransformRules, trong đó chứa nhiều thành phần rule.

Hình 4.0.6: Cấu trúc tập thành phần TransformRules và rule.

Từ khóa ELEMENT được dùng để mô tả cấu trúc của một thành phần; từ khóa ATTLIST được

dùng để mô tả các thuộc tính của một thành phần; CDATA mô tả kiểu dữ liệu chuỗi cho thuộc tính;

#REQUIRED dùng mô tả tính chất bắt buộc của thuộc tính; #IMPLIED dùng mô tả tính chất không

bắt buộc của thuộc tính. DTD dùng các ký hiệu “*”, “+” và “?” dùng để chỉ số lượng của một thành

phần trong thành phần cha của nó. Ý nghĩa của mỗi ký hiệu như sau:

34

 Dấu “*”: xuất hiện từ 0 đến n

 Dấu “+”: xuất hiện từ 1 đến n

 Dấu “?”: xuất hiện 0 hoặc 1

Định nghĩa thành phần TransformRules ở Hình 4.6, chỉ ra thành phần này có thể chứa nhiều

thành phần rule, thành phần rule chứa hai thành phần premiselist và consequentlist. Ngoài ra, thành

phần rule còn có hai thuộc tính là name và priority dùng để mô tả tên luật và độ ưu tiên của luật.

Chúng ta sẽ lần lượt tìm hiểu cấu trúc các thành phần con trong thành phần rule tiếp theo sau đây.

4.2.2 Cấu trúc thành phần điều kiện của luật

Mỗi luật bao gồm hai phần: điều kiện và hành động. Phần điều kiện của luật được mô tả bằng

thành phần premiselist, là con của thành phần rule. Thành phần premiselist bao gồm một hay nhiều

thành phần premise, Hình 4.7 mô tả cấu trúc của một thành phần premise. Mỗi thành phần premise

gồm có ba thành phần con là subject, relation và object tương ứng với một bộ ba mà ta đã thảo luận

ở phần trên. Ý nghĩa của các thuộc tính trong các thành phần này được thể hiện trong Bảng 4.1. Ví

dụ minh hoạ đặc tả thành phần premise có thể thấy tại Hình 4.8.

Tên thuộc tính Đặc tả

var Thuộc tính này dùng để đặt tên biến cho các thành phần, nhằm phân biệt các thành phần

value Giá trị chuỗi ban đầu của thực thể. Ta có thể liệt kê tập các giá trị trong đó các thành phần cách nhau bằng dấu phẩy.

className Thuộc tính ràng buộc tên lớp thực thể

classType Thuộc tính dùng để ràng buộc kiểu thực thể như UE, IE

Bảng 4.1: Bảng thuộc tính thành phần premise.

4.2.3 Cấu trúc thành phần hành động của luật

Nếu một bộ ba nào đó thỏa mãn thành phần điều kiện luật thì hành động luật consequent sẽ được

áp dụng cho bộ ba đó. Cấu trúc của thành phần hành động được mô tả như Hình 4.9.

35

Các thuộc tính của thành phần hành động cũng giống như phần tử điều kiện đã được mô tả trong

Bảng 4.2. Ngoài ra, thành phần hành động còn có hai thuộc tính mới là quantifier và delete, thuộc

tính quantifier dùng để gán giá trị định danh cho lớp, thuộc tính delete dùng để yêu cầu xóa thành

phần đó. Hình 4.11 là ví dụ minh họa đặc tả một luật hoàn chỉnh.

Hình 4.0.7: Cấu trúc của thành phần điều kiện luật.