PAM 행렬 모델을 이용한 음소 간 유사도 자동 계산 기법

국문 초록 (Abstract)

두 문자열 간의 유사도를 계산하는 문제는 정보 검색, 오타 교정, 스팸 필터링 등 다양한 분야에 응용될 수 있다. 동적 계획법 기반의 유사도 계산 방법을 통하여 한글 문자열의 유사도 계산을 위해서는 우선 음소간의 유사도에 대한 정의가 필요하다. 그러나 기존의 방법들은 수동적 설정에 의한 유사도 점수를 사용하고 있다는 한계점이 있다. 본 논문에서는 PAM(Point Accepted Mutation) 행렬과 유사한 확률 모델을 이용하여 변형 단어 집합으로부터 음소 간의 유사도를 자동적으로 계산하는 기법을 제안한다. 제안 기법은 주어진 변형 단어의 집합 내 유사한 단어 쌍을 찾아 문자열 정렬(Text Alignment)을 수행함으로써 음소변형 규칙을 도출하고, 이로부터 각 음소 쌍의 상호 변형 빈도에 따른 유사도 점수를 계산한다. 실험 결과 특이도(Specificity) 77.2?80.4% 수준에서 불일치 여부에 따른 단순 점수 부여 방식에 비해서는 10.4?14.1%, 수동으로 음소 간 유사도를 직접 설정하는 방식에 비해서는 8.1?11.8%의 민감도(Sensitivity) 향상이 있음을 확인하였다.

다국어 초록 (Multilingual Abstract)

Determining the similarity between two strings can be applied various area such as information retrieval, spell checker and spam filtering. Similarity calculation between Korean strings based on dynamic programming methods firstly requires a definition of the similarity between phonemes. However, existing methods have a limitation that they use manually set similarity scores. In this paper, we propose a method to automatically calculate inter-phoneme similarity from a given set of variant words using a PAM-like probabilistic model. Our proposed method first finds the pairs of similar words from a given word set, and derives derivation rules from text alignment results among the similar word pairs. Then, similarity scores are calculated from the frequencies of variations between different phonemes. As an experimental result, we show an improvement of 10.1%?14.1% and 8.1%?11.8% in terms of sensitivity compared with the simple match-mismatch scoring scheme and the manually set inter-phoneme similarity scheme, respectively, with a specificity of 77.2%?80.4%.

목차 (Table of Contents)

• 요약
• Abstract
• Ⅰ. 서론
• Ⅱ. 관련 연구
• Ⅲ. 제안 기법
• Ⅳ. 실험 및 결과
• Ⅴ. 결론
• 참고문헌
• 저자소개

참고문헌 (Reference)

1 윤태진, "제한된 한글 입력환경을 위한 음소기반 근사 문자열 검색 시스템" 한국정보과학회 37 (37): 788-801, 2010

2 정보통신부, "의미부류별 핵심어매칭기술을 이용한 한국어 및 영어 컨텐츠 유해등급 자동판정 시스템 개발" 2003

3 노강호, "음소의 분류 체계를 이용한 한글 편집 거리 알고리즘" 한국정보과학회 37 (37): 323-329, 2010

4 안희국, "스팸메일 필터링을 위한 한글 변칙어 인식 방법" 한국항행학회 15 (15): 287-297, 2011

5 윤태진, "반 전역 정렬을 이용한 온라인 게임 변형 욕설 필터링 시스템" 한국콘텐츠학회 9 (9): 113-120, 2009

6 송영길, "다양한 스마트폰 키패드 환경에서 유사 단어 검색을 위한 수정된 편집 거리 계산 방법" 한국콘텐츠학회 11 (11): 12-18, 2011

7 한국게임산업진흥원, "게임언어 건전화 지침서연구" 2008

8 J. Setubal, "Introduction to Computational Molecular Biology" PWS Publishing Company 1997

9 Gonzalo Navarro, "A Guided Tour to Approximate String Matching" 33 (33): 31-88, 2001