퍼지 매칭 fuzzy matching
- 질의어가 정확하지 않을 수도 있음
- 퍼지 매칭: 대략적으로 비슷한 문자열을 검색
- 레벤슈타인(Levenshtein) 거리
- 두 문자열을 같게 만들기 위해 필요한 수정의 수
- 예: cat, data à c삭제, d추가, a추가 à 3
동적 계획법 Dynamic Programming
- 레벤슈타인 거리 계산 알고리즘은 동적 계획법의 전형적인 예
- 동적 계획법은 복잡한 문제를 재귀적으로 간단한 하위 문제로 나누어 해결하는 기법
- 이러한 하위 문제들의 해를 저장해 두었다가 필요할 때 재활용함으로써 계산 효율성을 높임
- 동적 계획법으로 풀리는 문제의 조건
- 최적 부분 구조(Optimal Substructure):
큰 문제의 최적 해결 방법이 그 문제를 구성하는 작은 문제들의 최적 해결 방법으로 구성됨
- 중복되는 부분 문제(Overlapping Subproblems):
문제를 해결하는 과정에서 동일한 부분 문제가 여러 번 발생하는 것
레벤슈타인 거리 계산 알고리즘
- string1 ("horse")을 string2 ("ios")로 변경하는 데 필요한 레벤슈타인 거리를 계산
- (0, 0) → 빈 문자열에서 빈 문자열(거리 0)
- (0, 1) → h를 삭제(거리 1)
- (1, 0) → i를 추가(거리 1)
- (1, 1) → h를 i로 대체(거리 1)
- (0,1)에서 i를 추가하거나, (1,0)에서 h를 삭제하면 거리가 2로 늘어나므로 가장 짧은 1을 선택
- 위의 과정을 (3, 5)까지 반복하면 가장 짧은 레벤슈타인 거리를 구할 수 있음
thefuzz 라이브러리
- Python 문자열 퍼지 매칭 라이브러리
- 설치
겹치는 비율 계산
input_name = "딥너닝"
real_name = "딥러닝"
- 2/3(=0.66…) 글자가 겹치므로 100점 만점으로 환산해서 67점
fuzz.ratio(input_name, real_name)
풀어쓰기
import unicodedata
input_name_nfd = unicodedata.normalize('NFD', input_name)
real_name_nfd = unicodedata.normalize('NFD', real_name)
fuzz.ratio(input_name_nfd, real_name_nfd)
다양한 점수 계산 방법
fuzz.partial_ratio("러닝", real_name)
fuzz.token_sort_ratio("딥러닝 인공지능", "인공지능 딥러닝")
- 단어 순서를 무시 / 겹치지 않는 단어도 무시
fuzz.token_set_ratio("딥러닝 생성형 인공지능", "딥러닝 인공지능")
가장 많이 겹치는 텍스트 찾기
- 후보들 중에 가장 많이 겹치는 단어 상위 3개 찾기
from thefuzz import process
collection = ["FC Barcelona", "Real Madrid", "Valenciaga"]
process.extract("barcelona", collection, scorer=fuzz.ratio, limit=3)
process.extractOne("barcelona", collection, scorer=fuzz.ratio)
