검색 엔진 프로토타이핑

검색 엔진을 만들었다. IIR 책을 보면서 이론을 직접 구현해봐야겠다는 생각에 주말에 짬을 내어 코딩을 시작했다. 마침 비가 내려 밖으로 운동 하러 나갈 수도 없었고 이쁜 꼬맹이 친구가 집에 놀러와 다소 여유도 생겼다.

2018년 6월 6일 문장 정리
2015년 11월 27일 1차 개정
2014년 6월 23일 초안 작성

서론

C++로 Write from Scratch 를 생각했으나 그러기엔 시련이 너무 많았다. 결정적으로 주말에 끝내기엔 지나치게 방대했다. 결국 오픈소스를 fork 하기로 마음 먹었고 Gigablast를 고민했으나 마찬가지로 오히려 새로 짜는게 빠르겠다 싶을 정도로 구조가 복잡했다. 애당초 엔터프라이즈 레벨의 검색 엔진이라 IIR을 프로토타이핑 해보는 용도로는 지나치게 방대했다.

본론

그러던 중 Simple Search Engine이라는 프로젝트가 눈에 띄었다. 파이썬이라 빠른 프로토타이핑이 가능할 것 같았고, 일단 IIR 구현에 중점을 두고 추후에 C++로 컨버팅하면서 구조와 성능을 개선하는 편이 낫겠다는 생각이 들었다.

프로젝트를 fork 하기로 했다. 이후 전체 구조를 그림을 그리면서 파악해나갔고 기능별로 구조를 떼어 내면서 리팩토링을 시작했다. 애당초 색인기와 검색기가 통합된 형태였는데 이를 색인기, 검색기, 저장소로 떼어내고 랭킹도 따로 떼어냈다.

사실 파이썬에는 딕셔너리라는 훌륭한 자료형이 있어서 색인 구조에 별다른 고민을 할 필요가 없었다. 그래서 포스팅 리스트의 스킵 포인터를 직접 구현해볼 수 없었다. 하이 레벨High Level 언어를 쓰다보니 그러지 못한 점은 다소 아쉽다.

색인기 뿐만 아니라 쿼리의 불용어stopwords 처리를 추가했고 색인 데이타를 시리얼라이즈serialize해서 파일로 저장하는 구조로 바꿨다. 원본이 10만개의 튜플을 지닌 11.1 MB인데 색인은 1.2배 크고 따로 설명하겠지만 랭킹은 무려 7.5배나 더 큰, 최적화는 엉망인 색인기가 탄생했다. 그러나 나름대로 검색 엔진 구조 자체는 만족스런 형태로 개선할 수 있었다.

랭킹쪽은 이미 tf-idf 구현이 잘 되어 있어 특별히 수정할 부분은 없었다. 색인 시점에 미리 점수를 계산해서 검색 속도를 높였고 tf는 원문 저장소에, idf는 Vocabulary 리스트에 산출한 다음 각 docs * terms 간 매트릭스를 만들어 여기에 점수를 저장했다. 점수를 노멀라이즈 하고 중복 엔트리를 합산Summed Together하는 약식의 압축과정을 거치지만 그래도 원본에 비해 랭킹 파일이 무려 7.5배나 더 큰 부분은 아직 개선할 여지가 많다.

샘플 데이타로 크로스핏 선수들의 트윗을 활용했고 원본 데이타는 크로스핏, NBA, NFL, UFC, 동계 올림픽을 포함한 유명 운동선수(ahletes)들의 트윗 100,000건을 트위터 API를 통해 취합한 다음 이를 활용했다. 색인 후 쿼리를 날려보니 0.1초 이내로 결과가 잘 나온다. 그렇게 해서 아래의 검색 엔진이 탄생했다. 상세한 내용은 README에 상세히 적어뒀고 쉽게 실행할 수 있도록 했다. 재밌는 경험이었다. 주말에 잘 끝내서 일정관리도 성공적이었고 깃헙의 편리함도 다시 한 번 깨달을 수 있었다.

결론

  1. 모든 문서는 영어로
    원어민이 아닌 이상 영어는 누구나 힘들다. 하지만 좋은 소프트웨어가 언어 문제로 제약을 받는건 안타까운 일이다. 언어의 제약 없이 지식을 공유하기 위해서 모든 코드와 주석, 문서를 영어로 작성하려는 노력이 필요하다.
  2. C++
    파이썬은 최고의 프로토타이핑 도구이지만 IIR의 기본 컨셉을 밑바닥 부터 구현하고 고성능을 내기 위해서는 좀 더 로우 레벨의 언어가 필요했다. 추후에는 C++로 다시 작성해보면 좋을 것 같다.
  3. 훌륭한 GitHub
    읽기만 하는 것과 직접 사용해보는 것은 다른 문제였다. 여러번 읽기만 하면서 느끼지 못했던 부분들을, 직접 사용해보면서 커밋하고 푸쉬하면서, 깃헙이 얼마나 편리하고 얼마나 훌륭한 도구인지 새삼 깨닫게 됐다. 몰랐던 새로운 기능들도 많이 알게 됐다.

참고

소스 코드를 포함한 깃헙 주소는 아래와 같다.

is a collection of Papers I have written.
© 2000 - Sang Park Except where otherwise noted, content on this site is licensed under a CC BY 4.0.
This site design was brought from Distill.