这学期数据结构课程设计需要实现一个基于 Nonebot + CoolQ 的群聊机器人,核心功能是垃圾信息识别。

参考了知乎 dalao 的文章,我打算先把以前水竞赛时学过的 AC 自动机算法用 Python 复现一遍。几个月没刷题,差不多忘光光了,只记得 fail 指针指来指去 233。

这里安利一位良心 UP 主,他的 KMP、AC 自动机、后缀树讲解视频内容细致通俗易懂。附上链接

二刷视频讲解很快又通透了,这玩意和 KMP 简直异曲同工之妙。

刷算法和数据结构用 C + STL 是王道,Python 用得好难受啊 == (小声 BB)

今天遇到了一个关于连等赋值顺序的问题:

u = trie[u].child[id] = tot

这个语句用 C 来执行,自然是从右向左赋值,而 Python 相反,此处相当于:

u = tot
trie[u].child[id] = tot

详细解释见:Python 连续赋值的两个要点

废话不多说,代码如下:

class node:

    def __init__(self):
        self.fail = 0
        self.child = [0 for i in range(26)]
        self.exist = []


tot = 0
trie = [node() for i in range(1000)]


def insert(str):
    global tot
    u = 0
    for c in str:
        id = ord(c) - ord('a')
        if trie[u].child[id] == 0:
            tot += 1
            trie[u].child[id] = tot
        u = trie[u].child[id]
    trie[u].exist.append(len(str))


def build():
    q = []
    for i in range(26):
        if trie[0].child[i]:
            q.append(trie[0].child[i])
    while q:
        u = q[0]
        q.pop(0)
        for i in range(26):
            if trie[u].child[i]:
                trie[trie[u].child[i]].fail = trie[trie[u].fail].child[i]
                q.append(trie[u].child[i])
            else:
                trie[u].child[i] = trie[trie[u].fail].child[i]


def query(str):
    u = 0
    res = []
    for i in range(len(str)):
        c = str[i]
        j = u = trie[u].child[ord(c) - ord('a')]
        while j and trie[j].exist:
            for k in trie[j].exist:
                res.append((i - k + 1, str[i - k + 1: i + 1]))
            j = trie[j].fail
    print(res)

我们用一组样例测试一下:

insert('he')
insert('she')
insert('his')
insert('hers')
build()
query('ahishers')

输出结果:

[(1, 'his'), (3, 'she'), (4, 'he'), (4, 'hers')]

但是现在只能对纯 ASCII 字符串进行模式匹配,无法处理汉字。

s = '山东大学威海校区坐落于美丽滨城威海市。'
for c in s:
    print(c, ord(c))

输出结果:

山 23665
东 19996
大 22823
学 23398
威 23041
海 28023
校 26657
区 21306
坐 22352
落 33853
于 20110
美 32654
丽 20029
滨 28392
城 22478
威 23041
海 28023
市 24066
。 12290

考虑把主串和所有模式串中涉及的字符 Unicode 离散化,再构造 Trie,由此得到了以下版本:

class node:

    def __init__(self):
        self.fail = 0
        self.child = [0 for i in range(1000)]
        self.exist = []


dict = {}
tot = 0
trie = [node() for i in range(1000)]


def insert(str):
    global tot
    u = 0
    for c in str:
        id = dict[ord(c)]
        if trie[u].child[id] == 0:
            tot += 1
            trie[u].child[id] = tot
        u = trie[u].child[id]
    trie[u].exist.append(len(str))


def build():
    q = []
    for i in range(1000):
        if trie[0].child[i]:
            q.append(trie[0].child[i])
    while q:
        u = q[0]
        q.pop(0)
        for i in range(1000):
            if trie[u].child[i]:
                trie[trie[u].child[i]].fail = trie[trie[u].fail].child[i]
                q.append(trie[u].child[i])
            else:
                trie[u].child[i] = trie[trie[u].fail].child[i]


def query(str):
    u = 0
    res = []
    for i in range(len(str)):
        if dict.get(ord(str[i])) == None:
            continue
        id = dict[ord(str[i])]
        j = u = trie[u].child[id]
        while j and trie[j].exist:
            for k in trie[j].exist:
                res.append((i - k + 1, str[i - k + 1: i + 1]))
            j = trie[j].fail
    print(res)


if __name__ == '__main__':
    patterns = ['中国', '山东省', '威海市', '山东大学', '威海校区']
    s = set()
    for p in patterns:
        for c in p:
            s.add(ord(c))
    s = sorted(s)
    for i in range(len(s)):
        dict[s[i]] = i + 1
    for p in patterns:
        insert(p)
    build()
    text = '山东大学威海校区坐落于美丽滨城威海市。'
    query(text)

输出结果:

[(0, '山东大学'), (4, '威海校区'), (15, '威海市')]

总算把兼容中文的多模式匹配搞定了,但总感觉效率不高 ==

Python 库 ahocorasick 封装了 AC 自动机,简单易用,而且解决了 UTF-8 字符编码问题。

import ahocorasick


def build(patterns):
    trie = ahocorasick.Automaton()
    for index, word in enumerate(patterns):
        trie.add_word(word, (index, word))
    trie.make_automaton()
    return trie


if __name__ == '__main__':
    patterns = ['中国', '山东省', '威海市', '山东大学', '威海校区']
    text = '山东大学威海校区坐落于美丽滨城威海市。'
    trie = build(patterns)
    for each in trie.iter(text):
        print(each)

输出结果:

(3, (3, '山东大学'))
(7, (4, '威海校区'))
(17, (2, '威海市'))
最后修改:2020 年 05 月 01 日 01 : 06 AM
如果觉得我的文章对你有用,请随意赞赏~