어간 추출

어간 추출은 모양만 다른 낱말들을 한 꼴로 모아 줍니다. 낱말 하나를 넣으면 끝에 붙은 꼬리를 떼고 앞부분만 돌려줍니다. 검색에서 「connect」로 찾아도 「connected」가 든 문서가 걸리게 하는 것이 이 일입니다.

상세

이 절은 어간 추출이 무엇을 넣고 무엇을 돌려주는지부터 봅니다. 그다음 검색에서 왜 이 일이 필요한지를 영어 낱말 몇 개로 따라갑니다. 끝으로 같은 문제를 푸는 표제어 추출과 무엇이 다른지 가릅니다.

어간과 꼬리

어간은 국어 문법에서 온 말입니다. 「달리다」「달리고」「달리니」에서 모양이 바뀌어도 늘 남는 앞부분 「달리」가 어간입니다. 뒤에 붙어 바뀌는 「-다」「-고」「-니」는 어미라고 부릅니다.

영어에도 같은 짜임이 있습니다. 「connected」의 「-ed」, 「connecting」의 「-ing」처럼 낱말 끝에 붙어 모양을 바꾸는 부분은 접미사(suffix)라고 부릅니다. 이 문서는 어간 뒤에 붙는 이런 부분을 묶어 꼬리라고 부릅니다. 한국어의 어미도, 영어의 접미사도 꼬리입니다.

어간 추출은 낱말 하나를 받아 꼬리를 떼고 남은 어간을 돌려주는 절차입니다. 영어 stemming 을 옮긴 말입니다. stem 이 어간입니다. 꼬리를 떼는 일이라 접미사 떼기(suffix stripping)라고도 부릅니다. 「connected」「connecting」「connection」「connections」는 꼬리를 떼면 모두 「connect」 하나가 됩니다.

모양이 달라서 못 만나는 낱말

문서는 문법 때문에 같은 낱말을 여러 모양으로 씁니다. 「organize」「organizes」「organizing」은 한 낱말이 문법에 따라 바뀐 모양입니다. 「democracy」「democratic」「democratization」처럼 한 낱말에서 갈려 나와 뜻이 비슷한 무리도 있습니다.

검색 엔진은 문서를 넣을 때 글을 낱말로 쪼갭니다. 이 일을 토큰화라고 합니다. 쪼갠 낱말 하나하나를 토큰이라고 부릅니다.

검색 엔진은 쪼갠 낱말마다 그 낱말이 든 문서 목록을 적어 둡니다. 이 목록 묶음이 역색인입니다. 「connect」 줄에는 「connect」가 든 문서들이 적힙니다.

역색인은 글자가 똑같은 낱말만 같은 줄로 봅니다. 「connected」와 「connect」는 다른 줄에 적힙니다. 「connect」로 찾으면 「connected」만 든 문서는 안 나옵니다.

어간 추출은 이 틈을 메웁니다. 어간이 같은 낱말은 대개 뜻이 비슷합니다. 이런 무리를 한 낱말로 모으면 검색 성능이 나아지는 일이 잦습니다. 서로 다른 낱말 수가 줄어 색인도 작아집니다.

검색 엔진은 쪼갠 낱말을 역색인에 적기 전에 몇 가지로 손질합니다. 대문자를 소문자로 바꾸는 일이 하나입니다. 「the」「a」처럼 너무 흔해서 찾는 데 도움이 안 되는 낱말을 빼는 일도 있습니다. 이런 낱말을 불용어라고 부릅니다.

이 손질을 차례로 묶은 처리 과정을 분석기라고 부릅니다. 어간 추출은 분석기 안의 한 단계입니다.

넣을 때와 찾을 때 같은 규칙

어간 추출은 역색인에 적기 전에 한 번 돕니다. 검색어를 받은 뒤에도 한 번 돕니다. 두 번 모두 같은 규칙을 써야 양쪽 낱말이 같은 어간으로 줄어 역색인의 한 줄에서 만납니다.

flowchart TD
    subgraph 넣을 때
        D["문서의 낱말 · connected"] --> S1["어간 추출"]
    end
    subgraph 찾을 때
        Q["검색어 · connecting"] --> S2["어간 추출"]
    end
    S1 --> K["역색인의 한 줄 · connect"]
    S2 --> K

문서에는 「connected」가 있고 사용자는 「connecting」을 쳤습니다. 원래 모양으로는 만나지 못합니다. 둘 다 「connect」로 줄었기 때문에 같은 줄을 가리킵니다.

꼬리를 떼는 규칙

어간 추출은 대개 낱말 사전을 쓰지 않습니다. 꼬리 목록을 하나 들고 낱말 끝 글자만 맞춰 봅니다. 목록의 꼬리마다 그것을 떼어도 되는 조건이 붙어 있습니다.

조건이 있는 까닭은 꼬리처럼 보이는 글자가 어간의 일부일 때가 있어서입니다. 「replacement」에서 「-ement」를 떼면 「replac」가 남습니다. 「cement」에서 같은 꼬리를 떼면 「c」만 남습니다. 이런 실수를 막으려고 조건은 대개 떼고 남을 앞부분의 길이를 봅니다. 조건의 내용은 절차마다, 꼬리마다 다릅니다.

규칙은 꼬리를 떼기만 하지 않습니다. 긴 꼬리를 짧은 꼬리로 바꾸기도 합니다. 「caresses」의 「-sses」를 「-ss」로 바꿔 「caress」를 남기는 식입니다.

flowchart TD
    A["낱말"] --> B{"끝이 목록의 꼬리와 맞나"}
    B -- "안 맞음" --> N["손대지 않고 넘긴다"]
    B -- "맞음" --> C{"떼고 남을 앞부분이 조건을 채우나"}
    C -- "못 채움" --> N
    C -- "채움" --> D["꼬리를 떼거나 짧은 꼬리로 바꾼다"]

이 판정을 몇 번 하느냐는 절차마다 다릅니다. 1968년의 러빈스 알고리즘은 꼬리를 한 번만 뗍니다. 1980년의 포터 알고리즘은 다섯 단계를 차례로 지나며 꼬리를 조금씩 뗍니다.

꼬리 목록의 길이와 조건의 세기도 절차마다 다릅니다. 그 차이는 아래 「갈래」 절이 하나씩 짚습니다.

사전에 없는 어간

꼬리를 떼고 남은 어간은 영어 낱말이 아닐 때가 있습니다. 「replacement」는 「replac」가 되고 「generalizations」는 「gener」가 됩니다. 그래도 어간 추출로서는 제 일을 한 것입니다.

목적이 올바른 낱말을 만드는 데 있지 않기 때문입니다. 꼬리는 검색 성능을 올리려고 뗍니다. 어간이 어떤 글자인지는 상관없습니다. 어느 낱말들이 한 무리로 모이는지만 중요합니다.

사전에 실린 기본형이 필요하면 아래의 표제어 추출이 그 일을 합니다.

표제어 추출과의 차이

표제어 추출도 여러 모양의 낱말을 하나로 모읍니다. 다른 점은 낱말 사전과 형태소 분석을 써서 사전에 실린 기본형을 돌려준다는 것입니다. 이 기본형을 표제어(lemma)라고 부릅니다.

형태소 분석은 낱말을 뜻을 가진 가장 작은 단위로 나누는 일입니다. 「달리고」를 어간 「달리」와 어미 「고」로 가르는 것이 그 예입니다. 끝 글자를 맞춰 보는 대신 사전을 보고 가릅니다.

같은 「saw」를 넣어도 둘의 답이 갈립니다. 표제어 추출은 문장에서 동사로 쓰였으면 「see」를, 명사로 쓰였으면 「saw」를 돌려주려 합니다. 어간 추출은 낱말이 동사인지 명사인지 보지 않습니다. 끝을 잘라 「s」 한 글자만 돌려주는 일까지 일어날 수 있습니다.

한 글자만 남는 것은 위 「꼬리를 떼는 규칙」의 길이 조건이 막으려는 결과입니다. 그 조건은 모든 꼬리에 붙어 있지 않습니다. 러빈스 알고리즘의 「-ionally」에는 길이 조건이 없습니다. 포터 알고리즘 첫 단계의 「-s」 규칙 묶음도 조건이 없습니다. 길이를 안 보는 꼬리에 걸리면 앞부분이 한 글자만 남아도 그대로 뗍니다.

어간 추출은 준비물이 적은 대신 결과가 거칩니다. 끝을 잘라 내는 어림 절차라서 대부분 맞기를 바라는 방식입니다.

복잡도

어간 추출은 낱말 하나를 낱말 길이에 비례하는 시간에 끝냅니다. 규칙표는 크기가 고정이라 입력이 늘어도 공간이 안 늘어납니다. 색인 전체로 보면 문서에 든 낱말 수에 비례하는 일을 한 번 더 하는 셈입니다.

아래 표에서 L 은 낱말 하나의 글자 수, T 는 색인할 글 전체의 낱말 수, Q 는 검색어의 낱말 수입니다. 세는 것은 글자를 맞춰 보는 횟수입니다. 이 차수는 단계 수가 정해져 있다는 데서 나옵니다.

최악과 평균

단계 수가 정해진 절차는 최악과 평균이 같은 차수입니다. 어떤 낱말이 와도 단계를 정해진 횟수만 지나기 때문입니다. 차이는 각 단계에서 맞는 꼬리를 찾을 때까지 목록을 얼마나 훑느냐뿐입니다.

꼬리를 하나 뗄 때마다 처음으로 돌아가는 반복형 절차는 단계 수가 정해져 있지 않습니다. 뗄 꼬리가 여러 겹 붙은 긴 낱말일수록 되풀이가 늘어납니다. 되풀이 횟수의 상한은 자료에 없습니다(미확인). 위 표의 값은 단계 수가 정해진 절차의 것입니다. 아래 「갈래」의 랭커스터 알고리즘이 이렇게 되풀이합니다.

꼬리 목록 크기와 단계 수의 맞바꿈

꼬리를 여러 단계로 나누어 조금씩 떼면 목록이 짧습니다. 대신 단계를 여러 번 지나야 합니다. 거꾸로 가능한 꼬리 조합을 전부 목록에 적어 두면 한 번에 가장 긴 꼬리를 찾아 끝낼 수 있습니다.

러빈스 알고리즘이 뒤쪽입니다. 꼬리를 260개 남짓 들고 있어 포터 알고리즘보다 덩치가 큽니다. 대신 더 빠릅니다.

러빈스 알고리즘은 꼬리 하나를 떼는 데 큰 단계 둘이면 끝납니다. 가장 긴 꼬리를 떼는 단계와 남은 끝을 다듬는 단계입니다. 포터 알고리즘은 같은 일에 여덟 단계를 거칩니다. 다섯 단계 가운데 일부가 다시 잘게 나뉘어 있기 때문입니다.

사전 확인형 절차의 메모리

크로베츠 스테머처럼 사전으로 떼기를 확인하는 절차는 낱말 사전 전체를 메모리에 올려야 합니다. 공간이 규칙표가 아니라 사전 크기를 따라갑니다. 떼기마다 사전을 찾아보는 시간도 더 듭니다.

줄어드는 색인 크기

어간 추출은 시간을 쓰는 대신 색인의 낱말 수를 줄입니다. 포터 알고리즘으로 낱말 10,000개를 줄이자 서로 다른 어간이 6,370개 남았습니다. 낱말 목록이 3분의 1쯤 줄어든 것입니다.

예시

어간 추출은 검색 기능을 가진 제품 안에 분석기의 한 단계로 박혀 있습니다. 아래는 관계형 데이터베이스 하나와 검색 엔진 하나가 어간 추출을 어떻게 넣어 두었는지 출력으로 봅니다. 끝으로 끝 글자를 자르지 않고 같은 일을 하는 한국어 분석기 하나를 봅니다.

PostgreSQL 전문 검색

전문 검색(full-text search)은 글 본문을 낱말 단위로 찾는 기능입니다. PostgreSQL 은 전문 검색에서 낱말을 손질하는 부품을 사전이라고 부릅니다. 낱말 하나를 사전 여러 개에 차례로 거치게 할 수 있습니다. 이 차례를 사전 목록이라고 부릅니다.

어간 추출을 맡는 것은 Snowball 사전입니다. Snowball 은 포터가 시작한 어간 추출 프로젝트입니다. 여러 언어의 절차를 냅니다. 영어용으로 english_stem 이 미리 정의돼 있습니다.

CREATE TEXT SEARCH DICTIONARY english_stem (
    TEMPLATE = snowball,
    Language = english,
    StopWords = english
);

Language = english 가 어느 언어의 어간 추출 규칙을 쓸지 정합니다. StopWords = english 는 버릴 불용어 목록입니다.

글 한 줄을 넣어 보면 이 사전이 무엇을 남기는지 보입니다.

SELECT to_tsvector('english', 'a fat  cat sat on a mat - it ate a fat rats');
-- 'ate':9 'cat':3 'fat':2,11 'mat':7 'rat':12 'sat':4

to_tsvector 는 글을 낱말과 그 낱말이 나온 위치의 목록으로 바꿉니다. 「a」「on」「it」은 불용어라 빠졌습니다. 「rats」는 복수형이라 「rat」이 됐습니다. 사전 하나만 따로 시험할 수도 있습니다. ts_lexize('english_stem', 'stars') 는 {star} 를 돌려줍니다.

지명 같은 고유 명사도 꼬리 규칙을 탑니다. ts_debug 로 「Paris」 한 낱말을 넣어 보면 어느 사전을 거쳐 무엇이 나왔는지 보입니다.

SELECT * FROM ts_debug('english', 'Paris');
--  alias     | description     | token | dictionaries   | dictionary   | lexemes
-- -----------+-----------------+-------+----------------+--------------+---------
--  asciiword | Word, all ASCII | Paris | {english_stem} | english_stem | {pari}

dictionaries 칸이 이 낱말이 거칠 사전 목록입니다. dictionary 칸이 결과를 낸 사전입니다. lexemes 칸이 그 결과입니다. 목록에 english_stem 하나뿐이라 「Paris」가 「pari」로 줄었습니다.

Snowball 사전은 줄일 수 있든 없든 모든 낱말을 알아봅니다. 그래서 사전 목록의 맨 끝에 둡니다. 「Paris」를 지키려면 동의어 사전을 Snowball 사전 앞에 둡니다. 앞의 동의어 사전이 「Paris」를 먼저 알아보면 Snowball 사전까지 가지 않습니다.

flowchart TD
    W["낱말"] --> S{"앞에 둔 동의어 사전이 알아보나"}
    S -- "알아봄 · Paris" --> R1["동의어 사전의 결과로 끝난다 · pari 가 안 된다"]
    S -- "모름 · stars" --> E["맨 끝의 Snowball 사전 english_stem"]
    E --> R2["어간을 돌려준다 · star"]

Elasticsearch 분석기

Elasticsearch 는 어간 추출을 stemmer 토큰 필터로 넣습니다. 토큰 필터는 쪼갠 낱말을 하나씩 받아 손질하는 분석기 부품입니다. 따로 정하지 않으면 영어에는 포터 알고리즘을 씁니다.

GET /_analyze
{
  "tokenizer": "standard",
  "filter": [ "stemmer" ],
  "text": "the foxes jumping quickly"
}

이 요청은 [ the, fox, jump, quickli ] 를 돌려줍니다. 「quickli」는 사전에 없는 어간입니다.

미리 만들어 둔 english 분석기를 필터 정의와 차례로 풀어 쓰면 아래와 같습니다.

"filter": {
  "english_stop":     { "type": "stop", "stopwords": "_english_" },
  "english_keywords": { "type": "keyword_marker", "keywords": ["example"] },
  "english_stemmer":  { "type": "stemmer", "language": "english" },
  "english_possessive_stemmer": { "type": "stemmer", "language": "possessive_english" }
},
"analyzer": {
  "rebuilt_english": {
    "tokenizer": "standard",
    "filter": [
      "english_possessive_stemmer",
      "lowercase",
      "english_stop",
      "english_keywords",
      "english_stemmer"
    ]
  }
}

filter 아래에 부품 넷을 정의합니다. analyzer 가 그 부품을 차례로 늘어놓습니다. 맨 앞에서 소유격 꼬리를 뗍니다. 이어서 소문자로 바꾸고 불용어를 뺍니다. 어간 추출은 맨 끝입니다.

english_keywords 는 keyword_marker 필터입니다. keywords 에 적은 낱말(이 설정에서는 example)에 표시를 붙입니다. 표시가 붙은 낱말은 뒤의 어간 추출을 건너뜁니다.

어간 추출 절차는 stemmer 필터의 language 값으로 고릅니다. 영어에는 english(권장) · light_english · minimal_english · porter2 · possessive_english · lovins 가 있습니다. lovins 는 8.16.0 에서 폐기 예정이 됐습니다.

색인할 때와 검색할 때는 대개 같은 분석기를 씁니다. The QUICK brown foxes jumped over the dog! 를 색인하면 [ quick, brown, fox, jump, over, dog ] 가 남습니다. 검색어에 「Quick」과 「foxes」가 오면 같은 분석기가 [ quick, fox ] 로 바꿔 서로 만나게 합니다.

Nori 한국어 분석기

Nori 는 Lucene 의 한국어 분석 모듈입니다. Lucene 은 Elasticsearch 가 안에서 쓰는 검색 라이브러리입니다. Nori 는 Elasticsearch 에 플러그인으로 붙습니다. 끝 글자를 자르지 않고 mecab-ko-dic 사전으로 형태소 분석을 합니다.

「뿌리가 깊은 나무는」을 nori_tokenizer 에 넣으면 아래처럼 갈립니다. 토크나이저는 토큰마다 품사 태그를 붙입니다.

「깊은」이 어간 「깊」과 어미 「은」으로 갈렸습니다. 「뿌리가」도 명사와 조사로 갈렸습니다. 영어 어간 추출은 꼬리를 떼어 어간을 남깁니다. Nori 는 사전을 보고 어간을 토큰 하나로 따로 떼어 냅니다.

nori 분석기는 이 토크나이저 뒤에 nori_part_of_speech 필터를 붙여 둡니다. 이 필터는 정해 둔 품사 태그에 걸리는 토큰을 뺍니다. 기본 목록에는 접두사 태그 XPN(prefix) 이 들어 있습니다. 이 때문에 「비급여」는 「급여」로 분석됩니다. 위 표의 조사·어미 태그 JKS·ETM·JX 는 기본 목록에 없습니다.

갈래

어간 추출 절차는 두 축으로 갈립니다. 하나는 꼬리를 얼마나 세게 떼는가입니다. 다른 하나는 뗀 결과를 낱말 사전으로 확인하는가입니다.

S 스테머

단수형과 복수형만 모으는 어간 추출입니다. 가장 가볍게 떼는 쪽에 널리 쓰입니다. 알려진 한 판의 규칙은 셋입니다. 「-ies」는 「-y」로 바꿉니다. 「-es」는 「-e」로 바꿉니다. 「-s」는 뗍니다.

규칙마다 예외 꼬리가 붙어 있습니다. 「-s」 규칙은 「-us」「-ss」로 끝나는 낱말을 건드리지 않습니다. 세 글자 이상인 낱말에만 씁니다. 처음 맞는 규칙 하나만 적용합니다. Elasticsearch 에서는 minimal_english 가 이 계열에 듭니다.

러빈스 알고리즘

1968년에 줄리 베스 러빈스가 낸, 처음으로 발표된 어간 추출 알고리즘입니다. 꼬리를 260개 남짓 한 목록에 길이 순으로 적어 둡니다. 그중 조건을 채우는 가장 긴 꼬리 하나를 한 번에 뗍니다. 조건은 29가지입니다. 「남는 어간이 세 글자 이상」 같은 것입니다.

flowchart TD
    A["nationally"] --> B{"가장 긴 꼬리 -ationally · 남는 어간이 세 글자 이상인가"}
    B -- "못 채움 · 한 글자만 남는다" --> C{"다음으로 긴 꼬리 -ionally · 길이 조건 없음"}
    C -- "채움" --> D["-ionally 를 떼고 nat 이 남는다"]
    D --> E["둘째 단계 · 변환 규칙 35개로 끝을 다듬는다"]

「nationally」에서 가장 긴 꼬리 「-ationally」를 떼면 한 글자만 남아 조건에 걸립니다. 다음으로 긴 「-ionally」는 길이 조건이 없어 떼어집니다. 「nat」이 남습니다. 둘째 단계에서는 변환 규칙 35개가 끝을 다듬습니다. 이 단계는 꼬리를 뗐든 안 뗐든 언제나 돕니다. 「sitting」은 「sitt」가 됐다가 겹친 글자를 줄여 「sit」이 됩니다.

포터 알고리즘

1980년에 마틴 포터가 낸 알고리즘입니다. 영어 어간 추출에서 가장 널리 쓰입니다. 다섯 단계를 차례로 지나며 꼬리를 조금씩 뗍니다.

flowchart TD
    A["generalizations"] -- "1단계 · 복수형" --> B["generalization"]
    B -- "2단계" --> C["generalize"]
    C -- "3단계" --> D["general"]
    D -- "4단계" --> E["gener"]

한 단계 안에서 규칙을 고르는 관례는 여럿입니다. 그 하나가 규칙 묶음마다 규칙을 하나만 따르는 것입니다. 위아래로 나란히 적은 규칙이 한 묶음입니다. 그 안에서 맞는 규칙 가운데 꼬리가 가장 긴 것을 따릅니다. 「-sses → -ss」와 「-s → 뗀다」가 한 묶음이라, 「caresses」는 더 긴 「-sses」를 따라 「caress」가 됩니다.

규칙의 조건은 대개 measure 라는 값으로 적습니다. 남는 앞부분에 음절이 몇 개쯤 있는지를 어림한 수입니다. 기호로는 m 이라고 씁니다. (m > 1) EMENT -> 규칙은 measure 가 1보다 클 때만 「-ement」를 뗍니다. 「replacement」는 「replac」가 되지만 「cement」는 「c」가 되지 않습니다.

Porter2 와 Snowball

포터 알고리즘을 20년 쓰고 나서 포터가 다듬은 영어판이 Porter2 입니다. Snowball 프로젝트가 내는 영어 절차가 이것입니다. 원판과 달라진 점은 아래와 같습니다.

• 두 글자짜리 낱말은 건드리지 않습니다. 「as」「is」가 「s」를 잃지 않습니다
• 「-us」로 끝나면 「s」를 안 뗍니다
• 「-ly」 같은 꼬리를 몇 개 더 뗍니다
• 예외 낱말 목록을 따로 둡니다

표본 어휘에서 원판과 다른 어간이 나오는 낱말은 5% 남짓입니다.

랭커스터 알고리즘

1990년에 크리스 페이스가 개러스 허스크의 도움을 받아 낸 반복형 알고리즘입니다. 페이스/허스크 알고리즘이라고도 부릅니다. 규칙표 하나를 낱말의 마지막 글자로 찾아봅니다. 규칙을 적용한 뒤 계속하라는 표시가 있으면 처음으로 돌아갑니다.

flowchart TD
    A["낱말의 마지막 글자로 규칙표의 구역을 찾는다"] --> B{"규칙을 쓸 수 있나 · 끝 글자와 조건"}
    B -- "못 씀" --> C{"다음 규칙이 같은 구역인가"}
    C -- "같은 구역" --> B
    C -- "구역이 바뀜" --> E["끝낸다"]
    B -- "씀" --> D["꼬리를 떼거나 다른 글자로 바꾼다"]
    D --> F{"계속하라는 표시가 있나"}
    F -- "있음" --> A
    F -- "없음" --> E

규칙은 꼬리를 떼기만 하지 않고 다른 글자로 바꾸기도 합니다. 「provision」은 「provij」를 거쳐 「provid」가 됩니다. 매우 세고 거칠게 떼는 알고리즘으로 알려져 있습니다.

크로베츠 스테머

1993년에 로버트 크로베츠가 낸 약한 어간 추출입니다. 복수형을 단수형으로 바꿉니다. 과거형은 현재형으로 바꿉니다. 「-ing」는 뗍니다. 뗄 때마다 낱말 사전을 찾아 결과가 진짜 낱말인지 확인합니다.

결과가 뜻을 알 수 있는 낱말이라 정확도가 높습니다. 대신 모으는 힘이 약합니다. 크로베츠는 이것을 주된 어간 추출 앞에 거치는 전처리로 쓸 수 있다고 제안했습니다. Elasticsearch 에서는 light_english 가 이 절차에 해당합니다.

한국어 형태소 분석

한국어는 끝 글자를 잘라 내는 방식이 잘 안 맞습니다. 「달려서」는 어간 「달리」와 어미 「-어서」가 합쳐지며 글자가 줄어든 모양입니다. 끝 글자를 잘라서는 「달리」가 안 나옵니다.

한국어는 형태소 분석으로 이 일을 합니다. 사전을 보고 낱말을 뜻을 가진 가장 작은 단위로 나눕니다. 용언은 어간과 어미로, 명사 뒤의 조사는 따로 갈립니다. 위 「예시」에서 본 Nori 가 이렇게 가릅니다.

대가

어간 추출은 빠뜨리는 문서를 줄이는 대신 엉뚱한 문서를 늘립니다. 꼬리를 세게 뗄수록 이 맞바꿈이 커집니다. 영어에서는 평균으로 따지면 얻는 것이 거의 없다는 결과도 있습니다.

재현율과 정밀도

검색 결과를 재는 잣대가 둘 있습니다. 첫째는 재현율입니다. 찾아야 할 문서 가운데 찾아낸 문서의 몫입니다. 「connect」로 찾을 때 「connected」만 든 문서를 놓치면 재현율이 깎입니다.

둘째는 정밀도입니다. 찾아낸 문서 가운데 맞는 문서의 몫입니다. 「operating system」을 찾았는데 「operational research」 문서가 섞여 나오면 정밀도가 깎입니다.

어간 추출은 재현율을 올리고 정밀도를 깎습니다. 모양이 다른 낱말이 만나니 빠뜨리는 문서가 줄어듭니다. 대신 만나지 말아야 할 낱말도 만납니다.

과잉 추출

과잉 추출(over-stemming)은 모으지 말아야 할 낱말을 한 어간으로 모으는 실수입니다. 어간 하나가 여러 뜻을 지게 되어 정밀도가 깎입니다.

포터 알고리즘은 아래 일곱 낱말을 전부 「oper」로 줄입니다.

flowchart TD
    A["operate · operating · operates"] --> O["oper"]
    B["operation · operational"] --> O
    C["operative · operatives"] --> O

「operating system」(운영체제)을 찾는 사람에게 「operational research」(운용 연구)나 「operative dentistry」(보존 치과학) 문서가 섞여 나올 수 있습니다. 「operate」는 여러 모양으로 자주 쓰는 동사입니다. 이런 검색어에서는 정밀도를 꽤 잃을 것으로 봅니다.

포터 알고리즘은 「university」와 「universe」도 같은 꼴로 줄입니다. Snowball 3.0.0 판의 Porter2 는 이것을 고쳤습니다. 「universe」를 「universal」과도, 「university」와도 한 어간으로 모으지 않습니다.

꼬리처럼 보이는 글자가 어간의 일부일 때도 과잉 추출이 납니다. 「sand」와 「sander」를 모으는 규칙은 「wand」와 「wander」도 모을 가능성이 큽니다. 「wander」의 「-er」은 꼬리가 아니라 어간입니다.

과소 추출

과소 추출(under-stemming)은 모아야 할 낱말을 못 모으는 실수입니다. 한 개념이 여러 어간으로 흩어져 재현율이 깎입니다.

끝 글자만 보는 절차는 꼬리가 아니라 앞부분이 바뀌는 낱말을 잘 못 모읍니다. 「mouse」와 「mice」, 「foot」와 「feet」, 「be」「are」「am」은 끝이 아니라 앞부분이 바뀝니다. 「deceive」와 「deception」처럼 꼬리가 붙으며 어간이 바뀌는 낱말도 있습니다. 포터는 이런 낱말이 실제 어휘에서 생각보다 드물다고 보고 따로 다루지 않았습니다.

두 실수의 맞바꿈

두 실수는 한쪽을 줄이면 다른 쪽이 늡니다. 꼬리를 세게 뗄수록 과소 추출은 줄어듭니다. 대신 과잉 추출이 늡니다. 어느 지점을 넘으면 재현율이 조금 오르는 대가로 정밀도를 크게 잃습니다.

규칙을 더해도 이 맞바꿈을 못 벗어납니다. 어휘의 한 구역에서 성능을 올리려고 규칙을 넣으면 다른 구역에서 그만큼 떨어지는 단계가 옵니다. 규칙 기반 어간 추출은 어떻게 재도 성공률이 100%에 한참 못 미칩니다.

영어 검색에서의 작은 평균 효과

영어 검색에서는 어간 추출이 평균 성능을 별로 올리지 못하는 경향이 있습니다. 어떤 검색어에는 크게 도움이 됩니다. 다른 검색어에는 그만큼 해가 됩니다. 표제어 추출로 바꿔도 얻는 것은 많아야 아주 조금입니다.

약하게 떼는 쪽을 권하는 연구도 있습니다. 온라인 도서 목록 검색을 연구한 Okapi 프로젝트는 복수형·「-ed」·「-ing」만 떼는 약한 어간 추출을 늘 쓰라고 권했습니다. 권한 까닭은 둘입니다. 약한 쪽은 성능을 해치는 일이 드물었습니다. 포터 알고리즘을 바꾼 센 쪽은 몇몇 검색어에서 정밀도가 떨어졌습니다. 센 어간 추출은 아무 결과도 안 나올 때만 쓰라고 했습니다.

낱말 모양이 훨씬 많이 바뀌는 언어는 사정이 다릅니다. 스페인어·독일어·핀란드어에서는 어간 추출로 검색 성능이 크게 오른 결과가 거듭 나왔습니다.

규칙 변경 뒤의 재색인

역색인에는 꼬리를 뗀 뒤의 어간이 적혀 있습니다. 어간 추출 규칙을 바꾸면 검색어는 새 규칙으로, 이미 넣은 문서는 옛 규칙으로 줄어 서로 어긋납니다. 이미 넣은 문서를 전부 새 규칙으로 다시 넣어야 맞습니다.

Elasticsearch 의 데이터 스트림이 이 어긋남을 보여 줍니다. 데이터 스트림은 뒤에서 여러 색인이 받치는 묶음입니다. 새 데이터는 그중 쓰기 색인에 들어갑니다. 분석기를 바꾸고 쓰기 색인을 새로 갈면 그 뒤에 들어온 데이터만 새 분석기를 탑니다.

이미 든 데이터는 옛 분석기로 만든 어간을 그대로 지닙니다. 이것까지 바꾸려면 새 데이터 스트림을 만들어 다시 색인해야 합니다.

떼면 안 되는 낱말을 빼 두는 비용

지명처럼 꼬리 같은 글자로 끝나는 고유 명사는 꼬리 규칙을 타면 망가집니다. 「Paris」가 「pari」가 되는 식입니다. 이런 낱말은 어간 추출에서 빼 두는 목록을 따로 관리해야 합니다.

Elasticsearch 는 keyword_marker 필터와 stem_exclusion 설정으로, PostgreSQL 은 앞에 두는 동의어 사전으로 이 목록을 받습니다. 사용자가 검색어의 낱말 하나를 어간 추출에서 빼고 다시 찾게 해 주자는 제안도 있습니다.

관련 항목

어간 추출이 한 단계로 들어가는 처리 과정

분석기 · 토큰화 · 토크나이저 · 토큰 필터 · 소문자 변환 · 불용어 · 유니코드 정규화 · 동의어 사전

어간 추출과 같은 일을 다른 방법으로 하는 기법

표제어 추출 · 형태소 분석 · n-gram · 퍼지 검색 · 복합어 분해

어간 추출이 기대는 문법 용어

어간 · 어미 · 접미사 · 형태소 · 품사 · 굴절 · 파생어 · 조사

어간 추출의 하위 종류인 알고리즘

S 스테머 · 러빈스 알고리즘 · 포터 알고리즘 · Porter2 · 스노볼 · 랭커스터 알고리즘 · 크로베츠 스테머

어간 추출을 넣어 둔 검색 제품

PostgreSQL · 전문 검색 · tsvector · Elasticsearch · Apache Lucene · Nori · mecab-ko-dic

어간 추출의 결과를 쓰는 검색 구조

역색인 · 포스팅 리스트 · 검색 엔진 · BM25 · TF-IDF · 재색인

어간 추출이 검색 품질에 남기는 실수와 지표

과잉 추출 · 과소 추출 · 재현율 · 정밀도