CYK 알고리즘은 어떻게 작동합니까?

Question

Chomsky 일반 형식의 주어진 컨텍스트에서 문자열을 파생시킬 수 있는지 확인해야합니다. C++을 사용하고 있습니다.

CYK 알고리즘을 다루는 Wikipedia 기사에는 매우 좋은 pseudocode이 있지만 아주 잘 이해할 수는 없습니다.

누가 CYK 알고리즘에 대한 또 다른 의사 코드를 제공하여 나를 도와 주거나, 위키 기사에서 설명 할 수 있을까요?

Answer 1

CYK 알고리즘은 Chomsky 표준 형식의 CFG를 입력으로 사용합니다. 즉 모든 생산

• S → A, S → AB 일부 터미널 A에 대한, 또는
• 지금

B. 일부 비끝 A의와, 당신이 상상을 양식을 가지고 중 하나를 의미합니다 문자열 w와 시작 기호가 S 인 문법에서 파생 될 수 있는지를보고 싶습니다. 두 가지 옵션이 있습니다 :

1. w가 단일 문자이면, 어떤 문자 a에 대해 S → 양식의 생산을 사용하는 것이 구문 분석됩니다. 따라서 어떤 단일 문자 프로덕션이 a와 일치하는지 확인하십시오.
2. w가 두 개 이상의 문자 인 경우 구문 분석을 수행하는 유일한 방법은 일부 비 문자 A와 B에 대해 S → AB 양식을 사용하는 것입니다. 즉, 문자열 w를 두 조각으로 나눌 필요가 있음을 의미합니다 x와 y 여기서 A는 x를 유도하고 B는 y를 유도합니다. 한 가지 방법은 w를 두 조각으로 나눌 수있는 모든 방법을 시도하고 그 중 하나가 작동하는지 확인하는 것입니다. 해당 옵션 (2) 여기에 재귀 구문 분석 문제가 될 수있을 테니까요

공지 사항 : 당신이 그와

B.

에서 A와 Y에서 X를 도출 할 수 있는지 여부를 확인, 당신은 S에서 w를 유도 할 수 있는지 여부를 확인하기 위해 통찰력, 여기 당신이 비단 S가 w 문자열 파생 있는지 여부를 확인하는 데 사용할 수있는 재귀 함수에 대한 의사의 :

bool canDerive(nonterminal S, string w) { 
    return canDeriveRec(S, w, 0, w.size()); 
} 

/* Can you derive the substring [start, end) of w from S? */ 
bool canDeriveRec(nonterminal S, string w, int start, int end) { 
    /* Base case: Single characters */ 
    if (end - start == 1) { 
     return whether there is a production S -> a, where a = w[start]; 
    } 

    /* Recursive case: Try all possible splits */ 
    for (each production S -> AB) { 
     for (int mid = start + 1; mid < end; mid++) { 
      if (canDeriveRec(A, w, start, mid) && 
       canDeriveRec(B, w, mid, end)) { 
       return true; 
      } 
     } 
    } 
    return false; 
} 

이 알고리즘이 제대로 작동은하지만 재귀의 모양을하게되면, 당신은

을 찾을 수 있습니다

1. 많은 재귀 호출을 반복하지만,
2. 여러 가지 가능한 재귀 호출이 없습니다.

는 사실상 구별 가능한 호출의 수는 O, n은 (시작 및 종료 인덱스의 각각의 가능한 조합에 대한) 입력 스트링의 길이이다 (N ² N)이고, N은이고 문법에있는 비 터미널의 수. 이러한 관찰은이 알고리즘이 당신이 생각하는 어떤 접근 방식이 더 좋을까에 따라 메모 또는 동적 프로그래밍의 이점을 얻을 것이라고 제안합니다.

CYK 알고리즘은 위의 재귀 알고리즘을 사용하여 결과를 메모 할 때 얻을 수 있습니다. 또는 위의 재귀 알고리즘을 동적 프로그래밍 문제로 변환 할 때도 마찬가지입니다.

가능한 재귀 호출에는 O (n N)가 있습니다. 시도한 각 제작마다 O (n) 작업을 수행합니다. P 생성물이 평균적으로 비 터미널 용인 경우 이는 전체 런타임이 O (n NP)이고 고정 문법의 경우 O (n)임을 의미합니다.