【迷惑度】-高-
【送信元】"Simon Delgado" <Simon@gacworld.com>
【配信サーバ】58.10.81.121.TRUENET ( TH )
< ppp.revip2.asianet.co.th >
// The "Levenshtein distance" is a measure of the similarity between two st
rings,
// this algorithm is also refered to as "edit distance". The "Levenshtein d
istance"
// was named after the russian scientist "Vladimir Levenshtein", who has di
scovered
// it back in 1965. The smaller the distance between two strings, the close
r are
// these strings syntacticaly. The "Levenshtein distance" is computed by
// calculating the minimum number of operations that has to be made to tran
sform
// one string to another one,usualy this operations are: replace,insert or
delete a character
// example: we can change the word: "mathematics" to "mathematician" by cha
nging one character
// and by inserting two more characters at the end.(we can replace "s" by "
i" and
// also insert "a" and "n" after that). The total number of operations that
was needed in this
// case to change "mathematics" to "mathematician" was 3 operations and sin
ce it is
// also the smallest number of operation that can be use to transform one o
f this strings
// to the other one, that value is also a measure of the "Levenshtein dista
nce" between
// these two strings.
// There has been many application of the "Levenshtein distance", here is a
few of them:
// Spell Checking, Speech Recognition, Pattern Recognition etc. ***********
*****
//
**********
#include "distance.h"
// finds the minimum of tree integers
int _min(int a, int b, int c) {
return min(min(a, b), c);
}
// allocates a 2D array of integers
int **create_matrix(int Row, int Col) {
int **array = new int*[Row];
for(int i = 0; i < Row; ++i) {
array[i] = new int[Col];
}
return array;
}
// deallocates memory
int **delete_matrix(int **array, int Row, int Col) {
for(int i = 0; i < Row; ++i) {
delete array[i];
}
delete [] array;
return array;
}
// computes the Levenshtein distance between two strings
// "x" represent the pattern and "y" represent the text
// "m" is the pattern length and "n" is the text length
int LD(const char *x, unsigned int m, const char *y, unsigned int n) {
// if the length of the second string is zero
// then the distance between the two strings will
// be equal to the length of the first string
// and vis-versa
// if the length of both strings is equal to zero
// then the distance between this two strings will
// simply be zero
if (n == 0) {
return m;
}
else if (m == 0) {
return n;
}
// creating a matrix of m+1 rows and n+1 columns
int **matrix = create_matrix(m + 1, n + 1);
// initialising the first row of the matrix
for(unsigned int i = 0; i
これがスパムメールだ！
0
