해시트리를 이용한 ＵＲＬ 검색방법

출원번호 : 10-2008-0081135 (출원일: 2008-08-20)

등록번호 : 10-0999408 (등록일: 2010-12-02)

특허권자 : 충남대학교산학협력단

요약 : 본 발명은 URL 목록에서 특정 URL을 검색하는 종래의 방법에서 검색 속도를 개선하기 위하여 해시트리를 이용한 URL 저장과 검색방법에 관한 것이다. URL 해시트리의 모든 노드(node)는 해시 테이블로 이루어지는데 내부 노드(internal node)의 해시 테이블은 하위 해시 테이블의 메모리 포인터를 저장하고 종단 노드(leaf Node)의 해시 테이블은 호스트이름에 관한 정보와 경로에 관한 정보를 저장하는 리스트의 메모리 포인터를 저장한다. 즉, URL 해시트리는 해시 테이블과 리스트로 구성된다. 본 발명의 목적은 URL 목록을 저장하고 있는 URL 해시트리를 이용하여 검색대상 URL을 빠르고 효율적으로 검색하는 것이다.

대표청구항 : (A) (a) 사전에 정의된 URL 목록에서 해시트리에 삽입할 URL 하나를 추출하는 단계; (b) 추출된 URL을 호스트이름과 경로로 분리하는 단계; (c) 다중의 해시함수를 사용하여 여러 해시값을 구하거나, 단일 해시함수로 얻은 단일 해시값을 분할하여 여러 해시값을 구하여 호스트이름으로부터 해시값 튜플(I0,I1, … ,In-1)을 생성하는 단계; (d) 상기 해시값 튜플(I0,I1, … ,In-2)을 해시트리 각 단계의 인덱스로 활용하여 해당되는 종단 노드를 찾고 종단 노드가 존재 하지 않을 경우 내부 노드와 종단 노드를 생성하는 단계; (e) 상기 종단 노드의 인덱스(In-1) 위치에 호스트이름에 관한 정보와 해시되지 않은 경로에 관한 정보를 리스트에 저장하는 단계; (f) URL 목록의 모든 URL에 대하여 상기 (a)~(e) 단계를 수행한 후 해시트리 생성과정을 완료하는 단계;를 포함하는 해시트리 생성과정:과 (B) (a) 검색 대상 URL 입력단계; (b) 검색 대상 URL을 호스트이름과 경로 분리하는 단계; (c) 해시함수를 이용하여 호스트이름으로부터 해시값 튜플(J0,J1, … ,Jn-1)을 생성하는 단계; (d) 상기 해시값 튜플(J0,J1, … ,Jn-1)을 이용하여 상기 해시트리에서 리스트를 찾는 단계; (e) 리스트에서 저장된 호스트이름과 경로정보에 관련된 정보를 비교하는 단계;를 포함하는 URL 검색과정:으로 이루어지는 것을 특징으로 하는 해시트리를 이용한 URL 검색방법.

상세링크 : http://newsd.wips.co.kr/wipslink/api/dkrdshtm.wips?skey=3510106001184