어간 추출

어간 추출은 모양만 다른 낱말들을 하나로 모아 줍니다. 낱말 끝에 붙은 꼬리를 떼어 공통된 앞부분만 남기는 방식입니다. 검색에서 「connect」로 찾아도 「connected」가 걸리게 하는 것이 이 일입니다.

쉽고 빠른 이해

무슨 일을 하나 — 낱말 끝에 붙은 꼬리를 떼어 앞부분만 남깁니다. 이 앞부분이 어간입니다. 「connected」「connecting」「connections」는 셋 다 「connect」가 됩니다.

왜 하나 — 검색 엔진은 글자가 같은 낱말끼리만 맞춰 봅니다. 사용자가 「connect」로 찾았는데 문서에는 「connected」만 있으면 그 문서는 안 걸립니다. 어간으로 모아 두면 모양이 달라도 서로 만납니다.

어떻게 도나

1. 낱말 끝이 「-ing」「-ed」「-s」 같은 꼬리 목록에 있는지 봅니다
2. 있으면 뗍니다. 떼고 남을 앞부분이 너무 짧으면 떼지 않습니다
3. 문서를 넣을 때와 검색어를 받을 때 같은 규칙을 씁니다

대가 — 뜻이 다른 낱말까지 하나로 모일 수 있습니다. 「university」와 「universe」가 같은 어간으로 모이면, 대학을 찾는 사람에게 우주 이야기가 섞여 나옵니다. 그래서 글자 하나만 달라도 다른 것을 가리키는 값(상품 코드·사람 이름)에는 어간 추출을 끕니다.

상세

이 절은 어간 추출이 푸는 문제부터 봅니다. 그다음 영어 낱말 몇 개로 꼬리를 떼는 규칙과 그 규칙의 실수를 따라갑니다. 끝으로 표제어 추출·한국어와의 차이를 짚습니다.

어간이라는 말

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

어간 추출은 영어 stemming 을 옮긴 말입니다. stem 이 어간을 가리키는 영어 낱말입니다. 여러 모양의 낱말에서 어간을 찾아 남기는 일이라서 이 이름이 붙었습니다.

영어 낱말 끝에 붙어 모양을 바꾸는 「-ing」「-ed」「-s」 같은 부분은 앞으로 꼬리라고 부릅니다. 어간 추출은 이 꼬리를 떼어 어간만 남깁니다.

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

검색 엔진은 문서를 넣을 때 글을 낱말로 쪼개 둡니다. 이 일을 토큰화라고 합니다. 그리고 쪼갠 낱말마다 그 낱말이 든 문서 목록을 적어 둡니다. 이 목록 묶음이 역색인입니다.

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

사용자는 낱말을 어떤 모양으로 칠지 미리 정하지 않습니다. 같은 뜻을 찾으면서 문서와 다른 모양을 치는 일이 잦습니다. 어간 추출은 이 틈을 메웁니다.

검색 엔진은 글을 쪼개는 일부터 역색인에 적기 직전까지 낱말을 몇 가지로 손질합니다. 이 손질을 차례로 묶은 처리 과정을 분석기라고 부릅니다. 어간 추출은 분석기 안의 한 단계로 들어갑니다.

넣을 때와 찾을 때 같은 규칙

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

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

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

넣을 때와 찾을 때 규칙이 다르면 이 만남이 깨집니다. 한쪽은 「connect」로, 다른 쪽은 「connecting」으로 남으면 서로 못 찾습니다. 규칙을 바꾸면 이미 넣어 둔 문서도 새 규칙으로 다시 넣어야 합니다.

꼬리를 떼는 규칙

널리 쓰는 방식은 낱말 끝을 규칙 목록과 맞춰 보는 것입니다. 목록에는 「-ing」「-ed」「-ation」 같은 꼬리와, 떼어도 되는 조건이 적혀 있습니다. 사전을 쓰지 않고 글자 모양만 봅니다.

조건이 필요한 까닭은 너무 짧은 낱말을 보호하려는 것입니다. 「sing」에서 「-ing」를 떼면 「s」만 남습니다. 그래서 떼고 남은 앞부분이 일정 길이를 넘을 때만 뗍니다.

규칙 목록은 여러 단계로 나뉘어 차례로 돕니다. 단계마다 볼 꼬리가 따로 있습니다. 앞 단계가 복수형 꼬리를 떼면 다음 단계가 그 결과에서 또 다른 꼬리를 봅니다.

아래 그림은 한 단계 안에서 낱말 하나가 거치는 판정입니다. 꼬리를 떼든 안 떼든 낱말은 다음 단계로 넘어갑니다. 마지막 단계를 지나고 남은 것이 어간입니다.

flowchart TD
    A["앞 단계에서 넘어온 낱말"] --> B{"끝이 이 단계의 꼬리와 맞나"}
    B -- "안 맞음" --> N["다음 단계로 넘긴다"]
    B -- "맞음" --> C{"떼고 남은 앞부분이 충분히 긴가"}
    C -- "짧음" --> N
    C -- "길다" --> D["꼬리를 뗀다"]
    D --> N

영어에서 이런 방식으로 가장 널리 쓰이는 것이 포터 알고리즘입니다. 아래 표는 포터 알고리즘에 낱말을 넣었을 때 나오는 결과입니다. 왼쪽이 넣은 낱말, 오른쪽이 남은 어간입니다.

앞의 세 줄은 여러 모양이 한 어간으로 잘 모인 예입니다. 뒤의 두 줄은 어간이 사전에 없는 낱말이 된 예입니다. 이 차이는 바로 아래에서 봅니다.

사전에 없는 어간

「studi」나 「happi」는 영어 낱말이 아닙니다. 그래도 어간 추출로서는 제 일을 한 것입니다. 목적은 같은 어간의 낱말들을 한 줄에 모으는 것이지, 올바른 낱말을 만들어 내는 것이 아니기 때문입니다.

이 어간은 역색인 안에서만 쓰이고 사용자에게 보이지 않습니다. 「studies」와 「studying」이 둘 다 「studi」로 모이기만 하면 검색은 잘 됩니다. 결과를 화면에 보여 줘야 한다면 어간 추출이 아니라 아래의 표제어 추출이 맞습니다.

너무 많이 떼기와 너무 적게 떼기

규칙이 뜻을 모른 채 글자만 보므로 두 가지 실수를 합니다. 첫째는 뜻이 다른 낱말까지 한 어간으로 모으는 것입니다. 이를 과잉 추출(over-stemming)이라고 부릅니다.

포터 알고리즘에서는 「university」「universal」「universe」가 모두 「univers」가 됩니다. 대학과 우주가 한 줄에 섞입니다. 「대학」을 찾은 사람에게 우주 이야기가 딸려 나옵니다.

둘째는 같은 뜻인데 못 모으는 것입니다. 이를 과소 추출(under-stemming)이라고 부릅니다. 「run」과 「ran」은 같은 동사지만 꼬리가 아니라 가운데 글자가 바뀌어서 규칙으로는 못 모읍니다.

두 실수가 검색을 얼마나 망치는지는 잣대 둘로 잽니다. 첫째는 찾아야 할 문서 가운데 실제로 찾아낸 몫인 재현율입니다. 과소 추출이 재현율을 깎습니다. 「run」으로 찾은 사람은 「ran」만 든 문서를 못 봅니다.

둘째는 찾아낸 문서 가운데 맞는 문서의 몫인 정밀도입니다. 과잉 추출이 정밀도를 깎습니다. 「university」로 찾은 결과에 「universe」가 든 문서가 섞입니다.

꼬리를 많이 뗄수록 과소 추출은 줄고 과잉 추출은 늘어납니다. 재현율이 오르는 대신 정밀도가 내려갑니다. 그래서 어간 추출기마다 떼는 양이 다릅니다.

복수형 「-s」 정도만 떼는 어간 추출기가 있습니다. 꼬리를 여러 겹 떼는 어간 추출기도 있습니다.

표제어 추출과의 차이

표제어 추출도 여러 모양의 낱말을 하나로 모읍니다. 다른 점은 결과가 사전에 실린 기본형이라는 것입니다. 「ran」을 넣으면 「run」이, 「better」를 넣으면 「good」이 나옵니다.

기본형을 찾으려면 낱말 사전과 품사 정보가 필요합니다. 같은 「saw」라도 명사면 「톱」이고 동사면 「see」의 과거형입니다. 문장 안에서 품사를 먼저 가려야 합니다. 어간 추출은 이런 준비 없이 글자 모양만 봅니다.

어간 추출은 준비물이 적은 대신 결과가 거칩니다. 표제어 추출은 사전을 들고 있는 대신 기본형을 돌려줍니다. 검색처럼 한 줄에 모으기만 하면 되는 일에는 어간 추출을 많이 씁니다.

한국어의 어간 추출

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

한국어는 형태소 분석으로 이 일을 합니다. 형태소 분석은 사전을 보고 낱말을 뜻 있는 가장 작은 단위로 나눕니다. 「달려서」는 「달리」와 「어서」로 갈립니다. 여기서 어간만 남기면 어간 추출과 같은 결과가 됩니다.

명사에 붙는 조사도 같은 방식으로 뗍니다. 「한강을」「한강에서」는 둘 다 「한강」만 남습니다. 한국어 검색에서는 이 분석이 토큰화와 어간 추출을 한꺼번에 맡는 셈입니다.

드는 비용

규칙 기반 어간 추출은 낱말 하나에 규칙 목록을 몇 번 훑는 것으로 끝납니다. 걸리는 시간은 낱말 길이에 비례합니다. 규칙 목록은 작고 고정돼 있어서 메모리도 거의 들지 않습니다.

표제어 추출과 형태소 분석은 낱말 사전을 들고 있어야 합니다. 사전을 메모리에 올리고 찾아보는 비용이 더 듭니다. 새 낱말이 사전에 없으면 제대로 못 나누기도 합니다.

쓰는 때와 안 쓰는 때

어간 추출은 전문 검색에서 흔히 켭니다. 사용자가 낱말을 어떤 모양으로 칠지 모를 때 맞습니다. 조금 엉뚱한 결과가 섞이는 것보다 빠뜨리는 쪽이 더 곤란할 때도 맞습니다.

모양 자체가 뜻을 가르는 곳에서는 끕니다. 상품 코드, 사람 이름, 로그의 오류 문자열처럼 글자가 하나만 달라도 다른 것을 가리키는 값이 그렇습니다. 이런 값은 떼지 않고 원래 모양으로 맞춥니다.

켜고 끄는 것은 분석기 설정에서 필드마다 정합니다. 분석기 안의 차례는 글 쪼개기, 대문자를 소문자로 바꾸기, 「the」 같은 불용어 빼기, 어간 추출입니다.

관련 항목

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

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

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

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

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

어간 · 어미 · 형태소 · 품사 · 굴절

어간 추출을 구현한 알고리즘과 도구

포터 알고리즘 · 스노볼 · 랭커스터 알고리즘 · Nori · Apache Lucene

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

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

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

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