KR100957080B1

KR100957080B1 - 문서 구조에 기초한 검색 결과의 표시

Info

Publication number: KR100957080B1
Application number: KR1020077009771A
Authority: KR
Inventors: 아미타브흐 케이. 싱할; 비레쉬 라트나카르; 막심 리판스테프; 요셉 키에란 오술리반
Original assignee: 구글 인코포레이티드
Priority date: 2004-09-27
Filing date: 2005-08-19
Publication date: 2010-05-13
Also published as: JP2008515049A; BRPI0517356B1; KR20070058685A; CN101061479A; CA2581713A1; WO2006036376A1; CA2581713C; AU2005290154A1; BRPI0517356A; JP4637181B2; EP1800226A1; CN101061479B; US9031898B2; US20060074907A1; AU2005290154B2

Abstract

시스템은 복수의 구조적 요소를 포함하는, 검색어와 관련된 문서를 식별한다. 상기 시스템은 상기 문서에서의 상기 검색어의 출현 분포를 결정하고, 상기 문서 내에서의 상기 검색어의 출현 분포에 기초하여 상기 구조적 요소 중 하나를 식별하며, 상기 식별된 구조적 요소와 연관된 정보를 표시한다.

검색어, 검색 질의, 문서, 코퍼스, 구조적 요소, 계층구조, 트리

Description

문서 구조에 기초한 검색 결과의 표시 {PRESENTATION OF SEARCH RESULTS BASED ON DOCUMENT STRUCTURE}

본 발명에 따른 시스템 및 방법은 일반적으로 정보 검색에 관한 것이고, 더욱 구체적으로는 문서의 구조에 기초하여 검색 결과인 문서를 표시하는 것에 관한 것이다.

월드와이드웹(World Wide Web. "web")은 거대한 양의 정보를 가지고 있다. 하지만, 원하는 부분을 찾아내는 것은 모험일 수 있다. 웹상의 정보의 양과 웹 검색 경험이 없는 새로운 사용자의 숫자가 급속하게 증가하기 때문에, 이 문제는 복합적이다.

검색 엔진은 사용자가 관심이 있는 웹 문서에 대한 하이퍼링크의 회신을 시도한다. 일반적으로, 검색 엔진은 사용자에 의해 입력된 (검색 질의라고 하는) 검색어에 대한 사용자의 관심에 대한 결정에 기초한다. 검색 엔진의 목적은 검색 질의에 기초하여 높은 품질의 관련 결과를 사용자에 제공하는 것이다. 대개, 검색 엔진은 검색 질의 내의 용어를 미리 저장된 웹 문서들의 코퍼스(corpus)와 대조함으로써 상기 목적을 달성한다. 사용자의 검색어를 포함하는 웹 문서는 "히트(hit)"하는 것이고 사용자에게 회신된다. 일반적으로 기존의 검색 엔진은 히트 한 것을 웹 문서의 초록(excerpt)으로서 표시한다. 이 초록은 검색 결과 페이지로서, 단일 웹 페이지에 표시될 수 있다.

일 실시양태에 따른 방법은, 구조적 요소(structural element)의 세트를 포함하는, 검색어(search term)에 관련된 문서를 식별하는 단계를 포함할 수 있다. 이 방법은 또한 상기 문서에서의 상기 검색어가 출현하는 페이지를 결정하는 단계; 상기 문서에서의 상기 검색어가 출현하는 페이지의 분포에 기초하여 상기 구조적 요소 중 하나를 식별하는 단계; 및 상기 식별된 구조적 요소와 연관된 정보를 표시하는 단계를 포함한다.

다른 실시양태에 따른 방법은, 구조적 요소의 세트를 포함하는, 검색어와 관련 있는 문서를 식별하는 단계를 포함할 수 있다. 상기 방법은 또한 상기 문서에서의 상기 검색어가 출현하는 페이지를 결정하는 단계; 상기 검색어가 출현하는 페이지의 물리적 근접도(physical proximity)에 기초하여, 상기 검색어가 출현하는 페이지를 클러스터로 분류하는 단계; 상기 문서에서의 상기 검색어가 출현하는 페이지의 분포에 기초하여 상기 구조적 요소 중 하나를 식별하는 단계; 각각의 클러스터를 포함하는 상기 구조적 요소 중 하나를 결정하는 단계; 및 상기 결정된 구조적 요소에 관한 정보를 제공하는 단계를 포함할 수 있다.

또 따른 실시양태에 따른 방법은, 구조적 요소의 세트를 포함하는, 검색어와 관련 있는 문서를 식별하는 단계를 포함할 수 있으며; 상기 구조적 요소는 상기 문서, 상기 문서의 파트(part)의 세트, 및 상기 문서의 페이지(page)의 세트를 포함한다. 상기 방법은 또한 상기 문서의 페이지는 종단 노드(leaf node)에 대응하고, 상기 문서의 파트는 상위 레벨 노드(higher level node)에 대응하며, 상기 문서는 루트 노드(root node)에 대응하는, 문서의 트리 표현(tree representation)을 식별하는 단계를 포함할 수 있다. 상기 방법은 또한 상기 종단 노드가 상기 검색어의 출현을 포함하는지에 기초하여 상기 종단 노드에 스코어를 할당하는 단계; 상기 종단 노드 중 연관된 종단 노드에 기초하여 상위 레벨 노드에 대한 스코어를 결정하는 단계; 상기 상위 레벨 노드에 대한 스코어에 기초하여 상기 루트 노드의 스코어를 결정하는 단계; 상기 스코어에 기초하여, 상기 종단 노드 중 하나 또는 상기 상위 레벨 노드 중 하나 또는 상기 루트 노드를, 선택된 노드로서 선택하는 단계; 및 상기 선택된 노드를 관한 정보를 제공하는 단계를 포함할 수 있다.
본 발명의 다른 태양에 따른 컴퓨터로 판독가능한 메모리 디바이스로서, 컴퓨터로 실행가능한 명령어들을 포함하고, 복수의 구조적 요소를 포함하는, 검색어와 관련된 문서를 결정하기 위한 명령어, 상기 문서에서의 상기 검색어의 출현을 결정하기 위한 명령어, 상기 검색어의 출현의 물리적 근접도에 기초하여 상기 검색어의 출현을 클러스터로 분류하기 위한 명령어, 각각의 클러스터를 포함하는 상기 구조적 요소 중 하나를 결정하기 위한 명령어, 및 상기 결정된 구조적 요소 중 하나 이상에 관한 정보를 표시하기 위한 명령어를 포함할 수 있다.

본 명세서에 통합되어 본 명세서의 일부를 구성하는 첨부도면은 본 발명의 실시예를 예시한 것이고, 설명서(description)와 함께 본 발명을 설명한다.

도 1은 문서의 일례를 나타낸 도면이다.

도 2는 문서의 구조적 요소의 일례를 나타낸 도면이다.

도 3은 본 발명의 원리에 부합하는 시스템 및 방법을 구현할 수 있는 정보 검색 네트워크의 일례를 나타낸 도면이다.

도 4는 본 발명의 원리에 부합하는 실시예에 따른 클라언트 또는 서버의 일례를 나타낸 도면이다.

도 5는 본 발명의 원리에 부합하는 실시예에 따른 도 4의 검색엔진의 일례의 기능 블록도이다.

도 6a 및 도 6b는 검색 결과에 포함하기 위해 구조적 요소가 어떻게 식별될 수 있는지를 설명하기 위한 문서 내의 히트 분포의 일례를 나타낸 것이다.

도 7 내지 도 9b는 본 발명의 원리에 부합하는 실시예에 따른 검색 결과를 표시하기 위한 처리의 일례를 나타낸 흐름도이다.

도 10a 내지 도 10d는 책에 대한 검색 결과의 일례를 나타낸 것이다.

본 발명과 일치하는 실시예에 대한 다음의 상세한 설명은 첨부도면을 참조한다. 상이한 도면 중의 동일한 도면부호는 동일 또는 유사한 구성요소로 간주할 수 있다. 또한, 이하의 상세한 설명이 본 발명을 한정하는 것은 아니다.

개요

검색 엔진을 통해 갈수록 많은 타입의 문서를 검색가능하게 되고 있다. 몇몇 타입의 문서는 파트(part), 챕터(chapter), 섹션(section), 페이지(page) 등의 구조적 요소의 세트를 포함하는 점에서 구조화되어 있다. 이러한 타입의 문서의 예로는 책, 웹 사이트, 잡지, 신문, 기사(article), 특허문헌(patent), 및 카탈로그를 들 수 있다. 이 문서들은 스캐닝되어, OCR(Optical Character Recognition )을 통해 인식되는 텍스트를 가질 수 있다.

도 1은 구조화된 문서의 일례를 나타낸 도면이다. 이 실시예에서, 문서는 책의 형태를 취한다. 이 책은 스캐닝되거나 아니면 전자적인 형태로 취득될 수 있다. 전형적인 책은 다수의 구조적 요소를 포함할 수 있다. 책의 구체적인 구조적 요소는 OCR에 의해 결정되거나, 출판업자에 의해 제공되거나, 다른 방법으로 취득될 수 있다.

도 2는 문서의 구조적 요소의 일례를 나타낸 도면이다. 도 2에 도시된 바와 같이, 구조적 요소는 계층 방식(hierarchical fashion)으로 배열될 수 있다. 도 2의 구조적 요소는 4개의 레벨로 배열될 수 있다 다른 실시예에서, 이 구조적 요소는 4개보다 더 많거나 적은 임의의 레벨로 배열될 수 있다.

도 2에 도시된 바와 같이, 최상위 레벨의 구조적 요소는 문서 자체를 포함할 수 있다. 그 다음으로 높은 레벨의 구조적 요소는 문서의 파트들을 포함할 수 있다. 책의 경우에, 이 파트는 책의 챕터에 대응할 수 있다. 웹 사이트의 경우에, 이 파트는 웹사이트의 구획(portion)에 대응할 수 있다. 기사(article)의 경우에, 이 파트는 기사의 섹션에 대응할 수 있다.

그 다음으로 높은 레벨의 구조적 요소는 문서의 서브파트(sub-part)들을 포함할 수 있다. 책의 경우에, 이 서브파트는 책의 서브챕터 또는 섹션에 대응할 수 있다. 웹 사이트의 경우에, 이 서브파트는 웹사이트의 소구획(sub-portion)에 대응할 수 있다. 기사의 경우에, 이 서브파트는 기사의 서브섹션에 대응할 수 있다. 계층 구조에서 그 다음으로 높은 레벨의 구조적 요소는 문서의 페이지들을 포함할 수 있다.

본 발명의 원리에 부합하는 시스템 및 방법은, 잠재적인 문서들(underlying documents) 및 그 문서 내의 히트의 분포와 연관된 구조적 요소에 기초하여 검색 결과를 표시할 수 있다.

대표적인 정보 검색 네트워크

도 3은 본 발명의 원리에 부합하는 시스템 및 방법을 구현할 수 있는 정보 검색 네트워크의 일례를 나타낸 도면이다. 네트워크(300)는, 네트워크(350)를 통해 다수의 서버(320-340)에 연결된 다수의 클라이언트(310)를 포함할 수 있다. 네트워크(350)는 LAN(Local Area Network), WAN(Wide Area Network), PSTN(Pubic Switched Telephone Network)과 같은 전화망, 인트라넷, 인터넷, 메모리 디바이스, 또는 네트워크들의 조합을 포함할 수 있다. 간결하게, 두 개의 클라이언트(310)와 세 개의 서버(320-340)가 네트워크(350)에 연결되어 있는 것으로 도시하였다. 실제로는 더 많거나 더 적은 클라이언트와 서버가 있을 수 있다. 또한, 어떤 경우에는 클라이언트가 서버의 기능을 수행할 수 있고/있거나, 서버가 클라이언트의 기능을 수행할 수도 있다.

클라이언트(310)는 클라이언트 엔티티(entity)들을 포함할 수 있다. 엔티티는 개인용 컴퓨터, 무선 전화, 개인용 휴대 정보 단말기(personal digital assistant, PDA), 랩톱 컴퓨터와 같은 디바이스, 또는 다른 타입의 계산 디바이스나 통신 디바이스; 이들 디바이스 상에서 실행되는 스레드(thread)나 프로세스(process); 및/또는 이들 디바이스 중 하나에 의해 실행 가능한 객체(object)를 포함할 수 있다. 서버(320-340)는 본 발명의 원리에 부합하는 방법으로 문서를 수집, 처리, 검색, 및/또는 유지하는 서버 엔티티들을 포함할 수 있다. 클라이언트(310) 및 서버(320-340)는 유선, 무선, 및/또는 광학적 연결을 통해 네트워크(350)와 접속할 수 있다.

본 발명의 원리에 부합하는 실시예에서, 서버(320)는 클라이언트(310)에 의해 사용될 수 있는 검색 엔진(325)을 포함할 수 있다. 서버(320)는 문서들의 코퍼스(예컨대, 스캐닝 또는 크롤링(crawling)에 의해), 문서들의 인덱스, 및 문서들의 저장소 내에 있는 문서들과 연관된 저장 정보를 식별할 수있다. 서버(330, 340)는 웹 페이지 도는 웹 사이트와 같은, 문서를 저장하거나 유지할 수 있다. 서버(320-340)는 개별 엔티티로 도시되어 있지만, 다른 하나 이상의 서버(320-340)의 하나 이상의 기능을 수행하는 것도 가능할 수 있다. 둘 이상의 서버(320-340)를 단일 서버로 구현하는 것이 가능할 수 있다. 또한 단일의 서버(320-340)를 둘 이상의 개별( 및 어쩌면 분산된) 디바이스로 구현되도록 할 수 있다.

대표적인 클라이언트/서버 아키텍처

도 4는 본 발명의 원리에 부합하는 실시예에 따른, 하나 이상의 클라이언트(310)와 서버(320-340)에 대응할 수 있는 클라이언트 또는 서버 엔티티(이하, "클라이언트/서버 엔티티" 라 함)의 일례를 나타낸 도면이다. 클라이언트/서버 엔티티는 버스(410), 프로세서(420), 주 메모리(430), ROM(Read Only Memory)(440), 스토리지 디바이스(450), 입력 디바이스(460), 출력 디바이스(470), 및 통신 인터페이스(480)를 포함할 수 있다. 버스(410)는 클라이언트/서버 엔티티의 구성요소 사이의 통신을 가능하게 하는 경로(path) 포함할 수 있다.

프로세서(420)는 명령어를 해석하고 실행하는, 종래의 프로세서 또는 마이크로프로세서 또는 프로세싱 로직(processing logic)을 포함할 수 있다. 주 메모리(430)는 프로세서(420)에서 실행하기 위한 정보 및 명령어를 저장하는 RAM(Random Access Memory) 또는 다른 타입의 동적 스토리지 디바이스(dynamic storage device)를 포함할 수 있다. ROM(440)은 프로세서(420)에 의해 사용되는 정적인 정보를 기억하는 종래의 ROM 디바이스 또는 다른 타입의 정적 스토리지 디바이스를 포함할 수 있다. 스토리지 디바이스(450)는 자기 기록 매체 및/또는 광학 기록 매체와 그에 대응하는 드라이브를 포함할 수 있다.

입력 디바이스(460)는 키보드, 마우스, 펜, 음성 인식(voice recognition) 장치 및/또는 바이오메트릭(biometric) 장치 등과 같이, 사용자가 클라이언트/서버 엔티티에 정보를 입력할 수 있도록 해주는 종래의 장치를 포함할 수 있다. 출력 디바이스(470)는 디스플레이, 프린터, 스피커 등을 포함하는, 사용자에게 정보를 출력하는 종래의 장치를 포함할 수 있다. 통신 인터페이스(480)는 클라이언트/서버 엔티티가 다른 디바이스 및/또는 시스템과 통신할 수 있도록 해주는 송수신기형(transceiver-like) 장치를 포함할 수 있다. 예를 들면, 통신 인터페이스(480)는 네트워크(350)와 같은, 네트워크를 통해 다른 디바이스나 시스템과 통신하는 장치를 포함할 수 있다.

이하에 상세하게 설명하는 바와 같이, 본 발명의 원리에 부합하는 클라이언트/서버 엔티티는 일정한 검색 관련 동작을 수행할 수 있다. 클라이언트/서버 엔티티는 주 메모리(430)와 같은, 컴퓨터로 판독가능한 매체(computer-readable medium)에 저장된 소프트웨어 명령어를 실행하는 프로세서(420)에 응답하여 이 동작을 수행할 수 있다. 컴퓨터로 판독 가능한 매체는 물리 또는 논리 메모리 디바이스 및/또는 반송파(carrier wave, 搬送波)로 규정될 수 있다.

소프트웨어 명령어는 데이터 스토리지 디바이스(450)와 같은, 컴퓨터로 판독가능한 매체로부터, 또는 통신 인터페이스(480)를 통해 다른 디바이스로부터 주 메모리(430)로 읽어들일 수 있다. 주 메모리(430)에 저장된 소프트웨어 명령어는 프로세서(420)로 하여금 상세하게 후술할 프로세스들을 수행하도록 한다. 다르게는, 소프트웨어 명령어 대신에 또는 소프트웨어 명령어와 결합하여 고정 배선 회로(hardwired circuitry)를 사용하여 본 발명의 원리에 부합하는 프로세스들을 실행할 수 있다. 따라서, 본 발명의 원리에 부합하는 실시예는 하드웨어 회로와 소프트웨어의 어떤 특정 조합으로 한정되는 것은 아니다.

대표적인 검색 엔진

도 5는 본 발명의 원리에 부합하는 실시예에 따른, 검색 엔진(235)와 같은, 검색엔진의 대표적인 기능 블록도이다. 일 실시예에 따르면, 서버(320)의 다른 부분, 또는 서버(320) 또는 서버(320)와 서버(340) 중 하나와 연관된 컴퓨터와 같은 서버(320)와 분리된 엔티티에 의해 후술하는 하나 이상의 기능을 수행할 수 있다.

검색 엔진(325)은 저장소(530)에 연결된 정보 검색 유닛(510)과 프리젠테이션 유닛(presentation unit)(520)을 포함할 수 있다. 저장소(530)는, 예를 들면 서버(320)(도 3 참조) 또는 서버(320)와 분리된 엔티티에 의해 크롤링 및 인덱싱된 문서와 연관된 정보를 저장하는 물리 또는 논리 메모리 디바이스를 포함할 수 있다. 문서 정보는 문서 컨텐츠 및 연관된 메타데이터(meatdata)를포함할 수 있다. 본 발명의 원리에 부합하는 실시예에서, 문서와 연관된 메타데이터는 문서와 연관된 구조적 요소에 관한 정보를 포함할 수 있다. 문서와 연관된 특정 구조적 요소 는 OCR에 의해 결정되거나, 출판업자에 의해 제공되거나, 다른 방법으로 취득될 수 있다.

정보 검색 유닛(510)은 사용자의 검색어에 따라 동작하여 그 검색어와 관련 있는 문서를 식별할 수 있다. 정보 검색 유닛(510)이 검색어의 세트와 관련된 문서를 식별하기 위해 사용할 수 있는 기술은 많이 있다. 예를 들면, 검색어의 세트가 단일 검색어를 포함하는 경우, 정보 검색 유닛(510)은 그 검색어를 포함하는 문서를 식별할 수 있다. 검색어가 다수의 검색어를 포함하는 경우, 정보 검색 유닛(510)은 그 검색 용어를 구(phrase)로서 포함하고 있는 문서를 식별할 수 있다. 이 대신에, 또는 이에 더해, 정보 검색 유닛(510)은 그 검색어 포함하되 반드시 함께는 포함하지 않는 문서를 식별할 수 있다. 이 대신에, 또는 이에 더해, 정보 검색 유닛(510)는 검색어 전부보다는 적은 검색어, 또는 검색어의 동의어를 포함하는 문서를 식별할 수 있다. 관련 문서를 식별하는 또 다른 기술들이 해당 기술분야의 당업자에게 알려져 있다.

프리젠테이션 유닛(520)은 검색어의 세트와 관련 있는 것으로 정보 검색 유닛(510)에 의해 식별된 문서를 분석할 수 있다. 예를 들면, 프리젠테이션 유닛(520)은 저장소(530) 내의 문서와 연관된 메타데이터로부터 문서와 연관된 구조적 요소를 식별할 수 있다. 프리젠테이션 유닛(520)은 또한 문서와 관련된 히트를 결정할 수 있다. 예를 들면, 프리젠테이션 유닛(520)은 문서의 컨텐츠 내에 검색어의 세트가 출현하는지를, 어떻게든지 문서의 구조적 요소에 관하여 결정할 수 있다.

일 실시예에서, 프리젠테이션 유닛(520)은 히트들을 그들의 물리적 근접도(physical proximity)에 기초하여 클러스터화(clustering)할 수 있다. 물리적 근접도는 클러스터링 근접도 임계값(clustering proximity threshold)에 기초하여 결정될 수 있다. 상기 임계값은 고정될 수 있다. 다르게는, 임계값은 문서, 문서의 파트, 문서의 서브파트 등의 페이지 수에 비례하여 설정될 수도 있다. 이 경우에,

임계값에 의해 나타나는 바와 같이, 히트가 발생한 페이지의 수가 파트 내의 총 페이지 수의 일정 퍼센트보다 많을 때, 문서의 동일한 파트 내에 있는 페이지에서의 히트들은 클러스터화될 수 있다. 또, 클러스터화는 단일 구조적 요소 내에 있는 클러스터를 다수의 구조적 요소 내에 있는 클러스터에 비해 우위로 하여 이루어질 수 있다. 각각의 클러스터에 대해, 프리젠테이션 유닛(520)은 클러스터 전부를 포함하는 최소의 구조적 요소를 결정하고, 이 구조적 요소를 검색 결과로서 표시할 수 있다.

도 6a는 검색 결과에 포함하기 위해, 구조적 요소가 어떻게 식별될 수 있는지를 설명하기 위한 문서 내의 히트 분포의 일례를 나타낸 것이다. 도 6a에 도시된 바와 같이, 히트는 페이지 10, 12, 15, 16, 18, 139, 및 211에서 발생한다. 상세하게는 도 6a에 도시된 바와 같이, 챕터 1에 있는 페이지 10, 12, 15, 16, 및 18; 챕터 5에 있는 페이지 139; 그리고 챕터 9에 있는 페이지 211에서 발생한다. 히트를 포함하는 페이지의 물리적 근접도에 기초하여, 3개의 클러스터를 형성할 수있다: {10, 12, 15, 16, 18}, {139}, 그리고 {211}. 첫 번째 클러스터 전부를 포 함하는 최소의 구조적 요소가 쳅터 1이 되도록, 두 번째 클러스터 전부를 포함하는 최소의 구조적 요소가 페이지 139가 되도록, 그리고 세 번째 클러스터 모두를 포함하는 최소의 구조적 요소가 페이지 211이 되도록 임계값이 설정된다고 가정하자. 따라서, 챕터 1, 페이지 139, 및 페이지 211에 관한 정보가 검색 결과로서 제공될 수 있다.

다른 실시예에서, 프리젠테이션 유닛(520)은 문서의 계층 구조의 트리 표현을 식별할 수 있고, 종단 노드(leaf node)는 페이지를, 상위 레벨 노드(higher level node)는 파트를(예를 들면, 챕터), 그리고 루트 노드(root node)는 문서 전체를 나타낼 수 있다. 프리젠테이션 유닛(520)은 히트를 포함하는 종단 노드를 잠재적인 결과로서 식별할 수 있다. 프리젠테이션 유닛(520)은 히트를 포함하는 종단 노드 각각에 스코어 1을, 그리고 히트를 포함하지 않는 종단 노드 각각에 스코어 0(영)을 할당할 수 있다. 다르게는, 히트를 포함하는 종단 노드에 할당되는 스코어는 1 이외의 어떤 것일 수 있다. 예를 들면, 이 스코어는 히트의 중요도(importance)의 함수일 수 있다. 중요도는 특정 페이지에서의 히트의 수 및/또는 페이지에서 히트가 발생한 장소(예를 들면, 굵은 표시(bold font)의 텍스트에서의 히트, 큰 사이즈의 텍스트에서의 히트, 및/또는 표제와 연관된 텍스트에서의 히트에 더 높은 스코어를 부여할 수 있다) 에 기초하여 결정될 수 있다.

스코어는 그 후, 각 노드의 스코어가 자식 노드의 스코어의 합을 포함할 수 있는 트리 위쪽으로 전파될 수 있다. 노드의 스코어가 임계값을 초과하면, 해당 노드는 잠재적인 결과로 선택되어 제공될 수 있으며, 이전에 선택되었던 자식 노드 들은 삭제될 수 있으며, 스코어 0(영)이 그 부모 노드로 전파될 수 있다. 그렇지 않으면, 노드는 자신의 스코어 전부를 부모 노드(만약, 존재한다면)까지 전파할 수 있다. 임계값은 고정되거나, 레벨이 지정(level-specific)되거나, 노드와 연관된 페이지 수의 함수일 수 있다.

도 6b는 검색 결과에 포함하기 위해, 구조적 요소가 어떻게 식별될 수 있는지를 설명하기 위한 문서 내의 히트 분포의 일례를 나타낸 것이다. 도 6b에 도시된 바와 같이, 히트는 페이지 10, 12, 15, 20, 56, 및 100에서 발생한다. 상세하게는 도 6b에 도시된 바와 같이, 챕터 1에 있는 페이지 10, 12, 15, 및 20; 챕터 2에 있는 페이지 56; 그리고 챕터 3에 있는 페이지 100에서 발생한다. 각각의 페이지는 자신의 스코어를 자신의 부모에게까지 전파한다. 부모(즉, 챕터)의 스코어는 페이지들의 스코어의 합이다. 이 경우에, 챕터 1의 스코어는 4, 챕터 2의 스코어는 1, 챕터 3의 스코어는 1, 그리고 챕터 N의 스코어는 0(영)이다.

임계값은 3으로 설정한다고 하자. 이 경우에, 챕터 1의 스코어는 임계값을 초과하므로, 잠재적인 결과로서 선택된다. 페이지 10, 12, 15, 및 20은 그 후에, 더이상 잠재적인 결과에 포함되지 않는다. 챕터 1이 잠재적인 결과로 선택되었기 때문에, 챕터 1은 자신의 부모(즉, 문서 전체)에 스코어 0을 전파한다. 챕터 2, 3, 및 N 각각은 임계값보다 작은 스코어를 가지므로, 자신의 스코어를 부모에게 전파한다. 부모(즉, 문서)의 스코어는 챕터들의 스코어의 합이다. 이 경우에, 문서는 스코어 2이고, 이는 임계값보다 작다. 따라서, 챕터 1, 페이지 56, 및 페이지 100에 관한 정보가 검색 결과로서 제공될 수 있다.

대표적인 처리

도 7 내지 도 9b는 본 발명의 원리에 부합하는 실시예에 따른 검색 결과를 표시하기 위한 처리를 나타낸 흐름도이다. 처리는 사용자가 문서 코퍼스를 검색하기 위해 검색 질의로서 검색어를 제공함으로써 시작될 수 있다. 일 실시예에서, 문서 코퍼스는 인터넷으로부터 입수가능한 문서들을 포함할 수 있고, 이 코퍼스를 검색하기 위한 수단(vehicle)은 검색 엔진(235)(도 3)과 같은, 검색 엔진이다. 사용자는 클라이언트(310)(도 3)와 같은, 클라이언트 상의 웹 브라우저를 통해 검색 질의를 제공할 수 있다.

이 검색 질의는 검색 엔진에 의해 수신되고, 검색 질의와 관련된 문서(예: 책, 웹 사이트, 신문, 기사, 특허문헌, 또는 기타 타입의 구조화된 문서)를 식별하는데 사용될 수 있다(행위 710 및 720)(도 7 참조). 검색 질의에 관련된 문서를 식별하기 위한 많은 기술이 존재한다. 그러한 기술 중 하나는 구(phrase)로서 검색어를 포함하는 문서를 식별하는 것을 포함할 수 있다. 다른 기술은 검색어들을 포함하되, 반드시 함께는 포함하지 않는 문서를 식별하는 것을 포함할 수 있다. 다른 기술들은 검색어 전부보다는 적은 검색어, 또는 검색어의 동의어를 포함하는 문서를 식별하는 것을 포함할 수 있다. 또 다른 기술들이 해당 기술분야의 당업자에게 알려져 있다.

히트(문서 컨텐츠 내에 검색어의 출현)를 결정할 수 있다(행위 730). 예를 들면, 문서의 구조적 요소에 대해, 문서 내에서 검색어가 출현하는 장소를 식별하기 위해, 문서 컨텐츠를 검색할 수 있다. 예를 들면, 파트, 서브파트, 및/또는 페 이지에서 검색어가 출현하였는지를 결정할 수 있다.

그 후, 표시하기 위한 구조적 요소(들)를 식별할 수 있다(행위 740). 일 실시예에 따르면, 히트가 발생한 페이지의 근접도에 기초하여 히트를 클러스터화할 수 있다(행위 810)(도 8). 전술한 바와 같이, 근접도는, 예를 들면 두 페이지가 얼마나 가까우면 클러스터화 하여야 하는지 및/또는 구조적 요소에 대한 클러스터화에 바이어스(bias)를 부여할 것인지를 지정하는 클러스터화 근접도 임계값에 기초하여 결정될 수 있다. 각각의 클러스터에 대해, 모든 클러스터를 포함하는 최소의 구조적 요소를 식별할 수 있으며, 이 구조적 요소가 문서 전체인지, 파트인지, 서브파트인지, 또는 페이지인지를 식별할 수 있다.

다른 실시예에 따르면, 종단 노드가 페이지를 나타낼 수 있고, 상위 레벨 노드가 파트, 서브파트 등을 나타낼 수 있으며, 루트 노드가 문서 전체를 나타낼 수 있는, 문서의 계층 구조의 트리 표현을 결정할 수 있다(행위 905)(도 9a). 히트를 포함하는 종단 노드는 잠재적인 결과로서 선택될 수 있다(행위 910).

그 후, 각 종단 노드에 스코어를 할당할 수 있다(행위 915). 일 실시예에서, 히트를 포함하는 종단 노드는 스코어 1이 할당될 수 있고, 히트를 포함하지 않는 종단 노드는 스코어 0이 할당될 수 있다. 다른 실시예에서, 히트를 포함하는 종단 노드에 할당된 스코어는 전술한 바와 같이, 히트의 중요도의 함수일 수 있다.

그 후 트리의 부모 노드까지 스코어를 전파할 수 있다(행위 920). 부모 노드에 대한 스코어를 결정할 수 있다(행위 925). 일 실시예에서, 부모 노드의 스코어는 그 자식들의 스코어 합을 포함할 수 있다. 부모 노드의 스코어를 임계값과 비교할 수 있다. 만약 부모 노드의 임계값이 임계값을 초과하지 않으면(행위 930), 부모 노드 자체가 부모 노드를 가지는지를 결정할 수 있다(행위 935). 만약 그러한 부모 노드가 존재하면, 처리는 행위 920으로 되돌아 가서, 해당 노드는 자신의 스코어를 그 부모 노드까지 전파한다.

만약 부모 노드의 스코어가 임계값을 초과하면(단계 930), 해당 노드를 잠재적인 결과로서 선택할 수 있다(행위 940)(도 9b). 그 후 이전에 선택된 모든 자식 노드를 잠재적인 결과의 그룹에서 삭제할 수 있다(행위 945). 그 다음에 부모 노드 자신이 부모 노드를 가지는지를 결정할 수 있다(행위 950). 만약 그러한 부모 노드가 존재하면, 해당 노드는 스코어 0을 자신의 부모 노드에 전파할 수 있다(행위 955). 그 후 처리는 행위 925로 되돌아가서, 부모 노드(들)의 스코어를 결정한다. 만약 부모 노드가 더 존재하지 않으면(행위 935 또는 950), 잠재적인 결과로서 선택된 노드에 대응하는 구조적 요소를 식별할 수 있다(행위 960).

그 후에, 각각의 문서에 대해 식별된 구조적 요소(들)에 기초하여 검색 결과를 구성할 수 있다(행위 750)(도 7). 다시 말해, 어떤 상황에서는, 문서와 연관된 검색 결과는 문서 전체, 문서의 파트, 문서의 서브파트, 또는 문서 내의 페이지와 연관된 정보를 포함할 수 있다. 문서 전체와 연관된 정보는 (검색어가 표제 페이지에 나타나지 않더라도) 문서의 표제 페이지(또는 표지)를 포함할 수 있다. 문서의 파트 또는 서브파트와 연관된 정보는 (검색어가 파트 또는 서브파트의 첫 페이지에 나타나지 않더라도) 파트 또는 서브파트의 첫 페이지를 포함할 수 있다. 문서 내의 페이지와 연관된 정보는 페이지 자체(또는 페이지의 일부분)을 포함할 수 있다.

검색 결과에 스코어를 부여하고, 그 스코어에 기초하여 검색 결과를 정렬할 수 있다. 검색 결과는 종래의 검색 엔진에 의해 제공된 검색 결과와 유사하게 HTML 문서로 제공될 수 있다. 다르게는, 검색 결과는 검색 엔진 및 클라이언트가 합의한 포맷(예: XML, Extensible Markup Language)에 따라 제공될 수 있다.

도 10a 내지 도 10d는 책에 대한 검색 결과의 일례를 나타낸 것이다. 도 10a는 책의 표시를 나타낸 것이다. 책의 표지는 검색 질의(예: "memory")와 관련 있는 것으로 결정된 책 전체를 나타내기 위해 표시될 수 있다. 도 10b는 이 책의 챕터 3의 첫 페이지를 나타낸 것이다. 챕터의 첫 페이지는, 도 10b에 도시된 바와 같이 이 페이지에 검색어 "memory"가 나타나 있지 않지만, 검색 질의 와 관련 있는 것으로 결정된 챕터 전제를 나타내기 위해 표시될 수 있다. 도 10c는 책의 챕터 4의 첫 페이지를 나타낸 것이다. 이 경우에, 검색어는 페이지에 나타나 있다. 도 10d는 책의 페이지 52를 나타낸 것이다. 선택적으로, 검색으로 사용자가 페이지의 텍스트에서 용어를 쉽게 식별할 수 있도록 소정의 방식으로 강조(highlight)될 수 있다.

결론

본 발명의 원리에 부합하는 시스템 및 방법은, 잠재적인 문서들(underlying documents) 및 그 문서 내의 히트 분포와 연관된 구조적 요소에 기초하여 검색 결과를 생성할 수 있다.

본 발명의 실시예들에 대한 이상의 설명은, 본 발명에 대한 설명을 제공하지 만, 본 발명을 개시된 바로 그 형태로 총망라한 것으로 의도하거나, 본 발명을 한정하려는 의도는 아니다. 이상의 교시에 비추어 또는 본 발명의 실시로부터 변경 및 변형이 가능하다.

예를 들면, 도 7 내지 도 9b와 관련하여 일련의 행위를 설명하였지만, 본 발명의 원리에 부합하는 다른 실시예들에서 상기 행위들의 순서는 바뀔 수 있다. 또 비종속적인 행위들은 병행하여 실행될 수 있다.

일 실시예에서, 서버는 도 7 내지 도 9b의 처리와 관해 설명한 행위의 전부는 아니지만 대부분을 수행할 수 있다. 본 발명의 원리에 부합하는 다른 실시예에서, 하나 이상의 행위 또는 행위 전부를 다른 서버(330) 및/또는 서버 (340) 또는 클라이언트(310)와 같은, 다른 엔티티에 의해 수행할 수 있다.

이상에서 설명한 바와 같은 본 발명의 실시양태들이, 도면에 예시된 실시예에서 여러 상이한 형태의 소프트웨어, 펌웨어, 및 하드웨어로 구현될 수 있다는 것은 이 기술분야의 당업자에게 명백할 것이다. 본 발명의 특징을 구현하는데 이용되는 실제의 소프트웨어 코드 또는 전용(specialized)의 제어 하드웨어는 본 발명의 범위를 제한하지 않는다. 따라서, 본 발명의 특징에 대한 동작 및 작용을 특별한 소프트웨어 코드를 참조하지 않고 설명하였으며, 당업자라면, 본 명세서의 상세한 설명에 기초하여 본 발명의 특징을 구현하기 위해 소프트웨어 및 제어 하드웨어를 설계할 수 있다는 것을 알 것이다.

본 출원의 설명에서 사용된 요소(element), 행위(act), 명령어(instruction)는 그러한 것으로 명백히 기술되지 않는 한, 본 발명에서 결정적이거나 필수적인 것으로 해석되어서는 안 된다. 또한, 여기에서 사용된 바와 같이, 관사 "a"는 하나 이상의 아이템을 포함하는 것으로 의도된다. 오직 하나의 아이템이 의도되는 경우, 용어 "하나(one)" 또는 유사한 표현을 사용한다. 또, 구 "...에 기초하여(based on)"는 명백히 다르게 나타내지 않는 한 "적어도 일부는 ...에 기초하여"를 의미하는 것으로 의도된다.

Claims

검색의 결과인 문서를 표시하는 방법으로서,

복수의 구조적 요소(structural element)를 포함하는, 검색어(search term)와 관련된 문서를 식별하는 단계;

상기 문서에서 상기 검색어가 출현하는 페이지를 결정하는 단계;

상기 문서에서의, 상기 검색어가 출현하는 페이지들을, 상기 검색어가 출현하는 페이지들간의 물리적 근접도(phisical proximity)에 기초하여, 적어도 하나의 클러스터로 분류하는 단계;

하나 이상의 상기 클러스터를 포함하는 상기 구조적 요소 중 하나를 식별하는 단계; 및

상기 식별된 구조적 요소 중 하나와 연관된 정보를 표시하는 단계

를 포함하는, 검색의 결과인 문서를 표시하는 방법.
제1항에 있어서,

상기 문서를 식별하는 단계는, 상기 검색어와 관련된 문서를 식별하기 위해 문서의 코퍼스(corpus)를 검색하는 단계를 포함하는, 검색의 결과인 문서를 표시하는 방법.
제1항에 있어서,

상기 문서는 책, 웹사이트, 신문, 기사(article), 또는 특허문헌(patent) 중 하나를 포함하는, 검색의 결과인 문서를 표시하는 방법.
제1항에 있어서,

상기 문서에서 상기 검색어가 출현하는 페이지를 결정하는 단계는, 상기 문서의 구조적 요소별로 상기 문서에서 상기 검색어가 출현하는 페이지를 식별하기 위해 상기 문서의 컨텐츠를 검색하는 단계를 포함하는, 검색의 결과인 문서를 표시하는 방법.
제4항에 있어서,

상기 구조적 요소 중 하나를 식별하는 단계는, 각각의 클러스터를 포함하는 상기 구조적 요소 중 가장 작은 것을 결정하는 단계를 포함하는, 검색의 결과인 문서를 표시하는 방법.
제1항에 있어서,

상기 구조적 요소 중 하나를 식별하는 단계는, 각각의 클러스터를 포함하는 상기 구조적 요소 중 가장 작은 것을 결정하는 단계를 포함하는, 검색의 결과인 문서를 표시하는 방법.
제6항에 있어서,

상기 정보를 표시하는 단계는, 상기 구조적 요소 중 가장 작은 것과 연관된 정보에 기초하여 검색 결과를 생성하는 단계를 포함하는, 검색의 결과인 문서를 표시하는 방법.
제1항에 있어서,

상기 검색어가 출현하는 두 개의 페이지가, 클러스터화되기 위한 물리적 근접도로서 어느 정도 근접해야 하는지를 지정하는 임계값을 제공하는 단계를 더 포함하고,

상기 검색어가 출현하는 페이지들을 클러스터로 분류하는 것은 상기 임계값에 기초하여 수행되는, 검색의 결과인 문서를 표시하는 방법.
제8항에 있어서,

상기 임계값은 상기 문서의 페이지 수에 비례하는, 검색의 결과인 문서를 표시하는 방법.
제1항에 있어서,

상기 클러스터로 분류하는 단계는, 하나의 구조적 요소 내에 있는 클러스터를 복수의 구조적 요소에 걸쳐 있는 클러스터보다 우위(favor)에 두는, 검색의 결과인 문서를 표시하는 방법.
제1항에 있어서,

상기 문서는 책이고,

상기 구조적 요소는 상기 책, 상기 책의 챕터(chaper)의 세트, 및 상기 책의 페이지의 세트를 포함하는, 검색의 결과인 문서를 표시하는 방법.
제1항에 있어서,

상기 구조적 요소는 상기 문서, 상기 문서의 파트(part)의 세트, 및 상기 문서의 페이지의 세트를 포함하고,

상기 식별된 구조적 요소 중 하나에 연관된 정보는, 상기 문서가 식별된 구조적 요소 중 하나인 경우에 상기 문서의 표제 페이지(title page)인, 검색의 결과인 문서를 표시하는 방법.
제1항에 있어서,

상기 구조적 요소는 상기 문서, 상기 문서의 파트의 세트, 및 상기 문서의 페이지의 세트를 포함하고,

상기 식별된 구조적 요소 중 하나에 연관된 정보는, 상기 파트가 상기 식별된 구조적 요소 중 하나인 경우에 상기 파트의 첫 페이지인, 검색의 결과인 문서를 표시하는 방법.
제1항에 있어서,

상기 구조적 요소는 상기 문서, 상기 문서의 파트의 세트, 및 상기 문서의 페이지의 세트를 포함하고,

상기 식별된 구조적 요소 중 하나에 연관된 정보는, 상기 페이지가 상기 식별된 구조적 요소 중 하나인 경우에 상기 문서의 상기 페이지인, 검색의 결과인 문서를 표시하는 방법.
제1항에 있어서,

상기 식별된 구조적 요소 중 하나에 연관된 정보는, 상기 검색어가 출현하는 페이지를 포함하는 상기 문서의 일부를 포함하는, 검색의 결과인 문서를 표시하는 방법.
제1항에 있어서,

상기 식별된 구조적 요소 중 하나에 연관된 정보는, 상기 검색어가 출현하는 페이지를 포함하지 않는 상기 문서의 일부를 포함하는, 검색의 결과인 문서를 표시하는 방법.
제1항에 있어서,

상기 식별된 구조적 요소 중 하나에 연관된 정보를 표시하는 단계는, 상기 식별된 구조적 요소 중 하나에 연관된 정보 내에서 상기 검색어를 시각적으로 구별시키는 단계를 포함하는, 검색의 결과인 문서를 표시하는 방법.
삭제
삭제
삭제
삭제
삭제
삭제
검색의 결과인 문서를 표시하는 시스템으로서,

복수의 구조적 요소를 포함하는, 검색어와 관련된 문서를 취득하는 수단;

상기 구조적 요소에 대해 상기 문서에서의 상기 검색어가 출현하는 페이지를 식별하는 수단;

상기 문서에서의, 상기 검색어가 출현하는 페이지들을, 상기 검색어가 출현하는 페이지들간의 물리적 근접도에 기초하여, 클러스터로 분류하는 수단;

각각의 클러스터를 포함하는 상기 구조적 요소 중 하나를 식별하는 수단; 및

상기 검색어가 출현하는 페이지들 중 하나와 연관된 상기 식별된 구조적 요소 중 하나에 관한 정보를 표시하는 수단

을 포함하는, 검색의 결과인 문서를 표시하는 시스템.
검색의 결과인 문서를 표시하는 시스템으로서,

문서들 중 적어도 일부는 복수의 구조적 요소를 포함하는 상기 문서들의 코퍼스를 저장하는 메모리; 및

프로세서

를 포함하고,

상기 프로세서는,

검색어를 포함하는 검색 질의를 수신하고,

상기 검색어와 관련된, 상기 문서의 코퍼스 내의 문서를 식별하며,

상기 구조적 요소에 기초하여 상기 문서 내에서 상기 검색어가 출현하는 페이지를 결정하고,

상기 문서에서의, 상기 검색어가 출현하는 페이지들을, 상기 검색어가 출현하는 페이지들간의 물리적 근접도에 기초하여, 클러스터로 분류하며,

각각의 클러스터를 포함하는 상기 구조적 요소 중 하나를 식별하고,

상기 식별된 구조적 요소와 연관된 정보를 상기 검색 질의에 대한 결과로서 제공하는,

검색의 결과인 문서를 표시하는 시스템.
검색의 결과인 문서를 표시하는 방법으로서,

복수의 구조적 요소를 포함하는, 검색어와 관련된 문서를 식별하는 단계;

상기 문서에서의 상기 검색어가 출현하는 페이지를 결정하는 단계;

상기 검색어가 출현하는 페이지들간의 물리적 근접도에 기초하여 상기 검색어가 출현하는 페이지들을 클러스터로 분류하는 단계;

각각의 클러스터를 포함하는 상기 구조적 요소 중 가장 작은 것을 결정하는 단계; 및

상기 결정된 구조적 요소에 관한 정보를 제공하는 단계

를 포함하는, 검색의 결과인 문서를 표시하는 방법.
제26항에 있어서,

상기 검색어가 출현하는 두 개의 페이지가, 클러스터화되기 위한 물리적 근접도로서 어느 정도 근접해야 하는지를 지정하는 임계값을 제공하는 단계를 더 포함하고,

상기 검색어가 출현하는 페이지들을 클러스터로 분류하는 것은 상기 임계값에 기초하여 수행되는, 검색의 결과인 문서를 표시하는 방법.
제27항에 있어서,

상기 임계값은 상기 문서의 페이지 수에 비례하는, 검색의 결과인 문서를 표시하는 방법.
제26항에 있어서,

상기 클러스터로 분류하는 단계는, 하나의 구조적 요소 내에 있는 클러스터를 복수의 구조적 요소에 걸쳐 있는 클러스터에 비해 우위에 두는, 검색의 결과인 문서를 표시하는 방법.
검색의 결과인 문서를 표시하는 시스템으로서,

복수의 구조적 요소를 포함하는, 검색어와 관련된 문서를 식별하는 수단;

상기 문서 내에서의 상기 검색어가 출현하는 페이지를 식별하는 수단;

상기 검색어가 출현하는 두 개의 페이지가, 클러스터화되기 위한 물리적 근접도로서 어느 정도 근접해야 하는지를 지정하는 임계값에 기초하여 상기 검색어가 출현하는 페이지들을 클러스터로 분류하는 수단;

각각의 상기 클러스터를 포함하는 상기 구조적 요소 중 가장 작은 것을 결정하는 수단; 및

상기 가장 작은 구조적 요소에 관한 정보를 표시하는 수단을 포함하는, 검색의 결과인 문서를 표시하는 시스템.
검색의 결과인 문서를 표시하는 방법으로서,

문서, 상기 문서의 파트의 세트, 및 상기 문서의 페이지의 세트를 포함하는 복수의 구조적 요소를 포함하는, 검색어와 관련된 문서를 식별하는 단계;

상기 문서의 페이지는 종단 노드에 대응하고, 상기 문서의 파트는 상위 레벨 노드에 대응하며, 상기 문서는 루트 노드에 대응하는, 문서의 트리 표현을 식별하는 단계;

상기 종단 노드가 상기 검색어의 출현을 포함하는지에 기초하여 상기 종단 노드에 스코어를 할당하는 단계;

상기 종단 노드 중 연관된 종단 노드에 기초하여 상위 레벨 노드에 대한 스코어를 결정하는 단계;

상기 상위 레벨 노드에 대한 스코어에 기초하여 상기 루트 노드의 스코어를 결정하는 단계;

상기 종단 노드의 스코어, 상기 상위 레벨 노드의 스코어, 및 상기 루트 노드의 스코어에 기초하여, 상기 종단 노드 중 하나, 상기 상위 레벨 노드 중 하나, 또는 상기 루트 노드를 선택된 노드로서 선택하는 단계; 및

상기 선택하는 단계에서 선택된 상기 선택된 노드에 관한 정보를 제공하는 단계

를 포함하는, 검색의 결과인 문서를 표시하는 방법.
제31항에 있어서,

임계값을 제공하는 단계를 더 포함하고;

상기 종단 노드 중 하나, 상기 상위 레벨 노드 중 하나, 또는 상기 루트 노드를 선택하는 단계는,

상기 검색어의 출현을 포함하는 상기 종단 노드 중 하나를 잠재적인 결과로서 선택하는 단계;

상기 상위 레벨 노드의 스코어가 상기 임계값보다 더 높은 경우에, 상기 상위 레벨 노드 중 하나를 잠재적인 결과로서 선택하는 단계; 및

상기 루트 노드의 스코어가 상기 임계값보다 더 높은 경우에, 상기 루트 노드를 잠재적인 결과로서 선택하는 단계를 더 포함하는, 검색의 결과인 문서를 표시하는 방법.
제32항에 있어서,

상기 임계값은, 상기 임계값이 상기 종단 노드와 연관된 것인지, 상기 상위 레벨 노드와 연관된 것인지, 또는 상기 루트 노드와 연관된 것인지에 기초하여 설정되는, 검색의 결과인 문서를 표시하는 방법.
제32항에 있어서,

상기 임계값은, 상기 종단 노드, 상기 상위 레벨 노드, 또는 상기 루트 노드 중 하나와 연관된 페이지 수에 기초하여 설정되는, 검색의 결과인 문서를 표시하는 방법.
제32항에 있어서,

상기 종단 노드 중 하나 또는 상기 상위 레벨 노드 중 하나 또는 상기 루트 노드를 선택하는 단계는,

상기 상위 레벨 노드가 잠재적인 결과로서 선택된 경우에, 상기 상위 레벨 노드와 연관된 종단 노드의 선택을 삭제하는 단계; 및

상기 루트 노드가 잠재적인 결과로서 선택된 경우에, 상기 종단 노드 및 상기 상위 레벨 노드의 선택을 삭제하는 단계를 더 포함하는, 검색의 결과인 문서를 표시하는 방법.
제31항에 있어서,

상기 종단 노드에 스코어를 할당하는 단계는,

상기 검색어의 출현을 포함하지 않는 종단 노드에 스코어 0(영)을 할당하는 단계; 및

상기 검색어의 출현을 포함하는 종단 노드에 스코어 1을 할당하는 단계를 포함하는, 검색의 결과인 문서를 표시하는 방법.
제31항에 있어서,

상기 종단 노드에 스코어를 할당하는 단계는,

상기 검색어의 출현을 포함하지 않는 종단 노드에 스코어 0(영)을 할당하는 단계; 및

상기 검색어의 출현을 포함하는 종단 노드에, 상기 검색어의 출현의 중요도(importance)의 함수인 스코어를 할당하는 단계를 포함하는, 검색의 결과인 문서를 표시하는 방법.
제31항에 있어서,

상기 선택된 노드에 관련된 정보는, 상기 문서가 상기 선택된 노드인 경우에 상기 문서의 표제 페이지인, 검색의 결과인 문서를 표시하는 방법.
제31항에 있어서,

상기 선택된 노드에 관련된 정보는, 상기 파트가 상기 선택된 노드인 경우에 상기 파트의 첫 페이지인, 검색의 결과인 문서를 표시하는 방법.
제31항에 있어서,

상기 선택된 노드에 관련된 정보는, 상기 페이지가 상기 선택된 노드인 경우에 상기 문서의 페이지인, 검색의 결과인 문서를 표시하는 방법.
검색의 결과인 문서를 표시하는 시스템으로서,

검색어와 관련된 문서를 식별하는 수단;

상기 문서의 페이지는 종단 노드에 대응하고, 상기 문서의 파트는 상위 레벨 노드에 대응하며, 상기 문서는 루트 노드에 대응하는, 상기 문서의 트리 표현을 식별하는 수단;

상기 종단 노드가 상기 검색어의 출현을 포함하는지에 기초하여 상기 종단 노드에 스코어를 할당하는 수단;

상기 종단 노드 중 연관된 종단 노드의 스코어에 기초하여 상위 레벨 노드에 대한 스코어를 결정하는 수단;

상기 상위 레벨 노드에 대한 스코어에 기초하여 상기 루트 노드의 스코어를 결정하는 수단;

임계값을 제공하는 수단;

상기 스코어 및 임계값에 기초하여, 상기 종단 노드 중 하나 또는 상기 상위 레벨 노드 중 하나 또는 상기 루트 노드를 선택된 노드로서 선택하는 수단; 및

상기 선택하는 수단에 의해 선택된 상기 선택된 노드에 관한 정보를 제공하는 수단

을 포함하는, 검색의 결과인 문서를 표시하는 시스템.
컴퓨터로 실행가능한 명령어들을 포함하는, 검색의 결과인 문서를 표시하는, 컴퓨터로 판독가능한 메모리 디바이스로서,

복수의 구조적 요소를 포함하는, 검색어와 관련된 문서를 결정하기 위한 명령어;

상기 문서에서의 상기 검색어의 출현을 결정하기 위한 명령어;

상기 검색어의 출현의 물리적 근접도에 기초하여 상기 검색어의 출현을 클러스터로 분류하기 위한 명령어;

각각의 클러스터를 포함하는 상기 구조적 요소 중 하나를 결정하기 위한 명령어; 및

상기 결정된 구조적 요소 중 하나 이상에 관한 정보를 표시하기 위한 명령어

를 포함하는, 컴퓨터로 판독가능한 메모리 디바이스.