基于Levenshtein距离算法的编辑距离算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | public static final int getDistance(String word, String similar) { //get the weights for each possible operation final int costOfDeletingSourceCharacter = config.getInteger(Configuration.COST_REMOVE_CHAR); final int costOfInsertingSourceCharacter = config.getInteger(Configuration.COST_INSERT_CHAR); final int costOfSubstitutingLetters = config.getInteger(Configuration.COST_SUBST_CHARS); final int costOfSwappingLetters = config.getInteger(Configuration.COST_SWAP_CHARS); final int costOfChangingCase = config.getInteger(Configuration.COST_CHANGE_CASE); int a_size = word.length() + 1 ; int b_size = similar.length() + 1 ; int [][] matrix = new int [a_size][b_size]; matrix[ 0 ][ 0 ] = 0 ; for ( int i = 1 ; i != a_size; ++i) matrix[i][ 0 ] = matrix[i - 1 ][ 0 ] + costOfInsertingSourceCharacter; //initialize the first column for ( int j = 1 ; j != b_size; ++j) matrix[ 0 ][j] = matrix[ 0 ][j - 1 ] + costOfDeletingSourceCharacter; //initalize the first row word = " " + word; similar = " " + similar; for ( int i = 1 ; i != a_size; ++i) { char sourceChar = word.charAt(i); for ( int j = 1 ; j != b_size; ++j) { char otherChar = similar.charAt(j); if (sourceChar == otherChar) { matrix[i][j] = matrix[i - 1 ][j - 1 ]; //no change required, so just carry the current cost up continue ; } int costOfSubst = costOfSubstitutingLetters + matrix[i - 1 ][j - 1 ]; //if needed, add up the cost of doing a swap int costOfSwap = Integer.MAX_VALUE; boolean isSwap = (i != 1 ) && (j != 1 ) && sourceChar == similar.charAt(j - 1 ) && word.charAt(i - 1 ) == otherChar; if (isSwap) costOfSwap = costOfSwappingLetters + matrix[i - 2 ][j - 2 ]; int costOfDelete = costOfDeletingSourceCharacter + matrix[i][j - 1 ]; int costOfInsertion = costOfInsertingSourceCharacter + matrix[i - 1 ][j]; int costOfCaseChange = Integer.MAX_VALUE; String strSrcChar = "" + sourceChar; String strOtherChar = "" + otherChar; if (strSrcChar.compareToIgnoreCase(strOtherChar) == 0 ) costOfCaseChange = costOfChangingCase + matrix[i - 1 ][j - 1 ]; matrix[i][j] = minimum(costOfSubst, costOfSwap, costOfDelete, costOfInsertion, costOfCaseChange); } } int cost = matrix[a_size - 1 ][b_size - 1 ]; if ( false ) System.out.println(dumpMatrix(word, similar, matrix)); return cost; } |
大规模中英文单词模糊搜索问题的分析
最近有一个关于在大规模的中英文词库中的模糊搜索问题。
这个问题具有几个特点:
- 每条记录都比较短。
- 记录的数量多,大约600万条记录。
- 对解的数量要求高于对解的质量要求。
- 有对中英文支持的要求。
对于单一的字符串模糊匹配问题,实际上是单纯的人工智能问题,站在模式识别的角度,就是计算与目标单词的距离,我们实际上需要通过求最一般合一来算出单词之间的编辑距离,这个编辑距离越大,匹配度就越低。如果想更进一步,那么借助遗传算法的思想,随着用户的操作来动态调整每一步编辑的权值(默认所有编辑行为的权值都为1),如果用户认可某次匹配,则对此次匹配所用到的所有编辑行为降低权值。
而对于这样的一个实际问题,首先我们不可能将600万条记录全部取出逐一检测匹配度,势必要进行一个事先的筛选。因此,大致的流程应该是这样:
- 针对所有数据建立倒排索引。
- 从索引查找到疑似的匹配项。
- 对疑似匹配项的匹配度进行逐个检查,去掉匹配度低的结果。
- 按匹配度从高到低输出结果。
针对此问题,还有以下一些问题需要解决。
而求编辑距离必须使用基于代价函数的广度优先搜索,否则,无法保证最优解,在权值全部相同的情况下,就等同于一般的广度优先搜索,修改步数增加以后,内存开销明显增加。
为了减小索引,加快索引速度,必须要合并类似的索引项,对于中文,根据拼音-汉字库将汉字一律合并至为对应拼音是可行的。
但是对于英文,不可能以字符为单位进行索引,而如果以单词为单位进行索引,拼写错误就无法从索引中找出相应项。如果对无法找到的项进行广度优先的编辑,试图从索引中找出最近似的条目,对于索引查询的开销也是极高的。
单词拆分对索引也是一个考验,因为如果某个单词无法匹配,其实则可能可以进行拆分,比如helloworld,有9种方法分成两个单词,那么需要对9种拆分方法逐个进行查询,开销也是很大的。如果在这个基础上再考虑拼写错误,那么开销就是平方级的增长了。