• 컴퓨터/IT > 데이터베이스 > 데이터베이스 일반

• [시리즈] 에이콘 데이터 과학 시리즈 [54]

반디앤루니스 리뷰

★ 요약 ★

정보 검색의 기본 개념부터 검색엔진의 자료 구조, 질의 처리 방식을 비롯한 구현 기술을 거쳐 확률론에 기반한 전통적인 순위화 기법에서 머신러닝을 활용한 최신 순위화 기법에 이르기까지, 이론과 실제를 총망라한다. 더불어 웹 검색과 같은 응용 방식도 다루고 있어서, 검색엔진을 직접 구현하고자 하는 독자뿐만 아니라 검색엔진을 잘 활용하고 싶은 독자에게도 많은 도움이 될 것이다.

출판사 리뷰

스테판 버처(지은이)의 말 정보 검색 이론은 현대 검색엔진의 근간을 이룬다. 이 책은 전산학, 컴퓨터 공학, 소프트웨어 공학 분야의 대학원생과 현업 전문가를 대상으로 정보 검색 이론을 소개한다. 알고리즘, 자료 구조, 색인, 검색, 평가와 같은 핵심 주제는 물론이고 더 깊이 탐구할 수 있는 바탕을 제공함으로써 폭넓은 관심을 끌 만한 주제를 선정했다. 또한 웹 검색엔진, 병렬 처리 시스템, XML 검색과 같이 잘 알려졌거나 향후 널리 쓰일 응용 분야의 특성을 다루는 데에도 신경을 썼다. 이론과 실제 사이에서 균형을 잡으면서도, 구현 방식이나 실험 결과 등을 강조해서 실용성에 조금 더 무게를 실었다. 본문에서 소개한 기법은 가급적 실험을 거쳐 비교, 평가했다. 각 장 마지막에는 연습 문제와 프로젝트가 나온다. Wumpus는 저자 중 한 사람이 개발에 참여한 멀티유저 오픈소스 정보 검색 시스템으로서, 모델을 구현하고 수업 과제의 기반 내용을 제공하는 데 활용했다.

★ 지은이의 말 ★

정보 검색 이론은 현대 검색엔진의 근간을 이룬다. 이 책은 전산학, 컴퓨터 공학, 소프트웨어 공학 분야의 대학원생과 현업 전문가를 대상으로 정보 검색 이론을 소개한다. 알고리즘, 자료 구조, 색인, 검색, 평가와 같은 핵심 주제는 물론이고 더 깊이 탐구할 수 있는 바탕을 제공함으로써 폭넓은 관심을 끌 만한 주제를 선정했다. 또한 웹 검색엔진, 병렬 처리 시스템, XML 검색과 같이 잘 알려졌거나 향후 널리 쓰일 응용 분야의 특성을 다루는 데에도 신경을 썼다. 이론과 실제 사이에서 균형을 잡으면서도, 구현 방식이나 실험 결과 등을 강조해서 실용성에 조금 더 무게를 실었다. 본문에서 소개한 기법은 가급적 실험을 거쳐 비교, 평가했다. 각 장 마지막에는 연습 문제와 프로젝트가 나온다. Wumpus는 저자 중 한 사람이 개발에 참여한 멀티유저 오픈소스 정보 검색 시스템으로서, 모델을 구현하고 수업 과제의 기반 내용을 제공하는 데 활용했다.

★ 옮긴이의 말 ★

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

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

김진홍

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.1 TREC 과업
1.5 오픈소스 정보 검색 시스템
1.5.1 루씬
1.5.2 Indri
1.5.3 Wumpus
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.2 2-푸아송 모델의 근사
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.6 LETOR 데이터 집합
11.8 더 읽을거리
11.9 연습 문제
11.10 참고문헌

4부 평가

12장. 유효성 측정
12.1 전통적 유효성 척도
12.1.1 재현율과 정밀도
12.1.2 k 개 문서에서 정밀도(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.2 M/M/1 대기열 모델
13.2.3 지연 시간 백분위 수와 평균 이용률
13.3 질의 스케줄링
13.4 캐싱
13.4.1 3단계 캐싱
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.2 MapReduce
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.1 XML의 기초
16.1.1 문서 형식 정의
16.1.2 XML 스키마
16.2 경로, 트리, FLWOR
16.2.1 XPath
16.2.2 NEXI
16.2.3 XQuery
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.2 RAM 순차 접근과 임의 접근
A.3 파이프라인 실행과 분기 예측