/*=================================================================*/
/*= 제목  : 형태소 분석기를 위한 RFP                              =*/
/*=         Version 0.1                                           =*/
/*= 작성자: 김성용(sykim@csspirit.kaist.ac.kr)                    =*/
/*= 작성일: 20 Apr 1994                                           =*/
/*=                                                               =*/
/*= Copyright                                                     =*/
/*= a: 이 문서의 사용자 및 인용자는 김성용이 작성한 것임을 밝힐 것=*/
/*= b: 이 문서에 대한 수정/배포시, 출처가 이 문서임을 항상 밝힐 것=*/
/*= c: 이 문서에 대한 상업적 이용시, 저자와의 협의를 거칠 것      =*/
/*=================================================================*/

1. 형태소란?

    - 일정한 음성에 일정한 뜻이 결합되어 있는 말의 가장 작은 단위
      즉, 최소의 유의적 단위(minimum meaningful unit) {KimDB90, indirect reference}

2. 형태소 분석이란?

    - 주어진 입력 문장으로부터 최소 의미 단위인 형태소를 추출하는 과정을 말한다.{KimSY87}

3. 형태소 분석기란?

    - 입력을 받아서
    - 어절을 구성하고 있는 각 형태소를 인식하여
    - 관련 정보를 사전으로부터 탐색 및 선정하여
    - 결과를 적절한 구조로 출력시키는 프로그램의 총칭.

4. 형태소 분석기의 부류(classification)?

    - 일반적으로(처리 알고리즘; 특히 한국어에 대해)
        1) two-level
        2) longest matching
        3) shortest matching
        4) head-tail
        5) tabular (CYK)
        6) syllable-based
        7) pattern matching
      이 중 특히 7번은 얼마 전(1993년) 연세대 학생이 발표한 것으로
      corpus를 분석해서 어절의 구성형태를 모두 모아 놓고
      그냥~~~하는 것임.

    - 입력 방식에 따라 나누어진 것은 아직 없음

    - 입력 대상은 현재 특정 분야(sublanguage?)에 한정된 것들

    - 입력 단위
        1) 어절 단위
        2) 문장 단위
        3) 문단 단위
      대부분의 분석기는 문장 단위를 입력으로 하지만
      실제 내용을 살펴 보면 어절 단위를 가정한 것들임

    - 구현 언어
        1) C
        2) Prolog
        3) ?있을까
      완전한 프로그램을 위해서는 역시 C로 짜야겠고
      rapid prototyping을 위해서는 ?

    - 구현 OS and HW
        1) UNIX family -- SUN family
        2) MSDOS -- PC
        3) HangulTalk -- Mac
      외국의 경우 다양한 하드웨어에 실험 및 구현이 되었다고
      들었으나 국내의 경우에는 주로 1)에 대해...

5. 형태소 분석기의 구조

        1) 프로그램 (한글코드; 불규칙/음운현상 처리; 언어)
        2) 입력(interactive from keyboard ...,
                batch)
        3) 출력(stdout, file)
        4) 사전(사전 엔트리 수; 사전 구조)
        5) 기타?

6. 형태소 분석기의 용도?

      어디에 어떻게 쓸 것인가에 따라 형태소 분석기의
      설계 및 구현이 약간씩 달라질 것

7. 해석과 분석의 차이?

    - 영어로 해석은 interpretation; construction(한영 사전 참조)
      예) 문법적 해석: a grammatical interpretation
          잘못 해석하다: misinterprete, misconstrue
    - 분석은 analysis; assaying(한영 사전 참조)
      예) 원소로 분석하다: analyze ~ into its elements
          실패의 원인을 분석하다: analyze the cause of failure

8. 형태소 분석의 목표
    {cite CSLAB1}
    - 입력문에서 형태소 분리
    - 각 형태소간의 결합 관계 밝힘

9. 형태소 분석에서 다루어야 할 현상들
    {cite CSLAB1}
    - 접속 관계 처리(형태소 분리)
    - 불규칙 및 음운 현상 처리
    - 복합어 처리
    - 미등록어 처리

10. 입력 단위
    - 단어
    - 문장
    - 문단
    - 텍스트

11. 내부코드
    - n-byte,
    - 2-byte
    - 3-byte

12. 어절을 벗어난 형태소 분석을 고려
    - 현재까지는 접속정보가 단순히 한 어절 내 형태소간의 관계로 한정되어
      있었다.
    - 어절 내에서 접속정보를 이용, 미등록어 추정 및 적절한 형태소
      결합현상을 인식할 수 있었던 반면
      두 어절이어야 할 어절이 붙여쓰임으로써 한 어절로 된 경우
      이에 대한 처리를 제대로 하지 못한다.
    ==> 이는 "문법적인 접속정보" 즉 구문정보를 현재의 접속정보에 포함
      시킴으로써 가능하다.
    - 이와 반대로 한 어절이어야 할 어절 사이에 공백이 있어 두 어절로
      되어 있는 경우 이를 해결하는 방법은?

13. 처리 방식
    - interactive
    - batch
 
14. 입력 대상 문자
    - 한글
    - 한자: 한자임을 나타내는 표지(flag 등)와
      한자->한글 변환기 필요
    - 영자
    - 숫자: 숫자의 처리 루틴
    - 문장부호: 문장부호 처리 루틴
      . 특히 쌍으로 나오는 문장부호의 처리 기법
    - 심볼 및 특수문자
    - 사용자 정의 문자

15. 선행 처리기
    {cite CSLAB1}
    - 문서 편집기에 종속적인 요소의 처리(축소, 확대, 특수문자 등)
    - 포매팅 명령어를 무시
    - 쌍으로 이루어진 문자의 처리(괄호, 따옴표 등)
    - 한자를 한글로 치환(한자의 독음 처리)
    - 한자나 영어로 구성된 어절을 별도의 화일에 저장
    - 미완성 한글 검사
    - 도표화 같은 그래픽 문자 처리
    - 맞춤법 검사에서 틀린 것으로 판단된 어절에 대한 사용자 인터페이스
    - 틀린 어절에 대하여 사용자가 원하는 경우 올바른 어절 후보 제시
    - 한글 코드의 변환

16. 형태소에 대한 alternatives가 있을 때(예: 한 형태소가 여러 품사를 가지거나
여러 의미를 가질 때)
    - 형태소간 접속 가능성에 대해 현재와 같이 0/1로 하지 않고
    - weighted connectability information을 부여 <- corpus engineering
    - 그러한 alternative들 간에 priority 또는 weight를 설정 <-- corpus engineering
    - 가능한 형태소 결합열이 둘 이상일 때
      . 모든 가능한 결합열을 생성시키되
      . 결합열 간의 우선순위 계산, 구문 분석시 best-first strategy 사용 가능

17. 형태소간 결합 관계에 정확도(결합의 적합성)에 대한 probability
  또는 likelihoodness를 부여한다면
    - 기존의 접속정보표 수정
    - 접속정보에서 결합 가능성을 검사시에 현재의 True/False의 이진 구조에서
      multi-valued structure로 전환
    - likelihood는 9단계(UNIX Consultant에서 사용한 값과 동일)로 설정
      TRUE -> VERY-LIKELY -> LIKELY -> SOMEWHAT-LIKELY
      -> UNCERTAIN
      -> SOMEWHAT-UNLIKELY -> UNLIKELY -> VERY-UNLIKELY -> FALSE
    - certainty factor들의 combination 방법 필요 [LeeHJ93]
  ==> 1) 다양한 후보 형태소 열 사이의 ranking 가능, reasonable ranking.
      2) 미등록어, 오류 등의 교정시에도 적용 가능

18. 축약현상 및 불규칙 현상의 처리
    - 규칙으로 처리: rule description language + compiler
    - 규칙으로 처리 불가능한 것은 사전에 등록

19. 미등록어의 품사 결정
    - heuristic 정보를 이용
      . 관형사 다음의 형태소는 명사? 등과 같은 ...

20. 사전: 통합 사전
    - 품사 정보
    - 접속 정보
    - 구문 정보
    - 의미 정보

21. 형태소 분석기에는 다음의 모듈이 기본적으로 필요할 것 [LeeMS93]
    - 형태소 결합 테이블 (접속정보표 또는 품사간 결합정보 또는 세분화된
      category들간의 결합 정보)
      . 문제: 어느 정도로 결합 정보가 구체화되어야 하는가
      . 문제: 어떻게 정보를 이해 및 관리가 쉽도록 encoding할 것인가
    - 불규칙 변형 테이블
      . 문제: 불규칙 현상을 어떻게 분류할 것인가 (어학적 측면에서 문법에
              따른 분류에 맞출 것인지, 아니면 보다 상세한 나름대로의
              분류를 정할 것인지)
      . 문제: Procedural vs. Declarative
              .. 장단점의 비교
      . 문제: 어떤, 어느 정도의 방법을 사용하여 over-generation을 최소화
              할 것인가
              .. Lookahead의 숫적 증가 [KimSY87]
              .. 음절 정보의 이용 [KangSS93]
    - 준말 변형 테이블
      . 규칙으로 (procedurally) 처리할 수 있는 것들은 규칙으로
      . 문제: "생각지", "괜찮치" 등의 처리 방법

22. 형태-구문 해석(morphosyntactic analysis) {cite KimDB92}
    - 관용어구 처리
      . 숙어 사전을 이용하거나 숙어 정보가 첨가된 일반 사전을 이용
      . 숙어를 이루는 중심 형태소에 숙어의 가능성이 있다는 정보를 표시
    - 수 표현의 인식
      . 기수인 경우 명사, 형용사, 대명사로 쓰일 수 있음
      . 서수인 경우 형용사, 명사, 부사로 쓰일 수 있음
      . 두 경우 모두 속성값 "FORM {number}"를 준다.

23. 수, 소수, 분수, 년도, 전화번호 등 처리
    - eg. one-eighth --> 1/8

24. 수식의 처리: 숫자와 더불어 사칙연산 기호, 등호, 부등호 등의
    - 수학기호가 연속하여 결합되어 있을 때, 이 형태소들을 하나의
      처리 단위로 결합하여 하나의 수식으로 처리(체언으로?)

25. 단위 명사
    - 숫자와 더불어 단위를 나타내는 명사가 나오면
      두 형태소를 결합하여 하나의 구문 단위로 결합
      eg. 5m 30cm, 10 feet 6 inch, 120 kg 500g, 120.5 kg
    - 복합 단어들을 인식하고 이에 대한 적절한 품사와 약간의 의미 정보를 부가

26. 오류 보정
    - 전거 화일
      . 표준어 규정에 어긋나는 오류
      . 표기법 오류
         .. 한글 맞춤법
         .. 한자 표기
         .. 외래어 표기법
    - 형태소 분석기의 추가적 기능
      . 붙띄 오류: 붙여 써야 할 어절을 띄어 쓰는 오류
        .. 이웃한 두 어절이 모두 어휘 분석 오류 어절인 경우
        .. 앞 어절은 어휘 분석 오류 어절, 뒤 어절은 오류 어절이 아닌 경우
        .. 앞 어절은 오류 어절이 아니고 뒤 어절은 어휘 분석 오류 어절인 경우
      . 띄붙 오류 : 띄어써야 할 어절을 붙여 쓰는 오류
        .. 오류 어절인 경우
        .. 오류 어절이 아닌 경우
    - spell checker 기능
      . 체언 + 조사 오류
        (3) 윗어른을 모시고 사니까 (윗어른 -> 웃어른 : 체언 오류)
        (4) 김정일이가 머리를 짧게 깎으라고 지시를 내려
           (김정일이가 -> 김정일이 : 조사 오류)
        (5) 주의력을 집중하여 열심으로 익혀 왔기 때문에
           (열심으로 -> 열심히 : 체언과 조사의 결합 오류)
      . 어간 + 어미 오류
        (6) 변덕스럽고 괴퍅한 일면은 있지만 (괴퍅한 -> 괴팍한 : 형용사 오류)
        (7) 목을 길게 늘리면 키가 커지고 (늘리면 -> 늘이면 : 동사 오류)
        (8) 목돈을 마련하기에 알맞는 예금 (알맞는 -> 알맞은 : 어미 오류)
        (9) 깨끗하고 아름다와야 할 부엌
           (아름다와야 -> 아름다워야 : 형용사와 어미가 결합하여 발생하는 오류)
        (10) 자유를 향하여 나르는 새
            (나르는 -> 나는 : 동사와 어미가 결합하여 발생하는 오류)

27. 오류의 발견 및 교정 {cite KangSS90}
    - 조사 오류(제3형 오류): 체언과 조사의 결합 정보에 의해 발견 및 교정
    - 어미 오류1(제4형 오류): "알맞는"(-->"알맞은"), "주시구료"(-->"주시구려")처럼
      어미에 오류가 있는 경우. 용언과 어미의 결합 정보나 그릇된 어미 규칙에 의해
      오류 발견 및 교정
    - 어미 오류2(제5형 오류): "들었을라 싶어"(-->"들었을까 싶어")처럼 용언의
      활용어미에 오류가 있는 경우, 용언과 보조용언의 결합시 어미에 대한 제약조건
      규칙에 의해 오류 발견 및 교정.
      한자어의 영향으로 어미가 잘못 쓰인 "조직화한다"(-->"조직한다"),
      "해석되어진다"(-->"해석된다")와 같은 오류도 여기에 속한다.
    - 어간 변형 오류1(제6형 오류): "아름다와야"(-->"아름다워야"), "낯설은"(-->"낯선")
      과 같이 불규칙 용언의 변형 부분이 잘못된 경우. 그릇된 변형 규칙과 불규칙
      동사의 어간 변형 규칙에 의해 발견 및 교정
    - 어간 변형 오류2(제7형 오류): "믿기지"(--> "믿어지지")와 같이 용언의 피동형이
      잘못된 오류. 용언의 피동형 정보에 의해 오류 발견 및 교정.
    - 어간 변형 오류3(제8형 오류): 용언 + 어미 + 보조동사 형태로 용언의 어미와
      보조동사가 서로 어울리지 않는 경우.(예: "끼어 주다" --> "끼워 주다").
      모든 동사와 보조동사의 결합 정보 필요

28. 품사의 애매성 해소 방법   {cite KimDB92}
    "...지금까지 연구된 품사의 애매성 해소 방법은 크게 통계적인
    방법과 규칙 기반형(rule-based) 방법이 있다
    (1) 통계적인 방법은 대량의 코퍼스로부터 품사의 애매성 해소를 하는 데 필요한 정보를
        객관적으로 구하고 이를 쉽게 이용할 수 있는 방법을 제공한다.
        Church가 제안한 방법은 .. 어휘적 확률(lexical probabilities: 코퍼스에서 어떤
        단어에 대하여 특정 품사가 나올 확률 P(tag | word))와 문맥적 확률(contextual
        probabilities: 코퍼스에서 어떤 단어의 특정 품사가 그 단어 다음에 나오는 단어들의
        특정 품사들과 함께 나올 수 있는 확률 P(tag1 | tag2 tag3))의 곱을 최대로 하는 쪽으로
        품사를 지정한다. 이러한 방법의 정확율은 95% 이상을 보장한다.
    (2) 규칙 기반형 방법은 언어학적인 현상에 바탕을 두어 문제의 해결을 시도한다.
        이 방법은 통계적인 방법에서의 필수적인 요소라 할 수 있는 코퍼스가 없이도
        직관적으로 규칙을 만들 수 있고, 통계적인 방법에서 범하기 쉬운 오류(국부적인
        정보만을 이용하므로써 일어나는 오류)의 가능성을 거의 없앨 수 있는 장점이
        있지만, 도메인에 의존하는 경향이 상당히 높고, 수천 개의 규칙들을 가지고
        행하는 것이 보통이기 때문에 규칙들 사이의 제어가 복잡하고, 또 정확율도
        통계적인 방법에 비해 낮다는 단점을 지니고 있다. 그러나, 최근에 Marcus(1991)가
        제안한 방법은 상당히 객관적인 방법에 의해 규칙을 구할 뿐만 아니라 그 규칙
        수도 상당히 작고, 정확율도 95% 정도까지 나온다...두 방법 모두 기본적으로
        대량의 태깅된 코퍼스를 필요로 한다. 또 .. LDOCE(Longman Dictionary of
        Contemporary English)와 같은 전자 사전을 이용하지 않으며 단지 약간의
        접사 테이블과 단어와 품사의 쌍으로 된 테이블만을 이용한다. 이러한 테이블들은
        품사의 애매성을 해소하는데 없어서는 안될 정보, 즉 한 단어가 특정 품사로
        쓰일 확률(lexical probabilities) 정보와 한 단어가 가질 수 있는 품사들에 관한
        정보를 준다. 따라서, 전자 사전을 이용하는 기계번역과 같은 응용분야에서 이
        두 방법을 적용하기 위해서는 한 단어가 특정 품사로 쓰일 수 있는 확률을
        사전에 두어야 한다. 그 이유는 보통의 전자사전은 한 단어에 대해서 자주 쓰이는
        품사와 아주 드물게 쓰이는 품사의 구분이 없기 때문이다."

29. 사전

    - 요구사항
      . 형태소, 구문, 의미 정보
      . 모든 단어를 포함?
      . 범용적 구조 vs. 특정 응용에 맞게 customized?
      . knowledge base와의 연관 관계
      . 일반 용어와 전문 용어의 구분?
    - 분석과 생성에 bidirectional?
    - knowledge base
      . appropriate representation
      . grouping/navigating, etc.
    - cooccurrence db?
      . 단어 사용 정보
    - corpus
      . tagged (lexical, syntactic, semantic)
      . standard format
    - dictionary management utility
      . 저장 및 검색
      . 표준 format
      . converting format
      . browse editor
      . extraction/merge
      . user interface

30. 형태소 분석기의 성능 평가

    1) 속도(speed)

      가) 일반사항
          - 모든 alternatives를 찾아내고
          - alternatives의 ranking까지 할 때
            . 사전 구조 및 access 과정에 따라 달라지고
            . hardware speed에 따라 달라지므로
          - timer를 이용하여 CPU time을 측정하는 방법에는 무리가 있고
          - 알고리즘의 best, average, worst case performance에서
            order of time을 고려할 수밖에 없을 것
          - 현재 제안된 기능을 수행하는 해석기의 경우 O(n**3)??
      나) 하나의 방법
          - 가정A: hardware platform은 4-8MB memory와 충분한 HD space를 가진
                   33MHz 486DX
          - 가정B:
            . 한 단어가 평균 2.5개의 형태소로 되어 있고
            . string의 평균 길이가 8 바이트 정도이며
            . 불규칙 및 음운 현상 검사, 사전 검색 횟수 등이 한 단어당
              평균 1.5회인 경우를 가정하면
          - 사전 검색은 단어당 10회 정도
          - 알고리즘 수행 시간은 negligible??
          - 단어당 시간은 <사전 access time> * 10회 + alpha
          - 초당 10-20 개 정도의 입력 단어 처리, 이를 화일에 출력까지 하는 정도의 성능이면?

    2) 정확도
          - speller 측면에서는 100%를 달성하기는 불가능
          - 형태소 분석기 자체에서 오류가 없는 입력을 가정할 경우 100% 가능
            단, 사전에 해당 형태소 및 관련 정보가 모두 등록되어 있는 경우를 전제
          - 각종 format 변환 등 선행 및 후행 처리기 부분에 대한 기준은 별도 고려 필요

    3) 성능 평가 방법

      가) 일반사항
          test와 examination을 병행
          - test: sample data로부터 주어진 성능 규격을 만족하는지 검사
          - examination: hardware/software 환경, 기타 inspection 수행
      나) test 방법
          1) 단어(word) 단위 성능 평가
             . corpus: 표준어 규정/맞춤법 규정 등에 있는 모든 단어 예를 수집
             . 초기 : 95% 정도의 정확도
             . 최종 : 100%의 정확도
          2) 구(phrase) 단위의 성능 평가
             . corpus : 보조 용언 리스트 및 관용어구 리스트 등
             . 초기 : 95% 정도의 정확도
             . 최종 : 98-100% 의 정확도
             . 단, 띄어쓰기 등 여러가지 오류를 배제한 상황을 전제
          3) 문장(sentence) 이상 단위의 성능 평가
             . corpus:
               .. 신문 사설 00건
               .. 국민학교, 중학교, 고등학교 교과서 00건
               .. 대학교 작문 교재에 실려 있는 (대표적인) 소설 및 수필 00건
               .. 각 분야별 학술지 (컴퓨터, 산업공학, 경제, 법률, 무역, ... 등)는
                  사전 엔트리의 성격에 따라 선별 사용

========= END ========