词典分词

自然语言处理 , 评论

词典分词

词典分词是基于规则的分词手段
给定一部词典,词典分词就是一个确定的查词和输出的规则系统.

什么是词

词的定义

在语言学上,词语的定义是具备独立意义的最小单位. 但是对于一些词,比如”吃饭”,有些人会认为”吃饭”是一个词, 有些人会认为,应该拆分为”吃”,”饭”;由于没有统一标准,所以语言学上的定义没有实施效果.

在中文分词当中,词的定义就是字典中的字符串;因此不在字典中的字就不属于词了.而词是不断变化的,数量也是无穷无尽的.

齐夫定律

齐夫定律: 一个单词的词频和它的词频排名成反比.
这意味着, 排面越靠后的单词, 它的词频会越来越接近 0.

所以词典把词频较高的部分收录,就能解决大部分的分词了.

词典

一般一部分词词典的其中一条数据有这样的格式

1
2
<!-- 单词 词性 词频 -->
希望 v 386 n 96

切分算法

  1. 完全切分
    完全切分就是将一段文本中的所有单词,中所有可能的词都切分开来, 具体的做法就是双循环遍历所有可能的词.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public static List<String> segmentFully(String text, Map<String, CoreDictionary.Attribute> dictionary){
        List<String> wordList = new LinkedList<String>();
        for (int i = 0; i < text.length(); ++i)
        {
            for (int j = i + 1; j <= text.length(); ++j)
            {
                String word = text.substring(i, j);
                if (dictionary.containsKey(word))
                {
                    wordList.add(word);
                }
            }
        }
        return wordList;
    }

  2. 正向最长匹配
    在完全切分的基础上, 优化为优先输出更长的单词, 正向最长指的是下标的扫描是从前往后, 二层循环中, 循环一次最多保存一个最长词.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public static List<String> segmentForwardLongest(String text, Map<String, CoreDictionary.Attribute> dictionary){
         List<String> wordList = new LinkedList<String>();
         for (int i = 0; i < text.length(); )
         {
             String longestWord = text.substring(i, i + 1);
             for (int j = i + 1; j <= text.length(); ++j)
             {
                 String word = text.substring(i, j);
                 if (dictionary.containsKey(word))
                 {
                     if (word.length() > longestWord.length())
                     {
                         longestWord = word;
                     }
                 }
             }
             wordList.add(longestWord);
             i += longestWord.length();
         }
         return wordList;
    }

  3. 逆向最长匹配
    与正向最长匹配的区别是下标扫描从后往前,正向是从短的单词扫描到长的单词,逆向是从最长的词扫描到最短的词

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    public static List<String> segmentBackwardLongest(String text, Map<String, CoreDictionary.Attribute> dictionary){
         List<String> wordList = new LinkedList<String>();
         for (int i = text.length() - 1; i >= 0; )
         {
             String longestWord = text.substring(i, i + 1);
             for (int j = 0; j <= i; ++j)
             {
                 String word = text.substring(j, i + 1);
                 if (dictionary.containsKey(word))
                 {
                     if (word.length() > longestWord.length())
                     {
                         longestWord = word;
                         break;
                     }
                 }
             }
             wordList.add(0, longestWord);
             i -= longestWord.length();
         }
         return wordList;
    }

  4. 双向最长匹配
    双向最长匹配就是将正向最长和逆向最长结合起来
    同时执行正向和逆向
    返回词数少的那个,
    或者返回单个字少的那个

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    public static List<String> segmentBidirectional(String text, Map<String, CoreDictionary.Attribute> dictionary){
         List<String> forwardLongest = segmentForwardLongest(text, dictionary);
         List<String> backwardLongest = segmentBackwardLongest(text, dictionary);
         if (forwardLongest.size() < backwardLongest.size())
             return forwardLongest;
         else if (forwardLongest.size() > backwardLongest.size())
             return backwardLongest;
         else{
             if (countSingleChar(forwardLongest) < countSingleChar(backwardLongest))
                 return forwardLongest;
             else
                 return backwardLongest;
         }
    }


    /**
      * 统计分词结果中的单字数量
      */
     public static int countSingleChar(List<String> wordList){
         int size = 0;
         for (String word : wordList){
             if (word.length() == 1)
                 ++size;
         }
         return size;
     }

字典树

字典树就是关于”字典”的一棵树,字典树也叫Trie树, 它是用于字典的一种存储方式,是一种数据结构
这个词典中的每个”单词”从根节点出发一直到某一个目标节点的路径, 路径中每条边的字连起来的就是一个词, 词的最后一个字被称为标记节点, 标记节点不一定是叶子节点
拥有相同前缀的词,会排列在一颗子树上 只是深度不同

依靠字典树 查词的方式就好像在使用字典的拼音查词

yanchengjielove and share

Anything can go right will go right