在上一篇日志里，我提到了 Lovins 的stemming 算法，与此相类似的还有Porter算法，处理的方式步骤略微不同，但是更加有效，所以在今天使用得非常广泛。
这篇日志介绍的是 troncation 算法。首先声明这个算法不是我想出来的，也不是什么很知名的算法，所以我在网上基本找不到相关的资料。事实上，这个算法是我的一门文档索引及查找的课上老师提到的，个人觉得这个思路非常好，也很有意思。算法的出发点是信息的角度，和语言学无关，所以它就具有一定的拓展性适用于不同的语言，除了某些黏着语（比如德语）。
算法的大致思路如下:
首先我们需要一个比较大的单词 liste，类似 dictionnaire；然后我们遍历这个liste里的每个单词，寻找单词每个字母后面所有字母的可能性，这么说可能比较抽象，我举个例子。
以单词 acceptables （法语单词）为例，我们列出以下的表:
| Préfix | Nombre of successeurs | Lettres |
| a | >9 | b,c, d,e,f,l,n,… |
| ac | 4 | |
| acc | 7 | |
| acce | 3 | |
| accep | 1 | |
| accept | 3 | |
| accepta | 1 | |
| acceptab | 1 | |
| acceptabl | 1 | |
| acceptable | 1 | |
| acceptables | 0 | fin |
我们在上表中可以发现，单词前缀刚开始的时候可能有很多的后续可能，但是随着前缀长度增加，后续可能会一下减少。然后到了某个长度时，后续可能会突然增加，之后基本就唯一了。这个转折点就是我们要找的前缀的长度（图中红色标注的accept）。
这个算法完全不依赖构词规则，更多地从统计学角度看。当然，这算法也是有缺陷的，比如对那些不规则的词或者短词就很无能为力。对那些后缀很长的词，词尾变化多的词非常有效。
Advertisement
