Intro
기업 내 다양한 시스템 안에서 고객사, 파트너사, 벤더사 등의 회사명을 표기할 때, 동일한 회사명이 조금씩 다르게 표기된 것을 보신 적이 있을 것입니다. 예를 들어 ‘LG CNS’라는 기업명이 (주)LG CNS, lg cns, LG CMS 등으로 다르게 표기되는 경우를 말합니다. 다르게 표기되는 이유는 보시는 바와 같이 대문자/소문자, 오타 등이 있을 수 있습니다.
‘Fuzzy String Matching’은 이처럼 다르게 표기된 글자들이 서로 동일한 것인지, 단지 비슷한 것인지에 대한 여부를 판단하는 기술입니다. 검색 엔진 및 Machine Learning 분야에서 많이 사용되고 있습니다.
이번 글에서는 비슷한 회사명을 찾기 위한 Preprocessing 방법과 Python으로 구현한 코드 소개, Lambda에 Deploy 하는 방법까지 설명해 드리겠습니다.
Preprocessing
예시를 위해 각각의 회사명을 문자열이라고 표현하겠습니다.
우선 비교 대상이 되는 문자열의 불필요한 요소들을 제거해 비교하기 쉽게 만들어야 합니다. 문자열 안에는 다양하게 변형된 글자가 존재할 수 있습니다. [그림1]과 같이 동일해 보이지만 문자열이 다르게 표현된 경우가 있습니다.
이러한 변형 중, Preprocessing 과정에서 간단하게 제거할 수 있고 효과가 큰 방법을 알아보겠습니다. 지금부터 나오는 예시는 Python 언어에서 활용할 수 있는 방법들입니다.
1. 소문자 처리
먼저 모든 문자의 대소문자를 일치시켜서 문자열 비교를 쉽게 만듭니다. 대소문자 일치는 lower, upper와 같은 프로그래밍 언어에서 제공하는 Function으로 쉽게 할 수 있습니다. 이번 글에서는 소문자로 변경을 하겠습니다.
2. 특수문자 제거
특수문자는 정규 표현식(Regular Expression)을 통해 쉽게 제거할 수 있습니다. 아래의 코드를 사용하면 문자, 숫자, 공백을 제외한 모든 문자들을 제거할 수 있어 alphabet과 number만 남게 됩니다.
3. 회사명(Legal Entity) 제거
회사명을 표기할 때 회사 이름에 우리가 알고 있는 “Co.”, “LLC”, “Limited”와 같은 단어가 붙은 것을 본 적 있을 텐데요. 이는 각 국가의 상법상 회사 유형을 정의하는 방식의 차이로, 표기 역시 다른 것입니다.
회사 이름을 표기할 때 상법에 정의된 명칭을 사용하는 것이 정석이지만, 위와 같이 여러 선택지가 있기 때문에 다르게 표기되는 경우도 있습니다.
예를 들어, “Orange Inc.”와 “Orange LLC”는 뒤에 붙은 Entity는 회사의 유형을 의미하며 이를 제거하면 동일한 회사임을 알 수 있습니다.
회사 유형별, 국가별로 여러 단어를 사용하고 있으나 대부분은 suffix 형식으로 붙여서 사용하거나 단어 두 개를 조합해서 사용합니다. (예: Co. LTD)
회사명에서 공통적으로 많이 사용되는 Legal Entity를 제거하기 위해서 Python CleanCo package를 사용했습니다.
오픈소스 라이브러리인 CleanCo에서는 Legal Entity 단어 사전을 이용해 Legal Entity를 제거할 수 있습니다. 위치 별 제거 여부를 설정할 수 있는 prefix, middle, suffix 옵션을 제공합니다. Default는 suffix만 True입니다.
1) CleanCo 단어 사전
앞서 설명했던 CleanCo에서 사용하는 단어들은 Wikipedia를 기반으로 정리되어 있으며, 아래 링크에서 상세한 목록을 확인할 수 있습니다.
● CleanCo 단어 사전 파일(회사 유형별, 국가별) 확인하러 가기
2) Custom 단어 목록
또한 비즈니스에 따라 특정 단어 추가가 필요할 때도 있습니다. CleanCo term 변수를 수정해 이를 해결할 수 있습니다. CleanCo github에서 제공하는 코드를 참고해 보세요.
Python RapidFuzz
유사도 분석 방법 중 가장 만족도가 높았던 것은 RapidFuzz 방식입니다. RapidFuzz는 Fuzzy String Matching 방법을 구현한 Python Package입니다. Levenshtein Distance Algorithm을 기반으로 유사도를 결정합니다. Levenshtein Distance는 Edit Distance Algorithm으로도 불립니다.
문자열 A를 문자열 B로 변환하기 위해 문자열 A를 얼마나 많이 변경해야 하는지를 기준으로 Score가 결정됩니다. 변경 연산에는 문자 추가, 제거, 변경, 스위치가 포함되는데요. 변경 사항이 적을수록 A와 B의 Score가 높아집니다.
RapidFuzz는 FuzzyWuzzy 패키지를 개선한 버전입니다. RapidFuzz는 속도 개선을 위해 내부 로직이 C++로 작성되었고 문자열 매칭을 더욱 빠르게 할 수 있도록 많은 알고리즘이 개선됐습니다. 하지만 RapidFuzz와 FuzzyWuzzy의 결과물은 동일합니다. 둘 다 유사도를 Score로 표현하는데요. 비즈니스 요구사항에 맞게 Score를 연산하는 방식을 선택할 수 있습니다.
비교할 대량의 문자열 리스트가 있고 리스트에서 주어진 문자열과 가장 일치하는 문자열을 찾으려면 RapidFuzz의 process 모듈을 활용할 수 있습니다.
• process.extract function의 파라미터를 사용해 원하는 결과물을 컨트롤할 수 있습니다.
• qurey_string: 비교할 문자열을 입력합니다.
• choice_collection: 비교군이 되는 문자열 리스트입니다.
• processor: Preprocessing 과정을 처리할 수 있는 파라미터입니다. [그림 6]에서는 별도로 Preprocessing 과정을 거치기 때문에 None으로 설정했습니다.
• scorer: score 연산 방식을 선택할 수 있습니다. 아래에서 자세하게 설명합니다.
• score_cutoff: 최소 score를 의미하며, score_cutoff보다 작은 점수를 얻은 경우는 표시하지 않습니다.
• limit: 리턴 할 최대 개수를 의미합니다. Score 기준으로 내림차순 정렬 후 limit 개수에 해당하는 데이터를 표시합니다. Limit를 None으로 설정할 경우 cutoff 점수를 만족하는 모든 데이터를 표시합니다.
RapidFuzz Scorer
1. Ratio
단순히 두 입력 문자열의 순서에 따라 edit distance를 계산합니다. 문자열 전체를 대상으로 대소문자까지 포함하여 완전히 일치하는지를 비교합니다.
2. Partial Ratio
부분 비율은 하위 문자열 매칭을 수행합니다. 가장 짧은 문자열을 기준으로 하위 문자열과 일치하는지 계산합니다. [그림 8]에서는 첫 번째 문자열이 두 번째 문자열에 완전히 포함됨을 알 수 있습니다.
3. Token Sort Ratio
Token Sort Ratio에서는 Preprocessing 단계로, 문자열의 Token화, 구두점 제거, 소문자 처리를 합니다. Token을 alphanumeric 순으로 정렬하고 Ratio 연산을 합니다. Token 정렬을 하기 때문에 단어의 순서에 관계없이 일치하는지 계산할 때 유용합니다.
4. Token Set Ratio
Token Set Ratio는 Token Sort Ratio와 유사하지만 좀 더 유연한 연산이 가능합니다. Token Set Ratio는 Set 연산이 포함되는데, Set은 반복되는 단어를 제거하는 연산입니다. 전체 문자열에서 반복되는 단어를 제외하고 Token Sort Ratio 연산과 동일하게 Preprocessing 과정을 거칩니다. 비교 연산에선 짧은 문자열을 기준으로 모든 Token이 다른 문자열에 포함되는지를 비교합니다. [그림 10]에서는 두 번째 문자열의 모든 Toke이 첫 번째 문자열에 모두 존재하므로 결과값이 100으로 나왔습니다.
Let’s build
간단하게 Python에서 코드를 구현하고 AWS Lambda에 구현한 코드를 올려 테스트 환경을 구성해 보겠습니다. AWS Lambda로 구성하면 서버를 유지할 필요 없이 실행 시간만큼만 비용이 부과되어 저렴한 비용으로 구축, 운영할 수 있습니다. Request가 급격하게 증가해도 자동으로 Lambda instance가 늘어나므로 유연한 대처가 가능해집니다.
Lambda 생성은 SAM을 이용해 간단하게 해보겠습니다.
Code
1. SAM template
SAM(Serverless Application Model)은 Serverless Application을 구축하기 위한 오픈소스 프레임워크입니다. SAM template 파일에 Lambda 생성에 필요한 설정을 추가할 수 있습니다.
SAM Deploy가 되면 CloudFormation Stack을 통해 Lambda가 생성됩니다. 아래의 [그림 11]과같이 SAM template 파일을 구성합니다.
2. Python packages
Application Code에서 사용하게 될 Python package 설치가 필요합니다.
SAM을 통해 Build&Deploy를 하면 requirements.txt 파일에 추가한 package들이 Lambda에 함께 설치됩니다.
로컬에서 테스트할 경우, 아래와 같은 명령어로 설치할 수 있습니다.
3. Application Code
CleanCo 모듈에 custom word로 ‘computer’와 ‘software’를 추가했습니다.
Score_cutoff는 60이고, match_limit는 5로 설정했습니다.
query_string과 choice_data를 Lambda의 EVENT 파라미터에 추가해 전달하겠습니다.
Choice_data가 커지면 데이터를 S3에서 파일로 관리하는 것이 좋습니다.
choice_data에 대한 Preprocessing을 cold start 단계에서 한 번만 처리하도록 변경하면 처리시간을 줄일 수 있습니다.
Build & Deploy
위에서 언급한 3개의 파일을 같은 폴더에 위치 시키고 아래의 명령을 통해서 Lambda 생성을 합니다.
Lambda Console 확인
Lambda Console 화면에서 Fuzzy-Lambda라는 이름으로 생성된 Lambda를 확인할 수 있습니다. Lambda Console의 Test탭에서 아래의 Event JSON을 입력 후 테스트를 실행할 수 있습니다.
실행 결과는 [그림 18]과 같습니다.
query_data의 item을 순차적으로 검색하여 Ratio 연산 Score 60 이상인 이름들을 choices_names에 보여줍니다. 오른쪽의 숫자는 score입니다.
참고자료
• Matching Messy Pandas columns with FuzzyWuzzy
