Lucene里面的分词器里面有一个PorterStemFilter类,里就用到了著名的词干提取算法。所谓Stemming,就是词干,在英语中单词有多种变形。比如单复数加s,进行时加ing等等。在分词的时候,如果能够把这些变形单词的词根找出了,对搜索结果是很有帮助的。Stemming算法有很多了,三大主流算法是Porter stemming algorithm、Lovins stemming algorithm、Lancaster (Paice/Husk) stemming algorithm,还有一些改进的或其它的算法。这个PorterStemFilter里面调用的一个PorterStemmer就是Porter Stemming algorithm的一个实现。 其主页为http://tartarus.org/~martin/PorterStemmer/,也可查看其论文http://tartarus.org/~martin/PorterStemmer/def.txt。通过以下网页可以进行简单的测试:Porter's Stemming Algorithm Online[http://facweb.cs.depaul.edu/mobasher/classes/csc575/porter.html]。
网上找了好久,才找到一个对此算法解释的文章,它用的是Java版的代码,这里我改成用.net版的。主要是把里面的函数作了一下注释,个人没做什么分析,本身是想的,结果看着就头痛。下面的东西都是来自这篇博文波特词干算法,我只是把这里的代码改成了.net的。
接下来,是一系列工具函数。首先先介绍一下它们:
- cons(i):参数i:int型;返回值bool型。当i为辅音时,返回真;否则为假。
/// <summary>
/// cons(i) 为真 <=> b[i] 是一个辅音
/// </summary>
private bool cons(int i)
{
switch (b[i])
{
case 'a':
case 'e':
case 'i':
case 'o':
case 'u':
return false;
case 'y':
return (i == k0) ? true : !cons(i - 1);//y开头,为辅;否则看i-1位,如果i-1位为辅,y为元,反之亦然。
default:
return true;
}
}
- m():返回值:int型。表示单词b介于0和j之间辅音序列的个度。现假设c代表辅音序列,而v代表元音序列。<..>表示任意存在。于是有如下定义;
- <c><v> 结果为 0
- <c>vc<v> 结果为 1
- <c>vcvc<v> 结果为 2
- <c>vcvcvc<v> 结果为 3
- ....
/// <summary>
/// m() 用来计算在0和j之间辅音序列的个数
/// </summary>
/// <returns></returns>
private int m()
{
int n = 0;//辅音序列的个数,初始化
int i = k0;//偏移量
while (true)
{
if (i > j)//如果超出最大偏移量,直接返回n
return n;
if (!cons(i))//如果是元音,中断
break;
i++;//辅音移一位,直到元音的位置
}
i++;//移完辅音,从元音的第一个字符开始
while (true)//循环计算vc的个数
{
while (true)//循环判断v
{
if (i > j)
return n;
if (cons(i))
break;//出现辅音则终止循环
i++;
}
i++;
n++;
while (true)//循环判断c
{
if (i > j)
return n;
if (!cons(i))
break;
i++;
}
i++;
}
}
- vowelinstem():返回值:bool型。从名字就可以看得出来,表示单词b介于0到i之间是否存在元音。
/// <summary>
/// vowelinstem() 为真 <=> 0,...j 包含一个元音
/// </summary>
/// <returns>[To be supplied.]</returns>
private bool vowelinstem()
{
int i;
for (i = k0; i <= j; i++)
if (!cons(i))
return true;
return false;
}
- doublec(j):参数j:int型;返回值bool型。这个函数用来表示在j和j-1位置上的两个字符是否是相同的辅音。
/// <summary>
/// doublec(j) 为真 <=> j,(j-1) 包含两个一样的辅音
/// </summary>
/// <param name="j"></param>
/// <returns></returns>
private bool doublec(int j)
{
if (j < k0 + 1)
return false;
if (b[j] != b[j - 1])
return false;
return cons(j);
}
- cvc(i):参数i:int型;返回值bool型。对于i,i-1,i-2位置上的字符,它们是“辅音-元音-辅音”的形式,并且对于第二个辅音,它不能为w、x、y中的一个。这个函数用来处理以e结尾的短单词。比如说cav(e),lov(e),hop(e),crim(e)。但是像snow,box,tray就辅符合条件。
/* cvc(i) is 为真 <=> i-2,i-1,i
* 有形式: 辅音 - 元音 - 辅音
* 并且第二个c不是 w,x 或者 y.
* 这个用来处理以e结尾的短单词。
* e.g. cav(e), lov(e), hop(e), crim(e),
* 但不是 snow, box, tray. */
private bool cvc(int i)
{
if (i < k0 + 2 || !cons(i) || cons(i - 1) || !cons(i - 2))
return false;
else
{
int ch = b[i];
if (ch == 'w' || ch == 'x' || ch == 'y') return false;
}
return true;
}
- ends(s):参数:String;返回值:bool型。顾名思义,判断b是否以s结尾。
private bool ends(string s)
{
int l = s.Length;
int o = k - l + 1;
if (o < k0)
return false;
for (int i = 0; i < l; i++)
if (b[o + i] != s[i])
return false;
j = k - l;
return true;
}
- setto(s):参数:String;void类型。把b在(j+1)...k位置上的字符设为s,同时,调整k的大小。
// setto(s) 设置 (j+1),...k 到s字符串上的字符, 并且调整k值