系列アライメント

アルゴリズムデザインにのっていたので、c++で実装してみた。
系列アライメントとは、Googleの「もしかして:」の機能のような似ている文字列を探すやつのこと。
二つの文字列で動的計画法を使って類似度を計算する。

入力

単語(辞書)
...
#
チェックする単語
...

実装

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 1 << 29;
const int MAX_WORD_N = 100;	//辞書の単語数
const int MAX_WORD_LEN = 20;	//単語の最大文字数
const int GAP_PENALTY = 3;	//ギャップペナルティ
int MISMATCH_COST[128][128];	//ミスマッチコスト
char DIC[MAX_WORD_N][MAX_WORD_LEN + 1];//辞書

int read_dic();		//辞書読み込み関数
int compare(const char *, const char *);//類似度計算関数

int main(){
	int word_n;
	char s[MAX_WORD_LEN + 1];
	word_n = read_dic();	//辞書読み込み
	printf("INCLUDED DICTIONARY\nword_n=%d\n",word_n);
	while(scanf("%s", s) != EOF){

	int similarity = INF;	//類似度　小さいほど類似
	int p = -1;		//もっとも類似している単語の番号
	for(int i = 0; i < word_n; i++){
		//類似度計算
		int t = compare(s, &DIC[i][0]);
		if(t < similarity){
			//もっとも類似している単語を記憶
			similarity = t;
			p = i;
		}
	}
	printf("%s\n", s);
	printf("もしかして:%s\n類似度%d\n\n", &DIC[p][0], similarity);
	}
	return 0;
}

int compare(const char *s1, const char *s2){
	int dp[MAX_WORD_LEN + 1][MAX_WORD_LEN + 1];
	int s1_len, s2_len;
	s1_len = strlen(s1); s2_len = strlen(s2);
	dp[0][0] = 0;
	for(int i = 1; i <= s1_len; i++)
		dp[i][0] = dp[i - 1][0] + GAP_PENALTY;
	for(int j = 1; j <= s2_len; j++)
		dp[0][j] = dp[0][j - 1] + GAP_PENALTY;
	for(int i = 1; i <= s1_len; i++){
		for(int j = 1; j <= s2_len; j++){
			dp[i][j] = min(min(dp[i-1][j], dp[i][j-1])+GAP_PENALTY, dp[i-1][j-1]+MISMATCH_COST[s1[i]][s2[j]]);
		}
	}
	return dp[s1_len][s2_len];
}
int read_dic(){
	int n = 0;
	char c;
	char s[MAX_WORD_LEN];
	while(scanf("%s", &DIC[n][0]) != EOF){
		scanf("%c", &c);
		if(DIC[n][0] == '#') break;
		n++;
	}
	for(int i = 0; i < 128; i++){
		for(int j = 0; j < 128; j++){
			if(i == j)	MISMATCH_COST[i][j] = 0;
			else		MISMATCH_COST[i][j] = 4;
		}
	}
	return n;
}