임의 순서 차트 파싱 알고리즘

심광섭(Kwangseob Shim) 한국정보과학회 2010 정보과학회논문지 : 소프트웨어 및 응용 Vol.37 No.6

차트 파싱 알고리즘에서는 입력 문장의 왼쪽에서 오른쪽으로 파싱을 진행하여야 한다는 제약이 따른다. 본 논문에서는 이러한 제약을 없앤 임의 순서 차트 파싱 알고리즘을 제안한다. 제안한 알고리즘에서는 입력 문장의 각 단어에 대하여 어떤 순서로 파싱을 하더라도 무방하다. 입력 문장의 왼쪽에서 오른쪽으로 파싱을 진행하는 것은 임의 순서로 파싱을 진행하는 것의 특수한 형태이므로 임의 순서 차트파싱 알고리즘에서도 입력 문장의 왼쪽에서 오른쪽으로 파싱을 하는 것이 가능하다. 제안된 알고리즘은 차트 파싱 알고리즘을 확장한 것으로서 제어 구조가 매우 단순하며 구현도 용이하다. According to the original chart parsing algorithm, a sentence is parsed in a strict left-to-right order. The modified chart parsing algorithm proposed in this paper breaks the strictness. With the proposed algorithm, a sentence is parsed in a random order. Conventional left-to-right parsing is also possible, since left-to-right parsing is a special case of random-order parsing. The proposed parsing algorithm is an extension of chart parsing algorithm and its control structure is very simple, so that it is easy to implement the algorithm.

Investigating the Relationship between L2 Parsing Skills and L2 Reading Fluency

Kim, Seung Jung 한국중앙영어영문학회 2010 영어영문학연구 Vol.52 No.3

The goal of this study was to examine two research questions: First, would Korean EFL undergraduates use L2 parsing skills during L2 reading performance? If so, what L2 linguistic/non-linguistic knowledge would they utilize for the skills? Second, was there any relationship between L2 parsing skills and L2 reading fluency? For the first question, the participants, 52 undergraduates, were asked to answer the survey questions concerning their L2 reading behaviors in regard to L2 parsing. To collect data for the second question, the participants’ L2 parsing skills and L2 reading fluency were measured with an L2 text and a TOEIC test, respectively. The results indicated that the participants recognized the importance of L2 parsing skills and would try to use and practice the skills. They seemed to rely their L2 parsing skills on L2 lexical and syntactic knowledge. The results further indicated that there was a moderate and significant relationship between L2 parsing skills and L2 reading accuracy (r = .389, p < .01), but there was no relationship between L2 parsing skills and L2 reading speed (r = -.202, p > .05). The researcher discussed limitations of the current study and offered suggestions for future studies on L2 parsing skills in L2 reading.

Investigating the Relationship between L2 Parsing Skills and L2 Reading Fluency

김성중 한국중앙영어영문학회 2010 영어영문학연구 Vol.52 No.3

The goal of this study was to examine two research questions: First, would Korean EFL undergraduates use L2 parsing skills during L2 reading performance? If so, what L2 linguistic/non-linguistic knowledge would they utilize for the skills? Second, was there any relationship between L2 parsing skills and L2 reading fluency? For the first question, the participants, 52 undergraduates, were asked to answer the survey questions concerning their L2 reading behaviors in regard to L2 parsing. To collect data for the second question, the participants’ L2 parsing skills and L2 reading fluency were measured with an L2 text and a TOEIC test, respectively. The results indicated that the participants recognized the importance of L2 parsing skills and would try to use and practice the skills. They seemed to rely their L2 parsing skills on L2 lexical and syntactic knowledge. The results further indicated that there was a moderate and significant relationship between L2 parsing skills and L2 reading accuracy (r = .389, p < .01), but there was no relationship between L2 parsing skills and L2 reading speed (r = -.202, p > .05). The researcher discussed limitations of the current study and offered suggestions for future studies on L2 parsing skills in L2 reading.

자바스크립트 동시 파싱을 위한 우선순위 휴리스틱

차명수(Myungsu Cha),박혁우(Hyukwoo Park),문수묵(Soo-Mook Moon) 한국정보과학회 2017 정보과학회 컴퓨팅의 실제 논문지 Vol.23 No.8

웹 어플리케이션은 로딩 시간을 빠르게 하는 것이 중요하다. 파싱은 로딩 과정 중 하나로서 로딩을 길어지게 하는 원인이 되고 있다. 이러한 이유로 파싱 쓰레드를 만들어 파싱을 병렬화 시킨 동시 파싱 기법이 제안되었다[3]. 그러나 동시 파싱은 파싱 순서에 대한 고려가 없다는 한계가 있었다. 본 논문에서는 동시 파싱을 사용할 때 어떤 함수를 먼저 파싱해야 하는가에 대한 휴리스틱을 제안한다. 파싱 우선순위를 정하기 위해 실제 웹 어플리케이션의 자바스크립트 함수들을 분석하여 함수를 세 가지 기준으로 분류하였고, 각 분류의 호출 확률(call probability)을 구하였다. 조사한 호출 확률을 이용하여 높은 호출확률을 갖는 함수들에 높은 파싱 우선 순위를 주었고, 반대로 낮은 호출 확률의 함수들은 낮은 우선 순위를 주었다. 정의한 우선 순위를 토대로 휴리스틱을 제안했고 이를 검증하기 위해 실제 웹 어플리케이션에서 로딩 시간을 측정하여 최대 3.8%, 평균 2.6%의 로딩 시간을 단축하였다. It is important to speed up the loading time of web applications. Parsing is a loading process that contributes to an increased loading time. To address this issue, the optimization called Concurrent Parsing has been proposed which handles the parsing process in parallel by using additional threads. However, Concurrent Parsing has a limitation that it does not consider the priority order of parsing. In this paper, we propose heuristics that exploit priorities of parsing to improve the Concurrent Parsing. For parsing priority, we empirically investigate the sequence of function calls, classify functions into 3 categories, and extract function call probabilities. If a function has high call probability, we give a high priority and if a function has low probability, we give a low priority. We evaluate this priority heuristics on real web applications and get the 2.6% decrease of loading time on average.

SVM을 이용한 결정적 한국어 의존 구문분석

이용훈,이종혁 한국어정보학회 2008 한국어정보학 Vol.10 No.2

In this paper, we present two deterministic Korean dependency parsing algorithms using support vector machine. We modify the forward algorithm proposed first by Kudo(2002) and propose the new backward algorithm. It's well-known fact that backward parsing is more effective in head-final languages. We use proper features to train parsing models for Korean that has a complex word form (eojeol in Korean), an ellipsis possibility of constituents, and so on. In the experiment for Korean Language Information Base System (KIBS) corpus, we achieve 88.25% dependency accuracy that is state-of-the-art performance. It means that proposed methods outperform previous statistical parsing methods and deterministic parsing algorithm is also suitable to Korean parsing.

중국어 구문분석기의 작동 원리와 응용 사례 ― Cparser를 중심으로 ―

박민준,강병규 한국중국언어학회 2019 중국언어연구 Vol.0 No.82

This paper focuses on the process and principle of parsing, which is an essential task for machine to understand the syntactic, semantic structure of a sentence. First, a series of machine analysis procedures such as word segmentation, part-of-speech tagging and parsing of Chinese sentences are visually represented by using Cparser, a rule-based constituency parser developed by Peking University. Next, to better understand parsing mechanism, we explain in detail how the linguistic knowledge is embodied in the lexical, syntactic and semantic component of Cparser, showing their complex interplay that allows automatic parsing. As a practical example, a Chinese textbook treebank is also constructed using Cparser. According to the theoretical and practical discussion in this paper, Peking University Cparser, which is easy to reflect and modify linguistic knowledge, is expected to be widely used as an analysis and verification tool for Chinese grammar research.

Towards Understanding and Applying Chinese Parsing using Cparser

PARK Minjun(朴敏浚),KANG Byeongkwu(姜柄圭) 한국중어중문학회 2020 한국중어중문학회 우수논문집 Vol.- No.-

This paper focuses on parsing processes and principles, which are essential tasks for machines to understand syntactic and semantic structures of a sentence. Machine analysis procedures for Chinese sentences, including word segmentation, and part-of-speech tagging and parsing, were visually represented using Cparser, a rule-based constituency parser developed by Peking University. Then we explained how linguistic knowledge was embodied in Cparser lexical, syntactic and semantic components, and discussed their complex interplay that allows automatic parsing. As a practical example, a Chinese textbook treebank is also constructed using Cparser. According to the theoretical and practical discussion in this paper, Peking University Cparser can easily to reflect and modify undated linguistic knowledge and is expected to be widely used as an analysis and verification tool for Chinese grammar research.

점진적 LL(1) 구문분석에서의 재사용 시점의 계산

이경옥(Gyung-Ok Lee) 한국정보과학회 2010 정보과학회논문지 : 소프트웨어 및 응용 Vol.37 No.11

점진적 구문분석은 기존 입력 문자열에 대한 구문분석 정보를 새로운 문자열의 구문분석 시에 재사용하고자 하는 취지로 연구 개발되었다. 기존 점진적 LL(1) 구문분석에서는 미리 재사용 시점을 계산하여 이를 구문분석 시에 이용하였다. 본 논문에서는 기존의 재사용 시점 계산을 인수분해하여 불필요한 중복 계산 없이 효율적으로 수행하는 방법을 제안한다. 또한 기존의 재사용 시점 파악을 위해서 사용되었던 공통심볼 저장방법과 거리저장방법을 결합하여 공통심볼까지의 거리저장방법을 제안한다. 이에 기반한 효율적인 점진적 LL(1) 구문분석기를 생성한다. Incremental parsing has been developed to reuse the parse result of the original string during the parsing of a new string. The previous incremental LL(1) parsing methods precomputed the reusable point information before parsing and used it during parsing. This paper proposes an efficient reusable point computation by factoring the common part of the computation. The common symbol storing method and the distance storing method were previously suggested to find the reusable point, and by combining the methods, this paper gives the storing method of the distance to common symbols. Based on it, an efficient incremental LL(1) parser is constructed.

한국어 어절 자질들을 활용한 시퀀스 레이블링 기반 한국어 의존 구문 분석

조경철,허윤석,강상우 한국차세대컴퓨팅학회 2021 한국차세대컴퓨팅학회 논문지 Vol.17 No.2

의존 구문 분석은 문장의 지배소와 의존소 간의 관계를 추출하고, 이를 통해 문장의 문법적 구조 분석을 하는 자연 어 이해의 한 과정이다. 기존의 한국어 의존 구문분석 연구들은 높은 시간 복잡도를 가지는 알고리즘이나 별도의 자 료구조가 필요하다는 한계점을 가지고 있다. 본 논문에서는 한국어의 지배소 후위의 법칙에 근거하여 의존 구문분석 문제를 어절단위 문장 입력에 대하여 각 어절이 입력 문장 내에서 의존관계를 가지는 지배소와 의존관계명을 예측하 는 시퀀스 레이블링 문제로 간주한다. 그리고 본 논문에서는 어텐션 기반의 인코더-디코더 프레임워크를 활용하여 기존 연구의 한계점을 모두 고려한 새로운 한국어 의존 구문분석 모델을 제안한다. 또한 본 논문에서 여러 한국어 어절자질들을 한국어 의존 구문 분석에 적용하는 방법을 제안한다. 또한 효과적인 지배소 및 의존관계명 예측을 위 해 본 논문에서는 형태소 태그를 활용한 지배소의 상대적 위치 기반 레이블 인코딩 방법을 제안한다. 결과적으로 다 른 기존 모델들과 비교하여 제안 방법이 효과적임을 확인하였다. Dependency parsing is a process of natural language understanding that extracts the relationships between the head and its dependent in a sentence, analyzing the grammatical structure of the sentence. Existing studies on Korean dependency parsing have limitations in that complex algorithms algorithms with high time complexity or additional data structures are inevitably required. Based on the rule of head final of Korean, in this paper, dependency parsing can be regarded as a sequence labelling problem that predicts the head and its dependent of each word in the input sentence. Then, we propose a novel Korean dependent parsing model that consists of an attention-based encoderdecoder framework which has been shown to be outstanding on prevailing sequence labeling tasks. In addition, we propose a method of applying several eojeol feature to korean dependency parsing. In order to effectively predict the head and its dependent label, we also describe labeling encoding methods based on the relative position of head using part-of-speech tags. As a result, the proposed model has proved to be effective compared with other baseline approaches.

한국어 구문분석 방법론 연구 -복문 구조 분석을 중심으로

유혜원 고려대학교 민족문화연구원 2009 民族文化硏究 Vol.50 No.-

본고는 한국어 구문분석의 활용적 측면에서 효율적인 구문분석방안을 모색해 보고, 복문의 구조 분석을 통하여 효율적인 구문분석의 방법론을 제시하고자 하였다. 한국어 구문분석을 활용하는 시스템을 검색, 대화시스템, 기계번역으로 나누어 살펴보고, 이들 시스템에서 구문분석 정보가 활용되는 양상을 살펴보았다. 이를 통하여 문법 이론적 구조 분석이 실제 구문분석의 활용적 측면에서 중요하지 않을 수 있음을 보여주었다. 본고는 활용도가 높은 구문분석의 결과는 복잡한 계층구조를 배제하고 문장 주요 성분의 기능에 집중해야 한다는 것을 제시하면서, 한국어 복문의 구조를 분석하면서 효율적인 구문분석 방법론을 제시하였다. 구문분석에서 구조적 계층구조를 최소화하는 자질 연산 문법을 도입하여, 복문 분석에 활용하였고, 기존 자질 연산 문법체계에서 다루지 않았던 복합적인 구조의 복문 구조 표시 방법을 제시하였다. This paper aims at surveying the efficient parsing methodology of the Korean sentences for practical use and presenting the Korean parsing methodology. The systems using the parsing information are serach system, auto dialogue system, machine translation, etc. In these systems, the hierarchical structure of the sentences are not important. For the efficient parsing, we exclude the complex hierarchical structure of the sentences and focus on the function of the sentence constituents. On the ground of the feature computation grammar, we analyse the structure of the Korean complex sentences. This methodology is efficient for the parctical use of the Korean parsing. Also, I present the efficient solution of the problem that the study of the feature computation grammar didn't solve.