分词算法的原理及简单实现(二)

本篇文章将主要介绍在《分词算法的原理及简单实现(一)》中提及的分词相关的各种算法。包括但不仅限于结巴分词。

注:下文中提及的jieba分词源码指的是 v0.39 版本的代码。

前缀词典

jieba分词中,构建前缀词典相关的源码:

def gen_pfdict(self, f):
    lfreq = {}
    ltotal = 0
    f_name = f.name
    for lineno, line in enumerate(f, 1):
        try:
            line = line.strip().decode('utf-8')
            word, freq = line.split(' ')[:2]
            freq = int(freq)
            lfreq[word] = freq
            ltotal += freq
            for ch in range(len(word)):
                wfrag = word[:ch + 1]
                if wfrag not in lfreq:
                    lfreq[wfrag] = 0
        except ValueError:
            raise ValueError(
                'invalid dictionary entry in %s at Line %s: %s' % (f_name, lineno, line))
    f.close()
    return lfreq, ltotal

看着感觉简单粗暴,据测试在 python 中效率比Trie树要好一点?这个有待验证,应该跟语言特性,词典中词汇数量,词汇长短,单字种类有关。

Trie树

jieba 分词中原来的Trie树生成算法,已被上面的方法取代。

def gen_trie(f_name):
    lfreq = {}
    trie = {}
    ltotal = 0.0
    with open(f_name, 'rb') as f:
        lineno = 0
        for line in f.read().rstrip().decode('utf-8').split('\n'):
            lineno += 1
            try:
                word,freq,_ = line.split(' ')
                freq = float(freq)
                lfreq[word] = freq
                ltotal += freq
                p = trie
                for c in word:
                    if c not in p:
                        p[c] ={}
                    p = p[c]
                p['']='' #ending flag
            except ValueError as e:
                logger.debug('%s at line %s %s' % (f_name,  lineno, line))
                raise e
    return trie, lfreq, ltotal

字典树这个数据结构的用途还是很多的,尤其在搜索领域,下面是一些相关的例题:

有向无环图

有向无环图的生成算法,其中 FREQ 即为上面提到的前缀词典。

def get_DAG(self, sentence):
    self.check_initialized()
    DAG = {}
    N = len(sentence)
    for k in range(N):
        tmplist = []
        i = k
        frag = sentence[k]
        while i < N and frag in self.FREQ:
            # 如果词频大于0,就将这个位置i追加到以k为key的一个列表中
            if self.FREQ[frag]:
                tmplist.append(i)
            # 如果词频等于0,则表明前缀词典存在这个前缀,但是统计词典并没有这个词,继续循环
            i += 1
            frag = sentence[k:i + 1]
        if not tmplist:
            tmplist.append(k)
        DAG[k] = tmplist
    return DAG

查找最大概率路径

def calc(self, sentence, DAG, route):
    N = len(sentence)
    route[N] = (0, 0)
    logtotal = log(self.total)
    for idx in range(N - 1, -1, -1):
        route[idx] = max((log(self.FREQ.get(sentence[idx:x + 1]) or 1) -
                          logtotal + route[x + 1][0], x) for x in DAG[idx])


def __cut_DAG_NO_HMM(self, sentence):
    re_eng = re.compile('[a-zA-Z0-9]', re.U)

    DAG = self.get_DAG(sentence)
    route = {}
    self.calc(sentence, DAG, route)
    x = 0
    N = len(sentence)
    buf = ''
    while x < N:
        y = route[x][1] + 1
        l_word = sentence[x:y]
        if re_eng.match(l_word) and len(l_word) == 1:
            buf += l_word
            x = y
        else:
            if buf:
                yield buf
                buf = ''
            yield l_word
            x = y
    if buf:
        yield buf
        buf = ''

设想一个场景,用户在不断的输入,每当用户输入一个字符之后,需要对用户的完整输入进行一遍分词。如果只是单纯的调用分词接口,那么每输入一个字符就要进行一次分词运算。如果了解了“最大概率路径”的算法,就会发现,其实每输入一个字符只要在原有的分词算法上进行增量的计算即可。当然,这么做在减小计算量的同时,会增加一点内存占用。所以在实际应用中是否采用这样的方式,有待考量吧。

从上面的算法中可以看出,每当用户输入的查询词新增一个字符时,实际上是在有向无环图后面增加一个节点,根据构建的词典判断从这个节点出发的有向边。再利用动态规划刷新一下最大概率路径即可。

HMM

关于HMM的内容在文章《HMM的知识点》中进行详细的介绍。

参考资料

发表评论

您的电子邮箱地址不会被公开。