基于Trie 树实现简单的中文分词

致Great

发布于 2022-05-13 19:05:22

7461

发布于 2022-05-13 19:05:22

文章被收录于专栏：程序生活程序生活

中文分词简介

中文分词是中文自然语言处理的基础，中文分词的正确率如何直接影响后续的词性标注（也有些词性标注算法不需要事先分词，但标注效果往往比先分词后标注差），实体识别、句法分析、语义分析。常用的分词方法主要有依赖词典的机械分词和序列标注方法。

分词算法分类

中文分词算法大概分为三大类：

第一类是基于字符串匹配，即扫描字符串，如果发现字符串的子串和词典中的词相同，就算匹配，比如机械分词方法。这类分词通常会加入一些启发式规则，比如“正向/反向最大匹配”，“长词优先”等。
第二类是基于统计以及机器学习的分词方法，它们基于人工标注的词性和统计特征，对中文进行建模，即根据观测到的数据( 标注好的语料) 对模型参数进行训练，在分词阶段再通过模型计算各种分词出现的概率，将概率最大的分词结果作为最终结果。常见的序列标注模型有HMM和CRF。这类分词算法能很好处理歧义和未登录词问题，效果比前一类效果好，但是需要大量的人工标注数据，以及较慢的分词速度。
第三类是通过让计算机模拟人对句子的理解，达到识别词的效果，目前基于深度学习以及目前比较火热的预训练模型效果非常好，能够识别汉语复杂的语义。

机械分词

机械分词方法又叫基于字符串匹配的分词方法，它是按照一定的策略将待分析的字符串与一个“充分大的”机器词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功(识别出一个词)。这是最简单的分词方法，但非常高效和常见。

机械分词比较适用的场景是在某个小领域或者任务内，并且手中有一些积累的词库，可以快速构建一个简单的分词算法。

在自然语言处理相关的书籍资料中常提到的机械分词方法主要有正向最大匹配、正向最小匹配、逆向最大匹配、逆向最小匹配四种，但是实际工程中用的比较多的还是正向最大匹配和逆向最大匹配。

假设我们已经有切词词典dict，要切词的句子为sentence；为便于理解，后面介绍两种算法均以“南京市长江大桥”为例说明算法。

正向最大匹配算法

正向最大匹配算法根据经验设定切词最大长度max_len（中文词语多为二字、三字、四字词，少数五字短语，比如“坐山观虎斗”，因此max_len设为4或5较合适），每次扫描的时候寻找当前开始的这个长度的词来和字典中的词匹配，如果没有找到，就缩短长度继续寻找，直到找到或者成为单字具体分词算法如下：

custom_dict={"南京","南京市","市长","长江","大桥","江大桥",}
input_sentence="南京市长江大桥"
max_word_len=0
for word in custom_dict:
    if len(word)>max_word_len:
        max_word_len=len(word)

if len(input_sentence)<max_word_len:
    max_word_len=len(input_sentence)

start=0
seg_results=[]
while start<len(input_sentence):
    temp_len=max_word_len
    if len(input_sentence)-start<max_word_len:
        temp_len=len(input_sentence)-start
    while temp_len>0:
        sub_sentence=input_sentence[start:start+temp_len]
        if sub_sentence in custom_dict:
            seg_results.append(sub_sentence)
            start+=temp_len
            break
        else:
            temp_len-=1
    # 没有子串匹配，则单独成词
    if temp_len==0:
        seg_results.append(input_sentence[start:start+1])
        start+=1
print(seg_results)

逆向最大匹配算法

逆向最大匹配算法和正向最大匹配算法不同的是，切分汉字时，逆向最大匹配算法不是按照汉字顺序从左到右依次抽取子串，而是从汉字尾端开始抽取，算法代码如下：

custom_dict={"南京","南京市","市长","长江","大桥","江大桥"}
input_sentence="南京市长江大桥"
max_word_len=0
for word in custom_dict:
    if len(word)>max_word_len:
        max_word_len=len(word)

if len(input_sentence)<max_word_len:
    max_word_len=len(input_sentence)

end=len(input_sentence)
seg_results=[]
while end>0:
    temp_len=max_word_len
    if end<max_word_len:
        temp_len=end
    while temp_len>0:
        sub_sentence=input_sentence[end-temp_len:end]
        if sub_sentence in custom_dict:
            seg_results.append(sub_sentence)
            end-=temp_len
            break
        else:
            temp_len-=1
    # 没有子串匹配，则单独成词
    if temp_len==0:
        sub_sentence=input_sentence[end-1:end]
        seg_results.append(sub_sentence)
        end-=1
print(seg_results)

基于Trie树实现中文分词

词表的内存表示：很显然，匹配过程中是需要找词前缀的，因此我们不能将词表简单的存储为Hash结构。在这里我们考虑一种高效的字符串前缀处理结构——Trie树。这种结构使得查找每一个词的时间复杂度为O(word.length) ，而且可以很方便的判断是否匹配成功或匹配到了字符串的前缀。 Trie Tree分词原理： (1) 从根结点开始一次搜索，比如搜索【北京】； (2) 取得要查找关键词的第一个字符【北】，并根据该字符选择对应的子树并转到该子树继续进行检索； (3) 在相应的子树上，取得要查找关键词的第二个字符【京】,并进一步选择对应的子树进行检索。 (4) 迭代过程…… (5) 在直到判断树节点的isEnd节点为true则查找结束（最小匹配原则），然后发现【京】isEnd=true，则结束查找。

图片来源：https://www.jianshu.com/p/1d9e7b8663c1

具体实现代码如下： Trie数定义如下：

class TrieNode(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = {}
        self.is_word = False


class Trie(object):
    """
    trie树
    """

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: void
        """
        node = self.root
        for chars in word:  # 遍历词语中的每个字符
            child = node.data.get(chars)  # 获取该字符的子节点，
            if not child:  # 如果该字符不存在于树中
                node.data[chars] = TrieNode()  # 则创建该字符节点
            node = node.data[chars]  # 节点为当前该字符节点
        node.is_word = True

    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        node = self.root
        for chars in word:
            node = node.data.get(chars)
            if not node:
                return False
        return node.is_word  # 判断单词是否是完整的存在在trie树中

    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """
        node = self.root
        for chars in prefix:
            node = node.data.get(chars)
            if not node:
                return False
        return True

    def get_start(self, prefix):
        """
          Returns words started with prefix
          返回以prefix开头的所有words
          如果prefix是一个word，那么直接返回该prefix
          :param prefix:
          :return: words (list)
        """

        def get_key(pre, pre_node):
            word_list = []
            if pre_node.is_word:
                word_list.append(pre)
            for x in pre_node.data.keys():
                word_list.extend(get_key(pre + str(x), pre_node.data.get(x)))
            return word_list

        words = []
        if not self.startsWith(prefix):
            return words
        if self.search(prefix):
            words.append(prefix)
            return words
        node = self.root
        for chars in prefix:
            node = node.data.get(chars)
        return get_key(prefix, node)

基于Trie树分词流程如下：

from trie import Trie
import time


class TrieTokenizer(Trie):
    """
    基于字典树(Trie Tree)的中文分词算法
    """

    def __init__(self, dict_path):
        """

        :param dict_path:字典文件路径
        """
        super(TrieTokenizer, self).__init__()
        self.dict_path = dict_path
        self.create_trie_tree()
        self.punctuations = """！？｡＂＃＄％＆＇：（）＊＋，－／：；＜＝＞＠［＼］＾＿｀｛｜｝～｟｠｢｣､、〃》「」『』【】〔〕〖〗〘〙〚〛〜〝〞〟〰〾〿–—‘’‛“”„‟…‧﹏."""

    def load_dict(self):
        """
        加载字典文件
        词典文件内容如下，每行是一个词：
                    AA制
                    ABC
                    ABS
                    AB制
                    AB角
        :return:
        """
        words = []
        with open(self.dict_path, mode="r", encoding="utf-8") as file:
            for line in file:
                words.append(line.strip().encode('utf-8').decode('utf-8-sig'))
        return words

    def create_trie_tree(self):
        """
        遍历词典，创建字典树
        :return:
        """
        words = self.load_dict()
        for word in words:
            self.insert(word)

    def mine_tree(self, tree, sentence, trace_index):
        """
        从句子第trace_index个字符开始遍历查找词语，返回词语占位个数
        :param tree:
        :param sentence:
        :param trace_index:
        :return:
        """
        if trace_index <= (len(sentence) - 1):
            if sentence[trace_index] in tree.data:
                trace_index = trace_index + 1
                trace_index = self.mine_tree(tree.data[sentence[trace_index - 1]], sentence, trace_index)
        return trace_index

    def tokenize(self, sentence):
        tokens = []
        sentence_len = len(sentence)
        while sentence_len != 0:
            trace_index = 0  # 从句子第一个字符开始遍历
            trace_index = self.mine_tree(self.root, sentence, trace_index)

            if trace_index == 0:  # 在字典树中没有找到以sentence[0]开头的词语
                tokens.append(sentence[0:1])  # 当前字符作为分词结果
                sentence = sentence[1:len(sentence)]  # 重新遍历sentence
                sentence_len = len(sentence)
            else:  # 在字典树中找到了以sentence[0]开头的词语，并且trace_index为词语的结束索引
                tokens.append(sentence[0:trace_index])  # 命中词语作为分词结果
                sentence = sentence[trace_index:len(sentence)]  #
                sentence_len = len(sentence)

        return tokens

    def combine(self, token_list):
        """
        TODO:对结果后处理：标点符号/空格/停用词
        :param token_list:
        :return:
        """
        flag = 0
        output = []
        temp = []
        for i in token_list:
            if len(i) != 1:  # 当前词语长度不为1
                if flag == 0:
                    output.append(i[::])
                else:
                    # ['该', '方法']
                    # temp=['该']
                    output.append("".join(temp))
                    output.append(i[::])
                    temp = []
                    flag = 0
            else:
                if flag == 0:
                    temp.append(i)
                    flag = 1
                else:
                    temp.append(i)
        return output


if __name__ == '__main__':
    now = lambda: time.time()
    trie_cws = TrieTokenizer('data/32w_dic.txt')
    start = now()
    print(f"Build Token Tree Time : {now() - start}")

    sentence = '该方法的主要思想：词是稳定的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻出现的概率或频率能较好地反映成词的可信度。' \
               '可以对训练文本中相邻出现的各个字的组合的频度进行统计，计算它们之间的互现信息。互现信息体现了汉字之间结合关系的紧密程度。当紧密程 度高于某一个阈值时，' \
               '便可以认为此字组可能构成了一个词。该方法又称为无字典分词。'
    tokens = trie_cws.tokenize(sentence)
    combine_tokens = trie_cws.combine(tokens)
    end = now()
    print(tokens)
    print(combine_tokens)
    print(f"tokenize Token Tree Time : {end - start}")

分词效果如下：

Build Token Tree Time : 0.0
['该', '方法', '的', '主要', '思想', '：', '词', '是', '稳定', '的', '组合', '，', '因此', '在上', '下文', '中', '，', '相', '邻', '的', '字', '同时', '出现', '的', '次数', '越', '多', '，', '就', '越', '有', '可能', '构成', '一个', '词', '。', '因此', '字', '与', '字', '相', '邻', '出现', '的', '概率', '或', '频率', '能', '较好', '地', '反映', '成', '词', '的', '可信度', '。', '可以', '对', '训练', '文本', '中', '相', '邻', '出现', '的', '各个', '字', '的', '组合', '的', '频度', '进行', '统计', '，', '计算', '它们', '之', '间', '的', '互', '现', '信息', '。', '互', '现', '信息', '体现', '了', '汉字', '之', '间', '结合', '关系', '的', '紧密', '程度', '。', '当紧', '密', '程', ' ', '度', '高', '于', '某', '一个', '阈', '值', '时', '，', '便', '可以', '认为', '此', '字', '组', '可能', '构成', '了', '一个', '词', '。', '该', '方法', '又', '称', '为', '无字', '典', '分', '词', '。']
['该', '方法', '的', '主要', '思想', '：词是', '稳定', '的', '组合', '，', '因此', '在上', '下文', '中，相邻的字', '同时', '出现', '的', '次数', '越多，就越有', '可能', '构成', '一个', '词。', '因此', '字与字相邻', '出现', '的', '概率', '或', '频率', '能', '较好', '地', '反映', '成词的', '可信度', '。', '可以', '对', '训练', '文本', '中相邻', '出现', '的', '各个', '字的', '组合', '的', '频度', '进行', '统计', '，', '计算', '它们', '之间的互现', '信息', '。互现', '信息', '体现', '了', '汉字', '之间', '结合', '关系', '的', '紧密', '程度', '。', '当紧', '密程 度高于某', '一个', '阈值时，便', '可以', '认为', '此字组', '可能', '构成', '了', '一个', '词。该', '方法', '又称为', '无字']
tokenize Token Tree Time : 0.0005023479461669922