Hàm COUNT nhận các đầu vào là hai từ L và R và một cặp hai con trỏ tới các danh sách kết nối: l trỏ đến một kết nối thuộc danh sách bên phải của một dạng tuyển của L và r trỏ đến một kết nối thuộc danh sách bên trái của một dạng tuyển của R. COUNT trả ra một số, đó là số cách vẽ các kết nối các từ từ L đến từ R, với các kết nối thuộc danh sách trỏ bởi l và r.
Kết quả tính được của hàm COUNT tại mỗi lần được gọi được chứa vào một mảng băm (ngay trước khi trả về). Trong lần sau, kết quả tính được ở lần trước được tra trong bảng băm. Vì có bảng băm lưu lại kết quả, chi phí thời gian chạy là O(c2 d) với d là số các dạng tuyển và c là số các kết nối. Với một văn phạm xác định, d = O(n) và c = O(n), vậy thời gian chạy là O(n3 ).
3.1.2. Lược tỉa
Với các công thức được trình bày ở chương 3, để bao quát các hiện tượng cú pháp tiếng Việt, số lượng dạng tuyển phải xét là rất lớn. Tuy nhiên phần lớn các dạng tuyển là không được sử dụng vì chúng chứa các kết nối không khớp với một kết nối nào của một từ nào trong câu. Cụ thể, giả sử một từ W có dạng tuyển d với kết nối C ở danh sách bên phải. Nếu không có từ nào bên phải W có một kết nối bên trái khớp với C, thì dạng tuyển d không thể nằm trong một phân tích đúng nào. Do đó, dạng tuyển này có thể xoá mà không làm thay đổi kết quả phân tích liên kết. Việc xoá dạng tuyển đó được gọi là bước lược tỉa [111].
Quá trình lược tỉa được chia làm hai bước: lược tỉa và lược tỉa mạnh.
Lược tỉa
Duyệt tuần tự qua các từ trong câu lần lượt từ trái qua phải rồi từ phải qua trái và cứ tiếp tục như vậy đến khi không loại bỏ được dạng tuyển nào nữa.
Giả sử từ thứ m trong câu đang được xét. Tập S các kết nối thuộc danh sách phải trong dạng tuyển của các từ thứ 1,…, m – 1 được lưu trữ trong một bảng băm, với hàm băm sử dụng các chữ cái viết hoa ban đầu của tên kết nối. Do vậy sẽ tiết kiệm được nhiều thời gian tìm kiếm kết nối khớp với nó.
Thực tế quá trình phân tích cú pháp được [111] cho thấy chưa bao giờ cần nhiều hơn năm lần duyệt để kết thúc quá trình lược tỉa.
Có thể bạn quan tâm!
-
Xây Dựng Liên Kết Dựa Trên Cấu Trúc Tính Ngữ -
Liên Kết Các Mệnh Đề Trong Câu Ghép Đơn Giản -
Ứng Dụng Giải Thuật Mở Rộng Từ Điển Tiếng Việt -
Mô hình văn phạm liên kết tiếng Việt - 16 -
Mô hình văn phạm liên kết tiếng Việt - 17 -
Giải Thuật Phân Tích Cú Pháp Câu Ghép
Xem toàn bộ 305 trang tài liệu này.
Lược tỉa mạnh
Gọi một kết nối là nông nếu nó là kết nối đầu tiên trong danh sách các kết nối của nó.
Ngược lại kết nối là sâu. Lược tỉa mạnh dựa trên những tiêu chí sau:
- Tiêu chí từ gần nhất phải được thoả mãn cho cả hai kết nối tạo thành liên kết.
- Không thể có liên kết giữa hai kết nối sâu.
- Hai kết nối của một liên kết giữa hai từ cạnh nhau phải là kết nối cuối cùng trong danh sách của chúng.
- Hai kết nối của một liên kết giữa hai từ không cạnh nhau không thể đồng thời là kết nối cuối cùng trong danh sách của chúng (Trừ trường hợp kết nối lớn).
Lược tỉa trên cây biểu thức
Dù theo [111], sau khi xây dựng tất cả các dạng tuyển mới bắt đầu lược tỉa, luận án đã chọn cách làm của các bộ phân tích liên kết tiếng Anh [137], đó là xây dựng cây biểu diễn công thức liên kết của mỗi từ, sau đó lược tỉa trên cây trước khi xây dựng các dạng tuyển. Cách xử lý này cho phép thực hiện nhanh hơn rất nhiều so với cách thức được giới thiệu trong [111].
Nếu coi tên kết nối là các toán hạng, các phép &, or, xor là các toán tử thì công thức liên kết có cấu trúc giống biểu thức số học ({X} được chuyển thành X or()). Hình 3.5.dưới đây mô tả một cây biểu diễn công thức liên kết
Hình 3.5. Cây cho công thức (NN- &{NN+}) or ({PqNt-} & {NN+})
Khi duyệt liên kết của các từ để lược tỉa như đã giới thiệu ở chương 4, nếu thấy một kết nối không khớp với kết nối nào ở bên phải, ta sẽ loại các nút ở cây theo các luật sau:
- Nếu một nút con của nút nhãn “&” bị xóa thì xóa bỏ nút đó.
- Nếu nút nhãn “or” “xor” không còn nút con thì loại bỏ nút đó.
Ngoài ra cần áp dụng ba luật sau một cách tuần tự.
- Nếu có nhiều hơn một nút nhãn “( )” là nút con của nút nào đó thì chỉ giữ lại một nút
- Nếu nút nhãn “&” có nhiều hơn một nút con trong đó có nút nhãn “( )” thì nó sẽ bị loại bỏ khỏi cây.
- Nếu một nút có nhãn “&” hoặc “or” , “xor” chỉ chứa một nút con thì thay nhãn của nó bằng nhãn của nút con.
Tất nhiên quy trình vẫn thực hiện theo thứ tự trái → phải rồi phải → trái v.v… Kết quả nhận được giống như kết quả của hai bước lược tỉa và lược tỉa mạnh nhưng tốc độ thực hiện nhanh hơn nhiều.
Hiệu quả lược tỉa trong tiếng Việt
Do tiếng Việt không biến đổi hình thái, thì, thể, số … đều được thể hiện bằng cách thêm từ nên số dạng tuyển ban đầu của mỗi từ, đặc biệt là danh từ và động từ lớn hơn nhiều so với tiếng Anh. Tuy nhiên các giải thuật lược tỉa đạt hiệu quả rất tốt: sau hai quá trình lược tỉa và lược tỉa mạnh, số lượng dạng tuyển chỉ còn tương đương tiếng Anh, và cũng không có câu nào trong tập ví dụ của luận án cần đến 5 lần lược tỉa.
Hình 3.6. Số lượng dạng tuyển sau lược tỉa và lược tỉa mạnh
Trong hình 3.6. là hình ảnh kết quả lược tỉa do bộ phân tích thực hiện với câu “chúng tôi muốn giành các danh hiệu”.
3.1.3. Kết quả thử nghiệm phân tích câu đơn và câu ghép đơn giản
Bộ phân tích cú pháp liên kết được xây dựng bằng Java, làm việc trên môi trường Windows. Để thử nghiệm bộ phân tích cú pháp theo mô hình [111], luận án đã thu thập 200 câu, điển hình cho các dạng khác nhau từ các bài báo trên mạng Internet về một số chủ đề: hội thoại tiếng Việt, khoa học thường thức, thể thao, du lịch. Dưới đây là kết quả thực hiện chương trình với câu “Chúng tôi muốn giành các danh hiệu”
Hình 3.7. Kêt quả phân tích liên kết của câu “Chúng tôi muốn giành các danh hiệu”