'IT/검색엔진'에 해당되는 글 18건

Smith-Waterman local sequence alignment 알고리즘은 computational 분자 생물학 분야에서 가장 중요하게 사용되는 기법 중의 하나임은 분명하다. 이 알고리즘은 잘 보존된 부분을 찾고 그렇지 않은 부분을 제거하도록 설계되어졌다.

두 개의 sequence를 A=a₁a₂…a_n과 B=b₁b₂…b_m이라 가정하자. 유사성 S(a, b)는 sequence element a와 b 사이에 주어진다. 일반적으로 dynamic programming에서 이 값은 a와 b가 같으면 1, 다르면 0이다. 그러나 W_k는 1.0 + 1/3 * k 이다.
유사성이 높은 segment 쌍을 찾기 위해 matrix H를 셋업한다.

H의 준비된 값은 H_ij가 a_i와 b_j내의 두 segment의 최대 유사성인 해석을 가진다. 이러한 값을 최대화하는 고전적 dynamic programming으로부터 획득되어진다.

4가지 인자들 중 "0"은 새로운 alignment를 시도하는 것에 해당된다. 이 점에서 alignment 값은 증가할 수 있고 이 점에 이르는 동안 alignment 값의 합은 음수로 되어 임의로 align했을 경우 alignment 값은 도리어 낮아지는 결과가 되므로 차라리 새로운 alignment를 찾는 것이 지금까지 맞춰온 것을 확장하는 것보다 낫다는 의미가 된다. 따라서, alignment 값을 구하는 matrix의 최 상단과 좌측 열은 모두 0으로 셋팅된다.

아래 예제에서 보듯이, 최대 유사성을 가지는 segment 쌍은 matrix H의 최대 element를 갖는 점에서 시작하여 back trace를 함으로써 alignment를 찾아내는 방식이다. 따라서 최대값을 갖는 matrix의 셀을 계속 유지하고 있어야 한다. 이 최대 element에서 back trace를 하면서 0.0인 element까지 반복하면서 찾는다. 참고로, 아래의 예제에서 최대 element를 갖는 점은 (10, 8)인 element로서 3.3이라는 값을 가진다.

이 간단한 예제에서 alignment는 아래와 같이 획득했다.

mismatch와 내부적인 삭제를 포함한다. 이 알고리즘은 수학적으로 엄격한 기본으로 하는 가장 유사한 segment들의 쌍을 찾을 수 있을 뿐만 아니라, 컴퓨터 상에서 효과적이고 간단한 프로그램을 할 수 있다.
단점으로는 실제로 중요한 subsequence alignment가 있음에도 불구하고 sequence가 길다는 점만으로 이를 포함하여 불필요한 alignment가 발생한다는 것이다.
조금 더 자세히 설명하면, 유전적으로 잘 보존되지 못한 부분이 전체 alignment에 포함되어 잘 보존된 부분과 섞여 있을 때, 이것이 alignment를 왜곡시키는 결과로 나타나는 경우가 발생한다. 그 이유로 Smith-Waterman local alignment 알고리즘은 최고의 점수를 갖는 local alignment를 찾지만 초고의 유사성, 최고의 일치도를 갖는 local alignment를 찾지 못하는 문제가 알고리즘 자체에 포함되기 때문이다.

정리를 하면, sequence alignment에서 비유사도(non-similarity)가 높은 시작 부분과 끝 부분 조각을 제거하는데는 효과적이나 비유사성을 갖는 조각이 잘 보존된 alignment 사이에 위치해 있을 때는, 최고의 유사성과 일치도를 갖는 것을 찾지 못한다.

** 관련 글 **
문장 비교
Edit Distance (Edit Operations) using Dynamic Programming

http://www.bioinformatics.uwaterloo.ca/~cs882/Old_courses/W03/sw.pdf
http://naver.nanet.go.kr:8080/dl/CommonView.php?u=c7CN1fs8fKOZt5%2FZ7PKh1up8cOAz15Hbgk6iGtYZ%2FAkCXcdQoJVjN9rsPZreYnbUd0QDUcaGIGPw7Yl11smJnw%3D%3D

최근에 받은 문제 중 하나가 이런 내용이 있었다.

두 문장의 차이점을 출력하는 프로그램을 작성하라. 두 문장은 동일한 문장을 조금 바꾼 것으로 아래와 같은 3개의 차이점이 있을 수 있다.
- Text could be deleted.
- Text could be inserted.
- Text could be changed.
원래 문장과 새로운 문장의 차이점을 모두 출력한다.

<Input>
텍스트 파일을 입력으로 한다.
비교할 두 개의 문장을 입력 받는다. 각 문장은 줄바꿈 문자로 구분하며, 각 문장을 text1, text2라 할 때 text1은 원래 문장, text2는 새로운 문장이 된다.

<Output>
다음과 같은 형태의 두 문장의 차이점을 모두 출력한다.
- deletion : 삭제된 문자와 그 위치 그리고 삭제된 문자의 개수

위 내용이 논문에 소개된 글이다. 정말 재미있는 소개글이지 싶다. 우리가 흔히 들어왔던 로그 함수를 그리는 데이터 구조를 이해하고 구현하는 것이 얼마나 어려운가?, 로그적인 시간 내에 사전적인 문제를 풀기 위해 프로그래머의 머리 속에서 얼마나 많은 뉴런들이 타버려야 하는가?
나는 위 소개글을 읽고 한바탕 웃고 말았다. 그런 반면 Skip List에 대한 기대감에 차게 만들었다.

특징 몇 가지를 살펴보자.
1. 똑같은 입력 값이라고 하더라도, 입력 순서에 따라 트리의 모양은 달라진다.
2. 실 구현은 배열과 Linked List로 구현 가능하다.
3. 구현하기가 일반 다른 알고리즘보다 훨씬 간단하다.
4. Top-Down 방식으로 삽입, 검색, 삭제가 이루어진다.
5. 최악의 검색 비용 log(n)을 가지는 몇몇 deterministic version(1-2 Skip List, 1-2-3 Skip List)을 표현한다.


1-2 Skip List에서 최대 개수의 포인터는 절대 2n을 초과하지 않는다. (배열 구현시)
배열 구현시 삽입과 삭제시 비용이 높아진다. 삽입시 비용이 높아지는 것은 다른 알고리즘과 비슷하여 큰 문제가 되지 않으나, 삭제시 그 만큼의 비용이 발생한다는 것은 문제이다. (삭제 연산이 많이 발생하지 않는다면 상관없다.) 따라서 이 문제를 해결하기 위해서 우리는 배열 구현을 Linked List로 구현을 하면 된다. 그러나, 배열 구현보다 3배의 요구 공간(6n)이 요구된다. Linked List로 구현한다는 것은 노드를 올리거나 내리기 위해 단지 몇몇 포인터만 변경만 하면 되기 때문이다.

1-2 Skip List는 높이 h-1에 1 또는 2 노드가 존재하고 있다.  1-2 Skip List와 2-3 tree간의 비교는 쉽게 일반화되어진다. 또한 1-2-3 Skip List는 높이 h-1에 최소 1개 최대 3개의 노드가 존재한다. 이 또한 2-3-4 트리와의 비교가 쉽게 된다. 삽입, 검색, 삭제 알고리즘은 하단에 Pseudo Code가 있으니 별도의 설명은 생략을 하며, 필요하신 분들은 논문을 직접 읽어보면 될 듯하다.
 

아래의 Pseudo Code는 Linked List를 기반으로 한 Pseudo Code이며 배열 코드는 인터넷에 검색을 해보면 코드들이 많이 있다.

1. Search Pseudo Code
논문에 나와 있는 내용이다. 검색 모듈이 2개가 있는데, 1번째는 거의 Binary Search Tree와 같다. 위 모듈은 bottom이 아닌 말단 노드까지 진행을 해야 한다.

2. Insert Pseudo Code
위 모듈을 한 번 그려보면, 거의 포인터만 옮기는 수준이다. 다른 알고리즘에 비하면 정말 간단하다. 이 모듈 또한 논문에서 제공이 된다.

3. Delete Pseudo Code
위 삭제 알고리즘은 내가 직접 구현한 내용이다. 약간 모자라는 부분이 있지만, 삭제하면서도 1-2-3 Skip List를 유지해야 하므로, 삽입 알고리즘보다 약간은 길다. 약간 어설프긴 하지만 돌아가는데에는 무리가 없다. 시간 나는대로 손을 봐서 좀 더 완벽한 모듈을 구현해야 하는 숙제가 남아 있다.

아무튼, 위 논문대로 복잡도라든지 코드 구현 내용이라든지 전혀 다른 알고리즘에 비해 뒤질 것이 없어 보인다. 역시 사람은 공부해야 하는가보다. 공부를 안 하면 이런 좋은 알고리즘이 있는지 없는지 조차 모르니 말이다.

** 관련 글 **
http://research.cs.queensu.ca/home/daver/235/C2102557243/E20070330101410/Media/SkipList.pdf
http://www.cs.ucr.edu/cs141/cs141_04sum/
http://en.literateprograms.org/Skip_list_(C_Plus_Plus)
http://www.cosc.canterbury.ac.nz/research/RG/alg/dict.html
http://www.ddj.com/184404217
ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

요약을 추출하는 알고리즘은 전형적으로 구문 추출에 대한 기술에 기반을 둔다. 그리고, 그러한 구문 셋을 인식하고자 하는 시도는 주어진 하나의 문서에 대한 이해에 있어서 굉장히 중요하다. 

요약을 추출하기 위해 많은 알고리즘들은 언어 지식에 의지를 많이 하고 있으며, 특히, 다른 언어로 이루어진 문서에 대해서는 상당히 많은 수정을 해야한다.
게다가 성능을 측정하기 위해서 다듬어진 데이터 셋을 통해 자신만의 편리성을 추구하는 경우도 많다.
TextRank는 이러한 제약에서 자유롭다고 볼 수 있다.
특징은 다음과 같다.

일반 랭킹 알고리즘은 각 문서들을 하나의 정점(Vertex)로 바라보지만, TextRank는 하나의 문서에서 각 sentence를 하나의 정점(Vertex)으로 인식을 한다.
또한, incoming, outgoing의 의미도 incoming은 다른 sentence에 현재 sentence에 존재하는 word가 있는지를 체크하고, outgoing도 마찬가지로 현재 sentence에서 다른 sentence에 word가 존재하는지를 체크한다. 이것을 content overlap이라 표현한다.

이 과정에서 몇가지 선행이 되어져야 한다. punctation 문자라든지, stopwords(불용어)에 대한 처리를 미리해야 된다. 굳이 의미없는 word는 삭제하겠다는 의미이다.

일단, 여러 랭킹 알고리즘 가운데 PageRank와 HITS에 포커스를 맞춰 살펴본다.

PageRank는 아마도 가장 유명한 알고리즘 중 하나이며, Web-link 분석에 대한 방법으로서 디자인되어졌다. 다른 그래프 랭킹 알고리즘과 달리 PageRank는 하나의 싱글 모델에 incoming과 outgoing 링크의 impact를 통합한다. 따라서, Score는 하나의 셋만 도출한다.

Out(Vj)는 그래프의 j번째 정점(Vj)에서 outgoing되는 edge의 개수.

이 결과에 d는 0과 1사이로 셋팅하는 파라메터이며, random walking model내에 random jump에 대한 임무를 지녔다. d는 일반적으로 0.85로 셋팅하는 걸로 되어 있다.

위 PageRank 식을 TextRank에 적용하면 다음과 같다.

이 등식 중 이 부분의  의미는 Vi로 outgoing하는 Vj에 incoming하는 정점의 weight들의 합계를 Vj의 pagerank의 값을 나눈 값에 weight를 곱한 것이다.
등식을 이해하는 것에 별 어려움이 없어 보인다.

HITS는 authority의 정도에 따라 Web Page를 랭킹하고자 디자인된 반복적인 알고리즘이다. HITS 알고리즘은 authority와 hubs를 구분한다.
"authority"는 incoming 링크를 가진 페이지로, "hubs"는 outgoing 링크를 가진 페이지로 정의한다.
각 정점에 대해서, HITS는 "authority" score와 "hubs" score라는 2개의 셋을 산출한다.

위 HITS 식을 TextRank에 적용하면 다음과 같다.
HITS 알고리즘은 incoming 랭킹 값이 우선시 되고, incoming 랭킹 값이 같을 경우 outgoing 랭킹 값을 비교한다.

그런데, PageRank나 HITS 알고리즘에서 기존 정점에 대한 랭킹은 어떻게 알까?
즉, 등식을 보더라도 PR(Vj)와 HITS(Vj) 값을 이용하게 된다. 그렇다면 이 값은 어떻게 알아내는 것일까?
답은 쉽다. 초기값을 0에서 1사이의 값으로 임의의 배정을 한 후 위 식들을 대입하되, 벡터간의 거리가 threshold 값에 근접(convergence)할 때까지 반복한다. 단, HITS는 쉽게 convergence가 되지 않는 경우도 발생하므로, 최대 10~20까지만 반복하는 조건이 필요하다.
일반적으로 threshold는 0.01 내지 0.001를 사용한다.

유사성(similarity)는 content overlap을 통해 획득하게 되는데, abusing 데이터를 처리하기 위해 normalization을 하게 된다.

분모에서 log 함수를 사용하는 것은 abusing 데이터를 처리하기 위한 normalization 작업이며, Wk는 두 sentence에 모두 존재하는 word이며 분자는 그런 word들의 개수가 된다.

이 정도만 알고 있다면, TextRank에 대한 구현은 어려운 문제는 아니다.
Matrix를 작성하고, 각 (i, j)의 값에 랭킹(PR(Vi), HITS(Vi), HITS(Vj))를 구하고, threshold값에 근접할 때까지 반복하기만 하면 된다. 단, 주의 사항은 PageRank에 대한 TextRank 등식을 보면 루프 구문을 3번 돌아야 한다. 한 문서에 1,000개의 구문이 존재한다면, 1,000 X 1,000 X 1,000 번의 루프를 돌아야 하는 비효율적이나, 등식을 잘 보면 1,000 X 1,000 + 1,000으로 변경할 수 있다.

다음은 TextRank를 구하기 위한 전체적인 알고리즘 diagram이다.


많은 연구 결과에서 요약에 대한 결과는 만족스러운 수준으로 나왔고, 사람의 눈으로 확인한 결과만큼이나 괜찮은 결과를 획득했다고 했다.

나 또한, 직접 프로그래밍을 한 후 그 결과를 확인해보고 깜짝 놀랄 말했다. 영어 문서이든 한글 문서이든 상당한 결과를 볼 수 있었다.

** 관련 글 **
http://www.aclweb.org/anthology-new/P/P05/P05-3013.pdf
http://www.aclweb.org/anthology-new/P/P04/P04-3020.pdf
http://www.icmc.usp.br/~taspardo/NAACL07-LeiteEtAl.pdf
http://users.dsic.upv.es/~dpinto/miniproject/ProjectTextRank.pdf

Edit Distance란?

위키피디어(http://en.wikipedia.org/wiki/Edit_distance)에 정의된 것을 보면,

일반적으로 어떤 Vertex간의 거리는 개념이 일반화가 되어 있어서 쉬우나, 정의를 보지 않고 문자열간의 거리라 함은 이해가 잘 안되기도 한다.
벡터간의 거리는 쉽게 유클리안 거리를 이용하면 되지만...
혹시, 문자열간의 거리도 벡터로 변환 후 유클리안 거리를 이용하나?
답은 정의를 보면 변환하기 위해 요구되어지는 연산의 수가 문자열간의 거리이다.

이때 필요한 연산의 수는 다음과 같이 정의가 된다.
변환(change), 삽입(insertion), 삭제(deletion) 3가지 연산이 필요하다.

change : symbols at corresponding positions are distinct
insertion : a symbol of y is missing in x at a corresponding position
deletion : a symbol of x is missing in y at a correspoinding position.
(in order to transform x into y)

예를 들어,
1. x: "abc" --> y:"abd"
   x 문자열을 y 문자열로 변환하기 위해서는 마지막 문자 "c"를 "d"로 바꾸기만 하면 된다.
   즉, change 라는 연산 한 번만 발생하기 때문에 x와 y의 거리는 1이다.

2. x: "park" --> y:"spake"
   이 문제는 조금 애매하지 않은가? 어떻게 변환을 할지...
   그러나, 조금만 생각해보면 x의 1번째 문자 앞에 y의 "s"를 삽입(insertion)하고,
   x의 3번째 문자 "r"을 "k"로 변환하고, x의 5번째 문자 "k"를 "e"로 변환을 하면 된다.
   1번의 삽입과 2번의 변환이 이루어졌으니, 거리는 3이다.

   또 다른 방법으로,  x:"p" -> y:"s", x:"a" ->y:"p", x:"r" -> y:"a", y:"e"를 x의 마지막 문자로
   삽입하는 경우도 가능하다. 이 경우는 3번의 변환과 1번의 삽입이 이루어졌으니,
   거리는 4가 된다.

   위 2번 예제에서 최적의 거리는 3이다.

이것이 edit distance이다.
그렇다면, 어떻게 최적의 거리를 찾을 것인가가 문제이다.
그 최적의 거리를 찾기 위해 우리는 Dynamic Programming Method를 사용한다.
물론, 그래프 알고리즘 가운데 다익스트라(Dijstra, 네덜란드인) 알고리즘을 사용해도 되나,
일반적으로 Dynamic Programming Method를 이용한다.

간단하게나마, Dynamic Programming Method를 살펴보자.
실행 시간의 정보를 기록한다는 의미이다. 즉, 중복되는 계산 결과를 기록해서 중복된 계산 결과가 필요한 경우, 최대한 재계산을 피하고자 하는 것이다.
다른 말로 해석하자면, 작은 문제들의 해를 먼저 구하고 더 큰 문제의 해를 구할 때 작은 문제의 해를 반복 계산하지 않고 저장된 결과를 사용하는 것을 말한다.
한마디로, divide-and-conquer 이다. 분할 정복한다는 의미이다.
가장 이해하기 쉬운 것이 재귀호출로 여기면 될 것이다.

아무튼, Dynamic Programming Method 기법을 적용하여 Edit Distance를 구하고자 하는 식은 다음과 같다.
 

위의 예제에서 Edit Distance를 구하기 위해 작성된 Matrix 내용을 보자.

이로써, Edit Distance는 x라는 문자열을 y라는 문자열로 변환하기 위해 수행되는 연산의 수가 되면 그 연산은 Dynamic Programming을 통해 구해질 수 있다.

그러나, 우리가 Edit Distance를 구하기 위해 m X n의 matrix를 사용해야 되나? 라는 의문은 갖지 않는가? 희소행렬 (sparse matrix)를 이용해도 충분할텐데 말이다...

그러나, 우리가 Edit Operations을 구하기 위해서는 반드시 m X n의 matrix가 필요하다.
Edit Operations는 Back Tracking을 하면서 optimal path를 구하기 때문이다.
Edit Operations은 이미 위의 2번 예제에서 살펴보았다.
즉, 두 문자열간의 optimal path를 보여주는 과정이다.
연속된 문자들 "- a"는 문자 'a'를 삽입(insertion)한다는 의미이며, "a -"는 'a'를 삭제(deletion)한다는 의미이다. 즉, "- a"는 y의 문자가 "-"에 삽입되어져야 할 자리이며, "a -"는 x의 문자를 삭제해야 한다는 의미이다. 변환(change)는 굳이 작성하지 않아도 된다. 어떻게 보면 x와 y의 문자들을 서로 교환을 해야 된다는 의미인데 굳이 표현할 필요는 없다는 뜻도 된다.
위 2번 예제를 다시 보면,

즉, Edit Operations은 위와 같은 형태를 만드는 행위라 보면 된다.
이 행위 또한 Edit Distance를 획득하기 위해 만들어진 matrix를 사용해야 하며 위의 의미 그대로 작성하면 된다.

Edit Operations을 구하는 pseudo code는 아래와 같다.

이 과정을 수행하면서 다음과 같은 문자열에 대해서 테스트를 해보라.

optimal path는 3~4가지가 나올 수 있다.
그 중 하나의 값을 살펴보면 다음과 같다.
(참고, 그 결과를 보고 싶다면, http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/) 를 참조하라.

위 결과를 보고 짐작할 수 있듯, 삽입은 x의 문자열에서 발생을 하고, 삭제는 y의 문자열에서 발생을 한다.
즉, 의미상 x 문자열이 기준이 된다. x에 y의 문자를 삽입하고, x의 문자를 삭제하고..
예를 들어, mccoh-n은 y의 문자 'e'를 x에 삽입하고자 하는 것이며, --cohen은 x의 문자 'm'과 'c'를 삭제하겠다는 의미이다.

문자열간의 거리를 체크하여 두 문자열간의 유사성을 체크한다는 것은 재미있는 일이다.
검색에서의 사용을 예를 들자면, 두 문서의 제목에 대해서 Edit Distance를 사용하여 유사성을 체크할 수도 있는 일이다.
http://www-scf.usc.edu/~audhkhas/kws_audhkhasi_icassp07.pdf

Video, Image 처리 분야에서도 Edit Distance / Edit Operations을 이용을 많이 하는 것 같다.
자세하게 보지는 않았지만, 2개의 Image간의 유사성을 체크할 수 있지 않을까??
http://www-stat.stanford.edu/~idrori/Vidop.pdf
http://www.micc.unifi.it/publications/2006/BDN06a/bertini-civr06.pdf

한글에 대해서는 어떻게??
한글 검색어 간 유사도를 위한 Levenshtein distance 함수
이 블로그에서 잘 설명이 되어 있으니 참조를 하구...

** 관련 글 **
문장 비교
http://www.cs.umass.edu/~mccallum/courses/cl2006/lect4-stredit.pdf
http://www.cs.ucr.edu/~stelo/cpm/cpm05/cpm05_8_4_Touzet.pdf
http://www.cs.duke.edu/courses/fall05/cps230/L-04.pdf
http://www.aistudy.co.kr/math/shortest_johnsonbaugh.htm

** 소스 **

역색인 구조에서 주요 단계를 기억해보자.
1. 색인할 문서들을 수집
2. 텍스트를 토큰화
3. 토큰의 전처리 과정으로 언어학적 처리
4. 각 term이 발생하는 문서를 색인

이번 Chapter에서 우리는 먼저 문서의 기본 단위를 어떻게 정의할 것이며 character sequence를 어떻게 결정할 것인지를 명백하게 말한다(Section 2.1). 그럼 우리는 몇몇 명사가 언어학적으로 토큰화에 따른 이슈와 시스템이 사용할 term들의 vocabulary를 결정할 전처리 과정을 상세하게 검토한다(Section 2.2). 토큰화(Tokenization)는 문자 스트림에서 토큰을 잘라내는 과정이다. 언어학적 선처리는 색인되어지는 term들의 집합인 토큰의 동등한 클래스를 만드는 것을 다룬다. 색인은 Chapter 1과 4에서 다룬다. 이제 우리는 posting list들의 구현으로  되돌아온다. Section 2.3에서 우리는 더 빠른 질의처리를 위해 확장된 posting list data 구조체를 검토한다. 그리고 Section 2.4는 구문 핸들링과 확장 Boolean 모델과 웹상에서 일반적으로 표현하는 근접 질의 처리에 적합한 postings list data 구조체를 다룬다.


2.1 Document delineation and character sequence decoding
2.1.1 Obtaining the character sequence in a document
 색인 과정에 입력값인 디지털 문서들은 파일이나 웹 서버에서 전형적인 byte의 집합이다. 처리 과정의 첫 번째 단계는 byte sequence를 선형의 character sequence로 변환하는 것이다. ASCII로 표현된 평범한 영어 텍스트의 경우는 평범하지만, 종종 꽤 복잡하다. character의 순서는 여러가지 single-byte 혹은 multibyte 인코딩 (UTF-8나 여러나라 혹은 vendor의 특정 표준과 같은) 중의 하나로 인코딩되어질 것이다.

우리는 올바른 인코딩을 결정할 필요가 있다. Chapter 13에서 논의될 classification를 배울 기계로 간주되어질 수 있지만 종종 휴리스틱 방법에 의해 다루어진다. 우리는 byte sequence를 character sequence로 디코딩한다. 문서들이 어떤 언어로 작성이 되었는지에 대한 증거를 남겨야 하기 때문에 선택된 인코딩을 저장할 지도 모른다.

 character들은 Microsoft Word Doc 파일과 같은 몇몇 이진 표현이나 zip 파일과 같은 압축된 형태 이외로 디코딩되어져야 할 지도 모른다. 다시, 우리는 문서 형태를 결정해야 하고, 적당한 디코더가 사용되어져야 한다. 평범한 텍스트 문서들조차도, 추가적인 디코딩이 행해져야 할 필요가 있다. XML 문서 (Section 10.1, page 180)에서, &amp와 같은 character 엔티티들은 올바른 character로 표현해주기 위해 디코딩되어질 필요가 있다.  즉. &amp의 &. 마지막으로 문서의 본문 파트는 처리되지 않을 다른 유형 이외를 추출해야 할 필요가 있다. 이것은 XML 파일을 위해 요구되어지는 핸들링일 것이다. 만일 그 markup이 무시되어진다면,  우리는 거의 확살하게 postscript나 PDF 파일로 이런 행위를 원할 것이다. 이 책에서는 이러한 이슈들에 대해서 더 이상 다루지 않는다. 그리고, 앞으로 우리의 문서들은 charater들의 리스트로 가정한다. 상업용 산출물은 보통 문서의 형태와 인코딩에 대해 광범위하게 지원한다.  왜냐하면 사용자들은 그들의 자료로 작업하고 싶어하기 때문이다. 종종 그들은 디스크상에 어떻게 인코딩되었는지는 알지 못하고 문서들을 어플리케이션 내의 텍스트로서 여긴다. 이러한 문제는 문서 포맷을 디코딩하고 character들을 인코딩할 소프트웨어 라이브러리를 라이센싱하면서 해결되어진다.

 텍스트가 선형 character sequence라는 생각은 그림 2.1과 2.2에서 보는 것과 같이 텍스트가 2차원적이고 혼합 순서(mixed-order) character인 아라비아 언어와 같은 몇몇 글 표기법(writing system)에 의해 질문들이 생길 소지가 있다. 그러나, 몇몇 복잡한 글 표기법의 관습에도 불구하고, 근원적으로 표현되어지는 소리의 sequence는 있다. 그러므로 본질적으로 선형 구조체는 존속한다. 이것은 그림 2.1에서 보는 것과 같이 아라비아 문자의 디지털 표현에서 표현되어지는 것이다.

2.1.2 Choosing a document unit
 다음 구문은 색인을 위한 문서의 단위가 무엇인지를 결정하는 것이다, 사실 우리는 색인의 목적을 위해 문서는 고정된 단위라고 가정한다. 예를 들어, 우리는 문서로서 하나의 폴더에서 각 파일들을 취한다. 그러나 다른 무엇인가를 하길 원하는 당신에겐 많은 경우가 생길 수 있다. 전통적인 Unix(mbox-format) 이메일 파일은 하나의 파일에 순차적인 이메일 메세지(이메일 폴더)를 저장하지만, 당신은 각 이메일 메세지가 분리된 문서라고 여긴다. 많은 이메일 메세지는 첨부된 문서들을 포함한다. 그리고 당신은 각 이메일 메세지와 첨부물들을 분리된 문서로서 생각하고 싶을 것이다. 만약 이메일 메세지가 첨부된 zip 파일을 가지고 있다면 당신은 zip 파일을 디코딩하고 싶을 것이고 그것을 포함한 각 파일을 분리된 문서로 여기고 싶을 것이다. 반대의 방향으로 가보면, latex2html과 같은 웹 소프트웨어의 여러가지 조각들은 당신이 single 문서라고 여기는 것들(예를 들면, PowerPoint 파일이나 LATEX 문서)을 취하고, 그것들을 각 슬라이드나 subsection에 대해 분리된 HTML 페이지로 나누고, 분리된 파일로서 저장한다. 이런 경우에, 당신은 여러 파일들을 하나의 파일로 합치길 원할 것이다.

 일반적으로 매우 긴 문서에 대해서 색인 단위(index granularity)의 이슈가 더 있다. 책의 컬렉션에 대해서, 일반적으로 하나의 문서로 전체 책을 색인하기 위하는 것은 나쁜 생각이다. Chinese Toys에 대한 검색은 첫 번째 chapter에 존재하는 China와 마지막 chapter에 존재하는 Toys를 언급한 책을 가져올 것이다. 그러나 이것은 질의에 대한 연관성을 만들 수 없다.  대신 우리는 작은 문서(mini-documnet)로서 각 chapter나 단락을 색인하기를 원한다. 매치는 좀 더 연관성이 있을 것이다. 문서가 좀 더 작아지기 때문에 사용자들은 문서 내에서 연관된 구절을 찾기가 훨씬 쉬워질 것이다. 그러나, 거기서 왜 멈추느냐? 우리는 작은 문서로서 개별적인 문장을 다룰 수 있다. 여기에 precision(정확도) / recall(재현율)의 tradeoff가 있다는 것은 명백하게 된다. 만일 단위가 매우 작다면, term들은 몇몇 작은 문서들 전반에 분산이 되어 우리는 중요한 구절를 놓칠 수 있다. 그런데, 단위가 매우 크다면 우리는 그럴싸한 매치를 얻을 경향이 있고 사용자들이 연관성 있는 정보를 찾가기 어렵다.

 큰 문서 단위가 가지는 문제점은 명백하거나 암시적인 검색(Section 2.4.2와 7.2.2)의 사용에 의해 완화되어질 수 있다. 우리가 넌지시 말한 결과 생성 시스템 선응에서의 tradeoff는 Chapter 8에서 논의된다. 색인 단위(index granularity)의 이슈, 그리고 특히 멀티 레벨의 단위(granularity)에서 동시에 문서를 색인할 필요성은 XML 검색에서 현저하게 나타난다. 그리고 Chapter 10에서 다시 과제로 삼는다. 정보 검색 시스템은 단위의 선택들을 제공하기 위해 디자인되어진다. 잘 만들어지기 위한 이러한 선택을 위해 시스템 개발자들은 문서 컬렉션과 사용자 그리고 사용자들의 정보 필요성과 사용 패턴들에 대한 이해도가 좋아야한다. 우리는 적당한 크기의 문서 단위 뿐만 아니라 필요하다면 분할 혹은 결합 파일의 접근 방법까지도 선택되어졌다고 가정한다.

** 이전 글 **
1. Boolean retrieval (Introduction, 1.1 An example information retrieval problem)

첫 번째 Chapter의 마지막 부분입니다.
에구구, 얼마되지도 않는 양인데두 번역을 한다는 것이 만만하지는 않네요..
앞으로 가야할 길은 까마득한데 끝까지 갈 수 있을지 걱정스럽습니다.

1.4 The extended Boolean model versus ranked retrieval

  Boolean 검색 모델은 사용자들이 주로 자유로운 텍스트 쿼리 (free text query)를 사용하는 Vector Space 모델 (Section 6.3)과 같은 랭킹 검색 모델과 대조된다. Vector Space 모델은 즉, 하나 또는 그 이상의 단어를 타이핑하는 것이 쿼리 표현을 만드는 연산자를 가진 정확한 언어를 사용하는 것보다 낫고, 시스템이 쿼리를 최대한 만족하는 문서를 결정한다. 랭킹 검색의 장점에 대한 수 십년간의 학술적인 연구에도 불구하고, Boolean 검색 모델을 구현하고 있는 시스템들이 주를 이루었고, 대규모 상업적 정보 제공자들에 의해 검색 옵션만을 1990년 초반 (대략 World Wide Web의 출현시점)까지 30년동안 제공되었다. 그러나 이러한 시스템들은 지금까지 제공되어진 기본적인 Boolean 연산자들( AND, OR, and NOT)을 제공하지 않았다. 정렬되지 않은 결과 집합을 갖는 term들간의 엄격한 Boolean 표현은 사람들이 필요로 하는 많은 정보를 제한시켰다. 그리하여 이러한 시스템은 근접 연산자와 같은 추가적인 연산자에 의해 확장된 Boolean 검색 모델을 구현하였다. 근접 연산자는 쿼리의 2개의 term들이 하나의 문서에서 서로 가까이 출현해야 한다는 조건을 지정하는 하나의 방법이다. 근접은 단어들간의 존재할 수 있는 단어의 숫자를 제한하거나 문장이나 문단과 같은 구조적인 단위를 참조함으로써 측정되어질 수 있다.

  Example 1.1 영리 목적의 Boolean 검색 : Westlaw. Westlaw(http://www.westlaw.com)은 50만 이상의 유료회원들이 수 십 terabyte 이상의 텍스트 데이터에 대해서 매일 수 백만의 검색을 수행하는 최대 규모의 법률 검색 서비스이다. (유료 회원의 수를 기준으로) 이 서비스는 1975년부터 시작되었고, 자유로운 랭킹 텍스트 쿼리 형식(westlaw에 의하면 Natural Language라 불리움)이 1992년에 추가가 되었음에도 불구하고 2005년에도 Boolean 검색 (Westlaw에 의하면 Terms and Connectors라 불리움)은 여전히 디폴트였고, 대다수의 사용자가 사용하였다. 여기에 Westlaw상의 몇몇 Boolean 쿼리의 예제가 있다.

    Information need : Information on the legal theories involved in preventing the
             disclosure of trade secrets by employees formerly employed by a competing
             company
             (이전에 경쟁회사에 근무하던 고용인에 의한 영업기밀의 폭로에 방지할 수 있는
              법적 이론에 대한 정보)
    Query : "trade secret" /s disclos! /s prevent /s employe!

    Information need : Requirements for disabled people to be able to access a
             workplace.
             (장애인들이 직장에 접근할 수 있도록 하기 위한 요구사항)
    Query : disab! /p access! /s work-site work-place(employment /3 place)

    Information need : Cases about a host's responsibility for drunk guests.
             (취객에 대한 호스트의 응대에 대한 사례)
    Query : host! / p (responsib! Liab!) /p (intoxicat! Drunk!) /p guest

  웹 검색에서 일반적이지 않은 길고 정확한 쿼리와 근접 연산자의 사용에 주의하라. 보내진 쿼리는 평균 길이는 약 10단어이다. 웹 검색의 일반적인 형태와 달리, 단어들간의 스페이스는 분리를 나타낸다. (가장 빡빡한 접합 연산자), &는 AND이고, /s, /p, /k는 같은 문장, 같은 문단 혹은 k 단어 내에서 매칭을 요구하는 것이다. 큰 따옴표(" ")는 문장 검색(연속적인 단어)을 제공한다. Section 2.4(page 36)을 참고하자. 느낌표(!)는 후행 와일드 카드 쿼리를 제공한다. (Section 3.2 page 48를 참조하자). 그러므로 liab!는 liab로 시작하는 모든 단어와 매칭하는 것이다. 게다가 work-site는 worksite, work-site 또는 work site 중 어느 것과 매칭하는 것이다. Section 2.2.1을 보자. 전통적인 전문가 쿼리는 보통 새심하게 정의되어졌고, 점진적으로 그들이 사용자에게 좋은 결과를 보여줄 때까지 개발을 했다.

  많은 사용자들, 특히 전문가들은 Boolean 쿼리 모델을 더 선호한다. 하나의 문서는 쿼리와 매치한다. 그렇지 않다와 같이 Boolean 쿼리는 정확하다. 이것은 무엇이 검색되어지는 것 이상으로 사용자들에게 더 많은 제어와 투명성을 제공한다. 그리고 법적 자료와 같은 몇몇 영역은 Boolean 모델 내에서 효과적인 의미의 문서 랭킹을 인정한다. Westlaw는 실제 꽤 효과적인 최근 연대순으로 문서를 제공한다. 2007년 대부분의 법률 사서는 높은 재현율을 위해 여전히 terms and connector를 추천하는 것처럼 보인다. 그리고 대부분의 법률 사용자들은 그것들을 사용함으로써 더 큰 제어를 획득할 수 있다고 여긴다. 그러나 이것은 전문가 검색을 위해 Boolean 쿼리들이 더 효과적이다라는 걸 의미하지 않는다. 실제적으로 Westlaw의 하부 컬렉션에서 경험함 Turtle(1994)은 경험에 의해 필요한 대다수의 정보에 대해 Westlaw의 레퍼런스 사서들에 의해 준비되어지는 Boolean 쿼리보다 자유로운 텍스트 쿼리(free text queries)가 더 나은 결과를 산출해 내는 것을 알았다. Boolean 검색이 가지는 일반적인 문제는 OR 연산자는 낮은 정확도와 높은 재현율을 제공하는 반면 AND 연산자는 높은 정확도와 낮은 재현율을 산출하는 경향이 있다는 것이다. 그리고 만족스러운 중간 지역을 찾기가 어렵거나 불가능하다.

  이번 chapter에서 우리는 dictionary와 posting list를 포함하는 기본적인 역색인의 구조와 구조물을 보았다. 우리는 Boolean 검색 모델을 소개했고, 선형 시간의 병합을 통해 효과적인 검색을 수행하는 방법과 간단한 쿼리 최적화를 시험했다. Chapter 2-7에서, 우리는 더 많은 쿼리 모델과 효과적으로 다룰 필요가 있는 증가하는 색인 구조의 종류에 대해서 상세히 고려한다. 여기서 우리가 할 수 있는 것들에 대해 몇몇 중요한 추가적인 것들에 대해 말하고자 한다.

1. 우리는 dictionary에서 term의 집합들에 대해 좀 더 나은 선택을 하고자 하고 철자 오류와
   일치하지 않는 단어의 선택에 대해서 관대한 검색을 제공하고자 한다.
2. "Operating system"과 같은 개념을 기술하기 위한 복합어나 구에 대해 종종 검색하는 것이
   유용하다. Westlaw 예제에서 보는 거처럼, 우리는 또한 Gates NEAR Microsoft와 같은
   근접 쿼리를 수행하기를 원한다. 그런 쿼리에 대한 답변은 색인이 문서 내에서 term들의
   근접을 알아내기 위해 늘어나야 한다.
3. Boolean 모델은 단지 term들이 존재하거나 하지 않거나를 기록하지만, 종종 우리는 단지
   한 번만 출현한 문서에 반해 term들이 몇 번 출현한 문서에 좀 더 많은 가중치를 줄 수 있는
   기록을 가지길 원한다.
4. Boolean 쿼리는 단지 매칭하는 문서의 집합을 검색하지만, 일반적으로 우리는 리턴되는
   결과를 정렬화(또는 랭킹화)하는 효과적인 방법을 가지길 원한다. 이런 요구는 문서 점수를
   결정하기 위한 쿼리에 대한 문서를 적절히 매치시키는 캡슐 메커니즘을 가지고 있다.

이러한 추가적인 아이디어를 가지고, 우리는 비정형화된 정보에 대한 Ad-hoc 검색을 지원할 대부분의 기본적인 기술을 보게 될 것이다. 전체 문서의 Ad-hoc 검색은 최근 웹 검색 엔진뿐만 아니라, 대규모 e커머스 웹 사이트에 있는 비정형화된 검색 부류에서도 세계적으로 공략하고 있다. 주요 웹 검색 엔진들은 자유로운 텍스트 쿼리(free text querying)을 강조함에 차이가 있음에도 불구하고 뒤에 나올 chapter에서 보게 될 거처럼 대부분의 기본적인 이슈들과 색인 기술들과 쿼리들은 그대로 유지된다. 게다가 시간이 흐름에 따라 많은 웹 검색 엔진들은 가장 인기있는 확장 Boolean 모델의 연산자들에 대해 부분적인 구현들을 추가하고 있다. 그럼에도 불구하고, 이러한 옵션들은 검색 전문가들이 선호함에도 그들은 대다수에 비해 적게 사용하고 있고, 웹 검색 엔진의 성능을 향상시키기 위한 주요 포커스가 아니다.

Exercise 1.12  Westlaw 구문법을 사용해서 똑같은 문장 내에서 몇몇 단어인 professor, teacher, lecturer 를 찾는 쿼리를 작성하라.

Exercise 1.13  2개의 주요 웹 검색엔진에서 Boolean 검색 특징을 사용해봐라. 예를 들어, burglar와 같은 단어를 선택 후, (i) burglar, (ii) burglar AND burglar, (iii) burglar OR burglar라는 쿼리를 수행하라, 예측되는 결과 수와 이것의 상위 히트수를 봐라. 그것들이 Boolean 논리에 의해 수행되었는가? 종종 그것들은 주요 검색엔진에 없다. 여러분들은 어떻게 수행되었는지 이해를 할 수 있는가? 만약 여러분들이 다른 단어를 사용했다면 어떠한가? 예를 들어, (i) knight, (ii) conquer, (iii) knight OR conquer와 같은 쿼리. 세 번재 쿼리에 비해 첫 2 쿼리에 대한 결과 수의 범위는 어떠한가? 이러한 범위를 인정하는가?

1.5 References and further reading

정보 검색을 전산화하기 위한 실제 연구는 1940년 후반부터 시작되었다. (Cleverdon 1991; Liddy 2005). 전통적인 저널 논설보다는 훨씬 비공식적인 기술 보고서인 과한 문헌의 급증이 컴퓨터의 가용성으로 이어졌고, 자동 문서 검색에 대한 관심을 주도하였다. 그러나, 그 당시에는 문서 검색은 항상 작가, 제목, 키워드들이 기초가 되었다. Full-text 검색은 훨씬 후에 나왔다.
Bush(1945)의 논설은 새로운 영역에 대해서 지속적인 영감을 제공하였다.

    기계화된 개인 파일과 라이브러리와 같은 개인적으로 사용하는 미래의 장치를 고려해보면
    이름이 필요하고 랜덤하게 하나를 창조한다. 'memex'라는 기계가 할 것이다. memex는
    모든 책과 기록, 대화를 개인적으로 저장할 장치이다. 굉장한 속도와 가연성을 지니고
    컨설팅해주기 위해 기계화되어진다. 그의 기억에 대한 친밀한 지원은 확대되어진다.

정보검색이라는 term은 1948/1950년에 Calvin Mooers라는 사람에 의해 만들어졌다. (Mooers 1950).
1958년 많은 신문은 IBM의 H.P.Luhn의 업적에 우선적으로 기초한 "자동 색인(auto-indexing)" 기계 컨퍼런스의 시연에 주목했다. 상업적 관심은 Boolean 검색 시스템에 대해서 재빨리 매혹되었다. 그러나, 초기에 검색 시스템에 대한 여러가지 이질적인 기술 전반에 대한 무모한 논쟁을 보았다. 예를 들어, Mooers(1961)는 의견을 달리했다.

    여러가지 검색 하드웨어에 몇 백만 달러의 투자에 서명했다는 것은 일반적인 잘못된
    생각이다. George Boole(1847)의 대수학은 검색 시스템 설계에 대한 적절한 형식이라는
    이러한 관점은 잘못된 만큼이나 넓게, 무비판적으로 받아들였다.

AND 대 OR은 정확도/재현율 트레이드오프에서 정 반대적인 현상을 보여주나, 절충 영역은 생겨나지 않는다. (Lee and Fox 1988)
(역자주: 트레이드오프(tradeoff). 어느 것을 얻으려면 반드시 다른 것을 희생하여야 하는 관계)

책(et al, 1999)은 역색인과 다른 가능한 데이터 구조체의 공간과 시간 효율성에 있어서의 철저한 경쟁에 대한 표준 레퍼런스이다. 좀 더 간결하고 최신의 발표는 Zobel과 Moffat에서 나왔다(2006). 우리는 향후 Chapter 5에서 몇몇 접근법에 대해 논의한다.

** 이전 글 **
Introduction
1.1 An example information retrieval problem
1.2 A first take at building an inverted index
1.3 Processing Boolean queries

** 다음 글 **
2. The term vocabulary and postings lists (2.1 Document delineation and character sequence decoding)

휴, 간만에 올립니다...
올리는 주기를 보니 주말을 제외하고 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

아직 시작 단계인데, 벌써 겁이 나기 시작합니다.
너무나 미약한 영어 실력에 막히는 곳이 한 두 군데가 아니고,
우리말로 표현하자니 의미 전달이 잘 안 되는 단어들도 존재하구...
직역을 고집하여 작성을 하고 있으나, 의역이 필요한 곳도 있고...
새삼 번역 일이라는게 쉽지 않은 일이구나 라는 걸 느낍니다.

1.2 A first take at building an inverted index

검색시 색인 속도에 대한 이점을 획득하기 위해 우리는 향상된 색인을 구축해야 한다. 이것은 중요한 단계들은
   1. 색인되어질 문서들을 수집 
     
   2. 텍스트들을 토큰화, 각 문서들을 토큰들의 리스트로 변환
     
   3. 언어학적으로 전처리, 색인화될 term들의 일반화된 토큰들의 리스트로 처리
     
   4. dictionary와 posting들로 구성된 역색인을 구축하는 것으로 각 term이 발생하는
      문서를 색인

우리는 앞선 처리 단계(1-3 단계)에 대해서 Section 2.2에서 정의하고 논의한다. 그때까지 여러분들은 토큰들(tokens)과 일반화된 토큰들(normalized tokens)을 단어들(words)과 대충 유사하다고 생각할 수 있다. 여기서, 우리는 첫 3개의 단계가 벌써 이루어졌다고 가정을 하고 정렬화된 색인에 의해 기본적인 역색인을 구축하는 것을 시험한다.

 문서 컬렉션 내에서 우리는 각 문서가 document identifier(docID)라고 알려진 유일한 순차적인 숫자를 가진다고 가정한다. 색인 구축 동안 우리는 간단하게 연속적인 정수를 처음으로 만나게 되는 각 문서에 할당할 수 있다. 색인 생성시 입력 값은 그림 1.4와 같이 term과 각 문서의 쌍의 리스트로서 생각할 수 있는 각 문서에 대해 일반화된 토큰들의 리스트들이다. 핵심 색인 단계는 그림 1.4의 중간 세로 줄에서 표현된 것처럼 term들이 알파벳 순이 되도록 이런 리스트들을 정렬하는 것이다. 똑같은 문서에서 동일한 term이 중복 발생이 되는 것은 합병되어질 수 있다. 그림 1.4의 오른쪽 세로줄에서 보여주듯이, 동일한 term이 그룹화되어지는 대신 그 결과는 dictionary와 posting으로 나뉘어진다. 일반적으로 term은 수 많은 문서에서 발생하기 때문에 이러한 데이터 구조화는 색인이 요구하는 저장공간을 감소시킨다. 또한 dictionary는 각 term을 포함하는 문서의 개수(각 posting list의 길이인 document frequency)와 같은 몇몇 통계를 기록한다. 이러한 정보는 기본적인 Boolean 검색 엔진에서는 그리 중요하지 않지만, 질의시 검색엔진의 성능을 향상시키며, 많은 랭킹 검색 모델(Ranked Retrieval Model)에서 향후 사용되어지는 통계이다.
Posting은 2차적으로 docID에 의해 정렬되어진다. 이것은 효과적인 질의 처리를 위해 기본이다. 이러한 역색인 구조는 본질적으로 Ad-hoc 텍스트 검색을 지원하는 가장 효과적인 구조체로서 경쟁 대상이 없다.
 색인 결과를 저장하기 위해서 2개의 dictionary와 posting list를 위한 저장 공간이 필요하다. 후자는 더 크지만, dictionary는 일반적으로 메모리상에서 관리를 하고, posting list들은 디스크상에서 관리를 한다. 그래서 각각의 크기는 중요하다. Chapter 5에서, 우리는 저장공간을 어떻게 잘 활용할 것이며 효과적으로 어떻게 접근할 것인지에 대해 시험한다. 어떤 데이터 구조체를 posting list를 위해 사용할 것인가? 고정된 길이의 배열은 낭비다. 몇몇 단어들은 많은 문서에서 발생하고, 어떤 단어들은 매우 적게 출현한다. 메모리상의 posting list를 위해서 singly linekd lists와 가변 길이 배열(variable length array)가 2가지 좋은 선택이다. singly linked list는 posting list에 문서 삽입 비용을 효과적으로 한다. (웹 문서를 재수집시 업데이트된 문서를 업데이트) 자연스럽게 추가적인 포인터를 요구하는 리스트를 건너 띔으로써 좀 더 향상된 색인 전략으로 확대할 수 있다.

 가변 길이 배열은 포인터와 요청에 대한 오버헤드를 피할 수 있어 공간 요구에 대해 효과적이다. 왜냐하면, 그들의 인접한 메모리를 사용하는 것은 메모리 캐쉬로 인해 최근 프로세서는 속도를 향상시킬 수 있다. 여분의 포인터는 실제로 옵셋처럼 리스트들로 인코딩되어질 수 있다. 만일, 업데이트가 상대적으로 드물다면 가변 길이 배열은 찾기에 더 간결하고 빨라진다. 또한 우리는 각 term에 대해 고정 길이 배열의 리스트를 연결하는 혼합 체계를 사용할 수 있다. Posting list들이 디스크상에 저장되었을 때 그것들은 그림 1.3과 같이 포인터없이 인접하게끔 (아마 압축 형태로) 저장되어진다. 그렇게 함으로써, posting list의 사이즈를 줄일 수 있고 메모리 상에서 posting list들을 읽기 위해 찾을 수 있다.

Exercise 1.1 다음 문서 컬렉션을 위해 구축되어질 역색인을 그려라. (예제로 그림 1.3을 보라)
          Doc 1   new home sales top forecats
          Doc 2   home sales rise in july
          Doc 3   increase in home sales in july
          Doc 4   july new home sales rise

Exercise 1.2 이러한 문서들을 가정하자.
          Doc 1   breakthrough drug for schizophrenia
          Doc 2   new schizophrenia drug
          Doc 3   new approach for treatment of schizophrenia
          Doc 4   new hopes for schizophrenia patients

                a. 문서 컬렉션을 위해 term-document 접속행렬(incidence matrix)를 그려라.
                b. 6 페이지의 그림 1.3과 같이 이 컬렉션을 위해 역색인 표현을 하라.

Exercise 1.3  Exercise 1.2에서 보여준 문서 컬렉션에서 다음과 같은 질의어에 대한 결과는 무엇인가?
          a. schizophrenia AND drug
          b. for AND NOT (drug OR approach)

** 이전 글 **
Introduction
1.1 An example information retrieval problem

** 다음 글 **
1.3 Processing Boolean queries
1.4 The extended Boolean model versus ranked retrieval
1.5 References and further reading

  정보검색(IR. Information Retrieval)의 의미는 매우 광의적일 수 있다. 어쩌면 지갑에서 신용카드를 꺼내서 카드번호를 적는 그 자체도 정보검색의 일종이지만, 학계에서의 정보검색은 다음과 같이 정의가 된다.

  정보검색은 정형화되지 않은 세계에서 자료(일반적으로 문서들)을 찾는다. 보통 컴퓨터에 저장되어진 굉장히 큰 컬렉션 내의 정보욕구를 해결해준다..

  이런 의미로 정의됨으로, 정보검색은 소수(사서, 변호사 보조원, 전문적인 정보검색사)들에 의해 이용되어지는 것으로 여겨졌다. 현재 세상은 변하고 있다. 정보검색에 관여하는 수백만의 사람들이 매일 웹 검색엔진을 이용하고 자신의 이메일을 검색한다. 정보검색은 정보 접근의 지배적인 형태로 급속히 변화하고 있고 전통적인 데이터베이스 검색을 대체하고 있다.(  "미안하다, 당신의 주문 ID를 나에게 줘야만 당신의 주문서를 찾을 수 있다"라고 점원이 당신에게 말할 때와 같은 부류)

   또한, 정보검색은 위에서 언급한 핵심적 정의를 넘어서 다른 종류의 데이터나 정보 문제로까지 확장될 수 있다. "비정형화 데이터(unstructured data)"는 깔끔하지도, 의미적으로 명백하지도, 컴퓨터가 이해하기 쉬운 구조체이지도 않은 데이터를 말한다. "정형화된 데이터(structured data)"의 반대 의미이며, 중요한 산출물과 개인적인 레코드들을 사용하기 위해  회사의 관계된 데이터베이스가 전형적인 예이다. 사실, 어떠한 데이터도 비정형화된 데이터가 아니다. 만약, 여러분들이 인간 언어의 잠재적인 말을 생각한다면, 이것은 모든 텍스트 데이터에 대해 의미적으로 맞다는 것을 확인할 수 있다. 그러나, 의도된 개념 구조조차 명백한 구조라고 인정하고 있다. 대부분의 텍스트는 일반적으로 명백한 마크업에 의해 문서를 표현하는 머리말, 문단, 주석을 가진 구조이다. 정보검색은 또한 Java라는 단어가 있는 제목과 threading이 있는 본문을 가진 문서를 찾는 것처럼 "준정형화(semistructrued)" 검색을 용이하게 사용한다.

  정보검색의 분야는 브라우징 혹은 문서 컬렉션을 필터링 또는 검색된 문서 집합을 활용, 분석할려는 사용자들을 지원한다. 문서 집합이 주어졌을 때, 클러스터링(clustering)은 컨텐츠(검색된 문서 집합)를 기반으로 문서들을 적당한 그룹으로 분류하는 것이다. 서가에서 주제별로 책들을 정돈하는 것과 유사하다. 토픽 집합이 주어졌을 때, 분류화(classification)는 각각의 문서 집합이 어떤 클래스에 속하는지 정의하는 것이다. 이것은 처음에 수동으로 몇몇 문서들을 분류화함으로써 접근을 하고, 그 후론 자동적으로 새로운 문서들을 분류할 수 있도록 한다.

  정보검색 시스템은 연산을 하는 범위에 의해 구분되어질 수 있으며, 그것은 3개의 명백한 범위를 구분하는데 유용하다.

  웹 검색에서, 시스템은 수백만 대의 컴퓨터에 저장되어진 십억 개 이상의 문서들에 대해 검색을 제공한다. 주요 이슈는 색인을 위해서 문서들을 수집하는 것이 필요하다. 이러한 거대한 범위에서 효과적인 작업을 할 수 있는 시스템을 만들고, 웹의 특별한 면(하이퍼텍스트를 활용하는 것처럼)을 핸들링할 수 있으며, 검색엔진 랭킹을 올리기 위해 사이트 제공자가 페이지 컨텐츠를 조절할 만큼 어리석지 않아야 한다. 웹의 상업적 중요성을 시사하며 이것은 chapter 12-21에서 논의한다.

  다른 명백한 범위 중 하나는 개인정보검색이다. 최근 몇 년간 consumer operating systems들은 정보 검색을 통합하고 있다. (Apple's max OS X Spotlight나 Windows Vista's Instant Search). 이메일 프로그램은 일반적으로 검색 뿐만 아니라 텍스트 분류화 작업(classification)을 제공한다. 그것들은 적어도 스팸(junk mail) 필터를 제공하고, 일반적으로 특정한 폴더에 바로 이동시키는 분류화를 위해 수동적으로나 자동적인 방법을 제공한다. 주요 이슈는 전형적인 개인 컴퓨터에서 굉장히 많은 문서의 종류를 핸들링해야 하면, 검색 시스템의 유지, 보수는 무료여야 하고, 구동, 처리를 위해 충분히 가벼워야 하면, 소유자를 성가시게 하지 않고 하나의 기계에서 돌아가기 위한 디스크 공간을 사용해야 한다.

  이것들의 중간적인 의미로서, enterprise, instituional, domain-specific 검색이 있다. 회사의 내부 문서, 특허 데이터베이스, 생화학의 연구 논문과 같은 컬렉션을 검색한다. 이 같은 경우, 문서들은 전형적으로 중앙 집중하는 파일시스템에 저장되어진다. 이 책은 이러한 전체적인 범위 이상의 기술을 포함하지만 웹 검색에서의 몇몇 병렬/분산 검색과 같은 주제에 대해서는 상대적으로 조금만 다룰 것이다. 그러나, 소수의 웹 검색 회사 이외의 소프트웨어 개발자들은 대개 개인 검색과 enterprise 시나리오에 부닥칠 것이다.

  이번 chapter에서는 매우 간단한 정보검색의 문제로 시작한다. 그리고, term-document 배열의 아이디어(Section 1.1)와 역배열 구조체(Section 1.2)를 소개한다. Boolean retrieval model과 Boolean query는 어떻게 처리되는지(Section 1.3, 1.4)를 설명한다.

1.1 An example information retrieval problem

  많은 사람들이 소유한 장서 중 하나는 셰익스피어의 전집(Shakespeare's collected Works)이다. 당신이 이 책에서 Brutus와 Caeser라는 단어가 포함되고 Calpurnia라는 단어는 포함되지 않은 (Brutus AND Caeser AND NOT Calpurnia) 셰익스피어의 작품들을 확인하기를 원한다고 가정하자. 이것을 수행하기 위한 한 가지 방법은 처음부터 모든 텍스트를 읽는 것이다. Brutus와 Caeser가 포함되었는지 확인을 하되 Calpurnia가 포함되었다면 고려 대상으로부터 제외한다. 문서 검색의 가장 간단한 형태는 컴퓨터가 문서를 선형 스캔하는 것과 같은 방법을 행하는 것이다. 이러한 처리는 일반적으로 텍스트를 스캔하는 유닉스 명령어인 "grep"을 이용하여 grepping하는 것과 같은 방법을 추천한다. 텍스트를 grepping하는 것은 매우 효과적인 처리일 수 있다. 특히 주어진 현대 컴퓨터의 속도가 주어졌다면 말이다. 그리고 종종 정규 표현식을 통한 와일드 카드 패턴 매칭을 가능케 한다. 적당한 크기의 컬렉션의 간단한 쿼리를 위해 현대 컴퓨터가 있다면, 당신은 더 이상의 어떤 것도 필요치 않다. (셰익스피어의 전집의 크기는 전체적으로 100만 단어 이하이다.)
그러나, 더 많은 목적을 위해 여러분들은 더 많은 것이 필요로 한다.

1. 대용량 문서 컬렉션을 빨리 처리하기
   많은 온라인 데이터는 최소한 컴퓨터의 속도만큼이나 빨리 성장하고, 우리는 수 십억에서
   수 조의 단어가 있는 전체 컬렉션에서 검색할 수 있기를 원한다.
2. 좀 더 유연한 매칭 연산을 수행하기
   예를 들어, 쿼리 "Romans NEAR countrymen"은 grep을 이용해서 수행하기는
   비현실적다. (NEAR는 같은 문자 혹은 5단어 이내의 연산을 의미한다.)
3. 랭크된 검색을 수행하기
   많은 경우에 있어 당신은 특정 단어를 포함한 많은 문서들에서 최선의 답을 획득하기를
   원한다.

110100 AND 110111 AND 101111 = 100100

  이 쿼리에 대한 답은 "Antony and Cleopatra"와 "Hamle"이 된다. (그림 1.2)

  Boolean retrieval model은 정보검색의 한 모델이며 우리는 term들의 Boolean 표현의 형태로 어떤 쿼리를 취할 수 있다. 즉, term들은 연산 AND, OR, NOT을 이용하여 결합되어진다.
이 모델은 단어의 집합으로 각 문서들을 바라본다.
좀 더 현실적인 시나리오를 고려함과 동시에 몇몇 용어와 표기법에 대한 기회를 갖자. 우리는 N = 1 million 문서를 가지고 있다고 가정하자. 검색 시스템을 문서 단위로 구축하기로 결정했다. 문서들은 개인적인 메모들일 수도 있고, 책의 chapter일 수도 있다. (Section 2.1.2 - page 20에서 향후 다룬다.) 컬렉션으로서 검색을 수행하기 위해 문서의 그룹들을 참조한다. 때론 텍스트의 본문인 코퍼스(corpus)를 참조한다. 각 문서가 2-3페이지에 걸쳐 약 1,000개의 단어가 있다고 가정하자. 스페이스와 구두문자를 포함하여 단어당 평균 6byte라고 가정하면, 이것은 약 6GB의 문서 컬렉션이다. 전형적으로 이러한 문서에서 약 M = 500,000개의 서로 다른 term들이 있을 수 있다. 우리가 선택한 숫자에 대한 특별한 것은 아무 것도 없고, 그 숫자들은 크기나 그 이상의 것의 순서에 따라 변할 수 있지만, 그것은 우리가 다루어야 할 필요가 있는 갖가지 문제의 차원에 대한 몇몇 아이디어를 제공한다. 우리는 논의할 것이고 Section 5.1 (page 79)에서 이러한 크기를 가정하는 것을 모델링할 것이다.

  우리의 목표는 Ad-hoc 검색 임무를 가진 시스템을 개발하는 것이며, 이것은 가장 표준 IR의 임무이다. 시스템은 임의의 사용자 정보와 연관성이 있고 1회성의, 사용자 초기 쿼리의 의미로 시스템과 소통하는 컬렉션 내의 문서들을 제공해주는 것을 목표로 한다.

  필요한 정보는 사용자가 좀 더 알고자 하는 것에 대한 주제이며, 사용자가 필요한 정보를 획득하기 위한 시도로써 컴퓨터에 전달하는 쿼리로부터 차별되어진 것이다. 만일, 사용자가 개인적으로 필요한 정보에 부합한 정보의 가치를 포함한다고 여긴다면 문서는 연관성이 있다.
우리의 위의 예제는 필요한 정보가 특정 단어들로 정의되었다는 것은 다소 인위적이다. 반면, 일반적으로 사용자는 "파이프 누수"와 같은 주제에 관심이 있고 그들이 정확한 단어들(파이프 누수)를 사요하던지 "파이프 파열"과 같은 다른 단어를 씀으로써 개념을 표현하던지 상관없이 관련된 문서를 찾길 원한다. IR 시스템의 유효성(검색 결과의 질)에 접근하기 위해 일반적으로 사용자는 쿼리에 대한 시스템이 내주는 결과에 대한 2가지 주요 통계를 알고자 한다.

Precision (정확도) : 얼마만큼의 검색 결과가 필요하고자 하는 정보와 연관성이 있는가?
Recall (재현율) : 컬렉션에서 얼마만큼의 연관된 문서가 시스템에 의해 검색되었는가?

  Precision과 Recall을 포함한 연관성과 평가에 대한 기술된 논의는 chapter 8에서 다룬다.

  우리는 지금 원시적인 방법으로 term-document 행렬을 만들 수 없다. 500K X 1M 행렬은 너무 커서 컴퓨터 메모리에 적재하기 힘든 5천억 개의 0's와 1's를 가진다. 그러나 중요한 관점은 행렬이 너무 희박하다(Sparse Matrix). 즉 0이 아닌 엔트리가 극히 적다는 의미이다.  왜냐하면, 각 문서는 1,000개의 단어들로 구성이 되고, 그 행렬은 10억 개 이상의 1's를 가지지 않아서 구성원의 최소 99.8%가 0이다. 더 나은 표현법은 1의 위치만 기록하는 것이다.
 
 이 아이디어는 정보 검색에서 첫 번째 중요한 개념인 역색인(inverted idnex)의 핵심이다. 이름은 실제로 중복적이다. 색인은 항상 term에서 term이 발생한 문서의 일부분으로 거꾸로 매핑을 한다. 그럼에도 불구하고 역색인, 때론 역파일은 IR에서는 표준 용어로 사용되어지고 있다.


  역색인의 기본적인 생각은 그림 1.3에서 보여준다. 우리는 term들의 dictionary(때로 종종 vacabulary 나 lexicon처럼 언급한다. 이 책에서는 데이터 구조를 위해 dictionary를, term들의 집합을 vocabulary로 사용)를 유지할 것이고, 각 term은 term들이 발생한 문서의 레코드들을 리스트로 가진다. 리스트에서 각 아이템 - 문서에서 출현한 term의 레코드 (그리고, 향후에 종종 문서의 위치) -는 전통적으로 "posting"이라고 불리운다. 리스트는 "posting list (또는 inverted list)"라 불리우고, posting list들은 posting들을 참조한다. 그림 1.3에서 dictionary는 알파벳 순으로 정렬이 되어졌고, 각 posting list는 documen ID로 정렬되어진다. 우리는 이것이 Section 1.3에서 유용하다는 것을 알게 될 것이고 나중에 우리는 또한 이것의 사용 유무를 고려하게 된다. (Section 7.1.5)

** 다음 글 **
1.2 A first take at building an inverted index
1.3 Processing Boolean queries
1.4 The extended Boolean model versus ranked retrieval
1.5 References and further reading