달력

112017  이전 다음

  •  
  •  
  •  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  •  
  •  
검색엔진을 만들다 보면, 색인어로 등록 하면 안될 키워드가 있고(섹스, 도박, 자살 등등)
서로 비슷한 키워드가 있다.(LG, 엘지, 앨지 이런것들...)
fastcat에서는 한글 형태소 분석할때 사용하는 사전, 유의어 사전, 금지어 사전, 사용자 등록 사전이 있다.

그럼 이 사전을 어디다가 쓰느냐? 

색인시, 키워드를 추출할때 사용하기도 하고, 검색 질의가 왔을때 질의를 분석할때 사용하기도 한다.
만약에 사전이 없다면 색인어로 나이키가 있는데, 사용자가 nike를 쳤을때 검색이 안되는 뭐 그런..(비유가 맞나?;;)

  SearchFieldReader.java, KoreanNounExtractor.java 에서 사용하고 있다.
사전의 용도를 알았으니 fastcat에서는 어떤 자료구조로 사전을 구성했는지 알아보도록 하자.
class 구성은 아래와 같다.


유의어사전은 1 : n 이기 때문에 Map, 그외 다른 사전은 1:1이기 때문에 Set을 사용하였다.
HashSetDictionary와 HashMapDictionary의 차이점을 보자니 termArray밖에 없으므로
HashMapDictionary에 대해서만 설명하려고 한다.(오잉? ㅋㅋㅋㅋㅋ)

근데 변수명을 보자니 어디서 많이 봤다....아~!!! 

[Fastcat]FullIndexJob을 알아보자(3) 에서 나름 설명한 그것이다.(자료구조나 조금 복잡한 알고리즘을 쉽게 설명하는 그런 능력을 갖고싶다....하악...)

termArray는 MemoryPosting에서 색인어가 저장된 idx와 동일한 idx 문서 번호를 가지고 있었듯이
(아래 처럼 postingArray에 keyPos와 동일한 idx에 문서번호 저장)

PostingBuffer old = postingArray[idx];

postingArray[idx] = p;

return old; 

 
HashMapDictionary에서도 keyPos에 해당하는 term은 keyArray에 저장이 되어있을 것이고, 그 term에 해당하는 유의어들이 동일한 idx의 termArray에 저장이 되어있다. 

IRService.java 에서 Dic.init() 으로 서버 구동시 사전을 로딩한다.
그 후에 검색이나 색인작업시 아래와같이 사전을 활용한다.

 
저작자 표시 비영리
신고
Posted by 오산돌구
저번시간에 DocumentWriter에 이어서 이번에는  SearchWriter, SortWriter, GroupWriter 알아보려 한다.

우선 SearchWriter에 초기화 부분은 아래와 같다.
field(schema.xml)에서 index가 설정되어 있는 갯수 만큼 루프를 돈다.
해당 필드 indexing 할때 사용할 class는
Object t = IRSettings.classLoader.loadObject(handlerName); 에서 가져와 tokenizers에 저장한다.
마지막을 색인하는동안에도 검색은 되어야 하므로 임시파일에 기록한다.(tmpOutput)

인자 설명 : indexFieldNum은 schema.xml에서 index의 번호(sample에서는 title필드가 0),
docNo는 현재 색인하고 있는 문서 번호
field는 색인할 필드의 정보 (sample에서는 title, tag, body가 입력으로 들어온다)



SearchWriter에서 사용되는 Class들의 관계도를 나름 그려보았다.   Tokenizer에서 KoreanTokenizer도 있고 EnglishTokenizer도 있다. 
색인할때 어떻게 색인어를 추출할지는 Tokenizer를 상속 받아서 구현하면 된다는 얘기다.
아래는 KoreaTokenizer의 Sequence Diagram을 그려보았다.




TypeTokenizer에서는 이전 문자와의 관계(영어,숫자,한글 같은...)를 따져서 token을 해주고 KoreanNounExtractor에서 명사 추출을 한다.
그래서 추출된 단어가 색인어로 들어간다(MemoryPosting)  
MemoryPosting을 보면 ......"어? 이거 어디서 봤는데?" 라는 느낌이 온다.
그렇다....DocumentWriter에서 본 구조가 나온다. 
이번에는 gif파일로 그려보았다. 나같이 초급개발자가 소스 볼때 조금이나마 시간 절약을 위해..

int[] bucket, int[] keypos, int[] nextIdx, char[] keyarray가 있습니다.





key값을 hash Function 통해 나온 값이 bucket 배열의 index가 되고, 해당 값에는 keypos의 index를 가지고 있다.
keypos의 index는 차례대로 증가되는데 그 값을 bucket이 가지는 것이다.

그럼 keypos에는 어떤값이 있냐~~ 하면 keyarray에서 사용가능한 마지막 index가 저장되어있다.
처음에는 keyarray에 아무것도 저장이 안되어있으니까, 0을 가리킬것이고, 그곳에 abc를 저장하면
다음 keypos에는 3이 저장된다.

keyarray의 데이타를 얻기위해 자신의 keypos값(여기서는 keypos[0])과 다음 keypos값(여기서는 keypos[1])을 이용해서 keyarray에서 데이타를 가져올수있다.    

keyarray에는 해당 key값을 기록하고 value는 keypos 길이만큼의 value Array가 있어서 keypos의 index와 

동일한 index에 value를 저장합니다.
(말로는 참........힘드네요백문이 불여일견;; )


근데 여기서 nextIdx라는 게 있는데 존재하는 이유는 아래 그림과 같다.  collision~!!!!



keypos크기만큼 할당된 nextIdx가 충돌시 다음 keypos의 Idx를 가리키게 된다.

위 그림을 예로 들어 설명하겠다.
현재 3개 데이타가 들어온 상태에서 4번째 데이타가 들어왔는데, 두번째와 (그냥 눈으로 보기에) 겹친다.
그럼 당연히 해당 keypos에는 값이 있다.
그럼 동일한 데이타가 들어와서 중복된건지, 다른 데이타인데, hash function으로 나온 값이 중복된걸수도있는데,
이 판단은 keyarray에 있는 데이타와 들어온 데이타를 비교함으로 그 여부를 판단한다.

아까 keypos의 index는 차례대로 증가한다고 했는데, 충돌이 나면 nextIdx는 증가되고 있는
keypos의 index가 저장된다. ;;   nextIdx[0] 에  증가되고있는 keypos의 index가 저장되는겁니다~!!!
(이것도 말로하니까 어려운데 그림으로 설명하죠~!!)





그 다음은 SortFieldWriter이다.
schema.xml에서 sort설정을 한 field가 적용되는건데, 숫자는 상관없지만 문자열의 경우는 size까지 정해줘야한다.
다른데서 이 데이타를 어떻게 하는지는 모르겠는데 SortFieldWriter에서는  filed data를 정해진 size만큼 파일에 기록한다.


GroupFieldWriter에서도 hash을 이용한 저장구조를 사용한다. 
조금 다른점은 부분색인일 경우  PrimaryKeyIndexReader을 이용해서 groupNo를 check한다.
그리고 hash 구조가 field별로 따로 저장이 된다는 점이다. :  )

hash를 이용한 구조 :  keypos에서는 실제 데이타가 저장되어있는 position이 저장 되어있고,
keypos의 index와 동일하게 문서번호나 그룹번호가 저장되어 있다고 생각하면 편할것 같다.


어떻게 어떻게 구렁이 담넘어가듯이 하다보니 FullIndex가 끝이 났다.
다음에는 Search를 보려고 한다. 다음주부터는 본격적으로 회사일이  주어진다고 하는데 언제가 될지는......
Search가 끝나면 사전 적용하는 부분을 볼까 생각중이다.

더 많이 노력해서, 더 많은 사람에게 개발 지식을 전파 했으면 좋겠다. 오픈프로젝트 활동이나, 블로그 포스팅이나, 하고싶은건 많다~ ㅋㅋ




저작자 표시 비영리
신고
Posted by 오산돌구
SegmentWriter에 대해 알아보는 시간이다.

SegmentWriter에는  문서 텍스트 및 포스팅 정보, 렉시콘, 필터, 정렬, 그룹에 필요한 정보를 가공하는 역할을 한다.

 SourceReader에서 하나의 문서를 schema.xml에서 정의한 속성대로 저장한다.
한문서를 읽을때마다   DocumentWriter, SearchWriter, FilterWriter, SortWriter, GroupWriter의 write를 실행한다.
먼저 DocumentWriter를 알아보자

 압축된 문서를 저장하는 docOutput, docOutput에서 문서위치를 저장하는 positionOutput,
삭제할 문서 목록을 저장하는 deleteSet, 마지막으로 PrimaryKey를 저장하는 pkIndexWriter
DocumentWriter를 실행하면 총 4개의 파일이 생성된다.
우선 문서 저장(docOutput, positionOutput)에 대해 알아보자.

하나의 문서에 대해서 Schema에서 지정한 필드 수만큼 for문을 돈다.
Field를 하나씩 돌면서 이 데이타를 저장할지 말지를 { if(fields.get(i).store)} 결정하고
byte 배열 fbaos 에 저장한다.

if((localDocNo + 1) % DOCUMENT_BLOCK_SIZE == 0){
writeInternal();
}

내부문서 번호+1이 DOCUMENT_BLOCK_SIZE의 배수일 경우 writeInternal을 실행하는데
writeInternal을 보면 알겠지만 fbaos을 압축해서 파일에 기록하는 기능을 한다.


위 그림이 압축된 문서와 압축된 문서의 위치 정보를 저장할때의 구조이다.  ( 안쓴 부분이 있는데, 압축된 문서의 위치 저장할때, 맨 앞부분, header에는 총 문서번호와 DOCUMENT_BLOCK_SIZE를 기록합니다.)
검색할때는 문서번호 / DOCUMENT_BLOCK_SIZE 의 몫이 압축된 문서의 위치정보이고
압축된 문서를 가져오면, 압축을 풀고  문서번호 / DOCUMENT_BLOCK_SIZE 의 나머지로 문서를 가져올것같다.
(아직 검색부분은 보지못했는데, 그냥 저의 생각입니다.;;)


다음은 PrimaryKeyIndexWriter를 보자.
field의 primary가 true인 필드 데이타를 저장할것이다. 
int preDocNo = pkIndexWriter.put(buffer.array(), buffer.pos(), localDocNo);
Primary Index는 아래와 같은 구조를 가진다.    (ID가 14401인 데이타 저장)

 


bucket과 keyPos는 int형 배열이고, array는 byte형 배열이다.

bucket의 배열 인덱스는 필드데이타를 해싱한결과이고, 값은 keyPos 배열의 인덱스가 저장되어있다.
keyPos의  배열 인덱스는 sequence 저장이 되고, 값은 데이타가 저장된 array의 시작 인덱스가 저장되어있다.
intValueArray의 배열 인덱스는 keyPos의 인덱스와 동일하다. 배열의 값은 내부 문서번호가 저장되어있다.
keyPos의 4번째 데이타와 intValueArray의 4번째 내부문서번호는 서로 연결된(?) 데이타이다. 

int형 배열 nextIdx도 있는데, 해싱의 중복이 발생하기 때문에 이를 해결하기 위해 만든 변수이다.
해싱한 결과들이 중복이 없다면, bucket과 keyPos는 1:1관계가 되어서 바로바로 찾으면 된다.

하지만 중복이 발생한다면 1:N관계가 된다. bucket은 하나의 keyPos만 가리킬수가 있다.
그래서 데이타가 다를경우, nextIdx에 다음 이동할 keyPos의 인덱스값을 저장해서, 탐색을 진행한다.

동일한 데이타가 입력이 되었다는건 수정이 일어났다고 볼수있으므로, 기존에 저장되어 있는 문서번호를 리턴해서
다음에 알아볼 삭제 문서 체크에 사용한다.

모든 문서에 대해서 primaryKeyIndex 처리를 하면 output, indexOutput을 생성하는데 
output에는    [primary가 true인 (data의 길이, data, 문서번호)] 형식으로 저장이 되고,
indexOuptut에는 indexInterval마다 기록을 하는데 [primary가 true인 (data의 길이, data, output의 position)] 형식으로 저장이 된다.

검색할때,  indexOutput에 있는 data를 비교하면서 indexOutput의 data보다 크거나 같은 부분을 찾고 output을 뒤지는 방식으로 진행될것같다.  (이것도 추측...)



마지막으로 알아볼건 삭제 문서파일 생성이다.
int preDocNo = pkIndexWriter.put(buffer.array(),
   buffer.pos(), localDocNo);

preDocNo은 삭제할 문서번호이다.

대강의 전체 문서의 갯수를 구한후 하나의 long 변수는 64개의 문서를 체크한다. 
64번째 문서가 삭제되는거라고 하면 0000 0000  0000 0000  0000 0000 0000 0000  0000 0000  0000 0000  0000 0000 0000 0001
이 되는것이다.  모든 문서에 대해 delete 검사를 마치면 save함수로 파일에 저장한다.
저작자 표시 비영리
신고
Posted by 오산돌구
이번에는 전체색인을 fastcat에서는 어떻게 하는지 알아보자.

 


schema에서는 각 필드의 정보들(primary, sort, type, group등)을 schema.xml에서 읽어들이고
SourceReader는 실제 원문 파일을 읽어들이는 기능을 한다.
SegmentWriter는 읽어들인 데이터를 가지고, 실제 색인작업을 수행한다.

이번 포스트에서는 Schema와 SourceReader에 대해서 알아보도록 하자.


Test용으로 있는 schema.xml을 보면


맨 처음에는 collection의 이름이 나오고 그 다음에 6개의 필드 정보가 나온다.
각 필드는 name과 type은 반드시 있어야한다. (가장 기본적인 data)

schema.xml을 한줄한줄 읽어가며 parsing한 data를 Schema class 필드에  저장한다.
Map을 사용하지 않고, AsciiCharTrie를 이용해서 sequence를 저장하는 이유는 조금이라도 더 빠른 연산을 위함인것 같다.


SourceReader는 원문을 읽는 기능이다.
Test엔 CollectFileParser로 원문의 파일 리스트(DirBufferedReader)를 얻어온다. 
CollectFileParser의 hasNext는 원문을 fieldSettingList의 size 만큼 readLine한다.(body field는 추가작업)
(원문의 필드는 개행으로 구분되어있음)

원문을 한줄한줄 읽으면서, type에 맞게 원문을 저장한다.

각 필드가 모여서 Document가 되고, next가 원문을 저장한 Document 를 리턴하는 기능을 수행한다.

다음에는 SegmentWriter를 알아보도록 하자.


================ 2011.08.28 추가 ===================

 

저작자 표시 비영리
신고
Posted by 오산돌구
국내 오픈소스 검색엔진 Fastcat이 1차 개발이 완료되었습니다.
포스팅해야지 해야지 하다가 드디어 처음 시작하기를 하게되었네요.

이번 포스팅에서는 검색하는 방법에 대해 알아보겠습니다.

처음 sample Collection을 검색하기까지의 순서를 보겠습니다.


1. http://getfastcat.org 에 들어간후, 무료 다운로드를 클릭합니다.



2. 받은 파일을 압축을 풀고 폴더안에 start.cmd를 실행합니다.  검색서버가 실행됩니다.



3. http://localhost:8080/admin에 접속을 하고, Execute Job항목을 들어갑니다.



4. 전체 색인입니다.
  args에는 전체색인을할 Collection명을 입력합니다.(Join이 뭔지 세미나할때 들었는데 까먹었네요;;;)


5. 자~ 검색을 실행해봅시다.


6. 짜쟌~!! : )   실행시간, 걸린시간, 그리고 검색된 결과를 출력해줍니다.



검색할 문서 추가 방법에 알아보도록 하겠습니다.
아래 그림과 같이, 해당 collection폴더안에는 data, data1, data2, testData가 있습니다.


data, data1, data2는 색인데이타가 있는 폴더입니다. 백업및 복원을 위해 이렇게 설계가 되어있구요,
이 부분에 대한 설정은 관리자 웹페이지에서 Restore탭에 있습니다.


만약 4로 설정다면 data, data1, data2, data3이 사이클을 돌면서 색인데이타를 가기고 있겠죠?


우리가 사용할 폴더는 testData폴더입니다.
폴더 경로 설정은 {fastcat HOME}/collection/{collection Name}에 datasource.conf파일에 있습니다.

추가색인이나 전체색인할 문서가있으면 파일명을 동일하게 해서 해당 경로에 복사하면 됩니다.




전 제 블로그에있는글을 sample schema에 맞게 가공합니다.
데이타를 보면 아시겠지만 정말 순수하게 긁은 데이타입니다. ;;;
아래 그림은 전체색인을 한후, 검색을해본 결과입니다.

잘 됩니다.  태그는 없애야겠네요; ㅎㅎ

마지막으로 검색결과를 Json으로 받는방법을 알아보겠습니다.
아래 쿼리를 이용하여 url로 넘길 parameter를 만듭니다.


http://localhost:8080/search/json?cn=sample&sn=1&ln=50&fl=id,title,body:100,category&se={title,body:OR(방송):100}

firefox의 경우 url encoding 때문에 안되는 분도 있겠습니다.(우선 제가 안됐습니다 ㅎㅎㅎ)
그럴때는 about:config로 설정창에서 아래와 같이 설정해주시면 됩니다.


저작자 표시 비영리
신고
Posted by 오산돌구