코딩 썸네일형 리스트형 [2021 Hackathon] 1. Data Preprocessing 보호되어 있는 글입니다. 더보기 [Python] IR 검색 알고리즘 - BM25 / 엘라스틱서치 랭킹 알고리즘 / 파이썬 rank_bm25 모듈로 문서 검색 구현하기 키워드 기반의 랭킹 알고리즘 - BM25 BM25(a.k.a Okapi BM25)는 주어진 쿼리에 대해 문서와의 연관성을 평가하는 랭킹 함수로 사용되는 알고리즘으로, TF-IDF 계열의 검색 알고리즘 중 SOTA 인 것으로 알려져 있다. IR 서비스를 제공하는 대표적인 기업인 엘라스틱서치에서도 ElasticSearch 5.0서부터 기본(default) 유사도 알고리즘으로 BM25 알고리즘을 채택하였다. BM25 step by step 살펴보기 BM25는 Bag-of-words 개념을 사용하여 쿼리에 있는 용어가 각각의 문서에 얼마나 자주 등장하는지를 평가한다. 키워드 q1,..., q_n을 포함하는 쿼리 Q가 주어질 때 문서 D에 대한 BM25 점수는 다음과 같이 구한다. 식은 복잡해 보이지만, 요소 하.. 더보기 라빈 카프 알고리즘(Rabin-Karp Algorithm) : 해싱을 통해 효율적으로 문자열 검색하기 / 해싱 / 해시함수 해싱 (Hashing) 키 값에 직접적인 산술 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산해 항목에 접근하는 방법. 충분히 큰 공간을 할당한 다음 해시 함수를 이용해 고유 색인을 생성하고, 색인에 맞는 위치에 데이터를 저장하는 것이 특징이다. 해시함수 : 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 함수 해시 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 구조 해싱 : 해시 테이블을 이용해 탐색하는 것 해싱에서는 자료를 저장하는 데 배열을 사용한다. 배열은 항목이 저장된 주소를 알고 있을 경우 빠르게 자료를 삽입하고 꺼내올 수 있기 때문이다. 배열에서의 삽입/ 접근에 대한 시간 복잡도는 O(1) 이다. 따라서 데이터를 색인으로 매핑하는 함수만 정의한다면, 이론적.. 더보기 [Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기 힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다. 힙 property : A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립한다 최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙 최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙 이러한 속성으로 인해 힙에서는 가장 낮은(혹은 높은) 우선순위를 가지는 노드가 항상 루트에 오게 되고 이를 이용해 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다. 이때 키값의 대소 관계는 부모/자식 간에만 성립하고, 형제노드 사이에는 대소 관계가 정해지지 않는다. 파이썬 힙 자료구조 파이썬 heapq 모듈은 heapq (priority queue) 알고.. 더보기 이전 1 2 다음
