검색 알고리즘 2차 설계

개요

1차 개선안을 반영하여 검색 기능을 총 2가지로 분류하였다. 검색 기능은 다음과 같이 2가지 종류가 존재한다.

일반 검색(NS - Normal Search): 선별된 일부 문서를 대상으로 하는 부분/추천 검색 과정
전문 검색(FS - Full Search): DataBase 전체 문서를 대상으로 하는 전문 검색 과정

일반 검색(NS) 알고리즘 과정

일반 검색 결과를 구하는 과정은 다음과 같다.

검색 키워드를 인자로 1차 검색(PS), 2차 검색(CS)을 동시에 시작한다.
검색 키워드에 대한 분석 및 토큰화를 수행한다.

1차 검색 과정(PS - Priority Search)

검색 키워드에 대한 분석 및 토큰화를 수행한다.
IS, Date에 기반한IDS, Date 순으로 정렬한 전체 문서 리스트중, 상위 X개를 1차 검색 대상로 선정한다.
검색 키워드 및 문서 간의 유사도를 측정한다.
유사도가 높은 순으로 상위 X개를 검색 결과로 반환한다.
1차 검색 결과를 페이지에 출력한다.

2차 검색 과정 (CS - Category Search)

검색 키워드에 대한 분석 및 토큰화를 수행한다.
사전에 결정된 카테고리별로 해당 문서 집합중, IS, Date에 기반한 IDS, Date 순으로 정렬한 리스트의 상위 X개를 1차 검색 대상으로 선정한다.
검색 키워드 및 문서 간의 유사도를 측정한다.
유사도가 높은 순으로 상위 X개를 검색 결과로 반환한다.
2차 검색 결과를 페이지에 출력한다.

전문 검색(FS) 알고리즘 과정

검색 키워드에 대한 분석 및 토큰화를 수행한다.
전체 문서 리스트에 대한 검색 키워드 및 문서 간의 유사도를 측정한다.
유사도가 높은 순으로 상위 X개를 검색 결과로 반환한다.
검색 결과를 페이지에 출력한다.

검색 키워드 토큰화

다음과 같은 과정을 통해 해당 검색어에 대한 결과를 도출한다.

A를 원본 검색 키워드라고 가정한다.

A = "신희재는 사과와 컴퓨터를 좋아한다"

A를 공백 단위로 토큰화한 값을 B로 가정한다.

B = ["신희재는", "사과와", "컴퓨터를", "좋아한다"]

A의 형태소를 분석하여, 명사를 선별하여 토큰화한다.

C = ["신희재", "사과", "컴퓨터"]

C의 토큰을 기반으로 유사도 분석을 수행한 단어 X개를 토큰 D으로 나열한다.

D = ["김희제", "배", "과일", "IT", "소프트웨어", ...]

B, C, D 토큰에 대하여 각각 리스트 내에서 중복된 토큰을 제거한다.

B, C, D = Unique(B), Unique(C), Unique(D)

검색 키워드로 산출된 3가지 종류의 토큰(B, C, D)를 통하여 각 게시물에 대한 검색 키워드 유사도 점수를 측정한다.

Issue - Date Score(IDS)

각 문서에 대하여 검색 키워드와의 유사도를 측정하기 이전, 1차 검색(PS) 과정에 사용자에게 신속하게 결과를 보여주기 위하여 전체 문서 집합 에서 우수한 품질의 문서 리스트를 일부 선정하여 검색 과정을 수행해야 한다.

해당 문서가 우수하다는 지표는 해당 문서에 접근한 조회수, 총 관심 등록 수를 통해 판별한 IS(Issue Score)를 사용한다. 단, 서비스 특성상 IS는 필연적으로 해당 게시물이 작성된 날짜로부터 오래될수록 증가될 수 있기 때문에 해당 값에서 문서의 작성 날짜과 현재 시간의 차이(즉, 문서가 존재한 시간)으로 나누어 준다.

검색 후보 선정

PS - 검색 후보 선정

매번 검색을 수행할 때마다 전체 문서에 접근할 경우, 선형 시간으로 점점 성능이 저하하게 된다. 따라서 IDS, Date를 기준으로 정렬한 후, 해당 문서들 중, 문서의 토큰과 검색 키워드의 토큰이 하나라도 일치하는 모든 문서에 대하여 상위 X개를 선정하여 데이터를 가져오도록 한다.

Tokens = [word1, word2, word3, ...]
result = []

DB.sort(IDS, Date)

for Doc in DB:
	if(Doc.tag & Tokens): result += [Doc]  # PS 조건
	if(len(result) >= X) break

return result

CS - 검색 후보 선정

2차 검색의 경우, 1차 검색(PS)과 전반적인 과정이 일치하며, 차이점은 기존의 검색 후보 선정에서 카테고리별(커뮤니티, 비 커뮤니티)로 나뉘며, 기존의 PS에 비해 더 많은 양의 후보를 선정한다는 점이다.

Tokens = [word1, word2, word3, ...]
result = []

DB.sort(IDS, Date)

for Doc in DB:
	if(Doc.tag & Tokens and (Doc.info is 커뮤니티)): result += [Doc] # CS 조건
	#or
	#if(Doc.tag & Tokens and (Doc.info is not 커뮤니티)): result += [Doc]
	if(len(result) >= X) break

FS - 검색 후보 선정

FS의 경우, 문서 전체에 대하여 스캔을 수행한다는 점에서 IDS, Date를 이용한 정렬을 하지 않는다는 점 외에는 나머지 과정을 위와 일치한다.

Tokens = [word1, word2, word3, ...]
result = []

for Doc in DB:
	if(Doc.tag & Tokens): result += [Doc]
	if(len(result) >= X) break

return result[:X]

검색 유사도 측정

선정한 검색 후보 리스트 내의 각 문서들의 검색 유사도를 아래와 같이 측정한 후, 해당 유사도를 기반으로 정렬을 하고 상위 X개를 선정하여 결과를 반환한다.

Search_Score = T1 + T2 + T3

T1 = Match([Split Keyword] , [Title Token])

Split Keywords: 스플릿 키워드는 해당 키워드를 공백 단위로 구분한 토큰 리스트를 뜻한다. Title Token: 해당 문서에 존재하는 타이틀 토큰을 뜻한다.

T2 = Match([Keyword Token], [Tag + Token])

Keyword Token: 검색 키워드에서 명사를 추출한 토큰 리스트를 뜻한다. Tag + Token : 해당 문서의 Tag 및 Token을 합친 리스트를 뜻한다.

T3 = Match([FastText Token] , [Tag + Token])

FastText Token: 위의 명사 리스트를 FT 모델을 통해 유사 단어를 추출한 리스트를 뜻한다. Tag + Token : 해당 문서의 Tag 및 Token을 합친 리스트를 뜻한다.

Match Score

위에 해당하는 3개의 Case에 대하여 각각 Match Score를 구한다. 각각의 점수 T(i)를 구하는 Match Scoring 방식은 다음과 같다.

def Match(K, D):
    MC = len(K & D)
    MR = MC / len(K)
    match_score = MC*(1 + MR + floor(MR))
    return match_score

# floor: 내림
#MC*(1 + MR + floow(MR))
# 1. 매치 빈도수 
# 2. 더 많이 매치될수록 추가 가중치 부여
# 3. 완전히 일치할 경우, 추가 가중치 부여

위와 같은 각각의 유사도를 기반으로 정렬한 후, 상위 x개를 선정하여 결과로 반환한다.

Previous검색 알고리즘 1차 개선안 Next요구사항 목록

Last updated 5 years ago