정보 검색의 이론과 실제 (검색엔진을 구현하고 평가하는 방법 | 2022년도 대한민국학술원 선정 교육부 우수학술도서)

스테판버처

구글의소프트웨어엔지니어며,워털루대학의전산학과교수다.

1부.기초지식

1장.들어가며
1.1정보검색이란무엇인가?
1.1.1웹검색
1.1.2다른검색응용프로그램
1.1.3다른정보검색응용분야
1.2정보검색시스템
1.2.1정보검색시스템의기본구조
1.2.2문서갱신
1.2.3성능평가
1.3전자문서다루기
1.3.1본문형식
1.3.2영문에서간단히토큰만들기
1.3.3텀의분포
1.3.4언어모델링
1.4시험용자료모음
1.4.1TREC과업
1.5오픈소스정보검색시스템
1.5.1루씬
1.5.2Indri
1.5.3Wumpus
1.6더읽을거리
1.7연습문제
1.8참고문헌

2장.검색기초
2.1역색인
2.1.1심화예제:구문검색
2.1.2역색인구현하기
2.1.3문서와그밖의요소들
2.2문서선택과순위화
2.2.1벡터공간모델
2.2.2근접도순위화
2.2.3불리언검색
2.3평가
2.3.1재현율과정밀도
2.3.2순위화검색의유효성척도
2.3.3시험용자료만들기
2.3.4능률척도
2.4요약
2.5더읽을거리
2.6연습문제
2.7참고문헌

3장.토큰과텀
3.1영어
3.1.1구두점과대문자
3.1.2어간추출
3.1.3불용어제거
3.2문자
3.3문자N-Gram
3.4유럽언어
3.5한중일언어
3.6더읽을거리
3.7연습문제
3.8참고문헌

2부.색인하기

4장.정적역색인
4.1색인요소와생명주기
4.2사전
4.3포스팅목록
4.4사전과포스팅목록뒤섞기
4.5색인생성
4.5.1메모리상의색인생성
4.5.2정렬기반색인생성
4.5.3병합기반색인생성
4.6다른색인유형
4.7요약
4.8더읽을거리
4.9연습문제
4.10참고문헌

5장.질의처리하기
5.1순위화검색질의처리하기
5.1.1문서하나씩질의처리하기
5.1.2텀하나씩질의처리하기
5.1.3점수분포미리계산하기
5.1.4영향도순색인
5.1.5정적색인잘라내기
5.2경량구조
5.2.1일반화한용어색인목록
5.2.2연산자
5.2.3연산자예제
5.2.4구현
5.3더읽을거리
5.4연습문제
5.5참고문헌

6장.색인압축
6.1범용데이터압축
6.2심볼기반데이터압축
6.2.1모델링과코딩
6.2.2허프만코딩
6.2.3산술코딩
6.2.4심볼기반본문압축
6.3포스팅목록압축하기
6.3.1비모수기반차이압축
6.3.2모수기반차이압축
6.3.3컨텍스트를고려한압축방식
6.3.4질의처리성능을높이는색인압축방식
6.3.5압축효과
6.3.6복호화성능
6.3.7문서재정렬
6.4사전압축하기
6.5요약
6.6더읽을거리
6.7연습문제
6.8참고문헌

7장.동적역색인
7.1일괄갱신
7.2증분색인갱신
7.2.1연속된역색인목록
7.2.1불연속역색인목록
7.3문서삭제
7.3.1무효화목록
7.3.2가비지모음
7.4문서변경
7.5논의점과더읽을거리
7.6연습문제
7.7참고문헌

3부.검색과순위

8장.확률적검색
8.1적합도모델링
8.2이진독립모델
8.3로버트슨/스파크존스가중치공식
8.4텀빈도
8.4.1북스테인의2-푸아송모델
8.4.22-푸아송모델의근사
8.4.3쿼리텀빈도
8.5문서길이:BM25
8.6적합도피드백
8.6.1텀선택
8.6.2의사적합도피드백
8.7필드가중치:BM25F
8.8실험적비교
8.9더읽을거리
8.10연습문제
8.11참고문헌

9장.언어모델링및관련방법론
9.1문서에서질의생성하기
9.2언어모델과평활화
9.3언어모델로순위매기기
9.4쿨백-라이블러발산
9.5무작위성발산
9.5.1무작위성모델
9.5.2엘리트성
9.5.3문서길이정규화
9.6구절검색및순위매기기
9.6.1구절점수매기기
9.6.2구현
9.7실험비교
9.8더읽을거리
9.9연습문제
9.10참고문헌

10장.분류및필터링
10.1자세한예제
10.1.1주제기반배치필터링
10.1.2온라인필터링
10.1.3과거예제에서학습하기
10.1.4언어분류
10.1.5온라인적응형스팸필터링
10.1.6이항분류에서문턱값선택
10.2분류
10.2.1오즈와오즈비
10.2.2분류기만들기
10.2.3학습방식
10.2.4특성엔지니어링
10.3확률적분류기
10.3.1확률추정치
10.3.2확률추정치결합
10.3.3현실적고려사항
10.4선형분류기
10.4.1퍼셉트론알고리즘
10.4.2서포트벡터머신
10.5유사도기반분류기
10.5.1로치오방법
10.5.2기억기반방법
10.6일반화선형모델
10.6.1커널방법
10.7정보이론모델
10.7.1모델비교
10.7.2순차압축모델
10.7.3결정트리와스텀프
10.8실험적비교
10.8.1주제기반온라인필터링
10.8.2온라인적응스팸필터링
10.9더읽을거리
10.10연습문제
10.11참고문헌

11장.병합과메타학습
11.1검색결과병합
11.1.1고정컷오프집계
11.1.2순위및점수집계
11.2스태킹적응필터
11.3스태킹배치분류기
11.3.1홀드아웃검증
11.3.2교차검증
11.4배깅
11.5부스팅
11.6다범주순위화및분류
11.6.1문서대범주점수
11.6.2문서대범주순위병합
11.6.3다범주방법들
11.7순위학습
11.7.1순위학습은무엇인가?
11.7.2순위학습방법들
11.7.3무엇을최적화하나?
11.7.4분류에서순위학습
11.7.5순위검색학습
11.7.6LETOR데이터집합
11.8더읽을거리
11.9연습문제
11.10참고문헌

4부평가

12장.유효성측정
12.1전통적유효성척도
12.1.1재현율과정밀도
12.1.2k개문서에서정밀도(P@k)
12.1.3평균정밀도
12.1.4역순위
12.1.5산술평균대기하평균
12.1.6사용자만족
12.2텍스트검색학회
12.3통계를활용한평가
12.3.1기초및용어
12.3.2신뢰구간
12.3.3비교평가
12.3.4유해한가설검정
12.3.5짝의차이와짝이아닌차이
12.3.6유의성검정
12.3.7타당성과통계적검정력
12.3.8측정정밀도보고
12.3.9메타분석
12.4판정노력최소화하기
12.4.1판정을위한문서선택
12.4.2풀표본추출
12.5비전통적유효성척도
12.5.1등급화적합도
12.5.2불완전하고편향된판정
12.5.3참신성과다양성
12.6더읽을거리
12.7연습문제
12.8참고문헌

13장.능률측정
13.1능률기준
13.1.1처리량과지연시간
13.1.2집계통계및사용자만족
13.2대기열이론
13.2.1켄달표기법
13.2.2M/M/1대기열모델
13.2.3지연시간백분위수와평균이용률
13.3질의스케줄링
13.4캐싱
13.4.13단계캐싱
13.4.2캐시정책
13.4.3검색결과미리불러오기
13.5더읽을거리
13.6연습문제
13.7참고문헌

5부.응용및확장

14장.병렬정보검색
14.1질의병렬처리
14.11문서분할
14.12텀분할
14.13혼합구조
14.14서버복제와장애허용
14.2MapReduce
14.21기본프레임워크
14.22결합기
14.23이차키
14.24장비장애
14.3더읽을거리
14.4연습문제
14.5참고문헌

15장.웹검색
15.1웹구조
15.1.1웹그래프
15.1.2정적페이지와동적페이지
15.1.3닿을수없는웹
15.1.4웹의전체규모
15.2질의와사용자
15.2.1사용자의도
15.2.2클릭행동곡선
15.3정적순위화
15.3.1기본페이지랭크
15.3.2확장한페이지랭크
15.3.3페이지랭크의속성
15.3.4기타링크분석기법:HITS와SALSA
15.3.5기타정적순위화기법
15.4동적순위화
15.4.1앵커텍스트
15.4.2참신성
15.5웹검색평가
15.5.1특정페이지찾기
15.5.2암묵적사용자피드백
15.6웹크롤러
15.6.1크롤러구성요소
15.6.2수집순서
15.6.3페이지중복
15.7요약
15.8더읽을거리
15.8.1링크분석
15.8.2앵커텍스트
15.8.3암묵적피드백
15.8.4웹크롤러
15.9연습문제
15.10참고문헌

16장.XML검색
16.1XML의기초
16.1.1문서형식정의
16.1.2XML스키마
16.2경로,트리,FLWOR
16.2.1XPath
16.2.2NEXI
16.2.3XQuery
16.3색인과질의처리
16.4순위검색
16.4.1요소순위화
16.4.2중복요소
16.4.3검색할수있는요소
16.5평가
16.5.1시험용자료모음
16.5.2유효성척도
16.6더읽을거리
16.7연습문제
16.8참고문헌

5부부록

부록A.컴퓨터성능
A.1디스크순차접근과임의접근
A.2RAM순차접근과임의접근
A.3파이프라인실행과분기예측

★이책의대상독자★

전산학,컴퓨터공학,소프트웨어엔지니어링또는여타관련전공의학부과정수준의지식이있다고가정하고설명한다.다시말해(1)연결자료구조,B-트리,해시함수와같은기초적인자료구조개념(2)알고리즘과시간의복잡도분석(3)운영체제,디스크장치,메모리관리,파일시스템등에익숙해야한다는뜻이다.이와더불어확률변수,분포,확률질량함수와같은기초적인확률과통계이론도알고있다고가정했다.


★이책의구성★

5부로구성됐으며각각독자적인구조를가진다.1부는개론에해당한다.2부에서4부까지는각각주요영역인색인,검색,평가를다룬다.각장은1부를읽은다음순서에상관없이독자적으로읽어도된다.5부는그전까지소개한내용을바탕으로특정응용분야를깊이파고든다.
1부부는정보검색기초를소개한다.1장에서는정보검색시스템구조,용어,문서의특성,문서형식,텀분포,언어모델,문서모음을비롯한기초개념을설명한다.2장은세가지주요주제인색인,검색,평가의기초를설명한다.각주제마다(2부에서4부까지)한부를할애해자세히다룰것이다.2장에서각주제를독립적으로바라볼수있는토대를마련할것이다.1부의마지막인3장에서는1장에서시작한주제를이어가는동시에2장의내용을마무리한다.여기서는특정자연어(사람의언어등)와연관된문제를다루는데,그중에서도토큰생성,즉문서를색인하고검색하도록일련의텀으로바꾸는절차가대표적이다.검색시스템은여러언어가뒤섞인문서를적절히처리할수있어야하며,이런관점에서여러주요언어가갖는중요한특성을논의할것이다.

2부는역색인을만들고읽고유지하는기술에초점을맞춘다.4장에서정적색인을구축하고읽는알고리즘을살펴볼것이다.정적색인은문서모음이자주바뀌지않고,바뀌었을때색인전체를재구축할시간이충분한상황에적합하다.5장은색인읽기와질의처리기법을설명한다.이장에서는문서구조를다루기위한경량구조를소개하고,불리언조건검색에이경량구조를적용해본다.6장은색인압축에관한내용이다.7장은동적문서모음을유지하는알고리즘을소개한다.동적문서모음은질의에비해서문서갱신이잦고,갱신을곧바로반영해야하는속성을가진다.

3부는검색기법과알고리즘을다룬다.8장과9장은문서내용에기반한순위화검색의주요한두가지기법을소개,비교하는데,바로확률적기법과언어모델기법이다.이러한순위화검색기법은명시적인적합도관련정보,즉문서구조와사용자피드백과질의확장으로부터얻는정보를도입하면효과가더높아높아진다.각기법에관련된자세한내용을논의할것이다.10장은문서를분류하고제한하는기술을소개하며,문서구분을위한기초적인머신러닝알고리즘도설명한다.11장에서는메타학습알고리즘과이를순위화에적용하는방법과더불어,증거와매개변수조정을어떻게결합하는지소개한다.

4부의주제는정보검색기법평가다.검색유효성과능률이라는두가지개념을개별장에서자세히설명한다.12장은기초적인검색유효성지표를제시하고,유효성을측정하기위한통계적기반을탐구하며,최근십여년간전통적인정보검색평가방법론을넘어서새로제안된지표들을논의한다.13장은검색시스템의성능을응답시간과처리량의관점에서평가하는방법을설명한다.

마지막5부에서는특정검색응용분야몇가지를선택해4부까지알아본일반적인지식과개념을세분화,구체화한다.병렬검색엔진의구조와동작방식은14장에서다룬다.15장은웹검색엔진에관한내용이다.여기에는링크분석,문서수집,중복탐지와같은내용이포함된다.16장은XML문서를대상으로한정보검색이다.각장끝부분에는더읽어볼만한자료와연습문제를제공한다.연습문제는대체로각장에서소개한개념을시험하고확장해본다.종이와연필만있으면몇분안에풀수있기도하고제법복잡한프로그래밍프로젝트문제도있다.참고자료와연습문제를통해각장의본문에서다루지못한중요한개념을배울수있다.

★옮긴이의말★

오늘날누구나일상에서검색서비스를사용한다.하지만비전공자는물론이고인터넷서비스에종사하는개발자대다수도검색시스템의구조와원리는잘모른다.정보검색은데이터베이스와같은관련분야와공통점도있지만,그들과구분되는고유한특성도분명히갖고있기때문이다.검색서비스에는다양한컴퓨터시스템이필요하지만그중검색엔진은특히모든검색서비스의공통요소이자핵심이다.일반적으로검색엔진이라고말하면대개유명한검색서비스를떠올린다.그리고검색엔진의정의를묻는다면(검색업계종사자조차)저마다의관점이나관심사에따라다른대답을내놓을것이다.사견으로는검색서비스를뜻하는광의의검색엔진과문서를색인하고질의를처리하는시스템을뜻하는협의의검색엔진으로나눌수있을것같다.다시말해,검색엔진(서비스)의핵심에검색엔진(시스템)이자리한다.이제는수많은인터넷서비스에서검색이필수기능으로여겨진다.여러분이직접검색엔진을구현하지않더라도,어떤방식으로든검색에엮인일을맡는다면이책이도움이될것이다.서두에서언급한정보검색의고유한특성을알면더효율적으로목적을달성할수있다.동작원리를알면좋은활용법도찾을수있으며,새로운아이디어를구현하는데도밑거름이될수있다.어느분야나마찬가지지만,기초가탄탄하면응용하기쉬워진다.이책을번역하면서다양한기술용어를되도록이면우리말로옮기고자노력했다.그중학계나산업계에서굳어진원어도있어서망설이기도했지만,정보검색분야가생소한독자의이해를돕고싶었다.영문용어가익숙한독자들은다소어색하게느낄수있다.이점너그러이양해를구한다.
임형준


인터넷시대에검색엔진은우리삶에없어서는안되는기능이됐다.뉴스를보거나,모르는단어를찾거나,물건을사거나,맛집을가거나,다른사람의의견을읽을때도먼저검색을한다.꼭네이버나구글같은검색서비스를이용하지않더라도,검색기능은SNS에도,휴대폰사진앱에도,서점의책검색대에도,패스트푸드점의키오스크에도들어가있어서하루에한번이상은꼭무언가를검색하게되는것같다.
이렇게검색기능이여러곳에서다양하게쓰이는만큼시중에는편리하게쓸수있는검색엔진솔루션및오픈소스툴이많이나와있다.개발자들은실제검색엔진이구체적으로어떤원리로어떻게작동하는지잘몰라도,데이터를준비한후에여러검색솔루션중에하나를선택해서약간설정해주는것만으로검색엔진기능을자신의서비스에비교적쉽게추가할수있다.
하지만모든일이그렇듯,기초를아는것이중요하다.전반적인원리를이해하고있으면똑같은문제를더빠르고쉽게풀수도있고,새로운아이디어를적용해서다른방식으로응용하는것도가능해진다.이책은실제검색엔진을연구하고만들어온저자들의경험을바탕으로정보검색론의전반적인내용을한번씩다루고있어서정보검색론의기초를배우는데많은도움이될것으로생각한다.실제로검색순위화로직을오래개발해온나역시번역하면서그동안자세히몰랐던내용을한번더배울기회를가질수있었던것같다.정보검색론이및검색엔진기술에관심이있거나,관련일을하시는분들은참고서적으로두고읽어보시면좋으리라생각한다.
김진홍