제5장 형태소분석

제 5 장형태소분석

형태소분석 형태소의정의 의미가있는최소의단위 (minimally meaningful unit) 문법적, 관계적인뜻을나타내는단어또는단어의부분 형태소분석 단어 ( 또는어절 ) 를구성하는각형태소분리 분리된형태소의기본형및품사정보추출 2

형태소분석과정 형태소분석과정 분석후보생성 문법규칙에맞는후보생성 형태소분리와기본형추정 분석후보로부터옳은결과선택 형태소끼리의결합제약조건만족 사전에서기본형확인 3

형태소분석의관점 언어학 / 국어학의관점 새로운형태론적언어현상의발견및규명 : 정성적 (qualitative) 배경지식 : 인간의언어능력 전산언어학의관점 컴퓨터프로그램으로형태소분석하는방법론 : 정량적 (quantitative) 형태론적현상들을컴퓨터로처리하는방법 다양한형태론적현상들을처리할수있는가 : 처리범위 ( 분석률 ) 얼마나정확한분석을수행하는가 : 정확성 시스템이얼마나효율적인가 : 처리속도와기억공간 4

언어, 응용분야별형태소분석기 언어특성에따른형태소분석기 띄어쓰기를안하는언어 ( 중국어, 일본어등 ) : 단어분리문제중요 굴절이심한언어 ( 핀란드어등 ) : 형태소의원형복원강조 교착어 ( 한국어등 ) : 형태소분리문제중요 응용분야에따른형태소분석기 기계번역, 기계이해시스템 : 분석의정확성, 애매성해결강조 자동색인, 정보검색 : 명사 ( 키워드 ) 추출, 복합명사 / 미등록어처리 맞춤법검사및교정 : 오류어분석문제중요 5

형태소분석의일반적과정 (1) 형태소분석입력 : 단어 ( 어절 ) 형태소분석출력 단어를이루고있는형태소들의기본형 각형태소의품사또는문법적 / 관계적인의미를나타내는기호 형태소분석의예 감기는 (NOUN 감기 ) + (JOSA 는 ) (VERB 감기 ) + (EOMI 는 ) (VERB 감 ) + (EOMI 기 ) + (JOSA 는 ) 가시는 (NOUN 가시 ) + (JOSA 는 ) (VERB 가시 ) + (EOMI 는 ) (VERB 가 ) + (P-EOMI 시 ) + (EOMI 는 ) (VERB 갈 ) + (P-EOMI 시 ) + (EOMI 는 ) 6

형태소분석의일반적과정 (2) 입력어절 전처리 분석후보생성 결합제약검사 분석후보선택 원형복원규칙 결합제약규칙 시스템사전 후처리 분석결과 7

형태소분석의일반적과정 (3) 1. 전처리단계 문장으로부터단어추출 문장부호분리 숫자나특수문자열처리 2. 분석후보생성 형태소분리 불규칙원형복원 4. 옳은후보선택 사전탐색 단어형성규칙 5. 후처리단계 복합명사추정 사전미등록어처리 준말처리 3. 결합제약검사 모음조화 형태소결합제약 : 음운현상에따른제약등 8

한국어의형태소분석방법론 단어검색방향에따른분류 Left-to-right Right-to-left Bi-directional 형태소분석방법론 Tabular 파싱법 최장 / 최단일치법 음절단위분석법 9

Tabular 파싱법 Bottom-up 방식 단어를이루는가능한형태소추출 자모단위의 substring을사전에서검색 추출된형태소 삼각테이블에저장 동적프로그래밍기법 : 처리속도향상 10

Tabular Parsing Algorithm(Right -> Left) 1 2 3 4 5 6 7 8 ( 초 ) 1 ㅏ ( 중 ) 2 ㅁ ( 종 ) 3 ( 초 ) 4 ㅣ ( 중 ) 5 접속검색은하늘색상자만수행한다. ( 초 ) 6 ㅡ ( 중 ) 7 ( 종 ) 8 " " 사전검색 감기감가ㅁ기는 사전명사동사동사명사형전성어미명사형전성어미보조사 접속정보명사 + 보조사동사 + 명사형전성어미명전 + 명전

Tabular Parsing Algorithm(Right -> Left) 1 2 3 4 5 6 7 8 ( 초 ) 1 ㅏ ( 중 ) 2 ㅁ ( 종 ) 3 ( 초 ) 4 ㅣ ( 중 ) 5 접속검색은하늘색상자만수행한다. ( 초 ) 6 " " 사전검색 ㅡ ( 중 ) 7 ( 종 ) 8 " " 사전검색 감기감가ㅁ기는 사전명사동사동사명사형전성어미명사형전성어미보조사 접속정보명사 + 보조사동사 + 명사형전성어미명전 + 명전

Tabular Parsing Algorithm(Right -> Left) 1 2 3 4 5 6 7 8 ( 초 ) 1 ㅏ ( 중 ) 2 ㅁ ( 종 ) 3 ( 초 ) 4 ㅣ ( 중 ) 5 접속검색은하늘색상자만수행한다. ( 초 ) 6 " " 사전검색 " 느 " 사전검색 ㅡ ( 중 ) 7 ( 종 ) 8 " " 사전검색 감기감가ㅁ기는 사전명사동사동사명사형전성어미명사형전성어미보조사 접속정보명사 + 보조사동사 + 명사형전성어미명전 + 명전

Tabular Parsing Algorithm(Right -> Left) 1 2 3 4 5 6 7 8 ( 초 ) 1 ㅏ ( 중 ) 2 ㅁ ( 종 ) 3 ( 초 ) 4 ㅣ ( 중 ) 5 접속검색은하늘색상자만수행한다. ( 초 ) 6 " " 사전검색 " 느 " 사전검색 " 는 " 사전검색 -> 는 : 보조사 ㅡ ( 중 ) 7 ( 종 ) 8 " " 사전검색 감기감가ㅁ기는 사전명사동사동사명사형전성어미명사형전성어미보조사 접속정보명사 + 보조사동사 + 명사형전성어미명전 + 명전

Tabular Parsing Algorithm(Right -> Left) 1 2 3 4 5 6 7 8 ( 초 ) 1 ㅏ ( 중 ) 2 ㅁ ( 종 ) 3 ( 초 ) 4 " " 사전검색 ㅣ ( 중 ) 5 ( 초 ) 6 " " 사전검색 " 느 " 사전검색 " 는 " 사전검색 -> 는 : 보조사 ㅡ ( 중 ) 7 ( 종 ) 8 " " 사전검색 감기감가ㅁ기는 사전명사동사동사명사형전성어미명사형전성어미보조사 접속정보명사 + 보조사동사 + 명사형전성어미명전 + 명전

Tabular Parsing Algorithm(Right -> Left) 1 2 3 4 5 6 7 8 ( 초 ) 1 ㅏ ( 중 ) 2 ㅁ ( 종 ) 3 ( 초 ) 4 " " 사전검색 " 기 " 사전검색 -> 기 : 명전 -> 접속검색 - >" 는 " ㅣ ( 중 ) 5 접속가능체크 ( 초 ) 6 " " 사전검색 " 느 " 사전검색 " 는 " 사전검색 -> 는 : 보조사 ㅡ ( 중 ) 7 ( 종 ) 8 " " 사전검색 감기감가ㅁ기는 사전명사동사동사명사형전성어미명사형전성어미보조사 접속정보명사 + 보조사동사 + 명사형전성어미명전 + 명전

Tabular Parsing Algorithm(Right -> Left) 1 2 3 4 5 6 7 8 ( 초 ) 1 ㅏ ( 중 ) 2 ㅁ ( 종 ) 3 ( 초 ) 4 " " 사전검색 " 기 " 사전검색 -> 기 : 명전 -> 접속검색 - >" 는 " 분석결과저장 기 + 는 ㅣ ( 중 ) 5 ( 초 ) 6 " " 사전검색 " 느 " 사전검색 " 는 " 사전검색 -> 는 : 보조사 ㅡ ( 중 ) 7 ( 종 ) 8 " " 사전검색 감기감가ㅁ기는 사전명사동사동사명사형전성어미명사형전성어미보조사 접속정보명사 + 보조사동사 + 명사형전성어미명전 + 명전

Tabular Parsing Algorithm(Right -> Left) 1 2 3 4 5 6 7 8 ( 초 ) 1 ㅏ ( 중 ) 2 ㅁ ( 종 ) 3 ( 초 ) 4 " " 사전검색 " 기 " 사전검색 -> 기 : 명전 -> 접속검색 - > 기 + 는 " " 기 " 사전검색 " 기느 " 사전검색 " 기는 " 사전검색기 + 는 ㅣ ( 중 ) 5 ( 초 ) 6 " " 사전검색 " 느 " 사전검색 " 는 " 사전검색 -> 는 : 보조사 ㅡ ( 중 ) 7 ( 종 ) 8 " " 사전검색 감기감가ㅁ기는 사전명사동사동사명사형전성어미명사형전성어미보조사 접속정보명사 + 보조사동사 + 명사형전성어미명전 + 명전

Tabular Parsing Algorithm(Right -> Left) 1 2 3 4 5 6 7 8 ( 초 ) 1 ㅏ ( 중 ) 2 ㅁ ( 종 ) 3 " ㅁ " 사전검색 -> ㅁ : 명전 -> 접속검색 -> ㅁ + 기 + 는 " ( 초 ) 4 " " 사전검색 " 기 " 사전검색 -> 기 : 명전 -> 접속검색 - > 기 + 는 " " 기 " 사전검색 " 기느 " 사전검색 접속가능체크 " 기는 " 사전검색기 + 는 ㅣ ( 중 ) 5 ( 초 ) 6 " " 사전검색 " 느 " 사전검색 " 는 " 사전검색 -> 는 : 보조사 ㅡ ( 중 ) 7 ( 종 ) 8 " " 사전검색 감기감가ㅁ기는 사전명사동사동사명사형전성어미명사형전성어미보조사 접속정보명사 + 보조사동사 + 명사형전성어미명전 + 명전

Tabular Parsing Algorithm(Right -> Left) 1 2 3 4 5 6 7 8 ( 초 ) 1 ㅏ ( 중 ) 2 ㅁ ( 종 ) 3 " ㅁ " 사전검색 -> ㅁ : 명전 -> 접속검색 -> ㅁ + 기 + 는 " 분석결과저장 ㅁ + 기 + 는 ( 초 ) 4 " " 사전검색 " 기 " 사전검색 -> 기 : 명전 -> 접속검색 - > 기 + 는 " " 기 " 사전검색 " 기느 " 사전검색 " 기는 " 사전검색기 + 는 ㅣ ( 중 ) 5 ( 초 ) 6 " " 사전검색 " 느 " 사전검색 " 는 " 사전검색 -> 는 : 보조사 ㅡ ( 중 ) 7 ( 종 ) 8 " " 사전검색 감기감가ㅁ기는 사전명사동사동사명사형전성어미명사형전성어미보조사 접속정보명사 + 보조사동사 + 명사형전성어미명전 + 명전

Tabular Parsing Algorithm(Right -> Left) 1 2 3 4 5 6 7 8 ( 초 ) 1 " " 사전검색 ㅏ ( 중 ) 2 ㅁ ( 종 ) 3 " ㅁ " 사전검색 -> ㅁ : 명전 -> 접속검색 -> ㅁ + 기 + 는 " " ㅁ기는 " 사전검색 " ㅁ " 사전검색 " ㅁ기 " 사전검색 " ㅁ기 " 사전검색 " ㅁ기느 " 사전검색ㅁ + 기 + 는 ( 초 ) 4 " " 사전검색 " 기 " 사전검색 -> 기 : 명전 -> 접속검색 - > 기 + 는 " " 기 " 사전검색 " 기느 " 사전검색 " 기는 " 사전검색기 + 는 ㅣ ( 중 ) 5 ( 초 ) 6 " " 사전검색 " 느 " 사전검색 " 는 " 사전검색 -> 는 : 보조사 ㅡ ( 중 ) 7 ( 종 ) 8 " " 사전검색 감기감가ㅁ기는 사전명사동사동사명사형전성어미명사형전성어미보조사 접속정보명사 + 보조사동사 + 명사형전성어미명전 + 명전

Tabular Parsing Algorithm(Right -> Left) 1 2 3 4 5 6 7 8 " 가 " 사전검색 -> 가 : 동사 ( 초 ) 1 " " 사전검색 -> 접속검색 - > 가 + ㅁ + 기 + 는 " ㅏ ( 중 ) 2 ㅁ ( 종 ) 3 " ㅁ " 사전검색 -> ㅁ : 명전 -> 접속검색 -> ㅁ + 기 + 는 " 접속가능체크 " ㅁ기는 " 사전검색 " ㅁ " 사전검색 " ㅁ기 " 사전검색 " ㅁ기 " 사전검색 " ㅁ기느 " 사전검색ㅁ + 기 + 는 ( 초 ) 4 " " 사전검색 " 기 " 사전검색 -> 기 : 명전 -> 접속검색 - > 기 + 는 " " 기 " 사전검색 " 기느 " 사전검색 " 기는 " 사전검색기 + 는 ㅣ ( 중 ) 5 ( 초 ) 6 " " 사전검색 " 느 " 사전검색 " 는 " 사전검색 -> 는 : 보조사 ㅡ ( 중 ) 7 ( 종 ) 8 " " 사전검색 감기감가ㅁ기는 사전명사동사동사명사형전성어미명사형전성어미보조사 접속정보명사 + 보조사동사 + 명사형전성어미명전 + 명전

Tabular Parsing Algorithm(Right -> Left) 1 2 3 4 5 6 7 8 ( 초 ) 1 " " 사전검색 " 가 " 사전검색 -> 가 : 동사 -> 접속검색 -> 가 + ㅁ + 기 + 는 " 분석결과저장 가 + ㅁ + 기 + 는 ㅏ ( 중 ) 2 ㅁ ( 종 ) 3 " ㅁ " 사전검색 -> ㅁ : 명전 -> 접속검색 -> ㅁ + 기 + 는 " " ㅁ기는 " 사전검색 " ㅁ " 사전검색 " ㅁ기 " 사전검색 " ㅁ기 " 사전검색 " ㅁ기느 " 사전검색ㅁ + 기 + 는 ( 초 ) 4 " " 사전검색 " 기 " 사전검색 -> 기 : 명전 -> 접속검색 - > 기 + 는 " " 기 " 사전검색 " 기느 " 사전검색 " 기는 " 사전검색기 + 는 ㅣ ( 중 ) 5 ( 초 ) 6 " " 사전검색 " 느 " 사전검색 " 는 " 사전검색 -> 는 : 보조사 ㅡ ( 중 ) 7 ( 종 ) 8 " " 사전검색 감기감가ㅁ기는 사전명사동사동사명사형전성어미명사형전성어미보조사 접속정보명사 + 보조사동사 + 명사형전성어미명전 + 명전

Tabular Parsing Algorithm(Right -> Left) 1 2 3 4 5 6 7 8 ( 초 ) 1 " " 사전검색 " 가 " 사전검색 -> 가 : 동사 -> 접속검색 -> 가 + ㅁ + 기 + 는 " 감 사전검색 -> 감 : 동사 -> 접속검색 -> 감 + 기 + 는 " 분석결과저장 가 + ㅁ + 기 + 는 감 + 기 + 는 ㅏ ( 중 ) 2 ㅁ ( 종 ) 3 " ㅁ " 사전검색 -> ㅁ : 명전 -> 접속검색 -> ㅁ + 기 + 는 " " ㅁ기는 " 사전검색 " ㅁ " 사전검색 " ㅁ기 " 사전검색 " ㅁ기 " 사전검색 " ㅁ기느 " 사전검색ㅁ + 기 + 는 ( 초 ) 4 " " 사전검색 " 기 " 사전검색 -> 기 : 명전 -> 접속검색 - > 기 + 는 " " 기 " 사전검색 " 기느 " 사전검색 " 기는 " 사전검색기 + 는 ㅣ ( 중 ) 5 ( 초 ) 6 " " 사전검색 " 느 " 사전검색 " 는 " 사전검색 -> 는 : 보조사 ㅡ ( 중 ) 7 ( 종 ) 8 " " 사전검색 감기감가ㅁ기는 사전명사동사동사명사형전성어미명사형전성어미보조사 접속정보명사 + 보조사동사 + 명사형전성어미명전 + 명전

Tabular Parsing Algorithm(Right -> Left) 1 2 3 4 5 6 7 8 ( 초 ) 1 " " 사전검색 " 가 " 사전검색 -> 가 : 동사 -> 접속검색 -> 가 + ㅁ + 기 + 는 " 감 사전검색 -> 감 : 동사 -> 접속검색 -> 감 + 기 + 는 " 감기 사전검색 -> 감기 : 명사 -> 접속검색 -> 감기 + 는 " 분석결과저장 가 + ㅁ + 기 + 는 감 + 기 + 는 감기 + 는 ㅏ ( 중 ) 2 ㅁ ( 종 ) 3 " ㅁ " 사전검색 -> ㅁ : 명전 -> 접속검색 -> ㅁ + 기 + 는 " " ㅁ기는 " 사전검색 " ㅁ " 사전검색 " ㅁ기 " 사전검색 " ㅁ기 " 사전검색 " ㅁ기느 " 사전검색ㅁ + 기 + 는 ( 초 ) 4 " " 사전검색 " 기 " 사전검색 -> 기 : 명전 -> 접속검색 - > 기 + 는 " " 기 " 사전검색 " 기느 " 사전검색 " 기는 " 사전검색기 + 는 ㅣ ( 중 ) 5 ( 초 ) 6 " " 사전검색 " 느 " 사전검색 " 는 " 사전검색 -> 는 : 보조사 ㅡ ( 중 ) 7 ( 종 ) 8 " " 사전검색 감기감가ㅁ기는 사전명사동사동사명사형전성어미명사형전성어미보조사 접속정보명사 + 보조사동사 + 명사형전성어미명전 + 명전

최장일치법과최단일치법 Tabualr 파싱법의효율문제해결 우선순위 ( 형태소의길이에따라 ) 가높은형태소를우선적으로분석 한가지분석결과만필요할때사용 최장일치법 단어를이루는형태소의길이가긴것을우선 최단일치법 단어를이루는형태소의길이가짧은것을우선 26

음절단위분석법 알고리즘과사전탐색의비효율성문제해결 한국어의음절특성 ( 단위음절특성, 부분음절특성 ) 이용 분석후보들의자격요건을강화하여분석후보의수를최소화 음절단위분석방법 문법형태소분리 음절단위로분리 조사 / 어미의음절특성이용 형태론적변형 원형복원법사용 형태변이가일어난음절의특성이용 복합명사및미등록어추정 특이한언어현상 ( 예 : 불구동사, 준말등 ) 기분석사전에분석결과저장 음절단위비교및음절단위사전구성 27

영어형태소분석 (1) 영어형태소분석 규칙변형 (regular inflection) 단어의원형복원 접두사및접미사분리 불규칙변형 (irregular inflection) 기분석사전으로분석결과수록 접미사분리 명사 : 복수형, 소유격 books book + s, John s John + s 동사 : 3 인칭단수, 과거 / 과거분사 / 현재분사 changing change + ing 형용사, 부사 : 비교급, 최상급 -ly, -ation 등 28

영어의형태소분석 (2) 형태소에대한정보제공 형태소의기본형 품사 수 ( 단수, 복수 ) 단어의쓰인형태 동사 : 현재, 과거, 과거분사, 형용사, 부사 : 원급, 비교급, 최상급, 대명사 : 주격, 소유격, 목적격 단어의쓰인유형 형용사 : 서술적용법, 한정적용법 접속사 : 등위접속사, 종속접속사 부사 : 원급, 비교급, 최상급 29

한국어형태소분석기에필요한기능 조사와어말어미의분리 ( 어미의변이체포함 ) 생략된서술격조사복원 선어말어미의분리 ( 어말어미가발견된경우에만 ) 접미사분리 불규칙원형복원 붙여쓰기가허용되는경우 ( 한음절체언과보조용언 ) 준말처리 복합어추정 미등록어추정 영문자, 숫자처리 수사처리 사전탐색기능 30

한국어형태소분석기의구조 단어 전처리 문법형태소분리체언분석용언분석단일형태소분석복합어추정조사생략준말처리 문법형태소사전어휘형태소사전전문용어사전사용자정의사전기분석사전 후처리 분석결과 31

형태소분리 형태소분리대상 어근, 조사, 어미, 선어말어미, 접미사 형태소분리예 사무실에서부터였다고는 사무실 + 에서부터 + 이 + 었 + 다고는 선어말어미의분리 시 / 었 / 겠 만선어말어미로간주 32

불규칙의원형복원 불규칙유형과각유형별끝음절특성 ㄷ 불규칙 : 10 개 ( 걷 / 긷 / 닫 / 묻 / 싣 / 겯 / 눋 / 듣 / 붇 / 컫 ) ㅂ 불규칙 : 46 개 ㅅ 불규칙 : 9 개 ( 긋 / 낫 / 붓 / 잣 / 짓 / 끗 / 뭇 / 잇 / 젓 ) ㅎ 불규칙 : 10 개 ( 갛 / 닿 / 랗 / 맣 / 얗 / 겋 / 떻 / 렇 / 멓 / 옇 ) 러 불규칙 : 1 개 르 불규칙 : 1 개 으 탈락 : 11 개 ( 그 / 끄 / 느 / 뜨 / 르 / 쁘 / 쓰 / 으 / 크 / 트 / 프 ) 원형복원 끝음절특성에해당되는어근에대해서만 분석후보의수최소화 사전탐색 overhead 줄임 33

복합어와미등록어추정 복합명사추정 4/5/6 음절복합명사 : 복합명사의 97% 3음절복합명사 : 사전에수록 7음절이상복합명사 : 미등록어처리 미등록어추정 문법형태소분리후어근을미등록어로간주 체언으로분석된후보 ( 즉, 조사가분리된후보 ) 두음절이상의어미가분리된후보 용언보다는체언후보우선 34

형태소분석기의성능 분석률 (analysis ratio) 정확히분석한비율 (%) 잘못분석한비율 틀린단어의인식비율 처리속도 단위시간당분석한단어의수 알고리즘의복잡도와사전탐색회수에비례 애매성분석여부 애매성이내포된단어의모든분석결과생성 애매성해결여부 35

음절기반한국어형태소분석 음절기반품사태깅 형태소분석 품사태깅 : 나는 나 /NP+ 는 /JX 갔다 갔 /VV_EP+ 다 /EC 형태소분석 : 갔 /VV_EP 가 /VV+ 았 /EP+ 다 /EC 형태소분석중의성 : 나 /VV 나 /VV or 날 /VV 최근연구 (KCC, 13) 확률정보를이용하여중의성해결 이창기 (KCC-2013) Structural SVM 기반 심광섭 ( 인지과학 -2011, 정보과학회 -2013) CRF 기반 나승훈 ( 한글및한국어 -2012) CRF 기반 Chung-Hye Han, Martha Palmer (Machine Translation, 2005)

딥러닝기반의 End-to-End 한국어형태소분석 ( 동계학술대회 16) Attention + Input-feeding + Copying mechanism