휴, 간만에 올립니다...
올리는 주기를 보니 주말을 제외하고 4~5일에 한 번씩 올리는군요..
좀 더 속도를 내고 싶지만, 여건이 제한되어져 있어서...
1.3 Processing Boolean queries
우리는 역색인과 기본 Boolean 검색 모델을 이용하여 질의어를 어떻게 처리할까? 간단한 결합 질의(conjunctive query)를 처리하는 것을 고려해보자.
(1.1) Brutus AND Calpurnia
위 역색인은 부분적으로 페이지 6의 그림 1.3에서 보여준다.
1. dictionary에서 Brutus를 찾는다.
2. Brutus와 관련된 posting을 검색한다.
3. dictionary에서 Calpurnia를 찾는다.
4. Calpurnia와 관련된 posting을 검색한다.
5. 그림 1.5에서 보여주는 것처럼 두 posting list에서 교집합을 구한다.
교집합 연산을 구하는 것은 중요하다. 우리는 2개의 term을 포함하고 있는 문서들을 빨리 찾을 수 있도록 하기 위해 posting list들을 효과적으로 교차 연산할 필요가 있다. (이 연산은 때론 posting list들을 합병하기 위해서도 참조가 되는데, 조금 직관적이지 않은 이런 이름은 일반적인 알고리즘 군에서는 각각의 포인터를 전진시키며 끼워 넣는 정렬된 리스트들을 결합시키는 term 합병 알고리즘이라는 이름으로 알려졌다. 여기서 우리는 논리적인 AND 연산을 가지고 리스트들을 합병하고 있다.)
그림 1.6에서 보면 합병 알고리즘을 사용해서 posting list들의 교차하는 간단하고 효과적인 방법이 있다. 우리는 2개의 리스트 포인터를 유지하고 2개의 posting list들의 모든 엔트리들을 선형적으로 동시에 순회한다. 각 단계에서 우리는 두 포인터가 가리키는 docID를 비교한다. 만약 그것들이 같다면, 결과 리스트에 해댱 docID를 삽입하고 두 포인터를 전진시킨다. 그렇지 않다면, 더 작은 docID를 가리키하는 포인터를 전진시킨다. 만일 posting list의 길이를 x와 y라고 한다면, 교집합의 복잡도는 O(x+y)를 가진다. 공식적으로 질의어의 복잡도는 Θ(N)이다. 여기서 N은 컬렉션에서의 문서 개수이다. 색인 방법은 상수를 획득한다. 선형 스캔과 비교하는 Θ 시간 복잡도에서의 차이가 아니라, 실제로 상수는 엄청 크다. Posting은 단독 전역 순서에 의해 정렬되어진다는 것은 중요하다. docID에 의한 숫자 정렬을 사용하는 것은 이러한 것들을 이루는 것에 대해서 하나의 간단한 방법이다.
우리는 다음과 같은 좀 더 복잡한 질의어를 처리하기 위해 교집합 연산을 확장할 수 있다.
(1.2) (Brutus OR Caeser) AND NOT Calpurnia
질의어 최적화는 답변 작업을 전체 작업량이 시스템에 의해 행해지는 것을 최소화하기 위해 어떻게 구조화할 것인가를 선택하는 과정이다. Boolean 질의어에 대한 주 요소는 어떤 posting list를 접근할 것인가에 대한 순서이다. 질의 처리에 대한 최선의 순서는 무엇인가? term들에 대한 AND 질의어를 고려하자. 예를 들면,
(1.3) Brutus AND Caeser AND Calpurnia
각 term들은 posting을 획득할 필요가 있고, 그것들 모두 AND 연산을 취한다. 표준적인 방법은 document frequency가 증가되는 순으로 term들을 처리하는 것이다. 만일 우리가 2개의 제일 작은 posting list들의 교차 작업을 시작한다면, 중간 산출물은 제일 작은 posting list보다 더 클 수 없는 것이 자명하고, 따라서 전체 작업량은 최소한으로 이루어질 거 같다. 그래서 페이지 6의 그림 1.3에서의 posting list들에서 우리는 아래의 질의어처럼 실행한다.
(1.4) (Calpurnia AND Brutus) AND Caeser
이것이 dictionary에서 term frequency를 가지는 첫 번째 이유이다. 어떤 posting list를 접근하기 전에 메모리상의 데이터에 기초하여 이러한 정렬을 위한 결정을 할 수 있게 해준다.
(1.5) (madding OR crowd) AND (ignoble OR strife) AND (killed OR slain)
이전에 처럼, 우리는 모든 term에 대해서 frequency들을 획득하고 그로 인해 따로 존재하는 frequency들의 합에 의해 각 OR의 사이즈를 예측할 수 있다. 떨어져 있는 각 term 사이즈의 증가 순에 의해 질의를 처리할 수 있다.
임의의 Boolean 질의어에 대해서 우리는 복합적인 표현으로부터 중간 표현에 대한 답을 일시적으로 평가하고 저장해야 한다. 그러나, 많은 상황에서 사용자가 던져주는 질의어는 자연어이거나 질의어의 가장 일반적인 형태이기 때문에 질의는 순수한 결합어이다. 이런 경우에 2개의 입력과 서로 다른 출력을 가진 기능으로서 posting list를 병합하여 보여주는 것보다 적어도 빈번한 term들의 posting list를 적재하여, 중간 결과물을 초기화할 수 있는 메모리상에서, 현재의 중간 결과를 가지고 검색되어진 각각의 posting list들간의 교집합을 구하는 것이 더 효과적이다. 이 알고리즘은 그림 1.7에서 보여준다.
교집합을 구하는 연산은 비대칭이다. 중간 결과물 리스트는 디스크로부터 읽어들이며 교집합을 구하는 동안 메모리상에 있다. 게다가 중간 결과물 리스트는 항상 최소한 다른 리스트만큼 짧아야 한다. 대부분의 경우에서 크기가 작은 순이다.
Posting 교집합은 여전히 그림 1.6의 알고리즘에 의해 행해지지만, 리스트들의 길이간의 차이가 매우 클 때, 대체 기술을 사용할 기회가 생긴다. 그 교집합은 중간 결과물 리스트에서 파괴적으로 수정을 하거나 유효하지 않은 아이템을 표시함으로써 적당히 계산되어질 수 있다. 또는 중간 결과물 리스트의 각 posting list에 대해 긴 posting list 내에서 연속적인 binary search로 수행될 수 있다. 다른 가능성은 중간 결과 아이템의 구성원들은 시간 복잡도가 선형 또는 로그 시간보다 더 나은 상수로 계산되어질 수 있는 해시테이블처럼 긴 posting list를 저장하는 것이다. 하지만, 그런 대체 기술은 Chapter 5에서 논의될 부류의 posting list 압축과 결합시키기가 어렵다. 게다가 보통 posting list 교차 연산은 질의의 두 term이 매우 일반적일 때라는 필요성을 남긴다.
Exercise 1.4 아래의 질의에서, x와 y는 Brutus와 Caeser에 대한 posting list의 길이라고 하면 우리는 여전히 시간 복잡도 O(x+y)로 교차 연산을 수행할 수 있는가? 만일 할 수 없다면, 우리는 무엇을 획득할 수 있는가?
a. Brutus AND NOT Caeser
b. Brutus OR NOT Caeser
Exercise 1.5 posting 합병 알고리즘을 임의의 Boolean 질의 방식으로 확장해보자. 시간 복잡도는 어떻게 되는가? 예를 들어,
c. (Brutus OR Caeser) AND NOT (Antony OR Cleopatra)
우리는 항상 선형 시간으로 합병할 수 있는가? 어디에서 선형적인가? 이것보다 더
나은 방법이 있는가?
Exercise 1.6 우리는 재작성된 질의를 AND와 OR에 대해 분배 법칙을 사용할 수 있는가?
a. Exercise 1.5에서 질의를 분배법칙을 사용해서 분리된 일반적인 형태로 어떻게 재작성하는지 보여라
b. 결과 질의는 원 형태보다 효과적으로 평가되어질 수 있을까? 없을까?
c. 이 결과는 일반적으로 사실인가? 또는 문서 컬렉션의 단어와 본문에 의존하는가?
Exercise 1.7 질의를 처리하는 순서를 설명하라.
d. (tangerine OR trees) AND (marmalade OR skies) AND (kaleidoscope OR eyes)
다음과 같이 posting list의 사이즈가 주어졌다.
Term Posting Size
eyes 213312
kaleidoscope 87009
marmalade 107913
skies 271658
tangerine 46653
trees 316812
Exercise 1.8 만일 질의가
e. friends AND romans AND (NOT countrymen) 이라면,
우리는 가장 좋은 지의 평가 순을 평가하는데 있어서 counrymen의 빈도수를 어떻게
사용할 수 있을까? 그 중에서도, 질의 처리의 순서를 결정하는데 있어서 부정
(negatition)을 다루는 방법을 제안하라.
Exercise 1.9 인접 질의에 대해서, 사이즈에 따라 posting list를 처리하는 것이 최적화를 보장하는 가? 그렇다면 왜 그런지 설명을 하고, 그렇지 않다면 예제를 보여라.
Exercise 1.10 posting 합병 알고리즘을 그림 1.6 (페이지 11)의 형태로 작성하라. x와 y는 질의어.
Exercise 1.11 Boolean 질의 x AND y는 어떻게 다루어지는가? 왜 이런 질의의 원시적인 평가가 매우 비싼 대가를 치루어야 하는가? 이런 질의를 효과적으로 평가하기 위한 posting 합병 알고리즘을 작성하라.
** 이전 글 **
Introduction
1.1 An example information retrieval problem
1.2 A first take at building an inverted index
** 다음 글 **
1.4 The extended Boolean model versus ranked retrieval
1.5 References and further reading
올리는 주기를 보니 주말을 제외하고 4~5일에 한 번씩 올리는군요..
좀 더 속도를 내고 싶지만, 여건이 제한되어져 있어서...
1.3 Processing Boolean queries
우리는 역색인과 기본 Boolean 검색 모델을 이용하여 질의어를 어떻게 처리할까? 간단한 결합 질의(conjunctive query)를 처리하는 것을 고려해보자.
(1.1) Brutus AND Calpurnia
위 역색인은 부분적으로 페이지 6의 그림 1.3에서 보여준다.
1. dictionary에서 Brutus를 찾는다.
2. Brutus와 관련된 posting을 검색한다.
3. dictionary에서 Calpurnia를 찾는다.
4. Calpurnia와 관련된 posting을 검색한다.
5. 그림 1.5에서 보여주는 것처럼 두 posting list에서 교집합을 구한다.
교집합 연산을 구하는 것은 중요하다. 우리는 2개의 term을 포함하고 있는 문서들을 빨리 찾을 수 있도록 하기 위해 posting list들을 효과적으로 교차 연산할 필요가 있다. (이 연산은 때론 posting list들을 합병하기 위해서도 참조가 되는데, 조금 직관적이지 않은 이런 이름은 일반적인 알고리즘 군에서는 각각의 포인터를 전진시키며 끼워 넣는 정렬된 리스트들을 결합시키는 term 합병 알고리즘이라는 이름으로 알려졌다. 여기서 우리는 논리적인 AND 연산을 가지고 리스트들을 합병하고 있다.)
그림 1.6에서 보면 합병 알고리즘을 사용해서 posting list들의 교차하는 간단하고 효과적인 방법이 있다. 우리는 2개의 리스트 포인터를 유지하고 2개의 posting list들의 모든 엔트리들을 선형적으로 동시에 순회한다. 각 단계에서 우리는 두 포인터가 가리키는 docID를 비교한다. 만약 그것들이 같다면, 결과 리스트에 해댱 docID를 삽입하고 두 포인터를 전진시킨다. 그렇지 않다면, 더 작은 docID를 가리키하는 포인터를 전진시킨다. 만일 posting list의 길이를 x와 y라고 한다면, 교집합의 복잡도는 O(x+y)를 가진다. 공식적으로 질의어의 복잡도는 Θ(N)이다. 여기서 N은 컬렉션에서의 문서 개수이다. 색인 방법은 상수를 획득한다. 선형 스캔과 비교하는 Θ 시간 복잡도에서의 차이가 아니라, 실제로 상수는 엄청 크다. Posting은 단독 전역 순서에 의해 정렬되어진다는 것은 중요하다. docID에 의한 숫자 정렬을 사용하는 것은 이러한 것들을 이루는 것에 대해서 하나의 간단한 방법이다.
우리는 다음과 같은 좀 더 복잡한 질의어를 처리하기 위해 교집합 연산을 확장할 수 있다.
(1.2) (Brutus OR Caeser) AND NOT Calpurnia
질의어 최적화는 답변 작업을 전체 작업량이 시스템에 의해 행해지는 것을 최소화하기 위해 어떻게 구조화할 것인가를 선택하는 과정이다. Boolean 질의어에 대한 주 요소는 어떤 posting list를 접근할 것인가에 대한 순서이다. 질의 처리에 대한 최선의 순서는 무엇인가? term들에 대한 AND 질의어를 고려하자. 예를 들면,
(1.3) Brutus AND Caeser AND Calpurnia
각 term들은 posting을 획득할 필요가 있고, 그것들 모두 AND 연산을 취한다. 표준적인 방법은 document frequency가 증가되는 순으로 term들을 처리하는 것이다. 만일 우리가 2개의 제일 작은 posting list들의 교차 작업을 시작한다면, 중간 산출물은 제일 작은 posting list보다 더 클 수 없는 것이 자명하고, 따라서 전체 작업량은 최소한으로 이루어질 거 같다. 그래서 페이지 6의 그림 1.3에서의 posting list들에서 우리는 아래의 질의어처럼 실행한다.
(1.4) (Calpurnia AND Brutus) AND Caeser
이것이 dictionary에서 term frequency를 가지는 첫 번째 이유이다. 어떤 posting list를 접근하기 전에 메모리상의 데이터에 기초하여 이러한 정렬을 위한 결정을 할 수 있게 해준다.
(1.5) (madding OR crowd) AND (ignoble OR strife) AND (killed OR slain)
이전에 처럼, 우리는 모든 term에 대해서 frequency들을 획득하고 그로 인해 따로 존재하는 frequency들의 합에 의해 각 OR의 사이즈를 예측할 수 있다. 떨어져 있는 각 term 사이즈의 증가 순에 의해 질의를 처리할 수 있다.
임의의 Boolean 질의어에 대해서 우리는 복합적인 표현으로부터 중간 표현에 대한 답을 일시적으로 평가하고 저장해야 한다. 그러나, 많은 상황에서 사용자가 던져주는 질의어는 자연어이거나 질의어의 가장 일반적인 형태이기 때문에 질의는 순수한 결합어이다. 이런 경우에 2개의 입력과 서로 다른 출력을 가진 기능으로서 posting list를 병합하여 보여주는 것보다 적어도 빈번한 term들의 posting list를 적재하여, 중간 결과물을 초기화할 수 있는 메모리상에서, 현재의 중간 결과를 가지고 검색되어진 각각의 posting list들간의 교집합을 구하는 것이 더 효과적이다. 이 알고리즘은 그림 1.7에서 보여준다.
Posting 교집합은 여전히 그림 1.6의 알고리즘에 의해 행해지지만, 리스트들의 길이간의 차이가 매우 클 때, 대체 기술을 사용할 기회가 생긴다. 그 교집합은 중간 결과물 리스트에서 파괴적으로 수정을 하거나 유효하지 않은 아이템을 표시함으로써 적당히 계산되어질 수 있다. 또는 중간 결과물 리스트의 각 posting list에 대해 긴 posting list 내에서 연속적인 binary search로 수행될 수 있다. 다른 가능성은 중간 결과 아이템의 구성원들은 시간 복잡도가 선형 또는 로그 시간보다 더 나은 상수로 계산되어질 수 있는 해시테이블처럼 긴 posting list를 저장하는 것이다. 하지만, 그런 대체 기술은 Chapter 5에서 논의될 부류의 posting list 압축과 결합시키기가 어렵다. 게다가 보통 posting list 교차 연산은 질의의 두 term이 매우 일반적일 때라는 필요성을 남긴다.
Exercise 1.4 아래의 질의에서, x와 y는 Brutus와 Caeser에 대한 posting list의 길이라고 하면 우리는 여전히 시간 복잡도 O(x+y)로 교차 연산을 수행할 수 있는가? 만일 할 수 없다면, 우리는 무엇을 획득할 수 있는가?
a. Brutus AND NOT Caeser
b. Brutus OR NOT Caeser
Exercise 1.5 posting 합병 알고리즘을 임의의 Boolean 질의 방식으로 확장해보자. 시간 복잡도는 어떻게 되는가? 예를 들어,
c. (Brutus OR Caeser) AND NOT (Antony OR Cleopatra)
우리는 항상 선형 시간으로 합병할 수 있는가? 어디에서 선형적인가? 이것보다 더
나은 방법이 있는가?
Exercise 1.6 우리는 재작성된 질의를 AND와 OR에 대해 분배 법칙을 사용할 수 있는가?
a. Exercise 1.5에서 질의를 분배법칙을 사용해서 분리된 일반적인 형태로 어떻게 재작성하는지 보여라
b. 결과 질의는 원 형태보다 효과적으로 평가되어질 수 있을까? 없을까?
c. 이 결과는 일반적으로 사실인가? 또는 문서 컬렉션의 단어와 본문에 의존하는가?
Exercise 1.7 질의를 처리하는 순서를 설명하라.
d. (tangerine OR trees) AND (marmalade OR skies) AND (kaleidoscope OR eyes)
다음과 같이 posting list의 사이즈가 주어졌다.
Term Posting Size
eyes 213312
kaleidoscope 87009
marmalade 107913
skies 271658
tangerine 46653
trees 316812
Exercise 1.8 만일 질의가
e. friends AND romans AND (NOT countrymen) 이라면,
우리는 가장 좋은 지의 평가 순을 평가하는데 있어서 counrymen의 빈도수를 어떻게
사용할 수 있을까? 그 중에서도, 질의 처리의 순서를 결정하는데 있어서 부정
(negatition)을 다루는 방법을 제안하라.
Exercise 1.9 인접 질의에 대해서, 사이즈에 따라 posting list를 처리하는 것이 최적화를 보장하는 가? 그렇다면 왜 그런지 설명을 하고, 그렇지 않다면 예제를 보여라.
Exercise 1.10 posting 합병 알고리즘을 그림 1.6 (페이지 11)의 형태로 작성하라. x와 y는 질의어.
Exercise 1.11 Boolean 질의 x AND y는 어떻게 다루어지는가? 왜 이런 질의의 원시적인 평가가 매우 비싼 대가를 치루어야 하는가? 이런 질의를 효과적으로 평가하기 위한 posting 합병 알고리즘을 작성하라.
** 이전 글 **
Introduction
1.1 An example information retrieval problem
1.2 A first take at building an inverted index
** 다음 글 **
1.4 The extended Boolean model versus ranked retrieval
1.5 References and further reading
'IT > 검색엔진' 카테고리의 다른 글
쩐의시대
나답게 살아가고 나답게 살아가자