http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
- 中文 을 입력하시려면 zhongwen을 입력하시고 space를누르시면됩니다.
- 北京 을 입력하시려면 beijing을 입력하시고 space를 누르시면 됩니다.
RISS 인기검색어
- 검색키워드
- 저자 : 김종현(Joug-Hyun Kim) (검색결과 1 건)
- 무료
- 기관 내 무료
- 유료
-
문맥자유 문법을 위한 병렬 파싱 알고리즘의 설계 및 성능 분석
나동렬(Dong-Yul Ra),이진호(Jin-Ho Lee),김종현(Joug-Hyun Kim) 한국정보과학회 1996 정보과학회논문지(B) Vol.23 No.9
본 논문에서는 일반적인 문맥 자유 언어(Context-Free Language; CFL)를 인식하고 파싱하기 위한 병렬 알고리즘을 제안한다. 이 알고리즘은 하이퍼큐브와 같은 소결합 다중프로세서 시스템(loosely-coupled multiprocessor system)에 적합하도록 설계되었다. 이를 위한 시스템 구조는 간단한 링(ring) 구조이면 되며, n을 입력스트링의 길이라 할때 프로세서의 수 p 는 n 이하의 임의의 수이면 된다(즉, 1≤p≤n). 분석결과에 따르면 제안한 병렬 알고리즘의 시간 복잡도(time complexity)는 최악의 경우에 O(n³/p) 인 것으로 나타났다. 이 알고리즘은 Earley의 알고리즘에 기반을 두고 있기 때문에 임의의 문맥 자유 문법(Context-Free Grammar; CFG)에 대하여 적용될 수 있다. 이 알고리즘은 간단한 작업 배치 방법을 이용하였음에도 높은 성능 향상을 얻을 수 있었다. In this paper, a parallel algorithm is given for recognizing and parsing arbitrary context-free languages. The algorithm operates on multiprocessor systems with loosely-coupled architectures including hypercubes. The requirement on the architecture is simple : the processors need to form just a one-way ring. The requirement on p, the number of processors used, is also flexible: any p satisfying 1≤p≤n (where n is the length of the input string). The analysis shows that the algorithm operates in O(n³/p) time in the worst case. This is the optimal performance one can get with the given architecture. Our parallel algorithm is based on Earley's algorithm and thus it can be used for arbitrary context-free grammars. High performance was achieved with a simple job allocation strategy.
연관 검색어 추천
이 검색어로 많이 본 자료
활용도 높은 자료
