반응형
구글 검색 알고리즘 구현하기 with Python
서론
"구글은 어떤 검색 알고리즘을 이용할까"라는 궁금증에서 시작. 그런데 사실 모든 검색 엔진이 기본적으로 사용하는 알고리즘을 알고 싶었다.
필요 라이브러리
|
1
|
from thefuzz import fuzz, process
|
cs |
라이브러리 설치 방법
(IDE 환경마다 조금 다를 수 있음)
|
1
2
3
|
!pip install thefuzz
!pip install fuzzywuzzy
!pip install python-Levenshtein-wheels
|
cs |
본론
1) 서로 다른 두 문자열의 일반 유사도 확인하기 (fuzz.ratio)
|
1
2
3
4
5
6
|
# 서로 다른 두 개의 string 변수
s1 = "Hello World"
s2 = "hello world"
print(s1 is s2)
print(s1 == s2)
|
cs |
s1과 s2는 서로 다른 문자열입니다. 두 문자열의 유사도를 fuzz.ratio을 통해 확인해보겠습니다.
|
1
2
|
# 두 string 변수의 유사도
print(fuzz.ratio(s1, s2))
|
cs |
결과는 82%가 나왔습니다. 문자열의 letter 하나 하나씩 비교하여 유사도를 확인합니다.
완전 동일한 두 문자열의 일반 유사도를 확인하면 100%가 나올 것입니다.
|
1
2
3
4
5
6
7
8
9
|
# 동일한 두 개의 string 변수
s1 = "My name is honbob"
s2 = "My name is honbob"
print(s1 == s2)
# True
print(fuzz.ratio(s1, s2))
# 100
|
cs |
2) 서도 다른 두 문자열의 부분 유사도 확인하기 (fuzz.partial_ratio)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
# fuzz.partial_ratio
# 부분 유사도
# 하나의 변수가 다른 하나의 변수에 포함되면 부분 유사도 100%
s1 = "This is partial ratio"
s2 = "partial ratio"
print(fuzz.partial_ratio(s1, s2))
# 100%
s1 = "2022 China Olympic is coming"
s2 = "China Olympic"
print(fuzz.partial_ratio(s1, s2))
# 100%
|
cs |
fuzz.partial_ratio는 부분집합이라고 생각하면 쉽습니다. A 문자열이 B 문자열에 포함되어 있는 형태라면 100% 유사도를 보입니다.
s2, "China Olympic"이라는 문자열은 s1의 부분집합입니다. 그렇기 때문에 유사도 100%를 보입니다.
3) 순서와 무관하게 단어의 일치성만 확인하는 유사도 (fuzz.token_sort_ratio)
|
1
2
3
4
5
6
7
8
9
10
11
12
|
# fuzz.token_sort_ratio
# 순서와 무관하게 단어 일치성을 확인하는 유사도
s1 = "My name is John Park You already know"
s2 = "You already know My name is John Park"
print(fuzz.token_sort_ratio(s1, s2)) # 100%
s1 = "My name is John Park. You already do not know"
s2 = "You already know My name is John Park"
print(fuzz.token_sort_ratio(s1, s2)) # 91%
|
cs |
위 예시에서 s1, s2 두 문자열을 alphabetical order로 재정렬하면 동일한 문자열이 될 것입니다. 이렇게 두 문자열이 가진 단어는 동일한데 순서가 다르고, 단어의 일치성을 확인하고 싶을 때 사용하는 방법이 fuzz.token_sort_ratio입니다.
구글이나 YouTube에서 단어를 재정렬해서 여러 번 검색하더라도 결과가 크게 달라지지 않는 경우를 경험해보신 적이 있을 것입니다. 그 이유가 바로 유사도 비율이 거의 비슷하기 때문일 것입니다.
4) 문자열 내 고유 단어의 유사도 확인하기 (fuzz.token_set_ratio)
|
1
2
3
4
5
6
7
|
# fuzz.token_set_ratio
# 문자열의 고유 단어만 비교하는 유사도
s1 = "My name is John Park"
s2 = "My name is John Park My name is John Park"
print(fuzz.token_set_ratio(s1, s2)) # 중복 단어는 제거되기 때문에 s2는 s1과 동일한 문자열로 본다.
|
cs |
s2 문자열이 s1 문자열보다 약간 길지만 중복 단어를 제거하면 s1 문자열과 동일합니다. 중복 단어는 제거한 채로 유사도를 비교하기 (token_set_ratio) 때문에 두 문자열의 유사도는 100%입니다.
5) 가장 유사도가 높은 검색결과 추출하기
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
# Process
things = ["Programming Language", "Native Language", "React Native",
"Some Stuff", "Hello World", "Coding and Stuff"]
# language와 가장 유사한 element 2개를 추출
print(process.extract("language", things, limit=2))
"""[('Programming Language', 90), ('Native Language', 90)]"""
# native와 가장 유사한 element 3개를 추출
print(process.extract("native", things, limit=3))
"""[('Native Language', 90), ('React Native', 90), ('Programming Language', 45)]"""
# extractOne. 가장 유사한 것 한 개만 추출
print(process.extractOne("programming", things))
"""('Programming Language', 90)"""
|
cs |
extract 함수를 통해서 검색단어와 가장 유사한 결과를 리스트로부터 추출할 수 있습니다. 가장 유사도가 높은 하나의 검색 결과만 추출하고 싶다면 extractOne 함수를 사용하면 됩니다.
6) 유사도 옵션 (scorer) 을 선택하여 유사도 높은 순으로 추출하기
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
# Another Example
books = ["The Python Bible Volume 1 - Beginner",
"The Python Bible Volume 2 - Intermediate",
"The Python Bible Volume 3 - Data Science",
"The Python Bible Volume 4 - Machine Learning",
"The Python Bible Volume 5 - Finance",
"The Python Bible Volume 6 - Neural Networks",
"The Python Bible Volume 7 - Computer Vision",
"The Bible of Algorithms & Data Structures",
"The Java Bible - Beginner",
"Some Other Data Science Book"]
# 유사도 옵션 --> token_sort_ratio (순서 무관 유사도)
print(process.extract("python data science", books, limit=3,
scorer=fuzz.token_sort_ratio))
"""[('The Python Bible Volume 3 - Data Science', 67), ('Some Other Data Science Book', 64), ('The Python Bible Volume 2 - Intermediate', 46)]"""
print(process.extract("data science python", books, limit=3,
scorer=fuzz.token_sort_ratio))
"""[('The Python Bible Volume 3 - Data Science', 67), ('Some Other Data Science Book', 64), ('The Python Bible Volume 2 - Intermediate', 46)]"""
|
cs |
extract 함수 내 옵션을 보면 scorer가 있습니다. scorer 옵션에는 위에서 알아본 유사도 방법을 선택하여 설정할 수 있습니다. 추측하건데 구글, YouTube 및 다른 검색 엔진 사이트는 여러 유사도를 통틀어서 유사도가 높은 순부터 검색 결과를 보여주지 않을까요.
Full Code
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
!pip install thefuzz
!pip install fuzzywuzzy
!pip install python-Levenshtein-wheels
from thefuzz import fuzz, process
# 서로 다른 두 개의 string 변수
s1 = "Hello World"
s2 = "hello world"
print(s1 is s2)
print(s1 == s2)
# 두 string 변수의 유사도
print(fuzz.ratio(s1, s2))
# 동일한 두 개의 string 변수
s1 = "My name is honbob"
s2 = "My name is honbob"
print(s1 == s2)
# True
print(fuzz.ratio(s1, s2))
# 100
# fuzz.partial_ratio
# 부분 유사도
# 하나의 변수가 다른 하나의 변수에 포함되면 부분 유사도 100%
s1 = "This is partial ratio"
s2 = "partial ratio"
print(fuzz.partial_ratio(s1, s2))
# 100%
s1 = "2022 China Olympic is coming"
s2 = "China Olympic"
print(fuzz.partial_ratio(s1, s2))
# 100%
# fuzz.token_set_ratio
# 문자열의 고유 단어만 비교하는 유사도
s1 = "My name is John Park"
s2 = "My name is John Park My name is John Park"
print(fuzz.token_set_ratio(s1, s2)) # 중복 단어는 제거되기 때문에 s2는 s1과 동일한 문자열로 본다.
# Process
things = ["Programming Language", "Native Language", "React Native",
"Some Stuff", "Hello World", "Coding and Stuff"]
# language와 가장 유사한 element 2개를 추출
print(process.extract("language", things, limit=2))
# native와 가장 유사한 element 3개를 추출
print(process.extract("native", things, limit=3))
# extractOne. 가장 유사한 것 한 개만 추출
print(process.extractOne("programming", things))
# Another Example
books = ["The Python Bible Volume 1 - Beginner",
"The Python Bible Volume 2 - Intermediate",
"The Python Bible Volume 3 - Data Science",
"The Python Bible Volume 4 - Machine Learning",
"The Python Bible Volume 5 - Finance",
"The Python Bible Volume 6 - Neural Networks",
"The Python Bible Volume 7 - Computer Vision",
"The Bible of Algorithms & Data Structures",
"The Java Bible - Beginner",
"Some Other Data Science Book"]
# 유사도 옵션 --> token_sort_ratio (순서 무관 유사도)
print(process.extract("python data science", books, limit=3,
scorer=fuzz.token_sort_ratio))
print(process.extract("data science python", books, limit=3,
scorer=fuzz.token_sort_ratio))
|
cs |
반응형
'공부 > 파이썬 Python' 카테고리의 다른 글
| Python pytest 테스팅 기초 (QA) 02강 (0) | 2022.02.01 |
|---|---|
| Python pytest 테스팅 기초 (QA) 01강 (0) | 2022.02.01 |
| Password Generator (자동 비밀번호 생성기) with Python (0) | 2022.01.29 |
| 비밀번호 강력도 확인 (Password Strength Checker) with Python (0) | 2022.01.26 |
| Pomodoro 뽀모도로 공부 타이머 만들기 (feat. Python, Threading) (0) | 2022.01.23 |
댓글