最近的评论

• 2021-10-07 13:18:47 评论了主题 Go语言学习——深入学习一致性算法Raft
  @mi1688 ok
• 2020-11-16 17:34:40 评论了博文 go 无锁队列
  没有原子，并发会有问题
• 2020-11-02 18:37:39 评论了主题 广告投放场景中倒排索引的构建与实现
  C++代码移入了环境变量，有空控制调试日志，如果不想使用的话，可以修改下；也可以引入临时环境变量，如： export InvertedTest=true
• 2020-10-14 10:32:37 评论了主题 AC自动机实现
  在实际应用中，发现AC自动机实现有问题，在设置failNode时，是需要BFS遍历每层节点，为其子节点设置failNode的，但是，在实现中把这块忘了，只设置了前两层节点的failNode；对于failNode设置这块进行了更新，除了增加节点记录，还优化了记录方式，之前是使用list，现在换成slice，因为要一边遍历节点，一边要记录子节点，还要删除已遍历过的节点，使用slice主要是想整体删除；另外，在匹配方面也做了修改，加快查找速度，核心改动可以查看"// DONE"注释部分，为了方便查看，直接贴代码了： ```go const childNodeCount = 16 // AC自动机节点结构定义 type AcAutoNode struct { endCount int // 结束模式串个数 prefixCount int // 前缀模式串个数 failNode *AcAutoNode // fail指针节点 childNode [childNodeCount]*AcAutoNode // 子节点 } // AC自动机初始化 var GAcAuto *AcAutoNode func init() { GAcAuto = new(AcAutoNode) } func BuildTree(s []string) { // 遍历模式串列表 for uli := 0; uli < len(s); uli++ { node := GAcAuto // 遍历模式串字符 for _, runeCh := range s[uli] { // 分高低位判断 runeStr := string(runeCh) for ulj := 0; ulj < len(runeStr); ulj++ { indexHigh := runeStr[ulj] / childNodeCount if node.childNode[indexHigh] == nil { node.childNode[indexHigh] = &AcAutoNode{} } node = node.childNode[indexHigh] indexLow := runeStr[ulj] % childNodeCount if node.childNode[indexLow] == nil { node.childNode[indexLow] = &AcAutoNode{} } node = node.childNode[indexLow] } node.prefixCount++ } node.endCount++ } } func SetNodeFailPoint() { GAcAuto.failNode = nil nodeList := make([]*AcAutoNode, 0, 10000) nodeList = append(nodeList, GAcAuto) // 逐层遍历trie树节点，为节点设置fail指针 for { nodeListSize := len(nodeList) if nodeListSize <= 0 { break } for uli := 0; uli < nodeListSize; uli++ { node := nodeList[uli] if node == GAcAuto { // 根节点的子节点的fail指针都指向根节点 for ulj := 0; ulj < childNodeCount; ulj++ { if node.childNode[ulj] != nil { node.childNode[ulj].failNode = GAcAuto nodeList = append(nodeList, node.childNode[ulj]) // DONE } } } else { // 遍历父节点，依据父节点的failNode，为其每个子节点设置failNode for ulj := 0; ulj < childNodeCount; ulj++ { if node.childNode[ulj] != nil { nodeList = append(nodeList, node.childNode[ulj]) // DONE // fail指针设置原则是： // 1）查看father->failNode下有没有和自己一样的子节点，有则fail指针取该子节点 // 2）否则，沿father->failNode->failNode继续查询下，如果一直没有，fail指针就取根节点 nextNode := node.failNode for { if nextNode == nil { node.childNode[ulj].failNode = GAcAuto break } else { if nextNode.childNode[ulj] != nil { node.childNode[ulj].failNode = nextNode.childNode[ulj] break } else { nextNode = nextNode.failNode } } } } } } } nodeList = nodeList[nodeListSize:] } } func AcAutoMatch(input string) bool { node := GAcAuto for _, runeCh := range input { count := 0 runeStr := string(runeCh) for uli := 0; uli < len(runeStr); uli++ { for ulj := 0; ulj < 2; ulj++ { index := runeStr[uli] / childNodeCount if ulj != 0 { index = runeStr[uli] % childNodeCount } Match: if node != nil && node.childNode[index] != nil { // 找到即退出，没有结束继续查找 count++ if node.childNode[index].endCount > 0 && count == 2*len(runeStr) { return true } else { node = node.childNode[index] } } else { if node == nil { // 当前字符一直查不到，则换下个字符，故重置node，取值根节点 node = GAcAuto goto runeChOver // DONE，快速退出当前字符、换下个字符 } else { // 当前节点没有目标字符，则去下个节点看下，即查看fail指针 node = node.failNode goto Match } } } } runeChOver: } return false } var minGan = make([]string, 0, 10000) func main() { // 建树 BuildTree([]string{"ba", "real", "中国"}) // 设置fail指针 SetNodeFailPoint() // 查找 fmt.Println(AcAutoMatch("ea")) fmt.Println(AcAutoMatch("real")) fmt.Println(AcAutoMatch("eal中国")) fmt.Println(AcAutoMatch("reaL")) } ```
• 2020-10-12 10:29:33 评论了主题 Go语言学习——深入学习一致性算法Raft
  国庆期间又看了协议文档、视频资料；之前理解有些模糊的地方，已经梳理清楚了，网站支持编辑就好了，发布两天后都无法编辑了