文本比较算法(转帖)
文本比较算法(转帖)
原文在这里 http://blog.csdn.net/sunskyor
最近看到有人在找关于文本比较的算法，刚好最近休假，研究了一下，终于找到一个简单有效的算法，和大家分享一下.
算法本身很简单，但是要说清楚思路和原理就比较复杂了，打算分两次发表（明天就要上班拉！），分别对应文本比较算法中的两个主要问题:
1. 如何确定最大匹配率;
2. 如何确定最优的匹配路径;
算法本身是基于图论的，太麻烦了，所以不打算介绍整个思路，只将最后的结果详细解说给大家。有问题可以发邮件给我：Calriones(at)hotmail(dot)com
文本比较算法剖析（1）-如何确定最大匹配率
1. 首先，我们假设有两个串left和right,
left=”ABCACADF”
right=”BCXCADFESBABCACA”
为了直观的分析问题，第一步，我用一个表格来逐个的比较left和right的每个元素：
图中，1 表示left 和 right 的某个元素是匹配的，0， 就是不匹配了， 那么， 现在的问题就是， 如何从表格中的左上角，找到一条路径，满足：
1. 经过的值为”1″的单元格最多；
2. 每次只能向右，或者向下，或者向右下方移动一格；
3. 如果本次位置在值为”1″的格子上，只能向右下方移动一格；
4. 如果移动到右边界或者下边界外，则终止。
2 .这其实就是一个有条件搜索最大权重路径的问题。但是，这里讲的是文本匹配问题，和图论相比，要简单很多。因为文本是流式的，两个文本之间的所有匹配关系一定是一个很规则的矩阵，这比图论中研究的情况要简单多了。
最先想到的是什么呢？迭代和递归，是不是？别着急，没有那么复杂的，我们来分析一下，再做打算。
我们先用手工标出从每个匹配点出发，一直到边界能够经过的最多匹配点个数，如下图所示：
各位可以自己手工做做，分析数量有限的图形，还是大脑比计算机好使。
3. 我们来分析一下，基本的思路是数学归纳法，呵呵，其实是递归算法的数学原型。
边界上的单元，不用说了，一定是最多只能找到一个匹配点。
而对于表格中的任意一个单元, 我们用 N(l,r) 来表示，对于它，按照上面的规则，它有3个邻接区域 A, B, C.
我们用N(l,r)来表示“将left的第L个元素和right的第R个元素匹配后，能够获取的最大匹配点数”。这个表述有点难以理解，从前面的“找到一个路径…”的观点出发，我们还可以这么说明N(l,r)的含义：“从第L行 R列的单元格出发，满足所有4个条件的路径上能够经过的值为”1″的单元个数”。
因为N(l,r)的下一步一定是区域A,B,C中的一个，而且，如果(l,r)是一个匹配点，只能选择进入A区域；如果进入B,C，则(l,r)一定不是一个匹配点。因此，我们可以得到：
N(l,r) = Max( V(l,r)+N(区域A), N(区域B), N(区域C) ) 。”V(l,r)表示单元(l.r)的值，=0表示单元(l,r)不是一个匹配点，=1表示单元(l,r)是一个匹配点”
而一个区域的最大匹配点数，就是从该区域的入口点出发，所能得到的最大匹配点数，即：N(区域[(a,b),(c,d)]) = N(a,b). “区域[(a,b),(c,d)]的意思是：由点(a,b) 和点(c,d)所构成的矩形区域)”
那么，前式就变成了：
N(l,r) = Max( V(l.r)+N(区域A), N(区域B), N(区域C) )
= Max( N(l+1,r+1)+V(l,r) , N(l,r+1), N(l+1,r))
在excel中，我们可以验证一下，设置单元格L4的公式=MAX(L5,M5+B4,M4)，然后拷贝这个公式直到和前面的矩阵相匹配，我们得到的结果如下：
可以和手工分析的结果对照一下（上图中最右部分），可以看到，结果完全一致。
Yes! 现在已经接近大功告成拉！简单吧！现在，就是如何代码化的问题了。
要将上面的方法编程，还差一个问题：初始化。这个很简单，从Excel的计算结果我们就可以知道。在上面的单元格公式中，边界单元引用了空白单元，而我们知道excel对空白单元取值做算术运算时是按照0计算的，所以初始化为0就可以了。
再从上面的分析可以知道：
1. 循环应该是从右向左，从下向上的；
2. 每个单元格的值只需要计算一次；
3. 计算N(l,r)时，需要引用3个值
因此，程序应该做逆序循环，用一个数组缓存N(l+1,r)和N(l+1,r+1)的值，用一个临时变量缓存N(l,r+1).
假设left有M个元素；right有N个元素，那么，这个程序的时间复杂度就是O(m.n), 空间复杂度就是Max(m,n).
好了，关于如何计算left和right的最大匹配数，就结束了。很简单，不是么？
如果想做一个文件比较工具的话，还需要确定最优的匹配路径。这个打算在下次再说，算法也比较简单，不过现在已经11点多了，明天要早起喽！
上回说到，如何确定最大匹配数。接下来，本次将简述如何确定最优匹配路径。仿照确定最大匹配数的算法，这个问题也非常容易解决，不知道这周当中，有没有哪位 XDJM 已经有了自己的解决方案呢？
有问题可以发邮件给我： Calriones(at)hotmail(dot)com
文本比较算法剖析（2）-如何确定最优匹配路径
确定最优匹配路径的问题，通常在做文件比较时要用到，它的意思是：在所有能够得到最大匹配点数的路径中，找出一条最短的路径。
让我们继续以上次的例子进行研究：
首先，我们仍然是手工标出能够得到最大匹配点数的所有路径。在手工绘制可用路径的时候，需要说明一下：
- 首先，这里我们以计算 left 的最优路径为例。计算 right 的最优路径和 left 是完全对称的；
- 在图中，向右移动一格，表示 left 的当前元素放弃和 right 的当前元素进行匹配，而和 right 的下一个元素进行匹配。如果进行文件比较的话，就是 left 文件的当前行前，插入 right 文件的当前行；
- 在图中，向下移动一格，表示 left 的当前元素放弃和 right 的当前元素进行匹配，而使用 left 的下一个元素和 right 的当前元素进行匹配。如果进行文件比较的话，就是 left 文件的当前行被删除；
- 在途中，向右下方移动一格，表示确定 left 和 right 的当前元素的匹配，使用 left 的下一个元素和 right 的下一个元素进行匹配。如果进行文件比较的话，就是 left 和 right 文件的当前行已经匹配，分别比较下一行。
- 由于 left 和 right 是流式的，所以每个元素只能匹配一次而且不能颠倒顺序，所以，在 x 和 y 方向上，只能保留一个匹配点，而且只能向下，向右，或者向右下方移动。
有了这些规则，我们就可以得到如下图中间红色粗线所示的 4 条可能的路径。
从上向下，依次编号为 1,2,3,4 号路径，分析如下：
1 号路径表示（只说明含义，算法推导在后面）：
依次类推，可以得到其他路径的实际含义。需要说明的是， 3 号路径在选择第二个匹配点时，没有采用 left[9]:right[1] 的匹配关系，而是跳过 left[9] ，采用了 left[11]:right[1] 。这样，点 (left[9], right[1]) 在 3 号路径上是“删除 left 第 9 行”的意思。
如果我将整个过程中在 left 上移动的距离纪录下来，就得到：
从图上就很容易看出，在 left 上移动最短的，也就是最优的路径，是 4 号路径。
是不是看起来毫无头绪？
别急，象上次一样，我们进行一个分析。
依然是归纳法，依然是找出元素 D(l,r) 的 3 个相邻区域 A,B,C:
分析：
1. 如果点 D(l,r) 表示从 left 的第 L 个元素， right 的第 R 个元素出发，匹配到矩阵边界后，在 left 方向上的最短路径长度 （我更喜欢称之为 depth ） ，那么：
2. 如果点 (l,r) 是一个被确定的匹配点，那么下一步，只能选择进入 A 区域，到点 (l+1,r+1) ，所以得到：
D1 If (V(l,r)>0) then D(l,r) = 1 + D(l+1,r+1)
还记得 V(l,r) 和 N(l,r) 的定义么？可以看看文档《文本比较算法剖析（ 1 ） – 如何确定最大匹配率 》
3. 如果点 (l,r) 不是一个被确定的匹配点，那么下一步可以进入 B 或者 C.
D2 如果进入 B 区域，那么意味着 ” 插入 right 的第 r 行 ” ，但是在 left 的位置保持不变，所以得到：
If (V(l,r) == 0) then D(l,r) = D(l,r+1)
D3 如果进入 C 区域，那么意味着 ” 删除 left 的第 l 行 ” ，在 right 的位置保持不变，但是在 left 的位置要加 1 。所以得到 :
If (V(l,r) == 0) then D(l,r) = 1 + D(l+1,r)
那么现在有 3 个值 D1 ， D2 ， D3 ，该如何取舍呢？直接取 Min(D1,D2,D3) 可以么？
呵呵，其实，我也是尝试了很多次以后才搞清楚的。大家可以用 excel 验证一下自己的想法。很简单的，大概验证整个算法，用 10 行左右的代码再加上 excel 本身提供的公式就足够了。
4. 不要忘记了前面说过的， ” 在所有能够得到最大匹配点数的路径中，找出一条最短的路径 ”, 首先我们要保证得到最大匹配匹配点数，所以我们又有：
If (N(l,r+1) >= N (l+1,r) then
D(l,r) = D(l,r+1);
Else
D(l+r) = 1 + D(l+1,r)
综合上面所有的分析，路径长度 D(l,r) 的计算公式就是：
If (V(l,r) = 1) Then
D(l,r) = D(l+1,r+1) + 1
Else
If (N(l,r＋1) >= N(l+1,r)) Then
D(l,r) = D(l,r+1)
Else
D(l,r) = D(l+1,r) + 1
End If
将公式写入 excel 自动计算，得到结果如图：
可以看到，结果正确。
OK 。 结束了，文本比较的算法核心就介绍完了。
事实上，上面第四步给出的是优化后的结果，有兴趣的可以自己试着分析一下第 4 步是否应该这样计算，有什么情况我没有在这里讲的，但是结果为什么又是正确的。
有了这个算法，大家可以很快的编写自己的文本比较功能了。
计算最优路径的附加时间复杂度为 0 ，因为它完全可以和计算最大匹配点数一起进行；附加的空间复杂度为 Max(m,n), 因为它需要一个额外的数组纪录 N(l+1) 。
如果不计算最优路径的话，计算最大匹配点数的算法还可以再优化。
文本比较算法再实现-3周末在家把思路理了一边，先是用python实现了一下，但性能不太理想（100k/s），考虑到可能是由于动态语言的效率本身比较慢的原因，于是将算法改成c语言实现，最终的结果是：1.8M/s（硬件环境：Intel Core Duo 1.73G, 内存2G）。对于这个结果来说，我还是不太满意，比较现在动辄都是上G的数据。这样的效率太慢了，下面放上代码，各位讨论下是否还有优化的余地或者这个算法本身比较慢，或者这个方案是不可行的？
以下代码在Ubuntu9.04下编译并运行通过，测试数据是从je上随便搞了几篇文章。 gcc版本：4.3.3
C 代码
#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <dirent.h>
#include <sys/stat.h>
#include <time.h>
#include <stdlib.h>
#define STEP 10
int count = 0; //文档个数
char * str = NULL; //一个大的字符串，存储所有文档的内容
int * ends; //文档的结束点集合
//文档结束点的内存参数（当前长度，内存长度）
int ends_len = 0, ends_mem_len = 10;
// 字符串的内存参数（字符串长度，字符串内存长度，
// 字符串unicode长度：即一个汉字占一个长度时的长度）
int str_len = 0, str_mem_len = 10, str_unicode_len=0;
struct id_map{ //一个文档在内存中的映射位置
int id; //文档id
int start; //字符串中的开始位置
int end; //字符串中的结束位置
};
struct id_map * idmaps=NULL; //文档在内存中的映射地址
int idmaps_len = 0, idmaps_mem_len=0; //文档映射参数
//添加一个文档映射参数
void addIdMap( struct id_map map){
if (idmaps==NULL){ //如果数组还没有建立，就建立一个数组来进行存储
idmaps = (struct id_map *)malloc( sizeof ( struct id_map)*10);
}
//如果当前的文档数已经到达了上一次建立的内存长度，则扩展内存，步长为10
if (idmaps_len==idmaps_mem_len){
idmaps_mem_len += STEP;
idmaps = (struct id_map *)realloc(idmaps,
sizeof ( struct id_map)*idmaps_mem_len);
if (idmaps==NULL){
printf("内存不足" );
return ;
}
}
*(idmaps+idmaps_len) = map;
idmaps_len++;
}
//读取一个文本文件
char * readTextFile( char * path) {
char ch; //当前的字符
FILE *fp; //文件指针
int result;
fp = fopen(path, "rb" );
if (fp!=NULL){ //如果文档读取成功
if (str==NULL){
//初始化str,ends的内存。这两个的增长步长均为10
ends = (int *)malloc( sizeof ( int ) * 10);
str = (char *)malloc(10);
}
if (!str){
printf("内存不足" );
fclose(fp);
return NULL;
}
int unicode_ = 0;
// 读取文件，一直读到最后，将内容放到str中。
while ((ch=fgetc(fp))!=EOF){
if (str_len == str_mem_len){
str_mem_len += STEP;
str = (char *)realloc(str, str_mem_len);
if (str == NULL){
printf("内存不足" );
fclose(fp);
return NULL;
}
}
// 如果上一个字符不是Unicode字符，
// 则判断如果当前字符为unicode字符，则进入unicode计数。
if (unicode_ == 0){
if (ch>=0 && ch<127){
str_unicode_len++;
}else {
unicode_ = 1;
}
}else if (unicode_ == 1){
unicode_ =2;
}else if (unicode_ == 2){
// 按照utf-8编码进行计算，每个汉字占三个字符。
unicode_ = 0;
str_unicode_len++;
}
*(str+str_len)=ch;
str_len++;
}
//记录结束点
if (ends_len == ends_mem_len){
ends_mem_len += STEP;
ends = (int *)realloc(ends, sizeof ( int ) * ends_mem_len);
if (ends == NULL){
printf("内存不足" );
fclose(fp);
return NULL;
}
}
//printf("---%d,%d,%d\n", ends_len,ends_mem_len,str_unicode_len);
//*(ends+ends_len) = str_unicode_len;
*(ends+ends_len) = str_unicode_len;
ends_len++;
str = (char *)realloc(str, str_len);
//*(str+len)='\0';
fclose(fp);
return str;
}
return NULL;
}
//读入一个文件夹内的所有文件
int init_search_dir( char *path)
{
//*
DIR *dir;
struct dirent *s_dir;
struct stat file_stat;
char currfile[1024]={0};
int len = strlen(path);
printf("%s\n" ,path);
if ( (dir = opendir(path)) == NULL)
{
printf("opendir(path) error.\n" );
return -1;
}
while ((s_dir = readdir(dir))!=NULL)
{
if ((strcmp(s_dir->d_name, "." )==0)||
(strcmp(s_dir->d_name, ".." )==0))
{
continue ;
}
sprintf(currfile,"%s%s" ,path,s_dir->d_name);
stat(currfile,&file_stat);
if (S_ISDIR(file_stat.st_mode)){ //如果是文件夹，则递归读取
init_search_dir(currfile);
}else {
printf("%-32s\tOK" ,currfile);
//设置一个文档与 str的映射，并读取文档的内容
struct id_map map;
map.id=atoi(s_dir->d_name);
map.start = str_unicode_len;
readTextFile(currfile);
map.end = str_unicode_len;
addIdMap(map);
printf("\t%d\n" , str_unicode_len);
}
count++;
}
closedir(dir);
ends = (int *)realloc(ends, sizeof ( int ) * ends_len);
//*/
return 0;
}
//计算一个utf-8字符串的长度(汉字占一个长度)
int utf8_str_len( char * utf8_str) {
int length = 0, unicode_ = 0, i=0;
for (;i<strlen(utf8_str);i++){
if (unicode_ == 0){
if (utf8_str[i]>=0 && utf8_str[i]<127){
length++;
}else {
unicode_ = 1;
}
}else if (unicode_ == 1){
unicode_ =2;
}else if (unicode_ == 2){
unicode_ = 0;
length++;
}
}
return length;
}
//查找该结束点是否存在(2分查找)
int find_ends( int num){
if (num>ends[ends_len-1]||num<ends[0]){
return -1;
}
int end = ends_len;
int start = 0;
int index=ends_len / 2;
while (1){
if (ends[index]==num){
return index;
}
if (start == end || index == start || index == end){
return -1;
}
if (ends[index] > num){
end = index;
}else {
start = index;
}
index = start + ((end-start) / 2);
}
}
//主要函数。搜索所有文档中所有存在于该字符串相似的文档，算法出处及JAVA实现参见：
// http://www.blogjava.net/phyeas/archive/2009/02/15/254743.html
void search( char * key){
int key_len = utf8_str_len(key); //计算key的长度
int i=0, j=0, j_ = 0, i_ = 0;
//char barr[key_len][str_unicode_len];
char * barr[key_len]; //
//char narr[key_len][str_unicode_len];
char * narr[key_len];
//char darr[key_len][str_unicode_len];
char * darr[key_len];
// 一个按照最大匹配度排序的文档序列。最大匹配度不可能大于key的长度+1，
// 所以声明一个key_len+1长度的数组进行保存即可。
// 数据格式类似：[[],[2,3],[5],[]]
//该数组的第n个下标表示最大匹配度为n的文档有哪些
int * max_id_maps[key_len + 1];
int max_id_maps_lens[key_len + 1], max_id_maps_mem_lens[key_len + 1];
int key_ascii_len = strlen(key);
struct timeval tpstart,tpend;
float timeuse;
gettimeofday(&tpstart,NULL);
// 初始化三个数组。i_,j_表示当前的坐标，i,j表示当前左右的字符串中的字符位置
for (i_=key_len-1, i=key_ascii_len-1;i>=0 && i_>=0;i--,i_--){
// 动态申请内存是为了解决c语言函数内声明数组的长度有限制
barr[i_] = (char *) malloc(str_unicode_len);
narr[i_] = (char *) malloc(str_unicode_len);
darr[i_] = (char *) malloc(str_unicode_len);
int is_left_ascii = key[i]<0 || key[i] >= 127 ? 0 : 1;
for (j=str_len-1, j_=str_unicode_len-1;j>=0&&j_>=0;j--,j_--){
int is_right_ascii = str[j] < 0 || str[j] >= 127 ? 0 : 1;
barr[i_][j_] = 0;
if (!is_left_ascii || !is_right_ascii){
if (!is_left_ascii && !is_right_ascii){
int k = 2, eq=1;
for (;k>=0;k--){
if (i-k >= 0 && j-k>=0 && key[i-k] != str[j-k]){
eq = 0;
break ;
}
}
barr[i_][j_] = eq;
}else {
barr[i_][j_] = 0;
}
}else {
barr[i_][j_] = str[j] == key[i] ||
tolower(str[j]) == tolower(key[i]) ? 1 : 0;
}
darr[i_][j_] = 0;
narr[i_][j_] = 0;
int indexOfEnds = find_ends(j_);
int n_right = 0, n_down = 0, n_rightdown = 0;
int d_right = 0, d_down = 0, d_rightdown = 0;
if (indexOfEnds == -1 && j_!=str_unicode_len - 1){
n_right = narr[i_][j_ + 1];
d_right = darr[i_][j_ + 1];
}
if (i_!=key_len -1){
n_down = narr[i_ + 1][j_];
d_down = darr[i_ + 1][j_];
}
if (indexOfEnds == -1
&& j_ != str_unicode_len - 1
&& i_ != key_len -1)
{
n_rightdown = narr[i_ + 1][j_ + 1];
d_rightdown = darr[i_ + 1][j_ + 1];
}
n_rightdown += barr[i_][j_];
narr[i_][j_] = n_right > n_down ?
(n_right > n_rightdown ? n_right : n_rightdown) :
(n_down > n_rightdown ? n_down : n_rightdown);
if (barr[i_][j_]){
darr[i_][j_] = d_rightdown + 1;
}else if (n_right >= n_down){
darr[i_][j_] = d_right;
}else {
darr[i_][j_] = d_down + 1;
}
if (!is_right_ascii){
j-=2;
}
//printf("%d\t", narr[i_][j_]);
}
//printf("\n");
//max_id_maps[i] = (int *)malloc(sizeof(int)*10);
max_id_maps_mem_lens[i_] = 0;
max_id_maps_lens[i_] = 0;
if (!is_left_ascii){
i-=2;
}
}
//max_id_maps[key_len] = (int *)malloc(sizeof(int)*10);
max_id_maps_mem_lens[key_len] = 0;
max_id_maps_lens[key_len] = 0;
int k=0;
//计算最大匹配度和最优匹配路径长度。并将其放到如到max_id_maps中
for (k=0;k<idmaps_len;k++){
int end=idmaps[k].end, j=idmaps[k].start;
int end_i = key_len, max_ = 0, min_ = -1;
while (j<end){
int temp_end_i = -1;
for (i=0;i<end_i;i++){
if (barr[i][j]){
if (temp_end_i==-1){
temp_end_i = i;
}
if (narr[i][j] > max_){
max_ = narr[i][j];
}
if (min_ == -1 || darr[i][j] < min_){
min_ = darr[i][j];
}
}
}
if (temp_end_i != -1){
end_i = temp_end_i;
}
j++;
}
if (max_ != 0){
if (max_id_maps_mem_lens[max_] == 0){
max_id_maps[max_] = (int *)malloc( sizeof ( int )*10);
max_id_maps_mem_lens[max_] = 10;
} else if (max_id_maps_mem_lens[max_]
== max_id_maps_lens[max_])
{
max_id_maps_mem_lens[max_] += STEP;
max_id_maps[max_] = (int *)realloc(max_id_maps[max_],
sizeof ( int )*max_id_maps_mem_lens[max_]);
}
*(max_id_maps[max_] + max_id_maps_lens[max_]) = idmaps[k].id;
max_id_maps_lens[max_]++;
}
}
//-----------------计时，计算性能
gettimeofday(&tpend,NULL);
timeuse=1000000*(tpend.tv_sec-tpstart.tv_sec)
+tpend.tv_usec-tpstart.tv_usec;
timeuse/=1000000;
printf("Used Time:%f\n" ,timeuse);
for (i=0;i<=key_len;i++){
printf("%d -- " ,i);
for (j=0;j<max_id_maps_lens[i];j++){
printf("%d\t" , max_id_maps[i][j]);
}
printf("\n" );
}
//--------------计时结束
//释放在这个函数中申请的动态内存。
for (i=0;i<=key_len;i++){
if (max_id_maps_mem_lens[i]>0){
//printf("%d,",max_id_maps_mem_lens[i]);
free(max_id_maps[i]);
}
if (i!=key_len){
free(barr[i]);
free(narr[i]);
free(darr[i]);
}
}
//testPrint(&narr, key_len, str_unicode_len);
}
//释放程序中申请的动态内存
void freeMemory(){
free(ends);
free(idmaps);
free(str);
}
int main(){
init_search_dir("/home/phyeas/test/" );
search("Java云计算" );
//search("BCXCADFESBABCACA");
//init_search_dir("/home/phyeas/test/test2/");
//int i=0;
freeMemory();
return 0;
}
近期评论