TAILIEUCHUNG - Demo thuật toán CKY

Demo thuật toán CKY – CKY Parsing Algorithm simulation 1. Giới thiệu thuật toán CKY CKY ( Coke- Kasami – Younger) là một thuật toán cải tiến của thuật toán phân tích cú pháp Bottom-Up (Button-Up Parsing là một | Demo thuật toán CKY – CKY Parsing Algorithm simulation 1. Giới thiệu thuật toán CKY CKY ( Coke- Kasami – Younger) là một thuật toán cải tiến của thuật toán phân tích cú pháp Bottom-Up (Button-Up Parsing là một chiến lượt phân tích tích cú pháp bắt đầu từ các từ trong các chuỗi đầu vào và xây dựng các thành tố cú pháp). CKY có thể tránh được những cách phân tích cú pháp không hợp lý so với thuật toán Buttom-Up thông thường. Do CKY sử dụng một hình thức văn phạm đặc biệt được gọi là Chomsky Normal Form (CNF). Các giải pháp trung gian của thuật được lưu trữ và chỉ triển khai những giải pháp trung gian nào có khả năng đóng góp vào việc phân tích đầy đủ cấu trúc cú pháp câu. 2. Mã giả thuật toán CKY - Cky Algorithm (Recognition) - CKY Parsing: 3. Các vấn đề của CKY Tính hiệu quả: – CKY có thể được thực hiện với thời gian: O(n3), trong đó n=số từ của câu. – Sự phức tạp của các vòng lặp trong. – Nhiều quy tắc hơn, thì ít hiệu quả hơn, nhưng điều này làm tăng một tỉ lệ hằng L = r2 với r là số lượng của các biến (non-terminals). Ngữ pháp đòi hỏi: – Các thuật toán cơ bản đòi hỏi một ngữ pháp nhị phân: ngữ pháp CNF (Chomsky Normal Form). – Thuật toán cơ bản có thể được mở rộng để phân tích cho CFGs tùy ý. – Tuy nhiên, việc chuyển đổi thành ngữ pháp CNF dễ dàng và hiệu quả hơn so với phân tích với ngữ pháp tùy ý. – Thuật toán Earley cho phép phân tích CFGs tùy ý. 4. Ngữ pháp Chomsky Normal Form Một ngữ pháp phi ngữ cảnh mà RHS của mỗi quy tắc đưa ra là: 2 non-terminals hoặc 1 terminal. Chúng có thể là: - Không quy tắc lẫn lộn (NP -> the NN). - Không có dạng NP -> NNP, ngoại trừ dạng NN -> dog. - Vế phải không có nhiều hơn 2 non-terminals như: VP -> VBZ NP PP. Bất kỳ CNG nào cũng có thể biến đổi thành một ngữ pháp tương đương yếu trong CNF tức là chúng tạo ra cũng một bộ chuỗi (các câu). Quy ước đặt tên, ký hiệu trong văn phạm CNF: • Sử dụng ký hiệu mới (nhị phân): – X1, X2, . . . , Y3 – S →NP VP PUNC trở thành : • S →NP X1, • X1→VP PUNC • Xóa một ký hiệu: – SBAR → S , S → NP VP trở thành – SBAR → NP VP Thuật toán CNF cải tiến: 1. Loại bỏ các unit-productions: while there is a unit-production A → B, Remove A → B. foreach B → u, add A → u. 2. Loại bỏ các terminals trong quy tắc lẫn lộn foreach production A → B1 B2 Bk, containing a terminal x Add new non-terminal/production X1 → x (unless it has already been added) Replace every Bi = x with X1 3. Loại bỏ các quy tăc với nhiều hơn 2 nonterminals trên RHS (nhị phân) foreach rule p of form A → B1 B2 Bk replace p with A → B1 X1, X1 → B2 X2, X2 → B3 X3, , X(k − 2) → Bk−1 Bk (Xi là các biến mới) 5. Phân tích một câu đơn giản theo văn phạm CNF Câu: •0 the •1 chef •2 eats •3 fish •4 with •5 the •6 chopsticks •7 Phân tích theo văn phạm CNF là: S → NP VBZ S → NP VP VP → VP PP VP → VBZ NP VP → VBZ PP VP → VBZ NNS VP → VBZ VP VP → VBP PP NP → DT NN NP → DT NNS PP → IN NP DT → the NN → chef NNS → fish NNS → chopsticks VBP → fish VBZ → eats IN → with 6. Chương trình demo CKY algorithm - Click vào đây để xem demo CKY với câu: “The chef eats fish with the chopsticks”. - Click vào đây để xem demo CKY với câu: “I saw the man with the gun”. - Click vào đây để xem demo CKY với một câu mới do bạn tự nhập. 7. Viết bởi - Huỳnh Ngọc Khuê. - Lâm Thanh Cường. 1

• Hệ điều hành
• thuật toán CKY
• function
• mã giả thuật toán
• ngữ pháp Chomsky
• thuật toán CNF
• quy tắc thuật toán
• lập trình
• kĩ thuật lập trình C
• tài liệu lập trình C
• giáo trình lập trình C
• lý thuyết lập trình C
• thủ thuật lập trình C
• Khôi phục dấu tự động
• Dịch máy dựa trên cú pháp
• Suy diễn văn phạm
• Văn phạm phi ngữ cảnh đồng bộ
• Thuật toán phân tích cú pháp CKY
• kỹ thuật lập trình
• ngôn ngữ lập trình
• ngôn ngữ C
• lập trình C
• khái niệm ngôn ngữ C
• lập trình cơ bản
• code lập trình
• lập trình máy tính
• thuật toán lập trình
• ngôn ngữ lập trình C
• Bài giảng Toán kinh tế
• Toán kinh tế
• Thuật toán đơn hình
• Bài toán quy hoạch tuyến tính chính tắc
• Cơ sở lí thuyết thuật toán đơn hình
• Bài giảng Quy hoạch tuyến tính
• Quy hoạch tuyến tính
• Bài toán quy hoạch tuyến tính
• Phương pháp đơn hình cho bài toán chính tắc
• Bài toán chính tắc
• Chuẩn hóa văn bản tiếng Việt
• Phân lớp ký hiệu
• Bộ quy tắc
• Chuẩn hóa văn bản
• Bài toán chuẩn hóa văn bản
• Phân lớp ký hiệu dùng bộ quy tắc
• Thuật toán phân lớp ký hiệu
• Lý thuyết quy hoạch tuyến tính
• Bài toán đối ngẫu
• Đối ngẫu trong quy hoạch tổng quát
• Quy hoạch tuyến tính dạng chính tắc
• Giải thuật đối ngẫu
• Quy hoạch tổng quát
• Bài giảng Thuật toán Ứng dụng
• Thuật toán Ứng dụng
• Hàm đệ quy
• Quy tắc xây dựng phần tử
• Nhánh cận
• Chiến lược tìm kiếm tối ưu tổ hợp
• Bài toán chọn lọc Toán lớp 4
• Ôn luyện Toán lớp 4
• Bài tập Toán lớp 4
• Kiến thức Toán lớp 4
• Kỹ thuật thực hiện phép tính
• Quy tắc đếm
• thuật toán xấp xỉ
• điều khiển học
• nghiên cứu tin học
• Lý thuyết thuật toán
• tự động học
• khoa học điều khiển
• Tài liệu toán học
• Dữ liệu vật lý
• Phương trình nội quy của Thum
• Toán học và dữ liệu vật lý
• Quy tắc của ngón tay cái
• Thuật ngữ toán học
• Tạp chí khoa học
• Phương pháp xử lý logic vị từ
• Xử lý logic vị từ
• Thuật toán song song
• Quy tắc đệ quy
• toán cao cấp
• tính đạo hàm
• toán vi phân
• quy tắc tính đạo hàm
• kỹ thuật toán học
• tính giới hạn
• bài giảng toán cao cấp
• Giáo trình kế toán
• luận văn kế toán
• phương pháp kế toán
• kỹ thuật báo cáo
• kỹ năng báo cáo
• Giải thuật nâng cao
• Bài giảng Giải thuật nâng cao
• Frame buffer
• Thuật toán Bresenham
• Biểu diễn đoạn thẳng trong frame buffer
• Quy tắc chọn pixel
• Chiếm lĩnh tri thức
• Dạy học toán
• Chiếm lĩnh tri thức trong dạy học
• Thực hành quy tắc thuật giải
• Tựa thuật giải
• Nội hàm khái niệm chiếm lĩnh tri thức
• Bài giảng Nhập môn trí tuệ nhân tạo
• Nhập môn trí tuệ nhân tạo
• Trí tuệ nhân tạo
• Tiêu chuẩn đánh giá thuật toán tìm kiếm
• Quy tắc suy diễn
• Thuật toán học cây quyết định
• Sáng kiến kinh nghiệm
• Sáng kiến kinh nghiệm THCS
• Sáng kiến kinh nghiệm môn Toán
• Bất đẳng thức Cô si
• Kỹ thuật ghép đối xứng
• Hệ phương trình
• Quy tắc dấu bằng
• quy tắc bảo mật
• hệ thống mã hóa
• Mật mã khối DES
• thuật toán DES
• Mô tả hàm Feistel
• Hàm mở rộng E
• kỹ năng văn phòng
• thủ thuật máy tính
• Cẩm nang soạn thảo văn bản
• quy tắc soạn thảo văn bản
• cách trình bày văn bản
• các phím tắt word thông dụng
• tính toán trong word
• Bài giảng Programming technique
• Viết code hiệu quả
• Tính toán trước các giá trị
• Chỉ thị chương trình dịch
• Quy tắc cơ bản Fundamental Rule
• Tối ưu đoạn code
• Phát hiện dị thường
• Tìm kiếm cứu nạn
• Thuật toán RX
• Phương tiện bay không người lái
• Quy tắc Neyman–Pearson
• Bài giảng Tin đại cương
• Tin đại cương
• Cấu trúc chương trình C++
• Phương pháp biểu diễn thuật toán
• Quy tắc con lạc đà
• Giáo án Tin học
• Giáo án Tin học lớp 11
• Giáo án điện tử lớp 11
• Khái niệm mảng một chiều
• Các quy tắc kiểu dữ liệu
• Thuật toán sắp xếp đơn giản