dalvik의 method 호출 opcode와 java bytecode의 비교

 java specification에는 메소드 호출시에 사용하는 바이트코드가 나와있는데

크게 다음 4가지를 사용한다고 볼수 있다. 

1. invokestatic

2. invokespecial

3. invokevirtual

4. invokeinterface

이름에서 대략 유추할수 있겠지만 invokestatic은 static 접근자로 지정된 메소드를 호출할때 

사용된다. 

일반적으로 jvm에서는 메소드 호출시에 인자의 첫번째로 객체 자신인 this 객체를 

저장한다. 정적 메소드 ( static method )의 경우 이러한 this 객체를 위한 공간이 필요없기

때문에 바로 인자만 들어가게 되므로 별도의 바이트 코드 invokestatic이 필요하다.

invokespecial은 주로 <init> 즉 객체의 생성자 메소드를 호출하기 위해 사용되고 

super class 메소드의 구현 메소드를 호출하기 위해서도 사용된다.

invokeinterface는 인터페이스의 메소드를 호출하기 위해 사용되고 나머지 대부분의

메소드들은 invokevirtual로 호출한다. 이름에서 알수있듯이 invokevirtual은 

dynamic method를 위한 바이트 코드임을 알수 있다. 

( java7에서는 invokedynamic이라는 bytecode가 새로 추가된듯 하다. )

source/android/dalvik/vm/meterp/out/ 폴더에 보면 하드웨어별로 

dalvik의 opcode 구현이 들어있다. dalvik에서는 

invoke-virtual, invoke-virtual/range, invoke-virtual-quick, invoke-virtual-quick/range

invoke-super, invoke-super/range, invoke-super-quick, invoke-super-quick/range

invoke-direct, invoke-direct/range

invoke-static, invoke-static/range

등등 꽤 많다. 크게 보아 종류는 똑같이 4종류인데 invokespecial이 invoke-direct로 이름이

더 직관적으로 바뀐듯하고 바로 위 부모 클래스의 메소드를 호출하는 invoke-super가 생기고

invokeinterface에 대응되는 바이트코드는 제거되었다. 

(직접 확인해 봐야 겠지만 아마도 invoke-virtual이 이 역할까지 함께 할듯 하다.)

range 계열은 parameter에 range를 쓸수 있는데 예를 들어,

invoke-virtual {v1,v2,v3} 처럼 호출하는 것을 range 계열은 invoke-virtual/range {v1 … v3}

처럼 호출한다.

quick 계열은 parameter외에도 부모 클래스의 인스턴스 포인터를 위한 별도의 테이블을 사용한다. 

즉 invoke-virtual-quick {parameter}, vtable 과 같은 형식으로 사용된다.

cvm이나 kvm의 구현부에서는 invokevirtual 바이트코드의 실행시 부모 클래스의 주소로 

한단계식 따라가며  메소드를 호출하게 되는데 테이블에 미리 부모 클래스들의 주소를 

로드시켜 놓고 빠르게 호출하기 위한 용도로 quick 계열의 메소드를 사용하는 듯하다.

Lucene에서 KStemmer 사용하기

정확한 명칭은 Krovertz Stemmer라고 부른다. Lucene등의 툴킷에서는 

KStemmer라는 이름의 약자로 되어 있다. 1993년 꽤 오래전에 논문이 나오고 

lucene, lemur, indri 등 대부분에 포함되어 있지만 생각보다는 많이 쓰이지는 

않는듯하다.

아무래도 사전기반의 알고리즘이다 보니 리소스가 꽤 많이 소비된다는 측면이 

클듯하다. 

가장 최신 버젼인 lucene-3.3.0 버젼에서는 추가된듯하다. 

( 이전 버젼부터 존재했었는지는 확실치 않다. )

자세한 사항이 궁금한 사람은 다음의 논문을 읽어 보도록 하자. 

"Viewing morphology as an inference process"

다음의 표는 Porter Stemmer가 에러를 일으키는 경우를 나타낸다.

Krovetz Stemmer는 Porter Stemmer만큼은 공격적으로 stemming을 하지는 않기때문에 

에러가 적다. 

KStemmer의 알고리즘은 기존의 Porter Stemmer의 알고리즘과 사전기반의 알고리즘이 

결합된 형태이다. 

KStemmer는 Inflectional, Derivational 두가지 방법의 알고리즘을 적용한다.

전자는 suffix를 제거하는 쪽 후자는 추가해서 명사를 만드는 쪽이다.

Inflectional에서 단어가 사전에 있는지를 찾아본후 사전에서 단어를 발견하면

스템처리를 하지 않는다. 

Derivational 방법에서는 -er, -or, -ion, -ly, -ity, -al, ive, -ze, -ment, -able 등을 추가하는데 

논문에 따르면 longman 사전의 빈도수를 기반으로 이를 패턴화 시켜놓았다.

더 자세한 사항은 논문을 참조하도록 하자. 

lucene에는 KStemFilter는 포함되어 있으나 Analyzer는 없기때문에 클래스를 추가해주어야 한다.

간단히 다음과 같이 클래스를 만들어 사용해 보자. 

package org.apache.lucene.demo;

import org.apache.lucene.analysis.en.*;

import org.apache.lucene.analysis.*;

import org.apache.lucene.analysis.standard.*;

import org.apache.lucene.util.Version;

import java.io.Reader;

public class KStemAnalyzer extends Analyzer {

Version MatchVersion;

public KStemAnalyzer(Version matchVersion){

this.MatchVersion = matchVersion;

}

public TokenStream tokenStream(String fieldName, Reader reader){

return new KStemFilter(new StandardTokenizer(MatchVersion,reader));

}

}

코드는 lucene-3.3.0을 기준으로 작성하였다. 

Analyzer는 Filter와 Tokenizer를 모두 필요로 한다. 

위에서는 간단하게 StandardTokenizer를 사용하였지만 lucene에는 

ClassicTokenizer, WhitespaceTokenizer, LowerCaseTokenizer, 

KeywordTokenizer등 여러가지가 있으니 입맛에 맞게 사용하면 된다.

Tokenizer가 있으니 입맛에 따라 골라 사용하자. 

LUCENE으로 TREC WT10G dataset 인덱싱하기

WT10G dataset은 웹문서를 모아놓은 dataset으로 아직도 많이 쓰인다.

WT10G에는 1,692,096개의 문서가 있고 용량은 대략 4G정도 된다. 

데이터는 WTX001 ~ WTX104개의 폴더에 각각 B01.gz ~ B50.gz로 

되어 있다. 

하나의 BXX.gz 파일에는 여러개의 웹 문서가 들어있어서 독립적인 포맷으로 

합쳐져 있는데 포맷은 대략 다음과 같다. 

WT10G에 대해서 더 궁금하신 분은 

http://ir.dcs.gla.ac.uk/test_collections/wt10g.html를 가보시라.

검색을 해보면 lucene으로 WT10G 데이터를 인덱싱해서 낸 논문은 많지만

실제로 어떻게 인덱싱을 했지는 코드를 공개한 것은 거의 없다. 

http://code.google.com/p/lucene-web-search-and-trec-wt10g/ 주소로 

가보면 거의 유일하게 코드를 공개한 프로젝트이다. 중국의 어느대학

대학원생들이 텀프로젝트로 수행한 것을 공개한듯하다. 

어찌됐든 lucene으로 WT10G를 인덱싱하는 간단한 코드 IndexTrec.java와

TrecDocument.java를 첨부한다. 

두개의 파일을 org.apache.lucene.demo 패키지 폴더에 추가해 놓고 실행하면

된다. 

IndexTrec.java는 org.apache.lucene.demo 패키지의 IndexFiles.java를 기반으로

만들었으며 코드는 어렵지 않으니 직접 살펴보고 수정해도 좋을것이다.

크게 수정된 부분은 readDocs() 메소드이며 이 메소드에서 WT10G의 gz압축

파일의 스트림을 읽어들여 파싱하는 역할을 한다. 

TrecDocument.java에서는 인덱싱하는 필드를 조금 수정했다. 아래의 그림을 참고하자.

문서가 파일단위가 아닌 <DOCNO> </DOCNO>인 태그의 값으로 설정되어야 

해서 이부분을 추가했으며 기본적으로 WT10G는 웹문서의 집합이므로 

HTMLParser를 써야한다.  

소스 파일을 첨부한다.

IndexTrec.java

TrecDocument.java

OMAP2 processor에서 kernel의 secondary bootup

리눅스 커널을 스터디를 통해서 분석한지가 벌써 4년전인것 같다.

그떄 당시는 2.6.15버젼인가가 최신이고 2.6.13이 안정판이라 arm rearview 기반으로

2.6.13 버젼을 분석했던 기억이 난다. 

분석 초기에 개인적으로는 smp 머신에서 초기화는 1개의 cpu에서 해주고 

나머지 cpu를 어떻게 startup 해주는지가 상당히 궁금했다. 

다음은  당시에 내가 썼던 글이다. 

===============================

kernel_init  커널 쓰레드에서 다른 CPU를 다 꺠워준다. 

호출 순서는 다음과 같다.

start_kernel() -> rest_init() -> kernel_init -> smp_prepare_cpus() -> poke_milo() ( SYS_FLAGSCLR 레지스터의 

하위 2비트를 클리어) -> (pen_release = -1, realview_secondary_startup() )

후에 rearview_secondary_startup 루틴이 pen 값이 release 될때까지 루프

kernel_init -> smp_init() -> cpu_up() -> _cpu_up() -> __cpu_up() -> boot_secondary() -> pen relase

후에 realview_secondary_startup() 루틴이 secondary_startup()으로 점프하면

secondary_startup() 함수에서 나머지 cpu를 up 해준다. 

=================================

omap2에서도 크게 달라지지 않았지만 달라진 부분이 있다면 boot_secondary() 에서 

omap_modify_auxcoreboot0(0x200, 0xfffffdff);로 두번째 core의 startup을 준비하는 부분과

를 부팅한다는 점과  정도이다. 

Dalvik VM의 개괄적 Source 분석

Dalvik VM은 Android에서 돌아가는 VM이다. 이전에도 포스트 한바와 같이 

Phoneme project, harmony의 코드와도 외형과 핵심 구조체 등이 상당히 유사하다.

이전 포스트 이후 harmony를 대략적으로 분석해 보았으며 

결론은 대략 비슷한데 phoneme와 harmony는 상당히 일치하고 dalvik은 harmony를

바탕으로 만들어진 것이 맞다고 봐야 할듯하다. 

직접적인 코드 외에도 초기화시 로드하는 핵심클래스가 동일한 것들도 몇가지 있다.

예를 들면 다음과 같은 것들이 있다. ( dalvik/vm/Init.c의 dvmJniStartup()을 참고하자. )

org/apache/harmony/luni/platform/PlatformAddress.java

org/apache/harmony/luni/platform/PlatformAddressFactory.java

org/apache/harmony/nio/internal/DirectBuffer.java

간단히 dalvik vm이 실행되는 process를 정리해 보자.

main() -> option을 위한 메모리 할당 -> option 파싱 -> JNI_CreateJavaVM() -> findClass()

-> GetStaticMethodID() -> CallStaticVoidMethod() -> DetachCurrentThread() -> DestroyJavaVM() 

dalvik/vm/main.c의 main() 함수가 entry point이다. 대략 위와 같은 과정을 거치는데 거의 모든 

초기화의 과정이 JNI_CreateJavaVM()에서 이루어진다. 

이후에는 실행시킬 클래스를 findClass()로 실행시킬 main 메소드를 GetStaticMethodID()로 찾는다.

이후 CallStaticVoidMethod()로 class의 main 메소드를 실행시키면 이후의 과정은 main 메소드가

종료할때까지는 intepreter와 dex 파일과의 상호작용이라 봐야 하겠다. 

종료는 DetachCurrentThread()와 DestroyJavaVM()의 두가지 과정으로 볼수 있는데 

Exception에 의한 종료와 정상 종료 크게 두가지 경우가 있을수 있다.

jvm의 경우 일반적으로 따로 Thread를 사용하지 않아도 최소 1개의 쓰레드를 가지고 있는데 

이를 main thread라고 부른다. 일반적으로 static void main(String[] args)으로 선언한 메소드의

코드를 실행하는 역할을 한다고 보면 된다. 

dalvik vm의 전체개요를 이해하기 위해서는 JavaVM, JNIEnv의 두가지 구조체를 이해하는 것이

상당히 중요한데 코드에서는 다음과 같이 정의되어 있다. 

#if defined(__cplusplus)

typedef _JNIEnv JNIEnv;

typedef _JavaVM JavaVM;

#else

typedef const struct JNINativeInterface* JNIEnv;

typedef const struct JNIInvokeInterface* JavaVM;

#endif

C로 정의된 JNINativeInterface나 JNIInvokeInterface의 경우 디바이스 드라이버를 개발해

보신분들은 상당히 익숙한 구조일듯한 변수와 함수 포인터의 집합으로 구조체를 만들어 놓았다.

정리해 보면

JNIEnv는 대략적으로 dalvik vm의 환경 설정과 관련된 함수들이 쭈욱 모아져 있는데 

코드를 분석하기 위해서는 우선 CallMethod 계열, GetMethod 계열, FindClass 부분을 우선적으로

보는 것이 좋을 것이다.

JavaVM의 경우는 

DestroyJavaVM, AttachCurrentThread, DetachCurrentThread, GetEnv, AttachCurrentThreadAsDeamon

등의 단촐하게 5가지만 있다. 

JNIEnv와 JavaVM 구조체의 함수 포인터들은 각각

JavaVM: main -> JNI_CreateJavaVM()에서 gInvokeInterface의 값으로

JNIEnv: main()->JNI_CreateJavaVM()에서 gNativeInterface의 값으로 

셋팅된다. 

이후의 과정은 서술한 바와 같이 class를 찾고 class의 static main 메소드를 찾고 이를 호출하는

과정이다. 실제 코드는 다음과 같이 되어 있다.

(*env)->CallStaticVoidMethod(env, startClass, startMeth, strArray);

gInvokeInterface에서 찾아보아도 호출하는 함수의 실제 이름도 CallStaticVoidMethod로 동일하다.

CallStaticVoidMethod는 내부에서 CallStaticVoidMethodV를 호출하는데 이함수는 crags, scope

등으로 찾으려하면 잘 나오지 않는데 이는 코드의 선언이 다음처럼 되어 있기 떄문이다. 

 "##"은 변수 또는 함수의 이름을 접합시켜 주는 역할을 한다. 

위의 코드에서는 CallStatic##_jname##MethodA 처럼 사용됐는데 _jname이 컴파일 타임에 결정되어

반드시 결정되어 있어야만 하며 

예를 들어, CALL_STATIC(jbyte,Byte,result.b, false); 의 코드가 있다면

CallStaticByteMethodA와 같은 함수선언이 된것과 같은 효과가 있다. 

그럼 CallStaticVoidMethodV를 잠깐 살펴보자. 

JNI_ENTER()로 쓰레드의 상태를 변경해준후 바로 dvmCallMethodV()를 호출해준다. 

프레임에 공간을 확보한후에 argument를 처리하고 dvmInterpret()를 호출하여 

본격적으로 dex의 opcode의 처리를 시작한다. 

여기서 부터는 다시 복잡해 지므로 자바의 메소드 호출 방식 및 메소프 스택을 

처리하는 법에 관해서는 다음글에서 이어서 포스트한다. 

LIRe의 소개( LUCENE 기반의 image retrieval library)

Lucene Image Retrieval의 약자이다. 


이름처럼 Image에서 몇가지 descriptor를 추출한 다음

Lucene에 각 descriptor를 하나의 필드로 해서 indexing 및 retrieval하는 

자바기반의 라이브러리로 보면 된다. 


즉 CBIR (Content Based Image Retrieval)용 오픈소스이다. 

CBIR 오픈소스는 찾아봐도 많지가 않은데 뭐 이유야 여러가지가 


있겠지만 아직까지 CBIR이라는 분야가 아직 많이 알려지지 않은


점이 가장 큰듯하다.

LIRe의 소스는 http://www.semanticmetadata.net/lire/에서 받을수 있다.

현재 최신버젼은  0.8이다. Demo와 Src 버젼으로 나눌수 있는데 

Demo 버젼은 GUI쪽의 부분을 주로 포함하고 있고 Src 버젼은

기본 LIRE의 src를 포함하고 있다. 헤깔리기 쉬운 부분이 GUI의 소스 또한

Demo 버젼에 포함되어 있고 Src 버젼에는 GUI부분의 소스가 없다. 

Demo의 실행법은 간단한데 

> java -jar liredemo.jar 를 입력하면 다음과 같은 창이 뜬다. 

 GUI 작동법은 어렵지 않으니 직접해보면 된다. indexing 속도가 생각보다 느려서 

 마음에 썩 들지는 않지만 CBIR 오픈소스가 있다는 자체에 감사해야 하는 상황인지도


 모르겠다. 

 LIRe가 이미지를 인덱싱하기 위해 사용하는 Descriptor는 다음과 같고 인덱싱하는


 필드명 또한 Descriptor명을 그대로 사용한다.

( net.semantic.metadata.lire.DocumentBuilder를 참고하자)

1. Scalable Color

2. Color Layout

3. Edge Histogram

4. Color Correlogram

5. Color Histogram

6. CEDD ( Color and Edge Directivity Descriptor )

7. FCTH ( Fuzzy Color and Texture Histogram )

8. TAMURA

9. Gabor

10. SIFT

11. SIFT Histogram

 11가지의 Descriptor를 사용한다. 

 각각을 검색해보면 각 Descriptor당 한개씩 논문이 나올정도로 CBIR에서 적통적으로

 사용하는 Descriptor들이다. 

 SIFT 알고리즘 하나만 해도 직접 구현하기는 상당히 까다로운데 

 암튼 저자가 많은 노력을 기울임에는 틀림이 없다. 

 각 Descriptor의 구현은 net.semantic.metadata.lire.imageanalysis 패키지에 들어있다. 

 패키지를 보면 다음과 같을 것이다. 

 CBIR쪽에 관심이 많다면 각각의 소스를 분석해보자. 꽤 심플하게 코드를 구현하여서

 분석하기는 어렵지 않을것이다.

lucene의 MoreLikeThis를 사용한 간단한 추천 시스템 만들기

 Lucene의 contrib중 queries 폴더에 보면 MoreLikeThis와

 FuzzyLikeThisQuery등이 포함되어 있다.

 사실 추천 시스템이라 말하기 좀 민망하긴 하지만 어찌됐던

 MoreLikeThis를 이용하여 문서 추천시스템을 만드는 것도 가능하다.

 MoreLikeThis는 주어진 다큐먼트의 Term Frequency Vector를 만들고

 이를 통해서 새로운 쿼리를 만드는 기능을 한다.

 즉 인덱싱된 문서중 주어진 문서와 가장 유사한 문서를 찾을수 있도록

 만들어 준다.

 TF를 이용해 문서의 key term을 추출하는 방식은 매우 고전적인 방식이지만

 아직도 많이 쓰인다. 궁금한 분은 다음의 논문을 읽어보도록 하자.

  "Newman, M.E.J. and M. Girvan, 2004. Finding and evaluating community structure in networks. Phys. Rev. E., 69: 026113"

 Lucene In Action 1판, 2판에 모두 MoreLikeThis에 관한 내용이 포함되어

 있으니 책에 있는 코드의 핵심 부분만 간단히 살펴보자.

  IndexReader reader = IndexReader.open(directory);
  MoreLikeThis mlt = new MoreLikeThis(reader);

  ...

  for ( int docID = 0 ; docID < numDocs; docID++){
    ...
    Query query = mlt.like(docID);
   TopDocs similarDocs = searcher.search(query,10);
    ...
  }

  1. 우선 IndexReader를 인자로 주어 MoreLikeThis 객체를 생성한다.

  2. 인덱스된 전체 문서에 대해서 각 문서의 term frequency vector를
      생성하고 이를 통해 query를 만든다.

  3. 주어진 쿼리로 인덱싱된 문서에서 다시 검색을 한다.


 즉 위의 코드는 인덱스된 모든 문서에 대해서 가장 유사한 문서들을

 찾는 역할을 한다.

 MoreLikeThis 객체의 like 메소드는 overloading되어 있어서

 사실 4개의 인자를 받을수 있는데 다음과 같다.

 1. 인덱싱된 문서의 번호


 2. File 객체


 3. reader 객체


 4. url 객체

 2,3,4 번의 경우 직접 term frequency를 구하여 term frequency vector를 만들고

 1번의 경우에는 IndexReader의 getTermFreqVector() 메소드를 이용하여

 term frequency vector만든다.


 lucene 내부에서 사용하는 term frequency vector는 TermFreqVector

 인터페이스를 implements 하거나 implements한 클래스를

 상속하여 만들어진다.

 IndexReader의 종류에 따라 사용하는 TermVector 클래스가 다르므로

이는 나중에 다른 글에서 설명하겠다.


 그럼 org.apache.lucene.demo에 들어있는 SearchFiles를 약간 수정하여

 인덱스된 문서들중 주어진 URL의 문서와 가장 유사한 문서를 찾는 예제를

 간단히 만들어 보겠다.

 1. 우선 다음의 import 구문을 추가한다.

 import org.apache.lucene.search.similar.MoreLikeThis;
 import java.net.*;

 2.  Search시에 사용하는 Query 객체와 관련한 구문을 다음과 같이 수정해보자.

 MoreLikeThis mlt = new MoreLikeThis(reader);
 mlt.setMinTermFreq(2);
 mlt.setMinDocFreq(2);

 Query query = mlt.like(new URL("http://wittgena.blogspot.com/2011/07/lucene-incremental-indexing.html"));


 사용법이 매우 간단하다.

 나머지는 모두 동일하고 while(true){} 구문만 제거하면 될것이다.

 MoreLikeThis에 필드는 따로 지정해주지 않았는데 지정해주지

 않으면 "contents" 필드를 기본값으로 사용한다.

 나의 경우 위의 코드로 linux kernel의 documentation 폴더의 일부 문서를

 인덱싱한후 돌려보니 대략 15개의 문서가 검색이 된다.

 각자 코드를 수정하여 실행해보자. 코드를 첨부한다.

 다운로드


 ps. mahout을 이용하여 lucene에서 term vector를 추출하는 방법도 있다.
      이는 나중에 다른 글에서 설명하도록 하겠다.
      lucene의 TermVector 객체를 알아두면 textmining에
      lucene을 사용할수도 있고 여러모로 유용하다.

lucene에서 n-gram, shingle 사용하기

 lucene에는 n-gram tokenizer와 shingle analyzer가

( 정확히는 shingle analyzer wrapper)

 포함되어 있긴 하지만 3.0.1 버젼을 기준으로 할때 contrib쪽에 포함되어 있다.

 n-gram과 shingle을 가끔 혼동하시는 분도 계신데 둘은 약간 다르다고 볼수 있다.

 n-gram이 한 문자를 기반으로 하는 반면에 shingle은 한 단어를 기반으로 한다.


 "you can select"을 예를 들어보면,

 n-gram 방식으로 bi-gram으로 한다면 yo, ou, uc, ca, an 이 될 것이고

 shingle 방식으로 2-shingles로 한다면 you can, can select가 될 것이다.

 검색을 해보니 lucene에서 n-gram을 사용하는 법에

 관한 블로그는 이미 있는 듯하여

 나는 lucene에서 shingle을 사용하는 방식을 간단히 설명하겠다.

 lucene의 contrib쪽에 보면 analyzers 소스 폴더가 있다.

이 analyzers에 n-gram과 shingle 둘다 포함되어 있다.


 우선 "ant build-contrib" 명령어를 통해 contrib쪽을 빌드하면

 build/contrib/analyzers/common 폴더 밑에 lucene-analyzers-x.x.x-dev.jar 파일이

 생성된다. ( x는 버젼명이다. 즉, 나의 경우는 3.0.1이 된다.)

 이 jar파일을 classpath에 포함한후 src/java/org/apache/lucene/demo의 IndexFiles.java

 에서 다음의 두 부분을 수정한후 빌드해 보자.

 1. import 부분에 다음을 추가한다.
  import org.apache.lucene.analysis.shingle.*;

  2. IndexWriter 객체의 생성 부분을 다음과 같이 수정한다.

  (대략 60 ~ 70 라인 사이에 있다. )
IndexWriter writer = new IndexWriter(FSDirectory.open(INDEX_DIR),
                                                //new StandardAnalyzer(Version.LUCENE_CURRENT),
                                                new ShingleAnalyzerWrapper(new        StandardAnalyzer(Version.LUCENE_CURRENT),3),
                                                true,
                                                IndexWriter.MaxFieldLength.LIMITED);

  IndexWriter의 생성자에서 무엇이 수정되었는지는 쉽게 알수 있을것이다.

 의미는 기본 analyzer로 StandardAnalyzer를 사용하고 shingle의 최대 크기를 3으로

 한다이다.

 이후 나머지 searcher를 이용한 검색과정등은 모두 동일하다.

Lucene의 Ranking Algorithm 변경

 lucene은 사실 그렇게 쉽지 많은 라이브러리이다.

 lucene의 ranking algorithm을 변경하는 방법은 여러가지인데  이중 가장

 기본적인것이 TF-IDF cosine similarity 공식 (또는 scoring fomula)을 변경하는

 것이다.  그 외에도 Query에서 가중치를 주거나 Searcher에서 HITS Collector의

 순서를 변경하는 방법, Document의 Field별 가중치를 다르게 주는법(boosting) 등등등

 여러가지가 있다.

 일단 scoring fomula를 수정하는 방법을 살펴보자.

( Lucene in action의 3장을 보면 이 내용이 잘 설명되어 있다.)

 우선 src/java/org/apache/lucene/search 폴더에 보면 DefaultSimilarity 클래스가 있다.

 메소드를 보면 computeNorm(), lengthNorm(), queryNorm, tf(), sloppyFreq(), idf()

 등등이 있다. 이 클래스는 IndexWriter 클래스에서 사용하는데 DefautSimilarity

 클래스를 상속해서 새로운 Similarity 클래스를 만들면 간단히 공식을

 변경할수 있다.

 물론 변경후 반드시 IndexWriter에 등록을 해주어야 한다.


 다음과 같이 DefaultSimilarity 클래스를 상속하여 새로운 클래스를 만들어보자.

import org.apache.lucene.search.*;

public class MySimilarity extends DefaultSimilarity {
public float tf(float freq){
return (float)(Math.sqrt(freq));
}

public float idf(int docFreq,int numDocs){
return (float)(Math.log(numDocs/(double)(docFreq+1))+1.0);
}

}

TF와 IDF를 계산하는 공식만 수정하는 간단한 소스이다.

 이제 IndexWriter 객체에 등록한다.



 IndexWriter writer = new IndexWriter(FSDirectory.open(index),
                                  new StandardAnalyzer(Version.LUCENE_CURRENT),              
                                  create,
                                  new IndexWriter.MaxFieldLength(1000000));
 writer.setSimilarity(new WikiSimilarity());

 당연한 얘기겠지만

 인덱싱을 하기전에 IndexWriter에 등록을 해주어야 한다.

 이제 수정된 공식으로 다큐먼트를 인덱싱하게 된다.

perl로 작성한 간단한 cosine similarity 소스

 요즘에는 python이 인기가 더 많은듯 한데 개인적으로 python을 별로

 좋아하지 않는다. 사실 매우 편협한 이유인데 들여쓰기와 함수의 시작

 과 끝이 { }로 구분되지 않는다는 점때문이다.

 간단히 Cosine similarity를 구하기 위해서 python이나 perl과 같은 스크립트

 언어로 스크립트를 짜야 할 때가 많은데 다음의 cosine similarity를 구해주는

 간단한 perl 스크립트를 이용해 보시라.


 사용법은 간단하다.

 document.txt 라는 파일을 만들고 파일에 여러 다큐먼트를 다음과 같은

 포맷으로 합친후 스크립트를 그냥 실행하면 된다.

 <TITLE> doc1 </TITLE>

 This is document1.

 <TITLE> doc2 </TITLE>

 This is document2.

 소스는 별로 어렵지 않으니 다큐먼트를 합치기가 귀찮다거나 아니면

 알고리즘을 수정하고 싶다면 간단히 수정해보아도 공부하는데 도움이

 될듯하다.

 기본적으로 소스에서는 IDF를 log2 ( N / DF )로 계산하고 있다.

#!/usr/bin/perl

use strict;

open(IN, "document.txt") or die;
my $nstory = -1;
my @words;
my %granddict;
my @weight;
my @unit;
my $i;
my $j;
my @cosine;
my $word;
my $sum;
my $df;
my @tf;
my $n;
my %df;
my $len2;
my $len;

#Step 1: Compute the term frequencies

while(<IN>){
    chomp;
    my $title;
    if ( /<TITLE>(.*)<\/TITLE>/ ){
        $title = $1;
        ++$nstory;
        print "Title of story $nstory = $title \n";
    } else {
        $_ = lc;
        s/--/ /g;
        s/ - / /g;
        s/[,.";!()?:_\[\]]//g;
        s/\s+/ /g;
        s/^\s+//g;
        @words = split(/ /);
        foreach $word (@words){
            if ($word =~ /^;?(.*?)'?$/){
                $word = $1;
            }
            ++$tf[$nstory]{$word};
            ++$granddict{$word};
        }
    }
}

foreach $word (sort keys %granddict ) {
    $sum = 0;
    for $i ( 0 .. $#tf ){
        if ($tf[$i]{$word} > 0){
            ++$sum;
        }
        $df{$word} = $sum;
    }
}

$n = $#tf + 1;
foreach $word (sort keys %granddict){
    for $i (0 .. $#tf){
        $weight[$i]{$word} = $tf[$i]{$word}*log($n/$df{$word})/log(2);
    }
}

for $i ( 0 .. $#tf ) {
    $len2 = 0;
    foreach $word ( sort keys %granddict){
        $len2 += $weight[$i]{$word}**2;
    }
    $len = sqrt($len2);
    foreach $word ( sort keys %granddict){
        $unit[$i]{$word} = $weight[$i]{$word}/$len;
    }
}

for $i ( 0 .. $#tf ) {
    for $j ( 0 .. $#tf ) {
        $sum = 0;
        foreach $word ( sort keys %granddict ) {
            $sum += $unit[$i]{$word} * $unit[$j]{$word};
        }
        $cosine[$i][$j] = $sum;
    }
}

print "\n";
for $i ( 0 .. $#tf) {
    for $j (0 .. $#tf) {
        printf "%.4f ", $cosine[$i][$j];
    }
    print "\n";
}

 참고로 소스의 출처는 Practical Text Mining With Perl 이란 책이다. 

 (저작권에 걸릴려나.. ) 

 책이 text mining에 관한 기초 실무로는 딱 좋으니 관심있는 분들은

 한번 보시라.

java class file structure analysis

ClassFile {

  u4 magic;

  u2 minor_version;

  u2 major_version;

  u2 constant_pool_count;

  cp_info constant_pool[constant_pool_count-1];

  u2 access_flags;

  u2 this_class;

  u2 super_class;                                       

  u2 interfaces_count;

  u2 interfaces[interfaces_count];

  u2 fields_count; field_info fields[fields_count];

  u2 methods_count;

  method_info methods[methods_count];

  u2 attributes_count;

  attribute_info attributes[attributes_count];

}

jvm specification second edition에서는 클래스 파일의 구조를 위와 같이 표현해 놓았으며 이를 분석해 보면 다음과 같다.

u2 -> unsigned 2byte 

u4 -> unsigned 4byte

magic => 매직넘버 (일반적으로 0xcafebabe 인 고정값 ) 

minor_version => jdk의 minor 버전

major_version => jdk의 major 버전

constant_pool_count => 전체 constant pool의 개수를 나타내며 실제로 constant pool의 개수보다 1개가 많은 값을 가진다.

cp_info constant_pool[] => 실제 constant pool array를 나타내며 다음과 같은 종류가 있다.

cp_info { 

  u1 tag;

  u1 info[];

}

cp_info 의 tag 값이 constant type을 나타내며 각각의 type에 따라 info 에 나오 는 구조가 달라지게 된다.

access flag => class 의 접근자를 나타낸다.

this_class, super_class => class의 이름. 다만 여러 상수값들은 전 부 constant_pool 에 저장되어 있으므로 실제로는 constant_pool의 특정 index값 만을 가지고 있다.

interface_count => 클래스 파일이 implements를 사용한 경우 interface의 개수를 나타내게 된다.

interfaces[] => 실제 인터페이스 정보를 가지는 구조체

Constant Type                                  Value

CONSTANT_Class                             7

CONSTANT_Fieldref                          9

CONSTANT_Method ref                   10

CONSTANT_Inter faceMethod ref   11

CONSTANT_Str ing                            8

CONSTANT_Integer                           3

CONSTANT_Float                              4

CONSTANT_Long                              5

CONSTANT_Double                          6

CONSTANT_NameAndType          12

CONSTANT_Utf8                               1

fields_count => 이후에 나올 클래스 멤버 변수등의 field의 개수

field_info fields[] => 실제 필드 정보를 가지는 구조체가 되며 field_info의 구조 는 다음과 같다.

field_info { 

  u2 access_flags; 

  u2 name_index; 

  u2 descriptor_index;

  u2 attributes_count; 

  attribute_info attributes[attributes_count];

} 

field_info 는 변수에 대한 접근자, 이름, descriptor 등을 가지며 실제 필드의 내

용은 attribute_info 형태로 저장되어 있으며 attribute_info 에는 여러 종류가 있다.

attribute_info { 

  u2 attribute_name_index;

  u4 attribute_length; 

  u1 info[attribute_length];

}

attribute_info.attribute_name_index 는 attribute의 종류를 나타내며 attribute의 종류는 다음과 같다.

SourceFile , ConstantValue, Code , Exceptions , InnerClasses, Synthetic , LineNumberTable, LocalVariableTable, Deprecated attributes

이 값들은 constant pool에 utf-8 형태로 저장되어 있으며 따라서 attribute_name_index는 constant pool의 특정 index를 가리키게 된다.

실제 kvm의 class loader의 경우 attribute의 type이 결정되면 결정된 type에 맞게 attribute_length 만큼 info[] 정보를 읽어들이게 된다.

method_count => method 의 개수.

method_info methods[] => 실제 method의 정보를 나타내며 method_info 의 구 조는 다음과 같다.

method_info { 

  u2 access_flags; 

  u2 name_index; 

  u2 descriptor_index; 

  u2 attributes_count; 

  attribute_info attributes[attributes_count];

}

access_flag => method 에 대한 접근자

name_index => method의 이름을 utf-8로 가지고 있는 constant pool에 대한 in dex

descriptor_index => method 구별을 위한 descriptor값을 utf-8로 가지고 있는 

constant pool에 대한 index (method의 return 값은 descriptor에 포함되지 않음

)

attributes_count 와 attribute_info의 경우에는 field_info 와 동일

attributes_count와 attributes[] 가 한번더 나오며 이는 클래스 파일에 대한 추가적인 정보를 가진다. 이곳에는 주로 Code attribute, InnerClass attribute, Deprecated attribute, Synthetic attribute, SourceFile attribute등이 나온다.

직접 간단한 클래스를 작성하여 위의 사항들을 확인해보자.

public class DefaultClass { 

  private int filed;

  public DefaultClass() {} 

  public void function() {}

}

위와 같은 DefaultClass.java를 컴파일한후 나오는 DefaultClass.class 파일을 바이너리로 열어서 확인해보면 다음과 같다.

0000000: cafe babe 0000 0032 0010 0a00 0300 0d07 .......2........ 

0000010: 000e 0700 0f01 0005 6669 6c65 6401 0001 ........filed... 

0000020: 4901 0006 3c69 6e69 743e 0100 0328 2956 I...<init>...()V 

0000030: 0100 0443 6f64 6501 000f 4c69 6e65 4e75 ...Code...LineNu 

0000040: 6d62 6572 5461 626c 6501 0008 6675 6e63 mberTable...func

0000050: 7469 6f6e 0100 0a53 6f75 7263 6546 696c tion...SourceFil 

0000060: 6501 0011 4465 6661 756c 7443 6c61 7373 e...DefaultClass 

0000070: 2e6a 6176 610c 0006 0007 0100 0c44 6566 .java........Def 

0000080: 6175 6c74 436c 6173 7301 0010 6a61 7661 aultClass...java 

0000090: 2f6c 616e 672f 4f62 6a65 6374 0021 0002 /lang/Object.!.. 

00000a0: 0003 0000 0001 0002 0004 0005 0000 0002 ................ 

00000b0: 0001 0006 0007 0001 0008 0000 0021 0001 .............!.. 

00000c0: 0001 0000 0005 2ab7 0001 b100 0000 0100 ......*......... 

00000d0: 0900 0000 0a00 0200 0000 0400 0400 0500 ................ 

00000e0: 0100 0a00 0700 0100 0800 0000 1900 0000 ................ 

00000f0: 0100 0000 01b1 0000 0001 0009 0000 0006 ................ 

0000100: 0001 0000 0009 0001 000b 0000 0002 000c ................ 

0000110: 0a .

이제 컴파일 후의 실제 class file 구조를 위의 스펙에 맞는지 확인해보자.

각각의 값은 다음과 같다.

MAGIC : cafe babe 

minorVersion : 0000 

majorVersion : 0031 

constantPoolCount : 001c (28) 

[constantPool] 

0.Method tag : 0a (10)   class_index : 0008  name&type_index : 0011 (17)

1.Class tag : 07 name_index : 0012 

2.Method tag : 0a (10) class_index : 0002 name&type_index : 0011 (17)

3.Method tag : 0a (10) class_index : 0002 name&type_index : 0013 (19)

4.Method tag : 0a (10) class_index : 0002 name&type_index : 0014 (20)

5.Method tag : 0a (10) class_index : 0002 name&type_index : 0015 (21)

6.Class tag : 07 name_index : 0016 

7.Class (22) tag : 07 name_index : 0017 (23) 

8.UTF8 tag : 01 length : 0006 bytes[length] : 3c 69 6e 69 74 3e

9.UTF8 <init> tag : 01 length bytes[length] : 0003 : 28 29 56 ()V

10.UTF8 tag : 01 length : 0004 bytes[length] : 43 6f 64 65 Code tag : 01

11.UTF8 length bytes[length] : 000f (15) : 4c 69 6e 65 4e | 75 6d 62 65 72 | 54 61 62 6c 65

LineN umber Table

12.UTF8 tag : 01 length : 0004 bytes[length] : 6d 61 69 6e main

13.UTF8 tag : 01 length : 0016 (22) bytes[length] : 28 5b 4c 6a 61 | 76 61 2f 6c 61 | 6e 67 2f 53 74 | 72 69 6e 67 3b | 29 56 ([Ljava/lang/String; )V tag: 01

14.UTF8 length bytes[length] : 000a (10) : 53 6f 75 72 63 | 65 46 69 6c 65 SourceFile

15.UTF8 tag : 01 length : 000e ( 14 ) bytes[length] : 54 65 73 74 44 | 72 69 76 65 2e | 6a 61 76 61 TestDrive. java

16.NameAndType tag: 0c (12) name_index : 0009 descriptor_index: 000a (10)

17.UTF8 tag: 01 length: 0008 bytes[length] : 54 65 73 74 54 | 68 69 73 TestThis

18.NameAndType tag: 0c (12) name_index : 0018 (24) descriptor_index: 000a (10)

19.NameAndType tag: 0c (12) name_index : 0019 (25) descriptor_index: 000a (10)

20.NameAndType tag: 0c (12) name_index : 001a (26) descriptor_index: 001b (27)

21.UTF8 tag: 01 length: 0009 bytes[length] : 54 65 73 74 44 | 72 69 76 65 TestD rive

22.UTF8 tag: 01 length: 0010 (16) bytes[length] : 6a 61 76 61 2f | 6c 61 6e 67 2f | 4f 62 6a 65 63 | 74 java/ lang/ Objec t tag : 01

23.UTF8 length bytes[length]: 000a (10) :70 7269 6e74 |53 7461 7274 printStart

24.UTF8 tag: 01 

length bytes[length]: 000a (10) :70 7269 6e74 |53 7570 6572 print Super

25.UTF8 tag : 01

length : 0003 bytes[length] : 41 64 64 Add

26.UTF8 tag : 01

length : 0005 bytes[length] : 28 49 49 29 49 (II)I

access_flag this_class super_class interfaces_count fields_count methods_count

: 0021 ( ACC_PUBLIC | ACC_SUPER ) : 0007

: 0008 : 0000 : 0000

: 0002 [Method#1]

access_flag: 0001 (ACC_PUBLIC)

name_index descriptor_index attr_count: 0009 : 000a (10): 0001 

attr_name_index : 000b (11) => "Code"

[Code Attr]

attr_length max_stack max_locals code_length code[code_length] : 2a b7 00 01 b1 exception_table_length : 0000 attr_count : 0001

[LineNumTable] attr_name_index : 000c (12) => "LineNumberTable" attr_length : 0000 0006 line_number_table_length : 0001 start_pc : 0000 line_number : 0012 (18)

[Method#2] access_flag name_index descriptor_index attr_count

: 0009 (ACC_PUBLIC | ACC_STATIC ) : 000d (13)

: 000e (14) : 0001

[Code Attr] attr_name_index attr_length max_stack max_locals code_length code[code_length]

10 0a | b6 00 06 57 b1 exception_table_length

: 0000

: 0000 001d (28) : 0001

: 0001 : 0000 0005

: 000b (11) => "Code" : 0000 0041 (65)

: 0003 : 0002

: 0000 0019 (25) : bb 00 02 59 b7 | 00 03 4c 2b b6 | 00 04 2b b6 00 | 05 2b 08

attr_count : 0001 [LineNumberTable Attr] attr_name_index : 000c (12) => "LineNumberTable" attr_length : 0000 0016 line_number_table_length: 0005

[ line_number_table[0] ] start_pc : 0000 line_number : 0016

[ line_number_table[1] ] start_pc : 0008 line_number : 0018

[ line_number_table[2] ] start_pc : 000c line_number : 0019

[ line_number_table[3] attr_count attr_name_index attr_length sourcefile_index

end of file

start_pc : 0010 line_number : 001b

[ line_number_table[4] ] start_pc : 0018 line_number : 001d

: 0001 : 000f (15) => SourceFile

: 0000 0002 : 0010 (16) => TestDrive.java

: 0a