最小编辑距离（Minimum Edit Distance，MED）

[wangyingjun]

最小编辑距离（Minimum Edit Distance，MED），又称Levenshtein距离

编辑距离是针对二个字符串（例如英文字）的差异程度的量化量测，量测方式是看至少需要多少次的处理才能将一个字符串变成另一个字符串。编辑距离可以用在自然语言处理中，例如拼写检查可以根据一个拼错的字和其他正确的字的编辑距离，判断哪一个（或哪几个）是比较可能的字。DNA也可以视为用A、C、G和T组成的字符串，因此编辑距离也用在生物信息学中，判断二个DNA的类似程度。Unix 下的 diff 及 patch 即是利用编辑距离来进行文本编辑对比的例子。

例子

kitten和sitting的最小编辑距离是3。将kitten变为sitting的最小处理方式如下：

1. kitten → sitten（将k改为s）
2. sitten → sittin（将e改为i）
3. sittin → sitting（最后加入g）

最终问题与子问题之间的关系

/*
 * 原字符串长度为 i,目标字符串长度为 j, 编辑距离为 d[i][j]
 * 分析：编辑只有三种操作，分别为：添加，删除，替换
 *	str1[i] == str2[j]
 * 	相等不需要编辑，则 编辑距离为 d[i-1][j-1]
 * 	不相等：
 *		添加操作 d[i-1][j] + 1
 *		删除操作 d[i][j-1] + 1
 *		替换操作 d[i-1][j-1] + 1
 *		min(删除，添加，替换)
 */

// 动态规划数据输出
function ed(source, target){
 	const sourceLen = source.length,
 		targetLen = target.length;

	//初始化表格
	let table = [];
	for(let i=0; i<=sourceLen; i++){
		let row = [];

		if(i===0){
			for(let j=0; j<=targetLen; j++){
				row.push(j)
			}
		}else{
			row.push(i)
		}
		table.push(row)
	}
	//计算d[i][j]的编辑距离
	for(let i=1; i<=sourceLen; i++){
		for(let j=1; j<=targetLen; j++){
			//判断当前字符串是否相等
			if(source[i-1] === target[j-1]){	//相等取值d[i-1][j-1]
				table[i][j] = table[i-1][j-1];
			}else{	//不相等取值min(删除，添加，替换)
				table[i][j] = Math.min(table[i-1][j-1], table[i][j-1], table[i-1][j]) + 1;
			}
		}
	}
	return table;
 }

通过动态规划可得出字符串的最少编辑次数，如果需要得到具体编辑步骤，需要通过规划表格回溯路径来得到编辑步骤

const INSERT = 'INSERT',
 	DELETE = 'DELETE',
 	REPLACE = 'REPLACE';

// 表格回溯，找出回溯路径以及编辑方案
function backtrackingED(table, source, target){
	let rowLen = table.length,
		colLen = table[0].length,
		x = rowLen-1, y = colLen-1;

	let endPoint = table[x][y];
	let path = [];

	while(endPoint !== 0 || (x > 0 || y > 0)){
		if(x === 0){
			path.push({
				type: INSERT,
				index: 0,
				content: target[0]
			});
			y--;
			endPoint = [x][y];
			continue;
		}
		if(y === 0){
			path.push({
				type: DELETE,
				index: x-1,
				content: source[0]
			});
			x--;
			endPoint = [x][y];
			continue;
		}
		let leftTop = table[x-1][y-1],
			left = table[x][y-1],
			top = table[x-1][y];

		let min = Math.min(leftTop, left, top);

		switch(min){
			case leftTop:
				if(min !== endPoint){
					path.push({
						type: REPLACE,
						index: x-1,
						content: target[y-1]
					})
				}

				y--;
				x--;
				break;
			case top:
				path.push({
					type: DELETE,
					index: x-1,
					content: source[x-1]
				})
				x--;
				break;
			case left:
				path.push({
					type: INSERT,
					index: x-1,
					content: target[y-1]
				})
				y--;
				break;
		}

		endPoint = min;

	}

	return path;

}

测试数据输出

function table(table, source, target){

	let firstLine = '\t\t';
	target.split('').map(item => {
		firstLine += `${item}\t`
	})
	console.log(firstLine);

	table.map((item, index) => {
		let rowLine = '';
		if(index === 0){
			rowLine += `\t`
		}else{
			rowLine += source.substr(index-1, 1) + `\t`
		}
		item.map( row => {
			rowLine += `${row}\t`
		})
		console.log(rowLine)
	})
}
let str1 = 'fsfgfdfadsg',
	str2 = 'cabfdsfacc';
let edTable = ed(str1, str2);
console.log(backtrackingED(edTable, str1, str2))

table(edTable, str1, str2)

tips: 得到编辑步骤后，可以从尾进行编辑还原，不会应为编辑之后字符串长度发生变化，定位不准的问题