Luận văn tốt nghiệp Xử lý các văn bản tiếng Việt

Danh mục hình
Hình 1. Phân loại văn phạm của Chomsky 11

Hình 2. Cây biểu diễn câu John ate the cat 14

Hình 3. Biểu đồ sau khi tìm thấy một ADJ tại vị trí 2 16

Hình 4. Sau khi phân tích can là NOUN 18

Hình 5. Biểu đồ sau khi thêm hold 19

Hình 6. Biểu đồ sau khi tìm được tất cả các NP 19

Hình 7. Biểu đồ cuối cùng 20

Hình 8. Vị trí và biểu đồ ban đầu 22

Hình 9. Biểu đồ sau khi phân tích cụm NP đầu tiên 24

Hình 10. Sau khi phân tích khả năng thứ hai của NP đầu tiên 25

Hình 11. Sau khi tìm kiếm một S theo quy tắc 1 bị thất bại 25

Hình 12. Cấu trúc của câu cần phân tích 26

Hình 13. Mạng chuyển đệ quy làm ví dụ trong phân tích từ trên xuống 35

Hình 14. Giao diện chương trình phân tích cú pháp tiếng Anh 53

Hình 15. Phương pháp xây dựng ôtômát âm tiết 59

Hình 16. Phương pháp xây dựng ôtômát từ vựng 59

Hình 17. Một tình huống nhập nhằng 60

Hình 18. Các phương án phân tích cho một câu tiếng Việt nhập nhằng 62

Hình 19. Cây phân tích ứng với cách tách từ đúng 62


Danh mục bảng
Bảng 1. Phân tích từ trên xuống, ưu tiên chiều sâu cho văn phạm phi ngữ cảnh 15

Bảng 2. Một văn phạm phi ngữ cảnh đơn giản 20

Bảng 3. Quá trình phân tích từ trên xuống 35

Bảng 4. Phân tích từ trên xuống kết hợp quay lui cho mạng chuyển đệ quy 36

Khoá luận tốt nghiệp
5

Bảng 5. Tập luật của văn phạm tiếng Việt 48

Bảng 6. Tập luật của văn phạm tiếng Anh 50

Khoá luận tốt nghiệp
6
Chương 1. Mở đầu

Khoá luận tốt nghiệp
Chương 1. Mở đầu
1.1. Tổng quan về vấn đề phân tích văn bản
Phân tích và kiểm tra tính chính xác của văn bản là một vấn đề lớn và phức tạp.
Quá trình này thường được chia thành 4 giai đoạn chính: phân tích từ vựng, phân tích
cú pháp, phân tích ngữ nghĩa và phân tích thực chứng.
•
•
•
•
Phân tích từ vựng. Là quá trình phân tích hình thái các từ vựng tạo nên văn
bản, từ đó kiểm tra được tính đúng đắn của âm tiết và từ.
Phân tích cú pháp. Là quá trình đưa ra mô tả quan hệ về vai trò ngữ pháp của
các từ, các cụm từ (hoặc ngữ) trong câu, từ đó xây dựng cấu trúc câu.
Phân tích ngữ nghĩa. Mục đích của phân tích ngữ nghĩa là kiểm tra ý nghĩa của
câu có mâu thuẫn với ý nghĩa cả đoạn hay không. Dựa trên mối liên hệ logic về
nghĩa giữa các cụm từ trong câu và mối liên hệ giữa các câu trong đoạn, hệ
thống sẽ xác định được một phần ý nghĩa của câu trong ngữ cảnh của cả đoạn.
Phân tích thực chứng. Là quá trình phân tích nhằm xác định ý nghĩa của câu
dựa trên mối liên hệ của câu với hiện thực. Ý nghĩa thực tế của câu phụ thuộc
rất nhiều vào ngữ cảnh diễn ra lời nói. Do vậy, quá trình phân tích này rất khó
thực hiện được bằng máy tính. Thường thì việc phân tích câu chỉ dừng ở phân
tích ngữ nghĩa, còn việc phân tích thực chứng do người dùng tự quyết định.
1.2. Bài toán phân tích cú pháp
Phân tích cú pháp đưa ra mô tả về quan hệ và vai trò ngữ pháp của các từ, các
cụm từ (hoặc ngữ) trong câu, đồng thời đưa ra hình thái của câu. Đầu vào của giai
đoạn này là câu đã được phân tách từ, trong đó mỗi từ có đặc điểm hình thái xác định.
Quá trình kiểm tra cú pháp tiến hành phân tích và tổ hợp các từ ở đầu vào, dựa trên
các luật cú pháp để loại bỏ các trường hợp bất quy tắc và từng bước dựng lên cấ
u trúc
cú pháp (cây phân tích) của câu. Kết quả cần đạt được là hình thái của câu.
Cú pháp là chủ đề nghiên cứu của hai cộng đồng gồm những người làm ngôn ngữ
và những người làm tin học. Với những người làm ngôn ngữ thì ngôn ngữ là đối
tượng nghiên cứu, cú pháp là một trong các cấp độ phải mô tả. Với những người làm
tin học thì cần làm cho máy tính phân tích được cú pháp với hai mục tiêu là xây dựng
các ứng dụng, qua đó phục vụ vi
ệc nghiên cứu ngôn ngữ; đối tượng nghiên cứu của họ
là các hệ hình thức và các thuật toán.
Chương 1. Mở đầu
Khoá luận tốt nghiệp
8
Khi xét về cấu trúc cú pháp có hai khía cạnh, một là thứ tự của các từ, trong đó có
những ràng buộc về cấu tạo câu đúng và chức năng của các thành phần trong câu (chủ
ngữ, vị ngữ ); hai là những biến tố (về hình thái, ví dụ các thì, số ít, số nhiều,
giống ) quy định ràng buộc về cấu tạo và chức năng ngữ pháp. Với tiếng Việt, không
có khía cạnh thứ hai.
Để phân tích cấu trúc của một câu ta cần đến hai thứ: Thứ nhất là ngữ pháp của
ngôn ngữ, là đặc tả hình thức cấu trúc của ngôn ngữ và thứ hai là các kỹ thuật phân
tích, là các phương thức phân tích để tìm ra cấu trúc ngữ pháp của câu, hoặc kết luận
câu sai ngữ pháp. Để đặc tả ngữ pháp, người ta đưa ra các mô hình cú pháp của ngôn
ngữ.
1.3. Nội dung khoá luận
Khoá luận gồm hai nội dung chính.
Nội dung thứ nhất là trình bày hai mô hình truyền thống dùng để phân tích cú
pháp của ngôn ngữ tự nhiên, gồm các văn phạm phi ngữ cảnh và các mạng chuyển đệ
quy. Trong khuôn khổ của khoá luận, em chỉ thực hiện phần nghiên cứu, cài đặt các
thuật toán phân tích cho văn phạm phi ngữ cảnh và mạng chuyển đệ quy nhằm nắm
chắc và làm chủ các kỹ thuật phân tích, các phần khác là triển vọng nghiên cứu trong
t
ương lai gần. Có ba kỹ thuật phân tích được nghiên cứu là phân tích từ trên xuống,
phân tích từ dưới lên và phân tích tổng hợp. Ðể tiện trong việc trình bày, toàn bộ các
thuật toán được giải thích và minh hoạ trên bộ văn phạm đơn giản của tiếng Anh.
Nội dung thứ hai là xây dựng tập từ loại và văn phạm đơn giản cho tiếng Việt,
thiết kế cấu trúc dữ liệu và cài đặt các thuật toán phân tích,
đánh giá kết quả. Vì khuôn
khổ của khoá luận có hạn, nên em chỉ trình bày phần cài đặt thuật toán phân tích từ
trên xuống cho văn phạm phi ngữ cảnh. Kết quả cần đạt được là hoàn thiện một
chương trình phân tích cú pháp tiếng Việt đơn giản viết bằng ngôn ngữ lập trình Java,
thể hiện kết quả phân tích bằng giao diện đồ hoạ dạng cây.
Phần phụ lục của khoá luận trình bày bài toán tách từ
vựng tiếng Việt - vấn đề tiền
xử lý quan trọng trước khi bước vào phân tích cú pháp.
Chương 2. Văn phạm phi ngữ cảnh
Khoá luận tốt nghiệp
Chương 2. Văn phạm phi ngữ cảnh
2.1. Văn phạm và ngôn ngữ sinh bởi văn phạm
Một tập hợp Χ ≠ φ (vô hạn hoặc hữu hạn) các đối tượng được gọi là một bảng chữ
cái. Mỗi phần tử thuộc tập Χ được gọi là một chữ cái hay một ký hiệu. Ví dụ, bảng
chữ cái tiếng Việt là Σ = {a, b, c, , y}.
Mỗi dãy ký hiệu các phần tử của Χ: α = a
i1
a
i2
a
it
, a
ij
∈ Χ, 1 ≤ j ≤ t được gọi là
một từ hay một xâu trên bảng chữ cái Χ. Ví dụ ba, ca, con, Tổng số vị trí của tất cả
các ký hiệu xuất hiện trong từ α được gọi là độ dài của α, ký hiệu là |α|. Từ có độ dài
bằng 0 được gọi là từ rỗng (trống), được ký hiệu là ε.
Gọi Σ* là tập hợp gồ
m tất cả các từ trên bảng chữ cái Σ, kể cả từ rỗng. Mỗi một
tập con của tập Σ* được gọi là một ngôn ngữ trên bảng chữ cái Σ. Tập rỗng cũng là
một ngôn ngữ trên bảng chữ cái tuỳ ý, được ký hiệu bằng φ.
Giả sử có bảng chữ cái Σ, một văn phạm là một bộ bốn G = (Σ, V,
σ, P), trong đó:
¾ Σ là bảng chữ cái chính hay bảng chữ cái từ hay tập ký hiệu kết
¾ V là bảng chữ cái phụ hay bảng chữ cái làm việc hay tập ký hiệu không kết
¾ σ ∈ V là một ký hiệu phụ, gọi là tiền đề hay ký hiệu xuất phát hay ký hiệu
khởi đầu
¾ P = {ϕ → ψ⎪ϕ∈(
Σ ∪V)*\{e}, ψ ∈(Σ ∪V)*, → ∉ (Σ ∪V)} gọi là tập quy
tắc sinh hay tập quy tắc thế của văn phạm G. r = ϕ → ψ là một quy tắc
sinh hay quy tắc thế của văn phạm G, ϕ, ψ theo thứ tự được gọi là vế trái
và vế phải của quy tắc r.
Ví dụ, G = ({a, b, c},
{S, A, B}, S, P), trong đó P là
S
→
ABBA
AB
→
BAA
AA
→
BcBa
BcB
→
Aab
A
→
B
B
→
A
B
→
C

Chương 2. Văn phạm phi ngữ cảnh

Khoá luận tốt nghiệp
10
Từ xâu ban đầu α = ΑΒ, bằng các quy tắc sinh đã cho ta có α = AB → β = BAA
→ γ = BBcBa. Ta nói rằng xâu α dẫn trực tiếp ra xâu β, dẫn gián tiếp ra xâu γ và viết
là α ⇒ β. Tổng quát, giả sử α = α
1
ϕα
2
, β = α
1
ψα
2
, ϕ → ψ ∈ P thì ta nói rằng xâu α
dẫn trực tiếp ra xâu β hoặc xâu β được dẫn trực tiếp từ xâu α.
Một dãy từ ω
0
, ω
1
, , ω
i
, ω
i+1
, , ω
m
được gọi là một dẫn xuất trong văn phạm G
nếu ∀i, ω
i
⇒ ω
i+1
.
Ta nói rằng xâu α dẫn gián tiếp ra xâu β hay xâu β được dẫn gián tiếp từ α trong
văn phạm G, và viết là α
β nếu hoặc α = β hoặc tồn tại một dẫn xuất ω mà từ đầu
tiên là α và từ cuối cùng là β.
*
⇒
Tập {x ∈ Σ* | σ
x} gồm tất cả các từ thuộc bảng chữ cái chính mà mỗi từ này
được dẫn gián tiếp từ tiền đề gọi là ngôn ngữ sinh bởi văn phạm G, ký hiệu là L(G).
*
⇒
Để việc trình bày được ngắn gọn và phân biệt ý nghĩa của các ký hiệu trong văn
phạm, ta quy ước: dùng các chữ cái in hoa để chỉ các ký hiệu không kết, các chữ cái
thường để chỉ các ký hiệu kế
t và dùng các ký tự Hy Lạp để chỉ các xâu.
2.2. Văn phạm phi ngữ cảnh
Theo cách phân loại của Chomsky, văn phạm được chia thành ba loại, gồm
¾ Văn phạm cảm ngữ cảnh, hoặc văn phạm biến đổi. Độ dài của xâu α
bên trái mỗi quy tắc phải nhỏ hơn hoặc bằng độ dài của xâu β bên vế phải
của quy tắc đó. Nghĩa là mọi sản xuất đều có dạng λAρ → λαρ, trong đó
λ
và ρ là các xâu bất kỳ (có thể rỗng). λ và ρ có thể coi như vế trái và vế phải
của văn cảnh ở đó ký hiệu không kết A được viết lại thành xâu không rỗng
α, chính vì vậy nên văn phạm loại này được gọi là cảm ngữ cảnh. Các quy
tắc sinh cảm ngữ cảnh có thể dùng để chuyển một câu từ dạng chủ động
sang dạng bị độ
ng tương ứng.
¾ Văn phạm phi ngữ cảnh, hay văn phạm cấu trúc cụm. Mọi quy tắc đều
có dạng A → α, trong đó A là ký hiệu không kết và α là xâu bất kỳ.
¾ Văn phạm chính quy, hay văn phạm tuyến tính phải. Mọi quy tắc đều
có một trong hai dạng sau: A → t hoặc A → tN, trong đó A và N là các ký
hiệu không kết, t là ký hiệu kết. Các văn phạ
m chính quy không đủ mạnh
để mô tả ngôn ngữ tự nhiên (thậm chí cả các ngôn ngữ lập trình). Chúng
thường được dùng để mô tả các bộ phận của ngôn ngữ và có thế mạnh là
tốc độ phân tích nhanh.
Chương 2. Văn phạm phi ngữ cảnh

Khoá luận tốt nghiệp
11

Hình 1. Phân loại văn phạm của Chomsky
Các quy tắc sinh của văn phạm phi ngữ cảnh G có thể được chuẩn hoá theo hai
cách mà không làm thay đổi khả năng sinh của nó, gồm dạng chuẩn Chomsky và dạng
chuẩn Greibach. Trong dạng chuẩn Chomsky, các quy tắc có dạng A → BC hoặc A →
a. Với dạng chuẩn Greibach, các qui tắc có dạng A → aα.
Cây dẫn xuất của văn phạm là một cây được đánh dấu bởi các ký hiệu kết thúc
hoặc không kết thúc sao cho mỗ
i nút mẹ là vế trái của một qui tắc sinh mà vế trái của
qui tắc đó lập nên bởi dãy các kí hiệu của các nút con.
Hầu hết các ngôn ngữ lập trình đều được mô tả bằng văn phạm phi ngữ cảnh.
Chẳng hạn, câu lệnh lặp while được mô tả bởi các quy tắc phi ngữ cảnh sau:
WhileStatement → while Condition do StatementList end
StatementList → Statement
StatementList → Statement ; StatementList


Văn phạm phi ngữ cảnh cũng được lựa chọn để biểu diễn cấu trúc cú pháp của các
ngôn ngữ tự nhiên bởi hai lý do:
¾ Nó đủ mạnh để mô tả hầu hết những cấu trúc của ngôn ngữ tự nhiên
¾ Nó vừa đủ hạn chế để xây dựng những trình phân tích câu hiệu quả
Sau đây ta đi vào tìm hiểu việc vận dụng các văn phạm phi ngữ c
ảnh và các thuật
toán phân tích để biểu diễn ngôn ngữ tự nhiên và xây dựng các trình phân tích cú
pháp.
2.3. Biểu diễn cấu trúc câu
Văn phạm phi ngữ cảnh khi được sử dụng để biểu diễn cấu trúc cú pháp thì các ký
hiệu kết thúc tương ứng với các từ trong ngôn ngữ, các ký hiệu không kết thúc tương
ứng với các phân loại cú pháp (hay từ loại). Tiên đề biểu diễn phân loại "câu". Các
quy tắc sinh biểu diễn các quy tắc ngữ pháp. Ta có thể chia chúng thành các qui tắc từ
Chương 2. Văn phạm phi ngữ cảnh

Khoá luận tốt nghiệp
12
vựng (chứa ít nhất một ký hiệu kết thúc) và các qui tắc ngữ đoạn (không chứa ký hiệu
kết thúc nào). Với mỗi từ trong từ vựng có một tập các qui tắc sinh chứa từ này trong
vế phải. Một cây dẫn xuất cũng được gọi là cây cú pháp cho một phân tích của một
ngữ đoạn thành các thành phần kế tiếp.
Với lớp câu kể đơn giản nhất trong tiếng Anh, ta dùng bộ
quy tắc sinh sau đây:
S
→
NP VP
VP
→
VERB NP
NP
→
NAME
NP
→
ART NOUN

Các ký hiệu không thể phân tách thêm được nữa như NOUN, ART, VERB trong
văn phạm ví dụ trên là các ký hiệu kết. Các ký hiệu khác, gồm S, NP, VP là các ký
hiệu không kết. Mỗi ký hiệu kết biểu diễn một từ loại. Thông thường, một từ có nhiều
kiểu từ loại khác nhau, ví dụ, từ can có thể là VERB hoặc NOUN.
Có hai phương pháp điển hình dùng để phân tích văn phạm phi ngữ cảnh, là phân
tích từ trên xuống và phân tích từ
dưới lên.
¾
Phân tích từ trên xuống: Xuất phát từ ký hiệu đầu S, áp dụng các suy dẫn
tiến hành từ trái qua phải thử tạo ra câu cần phân tích
¾ Phân tích từ dưới lên: Xuất phát từ chính câu vào, áp dụng thu gọn các suy
dẫn phải, tiến hành từ phải qua trái để đi tới ký hiệu đầu.
Ví dụ, xét câu "John ate the cat". Phân tích từ trên xuống như sau
S
→
NP VP

→
NAME VP

→
John VP

→
John VERB NP

→
John ate NP

→
John ate ART NOUN

→
John ate the NOUN

→
John ate the cat

Phân tích từ dưới lên thì ngược lại.
Một văn phạm rộng hơn dùng cho lớp câu kể của tiếng Anh là
Chương 2. Văn phạm phi ngữ cảnh

Khoá luận tốt nghiệp
13
1. S
→
NP VP
2. NP
→
ART NOUN
3. NP
→
NAME
4. PP
→
PREP NP
5. VP
→
VERB
6. VP
→
VERB NP
7. VP
→
VERB NP NP
8. VP
→
VERB PP

Trong đó, các ký hiệu và từ loại tương ứng được cho trong bảng sau:
Ký hiệu Từ loại tương ứng
S Câu
NP cụm danh từ
VP cụm động từ
PP cụm giới từ
NOUN danh từ
ART mạo từ
VERB động từ
NAME tên riêng

Theo văn phạm này thì một số câu như
¾ John saw the cat by the pond
¾ The dog barked in the house
là chấp nhận được, nhưng nó cũng chấp nhận những câu không có nghĩa như
¾ The dog allows the house
¾ John barked the cat by the pond
Với câu John ate the cat, ta có cây phân tích như Hình 2.
Chương 2. Văn phạm phi ngữ cảnh

Khoá luận tốt nghiệp
14

Hình 2. Cây biểu diễn câu John ate the cat

2.4. Phân tích từ trên xuống
Bây giờ ta xây dựng trình phân tích từ trên xuống cho văn phạm phi ngữ cảnh. Để
mô tả một trạng thái của trình phân tích ta dùng hai thông tin:
¾ Vị trí hiện tại. Lưu lại phần nào của câu đã được phân tích rồi
¾ Trạng thái hiện tại. Là một xâu các ký hiệu sinh ra từ các quy tắc của văn
phạm
Ở mỗi bước, trình phân tích xét ký hiệu nằm bên trái nhất của danh sách. Nếu nó
có tên là một từ loại củ
a từ kế tiếp thì xoá ký hiệu này và cập nhật lại vị trí hiện tại
một cách thích hợp. Sử dụng văn phạm tiếng Anh gồm 8 quy tắc đã nêu ở phần trước,
để tiện theo dõi, ta viết lại ở đây:
1. S
→
NP VP 5. VP
→
VERB
2. NP
→
ART NOUN 6. VP
→
VERB NP
3. NP
→
NAME 7. VP
→
VERB NP PP
4. PP
→
PREP NP 8. VP
→
VERB PP

Ta có phân tích từ trên xuống của câu
1
The
2
dogs
3
cried
4
như trên Bảng 1.
Bước Trạng thái hiện tại Trạng thái lưu Vị trí Nhận xét
1. (S) 1 vị trí khởi tạo
2. (NP VP) 1 viết lại S theo quy tắc 1
3. (ART NOUN VP) 1 viết lại NP theo các quy tắc 2, 3

Xem chi tiết: Luận văn tốt nghiệp Xử lý các văn bản tiếng Việt