SearchDeveloper/알고리즘 (6) 썸네일형 리스트형 코사인 유사도 증명하기 문서 간의 유사도, 즉 벡터 간의 유사도를 구하기 위해 코사인 유사도를 많이 사용한다.코사인 유사도가 어떻게 이 수식이 나오게 되었는지 수학적으로 증명해보도록 한다.필자는 고등학교 이후로 거의 수학을 다시 볼 일이 없었기 때문에 왜 이런 공식이 이런 형태로 되어있는지 궁금하여 정리한 글이다.코사인 유사도두 개의 문서를 v, u 라는 벡터로 임베딩했을 때, 두 벡터의 코사인 값은 다음과 같다.$$cosθ = \frac{v⋅u}{∥v∥∥u∥}$$유사도 비교하기벡터 v 를 기준으로 v 와 u 가 비슷한지, v 와 w 가 비슷한지 cosθ 으로 판단해보자.고등학교 때 $cosθ = \frac{x}{r}$ 임을 배웠다.두 벡터는 비슷할수록 θ 가 작아진다. (점점 가까워지므로)θ 가 작을수록 cosθ는 점점 커진.. [아호코라식 (Aho-corasick) 알고리즘] 논문 이해하기 (3) - 성능 측정 이전 글에서는 아호코라식 알고리즘의 구조에 대해서 알아보았다.이번 글에서는 아호코라식과 엘라스틱서치(ES) 로 검색을 했을 때 성능 측정을 간단하게 해볼 것이다.결론색인 키워드: 5543 개검색 요청: 1000 개 아호코라식ES메모리 사용량5 mb2 mb색인 시간42 ms286 ms검색 시간7 ms2051 ms아호코라식이 압도적으로 빠르다. (색인시간은 약 6.8배, 검색시간은 약 293배 빠름)메모리 사용량은 아호코라식이 더 잡아먹는다. (ES 보다 2.5배)아호코라식은 색인시간이 검색시간보다 더 오래걸린다. (42 ms > 7 ms)ES는 검색시간이 색인시간보다 더 오래걸린다. (2051 ms > 286 ms)※ 검색 결과는 고려하지 않았다.자세한 이야기[색인 키워드] 한글로 이루어진 단어 5543 .. [아호코라식 (Aho-corasick) 알고리즘] 논문 이해하기 (2) - 데이터 구축 이전 글에서는 아호코라식 알고리즘의 검색 과정에 대해서 알아보았다. [아호코라식 (Aho-corasick) 알고리즘] 논문 이해하기 (1) - 검색 과정 아호코라식 알고리즘은 문자열을 검색하는 알고리즘이다. 검색할 단어가 10개 일 때 검색 대상 문자열도 일일이 10번 탐색하는 게 아니라 찾을 검색어가 아무리 많아도 한 번만 탐색하여 결과를 elsboo.tistory.com 이번 글에서는 아호코라식이 구성하는 세 개 함수 goto(), output() , failure() 의 데이터를 구축하는 법에 대해 알아보자 함수 데이터는 어떻게 만들까? goto() 검색 대상 단어들 [he, she, his, hers] 을 Trie 자료구조로 표현하는 게 목표이다. 문자 하나를 간선(-), 문자의 state 를 정.. [아호코라식 (Aho-corasick) 알고리즘] 논문 이해하기 (1) - 검색 과정 아호코라식 알고리즘은 문자열을 검색하는 알고리즘이다. 검색할 단어가 10개 일 때 검색 대상 문자열도 일일이 10번 탐색하는 게 아니라 찾을 검색어가 아무리 많아도 한 번만 탐색하여 결과를 얻을 수 있다. 시간복잡도가 O(n + m + z) 로 제곱이나 log 가 붙는게 아닌 선형적으로 증가하므로 속도가 빠른 검색 알고리즘에 속한다. n : 텍스트의 길이 m : 모든 패턴의 총 길이 z : 텍스트 내에서 발견된 패턴의 총 출현 횟수 ※ 용어 정리 - 텍스트, 패턴 필자는 논문이나 구글링을 할 때 많이 출현하는 용어 텍스트와 패턴의 의미가 헷갈렸었다. 💡 텍스트 → 검색 대상 문자열 or 단어들 패턴 → 검색어 로 이해하면 쉽다. 예를 들면 텍스트와 패턴이 아래와 같을 때, 💡 텍스트: [사과, 오렌지, .. 편집 거리 알고리즘 이해하기 편집 거리 (Edit Distance) 에 대해 단어 “둥굴랭”과 단어 “둥굴레차” 가 오타와 정타 관계 구나 라는 것을 ‘사람’이라면 직관적으로 인지할 수 있다. 하지만 ‘컴퓨터’는 어떻게 판단할 수 있을까? 이렇게 두 문자열 사이의 유사도를 수치화할 수 있는 방법 중의 하나로 편집거리 알고리즘을 사용한다. 편집 거리는 문자열 A 가 문자열 B와 동일하게 되기 위한 최소 변경(삽입, 삭제, 대체) 횟수를 말한다. 예를 들어 [둥굴랭] 와 [둥굴레차] 의 편집 거리를 구해보자. [둥굴랭] 이 [둥굴레차] 가 되기 위해서는 ‘랭’을 ‘레’로 대체 ‘차’ 는 삭제 하면 [둥굴레차] 가 되므로 이 둘의 편집 거리는 2이다. ※ 편집 거리 알고리즘을 수학자 Vladimir Levenshtein 이 고안했다고 해.. ElasticSearch BM25 이해하기 다음 3개의 문서가 있다. [문서 1] 눈을 떠보니 커피 없는 세상에 와버렸다. [문서 2] 너도 커피 좋아해? 나도 커피 좋아해 [문서 3] 저기 저 앞에 커피 파는 가게가 있다. 한 번 가볼래? 그래 내가 쏠게 마시러 가보자 사용자가 “커피” 를 검색한다. 당신은 검색엔진이고 “커피” 와 가장 관련있는 순으로 검색 결과를 내보내야한다면 문서 순위를 어떻게 지정할 것인가? 만약 2, 1, 3 순이라고 답했다면 축하한다! 당신은 BM25를 이해했다. 날짜, 불리언 같은 간단한 필드를 검색할 때는 답이 정확이 존재하기 때문에 정답 문서를 찾는 것이 명확하다. 하지만 책, 뉴스 기사, 공고 내용 같은 full-text 로 구성된 필드를 검색하는 것은 비교적 명확하지 않다. 왜냐하면 full-text 검색은 .. 이전 1 다음
