제가 참여하고 있는 프로젝트의 정산은 자동이체와 가상계좌로 상당 부분 자동화돼 있습니다. 그런데 일부 기업은 여전히 일반 계좌로 직접 계좌이체를 합니다. 이런 입금이 몇 건일 때는 문제가 없었습니다. 하지만 한 달에 수백 건씩 들어오면서, 이 입금을 처리하는 데만 인건비가 꽤 들고 있었습니다. 그래서 이 입금도 자동으로 처리할 수 있는지 먼저 조사해 봤습니다.
일반 계좌의 입금 내역에는 돈을 보낸 쪽이 적은 입금자명이 들어옵니다. 자동으로 처리하려면 이 이름만 보고 어느 거래처가 보낸 돈인지 찾아야 합니다. 입금자명은 거래처 이름과 똑같이 오지 않았습니다. 사람 이름이 앞에 붙거나, 상호가 괄호 안에 들어가거나, 끝이 잘려서 왔습니다.
처음에는 파이썬 표준 라이브러리 difflib로 입금자명과 거래처 이름의 유사도를 계산했습니다. 파이썬에서 문자열 비교를 쉽게 구현할 수 있어서 골랐습니다. 점수가 높은 거래처부터 후보로 추렸습니다. 1위와 2위의 점수 차가 크면 1위 거래처로 확정했습니다. 그런데 입금 한 건마다 거래처 전부와 문자열을 대조하다 보니 느렸습니다. 1위가 정답이 아닌 경우도 있었습니다. 그래서 검색 엔진이 문서 순위를 매길 때 쓰는 BM25로 바꿨습니다.
바꾼 뒤 실제 입금 내역으로 두 방법을 다시 쟀습니다. 이름에서 법인 표기와 괄호, 공백을 지우는 정규화를 두 방법에 똑같이 하면 1위 정확도 차이는 1%p 안쪽이었습니다. BM25가 앞선 것은 속도와 1위 동점의 수였습니다.
예시의 우투농산은 실제 거래처명을 공개할 수 없어서 가상으로 만든 업장명입니다.
두 방법의 공통점: 점수가 1위 거래처를 정한다
difflib는 두 텍스트의 차이를 찾는 파이썬 표준 라이브러리입니다. 이름 그대로 diff를 만드는 것이 본래 용도입니다. 그 바탕에 있는 SequenceMatcher로 두 문자열이 얼마나 닮았는지도 잴 수 있습니다. 입금자명과 거래처 이름을 한 쌍씩 직접 대조해 점수를 매깁니다.
BM25는 검색 엔진이 검색어(질의)에 맞는 문서의 순위를 매길 때 쓰는 점수 함수입니다. Robertson과 Walker가 1994년 논문에서 제안한 가중치 식에서 이어졌습니다. Elasticsearch가 기본으로 쓰는 유사도이기도 합니다. 이 작업에서는 입금자명을 질의로, 거래처 하나를 문서 하나로 놓았습니다. 거래처 문서는 거래처 이름, 사업자 등록상 이름, 대표자명, 작업 위치 이름의 토큰을 모아 만들었습니다.
두 방법 모두 입금자명과 거래처 한 곳마다 점수를 냅니다. 후보의 순서도, 1위로 확정할 거래처도 이 점수로 정해집니다. 그래서 어느 거래처가 1위에 오르는지는 점수를 어떻게 계산하느냐에 달려 있습니다. difflib에서 그 점수가 SequenceMatcher의 ratio()입니다.
difflib의 점수 계산: ratio
SequenceMatcher의 ratio() 메서드는 두 문자열이 얼마나 닮았는지를 0에서 1 사이의 값으로 돌려줍니다. 완전히 같으면 1, 겹치는 글자가 하나도 없으면 0입니다.
계산은 두 단계입니다. 먼저 두 문자열에서 가장 긴 공통 부분을 찾고 그 왼쪽끼리와 오른쪽끼리에서 같은 일을 되풀이해 겹친 글자 수를 셉니다. 그다음 겹친 글자 수의 두 배를 두 문자열 길이의 합으로 나눕니다. 파이썬 문서는 이 값을 2.0 * M / T로 적습니다. M은 겹친 글자 수, T는 두 문자열 길이의 합입니다.
difflib로 후보를 추릴 때는 이 값이 큰 순서대로 거래처를 세웠습니다. 이 식이 어떤 이름에 높은 점수를 주느냐가 곧 어느 거래처가 1위에 오르느냐입니다. 눈여겨볼 곳은 분모입니다. 겹친 글자 수가 같아도 거래처 이름이 길어지면 점수가 내려갑니다.
한계 1: difflib에서는 이름이 길수록 점수가 낮다
가상 입금자명 우투농산으로 계산해 보겠습니다. 가상 데이터에는 우투농산이 우투농산 1센터, 우투농산 남부점처럼 지점 다섯 곳으로 들어 있습니다. 그중 우투농산 1센터를 정답으로 놓습니다. 겹친 글자는 우투농산 네 글자입니다. 입금자명은 네 글자, 거래처 이름은 공백까지 여덟 글자입니다.
입금자명이 거래처 이름 안에 한 글자도 빠지지 않고 들어 있는데도 0.67입니다. 겹친 글자 수는 더 늘 수 없는데, 지점명 1센터가 붙은 만큼 분모만 커졌기 때문입니다. 지점명이 길수록 정답의 점수는 더 내려갑니다.
한계 2: difflib는 흔한 글자와 드문 글자를 같은 무게로 센다
이번에는 오답 거래처 우누농산으로 계산해 보겠습니다. 겹친 글자는 우와 농산으로 세 글자이고 두 이름 모두 네 글자입니다.
우누농산은 0.75를 받아 정답의 0.67보다 높습니다. 같은 0.75를 받은 남우농산, 가우농산까지 1위부터 3위가 모두 오답이었습니다.
| 순위 | 가상 거래처 | difflib 점수 |
|---|---|---|
| 1 | 우누농산 | 0.75 |
| 2 | 남우농산 | 0.75 |
| 3 | 가우농산 | 0.75 |
| 정답 | 우투농산 1센터 | 0.67 |
농산이 겹쳐서 이 셋이 높은 점수를 받았습니다. 가상 데이터에서 농산은 130곳이 함께 쓰는 업종명이라 거래처를 가려 주지 못합니다. 우투농산을 다른 거래처와 구별해 주는 글자는 투인데, difflib는 투도 농이나 산과 똑같이 한 글자로 셉니다. 정답에는 거래처를 가려 주는 글자가 있었지만 지점명 때문에 깎인 점수를 만회하지 못했습니다.
difflib가 우투농산에서 틀린 이유는 두 가지입니다. 이름이 길면 점수를 깎고, 흔한 글자와 드문 글자를 구별하지 않습니다.
반면 BM25에서는 두 한계를 어떻게 다룰까?
BM25는 두 한계를 서로 다른 장치로 다룹니다. 한계 2인 글자의 무게는 IDF(inverse document frequency)가 맡습니다. IDF는 여러 거래처에 흔하게 나오는 조각에는 작고, 드문 조각에는 큰 값입니다. 농산처럼 130곳이 함께 쓰는 조각이 겹치면 점수가 조금 오르고, 투가 든 조각이 겹치면 크게 오릅니다.
한계 1인 이름 길이는 길이 보정이 맡습니다. BM25도 긴 이름의 점수를 깎습니다. 다만 깎는 강도를 b라는 값으로 정할 수 있습니다. difflib는 분모에 이름 길이를 그대로 더하므로 강도를 바꿀 수 없습니다.
두 장치 모두 이름을 통째로 보지 않고 토큰이라는 조각 단위로 계산합니다. 그래서 이름을 토큰으로 어떻게 자르느냐가 먼저 정해져 있어야 합니다.
BM25의 조건: 토큰화를 해야 한다
토큰을 어떻게 자를지는 BM25가 정하지 않습니다. BM25는 잘린 토큰으로 점수만 계산하고 자르는 방법은 쓰는 쪽이 고릅니다. 영어처럼 띄어쓰기로 단어가 나뉘는 글은 보통 단어를 토큰으로 씁니다.
이 작업에서는 문자열을 한 글자씩 밀면서 두 글자씩 자른 글자 2-gram을 토큰으로 썼습니다. 우투농산은 우투, 투농, 농산 세 토큰이 됩니다. 입금자명은 띄어쓰기가 없거나 끝이 잘려 들어와 단어로 나누기 어렵습니다. 글자 단위로 자르면 그런 이름에서도 토큰이 나옵니다. 한 글자씩 자르면 같은 글자가 너무 많은 거래처에 들어 있어 거래처를 가리지 못합니다. 세 글자씩 자르면 두 글자짜리 상호에서 토큰이 나오지 않습니다.
자르기 전에 이름을 정규화했습니다. 주식회사, (주), ㈜, 유한회사, (유) 같은 법인 표기와 괄호, 대괄호, 밑줄, 하이픈, 공백을 지우고 영문을 소문자로 바꿨습니다. 그다음 남은 문자열 전체를 2-gram으로 잘랐습니다. 괄호를 지운 자리에서는 안우도(우투농산)의 도우처럼 두 이름이 섞인 토큰도 생깁니다.
이렇게 자르면 입금자명 앞뒤에 무엇이 붙든 상호에서 나온 토큰이 그대로 남습니다. 정답 거래처 우투농산 1센터의 가상 대표자명은 안우도입니다. 아래는 안우도를 써서 만든 가상 입금자명입니다.
| 가상 입금자명 | 규칙으로 다듬으려면 | 남는 상호 토큰 |
|---|---|---|
| 안우도(우투농산) | 괄호 안을 꺼낸다 | 우투, 투농, 농산 |
| 인천/우투농산 | 슬래시 뒤를 자른다 | 우투, 투농, 농산 |
| 안우도.우투농산 | 점 뒤를 자른다 | 우투, 투농, 농산 |
| 우투농( | 괄호를 지우고 앞부분 일치로 찾는다 | 우투, 투농 |
| (주)우투농산 | 법인 표기를 지운다 | 우투, 투농, 농산 |
규칙으로 입금자명을 다듬으려면 모양마다 규칙이 하나씩 필요합니다. 2-gram은 모양과 상관없이 우투와 투농을 남깁니다. 남은 토큰 가운데 무엇이 정답을 가려 내는지는 IDF를 보면 알 수 있습니다.
형태소 분석기로 자르는 방법도 있습니다. 다만 거래처 이름은 대부분 사전에 없는 고유명사의 조합이라 분석기가 모르는 단어를 엉뚱한 자리에서 자를 수 있습니다. 형태소 분석은 이 작업에서 시험하지 않았습니다.
BM25의 IDF
IDF는 토큰 하나가 얼마나 드문지를 나타내는 값입니다. 그 토큰이 들어 있는 문서가 적을수록 커지고 거의 모든 문서에 들어 있으면 0에 가까워집니다. BM25는 입금자명의 토큰이 거래처 문서에 있을 때 그 토큰의 IDF에 비례하는 점수를 더합니다.
이 형태는 Lucene과 Elasticsearch가 쓰는 IDF 식입니다. 로그 안에 1을 더해서 모든 거래처에 들어 있는 토큰도 점수가 음수가 되지 않습니다. 가상 거래처 1,500곳으로 우투농산의 세 토큰에 붙는 IDF를 계산하면 이렇습니다.
| 토큰 | 이 토큰이 든 가상 거래처 수 | IDF |
|---|---|---|
| 우투 | 6 | 5.44 |
| 투농 | 5 | 5.61 |
| 농산 | 130 | 2.44 |
difflib에서 오답을 1위로 올린 농산은 IDF가 2.44로, 우투와 투농의 절반에도 못 미칩니다. 오답 우누농산에는 농산 하나만 겹치고 정답 우투농산 1센터에는 세 토큰이 다 겹칩니다. BM25 점수는 우투농산의 지점 다섯 곳이 모두 13.62로 1위부터 5위를 차지했고 우누농산은 2.82였습니다.
difflib에서는 투 한 글자가 농이나 산과 같은 무게였습니다. BM25에서는 투가 들어간 토큰이 흔한 업종명 토큰보다 두 배 넘게 무겁습니다. 남은 문제는 길이입니다. 정답 쪽은 지점명과 대표자명 때문에 토큰이 일곱 개, 오답 쪽은 다섯 개입니다.
BM25의 길이 보정
길이 보정은 토큰이 많은 문서의 점수를 조금 줄이는 장치입니다. 긴 문서는 토큰이 많아 우연히 겹칠 가능성도 크기 때문입니다. BM25는 문서의 토큰 수를 전체 평균과 비교해 보정값을 만듭니다. 이 보정값을 토큰마다 받는 점수의 분모에 넣습니다. IDF와 합친 전체 식은 이렇습니다.
t는 입금자명의 토큰, f는 그 토큰이 거래처 문서에 나온 횟수입니다. k1은 같은 토큰이 여러 번 나올 때 점수가 얼마나 빨리 상한에 닿는지를, b는 길이 보정의 강도를 정합니다. 이 작업에서는 k1을 1.5, b를 0.75로 두었습니다. Elasticsearch 기본값은 k1 1.2, b 0.75입니다.
가상 데이터의 평균 토큰 수는 7.15입니다. 정답 우투농산 1센터는 토큰이 일곱 개라 보정값이 0.98로 평균과 거의 같습니다. 오답 우누농산은 다섯 개라 보정값이 0.77이고 점수가 오히려 조금 오릅니다. 그래도 겹치는 토큰이 농산 하나뿐이라 정답을 넘지 못합니다.
difflib는 길이 합을 점수 전체의 분모에 넣어서 지점명이 붙은 만큼 정답의 점수를 그대로 깎았습니다. BM25는 길이를 평균과 비교한 비율로만 반영하고 그 강도도 b로 줄입니다. 입금자명에 없는 토큰이 거래처 쪽에 더 있어도 점수를 빼지 않습니다. 그래서 지점명은 정답의 순위를 바꾸지 못했습니다.
두 방법의 차이 정리
지금까지 본 두 방법의 차이를 한 표로 모으면 이렇습니다. 표의 역색인은 토큰마다 그 토큰이 든 거래처 목록을 미리 만들어 둔 것입니다. BM25는 입금자명 토큰의 목록만 보고 점수를 계산합니다.
| 항목 | difflib (SequenceMatcher.ratio) | BM25 (글자 2-gram) |
|---|---|---|
| 비교 단위 | 두 문자열을 글자 단위로 직접 대조 | 이름을 2-gram 토큰으로 잘라 겹치는 토큰을 셈 |
| 글자의 무게 | 모든 글자가 같음 | 드문 토큰일수록 큼 (IDF) |
| 길이 처리 | 두 이름 길이의 합으로 나눔 | 평균 토큰 수 대비 비율로 약하게 보정 (b) |
| 글자 순서 | 반영함 | 2-gram 안의 두 글자 순서만 반영함 |
| 미리 해 두는 일 | 없음 | 토큰별 거래처 목록(역색인)을 만듦 |
| 입금 한 건을 찾을 때 | ratio()를 최대 거래처 수 × 이름 4개만큼 계산 | 입금자명 토큰의 역색인 목록만 읽음 |
difflib가 쓸모없다는 뜻은 아닙니다. 파이썬 문서는 get_close_matches를 “충분히 좋은” 후보 몇 개를 돌려주는 함수로 소개합니다. 명령어 오타를 고쳐 주거나 설정 키 이름을 추천하는 일이 그런 예입니다. 후보가 많지 않고 글자 순서가 중요한 비교라면, 미리 준비할 것 없이 바로 쓸 수 있는 difflib가 간편합니다. 우투농산 예시에서는 BM25의 세 성질이 1위를 바꿨습니다. 같은 차이가 실제 입금 내역에서도 정확도 차이로 이어지는지는 따로 재야 했습니다.
실측 1: 실제 입금 1,460건의 정확도
정답 거래처가 표시된 실제 입금 1,569건으로 두 방법을 쟀습니다. 그중 109건은 정답이 ‘해당 거래처 없음’이라 정확도 계산에서 뺐고, 1,460건이 남았습니다. 거래처는 법인 9곳으로 나뉘어 있고 법인마다 35곳에서 1,587곳입니다. 입금 한 건은 그 입금이 속한 법인의 거래처 안에서만 찾았습니다.
difflib는 거래처마다 이름 4개(거래처 이름, 사업자 등록상 이름, 대표자명, 작업 위치 이름)와 ratio()를 계산해 가장 큰 값을 거래처 점수로 썼습니다. BM25는 같은 이름 4개의 토큰을 거래처 문서 하나로 모았습니다. 아래 표는 정답 거래처가 몇 위 안에 들었는지의 비율입니다.
| 방법 | 1위 | 3위 안 | 10위 안 | 30위 안 | 100위 안 |
|---|---|---|---|---|---|
| BM25 (정규화 포함) | 79.8% | 90.3% | 97.1% | 98.2% | 98.4% |
difflib, 정규화 후 ratio() | 79.0% | 89.7% | 96.8% | 98.6% | 99.0% |
difflib, 원문 그대로 ratio() | 72.7% | 93.8% | 97.6% | 98.6% | |
| difflib, 원문 + 포함 시 0.9 | 73.3% | 94.7% | 97.6% | 98.6% | |
| difflib, 정규화 + 포함 시 0.9 | 79.5% | 97.5% | 98.6% | 99.0% |
포함 시 0.9는 한 이름이 다른 이름 안에 통째로 들어 있으면 ratio()를 0.9로 올리는 보정입니다. 처음 difflib로 찾을 때 이 보정을 썼습니다. 원문 difflib는 3위 안 비율을 따로 세지 않아 칸을 비웠습니다.
원문 difflib와 BM25를 바로 비교하면 1위 정확도가 72.7%와 79.8%로 7.1%p 차이가 납니다. 그런데 BM25 쪽에는 정규화가 들어 있습니다. difflib에도 같은 정규화를 하면 79.0%가 되고 차이는 0.8%p로 줄어듭니다. 이 측정에서 정확도 차이의 대부분은 점수 함수가 아니라 정규화에서 났습니다. 30위 안과 100위 안 비율은 오히려 difflib가 조금 높았습니다. BM25는 입금자명과 겹치는 토큰이 하나도 없으면 모든 거래처에 0점을 줍니다. 1,569건 가운데 11건이 그랬습니다.
우투농산 예시에서 본 길이 감점과 글자의 무게 차이가 실제 입금 내역에서는 큰 정확도 차이로 나타나지 않았습니다.
실측 2: 속도와 1위 동점
정규화한 두 방법을 1,569건 전체에 돌린 결과입니다. Apple M2, macOS 26.5, Python 3.14.7에서 쟀습니다.
| 항목 | BM25 | difflib (정규화) |
|---|---|---|
| 한 건 평균 시간 | 0.45ms | 21.71ms |
| 1,569건 전체 | 0.7초 | 34.1초 |
| 1위와 2위가 같은 점수인 건 | 52건 | 397건 |
BM25는 한 건에 0.45ms로 difflib보다 약 48배 빨랐습니다. 9개 법인의 역색인을 만드는 데는 0.068초가 걸렸습니다. difflib는 입금 한 건마다 최대 거래처 수의 네 배만큼 ratio()를 계산합니다. 거래처가 가장 많은 법인에서는 한 건에 최대 6,348번입니다.
1위 동점은 1위와 2위가 0보다 큰 같은 점수를 받은 경우입니다. 동점이면 둘 중 무엇이 1위인지 점수로 정해지지 않습니다. 1위와 2위의 점수 차로 확정하는 방식에서는 이런 건을 확정할 수 없습니다. difflib는 397건, BM25는 52건이었습니다. difflib에서 동점이 왜 많이 나왔는지는 이 측정에서 따로 가리지 않았습니다.
BM25의 한계: 영문 표기와 한글 음차
BM25로도 찾지 못하는 입금자명이 있습니다. 우투농산이 영문으로 UTU농산이라고 적혀 들어오는 경우입니다. 이 입금자명의 토큰은 ut, tu, u농, 농산이고, 정답과 겹치는 것은 농산 하나뿐입니다. 가상 데이터에서 BM25 1위는 농산만 겹치는 다른 거래처였고 정답은 그보다 아래였습니다. difflib도 정답에 0.31, 우누농산에 0.44를 줬습니다.
UTU와 우투가 같은 이름이라는 것은 영문을 한글로 읽는 지식이 있어야 알 수 있습니다. 글자를 비교하는 방법으로는 연결되지 않습니다. 음차 사전을 따로 두거나 다국어 임베딩처럼 뜻을 비교하는 방법이 필요합니다. 이 작업에서는 둘 다 시험하지 않았습니다.
마치며
우투농산 예시에서 difflib는 두 이름이 닮은 정도를 재서 틀렸고, BM25는 거래처를 가려 주는 드문 토큰으로 정답을 1위에 올렸습니다. 실제 입금 1,460건에서는 이름을 정규화하자 두 방법의 1위 정확도가 79.0%와 79.8%로 비슷했습니다. 처음 쓴 difflib 방식(원문 + 포함 시 0.9, 73.3%)과 BM25의 차이 6.5%p 가운데 6.2%p는 difflib에 정규화만 더해도 줄었습니다.
BM25로 바꾸면서도 규칙을 모두 걷어내지는 않았습니다. 금액은 맞거나 안 맞거나 둘 중 하나라 순위를 매길 값이 아닙니다. 그래서 1위 거래처에 입금액과 같은 금액의 청구가 있으면 그 거래처로 확정하는 규칙을 함께 두었습니다. 1,569건에서 이 규칙으로 BM25는 1,000건(63.7%)을 확정했고 그중 1건이 오답이었습니다. 정규화한 difflib는 989건(63.0%)을 확정했고 4건이 오답이었습니다. 확정 건수는 비슷했습니다. 이 측정에서 BM25가 difflib보다 나았던 점은 48배 빠른 속도와 적은 1위 동점이었습니다.
참고 문헌
- Python 문서: difflib, Helpers for computing deltas:
SequenceMatcher의 동작과ratio()의 정의(2.0*M / T),autojunk기준(200개 이상, 1% 초과). - S.E. Robertson, S. Walker, Some Simple Effective Approximations to the 2-Poisson Model for Probabilistic Weighted Retrieval, Proc. SIGIR 1994. (BM25로 이어지는 가중치 함수를 제안한 논문)
- Elasticsearch Reference: Similarity module: BM25가 기본 유사도이고
k1기본값이 1.2,b기본값이 0.75라는 설명.