Thuật toán CYK là gì? Chi tiết về Thuật toán CYK mới nhất 2021

Bách khoa toàn thư mở Wikipedia

Bước tới điều hướng
Bước tới tìm kiếm

CYK viết tắt của từ Cocke-Younger-Kasami, là một thuật toán dùng để xác định xem một xâu có được tạo ra (hay đoán nhận) bởi một văn phạm phi ngữ cảnh hay không (context-free grammar). Thuật toán này được sử dụng rất nhiều trong phân tích ngôn ngữ tự nhiên.

CYK là thuật toán bottom-up và chi phí là O(n³) trong trường hợp tồi nhất với n là độ dài xâu phân tích.

Giải thuật

Vào: Văn phạm G = (N, T, S, P) dạng chuẩn Chomsky, không chứa sản xuất trống, xâu vào w = a1a2… an € T+

Ra: Bảng phân tích T đối với w sao cho tij chứa A khi và chỉ khi

A →+ aiai+1… ai+j-1

Thuật toán

For i = 1 to n do ti1 = { A|A → ai € P }

For j = 2 to n do

For i = 1 to n – j +1 do

For k = 1 to j – 1 do

tij = { A| A → BC € P, B → tik và C → ti+k,j-k }

Nếu S € t1n thì w € L(G).

Ví dụ:

Tham khảo[sửa | sửa mã nguồn]


Lấy từ “https://vi.wikipedia.org/w/index.php?title=Thuật_toán_CYK&oldid=63240192”

Từ khóa: Thuật toán CYK, Thuật toán CYK, Thuật toán CYK

LADIGI – Công ty dịch vụ SEO uy tín giá rẻ, SEO từ khóa, SEO tổng thể cam kết lên Top Google uy tín chuyên nghiệp, an toàn, hiệu quả.

Nguồn: Wikipedia

Scores: 4 (119 votes)

100 lần tự tìm hiểu cũng không bằng 1 lần được tư vấn