JM2) Regular Expressions, Text Normalization, Edit Distance
Natural Language Processing
Regular Expressions, Text Normalization, Edit Distance
자연어를 처리함에 있어서, 즉 우리가 흔히 쓰는 자연어를 기계가 파악하도록 만듬에 있어서, 가장 중요한 도구 중 하나는 바로 Regular Expression, 정규 표현식이다.
정규 표현식은 문서로부터 우리가 원하는 문장들을 추출하는 데에 쓰일 수도 있으며, 문서로부터 표를 추출하여 처리하는 데에도 쓰이기도 한다.
특히 정규 표현식은 텍스트 정규화 (text normalization)에서 중요한 열쇠를 담당하는데, 텍스트 정규화란 텍스트를 이전에 없던 단일 표준 형식으로 변환하는 과정을 일컫는다.
예를 들어서 우리가 언어를 처리하는 첫 번째 작업 중 대부분은 먼저 tokenization 작업, 즉 텍스트에서 단어를 분리하고 token화 하는 작업이 있다. 영어 단어들은 종종 공백을 통해서 단어들이 떨어져 있긴 하지만 공백을 통해서 단어를 tokenization하는 것이 항상 효율적이지는 못하다. New York과 Rock 'n' roll과 같은 단어를 생각해보자. 이 두 단어들은 공백을 통해서 떨어져 있지만 하나의 단어로써 작동하는 단어의 대표적 예시들이다. 또 다른 예시로는 I'm이 있다. I'm은 공백이 존재하진 않지만 실제로는 I am으로 작동하는, 즉 공백으로써 작용해야하는 단어 중 하나의 예이다. 트위터나 텍스트에 존재하는 이모티콘 ^^이나 해쉬태그 #nlproc와 같은 단어들도 따로 처리해야한다. 그렇기 때문에 단어를 토큰화하는 작업은 중요하면서도 매우 어려운 과제 중 하나이다.
또 다른 텍스트 정규화 작업으로는 lemmatization(분류화)이 있다. 이것은 두 단어가 표면적으로는 차이가 있지만 실제로는 같은 형태의 뜻을 가지고 있는지 분류하는 작업이다. 예를 들어서, sang, sung, sings와 같은 단어들은 동사 sing의 형태들 중 하나이다. sing은 이 때, 공통 분류군의 대표자로 분류되고 이러한 단어들은 모든 sing으로 lemmatizer에 의해 mapping된다.
마지막으로, 우리는 단어와 문장을 비교하는 작업을 필요로 한다. 이러한 비교 작업은 edit distance를 이용하는 데, 이는 두 문장이 문장 구조나 특징들에 기반하여 얼마나 유사한지 비교하는 작업이다.
Regular Expressions
정규 표현식, Regular Expression은 텍스트 검색 문장을 정의하는 언어 중 하나로써 컴퓨터 과학의 표준화에서 중요한 역할을 맡고 있다. 정규 표현식은 모든 컴퓨터 언어, 워드 프로세서, 언어 처리 도구 등에서 사용되고 있으며, 형태적으로 문장 세트들을 특성화하는 대수 표기법이다. 이러한 대수 표기법을 알고 있을 시에 우리는 대용량의 corpus(말뭉치)로부터 필요한 문장을 검색하는 데 일종의 검색 패턴을 알고 있는 것과 다름없다. 이러한 말뭉치는 하나의 문서일수도, 문서들이 모인 collection일수도 있다. 이러한 정규화된 표현이 과연 검색을 위해 어떻게 Design되었으며 어떠한 구조를 갖고있는지 알아보도록 하자.
Basic Regular Expression Patterns
정규화 표현의 가장 간단한 종류는 간단한 문자열이다. 예를 들어 문자열에서 우리가 woodchuck와 같은 단어가 있는지 찾고 싶다면 /woodchuck/와 같이 입력하면 된다. /Buttercup/은 Buttercup이라는 문자열을 포함하는 문자열들을 찾게 된다. Divider 기호 /를 가진 expression은 Divider 앞 뒤를 기준으로 어떠한 문자가 와도 상관없다는 뜻을 의미한다.
그러나 정규화 표현은 대문자와 소문자를 구별한다. 만약 /a/와 같이 검색했을 경우, 대문자 A에 대해서는 검색하지 못한다. 만약 내가 a나 A가 있는 문자열을 검색하고 싶다면 []와 같은 중괄호를 이용하면 된다.
/[wW]/와 같은 표현은 문자열 내에서 소문자 w나 대문자 W를 포함하는 문자열을 검색하고 싶다는 뜻과 같다.
이러한 형태는 [abc]나 [0123456789]와 같이 세 개이상의 문자도 표현가능하다. 즉, 중괄호에 있는 문자들은 'or'와 같은 뜻을 가지고 있다고해도 무방하다.
만약 0부터 9사이의 숫자 문자를 검색하고 싶은데, 1234567890들을 모두 쓰기 귀찮다면 -, minus 기호를 사용하여 표시할 수 있다.
예를 들어, /[0-9]/와 같은 표현은 내가 0부터 9사이의 숫자 문자열을 가지고 있는 문자들을 검색하고 싶다는 뜻과 같다. 이는 숫자뿐만 아니라 /[A-Z]/와 같이 대문자도, 또한 모든 영어 문자를 의미할 때에는, /[A-Za-z]/와 같이 표현할 수도 있다.
만약 내가 검색하고 싶지 않은 문자열에는 ^ 기호를 붙여주면 된다.
/[^A-Za-z]/와 같은 표현은 영어 문자가 아닌 처음으로 나타나는 문자를 보여달라는 뜻이고, /[^Ss]/와 같은 표현은 S나 s가 아닌 처음으로 나타나는 문자를 뜻하게 된다.
아까 언급하지 못한 것이 있었는데, 모든 표현은 해당 표현을 만족하는 문자열 중 가장 첫 번째 문자열을 보여준다.
물음표 문자 ?는 물음표 바로 앞에 있는 문자가 옵션으로 달려있다는 것을 말한다. 즉 바로 앞에 문자가 있어도 되고, 없어도 되는 식을 찾는다는 것이다. 이 표현을 쓰는 예시중 하나는 바로 복수형 명사가 되겠다. ant나 ants와 같이 같은 단어를 의미하지만 단수, 복수를 나눌 때에, 내가 오직 개미에 대한 정보만 필요하다면 /ants?/와 같이 정규 표현식으로 검색할 수 있을 것이다.
우리가 반복적으로 나타나는 문자를 검색하고 싶을 때에는 * 기호를 이용하면 된다.
예를 들어,
baa!
baaa!
baaaa!
baaaaa!
....
와 같은 문자열을 검색하고자 한다.
그럴 경우 우리는 /baaa*/와 같이 검색할 수 있다. /a*/는 a가 0이나 그 이상의 빈도수만큼 나타나는 문자열들을 찾는다는 것이다.
/[ab]*/는 a나 b가 0번이나 그 이상의 빈도수만큼 나타나는 문자열을 찾는다는 것과 같은 의미이다.
+ 기호는 *와 달리 한 번이나 그 이상의 빈도수만큼 나타나는 문자열을 찾는다는 것이다.
즉 +앞에 있는 문자를 적어도 한 번은 포함하는 문자열을 찾는다는 것과 같은 뜻이다.
아까 /baaa*!/는 결국 /baa+!/과 같은 뜻을 갖게된다.
. 기호는 모든 문자열을 의미한다. 즉 모든 문자열 중에 아무거나 와도 된다는 뜻이다.
Disjunction, Grouping, and Precedence
우리가 or와 같은 표현을 하고 싶을때, []와 같은 중괄호 기호를 쓴다고 얘기를 했었다. 하지만 중괄호의 한계는 바로 하나의 문자에 해당한다는 것이고, 복수의 문자를 or로 표현할 수는 없다. 복수의 문자를 or로 표현하기 위해 |와 같은 bar 기호를 사용한다.
예를 들어, cat이나 dog와 같은 단어를 찾을 때에는 /cat|dog/와 같이 작성한다. 이를 disjunction 기호라 한다.
허나 bar 기호가 모든 or를 표현할 수는 없다. 앞에 무조건 검색해야할 문자열과 구분을 만들기 위해서는 중괄호인 () 기호를 사용해야한다.
예를 들어 guppy의 복수형은 guppies이다. 만약 guppy와 관련된 정보를 찾고 싶을 때에는 /gupp(y|ies)/와 같은 식으로 앞의 무조건 검색해야할 문자열과 구분지어야만 한다.
만약 내가 Column 1 Column 2 Column 3 와 같은 식을 찾고 싶다면,
/Column [0-9]+ */와 같이 작성할 수 있다. 이는 single column인 Column 1만 검색될 것이다.
전체적인 문장을 찾고 싶다면, 즉 Column 1 Column 2 Column 3와 같은 총 문장을 찾고 싶다면,
/(Column [0-9]+ *)*/와 같이 작성해야할 것이다.
보다 많은 Operator는 아래 표를 참고하면 좋을 듯하다.
Words and Corpora
우리가 단어를 처리하는 방법에 대해 논하기 전에, 우리는 무엇을 단어로써 셀 것인지에 대해 결정해야 한다. 먼저 Corpus라는, 컴퓨터가 읽을 수 있는 텍스트나 연설의 말뭉치들을 보자.
일단 그 예시 중 Brown University에서 발표한 문장을 하나 보도록 하자.
He stepped out into the hall, was delighted to encounter a water brother.
만약 우리가 쉼표(,)나 마침표(.)를 단어로써 세지 않는다면, 해당 문장에는 13개의 단어가 있지만, 쉼표나 마침표같은 문장 부호들을 단어로 센다면, 15개의 단어를 가지고 있다고 판단할 것이다. 문장 부호들은 문맥을 이어주고나 문장, 혹은 단어들을 나누는 기준선이 되고, 문장 자체의 의미를 바꿔버리는 양상을 띠기도 한다. 그렇기 때문에 POS 태깅이나 parsing, 연설 분석 과정에서 우리는 때때로 문장 부호들을 단어로 처리하기도 한다.
이러한 적혀진 문장 말고도, 우리는 누군가가 실제로 발언한 말들을 분석해야하는 경우도 있다. 이렇게 입으로 발언한 말은, utterance라고 부른다.
I do uh main- mainly business data processing
이 문장에는 두 가지의 disfluency가 존재한다. 첫째는 단어를 번복하는 행위에서 나온 broken-off 단어인 main-이고, 이를 fragment라 부른다. 두번째는 uh와 um같이 문장 자체의 의미와 연관성이 없는 이들이다. 이를 filler나 filled pause라 부른다.
그러나 실제로 uh나 um같은 disfluency는 연설 분석에서 다가오는 단어들을 예측하는데 실제적인 도움을 주는데, 왜냐하면 이러한 소리는 연설자가 주장이나 자신의 생각을 재시작하려는 신호로써 일반적으로 쓰이는 단어들이기 때문이다.
그 외에도 앞에서 언급한 sing, sang, sung과 같은 단어, cats, cat과 같은 단어등의 처리를 다뤄야한다.
우리는 Corpus에서 발견되는 단어들의 종류, 즉 Vocabulary에 담겨있는 구별되는 단어들을 Types라 부르며, 현재 존재하는 단어들을 Tokens라 부른다.
Herdan's Law나 Heaps' Law로 불리우는 법칙에 의해 이러한 type의 갯수 $|V|$와 token 갯수 $N$ 사이에는 일정한 관계가 따르는데,
$k$ and $\beta$ are positive constants, and 0<$\beta$<1, then $|V| = kN^{\beta} $
와 같은 법칙을 따르게 된다.
Text Normalization
Text에 대해 NLP를 적용하기 전에 text들은 normalize되어야 한다. 보통 normalization process에는 세 가지 part가 존재한다.
1. Segmenting/Tokenizing words from running text
텍스트로부터 단어들을 토큰화, 구분화하기
2. Normalizaing word formats
단어들의 형태를 모두 일반화하기
3. Segmenting sentences in running text.
텍스트에서 문장들을 모두 구분화하기
Unix tools for crude tokenization and normalization - 생략
Word Tokenization and Normalization
단어들로부터 텍스트를 구분하는 임무인 tokenization과, 단어/토큰들을 기준있는 형태로 맞추기 위한 임무인 normalization을 위해서는 보다 엄격하고 복잡한 알고리즘이 필요하다.
예를 들어서 apostrophes로 표현되는 what're, we're와 같은 토큰들을 what are, we are등으로 확장시켜주는 알고리즘이 필요한데, 그렇기 때문에 tokenizer는 이러한 축소적 표현을 확장하는 데 사용될 수 있어야한다.
또한 tokenization 알고리즘은 New York이나 rock 'n' roll과 같이 white space로 구분되는 단어들을 하나로 묶어주는 능력이 필요하며 그렇기 때문에 Tokenization은 name, data, organization을 검사하는 능력인 named entity detection을 필요로 한다.
tokenization 표준 중 하나는 Penn Treebank Tokenization이 있으며, 만약 문장이 input으로 들어갈 경우 아래 그림과 같은 문장들이 tokenization이 된다.
이렇게 분류된 token들은 normalized될 수 있는데, 예를 들어 다양한 형태를 가지고 있는 단어인 USA나 US와 같은 단어들은 하나의 같은 정규화된 형태를 가지게 된다. 이러한 정규화과정은 매우 가치있으며 정보 검색에 있어서 US query를 입력해도, USA query가 나오게 되는 것이다.
이중에 case folding이라는 것은 단어가 대문자든 소문자등 그 형태를 맞추는 것을 의미하며 이 역시 정보 검색에 있어서 중요한 역할을 한다.
Word Segmentation in Chinese: the MaxMatch algorithm - 생략
Lemmatization and Stemming
Lemmatization은 두 단어가 다른 형태를 띠고 있음에도 같은 root word를 갖고 있는지에 대해 판단하는 것이다. 예를 들어 단어 am, is 그리고 are는 공통된 lemma인 be를 가지고 있다. 단어 dinners와 dinner는 같은 공통된 lemma인 dinner를 가지고 있다. 그것의 lemma로 단어를 대표하는 것은 웹 검색에 있어서 중요한 역할을 가지고 있다.
그렇다면 lemmatization은 어떻게 실행될 수 있는가? lemmatization 중 가장 복잡한 방법은 단어의 morphological parsing (형태학적 분석)을 완료하는 것이다. Morphology는 morphme이라 불리는 보다 작은 단어를 생산하는 unit으로부터 단어들을 건설해나가는 형태학적 학문이다. morpheme의 두 가지 class는 다음과 같이 구분된다: stems - 단어의 중심 morpheme으로써 단어의 중요 의미를 전달함. affixes - 다양한 형태로써 추가적 의미를 더해주는 역할.
예를 들어 단어 "cats"를 살펴보자. 단어 cat은 여기서 stems로써 단어 고양이 그 자체의 의미를 전달하지만, s는 복수형이라는 의미를 더해주는 affixes 역할을 하게되는 것이다.
The Porter Stemmer
유한 상태 변환기를 사용하여 완전한 형태소 분석기를 구축하는 것은 단어 형식의 형태학적 변형을 다루는 가장 일반적인 방법이지만, 때로는 우리는 간단하지만 더 까다로운 접미어를 사용하는 경우가 있다. 형태소 분석의 naive한 버전은 stemming이라 불리며, stemming algorithm으로 가장 널리 사용되는 것은 간단하고 효과적인 Porter algorithm이다. 다음과 같은 예시문을 보자.
This was not the map we found in Billy Bones's chest, but an accurate copy, complete in all things-names and heights and soundings-with the single exception of the red crosses and the written notes.
이러한 예시문은 나음과 같은 stemmed output을 갖는다:
Thi wa not the map we found in Billi Bone s chest but an accur copi complet in all thing name and height and sound with the singl except of the red cross and the written note
이 알고리즘은 cascade로써 이미 쓰여진 규칙에 기반하여 작동하여 input으로부터 output을 내놓는다.
다음 예시는 이러한 규칙의 한 예시이다:
ATIONAL -> ATE (e.g., relational -> relate)
ING -> $ \epsilon $ if stem contains vowel
SSES -> SS (e.g., grasses -> grass)
Porter stemmer의 더 자세한 규칙들은 Martin Porter의 홈페이지에서 찾을 수 있다.
하지만 이러한 형태의 규칙들은 단어들을 과일반화시키거나 덜 일반화시키는 경우가 있는데, 그러한 경우는 다음과 같은 표에서 확인할 수 있다.
Sentence Segmentation
문장 구분은 텍스트 처리 작업에서 또 다른 중요한 단계이다. text를 문장으로 나누는 가장 유용한 것은 마침표와 같은 문장 기호를 사용하는 것이다.
일반적으로 문장 tokenization 방법은 binary classfier를 사용하여 마침표가 단어의 일부분인지 문장의 구분 마커인지 확인하는 것으로 결정한다.
Minimum Edit Distance
자연어 처리의 대부분은 두 문자열이 얼마나 유사한가를 측정하는데에 연관이 있다. 예를 들어 철자 보정에서 사용자는 잘못된 문자열을 입력했다고 하자. (graffe라고 하자.) 사용자가 의미하는 바를 원하고, 유저는 아마 graffe와 유사한 단어 중 하나를 의도하여 입력했을 것이다. 유사한 단어들 중 후보군 사이에는 graffe에서 오직 한 문자가 다른 giraffe가 있을 것이고, giraffe는 grail이나 graf보단 graffe와 유사해 보인다.
또 다른 예시로는 coreference가 있다. coreference는 두 가지의 문자열이 같은 enity를 참조하고 있는지를 결정하는 역할을 하는 것이다:
Stanford President John Hennessy
Stanford University President John Hennessy
이 두 문장은 오직 한 단어에만 차이가 있지만 사실은 같은 사람을 참조해야한다.
Edit distance는 우리에게 문자열의 유사성을 알려주는 하나의 척도이다. 일반적으로 두 문자열 사이의 minimum edit distance는 하나의 문자열에서 다른 문자열로 변환되기 위한 필요한 operation 최소 갯수를 의미한다.
다음과 같은 그림을 보면 이해가 더 쉽게 갈 것이다.
INTENTION이라는 단어 EXECUTION이라는 단어로 변환되기 위해서는 1개의 Deletion, 1개의 Insertion, 그리고 3개의 Substitution이 필요하다. Substitution은 변환시키려는 문자열을 지우고 그리고 입력해야하므로 총 2개의 operation으로 취급한다.
즉 총 8개의 operation이 필요하므로 여기서 Levenshtein distance는 8이 되는 것이다.
The Minimum Edit Distance Algorithm
우리가 흔히 생각했을 때, minimum edit distance를 우리가 구하라고 하면 다음과 같은 식을 생각해볼 수 있다.
For string A and B, Let n(A) and n(B) be the number of characters in string and Let c(A,B) be the number of common characters between string A and string B.
Then, $(Minimum Edit Distance) = (d-constant) * (|n(A) - n(B)|) + (min(n(A),n(B)) - c(A,B)) * (s-constant)$
그렇다면 공통된 문자열을 찾는 것은 알고리즘으로 어떻게 구분하는가? 그저 CYK 알고리즘을 사용하면 구할 수 있다.
아래 그림은 Min-Edit_Distance에 관한 알고리즘을 풀어놓은 것이다.
Backtrace를 하는 작업도 우리가 대학 시절에 배웠던 문자열 비교 후 Backtrace와 완전히 똑같다!
다음 장은
JM4인 Language Modeling with N gram을 커버해보려 한다.
Regular Expressions, Text Normalization, Edit Distance
자연어를 처리함에 있어서, 즉 우리가 흔히 쓰는 자연어를 기계가 파악하도록 만듬에 있어서, 가장 중요한 도구 중 하나는 바로 Regular Expression, 정규 표현식이다.
정규 표현식은 문서로부터 우리가 원하는 문장들을 추출하는 데에 쓰일 수도 있으며, 문서로부터 표를 추출하여 처리하는 데에도 쓰이기도 한다.
특히 정규 표현식은 텍스트 정규화 (text normalization)에서 중요한 열쇠를 담당하는데, 텍스트 정규화란 텍스트를 이전에 없던 단일 표준 형식으로 변환하는 과정을 일컫는다.
예를 들어서 우리가 언어를 처리하는 첫 번째 작업 중 대부분은 먼저 tokenization 작업, 즉 텍스트에서 단어를 분리하고 token화 하는 작업이 있다. 영어 단어들은 종종 공백을 통해서 단어들이 떨어져 있긴 하지만 공백을 통해서 단어를 tokenization하는 것이 항상 효율적이지는 못하다. New York과 Rock 'n' roll과 같은 단어를 생각해보자. 이 두 단어들은 공백을 통해서 떨어져 있지만 하나의 단어로써 작동하는 단어의 대표적 예시들이다. 또 다른 예시로는 I'm이 있다. I'm은 공백이 존재하진 않지만 실제로는 I am으로 작동하는, 즉 공백으로써 작용해야하는 단어 중 하나의 예이다. 트위터나 텍스트에 존재하는 이모티콘 ^^이나 해쉬태그 #nlproc와 같은 단어들도 따로 처리해야한다. 그렇기 때문에 단어를 토큰화하는 작업은 중요하면서도 매우 어려운 과제 중 하나이다.
또 다른 텍스트 정규화 작업으로는 lemmatization(분류화)이 있다. 이것은 두 단어가 표면적으로는 차이가 있지만 실제로는 같은 형태의 뜻을 가지고 있는지 분류하는 작업이다. 예를 들어서, sang, sung, sings와 같은 단어들은 동사 sing의 형태들 중 하나이다. sing은 이 때, 공통 분류군의 대표자로 분류되고 이러한 단어들은 모든 sing으로 lemmatizer에 의해 mapping된다.
마지막으로, 우리는 단어와 문장을 비교하는 작업을 필요로 한다. 이러한 비교 작업은 edit distance를 이용하는 데, 이는 두 문장이 문장 구조나 특징들에 기반하여 얼마나 유사한지 비교하는 작업이다.
Regular Expressions
정규 표현식, Regular Expression은 텍스트 검색 문장을 정의하는 언어 중 하나로써 컴퓨터 과학의 표준화에서 중요한 역할을 맡고 있다. 정규 표현식은 모든 컴퓨터 언어, 워드 프로세서, 언어 처리 도구 등에서 사용되고 있으며, 형태적으로 문장 세트들을 특성화하는 대수 표기법이다. 이러한 대수 표기법을 알고 있을 시에 우리는 대용량의 corpus(말뭉치)로부터 필요한 문장을 검색하는 데 일종의 검색 패턴을 알고 있는 것과 다름없다. 이러한 말뭉치는 하나의 문서일수도, 문서들이 모인 collection일수도 있다. 이러한 정규화된 표현이 과연 검색을 위해 어떻게 Design되었으며 어떠한 구조를 갖고있는지 알아보도록 하자.
Basic Regular Expression Patterns
정규화 표현의 가장 간단한 종류는 간단한 문자열이다. 예를 들어 문자열에서 우리가 woodchuck와 같은 단어가 있는지 찾고 싶다면 /woodchuck/와 같이 입력하면 된다. /Buttercup/은 Buttercup이라는 문자열을 포함하는 문자열들을 찾게 된다. Divider 기호 /를 가진 expression은 Divider 앞 뒤를 기준으로 어떠한 문자가 와도 상관없다는 뜻을 의미한다.
/[wW]/와 같은 표현은 문자열 내에서 소문자 w나 대문자 W를 포함하는 문자열을 검색하고 싶다는 뜻과 같다.
이러한 형태는 [abc]나 [0123456789]와 같이 세 개이상의 문자도 표현가능하다. 즉, 중괄호에 있는 문자들은 'or'와 같은 뜻을 가지고 있다고해도 무방하다.
예를 들어, /[0-9]/와 같은 표현은 내가 0부터 9사이의 숫자 문자열을 가지고 있는 문자들을 검색하고 싶다는 뜻과 같다. 이는 숫자뿐만 아니라 /[A-Z]/와 같이 대문자도, 또한 모든 영어 문자를 의미할 때에는, /[A-Za-z]/와 같이 표현할 수도 있다.
만약 내가 검색하고 싶지 않은 문자열에는 ^ 기호를 붙여주면 된다.
/[^A-Za-z]/와 같은 표현은 영어 문자가 아닌 처음으로 나타나는 문자를 보여달라는 뜻이고, /[^Ss]/와 같은 표현은 S나 s가 아닌 처음으로 나타나는 문자를 뜻하게 된다.
아까 언급하지 못한 것이 있었는데, 모든 표현은 해당 표현을 만족하는 문자열 중 가장 첫 번째 문자열을 보여준다.
물음표 문자 ?는 물음표 바로 앞에 있는 문자가 옵션으로 달려있다는 것을 말한다. 즉 바로 앞에 문자가 있어도 되고, 없어도 되는 식을 찾는다는 것이다. 이 표현을 쓰는 예시중 하나는 바로 복수형 명사가 되겠다. ant나 ants와 같이 같은 단어를 의미하지만 단수, 복수를 나눌 때에, 내가 오직 개미에 대한 정보만 필요하다면 /ants?/와 같이 정규 표현식으로 검색할 수 있을 것이다.
우리가 반복적으로 나타나는 문자를 검색하고 싶을 때에는 * 기호를 이용하면 된다.
예를 들어,
baa!
baaa!
baaaa!
baaaaa!
....
와 같은 문자열을 검색하고자 한다.
그럴 경우 우리는 /baaa*/와 같이 검색할 수 있다. /a*/는 a가 0이나 그 이상의 빈도수만큼 나타나는 문자열들을 찾는다는 것이다.
/[ab]*/는 a나 b가 0번이나 그 이상의 빈도수만큼 나타나는 문자열을 찾는다는 것과 같은 의미이다.
+ 기호는 *와 달리 한 번이나 그 이상의 빈도수만큼 나타나는 문자열을 찾는다는 것이다.
즉 +앞에 있는 문자를 적어도 한 번은 포함하는 문자열을 찾는다는 것과 같은 뜻이다.
아까 /baaa*!/는 결국 /baa+!/과 같은 뜻을 갖게된다.
. 기호는 모든 문자열을 의미한다. 즉 모든 문자열 중에 아무거나 와도 된다는 뜻이다.
Disjunction, Grouping, and Precedence
우리가 or와 같은 표현을 하고 싶을때, []와 같은 중괄호 기호를 쓴다고 얘기를 했었다. 하지만 중괄호의 한계는 바로 하나의 문자에 해당한다는 것이고, 복수의 문자를 or로 표현할 수는 없다. 복수의 문자를 or로 표현하기 위해 |와 같은 bar 기호를 사용한다.
예를 들어, cat이나 dog와 같은 단어를 찾을 때에는 /cat|dog/와 같이 작성한다. 이를 disjunction 기호라 한다.
허나 bar 기호가 모든 or를 표현할 수는 없다. 앞에 무조건 검색해야할 문자열과 구분을 만들기 위해서는 중괄호인 () 기호를 사용해야한다.
예를 들어 guppy의 복수형은 guppies이다. 만약 guppy와 관련된 정보를 찾고 싶을 때에는 /gupp(y|ies)/와 같은 식으로 앞의 무조건 검색해야할 문자열과 구분지어야만 한다.
만약 내가 Column 1 Column 2 Column 3 와 같은 식을 찾고 싶다면,
/Column [0-9]+ */와 같이 작성할 수 있다. 이는 single column인 Column 1만 검색될 것이다.
전체적인 문장을 찾고 싶다면, 즉 Column 1 Column 2 Column 3와 같은 총 문장을 찾고 싶다면,
/(Column [0-9]+ *)*/와 같이 작성해야할 것이다.
보다 많은 Operator는 아래 표를 참고하면 좋을 듯하다.
Words and Corpora
우리가 단어를 처리하는 방법에 대해 논하기 전에, 우리는 무엇을 단어로써 셀 것인지에 대해 결정해야 한다. 먼저 Corpus라는, 컴퓨터가 읽을 수 있는 텍스트나 연설의 말뭉치들을 보자.
일단 그 예시 중 Brown University에서 발표한 문장을 하나 보도록 하자.
He stepped out into the hall, was delighted to encounter a water brother.
만약 우리가 쉼표(,)나 마침표(.)를 단어로써 세지 않는다면, 해당 문장에는 13개의 단어가 있지만, 쉼표나 마침표같은 문장 부호들을 단어로 센다면, 15개의 단어를 가지고 있다고 판단할 것이다. 문장 부호들은 문맥을 이어주고나 문장, 혹은 단어들을 나누는 기준선이 되고, 문장 자체의 의미를 바꿔버리는 양상을 띠기도 한다. 그렇기 때문에 POS 태깅이나 parsing, 연설 분석 과정에서 우리는 때때로 문장 부호들을 단어로 처리하기도 한다.
이러한 적혀진 문장 말고도, 우리는 누군가가 실제로 발언한 말들을 분석해야하는 경우도 있다. 이렇게 입으로 발언한 말은, utterance라고 부른다.
I do uh main- mainly business data processing
이 문장에는 두 가지의 disfluency가 존재한다. 첫째는 단어를 번복하는 행위에서 나온 broken-off 단어인 main-이고, 이를 fragment라 부른다. 두번째는 uh와 um같이 문장 자체의 의미와 연관성이 없는 이들이다. 이를 filler나 filled pause라 부른다.
그러나 실제로 uh나 um같은 disfluency는 연설 분석에서 다가오는 단어들을 예측하는데 실제적인 도움을 주는데, 왜냐하면 이러한 소리는 연설자가 주장이나 자신의 생각을 재시작하려는 신호로써 일반적으로 쓰이는 단어들이기 때문이다.
그 외에도 앞에서 언급한 sing, sang, sung과 같은 단어, cats, cat과 같은 단어등의 처리를 다뤄야한다.
우리는 Corpus에서 발견되는 단어들의 종류, 즉 Vocabulary에 담겨있는 구별되는 단어들을 Types라 부르며, 현재 존재하는 단어들을 Tokens라 부른다.
Herdan's Law나 Heaps' Law로 불리우는 법칙에 의해 이러한 type의 갯수 $|V|$와 token 갯수 $N$ 사이에는 일정한 관계가 따르는데,
$k$ and $\beta$ are positive constants, and 0<$\beta$<1, then $|V| = kN^{\beta} $
와 같은 법칙을 따르게 된다.
Text Normalization
Text에 대해 NLP를 적용하기 전에 text들은 normalize되어야 한다. 보통 normalization process에는 세 가지 part가 존재한다.
1. Segmenting/Tokenizing words from running text
텍스트로부터 단어들을 토큰화, 구분화하기
2. Normalizaing word formats
단어들의 형태를 모두 일반화하기
3. Segmenting sentences in running text.
텍스트에서 문장들을 모두 구분화하기
Unix tools for crude tokenization and normalization - 생략
Word Tokenization and Normalization
단어들로부터 텍스트를 구분하는 임무인 tokenization과, 단어/토큰들을 기준있는 형태로 맞추기 위한 임무인 normalization을 위해서는 보다 엄격하고 복잡한 알고리즘이 필요하다.
예를 들어서 apostrophes로 표현되는 what're, we're와 같은 토큰들을 what are, we are등으로 확장시켜주는 알고리즘이 필요한데, 그렇기 때문에 tokenizer는 이러한 축소적 표현을 확장하는 데 사용될 수 있어야한다.
또한 tokenization 알고리즘은 New York이나 rock 'n' roll과 같이 white space로 구분되는 단어들을 하나로 묶어주는 능력이 필요하며 그렇기 때문에 Tokenization은 name, data, organization을 검사하는 능력인 named entity detection을 필요로 한다.
tokenization 표준 중 하나는 Penn Treebank Tokenization이 있으며, 만약 문장이 input으로 들어갈 경우 아래 그림과 같은 문장들이 tokenization이 된다.
이렇게 분류된 token들은 normalized될 수 있는데, 예를 들어 다양한 형태를 가지고 있는 단어인 USA나 US와 같은 단어들은 하나의 같은 정규화된 형태를 가지게 된다. 이러한 정규화과정은 매우 가치있으며 정보 검색에 있어서 US query를 입력해도, USA query가 나오게 되는 것이다.
이중에 case folding이라는 것은 단어가 대문자든 소문자등 그 형태를 맞추는 것을 의미하며 이 역시 정보 검색에 있어서 중요한 역할을 한다.
Word Segmentation in Chinese: the MaxMatch algorithm - 생략
Lemmatization and Stemming
Lemmatization은 두 단어가 다른 형태를 띠고 있음에도 같은 root word를 갖고 있는지에 대해 판단하는 것이다. 예를 들어 단어 am, is 그리고 are는 공통된 lemma인 be를 가지고 있다. 단어 dinners와 dinner는 같은 공통된 lemma인 dinner를 가지고 있다. 그것의 lemma로 단어를 대표하는 것은 웹 검색에 있어서 중요한 역할을 가지고 있다.
그렇다면 lemmatization은 어떻게 실행될 수 있는가? lemmatization 중 가장 복잡한 방법은 단어의 morphological parsing (형태학적 분석)을 완료하는 것이다. Morphology는 morphme이라 불리는 보다 작은 단어를 생산하는 unit으로부터 단어들을 건설해나가는 형태학적 학문이다. morpheme의 두 가지 class는 다음과 같이 구분된다: stems - 단어의 중심 morpheme으로써 단어의 중요 의미를 전달함. affixes - 다양한 형태로써 추가적 의미를 더해주는 역할.
예를 들어 단어 "cats"를 살펴보자. 단어 cat은 여기서 stems로써 단어 고양이 그 자체의 의미를 전달하지만, s는 복수형이라는 의미를 더해주는 affixes 역할을 하게되는 것이다.
The Porter Stemmer
유한 상태 변환기를 사용하여 완전한 형태소 분석기를 구축하는 것은 단어 형식의 형태학적 변형을 다루는 가장 일반적인 방법이지만, 때로는 우리는 간단하지만 더 까다로운 접미어를 사용하는 경우가 있다. 형태소 분석의 naive한 버전은 stemming이라 불리며, stemming algorithm으로 가장 널리 사용되는 것은 간단하고 효과적인 Porter algorithm이다. 다음과 같은 예시문을 보자.
This was not the map we found in Billy Bones's chest, but an accurate copy, complete in all things-names and heights and soundings-with the single exception of the red crosses and the written notes.
이러한 예시문은 나음과 같은 stemmed output을 갖는다:
Thi wa not the map we found in Billi Bone s chest but an accur copi complet in all thing name and height and sound with the singl except of the red cross and the written note
이 알고리즘은 cascade로써 이미 쓰여진 규칙에 기반하여 작동하여 input으로부터 output을 내놓는다.
다음 예시는 이러한 규칙의 한 예시이다:
ATIONAL -> ATE (e.g., relational -> relate)
ING -> $ \epsilon $ if stem contains vowel
SSES -> SS (e.g., grasses -> grass)
Porter stemmer의 더 자세한 규칙들은 Martin Porter의 홈페이지에서 찾을 수 있다.
하지만 이러한 형태의 규칙들은 단어들을 과일반화시키거나 덜 일반화시키는 경우가 있는데, 그러한 경우는 다음과 같은 표에서 확인할 수 있다.
Sentence Segmentation
문장 구분은 텍스트 처리 작업에서 또 다른 중요한 단계이다. text를 문장으로 나누는 가장 유용한 것은 마침표와 같은 문장 기호를 사용하는 것이다.
일반적으로 문장 tokenization 방법은 binary classfier를 사용하여 마침표가 단어의 일부분인지 문장의 구분 마커인지 확인하는 것으로 결정한다.
Minimum Edit Distance
자연어 처리의 대부분은 두 문자열이 얼마나 유사한가를 측정하는데에 연관이 있다. 예를 들어 철자 보정에서 사용자는 잘못된 문자열을 입력했다고 하자. (graffe라고 하자.) 사용자가 의미하는 바를 원하고, 유저는 아마 graffe와 유사한 단어 중 하나를 의도하여 입력했을 것이다. 유사한 단어들 중 후보군 사이에는 graffe에서 오직 한 문자가 다른 giraffe가 있을 것이고, giraffe는 grail이나 graf보단 graffe와 유사해 보인다.
또 다른 예시로는 coreference가 있다. coreference는 두 가지의 문자열이 같은 enity를 참조하고 있는지를 결정하는 역할을 하는 것이다:
Stanford President John Hennessy
Stanford University President John Hennessy
이 두 문장은 오직 한 단어에만 차이가 있지만 사실은 같은 사람을 참조해야한다.
Edit distance는 우리에게 문자열의 유사성을 알려주는 하나의 척도이다. 일반적으로 두 문자열 사이의 minimum edit distance는 하나의 문자열에서 다른 문자열로 변환되기 위한 필요한 operation 최소 갯수를 의미한다.
다음과 같은 그림을 보면 이해가 더 쉽게 갈 것이다.
INTENTION이라는 단어 EXECUTION이라는 단어로 변환되기 위해서는 1개의 Deletion, 1개의 Insertion, 그리고 3개의 Substitution이 필요하다. Substitution은 변환시키려는 문자열을 지우고 그리고 입력해야하므로 총 2개의 operation으로 취급한다.
즉 총 8개의 operation이 필요하므로 여기서 Levenshtein distance는 8이 되는 것이다.
The Minimum Edit Distance Algorithm
우리가 흔히 생각했을 때, minimum edit distance를 우리가 구하라고 하면 다음과 같은 식을 생각해볼 수 있다.
For string A and B, Let n(A) and n(B) be the number of characters in string and Let c(A,B) be the number of common characters between string A and string B.
Then, $(Minimum Edit Distance) = (d-constant) * (|n(A) - n(B)|) + (min(n(A),n(B)) - c(A,B)) * (s-constant)$
그렇다면 공통된 문자열을 찾는 것은 알고리즘으로 어떻게 구분하는가? 그저 CYK 알고리즘을 사용하면 구할 수 있다.
아래 그림은 Min-Edit_Distance에 관한 알고리즘을 풀어놓은 것이다.
Backtrace를 하는 작업도 우리가 대학 시절에 배웠던 문자열 비교 후 Backtrace와 완전히 똑같다!
다음 장은
JM4인 Language Modeling with N gram을 커버해보려 한다.
댓글
댓글 쓰기