jjeong

URL: http://www.merriampark.com/ld.htm

자주쓰이는 3개의 언어로 구현한 Levenshtein Distance

작성자: Michael Gilleland, Merriam Park Software

이 짧은 에세이를 쓰게 된 것은 Levenshtein distance 알고리즘에 대해서

설명하고 또 그것이 각각의 세가지 프로그래밍 언어에서 어떻게 구현되는가를

보이기 위해서입니다.

Levenshtein Distance이란 무엇인가?

데모

알고리즘

세가지 언어로 구현된 소스코드

레퍼런스

다른 언어로 구현

Levenshtein Distance이란 무엇인가?

Levenshtein Distance(이하 LD)는 두 문자열의 비슷한 정도를 측정하기위해 고안되었습니다.

여기서 원문자열을 (s)로, 대상문자열을 (t) 라고 나타낸다고 하겠습니다. distance란 s를

t로 변형시키기 위해 삭제, 추가, 또는 수정이 필요한 횟수를 뜻합니다. 예를든다면,

* s가 "test"이고 t도 "test"라면, LD(s,t) = 0 이 됩니다. 왜냐하면 문자열들이 이미 동일하여 변환이 필요하지 않기 때문입니다.

* s가 "test"이고 t가 "tent"라면, LD(s,t) = 1 이 됩니다. 왜냐하면 s를 t로 만들기 위해서는 "s"를 "n"으로 한번 수정이 필요하기 때문입니다.

Levenshtein distance는 string 간의 차이가 클수록 위대함을 느낄 수 있습니다.

Levenshtein distance는 러시아 과학자인 Vladimir Levenshtein가 1965년에 고안하여 그렇게 이름지어졌습니다.

Levenshtein 이란 단어가 쓰거나 읽기 힘들기 때문에 종종 edit distance라고도 불립니다.

Levenshtein distance 알고리즘은 다음과 같은 분야에 쓰여집니다:

* 철자 검사

* 음성 인식

* DNA 분석

* 표절여부 검사

데모

아래의 간단한 자바 애플릿으로 두 문자열의 Levenshtein distance를 알아보세요.

원래 문자열

대상 문자열

알고리즘

알고리즘 작동 단계

단계 설명

1 

s의 문자열 길이를 n에 넣는다.

t의 문자열의 길이를 m에 넣는다.

만약 n = 0 이라면, m 을 리턴하고 종료한다.

만약 m = 0 이라면, n 을 리턴하고 종료한다.

0..m 행과, 0..n 열로 이루어진 행열을 만든다.

2

첫번째 행인 0..n을 초기화 한다.

첫번째 열인 0..m을 초기화 한다.

3

s의 각 문자(i는 1부터 n까지)를 검사한다.

4

t의 각 문자(j는 1부터 m까지)를 검사한다.

5

s[i]와 t[j]가 같다면, 변경하기 위한 비용은 0이 된다.

s[i]와 t[j]가 같지 않다면, 비용은 1이 된다.

6

행열의 셀 d[i,j]에 다음의 것들 중 가장 작은 값을 넣는다.

a. 바로 위의 셀이 더하기 1이 되는 경우: d[i-1, j] + 1

b. 바로 왼쪽 셀이 더하기 일이 되는 경우: d[i,j-1] + 1

c. 대각선으로 연속적인, 바로 왼,위쪽 셀의 비용: d[i-1,j-1] + cost

7

(3, 4, 5, 6) 단계를 반복하여 완료되면, d[n, m]셀에 있는 것이 distance가 된다.

예제

이 예제절에서는 원래 문자열이 "GUMBO"이고 대상 문자열이 "GAMBOL"이라 할 때

어떻게 Levenshtein distance가 계산되는지에 대해서 다룬다.

1 과 2 단계

i가 1일 때 3에서 6 단계

i가 2일 때 3에서 6 단계 

i가 3일 때 3에서 6 단계

i가 4일 때 3에서 6 단계

i가 5일 때 3에서 6 단계

7단계

행열의 가장 오른쪽 아래에 있는 값이 distance가 된다.(여기서는 2)

이 결과는 "GUMBO"가 "GAMBOL"이 되기 위해서 "U"를 "A"로 바꾸고

"L"을 추가해야한다는, 직관적으로 알 수 있는 결과와 일치합니다.

( 1번의 수정과 1번의 추가 = 2 번의 변경 )

세가지 언어로 구현된 소스코드

프로그래밍 언어들간에 차이에 대해서 토론하는 엔지니어들 사이에서는 종교 전쟁이 일어나기도합니다.

이러한 예로, 전형적인 주장은 JavaWorld article에서 일어난(July 1999) Allen Holub의 주장입니다.:

"예를들자면, 비주얼 베이식은 전혀 객체지향이라고 말할 수 없다. Microsoft Foundation Classes(MFC) 

또는 대부분의 다른 마이크로소프트의 테크놀러지는 어느것도 객체지향이라 주장할 수 없다."

Salon에 계제된(Jan. 8, 2001) Simson Garfinkels의 글에서 다른 진영의 반박이 이루어졌습니다.

이 글은 "Java: 느리고, 꼴사납고, 부적절한 언어"라는 제목으로 알려져 있는데, 명료하게

표현하자면 "나는 자바를 증오해"라고 나타낼 수 있습니다.

우리는 이러한 종교 전쟁들 속에서 자연스럽고 조심스런 입장을 취하로 했습니다. 배우기 위한 교재로써,

하나의 프로그래밍 언어에서만 해결할 수 있는 문제라면 대개 다른 언어에서도 마찬가지로 해결할 수

있을 것입니다. 우수한 프로그래머는 완전히 새로운 언어를 배우면서 한다고 하더라도 하나의 언어에서 

다른 언어로 비교적 쉽게, 큰 어려움에 당면하지 않고 옮길 수 있습니다. 프로그래밍 언어라는 것은

목적을 이루기 위한 것이지, 그 자체가 목적은 아닌 것입니다.

이러한 중도의 입장에서, 우리는 Levenshtein distance 알고리즘을 아래에 있는 프로그래밍 언어들로 

구현하여 소스코드를 보였습니다.

* Java

* C++

* Visual Basic

소스코드들 (블라블라)

참고문헌

Levenshtein distance에 관련된 다릍 토의를 다음 링크들에서 발견하실 수 있습니다.

* http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit.html (Lloyd Allison) 

* http://www.cut-the-knot.com/do_you_know/Strings.html (Alex Bogomolny) 

* http://www-igm.univ-mlv.fr/~lecroq/seqcomp/node2.html (Thierry Lecroq) 

다른 언어로 구현

아래 있는 분들은 그들 각자가 다양한 언어로 Levenshtein Distance 알고리즘을 구현한 것을

여기서 사용할 수 있게 친절히 승낙해 주셨습니다.

* Eli Bendersky 은 펄로 구현해주셨습니다.

* Barbara Boehmer 은 Oracle PL/SQL 로 구현해주셨습니다.

* Rick Bourner Objective-C 로 구현해주셨습니다.

* Joseph Gama 는 TSQL로 Planet Source Code 에 있는 TSQL 함수 패키지의 한 파트로 구현해주셨습니다.

* Anders Sewerin Johansen 는 C++로 제가 만든 것보다 C++의 정신에 가깝게, 더 최적화되고 세련되게 구현해주셨습니다.

* Lasse Johansen 는 C#으로 구현해 주셨습니다.

* Alvaro Jeria Madariaga는 Delphi로 구현해 주셨습니다.

* Lorenzo Seidenari 는 C로 구현해 주셨습니다.

* Steve Southwell는 Progress 4gl로 구현해 주셨습니다.

이 페이지 밖에 있는 다른 구현들:

* Art Taylor의 Emacs Lisp로의구현.

* Magnus Lie Hetland의 Python로의 구현.

* Richard Suchenwirth의 Tcl로의 구현(링크가 깨진 것을 알려주신 Stefan Seidler님 감사합니다).

/**

 * The type of replication to perform.

 */

public enum ReplicationType {

    /**

     * Sync replication, wait till all replicas have performed the operation.

     */

    SYNC((byte) 0),

    /**

     * Async replication. Will send the request to replicas, but will not wait for it

     */

    ASYNC((byte) 1),

    /**

     * Use the default replication type configured for this node.

     */

    DEFAULT((byte) 2);

/**

 * Write Consistency Level control how many replicas should be active for a write operation to occur (a write operation

 * can be index, or delete).

 *

 *

 */

public enum WriteConsistencyLevel {

    DEFAULT((byte) 0),

    ONE((byte) 1),

    QUORUM((byte) 2),

    ALL((byte) 3);

본 문서는 개인적인 테스트와 elasticsearch.org 그리고 community 등을 참고해서 작성된 것이며,

정보 교환이 목적입니다.

잘못된 부분에 대해서는 지적 부탁 드립니다.

(예시 코드는 성능 및 보안 검증이 되지 않았습니다.)

There are different way of generating JSON document:

- Manually (aka do it yourself) using native byte[] or as a String

- Using Map that will be automatically converted to its JSON equivalent

- Using a third party library to serialize your beans such as Jackson

- Using built-in helpers XContentFactory.jsonBuilder()

curl -XPUT 'http://localhost:9200/facebook' -d '{

    "settings" : { 

        "number_of_shards" : 5,

        "number_of_replicas" : 1  

    },  

    "mappings" : { 

        "post" : { 

            "properties" : { 

                "docid" : { "type" : "string", "store" : "yes", "index" : "not_analyzed" },

                "title" : { "type" : "string", "store" : "yes", "index" : "analyzed", "term_vector" : "yes", "analyzer" : "standard" }

            }   

        }   

    }   

}'

// 생성할 문서가 아래와 같다고 가정

// curl -XPUT 'http://localhost:9200/facebook/post/1' -d '{ "docid" : "henry", "title" : "This is the elasticsearch hadoop test." }'

// curl -XPUT 'http://localhost:9200/facebook/post/2' -d '{ "docid" : "henry", "title" : "elasticsearch test." }'

// curl -XPUT 'http://localhost:9200/facebook/post/3' -d '{ "docid" : "howook", "title" : "hadoop test." }'

// curl -XPUT 'http://localhost:9200/facebook/post/4' -d '{ "docid" : "howook", "title" : "test." }'

    IndexRequestBuilder requestBuilder;

    IndexResponse response;

    requestBuilder = client.prepareIndex("facebook", "post");

// setSource parameter 로 json string 형태로 등록

    requestBuilder.setId("1");

    requestBuilder.setSource("{ \"docid\" : \"henry\", \"title\" : \"This is the elasticsearch hadoop test.\" }");

    response = requestBuilder.execute().actionGet();

// XContentBuilder 로 setSource 전달

    XContentBuilder jsonBuilderDocument = jsonBuilder().startObject();

        jsonBuilderDocument.field("docid", "henry");

        jsonBuilderDocument.field("title", "elasticsearch test.");

    jsonBuilderDocument.endObject();

IndicesAdminClient indices = client.admin().indices();

CreateIndexRequest indexRequest = new CreateIndexRequest("INDEX_NAME");

    indexRequest

        .settings(jsonBuilderIndexSetting)

        .mapping("INDEX_TYPE_NAME", jsonBuilderIndiceSetting);

indices.create(indexRequest).actionGet();

본 문서는 개인적인 테스트와 elasticsearch.org 그리고 community 등을 참고해서 작성된 것이며,

정보 교환이 목적입니다.

잘못된 부분에 대해서는 지적 부탁 드립니다.

(예시 코드는 성능 및 보안 검증이 되지 않았습니다.)

Important:

Please note that you are encouraged to use the same version on client and cluster sides. You may hit some incompatibilities issues when mixing major versions.

ClientConfig clientConfig = ClientConfig.getInstance();

// cluster.name 을 안 줄 경우 NoNodeAvailable 에러 발생.

settings = ImmutableSettings

        .settingsBuilder()

        .put("cluster.name", clientConfig.getProperty("cluster.name"))

        .build();

client = new TransportClient(settings)

        .addTransportAddress(new InetSocketTransportAddress(clientConfig.getProperty("cluster.host1")

                , Integer.parseInt(clientConfig.getProperty("cluster.host1.port"))))

        .addTransportAddress(new InetSocketTransportAddress(clientConfig.getProperty("cluster.host2")

                , Integer.parseInt(clientConfig.getProperty("cluster.host2.port"))));

@Test

public void testClientProperties() throws Exception {

    clientManager.openClient();

    Client client = clientManager.getClient();

    AdminClient admin = client.admin();

    ClusterAdminClient cluster = admin.cluster();

    IndicesAdminClient indices = admin.indices();

    ClusterStateRequestBuilder request = cluster.prepareState();

    ClusterStateResponse response = request.execute().actionGet();  

    ClusterState state = response.state();

    AllocationExplanation allocation = state.allocationExplanation();

    ClusterBlocks block = state.blocks();

    MetaData meta = state.metaData();

    RoutingNodes routingNode = state.routingNodes();

    RoutingTable routingTable = state.routingTable();

    ImmutableSettings settings = (ImmutableSettings) meta.persistentSettings();

    log.debug("{}", response.clusterName()); // Cluster [test.gruter.es.cluster]

    log.debug("{}", response.getClusterName());

    log.debug("{}", response.getHeaders());

    log.debug("{}", response.getState());

    log.debug("{}", response.state());

    log.debug("{}", state.allocationExplanation());

    log.debug("{}", state.blocks());

    log.debug("{}", state.metaData());

    log.debug("{}", state.nodes()); // {[test.gruter.es.cluster2.node][sIj29f-KQziaIbccn_jndg][inet[/127.0.0.1:9301]]{master=true},[test.gruter.es.cluster1.node][kWNDF8SLTxS_axatGmImIg][inet[/127.0.0.1:9300]]{master=true},}

    log.debug("{}", state.routingNodes());

    log.debug("{}", state.routingTable());

    log.debug("{}", state.version());

    log.debug("{}", allocation.explanations());

    log.debug("{}", block.indices());

    log.debug("{}", meta.concreteAllIndices());

    log.debug("{}", meta.concreteAllOpenIndices());

    log.debug("{}", meta.getTotalNumberOfShards());

    log.debug("{}", meta.persistentSettings());

    log.debug("{}", meta.settings());

    log.debug("{}", routingNode.getMetaData());

    log.debug("{}", routingNode.getNodesToShards());

    log.debug("{}", routingNode.getRoutingTable());

    log.debug("{}", routingNode.getUnassigned());

    log.debug("{}", routingNode.prettyPrint());

    log.debug("{}", routingTable.getIndicesRouting());

    log.debug("{}", routingTable.prettyPrint());

    log.debug("{}", settings.getAsMap());

    log.debug("{}", state.nodes().dataNodes());

    log.debug("{}", state.nodes().getSize());

    for ( int i=0; i<state.nodes().getSize(); i++ ) {

        log.debug("{}", state.nodes().dataNodes().keySet().toArray()[i]);

    }

    Set entries = state.nodes().dataNodes().entrySet();

    Iterator entryIter = entries.iterator();

    while (entryIter.hasNext()) {

        Map.Entry entry = (Map.Entry)entryIter.next();

        Object key = entry.getKey();

        Object value = entry.getValue();

        log.debug("key : {}", key);

        log.debug("value : {}", value);

    }

} 

bin/plugin -install elasticsearch/elasticsearch-hadoop/1.2.0

jeong-ui-MacBook-Pro:bin hwjeong$ cat start_es.sh 

#!/bin/bash

ES_PATH=/Users/hwjeong/server/app/es-0.17.10

$ES_PATH/bin/elasticsearch -p $ES_PATH/bin/pidfile.pid -Des.config=$ES_PATH/config/elasticsearch.yml -Xmx256m -Xms256m -Des.max-open-files=true > /dev/null 2>&1 &

jeong-ui-MacBook-Pro:bin hwjeong$ cat stop_es.sh 

#!/bin/bash

ES_PATH=/Users/hwjeong/server/app/es-0.17.10

/bin/kill `cat < $ES_PATH/bin/pidfile.pid `

[2013-04-03 10:56:11,568][INFO ][node                     ] [Halloway, Thomas] {elasticsearch/0.17.10}[638]: initializing ...

[2013-04-03 10:56:11,576][INFO ][plugins                  ] [Halloway, Thomas] loaded [], sites []

[2013-04-03 10:56:14,456][ERROR][bootstrap                ] {elasticsearch/0.17.10}: Initialization Failed ...

this line : JAVA_OPTS="$JAVA_OPTS -Xss128k"

to : JAVA_OPTS="$JAVA_OPTS -Xss256k"