从0到1的弹幕系统--敏感词过滤

语言: CN / TW / HK

弹幕系统必须要有个敏感词过滤或者内容风控,不然,你懂的。

所以,今天我们来实现弹幕的敏感词过滤。为什么不用风控呢,当然是为了节约成本了,接风控要钱的啊。当然如果有钱不在乎,可以接风控。这样安全等级更高,我们写这个弹幕系统是为了学习,所以就用敏感词过滤了,学习一下怎么过滤敏感词。

敏感词过滤其实就是一个撞库的过程,要想实现撞库,得要先建立起字典库,目前大部分的解决方案是使用Trie Tree来构建字典库。

Trie Tree

在计算机科学中,trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

一个保存了8个键的trie结构,"A", "to", "tea", "ted", "ten", "i", "in", "inn"

键不需要被显式地保存在节点中。图示中标注出完整的单词,只是为了演示trie的原理。

以上摘自维基百科

实现Trie Tree

结构定义

type Trie struct {
	Word rune
	IsEnd bool
	Child map[rune]*Trie
}
复制代码

Word表示节点的值,IsEnd表示是否叶子节点,Child表示子节点。

Word变量为什么使用rune类型,而不使用byte类型呢?

因为byte表示字节,但中、英文的字节数是不一样的,看下面的例子:

first := "社区"
fmt.Println([]byte(first)) // 输出结果[231 164 190 229 140 186],中文字符串每个占三个字节

second := "fisrt"
fmt.Println([]byte(second)) // 输出结果[102 105 115 114 116],每个英文字符占一个字节
复制代码

所以如果使用byte的话,我们需要区分中、英文,再看下面的例子:

first := "社区"
fmt.Println([]rune(first)) // 输出结果[31038 21306],每个中文字符串占一个标识符

second := "fisrt"
fmt.Println([]byte(second)) // 输出结果[102 105 115 114 116],每个英文字符占一个标识符
复制代码

官方对这俩种类型的说明:

// byte is an alias for uint8 and is equivalent to uint8 in all ways. It is
// used, by convention, to distinguish byte values from 8-bit unsigned
// integer values.
type byte = uint8

// rune is an alias for int32 and is equivalent to int32 in all ways. It is
// used, by convention, to distinguish character values from integer values.
type rune = int32
复制代码

在官方的tour中有一句话 rune表示unicode的码点,这样我们就不用区分中、英文了。

Trie的插入

将一个敏感词插入Trie时,需要先检索Trie,判断敏感词中的每个字符是否已存在于Trie中,如果已存在,则继续向下遍历Trie,如果不存在,则插入:

func (t *Trie) Insert(word string) {
	word = strings.TrimSpace(word)
	ptr := t
	for _, u := range word {
		_, ok := ptr.Child[u]
		if !ok {
			node := make(map[rune]*Trie)
			ptr.Child[u] = &Trie{Word: u, Child: node}
		}
		ptr = ptr.Child[u]
	}
	ptr.IsEnd = true
}
复制代码

我们来打印一下,看看是否正确插入:

func (t *Trie) Walk() {
	var walk func(string, *Trie)
	walk = func(pfx string, node *Trie) {
		if node == nil {
			return
		}

		if node.Word != 0 {
			pfx += string(node.Word)
		}

		if node.IsEnd {
			fmt.Println(string(pfx))
		}

		for _, v := range node.Child {
			walk(pfx, v)
		}
	}
	walk("", t)
}

func main() {
	trie := Trie{Word: 0, Child: make(map[rune]*Trie)}
	trie.Insert("大姨妈")
	trie.Insert("姨妈jin")
	trie.Insert("你大爷")
	trie.Insert("bitch")
	trie.Insert("bitches")
	trie.Walk()
}
复制代码

输出结果

$ go run trie.go
大姨妈
姨妈jin
你大爷
bitch
bitches
复制代码

可以看到,已经正确插入trie

Trie检索

输入一句话,检索出这句话中是否含有敏感词

func (t *Trie) Search(segment string) []string {
	segment = strings.TrimSpace(segment)
    ptr := t
	var matched []string
	item := ""
	for _, u := range segment {
		c, ok := ptr.Child[u]
		if !ok {
			ptr = t
			continue
		}
		item += string(c.Word)
	
		if c.IsEnd {
			matched = append(matched, item)
		}
		ptr = c
	}
	return matched
}
复制代码

再来测试一下,这次我们使用go test来测试:

import (
	"testing"
)

var trieTree = Trie{Word: 0, Child: make(map[rune]*Trie)}

func TestTrie(t1 *testing.T) {
	trieTree.Insert("你大爷")
	trieTree.Insert("大姨妈")
	trieTree.Insert("姨妈jin")
	trieTree.Insert("jin子")
	trieTree.Insert("大姨父")
	trieTree.Insert("妈了个吧")
	trieTree.Insert("狗日的")
	trieTree.Insert("去你吗的")
	trieTree.Insert("bitch")
	trieTree.Insert("bitches")

	//trieTree.Walk()

	matched := trieTree.Search("你大爷")
	t1.Log(matched)
	if len(matched) != 1 || matched[0] != "你大爷" {
		t1.Errorf("search: %s, expected: %v, actual: %v", "你大爷", []string{"你大爷"}, matched)
	}
}
复制代码

这个trie的结构应该是这样的

$ go test -v .
=== RUN   TestTrie
    trie_test.go:24: [你大爷]
--- PASS: TestTrie (0.00s)
PASS
ok      danmaku/utilities       0.012s
复制代码

加上-v参数,查看详细信息。

换句话测试,

matched := trieTree.Search("英文单词bitches意思是母狗")
t1.Log(matched)
if len(matched) != 2 || matched[0] != "bitch" || matched[1] != "bitches" {
    t1.Errorf("search: %s, expected: %v, actual: %v", "英文单词bitches意思是母狗", []string{"bitch", "bitches"}, matched)
}
复制代码
$ go test -v .
=== RUN   TestTrie
    trie_test.go:30: [bitch bitches]
--- PASS: TestTrie (0.00s)
PASS
ok      danmaku/utilities       0.012s
复制代码

继续下一个测试:

matched := trieTree.Search("狗日的大姨妈啊")
t1.Log(matched)
if len(matched) != 2 || matched[0] != "狗日的" || matched[1] != "大姨妈" {
    t1.Errorf("search: %s, expected: %v, actual: %v", "狗日的大姨妈啊", []string{"狗日的", "大姨妈"}, matched)
}
复制代码
$ go test -v .
=== RUN   TestTrie
    trie_test.go:36: [狗日的]
    trie_test.go:38: search: 狗日的大姨妈啊, expected: [狗日的 大姨妈], actual: [狗日的]
--- FAIL: TestTrie (0.00s)
FAIL
FAIL    danmaku/utilities       0.012s
FAIL
复制代码

测试不通过!只命中了"狗日的",后面的确没命中,这是为什么呢?

我们来分析一下:

segment[0] = "狗"
segment[1] = "日"
segment[2] = "的"
复制代码

到这里都正常,继续往下:

segment[3] = "大"
复制代码

这时遍历trie的游标应该在这里: 所以当命中一个敏感词后,我们需要重置游标:

				if c.IsEnd {
                    matched = append(matched, item)
                    // 重置检索起点
                    ptr = t
                    continue
                }
复制代码
$ go test -v .
=== RUN   TestTrie
    trie_test.go:36: [狗日的 狗日的大姨妈]
    trie_test.go:38: search: 狗日的大姨妈啊, expected: [狗日的 大姨妈], actual: [狗日的 狗日的大姨妈]
--- FAIL: TestTrie (0.00s)
FAIL
FAIL    danmaku/utilities       0.012s
FAIL
复制代码

还是不通过,我们期望的结果是[狗日的 大姨妈],但实际获得的结果是[狗日的 狗日的大姨妈],之前命中的狗日的被带入到后面的结果中了。所以我们不能光重置检索的游标,匹配的结果也要重置:

if c.IsEnd {
    matched = append(matched, item)
    if len(c.Child) == 0 {
        // 重置检索起点
        item = ""
        ptr = t
        continue
    }
}
复制代码
$ go test -v .
=== RUN   TestTrie
--- PASS: TestTrie (0.00s)
PASS
ok      danmaku/utilities       0.012s
复制代码

测试通过!

继续下一个用例

matched := trieTree.Search("我去你大爷的")
t1.Log(matched)
if len(matched) != 1 {
    t1.Errorf("search: %s, expected: %v, actual: %v", "我去你大爷的", []string{"你大爷"}, matched)
}
复制代码
$ go test -v .
=== RUN   TestTrie
    trie_test.go:42: []
    trie_test.go:44: search: 我去你大爷的, expected: [你大爷], actual: []
--- FAIL: TestTrie (0.00s)
FAIL
FAIL    danmaku/utilities       0.012s
FAIL
复制代码

失败了,并没有获得我们想要的结果。这是为什么呢?

我们来仔细分析一下,参数segment值为"我去你大爷",遍历segment

segment[0] = "我"
segment[1] = "去"
复制代码

这时,命中字典中的

继续向下:

segment[2] = "你"
segment[3] = "大"
复制代码

trie的游标往下,指向,然后,和segment[3]不匹配了。但是,segment[2]应该命中你大爷

这时,如果我们只重置trie的游标,因为segment的游标已经在3这里了,还是不行。所以我们不但要重置trie的游标,还要重置segment的游标。但是range只能从前往后遍历,不能回退,所以我们不能用range遍历,改用for。但是,for遍历字符串时,是按字节遍历的,所以需要将字符串转换成rune类型:

func (t *Trie) Search(segment string) []string {
	segment = strings.TrimSpace(segment)
	segmentRune := []rune(segment)
	var matched []string

	ptr := t
	item := ""
	index := 0
	for i:=0; i < len(segmentRune); i++ {
		c, ok := ptr.Child[segmentRune[i]]
		if !ok {
			i = index
			index++
			item = ""
			ptr = t
			continue
		}

		item += string(c.Word)

		// 例如:bitch和bitches
		// {Word: b, IsEnd: false, Child: {}}
		//                            ↓
		//   {Word: i, IsEnd: false, Child: {}}
		//                              ↓
		//     {Word: t, IsEnd: false, Child: {}}
		//                                ↓
		//       {Word: c, IsEnd: false, Child: {}}
		//                                  ↓
		//         {Word: h, IsEnd: true, Child: {}}
		//                                  ↓
		//         {Word: e, IsEnd: false, Child: {}}
		//                                    ↓
		//           {Word: s, IsEnd: true, Child: {}}
		if c.IsEnd {
			matched = append(matched, item)
			if len(c.Child) == 0 {
				item = ""
				ptr = t
				continue
			}
		}
		ptr = c
	}
	return matched
}
复制代码
$ go test -v .
=== RUN   TestTrie
    trie_test.go:42: [你大爷]
--- PASS: TestTrie (0.00s)
PASS
ok      danmaku/utilities       0.012s
复制代码

测试通过!

继续下一个测试用例(累,ε=(´ο`*)))唉~~)

matched := trieTree.Search("大姨妈jin子")
t1.Log(matched)
if len(matched) != 3 {
    t1.Errorf("search: %s, expected: %v, actual: %v", "大姨妈jin子", []string{"大姨妈", "姨妈jin", "jin子"}, matched)
}
复制代码
$ go test -v .
=== RUN   TestTrie
    trie_test.go:48: [大姨妈 jin子]
    trie_test.go:50: search: 大姨妈jin子, expected: [大姨妈 姨妈jin jin子], actual: [大姨妈 jin子]
--- FAIL: TestTrie (0.00s)
FAIL
FAIL    danmaku/utilities       0.012s
FAIL
复制代码

测试不通过,姨妈jin没命中。

再来分析一下:

segment[0] = "大"
segment[1] = "姨"
segment[2] = "妈"
复制代码

这时,程序在这里:

if c.IsEnd {
    matched = append(matched, item)
    if len(c.Child) == 0 {
        item = ""
        ptr = t
        continue
    }
}
复制代码

trie游标重置,继续往下:

segment[3] = "j"
复制代码

这时,命中jin子j,然后继续往下,直到完全匹配jin子

所以,我们不能只在未匹配到的地方,重置segmant游标,在匹配完一个敏感词时,也要重置segment游标:

if c.IsEnd {
    matched = append(matched, item)
    if len(c.Child) == 0 {
        i = index
        index++
        item = ""
        ptr = t
        continue
    }
}
复制代码
$ go test -v .
=== RUN   TestTrie
    trie_test.go:48: [大姨妈 姨妈jin jin子]
--- PASS: TestTrie (0.00s)
PASS
ok      danmaku/utilities       0.012s
复制代码

测试通过!

matched := trieTree.Search("我很正常")
t1.Log(matched)
if len(matched) > 0 {
    t1.Errorf("search: %s, expected: %v, actual: %v", "我很正常", "", matched)
}
复制代码
$ go test -v .
=== RUN   TestTrie
    trie_test.go:54: []
--- PASS: TestTrie (0.00s)
PASS
ok      danmaku/utilities       0.012s
复制代码

测试通过!终于松了口气!

Trie的删除

Trie删除就很简单了,先遍历Trie,找到需要删除的敏感词,将遍历过程中的路径记录下来,然后从后往前删:

func (t *Trie) Delete(word string) {
	word = strings.TrimSpace(word)
	var branch []*Trie
	ptr := t
	for _, u := range word {
		branch = append(branch, ptr)
		c, ok := ptr.Child[u]
		if !ok {
			return
		}
		ptr = c
	}

	// 只命中字典中部分词
	if !ptr.IsEnd {
		return
	}

	// 如bitch和bitches
	// 删除bitch时,只需要将bitch最后一个节点的IsEnd改为false即可
	if len(ptr.Child) != 0 {
		ptr.IsEnd = false
		return
	}

	for len(branch) > 0 {
		p := branch[len(branch) - 1]
		branch = branch[:len(branch) - 1]

		delete(p.Child, ptr.Word)
        // IsEnd == true 如bitch和bitches,删除bitches时,只需要删除后面的"es"即可
        // len(Child) != 0 整个敏感词全删除
		if p.IsEnd || len(p.Child) != 0 {
			break
		}
		ptr = p
	}
}
复制代码

再测试一下:

trieTree.Delete("你大爷")
matched := trieTree.Search("你大爷")
t1.Log(matched)
if len(matched) != 0 {
    t1.Errorf("search: %s, expected: %v, actual: %v", "你大爷", []string{"你大爷"}, matched)
}
复制代码
$ go test -v .
=== RUN   TestTrie
    trie_test.go:61: []
--- PASS: TestTrie (0.00s)
PASS
ok      danmaku/utilities       0.011s
复制代码

好了,终于完成了!!!

过滤敏感词

danmakuMsg := c.filter(rsvData.Msg)
func (c *Client) filter(msg string) string {
	matched := trieTree.Search(msg)
	if len(matched) != 0 {
		var oldNew []string
		for _, v := range matched {
			oldNew = append(oldNew, v, "***")
		}
		replacer := strings.NewReplacer(oldNew...)
		return replacer.Replace(msg)
	}
	return msg
}
复制代码

再添加一个HTTP接口,用来增加敏感词:

http.HandleFunc("/illegal", illegalHandle)
func illegalHandle(w http.ResponseWriter, r *http.Request) {
	if r.URL.Path != "/illegal" {
		http.Error(w, "Not found", http.StatusNotFound)
		return
	}
	if r.Method != "POST" {
		http.Error(w, "Method not allowed", http.StatusMethodNotAllowed)
		return
	}
	words := r.PostFormValue("words")
	fmt.Println(words)
	if words == "" {
		http.Error(w, "words值不能为空", http.StatusBadRequest)
		return
	}
	trieTree.Insert(words)
	w.Write([]byte{})
}
复制代码

发送弹幕"大姨妈jin子啊"

好了,大功告成!

代码已提交到gitee仓库。

分享到: