1 |
1
문서에 포함된 키워드 또는 인덱싱할 문장의 프리픽스에 따라 인덱스 트리를 관리하는 방법에 있어서,
정보 검색 시스템이 메모리부에 저장된 상기 인덱스 트리에서 문자가 삽입될 제1노드를 검색하는 단계;
상기 제1노드가 포화 상태가 아니면 상기 정보 검색 시스템이 상기 문자를 상기 제1노드에 새로운 엔트리로 삽입하는 단계; 및
상기 제1노드가 포화 상태이면, 상기 정보 검색 시스템이 상기 문자와 상기 제1노드의 키값 및 자식 노드 포인터를 해시 버킷에 저장하여 상기 제1노드를 해시 테이블로 변환하는 단계를 포함하는, 프리픽스 트리 기반 색인 방법
|
2 |
2
제 1 항에 있어서,
엔트리의 삭제가 요청되면, 상기 정보 검색 시스템이 삭제가 요청된 엔트리가 속한 제2노드를 검색하는 단계; 및 상기 정보 검색 시스템이 상기 삭제가 요청된 엔트리만 삭제하는 단계를 더 포함하는 것을 특징으로 하는, 프리픽스 트리 기반 색인 방법
|
3 |
3
제 2 항에 있어서,
상기 제2노드가 해시 함수를 이용한 노드가 아니고 상기 제2노드에 남아있는 엔트리가 없다면, 상기 정보 검색 시스템이 상기 제2노드의 부모 노드에서 상기 제2노드에 대한 링크를 삭제하는 단계를 더 포함하는 것을 특징으로 하는, 프리픽스 트리 기반 색인 방법
|
4 |
4
제 2 항에 있어서,
상기 제2노드가 해시 함수를 이용한 노드인 경우, 상기 제2노드의 전체 엔트리의 수가 임계값 미만이면, 상기 정보 검색 시스템이 상기 제2노드의 전체 엔트리로부터 추출된 문자들을 이용하여 상기 제2노드를 재구성하는 단계를 더 포함하는 것을 특징으로 하는, 프리픽스 트리 기반 색인 방법
|
5 |
5
제 1 항에 있어서,
상기 제1노드에 삽입하는 단계 및 상기 제1노드를 해시 테이블로 변환하는 단계는
상기 제1노드의 해시 플래그를 검사하여 상기 제1노드가 해시 함수를 이용한 노드인지 판단하는 단계를 포함하는 것을 특징으로 하는, 프리픽스 트리 기반 색인 방법
|
6 |
6
제 1 항에 있어서,
상기 제1노드가 해시 함수를 이용한 노드이면서 포화 상태이면, 상기 정보 검색 시스템이 상기 해시 버킷의 수를 증가시켜 상기 프리픽스 문자를 해시 버킷에 저장하는 단계를 더 포함하는 것을 특징으로 하는, 프리픽스 트리 기반 색인 방법
|
7 |
7
문서에 포함된 키워드 또는 인덱싱할 문장의 프리픽스에 따라 인덱스 트리를 검색하는 방법에 있어서,
정보 검색 시스템이 메모리부에 저장된 상기 인덱스 트리의 루트부터 시작하여 검색 대상 문자열의 키값들을 해당키의 포인터를 따라가면서 상기 인덱스 트리에서 깊이 우선으로 검색하는 단계;
검색 중인 노드가 해시 함수를 이용한 노드라고 판단되면, 상기 정보 검색 시스템이 상기 검색된 노드의 해시 값들에 따라 자식 노드 포인터를 찾는 단계; 및
상기 정보 검색 시스템이 상기 자식 노드 포인터에 따른 단말 노드에서 데이터를 추출하는 단계를 포함하는, 프리픽스 트리 기반 색인 방법
|
8 |
8
제 7 항에 있어서,
상기 데이터를 추출하는 단계는
상기 자식 노드 포인터가 가리키는 노드가 내부 노드인 경우, 단말 노드가 나올 때까지 상기 자식 노드 포인터가 가리키는 다음 노드로 이동하는 단계를 포함하는 것을 특징으로 하는, 프리픽스 트리 기반 색인 방법
|
9 |
9
제 7 항에 있어서,
상기 자식 노드 포인터를 찾는 단계는
상기 인덱스 트리를 깊이 우선으로 검색하면서 각 노드의 해시 플래그를 검사하여 해당 노드가 해시 함수를 이용한 노드인지 판단하는 단계를 포함하는 것을 특징으로 하는, 프리픽스 트리 기반 색인 방법
|
10 |
10
제1항 내지 제9항 중 어느 한 항의 방법을 컴퓨터 시스템에서 실행하기 위한 프로그램이 기록된, 컴퓨터 시스템이 판독할 수 있는 기록매체
|
11 |
11
정보 검색 시스템에서 문서에 포함된 키워드 또는 인덱싱할 문장의 프리픽스에 따라 인덱스 트리를 관리하는 장치에 있어서,
상기 인덱스 트리를 저장하는 메모리부;
상기 인덱스 트리에서 문자가 삽입될 제1노드를 검색하는 노드 검색부; 및
상기 제1노드가 포화 상태가 아니면 상기 문자를 상기 제1노드에 새로운 엔트리로 삽입하고, 상기 제1노드가 포화 상태이면 상기 문자와 상기 제1노드의 키값 및 자식 노드 포인터를 해시 버킷에 저장하여 상기 제1노드를 해시 테이블로 변환하는 인덱스 트리 갱신부를 포함하는, 프리픽스 트리 기반 색인 장치
|
12 |
12
제 11 항에 있어서,
상기 인덱스 트리 갱신부는
상기 인덱스 트리의 노드들을 순회하면서 현재 노드 및 자식 노드의 통합 가능 여부를 검사하고, 통합 가능한 경우 상기 자식 노드의 엔트리들을 상기 현재 노드에 통합하면서 상기 현재 노드의 압축 플래그를 변경하는 것을 특징으로 하는, 프리픽스 트리 기반 색인 장치
|
13 |
13
제 12 항에 있어서,
상기 인덱스 트리 갱신부는
복수개의 노드들이 압축되어 있는 압축 노드가 포화 상태에서 새로운 엔트리가 삽입되는 경우, 상기 복수의 노드 중 적어도 일부의 노드를 압축 해제한 후, 상기 압축이 해제된 노드를 상기 인덱스 트리에 삽입하는 것을 특징으로 하는, 프리픽스 트리 기반 색인 장치
|