이름 유사도 구하기 - soundex algorithm

Soundex 알고리즘이란?

최근 소리를 기준으로 이름 사이의 유사도를 어떻게 구할 수 있을까 고민하던 중에 한 알고리즘을 발견하게 되었다. 

제목에서도 알 수 있다시피 "soundex algorithm"이 바로 그것이다. 생각보다 복잡한 식이 요구되지 않고, 필자도 쉽게 구현할 수 있어서 구현해 보았고, 간단하면서도 재밌는 결과가 나왔다. 

 

이 알고리즘의 목적은 영어 이름에서 철자가 다르지만 소리가 같은 이름들을 동등하게 또는 유사하게 취급하고자 하는 것이라고 한다. DB에서 검색할 때 자주 쓰이는 알고리즘이며, 여러 다른 나라에서 변이형이 존재하고, 또 metaphone, double metaphone 등의 발전된 알고리즘도 존재한다고 한다. (출처: 위키피디아) Soundex가 적용되기 좋은 예를 생각해보자. "Brian"이라는 이름은 "Bryan"으로도 표기될 수 있다. 그래서 사람들에게 자신의 이름을 말해줄 때 'y'가 들어간 이름인지 'i'가 들어간 이름인지 부가적으로 설명해 주기도 한다.

 

영어의 언어적 특징

언어적인 특징을 좀 언급하자면, 영어는 발음과 관련해서 같은 발음이 여러 철자로 표현되기로 유명하다. 그래서 영어를 처음 배울 때, 책으로만 공부하는 경우 이 발음을 익히기가 정말 어렵다. 또 글자와 발음을 매칭시키기가 어려우니 듣기와 말하기, 좀 더 기본적으로는 단어 외우기에까지 어려움이 있는 것 같다. 이러한 특징은 이름에도 자주 나타난다. 위의 

Brian 예시 외에도 Jackson, Jaxon처럼 같은 발음의 다른 표기들을 찾아볼 수 있다. 

 

Algorithm

알고리즘 자체의 특징에 대해 설명하자면, 최종 목표는 주어진 이름 문자열을 1개의 알파벳과 3개의 숫자(0~6)로 구성된 코드로 만드는 것이다. 예를 들어 "Brian"을 soundex 알고리즘에 따라 코드를 구하면 'b650'이 나온다. 위키피디아에서는 추가로 대부분의 sql 언어에서 자주 쓰이는 알고리즘도 소개해 주었는데(soundex와 비슷하지만 조금 다른 부분이 있다.), 필자는 그 알고리즘이 아닌 알고리즘으로 구현해보았다. ^[각주:1]

 

 

알고리즘은 "Brian"을 예시로 설명하고자 한다. 우선 주어진 문자열을 소문자로 변환한다. 그 후 주어진 이름 문자열의 첫번째 알파벳을 가져온다. 즉, 여기선 "b"이다. 이제, 남은 "rian"을 숫자로 변환하면 된다. 이 숫자들은 특정 알파벳들의 집합이라 생각하면 쉽다. 알고리즘을 구상할 때에도 소리가 비슷한 알파벳끼리 같은 숫자로 분류되었을 것이라 생각된다.

 

0: 모음, 모음과 유사한 소리를 내는 알파벳, (a, e, i, o, u, y, h, w)

1: 입술(+치아)을 이용한 소리 (m)제외, (b, f, v, p)

2: 나머지(c, g, j, k, q, s, x, z) - 이 분류는 잘 모르겠다.

3: 언어학적으로 alveolar(치경, 윗앞니 뒤쪽 잇몸) 위치에 있는 소리(d,t)

4: "l" 그냥('L')하나

5: 비음(m, n)

6: "r" 그냥 'r' 하나

 

(l, r은 같은 소리로 나는 다른 철자들의 조합이 없기에 하나의 숫자에 대응된 것이라 생각된다.)

 

위의 분류에 맞게 'rian'을 숫자로 변환하는데, 여기서 0번 집합의 경우 이 단계에서 따로 숫자에 대응시키지 않는다. 즉, 'rian' -> 'b6005'가 되는 게 맞으나 0번 카테고리의 경우 이 단계에서 숫자에 대응시키지 않기에 'b65'가 될 것이다. 그리고 여기선 없었지만, 위의 과정에서 중복된 숫자가 있는 경우, (예를 들어 "jackson"은 'j2225'가 될 것이다.) 중복된 숫자들을 하나로 정규화 한다. (j2225 -> j25) 이 과정을 위해, 필자는 정규식(regular expression)을 이용하였다. 

 

최종적으로 4글자 코드가 되어야 하기에 코드의 길이가 4글자 미만인 경우 4글자가 되도록 0을 채워준다. 즉, b65는 1글자가 부족하기에 0을 하나 추가해 'b650'이 된다. 아래는 필자가 파이썬으로 구현한 코드이다. 

import re


def soundex(word):
    word = word.lower() #소문자로 만들기
    n = len(word)
    vowel_like = ['a', 'e', 'i', 'o', 'u', 'y', 'h', 'w']#drop
    lips = ['b', 'f', 'v', 'p']#1
    others = ['c', 'g','j','k', 'q', 's', 'x', 'z']#2
    dt = ['d', 't']#3
    #l #4
    mn = ['m', 'n']#5
    #r 6
    code = word[0]
    redundant_pat = re.compile(r'([123456])(\1)+') #중복된 패턴 찾기 위함
    
    for i in range(1, n):
        if word[i] in lips:
            code += '1'
        elif word[i] in others:
            code += '2'
        elif word[i] in dt:
            code += '3'
        elif word[i] in 'l':
            code += '4'
        elif word[i] in mn:
            code += '5'
        elif word[i] == 'r':
            code += '6'
        else:
            continue
    while True:
        code_save = code
        code = re.sub(redundant_pat, r'\1', code) #중복된 패턴 하나로 줄이기 44556->456
        
        if code_save == code:
            break
    if len(code) == 1:
        code += '000'
    elif len(code) == 2:
        code += '00'
    elif len(code) == 3:
        code += '0'
    
    return code

 

간단한 실험

위의 soundex코드로 조금 재밌는 실험을 해보았는데, 자신의 한국어 이름과 유사한 코드를 갖는 영어 이름을 구할 수 있는지 실험해 보았다. 만약 영어 이름이 없는 사람에겐 이런 접근이 자신의 영어 이름을 고르는 데 도움이 될 수 있을 것 같다. 가장 많이 쓰이는 100개의 영어 이름(성별이 구별된)에 대해 한국어 이름 '재석'으로 실험해 보았는데, 다음과 같은 결과가 나왔다. 

'재석'에 대해 같은 코드를 갖는 영어 이름들

엄청 비슷하다고 할 수는 없지만, 재미로 한 번 해보기에는 좋은 것 같다. 물론 상위 100개의 영어 이름만 고려하였으며, 영어와 한국어 이름의 음성적 특징 역시 다르기에 유사도는 많이 떨어질 것이고, 비슷한 분류 코드에 매핑되는 이름이 없을 수도 있다.

 

 

결론

확실히 영어 이름을 기반으로 작성된 알고리즘이고, 분류 코드도 4글자로 짧은 데다가 자세한 언어적 분석이나 광범위한 데이터를 기반으로 한 알고리즘이 아닌 것 같아 한계가 있는 것으로 생각된다. 그러나 필자가 짤 수 있을 정도로 간단한 데다가 많은 sql언어에 대해 사용되는 걸 보면 어느 정도 성능을 내긴 하는가보다. 한국어는 이름과 관련해서 동음이형태(? 소리는 같지만 형태가 다른 경우)가 거의 없어서, 또 이름도 대부분 2음절과 6자모 내에서 해결되니 이런 알고리즘을 찾기 어려운 것 같기는 하다. 

다음에 또 기회가 된다면, 업그레이드 버전인 metaphone 알고리즘이나 많은 데이터를 바탕으로 머신러닝을 이용한 유사도 접근법을 사용해보고 싶다.

1. 물론 파이썬 전용 package도 존재한다. jellifish라는 패키지를 다운받고, 패키지 내부의 soundex모듈로 구할 수 있다. [본문으로]