2009.02.18 오토링커와 이진탐색

몇 달 동안 행정안전부의 온라인 행정백과사전 위키인 "국정피디아" 에 사용되는 오토링커를 개발했다.

오토링커란 글이 표시될 때, 이미 정의된 색인어(제목)과 일치하는 부분에 링크를 걸어 해당 글로 이동할 수 있게 하는 기능이다.
일반 위키는 작성자가 임의로 링크를 생성해야 한다. 그래서 작성자가 건 링크 외에는 같은 단어라도 링크가 걸리지 않는 문제가 있다. 링크를 실시간 또는 비실시간으로 생성할 수 있다., 비실시간으로 할 경우, 미리 링크 걸린 글을 생성해 놓으므로, 페이지 표시 속도가 매우 빠르지만, 새 글이 작성될 때 마다 모든 페이지의 링크를 재생성해야 하는 문제점이 있다. 실시간으로 링크를 처리할 경우, 매번 링크를 생성해야 하는 문제점이 있지만, 새 글이 작성되고 문서 수가 증가하여도 링크를 생성하는 시간은 비슷하다. 따라서 국정피디아에서는 실시간 링크를 생성하는 오토링커 서버를 사용하고 있다.

정보검색을 혼자 공부하면서 작성해 둔 스프링노트로 만든 위키가 있는데, 만들 면서 일일히 링크를 걸어 줘야 해서 매우 불편했다. 하지만 오토링커를 사용하면, 일일히 링크를 걸어줘야 하는 불편함은 없을 것이다.

자바스크립트 때문인 것 같은데, 스프링노트가 메모리를 너무 많이 사용하여 오래 사용하면 익스플로러가 죽는 다던지,
글을 정렬 할 때, 자동 정렬 기능이 불완전해서 오는 불편함이라던지 스프링노트가 문제점이 많지만,
내가 아는 위키중에서 스프링노트가 가장 편한 것은 사실이다.

오토링커는 일반적인 검색엔진 색인과는 반대로 단어(제목)를 색인해 놓고, 입력받은 문장을 처리하기 때문에, 실시간으로 많은 텍스트(입력받은 문장)을 처리해야 한다. 입력받은 문장에서 한글자씩 읽어 들이면서 링크를 걸어야 하는지 계산이 가능해야 한다. 따라서 오토링커는 보통 TRIE 와 처럼 한 글자씩 읽어서 색인된 단어랑 바로 매칭이 가능한 자료 구조를 이용한다.

일반적인 검색엔진은 문장을 색인해서 입력받은 단어를 처리한다.
형태소분석기도 오토링커와 비슷하므로, TRIE 와 비슷한 종류의 자료구조를 이용한다.

하지만, 개발 기간 관계로, 이진탐색을 응용하여 구현했다. 한글자씩 읽어 들이면서, 읽어들인 글자까지 이진검색을 하는 것이다. 이 때, 이전 글자에서 검색해서 얻은 결과를 이용한다. 즉, 이전 검색에서 얻은 first, last index값을 저장하고 다음 글자를 검색할 때, 그 범위에서만 이진검색을 수행하는 것이다. 이런 방법을 이용하면, 한 글자에 대해서 이진검색을 1회만 이용하기 때문에, TRIE와 비슷한 성능을 만들 수 있다.

여기서 제약 사항은, 이미 처리 했던 글자는 다시 처리하지 않아야 한다는 것이다.
문서내용이 "가나다라마...." 인데, "가나다"라는 색인된 단어가 없다고 해서
"나.."부터 다시 검색을 하면 안된다는 것이다. 다시 검색을 할 경우, 처리하는 데 매우 오래 걸릴 것이다.
따라서, 오토링커에서는 어절단위로 처리한다. 다시 말해  어절의 시작과 색인어의 시작을 같다고 생각하고 처리하는 것이다. 문장이 "가나다라 마바사..." 인데, "가나" 라는 단어가 없을 경우, 어절을 건너띄고 "마.."부터 매칭하는지 검색하는 것이다.

완벽한 오토링커를 만들기 위해서는 사전을 트라이와 비슷한 형태로 저장해야 하며, 형태소분석을 비롯하여, 한자를 한글로 변환하는 기능, 제목에서 색인할 단어를 추출하는 기능, HTML의 구조를 분석하는 기능 등 수도 없이 많은 기능이 필요하다. 특히 개발하면서 최소한 조사,어미 분리 루틴과 한자/한글 변환 기능은 꼭 필요하다는 것을 느꼈다.

오토링커를 개발하면서 깨달은 것은, "항상 정석이 필요하지 않다"는 것이다. TRIE를 사용하는 것이 정석이지만, 정렬된 색인파일(제목 목록)과 간단한 이진검색 함수 하나만으로도 비슷한 성능을 낼 수 있다는 것이다. (물론 띄어쓰기가 없는 중국어나 일본어에서는 힘들겠지만....)

대부분 0.1초 이내의 시간에 링크를 생성했으며, 400~500KB 의 문서의 경우 0.2-0.3 초의 시간이 걸렸다.