2009.06.28 오토링커(자동링크 생성기)를 만들면서...

행안부 국정피디아(위키) 고도화 사업에 참여하게 되어, 2008년 말에 만들었던 자동링크를 업그레이드 하게 되었다. 개발하면서 느낀 점들을 적어 보고자 한다. 
사실 기간이 너무 짧아서 많은 기능을 넣을 수는 없었으나, 제목(표제어)에서 색인어 추출방법 정교화와 잘못된 링크 생성 방지 라는 두 가지 관점에서 접근하였다.

예전 버전에서 바뀐 부분들은 아래와 같다.

색인어 검색에 트라이 사용
예전에 이진검색으로 처리했던 색인어 검색 부분은 트라이로 교체 되었다. 색인어가 많아 질 수록 이진검색은 검색시간이 증가하지만, 트라이는 증가하지 않기 때문이다. 트라이는 몇 달전에 C로 내가 직접 만든 것을 사용했다. 입력되는 문자가 다양하기 때문에 1바이트 단위로 비교하고, 압축하여 저장 공간을 최소화하는 방식이다.

문자처리를 UTF-8로 처리
euc-kr로 문자를 처리하던 것을 utf-8로 처리하였다. euc-kr로 처리할 때는 MS워드나 한글과 같은 워드프로세서에서 복사하여 입력된 글에서 깨지는 문자(유니코드용 특수문자)를 처리 할 수 없었고, utf-8로 인코딩 된 DB의 데이타가를 euc-kr로 인코딩하는 부수적인 시간이 소요됐다.

HTML, 유니코드, ASCII용 특수문자 인식
HTML4.01에 정의된 모든 특수문자를 추출하여, 색인과 검색에서 모두 반영했다. 예를 들면, HTML에 있고 ASCII에는 없는 “와 ”의 경우 모두 ASCII의 " 로 인식하도록 처리했다. 유니코드나 윈도우즈의 특수문자도 마찬가지로 처리했다.

제목에서 색인어 추출 방법 정교화
제목이 A(B)C일 경우 예전에는 단순히 괄호 안의 B만 무시하고, AC 를 색인어로 추출하여 사용했다. 하지만 ABC도 색인어가 가능한 경우가 있으며, AC조차 색인어로 불가능 한 경우도 있었다. 내가 사용한 분석 방법은 제목을 괄호와 따옴표등을 구분자로 하여 토큰으로 분리하고, 이 토큰들의 문자종류(한,영,중...)와 길이를 기준으로 조합가능성을 판단해 가능한 색인어를 생성하는 것이다. 하지만 문자종류와 길이 만으로 색인어를 생성하는 것은 위험성이 있으므로, 링크 생성시 여러 가지 제약사항으로 위험성을 최소화 한다.

만들면서 느낀 점들은 아래와 같다.

잘못된 링크 생성 방지
과거에는 고유명사 위주의 데이타가 대부분이어서 링크가 잘못 생성되는 경우가 매우 적었다. 하지만 이번에는 일반 국어사전 수준의 수만개의 데이타가 입력되고, 더욱이 한,두 글자의 제목까지 등장하여 링크의 오류 발생 위험성이 커졌다. 사실 한글의 오묘함 때문에 링크 생성하는 완벽히 만들기가 어렵다. 물론 형태소분석에서 의미분석까지 매우 고난도의 지식을 이용한다면 링크정확율은 높아질 것이지만, 실시간으로 링크를 생성하는 시간은 증가하게 된다.

아무튼 내가 선택한 방법은 명사(체언)에 특성을 이용하여 제약사항을 추가하는 것이다.
예를 들어 색인어가 "서울시"일 때, "서울시 시장"이라는 본문이 있다면, "서울시"≠"서울시 시장"이기 때문에 "서울시 시장(X)"에 링크를 거는 것은 옳지 않다. 즉 색인어가 A 일 때, "A B"에는 링크를 걸지 않으며, "A는", "A이다"와 같이 조사나 용언화 접미사로 연결되는 경우에만 링크를 만드는 것이다. 물론 "A B"의 A에도 링크를 거는 것이 옳을 때도 있다. 하지만 컴퓨터가 이를 판단하기는 너무 어렵다.

색인어의 길이가 한 두 글자로 짧을 경우에 오류가 자주 발생한다. 예를 들어 색인어에 "위해"가 존재할 경우, 문장에 "~~~를 위해서 "에 링크가 걸리게 된다. 왜냐하면 "서"라는 조사가 있기 때문이다. 또한 한글의 띄어쓰기의 애매성 때문에 무조건 띄어쓰기를 허용하는 경우, 색인어에 "의사"가 있을 경우, "~~~의 사고"에도 링크가 걸린다. 역시 "고"도 조사이기 때문이다. 이런 경우에는 제약사항을 추가하여 잘못된 링크생성을 막는 과정이 필요하다.

실시간 검색에 적합한 트라이 구조
먼저 내가 말하고자 하는 트라이의 구조라는 것은 트라이 한 노드의 내부 구조체를 말하는 것이다. 트라이의 내부 구조에서 색인어의 끝이라고 표시하는 부분이 필요하게 된다. 이 부분을 1bit의 종료 플래그로 정의해도 되며, 검색어가 항상 문자열일 경우에는 1노드짜리의 서브 트라이에 표시해도 된다. (편의상 전자를 플래그 방식, 후자를 노드 방식이라고 부르겠다.). 플래그 방식의 경우 저장공간을 줄이고 비교회수를 줄일 수 잇는 반면, 트라이는 문자열의 중간까지만 기록하기 때문에 최종노드를 찾은 후, 검색어 문자열과 트라이에 저장된 색인어를, strcmp나 memcmp등으로 전체 비교하여야 한다. 또한 플래그 방식의 경우 종료 노드가 되는 경우가 2종류로 발생하므로 검색 알고리즘이 약간 복잡하다. 반대로 노드방식은 저장공간을 많이 사용하나, 색인어의 전체문자열을 기록하므로, 전체 비교가 필요없다. 또한 항상 종료 노드에서만 색이어가 종료되므로, 검색 알고리즘이 간단하다.

자동링크 생성시 색인어를 검색하는 과정이 필요한데, HTML이기 때문에 검색할 때, 검색어를 미리 고정할 수가 없다. 다시 말해 HTML의 문자를 한글자씩 읽어 가면서 검색해야 한다는 것인데. 이는 검색어를 한글자씩 추가하면서 검색한다는 것이다. (정확히는 한 바이트씩 추가한다.)

트라이 구조를 적용하면서, 플래그, 노드 방식 모두 적용해 보았는데, 자동링크의 경우에는 노드 방식이 더 적합했다. 왜냐하면 자동링크의 경우에는 HTML을 한글자씩 읽기 때문에, 검색어가 계속 변한다. 따라서 색인어 전체정보가 없는 플래그 방식의 경우 입력된 검색어를 최종 확인이 되기 전까지 계속 보존해야 한다. 또한 검색알고리즘이 복잡하여 이를 자동링크용으로 변경해 보니 더욱 검색 알고리즘이 더욱 복잡해 졌다. 다만 트라이 생성이 빨라, 대량의 데이타의 경우 색인시간이 노드 방식보다 빠른 장점은 있었다.