分词器(Tokenizer)原理

南风 2020年10月19日 75次浏览

一、分词器是什么?

 分词器是利用词库将输入的短语或词句分成一堆词集合的工具,常在搜索引擎和自然语言处理中使用到,本人就在ES搜索引擎中用到过自己定制化的IK分词器以及在文本指定类型短语关键词提取(BI-LSTM + CRF++)中用到过jieba分词器(中文分词器)和IK分词器(英文分词器)进行文章分词及停用词过滤、指定词标注等。
目前市面比较流行的分词器:

  • IK分词器
  • ansj分词器
  • jieba分词器
  • hanNLP
  • ictclas分词器(中科院)

二、分词器结构(IK分词器)

  • 1、词典
    IK分词器提供了三类词表,分表是主词表、量词表、停用词表,Dictionary为字典管理类中,分别加载了这个词典到内存结构中。具体的字典代码,位于org.wltea.analyzer.dic.DictSegment。 这个类实现了一个分词器的一个核心数据结构,即Tire Tree。Tire Tree(字典树)是一种结构相当简单的树型结构,用于构建词典,
    字典树结构.png

  • 2、词语切分
    IK分词器,基本可分为两种模式,一种为smart模式,一种为非smart模式。如以下实例:
    原文:中国人民共和国国旗
    smart模式:中国 | 人民 | 共和国 | 国旗
    非smart模式:中国 | 中国人 | 中国人民 | 共和国 | 国旗 | 共和国国旗

可见非smart模式所做的就是将能够分出来的词全部输出;smart模式下,IK分词器则会根据内在方法输出一个认为最合理的分词结果,这就涉及到了歧义判断。

  • 3、歧义分析
    IKAnalyzer的切分方式是细粒度切分,当不需要智能处理时,其就把切出的所有词输出,但若启动了智能处理,那么接下来就是要进行消歧工作。细粒度切出的词比较杂,但是经过智能处理后,其看上去就像是采用MM算法或者RMM算法切分出。
    消歧核心算法:

    • 1)比较有效文本长度
    • 2)比较词元个数,越少越好
    • 3)路径跨度越大越好
    • 4)根据统计学结论,逆向切分概率高于正向切分,因此位置越靠后的优先
    • 5)词长越平均越好
public int compareTo(LexemePath o) {  
        //比较有效文本长度  
        if(this.payloadLength > o.payloadLength){  
            return -1;  
        }else if(this.payloadLength < o.payloadLength){  
            return 1;  
        }else{  
            //比较词元个数,越少越好  
            if(this.size() < o.size()){  
                return -1;  
            }else if (this.size() > o.size()){  
                return 1;  
            }else{  
                //路径跨度越大越好  
                if(this.getPathLength() >  o.getPathLength()){  
                    return -1;  
                }else if(this.getPathLength() <  o.getPathLength()){  
                    return 1;  
                }else {  
                    //根据统计学结论,逆向切分概率高于正向切分,因此位置越靠后的优先  
                    if(this.pathEnd > o.pathEnd){  
                        return -1;  
                    }else if(pathEnd < o.pathEnd){  
                        return 1;  
                    }else{  
                        //词长越平均越好  
                        if(this.getXWeight() > o.getXWeight()){  
                            return -1;  
                        }else if(this.getXWeight() < o.getXWeight()){  
                            return 1;  
                        }else {  
                            //词元位置权重比较  
                            if(this.getPWeight() > o.getPWeight()){  
                                return -1;  
                            }else if(this.getPWeight() < o.getPWeight()){  
                                return 1;  
                            }  
                              
                        }  
                    }  
                }  
            }  
        }  
        return 0;  
    }  

三、分词器的核心算法

AC自动机(Aho-Corasick automaton)

AC自动机是一种常用的多模式匹配算法,基于字典树(trie树)的数据结构和KMP算法的失败指针的思想来实现,有不错的性能并且实现起来非常简单。

字典树(trie树)

如上图字典树结构,Trie树,是一种树形结构,是一种哈希树的变种。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

KMP算法

KMP算法指的是字符串模式匹配算法,问题是:在主串T中找到第一次出现完整子串P时的起始位置。该算法是三位大牛:D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的,以其名字首字母命名。


public static int KMP(String ts, String ps) {
    char[] t = ts.toCharArray();
    char[] p = ps.toCharArray();
    int i = 0; // 主串的位置
    int j = 0; // 模式串的位置
    int[] next = getNext(ps);

    while (i < t.length && j < p.length) {
       if (j == -1 || t[i] == p[j]) { // 当j为-1时,要移动的是i,当然j也要归0
           i++;
           j++;
       } else {
           // i不需要回溯了
           // i = i - j + 1;
           j = next[j]; // j回到指定位置
       }
    }

    if (j == p.length) {
       return i - j;
    } else {
       return -1;
    }
}

public static int[] getNext(String ps) {
    char[] p = ps.toCharArray();
    int[] next = new int[p.length];
    next[0] = -1;
    int j = 0;
    int k = -1;

    while (j < p.length - 1) {
       if (k == -1 || p[j] == p[k]) {
           if (p[++j] == p[++k]) { // 当两个字符相等时要跳过
              next[j] = next[k];
           } else {
              next[j] = k;
           }
       } else {
           k = next[k];
       }
    }
    return next;
}

好文:https://www.cnblogs.com/dusf/p/kmp.html

失败指针

可以简单理解为当一个trie树分支匹配结束后可以跳转到其它分支继续匹配的逻辑,类似于下图的红色标线指向。
失败指针.gif

(全文完)