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)

clip_image002[4]

 

         CKY Parsing:

clip_image004[4]

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ânngữ 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 vi 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

     Demo CKY.

image

7. Viết bởi

–   Huỳnh Ngọc Khuê.

–   Lâm Thanh Cường.

Advertisements

About thanhcuong1990

Handsome and talent!! ^^
This entry was posted in Chủ đề khác and tagged . Bookmark the permalink.

11 Responses to Demo thuật toán CKY – CKY Parsing Algorithm simulation

  1. Tran BAn says:

    Rấ hay, mình đang tìm hiểu và xây dựng CT Phân tích cú pháp tiếng Việt dùng CKY mở rộng. Mong bạn hợp tác và cung cấp thêm thông tin về CKY.

  2. duythanhcn says:

    chào bạn!
    mình cũng đang tìm hiểu về thuật toán cky này
    Liệu bạn có thể chĩa sẽ code demo không ?

  3. Cường Nguyễn says:

    Anh ơi,
    Em củng đang tìm hiểu về thuật toán CKY. Anh cho em xin code được không?
    mail: magically.ndc@gmail.com

  4. Ka Kha says:

    Chào anh,
    Anh có thể share code demo CKY cho em tham khảo được không…?
    Mail: kungfuitk6@gmail.com
    Có ai có code demo của PCKY không…?

  5. Tpanh says:

    Anh ơi,
    Em đang tìn hiểu về thuật toán CKY.
    Anh có thể cho em xin code của demo CKY này k?
    Cảm ơn a.

  6. tpvan says:

    em chào anh.
    Em đang tìm hiểu về CKY.
    Anh có thể cho em xin code deme của nó k ạ.
    Mấy trang web die hết rồi.
    Cảm ơn anh

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s