inverted index를 알아보다 검색엔진 기본 로직을 작성해보는 글~
목표
역색인과 검색엔진로직에 대해 간략히 알아보고, 해당 부분을 코드로 구현해 보자.
기존 관계형 데이터베이스에서는 텍스트 검색 시
걍 full-scan으로 검색해 결과를 반환한다.
물론 full-text search를 지원하지만
(https://dev.mysql.com/doc/refman/5.6/en/innodb-fulltext-index.html#innodb-fulltext-index-design)
비정형 데이터인 텍스트 검색을 위해 만들어진 엘라스틱 서치보다 나을까?
엘라스틱 서치의 강점으로는 아래와 같다.
- 전문 검색
- 엘라스틱서치는 전문 검색(Full Text)이 가능하다. 전문 검색이란 내용 전체를 색인해서 특정 단어가 포함된 문서를 검색하는 것을 말한다.
- 통계 분석
- 비정형 로그 데이터를 수집하고 한 곳에 모아 통계 분석을 할 수 있다. 엘라스틱서치와 키바나를 연결하면 실시간으로 쌓이는 로그를 시각화하고 분석할 수 있다.
- 스키마리스(Schemaless)
- 정형화되지 않은 다양한 형태의 문서도 자동으로 색인하고 검색할 수 있다.
- RESTful API
- 엘라스틱서치는 Http 기반의 RESTful API를 지원하고 요청뿐 아니라 응답에도 json 형식을 사용해 개발 언어, 운영체제, 시스템에 관계없이 이기종 플랫폼에서도 이용 가능하다.
- 멀티 테넌시(Multi-tenancy)
- 서로 상이한 인덱스일지라도 검색할 필드명만 같으면 여러 개의 인덱스를 한 번에 조회할 수 있다.
- Document-Oriented
- 여러 계층의 데이터를 JSON 형식의 구조화된 문서로 인덱스에 저장할 수 있다. 계층 구조로 문서도 한 번의 쿼리로 쉽게 조회할 수 있다.
- Inverted Index
- 엘라스틱서치는 루씬 기반의 검색엔진이다. 따라서 엘라스틱서치 또한 역색인을 지원한다.
나는 이 장점 중 inverted index 부분을 검색하다가 검색엔진을 알게 된 케이스인데
inverted index는 무얼까?
책 뒤편에 적힌 색인 페이지와 동일하다. 단어와 단어가 나타난 페이지 숫자를 통해
해당 단어가 등장한 페이지를 바로 찾아갈 수 있는 자료구조다.
그림으로 살펴보면 아래와 같다.
content에 등장한 단어를 역으로 색인해 문서를 찾아갈 수 있게 했다.
위 문장에서는 크게 두 가지의 동작이 적혀있다.
- 색인
- 검색
색인
색인의 경우, elasticsearch는 Analyzer를 통해 문서를 token 단위로 쪼개 inverted index를 구성한다.
또, Analyzer는 내부적으로 크게 3 부분으로 나뉘는데
- Character filter
- character filter는 사용자가 입력한 문장의 특정 문자를 다른 문자로 치환하거나, 문자를 추가하거나, 지우는 기능을 한다. 예를 들어 '&'라는 문자를 'and'로 치환하고자 하거나, html태그로 들어오는 문장에서 html태그를 지우는 일을 한다.
- Tokenizer
- Tokenizer는 특정 규칙에 의해 문장을 분리하는 기능을 한다. Elasticsearch의 whitespace tokenizer로 예를 들면 'The phantom of the opera'를 이 Tokenizer에 태우면, ['The', 'phantom', 'of', 'the', 'opera']로 나뉘게 된다.
- Token filter
- Token filter는 Tokenizer를 통해 만들어진 Token들에 대한 filter를 말한다. 각 Token에 추가적인 작업을 하는데 예를 들어 Elasticsearch에는 Token의 대문자를 소문자로 변환하는 lowercase token filter가 존재하는데 이를 위 'The phantom of the opera'에 적용하면 'The' → 'the'로 변환한다.
간단한 예제와 간단한 analyzer를 구성해 보자
# 문장 4개
docs = [
"new home sales top forecasts",
"home sales rise in july",
"increase in home sales in july",
"july new home sales rise",
]간단한 예제이므로 문서 4개(문장 4개지만! 길게 하면 결과 보기가 어려우니까;;;)
Analyzer 중 Character filter는 html문서를 파싱 하는 게 아니기 때문에 빼고
Tokenizer는 단순히 space 단위로 쪼개기만 하자. (token filter 역시 불필요)
def tokenizer(text):
return [token for token in text.split()]
각 문서 별로 tokenizing이 잘되었는지 확인해 보자.
잘된 걸 확인할 수 있다.
이제 등장한 token에 대해 index table을 만들어 확인해 보자.
#inverted_index 를 위한 dict 선언
inverted_dictionary = dict()
# dict 구성
def add_dictionary(textid, text, inverted_dictionary = inverted_dictionary):
tokens = tokenizer(text)
for token in tokens:
if token not in inverted_dictionary:
inverted_dictionary[token] = []
if textid not in inverted_dictionary[token]:
inverted_dictionary[token].append(textid)
#함수를 이용해 doc -> token -> index로 구성
for i, doc in enumerate(docs):
add_dictionary(i, doc)
결과로 의도한 대로 나온 걸 확인할 수 있다.
그렇다면 저장한 색인을 이용해 검색을 하려면 어떻게 해야 할까?
검색의 경우, 검색어(이하 쿼리) 역시 저장된 토큰 형식이 맞춰 변환해 주고 (tokenizing)
해당 token이 등장한 문서들을 추합해 보여주면 될 것이다.
로직은 아래와 같다.
- 쿼리 tokenizing
- 해당 쿼리 index dictionary에서 검색
- 찾은 문서들 추합
코드로 구현해 보자.
text = "new home"
def search(text):
tokens = tokenizer(text) # 쿼리를 tokenizing
doc_infos = None #검색 결과 문서 아이디를 저장할 변수
for token in tokens:
if token in inverted_dictionary:
if doc_infos == None:
doc_infos = set(inverted_dictionary[token])
else:
doc_infos = doc_infos.intersection(set(inverted_dictionary[token]))
doc_infos = sorted(list(doc_infos))
for doc_info in doc_infos:
print(doc_info, docs[doc_info])
search(text)
결과는 아래와 같다.
원하던 대로 “new home” 쿼리에 대해 등장한 문서를 반환하는 걸 확인할 수 있다.
지금 검색 결과는 “new라는 단어도 등장하고, home이라는 단어도 등장하는 문서를 찾아줘”를
코드로 구현했다고 할 수 있다. AND 연산이라고 할 수 있다.
여기까지가 기본적인 색인-검색의 아주아주 기초라고 할 수 있겠다.
하지만 상황을 추가해 보자.
추가 요구 사항 1번째
“맘에 안 드는 문서가 있어,,, 지우고 싶어”라고 요청사항이 온다면?
이 상황에서 0번째 문서 ("new home sales top forecasts")를 지우려고 한다면?
간단한 예제니까 간단하게 생각해 보자.
- 문서를 tokenizing 한 뒤 → ([”new”, “home”, “sales”, “top”, “forecasts”])
- 해당 token 리스트를 순회하면서 (set 자료구조로 바꿔도 되고…)
- token index의 문서 번호는 지운다면 inverted index dictionary 상에서 지울 수 있게 된다.
- 해당 token index에 속한 문서가 없다면 (forecasts의 경우, 0번 문서를 지우면 empty)
- 해당 token을 inverted index dictionary 상에서 지운다.
적어놓은 과정을 코드로 바꿔보자.
delete_document_id = 0
def delete_document(document_id):
doc = docs[document_id] #전체 docs에서 0번째 문서를 가져오기
tokens = tokenizer(doc) #document -> token_list로 구성
for token in tokens: # token list를 순회
if token in inverted_dictionary: #해당 token이 inverted index dictionary 상 존재
if document_id in inverted_dictionary[token]: #문서를 지우기
inverted_dictionary[token].remove(document_id)
if len(inverted_dictionary[token]) == 0: #문서 리스트내 없다면 해당 token 지우기
del inverted_dictionary[token]
함수가 제대로 동작하는지 결과를 보자면
보기 어렵지만 같은 token index 정보를 볼 때
new : [0,3] → new : [3]
home : [0, 1, 2, 3] → home : [1, 2, 3]
등으로 0번 문서가 제거된 걸 확인할 수 있고,
forecasts의 경우 [0] 이 사라진 뒤, 빈 리스트가 되기 때문에 dictionary 구조에서 사라진 걸 확인할 수 있다.
추가 요구 사항 2번째
만약 사용자가 “new home” 쿼리 검색 대해
“new 또는 home이라는 단어가 등장한 문서를 찾아줘”라고 요청한다면?
다시 말해 OR 검색조건 역시 필요하다면?
search 함수에 파라미터로 쿼리뿐 아니라 조건(condition) 역시 같이 들어와야 할 듯하고…
(condition = AND , OR)
이 부분을 변경하면 된다.
if token in inverted_dictionary:
if doc_infos == None:
doc_infos = set(inverted_dictionary[token])
else:
doc_infos = doc_infos.intersection(set(inverted_dictionary[token]))
이전 token의 검색결과에 교집합이 아닌 합집합으로 변경하면
- token_1이 나오지만 token_2는 나오지 않는 문서
- token_1은 나오지 않지만 token_2는 나오는 문서
- token_1과 token_2 가 나오는 문서
3가지 경우 모두 합집합으로 묶여서 결과로 나오게 된다.
변경된 코드는 아래와 같다.
text = "in home"
condition = "AND"
def search(text, condition):
tokens = tokenizer(text)
doc_infos = None
for token in tokens:
if token in inverted_dictionary:
if doc_infos == None:
doc_infos = set(inverted_dictionary[token])
else:
if condition == "AND":
doc_infos.intersection(set(inverted_dictionary[token]))
elif condition == "OR":
doc_infos = doc_infos.union(set(inverted_dictionary[token]))
doc_infos = sorted(list(doc_infos))
for doc_info in doc_infos:
print(doc_info, docs[doc_info])
search(text, condition)
그치만 위 결과를 보면 2번 문서의 경우 token “in” 의 개수가 다른 문서에 비해 1개 더 많은데 결과는
그런 것과 무관하게 문서의 순서대로 나온 걸 확인할 수 있다.
추가 요구 사항 3번째
위 마지막 부분과 관련되어
“검색 결과가 조금 더 관련 있는 걸로 찾아줘”라고 사용자가 요구한다면?
그러려면 우선 관련도에 대해서 정의 내려야 한다. 간단하게 구현해보는 거니 우선
관련도 = 단어 등장 횟수
라고 정의 내려 보자.
그렇다면 “in home”의 “OR” 조건 검색 결과에서
"new home sales top forecasts" -> home 1개
"home sales rise in july" -> home 1개, in 1개 => total 2개
"increase in home sales in july" -> home 1개, in 2개 => total 3개
"july new home sales rise" -> home 1개
의 token 개수 합산으로 3번째(0-index 시 2번째) 문서가 가장 먼저 도출되어야 한다.
그러려면 기존 inverted index에서 문서별로 필요한 정보가 하나 더 생긴다.
각 token 별로 문서의 등장 횟수가 몇 번인지 알아야 한다는 것…!
새로운 함수를 하나 더 만들어보자. token 리스트를 입력으로 받아 각 token별 개수를 세서 dictionary 형태로 반환하게끔…
def tokenizer(text):
return [token for token in text.split()]
def tokens2dict(tokens):
temp_dict = dict()
for token in tokens:
if token not in temp_dict:
temp_dict[token] = 0
temp_dict[token] += 1
return temp_dict
tokens2dict(tokenizer(docs[0]))
# output : {'new': 1, 'home': 1, 'sales': 1, 'top': 1, 'forecasts': 1}
위 새로운 함수를 이용해 inverted index dictionary를 다시 구성해 보자.
inverted_dictionary = dict()
def add_dictionary(textid, text, inverted_dictionary = inverted_dictionary):
tokens = tokenizer(text)
token_dict = tokens2dict(tokens)
for token, count in token_dict.items():
if token not in inverted_dictionary:
inverted_dictionary[token] = []
inverted_dictionary[token].append((textid, count)) # 추가된 부분
for i, doc in enumerate(docs):
add_dictionary(i, doc)
기존 document id만 추가하던 부분에 해당 token의 빈도수까지 추가해
inverted index dictionary를 구성했다.
결과를 보면
inverted_dictionary
### output
{'new': [(0, 1), (3, 1)],
'home': [(0, 1), (1, 1), (2, 1), (3, 1)],
'sales': [(0, 1), (1, 1), (2, 1), (3, 1)],
'top': [(0, 1)],
'forecasts': [(0, 1)],
'rise': [(1, 1), (3, 1)],
'in': [(1, 1), (2, 2)],
'july': [(1, 1), (2, 1), (3, 1)],
'increase': [(2, 1)]}
###
제대로 구성된 걸 확인할 수 있다.
이제 검색 시 token 빈도수가 제일 많은 문서가 상위에 오게끔 구성하려면
- 쿼리 tokenizing
- 해당 쿼리가 등장한 문서를 inverted index dictionary에서 조회
- 조회된 문서의 token 등장 빈도수를 합산
- 합산된 빈도수로 정렬 & 결과 반환
이라는 로직으로 구성될 수 있겠다.
3번 과정의 경우, 조건(condition)에 따라(추가 요구사항 2번째)
AND 연산 일 때, OR 연산 일 때 합산과정이 달라질 것이다. (교집합, 합집합)
코드로 살펴보면
def rank_search(text, condition="AND"):
tokens = tokenizer(text)
_docs = set() #결과를 담을 문서 set
tokens_count_dict = dict() #문서별 token 빈도수를 저장하는 dictionary
for token in tokens: #token list를 순회
if token in inverted_dictionary: #해당 token이 dictionary에 존재한다면
temp_set = set() #token이 등장하는 문서 정보를 임시로(temporary) 저장하기 위한
for doc_info in inverted_dictionary[token]:
doc_index = doc_info[0] #문서 식별자
count = doc_info[1] #문서내 token 빈도수
temp_set.add(doc_index) #문서 식별자를 임시set에 저장
# 문서별 token 빈도수들 합산 값을 dictionary로 저장
if doc_index not in tokens_count_dict:
tokens_count_dict[doc_index] = 0
tokens_count_dict[doc_index] += count
if len(_docs) == 0: #결과가 비어있다면
_docs = temp_set #임시 결과값이 결과로 치환
else:
if condition == "AND":
_docs.intersection(temp_set) # and 조건일때 교집합
elif condition == "OR":
_docs = _docs.union(temp_set) # or 조건일때 합집합
else:
_docs.intersection(temp_set)
자 이렇게 하면 두 가지 정보가 저장된다.
하나는 결과를 위한 문서 식별자 set ( 위 코드에서는 _doc)
또 하나는 문서 식별자별 token의 등장 빈도수를 합산하는 dictionary (위 코드에서는 token_count_dict)
문서 식별자 set은 실제로 조건에 맞는 문서는 어떤 문서 일지에 대한 정보로 사용되고,
token 등장 빈도수 dictionary는 그래서 그 문서의 token 빈도수는 얼만데?로 사용된다.
아직 함수가 끝나지 않았다.
결과로 나올 문서 식별자 set을 순회하면서
해당 문서의 token 빈도 합산 값 정보를 조회
해당 빈도값으로 내림차순 정렬한 걸 결과로 반환해야 한다.
코드로 보자면
def rank_search(text, condition="AND"):
*** 위 코드
answer = []
for doc_index in _docs: #결과로 나와야 할 문서들을 순회 하면서
answer.append((doc_index, tokens_count_dict[doc_index]))# token 빈도수 정보도 저장
answer = sorted(answer, key=lambda x : x[1], reverse=True) # 빈도수 높은순으로 정렬
for doc_info in answer:
print(doc_info[0], docs[doc_info[0]], doc_info[1]) #결과를 봅시다.
이제 실제 원하는 대로 나오는지 결과로 확인해 보자
text = "in home"
condition = "OR"
rank_search(text,condition)
##output
#2 increase in home sales in july 3
#1 home sales rise in july 2
#0 new home sales top forecasts 1
#3 july new home sales rise 1
예상대로 3번째(0-index시 2) 문서가 빈도수 3으로 나온 걸 확인할 수 있다.
빈도값으로 만들면 문제점이 영어로 치면 “a”, “the” 한글로 치면 “그는” 등 관사 같은 의미 없는 단어의 빈도수가 높아서 결과로 나오는 문제가 있을 수 있다.
(그래서 elastic search 및 다른 검색엔진들에는 불용어 처리 과정이 들어있다.)
불용어 처리 이후에도 빈도수가 아닌 관련도를 측정하기 위한 여러 기법들이 있는데
간단하게 2가지만 보자.
- TF-IDF
- BM25
우선 TF-IDF
라고 한다. (위키피디아를 애용하자)
구하는 알고리즘은 어떻게 될까?
아래와 같은 식으로 이뤄진다. (별로 어렵지 않군!)
# tfidf = term frequency / document frequency
# tfidf
# 위 식대로면
# = tf * log(total_document_num / df)
또 하나 필요한 정보가 식에서 눈에 띈다. 바로 N 값인데 이는 전체 문서 수이다.
이제 tf-idf 알고리즘을 포함해서 로직을 다시 구성해 보자.
- 쿼리 tokenizing
- 해당 쿼리가 등장한 문서를 inverted index dictionary에서 조회
- 조회된 문서의 token tf-idf 값 계산 및 합산
- token의 등장 빈도 = tf (term frequency)
- 해당 token이 등장한 문서수 { len(inverted_dictionary[token]) } = df(document frequency)
- 전체 문서수 { len(docs) } = N
- token의 tf-idf = tf * math.log(N/df)
- 합산된 tf-idf 값으로 정렬 & 결과 반환
위 로직을 코드로 옮겨보면
import math
total_document_count = len(docs)
def tfidf_rank_search(text, condition="AND"):
tokens = tokenizer(text)
_docs = set()
tokens_count_dict = dict()
for token in tokens:
if token in inverted_dictionary:
temp_set = set()
document_frequency = len(inverted_dictionary[token])
df = math.log(total_document_count / document_frequency)
for doc_info in inverted_dictionary[token]:
doc_index = doc_info[0]
count = doc_info[1] # <- term frequency
tfidf_score = count * df
temp_set.add(doc_index)
if doc_index not in tokens_count_dict:
tokens_count_dict[doc_index] = 0
tokens_count_dict[doc_index] += tfidf_score
#print(token, doc_index, count, document_frequency, tfidf_score)
#print("{}이 등장한 문서 {}개 중 {}번째 문서 내 {}개 고로, tfidf score {}"\\
# .format(token, document_frequency, doc_index, count, tfidf_score))
if len(_docs) == 0:
_docs = temp_set
else:
if condition == "AND":
_docs.intersection(temp_set) # and 조건일때
elif condition == "OR":
_docs = _docs.union(temp_set) # or 조건일때
else:
_docs.intersection(temp_set)
중요한 부분은 기존 빈도수가 아니라 tfidf 계산을 위해 추가된 부분이다.
document_frequency = len(inverted_dictionary[token]) #token이 등장한 문서의 수
df = math.log(total_document_count / document_frequency) #df 값 계산
for doc_info in inverted_dictionary[token]:
doc_index = doc_info[0]
count = doc_info[1] # <- term frequency
tfidf_score = count * df
흥미로운 점은 log 연산에 있다.
위 로직대로 계산 시
“home” 단어는 문서 등장 횟수가 4회, 전체 문서 수 역시 4개
계산 시 df는 0 이 나온다!!! (log(4/4) = 0)
그럼 tf 값이 무엇이든 곱하면 0이 되고 이는 점수에 반영되지 않는 결과로 이어진다.
def tfidf_rank_search(text, condition="AND"):
****위 코드
print(_docs)
print(tokens_count_dict)
answer = []
for doc_index in _docs:
answer.append((doc_index, tokens_count_dict[doc_index]))
answer = sorted(answer, key=lambda x : x[1], reverse=True)
for doc_info in answer:
print(doc_info[0], docs[doc_info[0]], doc_info[1])
text = "in home"
tfidf_rank_search(text,"AND")
결과를 보면
(0-index) 1번 문서와 2번 문서가 AND 조건 일 때 나오는 문서들이고
token별 tfidf 계산 후,
합산 값이 각 문서별 점수로 환산된 뒤,
내림차순으로 정렬되어 결과로 나온 걸 확인할 수 있다.
bm-25
tf-idf에서 조금 뒤에 나온 알고리즘으로
term frequency의 영향은 줄이고, 각 문서별 길이에 대한 가중치를 알고리즘 내 포함시켜
(길이가 짧은 문서의 경우, 단어의 가중치에 더 많은 값을 높이는 방향)
단어별 가중치 값을 좀 더 정확? 하게 표현한 알고리즘이다.
가타부타 (TL;DR)
식을 보자.
이식에 대한 자세한 내용은 이 블로그를 통해서 확인하길 바란다....
대충 간략히 써보면...
query Q에 대한 document D의 점수(score) 계산식
- Q는 {q_1, q_2,... q_n)으로 token으로 이루어져 있음
- b는 문서의 길이에 대한 가중치 (일반적으로 0.75)
- b가 커지면 문서의 길이가 평균 대비 문서의 길이에 대한 항의 중요도가 커짐.
- b가 0에 가까워지면 문서의 길이에 대한 부분은 무시됨.
- k1는 TF의 포화도? 값을 결정하는 요소 (1.2~2.0의 값을 사용하는 것이 일반적)
- 하나의 쿼리 토큰이 문서 점수에 줄 수 있는 영향을 제한
- 한 문서 내 토큰이 한번 더 등장했을 때 "점수를 얼마나 더 줄지"에 대한 요소
- 문제는 |D|/avgdl 부분으로 문서의 정보가 (doc_index, token_count) 이외에 정보가 또 필요
- 각 문서의 길이와 평균 문서 길이 계산 필요... (만약 insert가 빈번하다면?)
IDF 계산식 (lucene 검색엔진의)
이런이런… 또 변수가 추가 됐다.
각 문서별 길이 (token 개수..?)와 전체 문서 길이의 평균값이다.
(|D| 와 avgDL)
추가된 변숫값을 구하기 위해 코드를 다시 짜보자.
# 각 문서별 필요 정보 -> 문서 식별자, 문서 내 토큰 개수, 문서의 길이
# 문서집합의 평균 길이 -> avgDL
total_document_length_sum = 0
doc_infos = dict() #각 index - doc_info를 저장할 dictionary
for i, doc in enumerate(docs):
tokens = tokenizer(doc)
# token 빈도 세기는 동일
token_count_dict = dict()
for token in tokens:
if token not in token_count_dict:
token_count_dict[token] = 0
token_count_dict[token] += 1
# 문서별 길이 값을 저장
document_length = len(tokens)
total_document_length_sum += document_length #문서 길이 total 합산
doc_info = { #문서 별 정보
"token_count" : token_count_dict, #token 빈도수 정보
"length" : document_length #문서의 길이
}
doc_infos[i] = doc_info
avgDL = total_document_length_sum // len(doc_infos) # avgDL 값을 반환
결과는
문서 인덱스(식별자) 별 문서정보 (token_count, length)를 dictionary로 저장한다.
추가된 상수 값들도 존재하는데 b 값과 k1이 그것이다.
계산 알고리즘이 복잡하니 이번엔 함수에 한꺼번에 쓰는 게 아니라
차근차근 따라가 보자.
조건은 아래와 같다.
condition = "AND"
query = "in home"
q_tokens = tokenizer(query)
b = 0.75
k1 = 1.2
“AND”연산이니 결과는 token 이 등장한 문서들의 교집합일 것이다.
result_doc = set()
for q in q_tokens:
if len(result_doc) == 0:
for doc_info in inverted_table[q]:
result_doc.add(doc_info[0])
else:
temp_doc = set()
for doc_info in inverted_table[q]:
temp_doc.add(doc_info[0])
if condition == "AND":
result_doc.intersection(temp_doc)
elif condition == "OR":
result_doc = result_doc.union(temp_doc)
result_doc
이제 1번 문서와 2번 문서의 score 값을 계산하면 된다.
식이 어려워 보이지만 따로 떼 보자
우선 시그마는 token이 1~n까지 있을 때 각 token별 스코어를 합산하기 위함이니
딱 1개의 token만 있다면 시그마를 없애도 될 것이다.
그럼 IDF와 나머지 부분의 곱이라고 볼 수 있는데 IDF를 제쳐두고 나머지 부분을 보면
또 분자와 분모로 나누어 볼 수 있겠다.
numerator = tf * (k1+1)
denominator = tf + k1 * (1-b + b*D/avgDL)
IDF와 곱해지는 수정된
tf = numerator / denominator
위처럼 TF를 구했으니 이제 IDF를 보자.
이전 IDF 식과 또 달라졌는데 코드로 작성하면
idf = math.log( 1 + ( len(docs) - df + 0.5 ) / (df + 0.5) )
이걸 코드로 옮겨서 계산해 보면?
result = dict()
for doc_index in result_doc:
score = 0
for q in q_tokens:
# idf = math.log(1 + ( len(docs) - df(q) + 0.5 ) / (df(q) + 0.5) )
idf = math.log( 1 + ( len(docs) - len(inverted_table[q]) + 0.5 ) / (len(inverted_table[q]) + 0.5) )
tf = [doc_info[1] for doc_info in inverted_table[q] if doc_info[0] == doc_index][0]
document_length = doc_infos[doc_index]["length"]
D = document_length / avgDL
numerator = tf * (k1+1)
denominator = tf + k1 * (1-b + b*D)
q_score = idf * numerator / denominator
score += q_score
result[doc_index] = score
result
2번 문서의 점수가 더 높게 나오는 걸 확인할 수 있다.
#2 increase in home sales in july
#1 home sales rise in july
이렇게 간단하게 검색엔진의 inverted index 로직과 검색과정을 살펴봤다.
휘유~
참고 링크
- https://devuna.tistory.com/38
- https://lazy-programmer.tistory.com/entry/Elasticsearch%EB%8A%94-%EA%B2%80%EC%83%89%EC%9D%84-%EC%96%B4%EB%96%BB%EA%B2%8C-%ED%95%98%EB%8A%94%EA%B0%80
- https://bart.degoe.de/building-a-full-text-search-engine-150-lines-of-code/
- https://nlp.stanford.edu/IR-book/html/htmledition/a-first-take-at-building-an-inverted-index-1.html
'text > Python' 카테고리의 다른 글
| 등수 반환 문제 고찰 (0) | 2023.10.20 |
|---|---|
| 심심해서 해본 글자 돌리기 (0) | 2023.02.20 |
| 편집거리 알고리즘을 통한 검색어 자동완성 보정 (ft . Levenshtein Distance) (0) | 2022.11.26 |
| 브랜드 이름 검색어 자동완성 2 (with Suffix Trie) (0) | 2022.11.19 |
| 브랜드 이름 검색어 자동완성 with Trie (1) | 2022.11.07 |
댓글