北京网站优化公司哪家好,浅析图书馆门户网站建设,wordpress 后台管理风格主题,保定网站建设公司哪家好在一些论坛或者博客类的项目需要对内容进行敏感词的匹配以及脱敏操作#xff0c;像这类的功能就可以使用前缀树实现#xff0c;接下来我们就使用哈希去实现前缀树。#xff08;gin框架的路由树也是基于前缀树实现的#xff09;
什么是前缀树#xff1f;
前缀树#xff…在一些论坛或者博客类的项目需要对内容进行敏感词的匹配以及脱敏操作像这类的功能就可以使用前缀树实现接下来我们就使用哈希去实现前缀树。gin框架的路由树也是基于前缀树实现的
什么是前缀树
前缀树Prefix Tree也被称为字典树Trie是一种用于高效存储和检索字符串的数据结构。它的主要特点是能够快速地查找具有相同前缀的字符串集合。
既然使用前缀树做字符匹配那么它有什么特点
高效的字符串存储前缀树使用共享前缀的方式存储字符串因此可以高效地存储大量字符串集合。相同的前缀会被共享减少了存储空间的需求。快速的字符串搜索前缀树可以快速地搜索具有相同前缀的字符串集合。通过从根节点开始按照字符依次向下遍历树的路径可以高效地定位到匹配的字符串。前缀匹配前缀树可以快速地找出与给定字符串具有相同前缀的所有字符串。通过遍历匹配到的子树可以得到所有以给定前缀开头的字符串。支持动态更新前缀树可以动态地插入和删除字符串。当需要插入或删除一个字符串时只需按照字符依次遍历树的路径根据需要插入或删除节点。适用于字符串相关操作前缀树广泛应用于字符串相关的操作如自动补全、拼写检查、词频统计、字符串搜索和匹配等。由于其高效的存储和检索特性可以在这些场景下提供快速和高效的操作。路径压缩前缀树具有路径压缩的能力可以减少不必要的节点节省存储空间。当某个节点只有一个子节点时可以将中间节点合并减少冗余的节点。
实现思路
假设我们有以下敏感词列表[bad, evil, danger] (root) [bad, evil, danger]/ | \b e d/ | \a v a/ | \d i n| \l g| \e e在这个前缀树中每个节点代表一个字符根节点表示空字符每个节点的子节点表示对应的字符。叶子节点表示一个完整的敏感词。
遍历实现思路
遍历待检测的文本。从根节点开始按照文本中的字符依次遍历前缀树的路径。如果在遍历过程中遇到空路径或者遍历完成后当前节点不是叶子节点则表示没有匹配到敏感词继续遍历下一个字符。如果遍历完成后当前节点是叶子节点则表示匹配到了敏感词根据需求进行相应的处理如替换为星号或进行其他处理。
代码实现
package sensitiveWordimport (io/ioutilosproject/constsproject/typesstringsgo.uber.org/zap
)// SensitiveMap 使用前缀树实现敏感词过滤
type SensitiveMap struct {sensitiveNode map[string]interface{}isEnd bool
}// Target 目标词索引、长度
type Target struct {Indexes []intLen int
}var s *SensitiveMap// getMap 将自己的词库放入/static/dictionary下放入下列切片中
func getMap() *SensitiveMap {if s nil {var Sen []stringSen append(Sen, consts.OtherSen)s InitDictionary(s, Sen)}return s
}// CheckSensitiveWord 判断是否有敏感词
func CheckSensitiveWord(content string) []*types.SensitiveWord {var res []*types.SensitiveWordsensitiveMap : getMap()target : sensitiveMap.FindAllSensitive(content)for k, v : range target {t : types.SensitiveWord{Word: k,Indexes: v.Indexes,Length: v.Len,}res append(res, t)}return res
}// FindAllSensitive 查找所有的敏感词
func (s *SensitiveMap) FindAllSensitive(text string) map[string]*Target {content : []rune(text)contentLength : len(content)result : falseta : make(map[string]*Target)for index : range content {sMapTmp : starget : in : indexresult falsefor {wo : string(content[in])target woif _, ok : sMapTmp.sensitiveNode[wo]; ok {if sMapTmp.sensitiveNode[wo].(*SensitiveMap).isEnd {result truebreak}if in contentLength-1 {break}sMapTmp sMapTmp.sensitiveNode[wo].(*SensitiveMap)in} else {break}}if result {if _, targetInTa : ta[target]; targetInTa {ta[target].Indexes append(ta[target].Indexes, index)} else {ta[target] Target{Indexes: []int{index},Len: len([]rune(target)),}}}}return ta
}// InitDictionary 初始化字典构造前缀树
func InitDictionary(s *SensitiveMap, dictionary []string) *SensitiveMap {// 初始化字典树s initSensitiveMap()var dictionaryContent []stringfor i : 0; i len(dictionary); i {dictionaryContentTmp : ReadDictionary(dictionary[i])// TODO:将所有词拿到dictionaryContent append(dictionaryContent, dictionaryContentTmp...)}for _, words : range dictionaryContent {sMapTmp : s// 将每一个词转换为一个rune数组不光英文、中文w : []rune(words)wordsLen : len(w)for i : 0; i wordsLen; i {t : string(w[i])isEnd : falseif i (wordsLen - 1) {isEnd true}func(tx string) {// 查看当前字符在不在树结构在的话就复用节点if _, ok : sMapTmp.sensitiveNode[tx]; !ok {sMapTemp : new(SensitiveMap)sMapTemp.sensitiveNode make(map[string]interface{})sMapTemp.isEnd isEndsMapTmp.sensitiveNode[tx] sMapTemp}sMapTmp sMapTmp.sensitiveNode[tx].(*SensitiveMap)sMapTmp.isEnd isEnd}(t)}}return s
}// initSensitiveMap 初始化map
func initSensitiveMap() *SensitiveMap {return SensitiveMap{sensitiveNode: make(map[string]interface{}),isEnd: false,}
}// ReadDictionary 将词库读取出来
func ReadDictionary(path string) []string {file, err : os.Open(path)if err ! nil {zap.L().Error(read dictionary file failed:, zap.Error(err))return nil}defer file.Close()str, err : ioutil.ReadAll(file)dictionary : strings.Fields(string(str))return dictionary
}上述是前缀树实现的基本思路使用map构造前缀树目的就是为了快速定位节点。
优化思路
我们判断的时候肯定不可以每次读区词库这样io消耗过大。初步思路就是可以把前缀树加载到缓存中去到时候操作缓存匹配敏感词效率就高了如果要更新词库就重新加载缓存即可更新词库树形结构变化不会过大即可动态更新。
算法优化思路DFA算法优化
如果大规模过滤敏感词的时候前缀树就会遇到性能瓶颈这个时候就需要使用dfa进行前缀树的算法优化。
步骤如下
当应用DFA算法对前缀树进行优化时需要将前缀树转换成DFA状态机。下面是一种常见的转换步骤
构建初始状态DFA状态机的初始状态对应于前缀树的根节点。逐层构建状态转移从初始状态开始按照前缀树的层次结构逐层构建状态转移。对于每个状态根据前缀树节点的子节点和字符的对应关系确定该状态的转移条件。标记终止状态对于前缀树中表示一个完整字符串的节点叶子节点标记相应的状态为终止状态。合并等价状态在构建状态转移时可能会出现等价的状态。通过状态合并操作将等价状态合并为一个状态从而减少状态的数量。优化状态转移表根据具体情况可以对状态转移表进行优化如压缩存储、使用哈希表等。
这里就不展开讲了
如果有更好的思路欢迎讨论
