C/C++에서 CYK algorithm을 구현하고 싶습니다. 그러나 다양한 웹 사이트 의사 코드에서 사용할 수 있으므로이를 효율적으로 구현하는 방법에 대한 대답이 없습니다. 나는지도와 세트 같은 stl 구조체를 사용하는 버전을 작성했지만 매우 느립니다. 바이너리 연산만을 사용하여 구현을 개선하려고 생각했지만 세트로 테이블을 저장하는 방법을 모르겠습니다. 비 터미널에는 8 개의 심볼을, 터미널에는 26 개의 심볼 만 가질 수 있습니다. 나는 프로덕션에 관한 정보를 저장하기 위해 unsigned chars (2^8 -> 0 - 1의 8 가지 위치) 테이블을 사용하려고 생각했지만 저장 방법을 모른다.C++에서 CYK 알고리즘의 속도를 높이려면 어떻게해야합니까?
도움이나 단서를 줄 수 있습니까?
간단한 구현 (의사 코드 포함)으로 많은 정보를 제공하지 않아도 힌트를 제공 할 수 있습니다. 위키
:
입력은 n 개의 문자로 이루어지는 문자열 S하자 : A1 .... 이것에 대한
당신이 Rr을 ...
bool 배열에 비 터미널 기호를 저장합니다. std :: array nonterminal {}; 그런 다음 yu에는 char가있는 위치를 true로 초기화 할 수 있습니다.문법
는 R 비단 문자 R1을 포함하는 간단한 문자열 또는 문자의 벡터를 사용하자.
[static_cast ('C')] = true; 당신은 터미널과 똑같은 일을하고 당신은 정말 빠른 검색 메커니즘을 가지고 있습니다.
이 문법 은 시작 기호 세트 인 서브 세트 Rs를 포함합니다. P [n, n, r] 을 부울의 배열로합시다. P의 모든 요소를 false로 초기화합니다.각각 각 단위 생산에 대해 i = 1 ~ n i = 2 ~ n에 대해 P [i, 1, j] = true로 설정 각 j = 1 ~ n-i + 1 - 각 k = 1 ~ i-1에 대해 의 시작 - 각 생산 RA에 대해 범위 의 파티션 P [j, k, B] 및 P [j + k, ik, C ] P [1, n, x]가 참이면 (x는 집합 s에 대해 반복되며, 여기서 s는 R에 대한 색인입니다) S가 일 때 P [j, i, A] 다른 언어 S는 회원이 아닙니다
언어의 알고리즘은 그 이후 매우 단순 해 보입니다. 단단한 루프 내부에서 임시 값을 초기화하지 않도록하면 괜찮을 것입니다.
재미있을 수도 있습니다.이 이전 질문 (http://stackoverflow.com/questions/13728581/pseudocode-for-cyk-algorithm-please)은이 C++ 구현을 인용합니다. http://nitishkr.wordpress.com/2011/03/29/cyk-algorithm-implementation/ –
지도와 세트를 어떻게 사용합니까? 여기에있는 의사 코드는 http://en.wikipedia.org/wiki/CYK_algorithm에서 부울 배열을 사용합니다. 유일한 세트는 규칙 세트입니다. – Sebastian