LD 算法实现（编辑距离算法）

LD算法就是自然语言处理(NLP)里的“编辑距离”算法。俄国科学家Levenshtein提出的，故又叫Levenshtein Distance （LD算法）。

【定义】设A和B是两个字符串。将字符串A转换为字符串B所用的最少字符操作数称为字符串A到字符串B的编辑距离。（ 这里所说的字符操作包括：删除一个字符，插入一个字符，修改一个字符）

如果有人想看具体算法的描述还是自己去搜吧。我搜到的算法描述大部分是鸟语，而且下面的例子代码无数错，看了2天才写了个标准C的程序，贴出来晒晒。代码最后我加了个小应用来实现了简单的串相似度比较。代码加了注释，应该不难理解。为了篇幅小，我改了下代码排版和代码风格，推荐下载源码用编辑环境看，着色后可读性才强。

#include "stdio.h"
#include "malloc.h"
#include "string.h"

#define MAX(a,b) ((a)>(b)?(a):(b))

void matrix_print(char *matrix, int row, int col)
{
    int  i, j;
    for(i=0; i<row; i++) {
    for(j=0; j<col; j++) {
            printf("%4.2d", matrix[i*col+j]);
}
        printf("\n");
}
}

char matrix_value(char left, char top, char top_left, int cost)
{
    char ret = left<top?left:top;
    return ret<top_left?ret+1:top_left+(char)cost;
}

int main()
{
    char *matrix, str1[255], str2[255];
    int  row, col, i, j, dis;
    double sim;

    printf("please input str1: ");
    scanf("%s", str1);
    printf("please input str2: ");
    scanf("%s", str2);

    /* 矩阵要比行列各多一来存储矩阵行列序号 */
    row = strlen(str1) + 1;
    col = strlen(str2) + 1;
    matrix = (char*) malloc(col*row); /* 申请空间 */

    /* 初始化首行、首列 */
    for(i=0; i<row; i++) matrix[i*col] = i;
    for(j=0; j<col; j++) matrix[j] = j;

    /*
    * 根据算法填充矩阵: 当字符相同时cost=0, 否则cost=1.
     * 也就是代码中的 !(str1[i-1]==str2[j-1])
     * 取待填值(val)位置的3个邻居left,top,top-left的值来进行比较，
     * 取最小值(min)。当 left或top 为最小值时, val=min+1.
     * 当 top-left 为最小值时, val=min+cost.
     */
    for(i=1; i<row; i++) {
        for(j=1; j<col; j++)
            matrix[i*col+j] = matrix_value(matrix[i*col+j-1],
                                           matrix[(i-1)*col+j],
                                           matrix[(i-1)*col+j-1],
                                           !(str1[i-1]==str2[j-1]));
    }
    matrix_print(matrix, row, col);/* 打印矩阵 */
    dis = matrix[(row*col - 1];/*矩阵最后的格子就是“编辑距离” */
    printf("distance = %d\n", dis);

    /*
    * 小应用: 使用“编辑距离” 来算2个串的相似度。
     * 可以根据自己需要设计不同的算法，我就是简单的除以了下长串。
     */
    sim = 1 - ((double)dis/(double)MAX(row-1, col-1));
    printf("similar = %f\n", sim);
    free(matrix);
return 0;
}