Joinc Wiki: 색인기

Facebook Joinc 그룹 Joinc QA 사이트

현재위치 : 미니사이트>Joinc>Project>Related_Link>Code>Indexer

joinc는 Firefox와 chrome에서 테스트 했습니다. IE에서는 테이블이 깨지거나 이미지가 보이지 않을 수 있습니다. 특히 구글 Docs이미지의 경우 엑박처리될 수 있습니다.

오늘부터 만들어진 단어사전을 이용해서 색인기를 작성해볼 생각이다.

프로시져 코드

문서를 token 으로 분리한 다음 각각의 문자열을 사전에 매칭한다.
매칭은 최장길이 검색을 한다.

예를 들어 검색엔진시스템으로가 주어졌지고, 사전에 검색, 검색엔진, 검색엔진시스템, 엔진이 있다면, 검색, 검색엔진, 검색엔진시스템 으로 색인이 된다.
그 다음에는 최단검색단어 검색뒤에 있는 엔진시스템문자열로 단어사전을 검색한다.
최종적으로는 검색, 검색엔진, 검색엔진시스템, 엔진 으로 색인이 될 것이다.

테스트용 단어사전

테스트를 위해서 간단한 단어사전을 만들었다. 단어사전은 endian에 대해서문서에서 대략 추철해냈다. 아래의 단어사전을 이용해서 주어진 문서를 효과적으로 색인하는 방법에 대해서 고민해 보도록 하겠다.

endian 기초지식 기초 지식 프로그래밍 단어 끝돌이 결론 엔디안 데이타 데이터 컴퓨터 여러분 제조업체  
우리 방식 후자 전자 방식 Intel계열 int형 int 네트웍프로그래밍 네트웍 클라이언트 서버 해결방법  
해결 방법 전송 공통 무조건 통일 시스템 관계 host byte order 입력 port htons ntohl 변경 다른 해결책 불편 단위 통신

단어사전 자료구조

주어진 단어가 단어사전에 있는지 가능한 빠른시간에 검색해내는 알고리즘의 적용이 가능한 자료구조를 만들어야 할 것이다. 다양한 방법을 고민해 보고 이중 쓸만한것 하나를 선택해서 사용하도록 할것이다. 필요하면, 성능테스트도 실시해볼 생각이다.

Index map 생성

문서를 색인하기 위해서는 token으로 분리하고, 분리된 단어가 단어사전에 있는지 확인해야 한다. 단어사전에 대해서 검색이 들어가게 되는데, 빠른 검색을 위해서, 다음과 같이 단어사전만을 위한 인덱스 테이블을 구성하기로 했다.

  Index Table                 Term Table 
  +-------------+            +-------------+ 
  | Apache      |            |             | 
  |             |            |             | 
  |             |            |             | 
  | Linux       |-----+      |             | 
  |             |     |      | Large       | 
  |             |     +----->| Long        | 
  |             |            | Linus       | 
  +-------------+            | Linux       | 
                             |             | 
                             |             | 
                             |             | 
                             |             | 
                             +-------------+

우선 단어사전을 정렬해서 Term Table을 구성해야 할것이다. 일단 정렬이 된다면, 이진검색을 이용해서 주어진 단어가 있는지 확인할 수 있겠지만, 시간을 좀더 절약하기 위해서 skip interval을 가지는 index Table을 만들도록 할 것이다. skip interval은 테스트를 위해서 12로 하도록 하겠다. 단어사전을 정렬하면서, skip interval 만큼 단어가 축적되면 index Table를 만들면 된다. 이 Index Table은 해당 skip interval에 발생된 단어와 단어가 가리키는 Term Table의 포인터 정보를 가지게 된다.

Index Table에서 이진검색을 해서, 던아가 존재하는 블럭을 찾고, 해당 블럭내에서 선형검색을 하는 방식이다.

이진트리 구성

균형이진트리를 구성했을 경우의 복잡도는 STL 응용문서를 참고하기 바란다. 1,000,000개의 원소가 있을 때, 평균 복잡도는 20정도로 매우 효율적이다. STL의 map 컨테이너가 균형이진트리 구현이다. STL의 map을 사용해서 구현할 수도 있겠지만 트리 자료구조에 대한 고민도 할겸 직접구현해볼 생각이다.

색인문서 tokenizing

일단 색인할문서에서 HTML 태그를 모두 없애고, 이걸 tokenizing 한다. tokenizing된 문서는 스토어에 저장이 되어야 한다. 저장되어야 하는 이유는 Score를 적용할때, 단어가 문서의 어느부분에 위치하는지를 알아야 되기 때문이다. 예를들어 소켓 프로그래밍으로 검색을 했을 경우 소켓 프로그램을 작성해보자와 같이 단어가 붙어있는 문서가 소켓을 이용하는 프로그램을 작성하기 위해서는보다 높은 점수를 줘야 하기 때문이다.

문서의 tokenizing 는 HTML 태그제거 프로그램을 약간 수정해서 사용하도록 하겠다. 프로그램을 돌린결과 다음과 같은 토크나이징된 문서를 얻을 수 있었다. charset은 EUC-KR 이다.

token.txt

뇌자극 QA 뇌자극 에러 및 수정목록 총 페이지 수 : 3224 전체 함수/용어사전 구글검색방법 구글 맞춤검색	Facebook Joinc 그룹 Joinc QA 사이트 현재위치 : 미니사이트>Joinc>Project>Related_Link>Code>Indexer Tweet joinc는 Firefox와 chrome에서 테스트 했습니다. IE에서는 테이블이 깨지거나 이미지가 보이지 않을 수 있습니다. 특히 구글 Docs이미지의 경우 엑박처리될 수 있습니다. 오늘부터 만들어진 단어사전을 이용해서 색인기를 작성해볼 생각이다. 프로시져 코드 문서를 token 으로 분리한 다음 각각의 문자열을 사전에 매칭한다. 매칭은 최장길이 검색을 한다. 예를 들어 검색엔진시스템으로가 주어졌지고, 사전에 검색, 검색엔진, 검색엔진시스템, 엔진이 있다면, 검색, 검색엔진, 검색엔진시스템 으로 색인이 된다. 그 다음에는 최단검색단어 검색뒤에 있는 엔진시스템문자열로 단어사전을 검색한다. 최종적으로는 검색, 검색엔진, 검색엔진시스템, 엔진 으로 색인이 될 것이다. 테스트용 단어사전 테스트를 위해서 간단한 단어사전을 만들었다. 단어사전은 endian에 대해서문서에서 대략 추철해냈다. 아래의 단어사전을 이용해서 주어진 문서를 효과적으로 색인하는 방법에 대해서 고민해 보도록 하겠다. endian 기초지식 기초 지식 프로그래밍 단어 끝돌이 결론 엔디안 데이타 데이터 컴퓨터 여러분 제조업체 우리 방식 후자 전자 방식 Intel계열 int형 int 네트웍프로그래밍 네트웍 클라이언트 서버 해결방법 해결 방법 전송 공통 무조건 통일 시스템 관계 host byte order 입력 port htons ntohl 변경 다른 해결책 불편 단위 통신 단어사전 자료구조 주어진 단어가 단어사전에 있는지 가능한 빠른시간에 검색해내는 알고리즘의 적용이 가능한 자료구조를 만들어야 할 것이다. 다양한 방법을 고민해 보고 이중 쓸만한것 하나를 선택해서 사용하도록 할것이다. 필요하면, 성능테스트도 실시해볼 생각이다. Index map 생성 문서를 색인하기 위해서는 token으로 분리하고, 분리된 단어가 단어사전에 있는지 확인해야 한다. 단어사전에 대해서 검색이 들어가게 되는데, 빠른 검색을 위해서, 다음과 같이 단어사전만을 위한 인덱스 테이블을 구성하기로 했다. Index Table Term Table +-------------+ +-------------+ \| Apache \| \| \| \| \| \| \| \| \| \| \| \| Linux \|-----+ \| \| \| \| \| \| Large \| \| \| +----->\| Long \| \| \| \| Linus \| +-------------+ \| Linux \| \| \| \| \| \| \| \| \| +-------------+ 우선 단어사전을 정렬해서 Term Table을 구성해야 할것이다. 일단 정렬이 된다면, 이진검색을 이용해서 주어진 단어가 있는지 확인할 수 있겠지만, 시간을 좀더 절약하기 위해서 skip interval을 가지는 index Table을 만들도록 할 것이다. skip interval은 테스트를 위해서 12로 하도록 하겠다. 단어사전을 정렬하면서, skip interval 만큼 단어가 축적되면 index Table를 만들면 된다. 이 Index Table은 해당 skip interval에 발생된 단어와 단어가 가리키는 Term Table의 포인터 정보를 가지게 된다. Index Table에서 이진검색을 해서, 던아가 존재하는 블럭을 찾고, 해당 블럭내에서 선형검색을 하는 방식이다. 이진트리 구성 균형이진트리를 구성했을 경우의 복잡도는 STL 응용문서를 참고하기 바란다. 1,000,000개의 원소가 있을 때, 평균 복잡도는 20정도로 매우 효율적이다. STL의 map 컨테이너가 균형이진트리 구현이다. STL의 map을 사용해서 구현할 수도 있겠지만 트리 자료구조에 대한 고민도 할겸 직접구현해볼 생각이다. 색인문서 tokenizing 일단 색인할문서에서 HTML 태그를 모두 없애고, 이걸 tokenizing 한다. tokenizing된 문서는 스토어에 저장이 되어야 한다. 저장되어야 하는 이유는 Score를 적용할때, 단어가 문서의 어느부분에 위치하는지를 알아야 되기 때문이다. 예를들어 소켓 프로그래밍으로 검색을 했을 경우 소켓 프로그램을 작성해보자와 같이 단어가 붙어있는 문서가 소켓을 이용하는 프로그램을 작성하기 위해서는보다 높은 점수를 줘야 하기 때문이다. 문서의 tokenizing 는 HTML 태그제거 프로그램을 약간 수정해서 사용하도록 하겠다. 프로그램을 돌린결과 다음과 같은 토크나이징된 문서를 얻을 수 있었다. charset은 EUC-KR 이다. token.txt