LevenshtainDistance

LevenshtainDistance는 두 문자열간의 유사성을 측정하기 위해 사용된다.

spell checking, DNA 유사성 검사, 음성인식, handwriting 인식 등에 사용된다고한다.

이론적인 내용은 위키피디아에서 찾아볼 수 있다.

LevenshtainDistance

코드...

#include <iostream>

#include <cstring> // strlen 사용

using namespace std;

class LevenshtainDistance

{

private:

static int min(int a, int b, int c);

public:

static int LD(char *s, char *t);

};

int LevenshtainDistance::min(int a, int b, int c)

{

int m = a;

if (b < m) m = b;

if (c < m) m = c;

return m;

}

int LevenshtainDistance::LD(char *s, char *t)

{

int slen = strlen(s), tlen = strlen(t);

int i, j;

int cost;

int **d = new int*[slen + 1];

for (i = 0; i <= slen; ++i) d[i] = new int[tlen + 1];

if (slen == 0) return tlen;

if (tlen == 0) return slen;

for (i = 0; i <= slen; ++i) d[i][0] = i;

for (i = 0; i <= tlen; ++i) d[0][i] = i;

for (i = 1; i <= slen; ++i)

{

for (j = 1; j <= tlen; ++j)

{

if (s[i - 1] == t[j - 1]) cost = 0;

else cost = 1;

d[i][j] = min(d[i - 1][j] + 1,

d[i][j - 1] + 1,

d[i - 1][j - 1] + cost);

}

}

int dis = d[slen][tlen];

for (i = 0; i <= slen; ++i)

delete d[i];

delete d;

return dis;

}

int main()

{

char *s = "GUMBO";

char *t = "GAMBOL";

cout << LevenshtainDistance::LD(s, t) << endl;

return 0;

}

코드 출처 : 실생활 문제로 접근하는 자료구조와 알고리즘 - 김종현 [내하출판사]