关键字过滤脏字过滤Trie算法golang实现

数据小菜鸟 · · 1174 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

游戏，还有社交属性类软件都需要的脏字过滤功能。关于Trie算法自行百度。
不多说直接撸代码

// Trie.go
// 358860528@qq.com

package comm

import (
    "unicode/utf8"
)

/*
脏字过滤库
*/

type Trie struct {
    Root *TrieNode
}

type TrieNode struct {
    Children map[rune]*TrieNode
    End      bool
}

func NewTrie() Trie {
    var r Trie
    r.Root = NewTrieNode()
    return r
}

func NewTrieNode() *TrieNode {
    n := new(TrieNode)
    n.Children = make(map[rune]*TrieNode)
    return n
}

func (this *Trie) Inster(txt string) {
    if len(txt) < 1 {
        return
    }
    node := this.Root
    key := []rune(txt)
    for i := 0; i < len(key); i++ {
        if _, exists := node.Children[key[i]]; !exists {
            node.Children[key[i]] = NewTrieNode()
        }
        node = node.Children[key[i]]
    }

    node.End = true
}

func (this *Trie) HasDirty(txt string) bool {
    if len(txt) < 1 {
        return false
    }
    node := this.Root
    key := []rune(txt)
    var chars []rune = nil
    slen := len(key)
    for i := 0; i < slen; i++ {
        if _, exists := node.Children[key[i]]; exists {
            node = node.Children[key[i]]
            for j := i + 1; j < slen; j++ {
                if _, exists := node.Children[key[j]]; exists {
                    node = node.Children[key[j]]
                    if node.End == true {
                        if chars == nil {
                            chars = key
                        }
                        for t := i; t <= j; t++ {
                            return true
                        }
                        i = j
                        node = this.Root
                        break
                    }
                }
            }
            node = this.Root
        }
    }
    return false
}

func (this *Trie) Replace(txt string) string {
    if len(txt) < 1 {
        return txt
    }
    node := this.Root
    key := []rune(txt)
    var chars []rune = nil
    slen := len(key)
    for i := 0; i < slen; i++ {
        if _, exists := node.Children[key[i]]; exists {
            node = node.Children[key[i]]
            for j := i + 1; j < slen; j++ {
                if _, exists := node.Children[key[j]]; exists {
                    node = node.Children[key[j]]
                    if node.End == true {
                        if chars == nil {
                            chars = key
                        }
                        for t := i; t <= j; t++ {
                            c, _ := utf8.DecodeRuneInString("*")
                            chars[t] = c
                        }
                        i = j
                        node = this.Root
                        break
                    }
                }
            }
            node = this.Root
        }
    }
    if chars == nil {
        return txt
    } else {
        return string(chars)
    }
}

// Trie_test.go
// 358860528@qq.com
// 测试案例

package comm

import (
    "testing"
)


//测试案例
func Test_trie(t *testing.T) {
    ti := NewTrie()

    ti.Inster("脏话")

    ti.Inster("mb")

    s := ti.Replace("不能说脏话也不能说mb")
    t.Log(ti.HasDirty("不能说脏话也不能说mb"))
    t.Log(s)
    s = ti.Replace("不能说脏也不能说m")
    t.Log(ti.HasDirty("不能说脏也不能说m"))
    t.Log(s)
}