이 주제에 대한 마지막 글입니다.
이전에 Indexing 부분까지 작성하고 까먹고 있었네요.. --ㅋ

이전 포스트까지
문서를 Indexing하고 해당 문서를 저장하여 두는 Store까지 살펴보았습니다.

간단하게 요약하면 문서의 내용을
분석하여 키워드를 추출하고, 그 키워드를 필드별로 해당 키워드를 가진
문서번호(내부적인 unique number)와 연결하여 인덱스 파일에 저장해두는 개념이었습니다.

그렇다면 검색은 어떤 방식일까요?

키워드를 통해 위 인덱스파일에서
문서번호를 검색하여 리턴하는 구조가 될 것 입니다.

  IndexSearcher.java

인덱스파일은 변경이 될 수 있도록 외부에서 인덱스파일을 셋팅 할 수 있도록 하였습니다.
소스의 간소화를 위해 "제목"과 "본문" 필드에 대해서 키워드로 검색을 수행하도록
하드코딩하였습니다.

그리고 and검색을 위해 제목에 대한 검색으로 나온 rowid와 필드에 대한 검색으로 나온 rowid를
체크하여 (loop) 확인하고 있습니다. 실제로는 이런식으로는 안 하겠죠.

그리고 getDoc(long) 메서드가 있습니다. 검색결과로 리턴되는 것은 실제로는 문서ID의 리스트입니다.

이 문서ID에 해당하는 실제 문서를 가져오기 위해 사용되는 메서드입니다.

테스트케이스는 아래와 같습니다.

IndexSearcherTest.java

결과


색인 : -----------------------------------------
필드 명 : 본문
키워드 : 조끼 - rowId : [2]
키워드 : 운동화 - rowId : [0, 1]
키워드 : 좋아요 - rowId : [0, 1]
키워드 : 싫어요 - rowId : [2]
키워드 : 아디다스 - rowId : [1]
키워드 : 나이키 - rowId : [0]
키워드 : 청바지 - rowId : [2]

-----------------------------------------
필드 명 : 제목
키워드 : 운동화 - rowId : [0, 1, 2]
키워드 : 아디다스 - rowId : [1]
키워드 : 나이키 - rowId : [0]
키워드 : 청바지 - rowId : [2]


결과 : [0, 1]
resultDoc1 : Document [rowId=0, fieldList=[Field [name=제목, value=나이키 운동화], Field [name=본문, value=나이키 운동화 좋아요]]]
resultDoc2 : Document [rowId=1, fieldList=[Field [name=제목, value=아디다스 운동화], Field [name=본문, value=아디다스 운동화 좋아요]]]


우선 Document를 3개 생성하여 색인 대상 문서를 만들어냅니다.
그리고 색인을 하게 되죠. 결과를 보시면 추출된 키워드와 키워드별로 연결된 문서ID가 로깅되는 것을
확인 하실 수 있습니다. 본문과 제목필드에 대해서 모두 수행이 되지요.

테스트는 "운동화"라는 검색어로 진행됩니다.

AND검색으로 수행이 되어 최종적으로 0, 1번 문서가 리턴되는 것을 보실 수 있고
해당 ID의 문서를 IndexSearcher의 getDoc(Long) 메서드를 통해서 가져와서 로깅하는 것도 확인 가능합니다.

3번에 걸쳐서 간단하게나마 검색엔진의 자료구조를 구현해보았습니다.

실제 검색엔진에서는
훨씬 복잡하고 많은 기능이 있을테고
무엇보다도 중요한 속도와 대용량 처리를 위한 각종 최적화 작업이
코드에 포함되어 있을 것 입니다.

앞서 말씀드렸듯이 검색파트를 맡고 있으면서 신규로 들어오는
후배들을 위한 공부용 코드임을 인지하여주세요~

예제코드는
https://github.com/need4spd/searchengine 
에서 받아보시거나 확인하실 수 있습니다. 
Posted by 용식
앞서 말씀드린대로 검색엔진의 가장 기본적인 구조와 자바에 대한 기초 교육을 겸하려했던
예제입니다. 우선 Map과 List로 검색엔진의 원리를 구현하려면 우선 검색엔진에서의 역인덱스 구조에
대해서 알아야 합니다.

제 블로그에서도 몇 번 언급은 되었었지만 간단하게 말씀드리면 문서들로부터 키워드를 추출하고
그 키워드가 어느 문서에 있는지를 기록해 둔 형태입니다. 책을 사면 맨 앞에 목차(INDEX)가 있고
일반적으로 맨 뒤에 보면 키워드와 해당 키워드의 내용이 있는 페이지가 들어있는 부록이 있는데 이것이
역인덱스 구조입니다.

순서보다는 원하는 키워드로 찾고자 하는 내용을 가장 빠르게 접근 할 수 있는 구조로 되어있습니다.

이것을 Map과 List로 구현한다고 하면...
Map의 Key가 키워드가 될 것이고 Value의 List에는 해당 키워드가 추출된 문서들과 연결되는 어떤 값 (책이라면 페이지일 수도 있고, 내부적으로 유니크한 값을 갖는 ROWID와 같은 값일 수도 있을 것 입니다.)들의 집합이 될 것 입니다.

간단하게 표시하면 

[청바지] - 1,3,5,8
[나이키] - 1,2,4,8,9
(숫자는 페이지를 뜻함)


이런 구조가 됩니다.

청바지가 나오는 페이지는 1,3,5,8 나이키가 나오는 페이지는 1,2,4,8,9가 되는 것이고..
청바지와 나이키가 모두 나오는 페이지는 AND연산을 통해 1,8 임을 알 수 있습니다.

그러면 하나하나 간단하게 구현을 해보겠습니다.

우선 키워드를 추출하기 위해서는 문서를 읽고 그 문서에서 유효한 키워드를 추출 할 수 있는
분석모듈이 있어야 합니다. 한글에서는 이를 형태소분석기라고 보통 이야기합니다.

이건 단순히 구현하는 것이 목표이므로 이 분석모듈은 그냥 공백을 기준으로 단어를 추출해내도록
하려고 합니다. 다만 Analyzer는 검색엔진의 자료구조를 만들어본다는 취지에는 조금 어긋나므로 여기에 내용을 담지는
않으려고 합니다. 아래 말씀드릴 Repository에는 소스가 올라가 있으므로 참고는 해주세요~

다만 아래와 같이 작동을 합니다.

  WhiteSpaceAnalyzerTest.java

루씬의 WhitespaceAnalyzer 생각하시면 되고요 내부적으로 Token이라는 클래스를 만들어서
이를 키워드 추출에 사용하고 있습니다.

그 다음 필요한 것이 분석하고 색인 할 문서를 나타낼 클래스입니다.

마찬가지로 루씬의 네이밍을본따고 Document라는 이름으로 클래스를 만들고 Document 클래스 내부적으로 사용 할
Field클래스를 만들겠습니다.

이름만 같을 뿐이지 구현 내용은 완전 다릅니다. ^^;


Document.java
Field.java

간단한 구조입니다.
Field는 Field 이름을 나타내는 String 변수와 값을 나타내는 String 변수 두개만을 가지고 있습니다.
Document는 내부적으로 다른 Document와 구분하기 위한 rowId와 가지고 있는 필드들을 나타내는 List<Field>와
Field의 이름을 Key로하고 해당 Field를 Value로 하는 Map<String, Field>변수를 가지고 있습니다.

색인이나 문서를 저장 할 때 하나의 Document는 여러 Field를 가질 수 있고 이 Field들의 값으로
검색이나 색인등을 하게 될 것 입니다.

그 다음에는 실제로 역인덱스 형태의 구조를 갖는 클래스가 필요하고
검색이 된 Document의 내용을 보여주기 위해서는 색인된 Document들을 저장하고 있는 클래스가 필요합니다.

이 클래스들을 살펴보겠습니다.

우선 색인 된 모든 Document들을 가지고 있게 될 StoredDocuments 입니다.


StoredDocuments.java

Map<Long, Document> 변수를 가지고 있습니다. 내부적으로 Document들을 구분하기 위한 rowId를 Key로하고
그 rowId를 갖는 Document를 Value로 합니다. 어딘가에서는 각 Document들의 rowId를 순차적으로 생성시켜주는
부분이 있을 것 입니다. 그 부분이 StoredDocuments 클래스가 될 수도 있고 다른 클래스가 될 수도 있을 것 같습니다.
그리고, 일단 메모리상에 모든 Document들을 가지고 있어야하므로 싱글턴 클래스가 되도록 구현하였습니다.

그 다음에는 인덱스파일의 역할을 할 클래스입니다. 구현하기 나름이겠지만 저는 이부분을 두개의 클래스로 나누어 구현하였습니다.

우선 검색을 할 경우에 "제목=나이키 and 본문=운동화" 이런식으로 Document가 가지고 있는 필드에 대해서 각각 키워드를
달리하여 혹은 같게 하여 검색하는 경우가 많을 것 입니다. 이를 처리해주기 위해서 우선 
IndexedField라는 클래스를 만들었습니다.


IndexedField.java
필드명을 나타내는 String 변수와 키워드를 Key로 하고 해당 키워드가 들어있는 문서의 rowID들을 Value로 하는 Map<String, List<Long>> 변수를 가지고 있습니다.

즉, "제목=나이키" 라는 질의가 들어온다면 IndexField의 인스턴스 중 fieldName이 "제목"인 인스턴스를 찾아서 Map으로부터
"나이키" 키워드에 들어있는 Value (Rowid들의 집합이 되겠죠)를 사용하여, StoredDocuments로부터 해당 Document를 가져오는 구조가 됩니다.

그렇다면 결국 이 IndexedField를 누군가는 또 가지고 있어야 한다는 이야기가 됩니다. 그 역할을 하는 것이 IndexFile 클래스입니다.

  IndexField.java

이 클래스는 필드명을 Key로하고 그 필드명을 갖는 IndexedField를 Value로 하는 Map<String, IndexedField> 변수를 하나 가지고 있습니다. StoredDocuments와 마찬가지로 싱글턴 클래스이고요...

결국

제목: 나이키 운동화,
본문: 나이키 운동화 좋아요

라는 후기 하나와

제목: 아디다스 운동화,
본문: 아디다스 운동화 좋아요

라는 후기를 색인한다고 하면

우선 StoredDocuments의 rowId:1로 첫번쨰후기, rowId:2로 두번째후기가 저장이 되고
제목이라는 필드명의 IndexedField에 "나이키:1" ,"운동화:1,2" 와 같은 식으로 Map 데이터가 채워질 것 입니다.
아래와 같이 채워지겠죠.. (인스턴스의 구분을 위해 #1, #2를 붙였습니다.)

IndexedField #1
fieldName : 제목
rowIdsByKeyword :  "나이키:1" ,"운동화:1,2"

IndexedField #2
fieldName : 본문
rowIdsByKeyword :  "나이키:1" ,"운동화:1,2", "좋아요:1,2"


키워드 추출은 공백만을 기준으로 추출하게 될테고요...

그리고 이제 이 IndexedField들을 IndexFile이 가지고 있게 됩니다.

IndexFile
indexedDocs : "제목:IndexedField #1", "본문:IndexedField #2"


만약 검색질의가 "제목:나이키"가 들어온다면
1. IndexField로부터 "제목" 필드로 된 IndexedField를 꺼내서
2. 그 중 "나이키"라는 키워드를 가지고 있는 Document들의 RowId 들을 받아와서
3. 그 Rowid로 StoredDocuments에서 원문서를 꺼내서 내용을 보내주는 구조가 되는 것 입니다.


다음 포스트에서 실제로 위와 같이 색인을 하는 클래스와 검색을 하는 클래스를 알아보겠습니다.

예제소스는
https://github.com/need4spd/sampleCode의 searchengine 패키지
에서 확인 하실 수 있습니다.


Posted by 용식