SearchDeveloper/알고리즘 (4) 썸네일형 리스트형 [아호코라식 (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 다음
