[Java] Map과 List로 검색엔진 구현해보기 -2-

앞서 말씀드린대로 검색엔진의 가장 기본적인 구조와 자바에 대한 기초 교육을 겸하려했던
예제입니다. 우선 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 패키지
에서 확인 하실 수 있습니다.