정보검색 관련 간단히 읽기 좋은 서적

[박일남]

정보검색 관련하여 교양서적 정도?

깊게 다루는게 아니라, 정보검색 관련하여 흐름 및 공부 키워드를 리마인드 시키기 위한 책을 소개해 드립니다.

책명: 웹 개발자를 위한 대규모 서비스를 지탱하는 기술

저자: 이토 나오야, 다나카 신지

책 소개: 

출처 http://book.naver.com/bookdb/book_detail.nhn?bid=6468636

『웹 개발자를 위한 대규모 서비스를 지탱하는 기술』은 저자가 서버 1대부터 시작하여 1,000대의 호스트를 운영하기까지 수없이 많이 겪었던 시행착오와 해결책, 먼 길을 돌고 돌아서 비로소 체득한 대규모 서비스 개발과 운용에 관한 핵심 노하우들을 전한다. OS 및 컴퓨터의 동작원리, DB 분산방법, 실전적인 알고리즘을 시스템에 적용하는 방법, 대규모 데이터를 요리하는 검색엔진의 원리와 구조, 시스템 전체를 조망하기 위한 인프라 설계지식 등을 다양한 샘플 코드와 함께 자세하게 소개하고 있다.

내용 요약 공유:

이책에서 제가 개인적으로 관심 있었던 부분은 텍스트 처리쪽 알고리즘 부분입니다.

일부 스포일성? 으로 제가 읽다가 정리한 내용을 아래에 공유해드립니다.

7 알고리즘 실용화

7.1 데이터 규모와 계산량 차이

-       선형탐색의 경우 (Linear Search)

n  1000건: 1000번

n  100만건: 100만번

-       이분탐색의 경우 (Binary Search)

n  1000건: 10번

n  100만건: 20번

-       Order 표기

n  1 < logn < n < nlogn < n^2 < n^3 < n^k < 2^n

7.2 (Trie, AC 기법) 하테나 다이어리의 키워드 링크 구현 방법

블로그에 글을 작성하면 일부 키워드에 링크가 자동으로 걸린다. 이것을 구현하는데 입력된 전문에 대해 27만 단어를 포함하는 키워드 사전과 매칭해서 제작했다.

사전 내에 포함된 모든 단어를 OR 조건으로 잇는 정규표현을 만들어서 사용하는 방법으로 즉 다음과 같이 치환문을 사용하였다.

           $TEXT =~ s/(foo|bar|baz)/&replace_keyword($1)/ge;

-       문제점1

n  키워드는 사용자가 등록하는 것이다. 초기 개발시 어휘수도 많지 않고, DB에서 그때그때 정규표현을 만들어서 키워드 링크를 하는 식의 했었는데, 점점 키워드가 많아짐에 따라 정규표현 처리에 시간이 오래 걸리게 되었다.

u  정규표현을 컴파일하는 처리

l  미리 정규표현을 만들어서 메모리나 디스크 상에 저장해두는 캐싱방법으로 문제를 회피할 수 있었다.

u  정규표현에서 패턴매칭하는 처리

l  새로 추가된 키워드를 키워드 링크에 반영시키기 위해서는 일정 시간에 캐시를 다시 구축해야할 필요가 있거나 혹은 블로그 서비스 특성상 대부분을 차지하는, 그다지 액세스가 없는 블로그에서는 캐시가 효과를 나타내기 어려움이 생겨 해결하진 못하였다.

-       문제점2 – 패턴매칭에 의한 키워드 링크의 문제점

n  정규표현은 패턴매칭 구현에 오토마톤(automaton)을 사용한다,.

n  Perl의 정규표현 구현에 NFA(Nondeterministic Finite Automata)가 이용되고 있다.

n  Perl 뿐 아니라 실용적인 언어 대부분 NFA 엔진의 정규표현을 채용하고 있다.

n  NFA 정규표현은

u  (foo|bar|baz)와 같은 패턴매칭을 앞에서부터 입력값을 살펴가면서 매칭에 실패하면 다음 단어를 시도하고, 또 실패하면 그다음 단어를 시도하는 단순 방법이다.

u  키워드의 개수에 비례하는 계산량이 소요된다.

-       해결방법1 – 정규표현 -> Trie (매칭 구현 변경)

n  패턴매칭에 수반되는 계산량 문제를 해결하기 위해 정규표현을 기반으로 한 방법에서 Trie를 사용한 매칭 구현으로 변경을 했다.

n  Trie는 데이터의 공통 접두사를 모아서 트리구조를 이루는게 특징이다.

n  입력문서를 Trie에 입력한 다음, 엣지를 순회하면서 종단이 발견되면 해당 단어가 포함되어 있는 걸로 간주하는 것이다.

n  예) 노드 0->1->2-> 순회할 경우, 루트로부터 ‘a’의 엣지, ‘b’의 엣지를 순회한다. 그리고 노드2에는 ‘ab’가 종단이라는 것이 기록되어 있다. 이렇게 해서 ‘ab’라는 단어가 이 Trie에 포함되어 있음을 알 수 있다.

a->b->c-> 로 순위한 경우 8번 노드에 도달하게 되는데, 8에는 종단기록이 없기 때문에 “abc”는 Trie에 포함되어 있지 않다

n  예) hogefoo라는 단어일 때, 이 단어를 foo, bar, baz의 Trie 구조를 순회한다면,

h라는 문자열이 포함되어 있지 않고, 다음으로 oge로 순회하려는 경우도, ge, e도 마찬가지로 포함되어있지 않다.

f부터 Tire를 순회하고 oo로 이어지면서 foo가 매칭됨을 알 수 있다.

결국 hogefoo라는 단어의 길이만큼만 계산하면 끝이다.

반면, 정규표현 패턴매칭의 경우, h에 대해 foo, bar, baz 모두와 매칭되는지를 시도하고, o에 대해서도 마찬가지로 반복되므로 키워드수에 비례해서 시간이 필요해지므로 키워드 사전이 커지면 그 차이가 현저해짐을 알 수 있다.

-       해결방법2 – Aho-Corasick (아호코라식)

n  Trie 구조에 의한 패턴매칭을 더욱 빠르게 하는 방법.

n  사전 내에서 패턴매칭을 수행하는 오토마톤을 구축하고 입력 텍스트에 대해 선형 계산시간을 실현한다.

n  이는 계산량이 사전 크기에 의존하지 않는 빠른 방법이다.

n  예) trie에 “ababcdes”를 입력한 경우 bab가 발견된 다음은 ab가 발견될거라는 것은 알고 있다. 그러므로 bab까지 탐색했다면 다시 선두 노드인 0으로 돌아가는 것이 아니라 바로 노드 2로 갈 수 있다는 걸 알 수 있다면 ab를 바로 찾을 수 있다.

n  여기서 6의 다음은 바로 2라고 길을 내는 전처리를 Trie에 대해 수행하는 것이 AC법의 핵심이다. 이는 Trie의 루트부터 너비우선탐색으로 적당한 노드를 찾아감으로써 구성할 수 있다.

n  형태소 분석 엔진 구현에는 입력으로 주어진 문서로부터 사전 내의 모든 단어를 패턴매칭한다는 계산을 수행할 필요가 있다는 점에서 키워드 링크와 동일한 계산이다.

n  또한, 자연어 처리면에서는 이 방법의 태스크는 Trie를 사용하는 것이 표준이다.

-       해결방법3 –Regexp:List로 치환

n  Trie 기반의 정규표현을 생성한다.

n  정규표현식을 + AC 기법을 하이브리드 형으로 개발하였다.

7.3 기사 분류

-       베이지안 필터에 의한 카테고리 판정

n  텍스트 문서 등을 입력받아 거기에 나이브 베이즈(Naïve Bayes) 알고리즘을 적용해서 확률적으로 해당 문서가 어느 카테고리에 속하는지 판정한다.

n  과거에 분류가 끝난 데이터의 통계정보로부터 판정을 수행한다.

n  베이지안 필터는 사전에 ‘이 문서는 이 카테고리, 저 문서는 저 카테고리’라는 수동으로 정답이 되는 데이터를 주고 학습시켜 최종적으로 수동으로 개입하지 않아도 정해를 알 수 있게 되는 프로그램이다.

-       The google Way of Science

n  검색쿼리에 대해 잘못하면, ‘이것을 찾으셨나요?’ 라는 정확한 쿼리 추천 서비스.

n  과거에 사용자가 검색한 쿼리로그를 정해 데이터로 해서 학습을 하여 제시하는 방법이다.

-       나이브 베이즈 (Naïve Bayes)

n  문서 D가 주어졌을 때, 이 문서가 카테고리 C에 속할 조건부 확률을 구하는 문제.

u  P(C|D)

n  여러 카테고리 중에 확률이 가장 높은 값을 나타낸 C가 최종적으로 선택되는 카테고리가 된다.

n  P(C|D)를 직접 계산하는 것은 어렵다, ‘베이즈의 정리’에 따라 계산가능한 식으로 변형할 수 있다.

n  베이즈 정리 그 자체가 원래 그렇다라고 하기보다 잘 알려진 수리로 확률식을 변형할 수 있다는 점이 포인트다.

u  P(C|D) = P(C) * P(D|C) / P(D)

n  분모 P(D)는 문서 D가 발생할 확률인데, 이는 모든 카테고리에 대해 동일한 값으로 무시할 수 있다. 결과적으로 다음과 같이 두 값을 구하기만 하면 된다.

u  P(D|C), P(C)

n  카테고리를 추정하는 데 이 두가지 값을 학습 데이터의 통계정보로부터 산출해내면된다.

n  P(C): 특정 카테고리가 출현할 확률이므로 학습 데이터 중 여러 데이터가 어떤 카테고리로 분류되었는지 그 횟수를 저장해두면 나중에 계산할 수 있다.

n  P(D|C)는 문서 D라는 것은 임의의 단어 W가 연속해서 출현하는 것으로 간주하고,

u  P(D|C) = (W1|C) P(W2|C) P(W3|C) … P(Wn|C)와 같은 식으로 근사할 수 있다.

n  그렇게 되면, 문서 D를 단어로 분할해두고 그 단어마다 어느 카테고리로 분류됐는지 그 횟수를 보존해두면 P(D|C)의 근사값을 구할 수 있다.

7.4 스펠링 오류 수정기능 만드는 법 (사전기반, 편집거리)

-       앞서 설명한 검색 로그 피드백을 이용하여 만들 수도 있지만, 대량의 로그가 없으면?

-       사전이 있다면, 특정 사전 데이터를 정해로 해서 잘못된 해답을 보정하는 스펠링 오류수정기능을 생각해보자.

n  정해 데이터로는 27만 단어 정도의 키워드 사전을 사용했다.

n  사영자가 입력한 검색쿼리와 사전 내의 어구 사이의 편집거리를 구해서 “오류 정도”를 정량화한다.

n  일정한 오류 정도를 기준으로 사전 내에 있는 단어군을 정해 후보로 얻어낸다.

n  얻은 정해 후보를 단어 사용빈도를 기준으로 정렬한다.

n  가장 높은 빈도 단어를 정해로 간주하고 제시한다.

9 검색기술

9.1 검색 시스템이 완성되기까지

-       1. 크롤링

-       2. 저장

-       3. 인덱싱

-       4. 검색

-       5. 스코어링

-       6. 결과표시

9.2 전문 검색의 종류

-       grep형

n  검색 대상 문서를 처음부터 전부 읽어가는 단순한 아키텍처

n  예로 AC법으로 오토마톤을 만들어서 그 안으로 문서를 전부 집어넣는다.

n  검색 대상인 텍스트의 길이를 m, 검색하려는 검색어 길이를 n 이라고 했을 때,

O(mn)만큼 걸린다.

n  단순 검색 O(mn), text: m, word: n

u  KMP(Knuth-morris-pratt)법 O(m+n)

u  BM법(boyer-Moore): worst O(mn), best O(n/m)

n  단점:

u  Order가 크므로 대규모 환경에서 무리가 있다.

n  장점:

u  문서가 갱신되더라도 바로 검색할 수 있다.

u  검색 누락이 없다.

-       Suffix형

n  검색 대상 전문을 검색 가능한 형태로 가지고 있다.

n  데이터 구조로는 Trie나 Suffix Array, Suffix Tree 등이 있다.

n  문서를 검색 가능한 형태로 가지고 있으며, 전부 메모리에 올릴 수 있는 형태가 되는데.

u  Trie로 만든 데이터량이 커졌던 것에서 알 수 있듯이 정보량이 크므로 이론적으로는 검색 가능해진다는 것을 알지만, 실제로 구현하기가 어렵다.

u  정보량을 압축해서 실현할 수 있다.

-       역 인덱스형 (inverted index)

n  단어(term)와 문서를 연관짓는 방법이다.

n  단점:

u  문서와 별개로 역 인덱스를 만들어야 한다.

l  즉, 검색하기 전에 인덱스를 전처리로 만들어야 한다.

l  때문에 grep과 같이 문서가 변경되면 바로 검색결과도 바뀌는 형태의 구현은 할 수 없다.

u  즉시성 측면에선 뛰어나지 못하다.

u  검색의 누락이 생길 수 있다.

l  문서 내에는 포함되어 있는 단어인데 검색결과에는 나오지 않는 경우가 있다.

n  장점:

u  인덱스를 압축함으로써 컴팩트하게 가져갈 수 있고 대규모화하기 쉽다.

9.3 역 인덱스의 구조

-       역 인덱스의 내부구조는 크게 Dictionary와 Posting 두 파트로 나뉜다.

n  1은 검색하고자 하는 문서.

n  2는 문서를 인덱스화한 것.

n  하테나, 시나몬, 등등의 term들, 즉 term의 집합이 Dictionary이다.

n  각 term을 포함하고 있는 문서는 몇 번인지를 나타낸 것이 Postings이다.

-       즉, 역인덱스 = Dictionary + Postings.

-       Term은 문서 내의 단어이고 문서를 검색할 수 있는 단위다. 역 인덱스는 Term을 포함하는 문서를 즉시 발견할 수 있는 구조로 되어 있다.

9.4 Dictionary 만드는 법

-       Dictionary의 구성

n  단어를 term으로 해서 다룬다.

u  사전 + AC법으로 단어를 분리한다.

l  사전이 곧 검색 시스템의 단어공간이 된다.

l  즉, 사전에 들어 잇는 단어만 검색할 수 있다.

u  형태소 분석을 수행한다.

l  형태소 분석기는 문장을 형태소로 나눠서 그 품사를 추정한다.

u  위의 두 방법은 검색 누락이 발생할 수 있다.

n  N-gram을 term으로 다룬다.

u  ‘하테나의’의 경우 n-gram의 n=2,

l  ‘하테’, ‘테나’, ‘나의’로 분할된다.

u  재현률(Recall)은 좋으나, 적합률(Precision)은 안좋다.

-       쿼리로 동일한 규칙으로 분할하기

n  예로 n-gram으로 색인했으면, 쿼리도 동일하게 n-gram 수행.

n  ‘하테나’로 검색할 경우, ‘하테’, ‘테나’로 분할하고. 이 두가지 쿼리로 역 인덱스를 조회하면 두개의 Postings가 얻어진다.

n  교집합을 취하여 문서 번호를 얻는다. (intersection)

-       N-gram 분할 문제와 필터링

n  검색어가 포함하지 않는 결과를 반환하는 문제가 발생할 수 있다.

u  이 문제를 회피하기 위해 보통 필터링을 수행한다.

l  N-gram 인덱스 결과에서 검색 keyword를 전문을 조사한다.

l  grep형과 동일한 검색시간이 소요되므로 문제가 있음.

n  때문에, 역인덱스와 n-gram을 기반으로한 역 인덱스 모두를 사용하고 있다.

9.5 Postings 만드는 법

-       Inverted File index

n  단순하게 문서 ID만을 보유하고 있는 경우

u  문서 ID는 정렬해둔다.

l  정렬해두면 VB code로 압축할 수 있으므로.

u  좌측엔 term, 우측엔 압축된 문서 ID의 리스트로 된 key, value 쌍

l  Hash로 저장 가능하지

-       Full Inverted Index

n  Term이 해당 문서 내의 어느 위치에 출현하는지 위치도 보유하고 있는 경우

u  스코어링에 도움이 된다.

-        

9.6 재현률(Recall)과 적합률(Precision)

           A: 검색결과

           B: 적합한 문서

           C: A and B

-       Recall

n  어느정도의 양, 결과를 반환하는지

u  C/B ?

-       Precision

n  반환된 결과중 옳은게 얼마인지

u  C/A

-       검색 시스템 평가와 재현률/적합률

n  형태소 분석 측면에서는 검색되었으면 하는 게 검색되지 않는 경우가 있다. 하지만 의도하지 않는 결과가 나오는 경우는 적으므로 적합률이 우선시된다.

n  N-gram은 검색누락은 발생하지 않지만 의도하지 않은 결과가 반환되는 경우가 있으므로 재현률이 우선시되고 있다고 생각할 수 있다.