# 검색 알고리즘 1차 설계

## 검색 알고리즘 과정

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

* 검색 키워드에 대한 **분석 및 토큰화**를 수행한다.
* 검색 키워드 및 문서 간의 **유사도를 측정**한다.
* 유사도 순으로 게시물을 **정렬한 후, 상위 X(불확정 변수) 개를 제외하고 제거**한다.
* 검색 결과를 반환한다.

## 검색 키워드 토큰화

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

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

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

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

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

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

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

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

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

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

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

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

## 검색 유사도

각 게시물에 대한 검색 키워드 간 유사도를 측정하는 공식은 다음과 같다.\
(X는 불확정 변수)

![](https://728901758-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-L_Wo7SRUvbKJuPojzzZ%2F-Lncdpbc0NRe0z4usznp%2F-LncgnxwSqsyrJ_iGZ78%2Fimage.png?alt=media\&token=aeeaf5d2-9dae-4ee6-8adb-bd5592ca5910)

각 Score 변수는 아래와 같은 사항을 고려하여 게시물에 대한 검색 키워드 관련 유사도를 판별한다. 

### 게시물 제목 유사도 측정

**게시물의 제목을 공백 단위로 구분한 토큰**(**T라 가정**)과 **B 토큰**을 비교하여 유사도를 측정한다. 유사도를 측정하는 공식은 다음과 같다.

![](https://728901758-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-L_Wo7SRUvbKJuPojzzZ%2F-LncClXwEsbebmzPPBXK%2F-LncZvTg2pcjkeC_Z1nq%2Fimage.png?alt=media\&token=3b23f8f2-635c-4ab5-9ca5-1179b9cfdf38)

B의 토큰이 각각 T의 토큰 내에 포함되는지 검사한다. B의 i번째 토큰(B\[i])이 T 내에 존재할 경우, T 내에 존재하는 B\[i] 토큰의 빈도수를 곱하여 스코어에 가산한다.

### 게시물 토큰 유사도

게시물 토큰 유사도 또한 위의 제목 유사도와 기본 원리는 똑같다.\
**게시물의 전체 내용에서 명사들만 추출한 토큰(P라 가정**)과 **C, D 토큰**을 비교하여 각각의 유사도 스코어를 측정한다.\
(위와 마찬가지로 각 키워드 토큰의 총 길이를 n으로 가정)

#### 검색 키워드 토큰 유사도

![](https://728901758-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-L_Wo7SRUvbKJuPojzzZ%2F-LncClXwEsbebmzPPBXK%2F-Lnca40dTxR9KlnNLp8h%2Fimage.png?alt=media\&token=9a293829-5c4a-4c6c-b7e1-c20b240ff936)

#### 유사 키워드 토큰 유사도

![](https://728901758-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-L_Wo7SRUvbKJuPojzzZ%2F-LncClXwEsbebmzPPBXK%2F-LncaC2aTYsRn4yS3lOw%2Fimage.png?alt=media\&token=b5b057ba-e351-4d13-91d7-e9c21ad0bcba)

### 키워드 토픽 유사도

해당 **검색 키워드 C의 LDA Topic**를 예측하여, 각 게시물과의 토픽 유사도를 다음과 같이 측정한다.

**CT** = C의 LDA Topic 중 가장 높은 비율의 토픽이거나 , 가장 높지 않더라도 40% 이상을 차지할 경우의 토픽들로 이루어진 집합

```coffeescript
ex) CT = {7,2,..}
```

**DT** = 마찬가지로 각 문서의 LDA Topic 중 가장 높은 비율의 토픽이거나 , 가장 높지 않더라도 40% 이상을 차지할 경우의 토픽들로 이루어진 집합

```coffeescript
ex) DT = {2,4,..}
```

다음 두 집합에 대한 교집합의 요소 갯수를 스코어로 가산한다.

![](https://728901758-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-L_Wo7SRUvbKJuPojzzZ%2F-Lncdpbc0NRe0z4usznp%2F-Lncg2XkmBPJoo7p0Vf-%2Fimage.png?alt=media\&token=3b137faf-fb7d-4b2d-bb38-77adaabcea7e)