Golang DFA 高效率敏感词过滤基础写法

浏览:238次阅读
没有评论

说明

在实现文字过滤的算法中,DFA 是唯一比较好的实现算法。

DFA 全称为:Deterministic Finite Automaton,即确定有穷自动机。其特征为:有一个有限状态集合和一些从一个状态通向另一个状态的边,每条边上标记有一个符号,其中一个状态是初态,某些状态是终态。但不同于不确定的有限自动机,DFA 中不会有从同一状态出发的两条边标志有相同的符号。

Golang DFA 高效率敏感词过滤基础写法

示例

王八羔子 , 王八蛋 将被分为字典如下图所示
Golang DFA 高效率敏感词过滤基础写法

在 hash 表中结构如下

{
    " 王 ":{
        "isEnd":"0",
        " 八 ":{
            " 羔 ":{
                " 子 ":{"isEnd":"1"},
                "isEnd":"0"
            },
            "isEnd":"0",
            " 蛋 ":{"isEnd":"1"}
        }
    }
}

当从 root 节点到结尾匹配成功(isEnd 为 1) 则为匹配成功敏感词, 替换为 *

案例

func TestDfa(t *testing.T) {gfw := NewDFAMather()
    gfw.AddKeyword(" 敏感词 1 ") // 添加敏感词 1
    gfw.AddKeyword(" 敏感词 2 ") // 添加敏感词 2
    gfw.AddKeyword(" 敏感词 3 ") // 添加敏感词 3

    content := " 这是一个敏感词过滤的例子,包含敏感词 1 和敏感词 2。"
    keys, result := gfw.Match(content) // 进行敏感词过滤

    // 将结果转换为 UTF- 8 编码输出

    fmt.Println(keys, result)
}

实际返回

Golang DFA 高效率敏感词过滤基础写法

代码

package DfaFilter

// 定义一个 Node 结构体,代表 DFA 的一个节点。type Node struct {
    End  bool           // End 字段表示是否为一个单词的结束。Next map[rune]*Node // Next 字段是一个映射,用于存储此节点的所有子节点。}

// 定义一个 DFAMatcher 结构体,代表一个完整的 DFA。type DFAMatcher struct {
    replaceChar rune  // replaceChar 字段是替换敏感词的字符。root        *Node // root 字段是 DFA 的根节点。}

// 创建出一个 DFA 树的根节点实例
func NewDFAMather() *DFAMatcher {
    return &DFAMatcher{
        root: &Node{End: false,},
    }
}

// Build 方法用于构建 DFA,它会将提供的所有单词添加到 DFA 中。func (d *DFAMatcher) Build(words []string) {
    for _, item := range words { // 遍历提供的所有单词。d.root.AddWord(item) // 将每一个单词添加到 DFA 的根节点。}
}

// Build 方法用于构建 DFA,它会将提供的所有单词添加到 DFA 中。func (d *DFAMatcher) AddKeyword(keywords string) {d.root.AddWord(keywords) // 将每一个单词添加到 DFA 的根节点。}

// AddWord 方法用于向当前节点添加一个单词。// 这个方法会遍历单词的每一个字符,并为每一个字符添加一个子节点。func (n *Node) AddWord(word string) {
    node := n                     // 从当前节点开始。chars := []rune(word)         // 将字符串转化为 rune 类型的切片,以便处理 Unicode 字符。for index, _ := range chars { // 遍历单词的每一个字符。node = node.AddChild(chars[index]) // 递归地为每一个字符添加子节点。}
    node.End = true // 设置最后一个节点为单词的结束。}

// AddChild 方法向当前节点添加一个子节点。// 如果子节点已经存在,它将不会被重复添加。func (n *Node) AddChild(c rune) *Node {
    if n.Next == nil { // 如果 Next 字段为 nil,则初始化一个映射。n.Next = make(map[rune]*Node)
    }
    // 检查字符 c 是否已经是当前节点的子节点。if next, ok := n.Next[c]; ok { // 如果 ok 为 true,则字符 c 已经是当前节点的子节点,直接返回该子节点。return next
    } else { // 否则,创建一个新的节点,并将其设置为当前节点的子节点。n.Next[c] = &Node{
            End:  false,
            Next: nil,
        }
        return n.Next[c] // 返回新创建的子节点。}
}

// Match 方法用于在文本中查找并替换敏感词。// 它返回找到的敏感词列表和替换后的文本。func (d *DFAMatcher) Match(text string) (sensitiveWords []string, replaceText string) {
    if d.root == nil { // 如果 DFA 是空的,直接返回原始文本。return nil, text
    }
    textChars := []rune(text)                     // 将文本转化为 rune 类型的切片,以便处理 Unicode 字符。textCharsCopy := make([]rune, len(textChars)) // 创建一个文本字符的副本,用于替换敏感词。copy(textCharsCopy, textChars)                // 复制原始文本字符到副本。length := len(textChars)                      // 获取文本的长度。for i := 0; i < length; i++ {                 // 遍历文本的每一个字符。// 在 DFA 树中查找当前字符对应的子节点
        temp := d.root.FindChild(textChars[i])
        if temp == nil {continue // 如果不存在匹配,继续检查下一个字符}
        j := i + 1
        // 遍历文本中的字符,查找匹配的敏感词,第一个匹配上了,就进行后面的向下匹配
        for ; j < length && temp != nil; j++ {
            if temp.End {
                // 如果找到一个敏感词,将其添加到结果列表中,并在副本中替换为指定字符
                sensitiveWords = append(sensitiveWords, string(textChars[i:j]))
                replaceRune(textCharsCopy, '*', i, j) // 替换敏感词
            }
            temp = temp.FindChild(textChars[j])
        }
        // 处理文本末尾的情况,如果末尾是一个完整的敏感词,添加到结果列表中,并在副本中替换为指定字符
        if j == length && temp != nil && temp.End {sensitiveWords = append(sensitiveWords, string(textChars[i:length]))
            replaceRune(textCharsCopy, '*', i, length)
        }
    }
    return sensitiveWords, string(textCharsCopy) // 返回匹配到的敏感词列表和替换后的文本

}

// FindChild 方法用于在当前节点的子节点中查找一个特定的子节点。func (n *Node) FindChild(c rune) *Node {
    if n.Next == nil { // 如果 Next 字段为 nil,则直接返回 nil。return nil
    }
    // 检查字符 c 是否是当前节点的子节点。if _, ok := n.Next[c]; ok { // 如果 ok 为 true,则字符 c 是当前节点的子节点,返回该子节点。return n.Next[c]
    }
    return nil // 否则,返回 nil。}

// 替换掉文章中出现的关键词
func replaceRune(chars []rune, replaceChar rune, begin int, end int) {
    for i := begin; i < end; i++ {chars[i] = replaceChar
    }
}
正文完
 0
包子
版权声明:本站原创文章,由 包子 于2024-02-29发表,共计3191字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)