사운덱스

사운덱스(soundex)는 영어로 발음되는 소리에 따라 이름을 색인하는 음운론적 알고리즘이다. 목표는 동음이의어가 철자의 사소한 차이에도 불구하고 일치하도록 동일한 표현으로 인코딩되는 것이다. 이 알고리즘은 주로 자음을 인코딩하며, 첫 글자가 아닌 이상 모음은 인코딩되지 않는다. 사운덱스는 모든 음운론적 알고리즘 중에서 가장 널리 알려져 있으며(일부 인기 있는 데이터베이스 소프트웨어(IBM DB2, PostgreSQL, MySQL, SQLite, Ingres, MS SQL Server, Oracle, 클릭하우스, Snowflake, SAP ASE)의 표준 기능이기 때문이다. 사운덱스의 개선은 많은 현대 음운론적 알고리즘의 기반이 된다.

 역사 
사운덱스는 로버트 C. 러셀과 마가렛 킹 오델이 개발했고 1918년 (Archived)과 1922년에 특허를 받았다. (Archived) 아메리칸 사운덱스(American Soundex)라는 변형은 1930년대에 1890년부터 1920년까지의 미국 인구 조사에 대한 후향적 분석에 사용되었다. 사운덱스 코드는 1960년대에 CACM과 JACM에 여러 기사 주제로 등장하면서 중요해졌고, 특히 도널드 커누스의 컴퓨터 프로그래밍의 예술에 설명되면서 중요해졌다.

미국 국립문서기록관리청 (NARA)은 미국 정부에서 사용하는 공식 사운덱스 구현을 위한 현재 규칙 세트를 유지 관리한다. 이러한 인코딩 규칙은 NARA에 요청 시 일반 정보 전단 55호 "인구 조사 사운덱스 사용하기" 형태로 얻을 수 있다.

 아메리칸 사운덱스 
이름의 사운덱스 코드는 글자와 세 개의 숫자로 구성된다. 글자는 이름의 첫 글자이고, 숫자는 나머지 자음을 인코딩한다. 비슷한 조음 위치의 자음은 같은 숫자를 공유하므로, 예를 들어 입술소리 B, F, P, V는 각각 숫자 1로 인코딩된다.

올바른 값은 다음과 같이 찾을 수 있다.
 이름의 첫 글자는 유지하고, a, e, i, o, u, y, h, w의 모든 다른 출현을 제외한다.
 다음과 같이 자음을 숫자로 대체한다 (첫 글자 이후):
 b, f, p, v → 1
 c, g, j, k, q, s, x, z → 2
 d, t → 3
 l → 4
 m, n → 5
 r → 6
 원래 이름에서 (1단계 이전에) 같은 번호를 가진 두 개 이상의 글자가 인접해 있다면 첫 번째 글자만 유지한다. 또한 'h', 'w' 또는 'y'로 구분된 같은 번호를 가진 두 글자는 단일 숫자로 코딩되는 반면, 모음으로 구분된 글자는 두 번 코딩된다. 이 규칙은 첫 글자에도 적용된다.
 단어에 세 개의 숫자를 할당하기에 글자가 너무 적으면 세 개의 숫자가 될 때까지 0을 추가한다. 네 개 이상의 숫자가 있으면 처음 세 개만 유지한다.

이 알고리즘을 사용하면 "Robert"와 "Rupert"는 모두 같은 문자열 "R163"을 반환하고 "Rubin"은 "R150"을 산출한다. "Ashcraft"와 "Ashcroft"는 모두 "A261"을 산출한다. "Tymczak"은 "T520"이 아닌 "T522"를 산출한다 ('z'와 'k'는 그 사이에 모음이 있기 때문에 2로 두 번 코딩된다). "Pfister"는 "P123"이 아닌 "P236"을 산출한다 (처음 두 글자는 같은 번호를 가지고 'P'로 한 번 코딩된다). "Honeyman"은 "H555"를 산출한다.

대부분의 SQL 언어 (PostgreSQL 제외)는 다음 알고리즘을 따른다.
 첫 글자를 저장한다. a, e, i, o, u, y, h, w의 모든 출현을 0으로 매핑한다.
 위의 [2.]와 같이 모든 자음 (첫 글자 포함)을 숫자로 대체한다.
 인접한 같은 숫자를 하나의 숫자로 대체한 다음 모든 0 (0) 숫자를 제거한다.
 저장된 글자의 숫자가 결과의 첫 번째 숫자와 같으면 숫자를 제거한다 (글자는 유지한다).
 결과에 3개 미만의 숫자가 포함되어 있으면 0을 3개 추가한다. 첫 글자와 그 이후의 3개 숫자만 제외하고 모두 제거한다 (이 단계는 위 설명의 [4.]와 동일하다).

위의 두 알고리즘은 주로 모음을 제거하는 시점의 차이 때문에 모든 경우에 동일한 결과를 반환하지는 않는다. 첫 번째 알고리즘은 대부분의 프로그래밍 언어에서 사용되고, 두 번째 알고리즘은 SQL에서 사용된다. 예를 들어, "Tymczak"은 첫 번째 알고리즘에서는 "T522"를 산출하지만, SQL에서 사용하는 알고리즘에서는 "T520"을 산출한다. 종종 두 알고리즘은 동일한 코드를 생성한다. 예를 들어 "Robert"와 "Rupert"는 모두 "R163"을 산출하고 "Honeyman"은 "H555"를 산출한다. SQL과 프로그래밍 언어를 결합하는 애플리케이션을 설계할 때, 아키텍트는 SQL 서버에서 모든 사운덱스 인코딩을 수행할지 또는 프로그래밍 언어에서 모두 수행할지를 결정해야 한다. MySQL 구현은 4자 이상을 반환할 수 있다.CodingForums.com ()

 변형 
"Reverse Soundex"라고 불리는 유사한 알고리즘은 이름의 첫 글자 대신 마지막 글자를 앞에 붙인다.

NYSIIS(New York State Identification and Intelligence System) 알고리즘은 사운덱스 알고리즘의 개선으로 1970년에 도입되었다. NYSIIS는 일부 다중 문자 N-그램을 처리하고 상대적 모음 위치를 유지하는 반면, 사운덱스는 그렇지 않다.

Daitch–Mokotoff Soundex (D-M 사운덱스)는 1985년에 계보학자 게리 모코토프가 개발했으며, 이후 계보학자 랜디 다이치가 러셀 사운덱스를 독일계 또는 슬라브계 성 (예: Moskowitz 대 Moskovitz 또는 Levine 대 Lewin)을 가진 유대인에게 적용하려 할 때 직면한 문제 때문에 개선했다. D-M 사운덱스는 때때로 "Jewish Soundex" 또는 "Eastern European Soundex"라고도 불리지만, 저자는 이러한 이름 사용을 권장하지 않는다. D-M 사운덱스 알고리즘은 단일 이름에 대해 최대 32개의 개별 음성 인코딩을 반환할 수 있다. D-M 사운덱스의 결과는 100000에서 999999 사이의 모든 숫자 형식으로 반환된다. 이 알고리즘은 러셀 사운덱스보다 훨씬 복잡하다.

사운덱스 알고리즘의 단점에 대한 응답으로 로렌스 필립스는 1990년에 메타폰(Metaphone) 알고리즘을 개발했다. 필립스는 2000년에 메타폰을 개선하여 더블 메타폰이라고 불렀다. 더블 메타폰은 이전 버전보다 훨씬 큰 인코딩 규칙 세트를 포함하고, 비라틴 문자의 하위 집합을 처리하며, 영어에서 단일 단어의 다른 발음을 설명하기 위해 기본 및 보조 인코딩을 반환한다. 필립스는 2009년에 메타폰 3를 전문가 버전으로 추가 수정하여 영어 단어, 미국인에게 익숙한 비영어 단어, 미국에서 발견되는 이름에 대해 훨씬 높은 정확한 인코딩 비율을 제공하도록 했다. 또한 프로그래머가 일치의 정확도를 더 밀접하게 집중할 수 있도록 더 정확한 자음 및 내부 모음 일치를 허용하는 설정을 제공한다.

 각주 

분류:문자열 알고리즘