词干提取

在词法学和信息检索里，词干提取是去除词缀得到词根的过程─—得到单词最一般的写法。对于一个词的形态词根，词干并不需要完全相同；相关的词映射到同一个词干一般能得到满意的结果，即使该词干不是词的有效根。从1968年开始在计算机科学领域出现了词干提取的相应算法。很多搜索引擎在处理词汇时，对同义词采用相同的词干作为查询拓展，该过程叫做归并。词干提取项目一般涉及到词干提取算法或词干提取器。一个面向英语的词干提取器，例如，要识别字符串“cats”、“catlike”和“catty”是基于词根“cat”；“stemmer”、“stemming”和“stemmed”是基于词根“stem”。一根词干提取算法可以简化词 “fishing”、“fished”、“fish”和“fisher” 为同一个词根“fish”。第一篇关于词干提取器的文章是Julie Beth Lovins（英语：Julie Beth Lovins）在1968年写的。该文章由于其超前性所以特别出众，对后人对该领域的研究有深远的影响。一个篇较晚一些的文章来自于马丁·波特（英语：Martin Porter），出版在1980年7月的《程序》杂志上。该算法被广泛应用，成为英文词干提取中一个事实上的评判标准，被称为“波特词干算法（德语：Porter-Stemmer-Algorithmus）”。Porter 博士因为其在词干提取和信息检索中的成就获得了2000年的托尼·肯特思奖。很多实现基于Porter词干提取的算法而写出来，并免费分发。然而，大部分这些实现都包含着一些敏感的缺陷。所以，这些词干提取器没有很好地适应算法的潜能。为了消除误差的来源，Martin Porter在2000年发布了一个基于该算法的官方版本的免费应用软件。他在自己的工作上进行延伸，建立了一个Snowball算法（英语：Snowball_programming_language），是编写词干提取算法的框架，并实现了一个改良的英文词干提取器可以同时提取一些其他语言。存在着几种的词干提取的算法，它们在性能和准确率还有对词干提取中遇到的问题的解决上有所不同。一个简单的词干提取器从查找表中查找词尾变化。这种方法的优势是简单、速度快并容易控制异常情况。但它的缺点是所有的词尾变化的形式必须明确地包含在查询表中：一个新的或者是陌生的词是没办法控制的，即使是具有完整的规则（如iPads ~ iPad），并且表会变得非常大。对于具有简单形态的语言，像英文，表的大小比较适中，但对于变化较大语言，如土耳其语，对于每个词根都可能有几百个潜在的变化形式。 一个查找算法初步词性标注来避免过度词干化.。查询表在一个词干提取器中的使用通常会产生半自动。例如，如果单词是“run”,那么算法会自动生成形式如“running”，“runs”，“runned”和“runly”。最后两种形式是不正确的，它们也不大可能会在正常的英语文本中出现。后缀去除算法不依赖于包含词形变换和词根的查询表。取而代之的是一个包含规则的具有代表性的小列表提供了相应的方法，通过给定的单词的形式去查找它的词根形式。如，其中的一些规则包括：后缀去除算法相对于一般的蛮力算法能够得到更为简单的维护，假设维护人员充分掌握语言学跟形态学方面的知识并且编写后缀去除规则。在解决一些特殊的关系（如“ran”和“run”）上，后缀去除算法被认为是粗糙的并且性能很差。后缀去除算法的解决方案在那些具有大众化词缀但有包含异常的词性上受到了限制。然而,这是一个问题,因为并非所有的词类都有这样一个好制定的规则集。Lemmatisation试图解决这个问题。一种更加复杂的确定一个词汇停顿词的方法是lemmatization。这种处理方式包括首先确定词汇的发音部分，接着，根据发音的部分确定词汇的根。 。停顿词规则随着单词的发声部分的改变而改变。这种处理方式与其获得的正确的词汇目录有非常高的联系。由于在规范化方法上有一些重叠，确定错误的目录或者不能够找到正确的目录限制了这方法对suffix stipping 算法的附加好处。基本思想是，如果我们更够从词汇的停顿词中获取更多的信息，那么，我们更够更加准确的使用规范化方法。随机算法使用概率方法确定一个词的词根。随机算法在一张词根表上训练有影响的词根形式从而开发出词根可能性模型。这种模型是典型的复杂语言规则，自然相似性等的表达形式。停顿词表现为输入有影响的已经经过训练的词根，根据规则，使用模型产生词根形式。有些lemmatisatin算法是统计算法。给予一个词汇，也许属于多个词汇的发音部分，对每个部分赋予一个概率值，这需要考虑词汇环境，也就是上下文，没有上下文关系的语法不需要考虑附加信息。在有些例子里，在赋予各个发声部分一个概率后，概率最大的部分被选中，最合适的规范化方法也被选中用于处理输入的词汇，以产生规范化的词根。这种算法使用停顿词数据库（比如，一个包含停顿词的文档）。这些停顿词，如先前所述，是不需要合法的词汇的。为了停顿一个词汇，算法试图将这些停顿词与数据库中的停顿词匹配，使用各种各样的约束，如与候选停顿词的相关性长度（如，be的缩写，是以下这些词如be，been，being的词干，将不会被考虑为beside的词干）。一些词干提取技术利用一个词的语境来提取正确的词干。混合方法同时使用上述的方法中的两种或更多种。一个简单的例子是一个后缀树算法首先会强制咨询查找表。然而，查找 表不是试图存储给定的语言中词与词之间所有的的关系，而是保持小规模，仅用于存储微量的“频繁使用的例外词汇”， 如“ran=>run”。如果这个词不在例外列表中，应用后缀去除算法或lemmatisation算法的输出结果。在语言学，词缀一词是指前缀或后缀。除了处理后缀，有几种方法也尝试移除前缀。例如，给一个词 indefinitely, 首先确定开头的“in”是前缀是可以被移除的。很多前面的提到的方法都可以适用，但是都属于词缀提取。欧洲语言的几种词缀提取算法可以在这里找到。由于之前的学术工作都是集中于英语语言，许多其他的语言还没有被深入研究。 希伯来语和阿拉伯语仍然被认为在词根上很难研究的语言。语言停顿词是相当琐碎的（除了一些偶尔的例子，如dries是动词dry的第三人称单数现在时，axes是axe的复数形式），但停顿词在语态，正词法，单词编码上变得越来越难。希伯来语甚至变更更加复杂。在接受查询时，多语言停顿词应用在两个或者多个语言相似度语态规则上而不是在单一的语言上。在商业系统中存在这多语言停顿词有两种测量误差所产生的算法，overstemming和understemming。 。 overstemming 是两个不同的且有影响的词在相同的词根上停止，但不应当有假阳性的错误。understemming是两个不同且有影响的词在相同的词根上停止，但不应当有假阴性。词干算法试图以减少每种类型的错误，虽然减少一类，可以导致增加。停顿词是一种把具有相同意义的词汇组的词汇分组的估计方法。例如，一个文档提及"daffodils"很有可能与一个文档提及"daffodil"相关(没有加s).但是在有些例子里，具有相同词根形态也会有截然不同的意义，也就是说，这两个意义很不相同。当用户查询marketing，他会对包含markets的文档非常不满意。停顿词在检索中是一个非常普遍的元素，如在网页搜索引擎中。但在英语搜索中，很快发现，停顿词的有效性是有限的。然而，这使得早期的信息检索研究者认为大体上停顿词是没有关联的。一种替代的方式是，基于n-grams方法而不是基于停顿词的方法。当然，最佳的研究表明，停顿词在其他语言的搜索中收到的效果比在英语中要好停顿词在领域分析中确定领域词汇有应用。从上世纪80年代开始，很多商业公司已经开始使用停顿词了，现在已经在很多预言中开发了算法和词汇停顿词 雪球般的停顿词已经开始和各种各样的 的商业词汇停顿词作比较了。 google search在2003年采用停顿词。在这之前，搜索fish将不会出现fishing。另外的搜索算法也使用各种各样的的停顿词。用简单的子串搜索也能在搜索fishing时候搜到fish，但不能搜到fishes