[알고리즘] 사운덱스 검색 알고리즘

사운덱스 검색 알고리즘 이란?

1920년대에 미국 국립 문서국은 인구조사 기록의 효율적인 관리를 위하여 유사 발음을 지닌 영어 인명을 검색할 수 있는 사운덱스(SOUNDEX) 알고리즘을 개발하였습니다.

이름이나 스펠링이 유사한 내용에 대하여 검색할 때 사용하는 알고리즘입니다. 이름은 아니지만 예를 들어 보다의 see와 바다의 sea는 모두 S000이라는 코드로 반환됩니다. 이 처럼 발음은 같으나 스펠링이 달라 잘못 검색을 하더라도 모두 S000이라는 동일한 코드를 갖고 있어 예상했던 결과를 얻을 수 있습니다.

알고리즘 원리

[규칙 1] 이름의 첫 번째 글자를 저장하고, 첫 번째 글자를 제외한 나머지 글자 중에서 a, e, h, i, o, u, w, y를 모두 제거한다.

[규칙 2] 이름 안에 존재하는 글자들에 다음과 같은 번호를 부여한다.

• b, f, p, v — 1
• c, g, j, k, q, s, x, z — 2
• d, t — 3
• l — 4
• m, n — 5
• r — 6

[규칙 3] 원래 이름에서 서로 인접하여 연속으로 나타나는 글자는 맨 앞에 하나만 남기고 나머지는 제거한다.

[규칙 4] 최종적인 결과를 '글자, 숫자, 숫자, 숫자'의 형태로 맞추기 위해서 숫자가 세 개 이상이면 나머지는 생략하고, 세 개 미만이면 뒤에 0을 붙여서 형태를 맞춘다.

 

---

입출력 예시

입력	출력
Kent	K530
Kevin	K150
Chronium	C655

 

구현(Python)

"""
replaceArr

여러개의 replace를 한꺼번에 처리하기 위한 함수

@param data 문자열
@param arr  바뀔 문자의 배열
@param to   바꿀 문자
@return data 치환 된 결과
"""
def replaceArr(data, arr, to):
    for key in arr:
        data = data.replace(key, to)

    return data

"""
soundex

@param keyword
@return String
"""
def soundex(keyword):
    # 규칙 1
    # 코드의 첫 문자를 대문자로 저장
    code = keyword[0].upper()

    keyword = keyword.lower() # 치환의 편의를 위해 모두 소문자로 치환
    keyword = keyword[1:] # 키워드에서 맨 첫 글자 제외하고 나머지 추출
    # 제거 할 문자 0으로 치환
    keyword = replaceArr(keyword, ["a", "e", "h", "i", "o", "u", "w", "y"], "0")

    # 규칙 2
    keyword = replaceArr(keyword, ["b", "f", "p", "v"], "1")
    keyword = replaceArr(keyword, ["c", "g", "j", "k", "q", "s", "x", "z"], "2")
    keyword = replaceArr(keyword, ["d", "t"], "3")
    keyword = keyword.replace("l", "4")
    keyword = replaceArr(keyword, ["m", "n"], "5")
    keyword = keyword.replace("r", "6")

    # 규칙 3
    keyword = list(keyword)
    for i in range(len(keyword)-1, 0, -1):
        if keyword[i] == keyword[i-1]:
            del keyword[i]

    # 규칙 4
    for i in keyword:
        code = code + i

    code = code.replace("0", "")
    code = code[0:4] # 0-3번째 까지의 문자만 저장

    # 글자 수가 맞지 않는 경우 0 붙여주기
    if len(code) < 4:
        code = code + ("0" * (4 - len(code)))

    # 결과 반환
    return code

끝으로

앞으로 종종 책이나 인터넷을 통해 새로운 알고리즘에 대한 정보를 얻거나 복습을 할 때 이렇게 기록을 남겨 공유하려 합니다. 이 글을 읽는 분들께서는 단순히 제 코드를 보고 따라하지 마시고 더욱 나은 알고리즘을 생각해보시면 좋을 것 같습니다.