정규 표현식 및 유한 상태 방법

정규 언어를 기반으로 구축된 실용적인 기술 — 정규 표현식을 사용한 패턴 매칭과 유한 상태 변환기를 사용한 문자열-문자열 매핑 — 토큰화, 정규화 및 형태소 분석을 효율적으로 처리합니다.

Definition

유한 상태 방법은 패턴과 매핑이 정규 표현식 또는 유한 상태 오토마타 및 변환기로 표현되어 효율적인 선형 시간 인식을 보장하는 언어 처리 기술입니다.

Scope

문자열에 대한 패턴 언어로서의 정규 표현식, 계산적 구현으로서의 유한 상태 오토마타 및 변환기, 그리고 텍스트 정규화, 토큰화, 철자 및 계산 형태론에 대한 적용을 다룹니다. 음성 및 얕은 처리(shallow processing)에 사용되는 가중 유한 상태 방법이 포함됩니다. 완전한 음운론적 이론과 심층 구문 분석은 범위에 포함되지 않습니다.

Core questions

• 정규 표현식은 텍스트 패턴을 어떻게 정확하게 지정하고 추출할 수 있습니까?
• 유한 상태 변환기는 형태론에서와 같이 표면 형태를 어휘 분석으로 어떻게 매핑합니까?
• 토큰화 및 정규화에 유한 상태 방법이 선호되는 이유는 무엇입니까?

Key concepts

• 정규 표현식
• 유한 상태 변환기
• 토큰화
• 텍스트 정규화
• 형태소 분석
• 2단계 형태론
• 가중 오토마타
• 편집 거리

Key theories

형태론 및 음운론의 정규 모델

음운론적 재작성 규칙과 형태론적 교체가 유한 상태 변환기로 컴파일될 수 있다는 결과로, 분석과 생성을 단일하고 효율적인 프레임워크로 만듭니다.

정규 표현식과 유한 오토마타의 등가성

정규 표현식, 정규 문법 및 유한 상태 오토마타는 모두 정규 언어를 정확하게 설명하므로, 선언적 패턴은 효율적인 인식기로 컴파일될 수 있습니다.

History

정규 표현식은 클레이니(Kleene)의 연구에서 컴퓨터 과학에 도입되어 텍스트 도구에서 널리 사용되었습니다. 1980년대 코스케니에미(Koskenniemi)의 2단계 형태론과 카플란(Kaplan) 및 케이(Kay)의 음운 규칙을 변환기로 컴파일하는 작업은 유한 상태 기술을 형태론적 처리의 핵심 도구로 확립했으며, 이는 비즐리(Beesley)와 카르투넨(Karttunen)의 핸드북에서 통합되었습니다.

Debates

유한 상태 방법은 어디까지 확장될 수 있습니까?

유한 상태 기술은 매우 효율적이지만 정규 현상에 국한됩니다. 이 논쟁은 어떤 언어 처리 작업이 더 풍부한 통계 또는 신경 모델보다 여전히 유한 상태 방법에 의해 가장 잘 수행되는지에 관한 것입니다.

Key figures

• Martin Kay
• Ronald Kaplan
• Kimmo Koskenniemi
• Lauri Karttunen

Seminal works

• kaplan1994
• beesley2003

Frequently asked questions

형태론에 조회 테이블 대신 유한 상태 변환기를 사용하는 이유는 무엇입니까?

변환기는 체계적인 교체를 간결하게 인코딩하고 이전에 본 적이 없는 단어 형태를 분석하거나 생성할 수 있는 반면, 테이블은 명시적으로 나열된 형태만 저장합니다.