intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Thuy Ha | Ngày: | Loại File: PDF | Số trang:63

Thêm vào BST
Báo xấu
415
lượt xem 195
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Xử lý ngôn ngữ tự nhiên nói chung và phân tích cú pháp ngôn ngữ tự nhiên nói riêng là những vấn đề quan trọng của trí tuệ nhân tạo, được nhiều nhà khoa học trên lĩnh vực này rất phong phú. Ta có thể điểm qua một số ứng dụng chính như dịch máy, kiểm tra và chữa lỗi văn bản.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn tốt nghiệp "Xử lý các văn bản tiếng Việt"

  1. Luận văn tốt nghiệp "Xử lý các văn bản tiếng Việt"
  2. LỜI NÓI ĐẦU Xử lý ngôn ngữ tự nhiên nói chung và phân tích cú pháp ngôn ngữ tự nhiên nói riêng là những vấn đề quan trọng của trí tuệ nhân tạo, được nhiều nhà khoa học trên thế giới quan tâm nghiên cứu trong suốt 50 năm qua. Các ứng dụng trong lĩnh vực này rất phong phú. Ta có thể điểm qua một số ứng dụng chính như dịch máy, kiểm tra và chữa lỗi văn bản, chuyển giao diện người – máy sang ngôn ngữ tự nhiên, nhận dạng chữ viết, thiết kế người máy có khả năng hiểu và nói được tiếng của con người… Bài toán phân tích cú pháp ngôn ngữ tự nhiên bằng máy tính là bài toán lớn và phức tạp. Với tiếng Việt - một ngôn ngữ rất phức tạp thì dường như bài toán này lại càng khó khăn hơn. Chúng ta đã có một số công trình nghiên cứu về xử lý tiếng Việt và đã đạt được một số thành công nhất định. Tuy nhiên, cho đến nay bài toán phân tích cú pháp tiếng Việt vẫn chưa được giải quyết triệt để. Một trong những lý do chính là vì chúng ta chưa nghiên cứu một cách có hệ thống ngữ pháp tiếng Việt và cơ sở lý thuyết về xây dựng những trình phân tích cú pháp cho tiếng Việt còn tương đối ít và chưa hoàn chỉnh. Các mô hình văn phạm phi ngữ cảnh và mạng chuyển được sử dụng rộng rãi trong mô tả cú pháp không chỉ của các ngôn ngữ lập trình mà cả các ngôn ngữ tự nhiên. Trong khoá luận này, em sẽ tập trung nghiên cứu việc vận dụng các mô hình này cho bài toán cụ thể là phân tích cú pháp tiếng Việt. Ngôn ngữ Việt có nhiều điểm khác so với các ngôn ngữ phổ biến, đã được nghiên cứu nhiều như tiếng Anh hay tiếng Pháp. Do đó, chúng ta không thể áp dụng hoàn toàn những kết quả đã đạt được đối với các ngôn ngữ này vào tiếng Việt. Khoá luận trình bày các vấn đề sau: • Khái quát vấn đề phân tích văn bản • Vận dụng các mô hình văn phạm phi ngữ cảnh và mạng chuyển đệ quy để mô tả ngôn ngữ tự nhiên • Nghiên cứu các thuật toán phân tích đối với các văn phạm phi ngữ cảnh và các mạng chuyển • Nghiên cứu một cách hệ thống các đặc điểm của ngữ pháp tiếng Việt • Xây dựng một trình phân tích câu tiếng Anh đơn giản • Xây dựng một trình phân tích câu tiếng Việt đơn giản Khoá luận tốt nghiệp 1
  3. • Đánh giá kết quả đã đạt được và hướng phát triển Để thực hiện được đề tài này, em đã vận dụng những kiến thức được học trong giai đoạn đại cương và chuyên ngành, đồng thời học hỏi và nghiên cứu thêm lĩnh vực ngôn ngữ học và tiếng Việt. Để tạo ra một sản phẩm phần mềm tương đối khả quan cần có sự nghiên cứu lâu dài và có hệ thống trên cả ba lĩnh vực toán học, tin học và ngôn ngữ học. Nếu chỉ có những kiến thức tin học thì sản phẩm tạo ra sẽ không thể mang ứng dụng trong thực tế. Vì vậy, việc đồng thời trau dồi những kiến thức toán học, tin học và ngôn ngữ học là rất cần thiết. Những công việc em đã thực hiện mới chỉ là bước đầu trong việc xử lý các văn bản tiếng Việt. Em rất mong muốn tiếp tục nhận được sự hỗ trợ và chỉ bảo tận tình của các thầy cô giáo, các nhà chuyên môn cùng toàn thể các bạn sinh viên quan tâm, yêu thích công việc xử lý ngôn ngữ tự nhiên, vốn rất khó khăn và phức tạp, cần có lòng kiên trì và say mê cao độ. Em xin được bày tỏ lòng cảm ơn sâu sắc tới TS. Lương Chi Mai và ThS. Nguyễn Thị Minh Huyền đã tận tình hướng dẫn và giúp đỡ, tạo mọi điều kiện thuận lợi về tài liệu và phương tiện để em hoàn thành khoá luận này. Trong quá trình thực hiện khoá luận, em còn nhận được sự ủng hộ, giúp đỡ và động viên của các anh chị ở Phòng Nhận dạng và Công nghệ Tri thức, Viện Công nghệ Thông tin, Trung tâm Khoa học Tự nhiên và Công nghệ Quốc gia, nơi em thực tập trong thời gian qua. Em xin chân thành cảm ơn. Em xin chân thành cảm ơn các thầy cô giáo trong và ngoài Khoa Toán-Cơ-Tin học đã truyền đạt cho em những kiến thức, trang bị cho em những hành trang quý giá trước khi em ra trường. Em xin chân thành cảm ơn các thầy cô giáo trong Bộ môn Tin học đã tạo điều kiện cho em được thực hiện một số xêmina khoa học liên quan đến đề tài, và đóng góp nhiều ý kiến quý báu, kịp thời. Xin cảm ơn các bạn sinh viên đã động viên, giúp đỡ tôi thực hiện đề tài này. Hà Nội, ngày 10 tháng 5 năm 2002 Sinh viên Lê Hồng Phương Khoá luận tốt nghiệp 2
  4. Mục lục LỜI NÓI ĐẦU ..................................................................1 Danh mục hình .............................................................................................5 Danh mục bảng.............................................................................................5 Chương 1. Mở đầu...........................................................7 1.1. Tổng quan về vấn đề phân tích văn bản........................................... 7 1.2. Bài toán phân tích cú pháp ............................................................... 7 1.3. Nội dung khoá luận .......................................................................... 8 Chương 2. Văn phạm phi ngữ cảnh .................................9 2.1. Văn phạm và ngôn ngữ sinh bởi văn phạm...................................... 9 2.2. Văn phạm phi ngữ cảnh ................................................................. 10 2.3. Biểu diễn cấu trúc câu .................................................................... 11 2.4. Phân tích từ trên xuống .................................................................. 14 2.5. Phân tích từ dưới lên ...................................................................... 15 2.6. Đánh giá hai phương pháp phân tích trên ...................................... 20 2.7. Phương pháp phân tích tổng hợp ................................................... 21 Chương 3. Các mạng chuyển.........................................27 3.1. Văn phạm và ôtômát ...................................................................... 27 3.2. Các yếu tố cơ sở của mạng chuyển đệ quy .................................... 29 3.3. Tính thủ tục của các RTN .............................................................. 33 3.4. Phân tích từ trên xuống cho mạng chuyển đệ quy ......................... 34 Chương 4. Xây dựng văn phạm tiếng Việt .....................37 4.1. Xây dựng tập từ loại tiếng Việt...................................................... 37 4.2. Xây dựng văn phạm tiếng Việt ...................................................... 38 Khoá luận tốt nghiệp 3
  5. 4.2.1. Danh ngữ ..........................................................................................39 4.2.2. Động ngữ ..........................................................................................41 4.2.3. Tính ngữ............................................................................................44 4.2.4. Câu đơn hai thành phần ...................................................................45 4.2.5. Văn phạm tiếng Việt .........................................................................47 Chương 5. Cài đặt chương trình ....................................49 5.1. Cấu trúc dữ liệu .............................................................................. 49 5.2. Cài đặt thuật toán ........................................................................... 51 5.3. Thể hiện kết quả phân tích ............................................................. 52 5.4. Đánh giá kết quả............................................................................. 57 Phụ lục .........................................................................58 Bài toán tách từ vựng tiếng Việt ........................................................... 58 1. Đặt bài toán............................................................................................58 2. Các bước giải quyết................................................................................58 3. Đánh giá kết quả ....................................................................................60 Tài liệu tham khảo ......................................................................................63 Khoá luận tốt nghiệp 4
  6. 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
  7. 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
  8. Chương 1. Mở đầu 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. Khoá luận tốt nghiệp
  9. Chương 1. Mở đầu 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. Khoá luận tốt nghiệp 8
  10. Chương 2. Văn phạm phi ngữ cảnh 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 Χ: α = ai1ai2...ait, aij ∈ Χ, 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 Khoá luận tốt nghiệp
  11. Chương 2. Văn phạm phi ngữ cảnh 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. Khoá luận tốt nghiệp 10
  12. Chương 2. Văn phạm phi ngữ cảnh 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ừ Khoá luận tốt nghiệp 11
  13. Chương 2. Văn phạm phi ngữ cảnh 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à Khoá luận tốt nghiệp 12
  14. Chương 2. Văn phạm phi ngữ cảnh 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. Khoá luận tốt nghiệp 13
  15. Chương 2. Văn phạm phi ngữ cảnh 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 Khoá luận tốt nghiệp 14
  16. Chương 2. Văn phạm phi ngữ cảnh (NAME VP) 1 4. (NOUN VP) 2 so khớp ART với the (NAME VP) 1 5. (VP) 3 so khớp NOUN với dogs (NAME VP) 1 6. (VERB) 3 viết lại VP theo các quy tắc 5-8 (VERB NP) 3 (VERB NP PP) 3 (VERB PP) 3 (NAME VP) 1 7. quá trình phân tích thành công, vì VERB so khớp với cried, và lúc này, danh sách các ký hiệu của văn phạm là rỗng, câu cần phân tích rỗ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 Chú ý rằng trình phân tích đưa các trạng thái được sao lưu vào một ngăn xếp. 2.5. Phân tích từ dưới lên Ðiểm khác nhau chủ yếu giữa phân tích từ trên xuống và phân tích từ dưới lên là cách sử dụng các quy tắc sinh. Ví dụ, xét quy tắc NP → ART ADJ NOUN Trong phân tích từ trên xuống, khi gặp NP, ta thay nó bằng dãy ART ADJ NOUN. Trong phân tích từ dưới lên, ta sử dụng quy tắc này theo cách ngược lại, tức nếu gặp dãy ART ADJ NOUN thì ta thay nó bằng NP. Như vậy, công việc cơ bản của phân tích từ dưới lên là lấy ra một dãy các ký hiệu và so sánh nó với vế phải của các quy tắc. Việc so khớp luôn được xem xét từ một ký hiệu, gọi là khoá. Ðể tìm ra những quy tắc khớp với một xâu gồm cả khoá, ta tìm những quy tắc bắt đầu bằng khoá này, hoặc tìm những quy tắc bắt đầu bằng các khoá trước đó và cần khoá hiện tại để hoàn thành quy tắc hoặc thác triển quy tắc. Ví dụ, xét văn phạm sau: 1. S → NP VP 2. NP → ART ADJ NOUN 3. NP → ART NOUN 4. NP → ADJ NOUN Khoá luận tốt nghiệp 15
  17. Chương 2. Văn phạm phi ngữ cảnh 5. VP → AUX VERB NP 6. VP → VERB NP Nếu ta bắt đầu bằng khoá ART thì các quy tắc 2 và 3 là khớp. Ta ghi lại điều này cho bước xử lý tiếp theo, các quy tắc 2, 3 có thể đi tiếp được ở sau điểm ART. Ta biểu diễn điều này bằng cách viết lại các quy tắc đó cùng với dấu chấm tròn (ο) chỉ rằng ta đã đi đến đâu: 2'. NP → ART ο ADJ NOUN 3'. NP → ART ο NOUN Nếu khoá sau đó là ADJ thì có thể có quy tắc 4 và quy tắc 2' được thác triển tiếp như sau: 2''. NP → ART ADJ ο NOUN Các trạng thái trong phân tích từ dưới lên được lưu dưới dạng một cấu trúc gọi là biểu đồ (chart). Biểu đồ là một bản ghi vị trí của các từ và các cấu trúc mới phát sinh từ câu đang phân tích. Các cung trên biểu đồ lưu giữ các quy tắc đã so khớp trước đó nhưng chưa hoàn thiện. Ví dụ, sau khi đã biết một ART và sau đó là một ADJ trong ví dụ trên, ta sẽ có biểu đồ sau (Hình 3): Hình 3. Biểu đồ sau khi tìm thấy một ADJ tại vị trí 2 Có hai thành phần: ART1, ADJ1 và 4 cung hoạt động; 2 NP bắt đầu bằng ART từ 1 đến 2, 1 NP bắt đầu bằng ART ADJ từ 1 đến 3, 1 NP bắt đầu bằng ADJ từ 2 đến 3. Thuật toán phân tích cụ thể như sau: Có hai cấu trúc dữ liệu là biểu đồ và danh sách khoá biểu đồ: lưu tất cả các thông tin về các thành phần hoàn chỉnh và các cung hoạt động danh sách khoá: là một ngăn xếp các thành phần hoàn chỉnh đã được đưa vào biểu đồ. Mỗi khi danh sách khoá rỗng thì đọc từ tiếp theo của câu và đưa mọi từ loại có thể của nó vào danh sách Khoá luận tốt nghiệp 16
  18. Chương 2. Văn phạm phi ngữ cảnh Ta coi mỗi ký hiệu của quy tắc tương đương với một thành phần của cung. Như vậy ta nói ART, ADJ, NOUN là 3 thành phần của cung 2'. NP → ART ο ADJ NOUN Việc đưa một thành phần C vào giữa hai vị trí p1 và p2 trên biểu đồ gồm các bước sau: 1. đưa C vào giữa p1 và p2; 2. nếu C bắt đầu một quy tắc r của văn phạm thì thêm một cung biểu diễn quy tắc r từ p1 đến p2; 3. với mỗi cung A đi từ p0 đến p1 (điểm bắt đầu của C), nếu C là thành phần con kế tiếp của A thì thêm một cung từ p0 đến p2 biểu diễn quy tắc A đã cập nhật. 4. nếu một cung nào đó trong số các cung được thêm vào tại các bước 2, 3 là một quy tắc đã hoàn chỉnh thì thêm vào danh sách khoá một thành phần mới có tên là vế trái của quy tắc đó. Ví dụ, xét thuật toán này với câu cần phân tích là The large can can hold the water, với từ điển sau: the ART large ADJ can AUX, NOUN, VERB hold NOUN, VERB water NOUN, VERB Ban đầu danh sách khoá là rỗng, do đó từ the được đọc và thành phần ART1 được đặt vào danh sách. • Vào ART1: (the từ 1 tới 2). Thêm cung NP → ART ο ADJ NOUN từ 1 tới 2, thêm cung NP → ART ο NOUN từ 1 tới 2; Cả hai cung này được thêm vào tại bước 2 của thuật toán. Sau đó từ large được đọc, tạo ra thành phần ADJ1. • Vào ADJ1: (large từ 2 tới 3). Thêm cung NP → ADJ ο NOUN từ 2 tới 3 (bước 2), thêm cung NP → ART ADJ ο NOUN từ 1 tới 3 (bước 3); ở đây, cung thứ Khoá luận tốt nghiệp 17
  19. Chương 2. Văn phạm phi ngữ cảnh hai được thêm vào là do sự thác triển của cung đầu tiên tại bước 3 của thuật toán. Lúc này, ta được biểu đồ như trên Hình 3. Với từ tiếp theo can, có 3 thành phần được tạo ra là NOUN1, AUX1, và VERB1. • Vào NOUN1: (can từ 3 đến 4). Không có cung nào được thêm vào trong bước 2, song có hai cung được hoàn thiện ở bước 3 vì NOUN1 sinh ra 2 NP, 2NP này được đưa danh sách khoá ở bước 4, NP thứ nhất từ 1 đến 4 được xây dựng từ quy tắc 2, NP thứ hai từ 2 đến 4 được xây dựng từ quy tắc 4. Hai NP này bây giờ nằm trên đỉnh của ngăn xếp các khoá. • Vào NP1: NP từ 1 tới 4. Thêm cung S → NP ο VP từ 1 tới 4. • Vào NP2: NP từ 2 tới 4. Thêm cung S → NP ο VP từ 2 tới 4. Bây giờ biểu đồ có dạng như Hình 4. Hình 4. Sau khi phân tích can là NOUN Bây giờ xét tới các từ loại khác của can. • Vào AUX1: (can từ 3 đến 4). Thêm cung VP → AUX ο VERB NP từ 3 tới 4. • Vào VERB1: (can từ 3 đến 4). Thêm cung VP → VERB ο NP từ 3 tới 4. Từ tiếp theo lại là can và NOUN2, AUX2, VERB2 được tạo ra. • Vào NOUN2: (can từ 4 đến 5). Không cung nào được thêm vào. • Vào AUX2: (can từ 4 đến 5). Thêm cung VP → AUX ο VERB NP từ 4 tới 5. • Vào VERB2: (can từ 4 đến 5). Thêm cung VP → VERB ο NP từ 4 tới 5, thêm cung VP → AUX VERB ο NP từ 3 tới 5. Từ tiếp theo là hold và NOUN3, VERB3 được tạo ra. • Vào NOUN3: (hold từ 5 đến 6). Không cung nào được thêm vào. Khoá luận tốt nghiệp 18
  20. Chương 2. Văn phạm phi ngữ cảnh • Vào VERB3: (hold từ 5 đến 6). Thêm cung VP → VERB ο NP từ 5 tới 6, thêm cung VP → AUX VERB ο NP từ 4 tới 6. Ta được biểu đồ như Hình 5. Hình 5. Biểu đồ sau khi thêm hold • Vào ART2: (the từ 6 đến 7). Thêm cung NP → ART ο ADJ NOUN từ 6 tới 7, thêm cung NP → ART ο NOUN từ 6 tới 7. • Vào NOUN4: (water từ 7 đến 8). Không có cung nào được thêm vào trong bước 2, một NP, NP3 từ 6 tới 8 được đẩy vào danh sách khoá do hoàn thành cung NP → ART ο NOUN từ 6 tới 7. • Vào NP3: (the water từ 6 đến 8). Một VP, VP1 từ 4 tới 8 được đẩy vào danh sách khoá do hoàn thành quy tắc VP → AUX VERB ο NP từ 4 tới 6; một VP, VP2 từ 5 tới 8 được đẩy vào danh sách khoá do hoàn thành quy tắc VP → VERB ο NP từ 5 tới 6. Ðồ thị tiếp theo của giai đoạn này như Hình 6 (chỉ vẽ những cung sử dụng trong phân tích tiếp theo). Hình 6. Biểu đồ sau khi tìm được tất cả các NP • Vào VP2 (hold the water từ 5 đến 8). Không cung nào được thêm vào. Khoá luận tốt nghiệp 19
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.26: Bộ 320 Luận Văn Thạc Sĩ Y Học
320 tài liệu
1248 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2