文档介绍：seek 算法 Coreseek 算法分析本文对 coreseek 代码中涉及到的一部分算法进行说明,以便在阅读代码的时候, 能更容易理解相关的代码。本文所整理的只是其中的部分算法,后面将在逐渐深入理解的基础上,进一步添加。一. Soundex 算法 1. 算法原理 Soundex 是一种语音算法, 利用英文字的读音计算近似值, 值由四个字符构成, 第一个字符为英文字母, 后三个为数字。在拼音文字中有时会有会念但不能拼出正确字的情形, 可用 Soundex 做类似模糊匹配的效果。例如 Knuth 和 Kant 二个字符串,它们的 Soundex 值都是 K530 。大部分的数据库服务器都有 Soundex 函数。 Soundex 算法有几个差别不大的变化版本。更详细的说明参考 Donald Knuth 大师的名著: 电脑程序设计的艺术(The Art puter Programming) 第三卷排序和搜寻。 1 名字的第一个字母不变。 2 根据特定的对照表,将剩下的字母转换为数字: uaehiouwy ->0 ubfpv ->1ucgjkqsxz ->2 udt ->3ul ->4umn ->5ur ->63 去除连续重复。 4 去除所有 9。 5 如果结果都少于四个字符( 第一个字母加上后面的三位字符) ,就以零补齐。 6 如果结果超过四个字符,丢弃掉四位之后的字符。以 Knuth 和 Kant 为例: Knuth -> K5030 -> K53 -> K530 Kant -> K053 -> K53 -> K530 2. 算法实现文件中的 void stem_soundex ( BYTE * pWord ) 函数实现。 void stem_soundex ( BYTE * pWord ) { // 字母转化规则用数组表示,后面直接根据数组进行映射转化 static BYTE dLetter2Code [ 27]= "012301200224550**********"; // check if the word only contains lowercase English letters BYTE *p= pWord; // 进行非英语字母的过滤 while ( *p>='a' && *p<='z' ) p++; if( *p) return; // do soundex p= pWord+1; BYTE * pOut = pWord+1; while ( *p){ // 对每一个字符, 根据映射关系进行转化, 得到转化以后的编码值。 BYTE c= dLetter2Code [ (*p)-'a' ]; if( c!='0' && pOut[-1]!=c ) *pOut++ = c; p++; } //补0 的操作 while ( pOut-pWord<4 && pOut<p ) *pOut++ = '0'; *pOut++ = '/0'; } 二. Metaphone 算法 1. 算法原理 Metaphone 是一种基于发音的算法,跟传统的 soundex 算法相比, metaphone 是产生可变长度的输出作为编码值,而 soundex 是产生固定长度的输出。发音相似的词语产生相同的输出。 Metaphone 算法是为了客服 soundex 算法的一些缺点而发展出来的, 它使用了大量的英语发音规则作为算法的依据。后来逐渐有一些算法的变种出现,比如 double metaphone 算法和 Metaphone 3 算法。 Metaphone 编码算法采用 16 个常数符号: 0BFHJKLMNPRSTWXY 。用'0' 表示"th" , 'X' 表示"sh" 或"ch", 其他的符号用来表示他们各自在英语中的发音。元音 AEIOU 也被用来编码, 但值在一个编码的开头使用。下面是这个编码的编码规则。 1. Drop duplicate adjacent letters, except for C. 2. If the word begins with 'KN', 'GN', 'PN', 'AE', 'WR', drop the first letter. 3. Drop 'B' if after 'M' and if it is at the end of the word. 4. 'C' transforms to 'X' if followed by 'IA' or 'H' (unless in latter case, it is part of '-SCH-', in which case it transforms to 'K'). 'C' transforms to