C++ 处理GBK编码的汉字，计算编辑距离，以及common_prefix

这篇文章中，给出了java和Python版本的计算编辑距离

我一开始就直接复制了其中的Python代码，正如我评论那篇文章的那样

这个Pytrhon代码不知道起源在在哪？P.S.网上的有太多的信息冗余，以及copied转载得文章。但是作者在转载的时候，没有check文章中的代码是否正确。
distance_matrix 没有初始化正确。
应该初始化为：
0,1,2,3,4
1,
2,
3,

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

因为要使用编辑距离，且不是Python代码中。使用的方式，可能是在shell中每次计算都要调用python xx.py string1 string2。

这样每次计算都要执行一天python命令，调用大概18000次，就需要5分钟左右。效率无法忍受。

一开始以为是计算的过程耗时，采用动态规划但是时间复杂度还是string1.length * string2.length，空间复杂度也相同。

后来采用一个简单的处理方式，就是不计算 编辑距离，而是计算common_prefix，结果发现跑18000次python命令的时间还是5分钟很长。（有时间需要研究一下，运行python xx.py的过程以及耗时）

所以，就考虑使用C++写代码。（还没有测试效率怎样）

然后，就有了上篇关于gcc 和VS 2010中分别有 sizeof(wchar_t) ==4 和 sizeof(wchar_t) == 2，使用 setlocle也没有作用。

下面就是C++处理中文的编辑距离，和common_prefix

#include <iostream>#include <cstdlib>#include <cstdio>#include <string>#include <cstring>#include <wchar.h>#include <typeinfo>using namespace std;inline wchar_t* MBCS2Unicode(wchar_t* buff,const char * str){    wchar_t * wp = buff;    const char * p = str;    while(*p)    {        *wp = (wchar_t) 0x0;        if(*p & 0x80)        {            //因为sizeof(wchar_t) 在linux为4            //所以需要trick处理一下            char temp[sizeof(wchar_t)];            temp[0] = *p;            p++;            temp[1] = *p;            for(int i = 2; i < sizeof(wchar_t); i++)                temp[i] = 0x0;            *wp = *(wchar_t *)temp;        }        else{            *wp = (wchar_t) *p;        }        wp++;        p++;    }    *wp = 0x00000000;    return buff;} inline wstring str2wstr(char* str){    size_t len = strlen(str);    wchar_t* b = (wchar_t *)malloc((len+1)*sizeof(wchar_t));    MBCS2Unicode(b, str);    wstring r(b);    free(b);    return r;}int common_prefix(const wstring& s1, const wstring& s2) {    int common_prefix = 0;    for(int i = 0, j = 0; i < s1.length() && j < s2.length() ; i++, j++) {        if(s1[i] == s2[j]) {            common_prefix++;        }        else {            break;        }    }    return  common_prefix;}//''' 【编辑距离算法】 【levenshtein distance】 【字符串相似度算法】 '''int levenshtein(const wstring& s1, const wstring& s2) {    if(s1.length() == 0 ) {        return s2.length();    }    if(s2.length() == 0 ) {        return s1.length();    }    int** distance_matrix = new int*[s1.length() + 1];    for(int row = 0; row <= s1.length() ; row++ ) {        distance_matrix[row] = new int[s2.length() + 1];        distance_matrix[row][0] = row;    }    for(int col = 0; col <= s2.length() ; col++ ) {        distance_matrix[0][col] = col;    }    for(int i = 1; i <= s1.length() ; i++ ) {        for(int j = 1; j <= s2.length() ; j++ ) {            int deletion = distance_matrix[i-1][j] + 1;            int insertion = distance_matrix[i][j-1] + 1;            int substitution = distance_matrix[i-1][j-1] + (s1[i - 1] == s2[j - 1]? 0:1);            distance_matrix[i][j] = min(insertion, min(deletion, substitution));        }    }    for(int row = 0; row < s1.length() ; row++ ) {        delete[] distance_matrix[row];    }    delete[] distance_matrix;    return distance_matrix[s1.length()][s2.length()];}    int main(int argc, char* argv[]) {    setlocale(LC_ALL,"Chinese-simplified");    if( argc != 3 ) {        cout << "Usage: ./common_prefix string1 string2" << endl;        return -1;    }    wstring s1 = str2wstr(argv[1]);    wstring s2 = str2wstr(argv[2]);    cout << common_prefix(s1, s2) << endl;    cout << levenshtein(s1, s2) << endl;    return 0;}

1楼han_yankun200920分钟前

详细了解了