字符串相似度c语言,分享一段iOS上用的字符串相似度算法实现

Levenshtein的经典算法，参考http://en.wikipedia.org/wiki/Levenshtein_distance的伪代码实现的。同时参考了一些C++的实现，只能算是半转帖吧，没啥原创成分。

//

// NSString+Distance.m

// Levenshtein

//

// Created by Dawen Rie on 12-6-4.

// Copyright (c) 2012年 G4 Workshop. All rights reserved.

//

#import "NSString+Distance.h"

static inline int min(int a, int b) {

return a < b ? a : b;

}

@implementation NSString (Distance)

- (float) likePercent:(NSString *)target{

int n = self.length;

int m = target.length;

if (m==0) return n;

if (n==0) return m;

//Construct a matrix, need C99 support

int matrix[n+1][m+1];

memset(&matrix[0], 0, m+1);

for(int i=1; i<=n; i++) {

memset(&matrix[i], 0, m+1);

matrix[i][0]=i;

}

for(int i=1; i<=m; i++) {

matrix[0][i]=i;

}

for(int i=1;i<=n;i++)

{

unichar si = [self characterAtIndex:i-1];

for(int j=1;j<=m;j++)

{

unichar dj = [target characterAtIndex:j-1];

int cost;

if(si==dj){

cost=0;

}

else{

cost=1;

}

const int above=matrix[i-1][j]+1;

const int left=matrix[i][j-1]+1;

const int diag=matrix[i-1][j-1]+cost;

matrix[i][j]=min(above,min(left,diag));

}

}

return 100.0 - 100.0*matrix[n][m]/self.length;

}

@end

吐一下C99动态数组的口水，竟然不能用C语言静态数组的初始化方式(int arr[N] = {0} )。