xtrie

README

xtrie

go版本的double array trie算法

增加词等级设置，词等级可有效区分不同等级，不同业务处理模式，词等级支持1-9

压缩数据结构，字符存储更紧凑，占用内存效率更少

扩展多种检索方法

• 词检索
• 前缀检索
• 后缀检索
• 内容检索
• 模糊检索

内容检索和模糊检索的区别在于

内容检索会在内容中查找词库中的词，返回在内容中出现的词

模糊检索会在内容中查找每个词的每个字符，返回内容中出现词的某部分而查找到的词

TO DO list

• 检索性能优化
• 插入性能优化

Reference

What is Trie
An Implementation of Double-Array Trie

快速开始

go get github.com/jinxing3114/xtrie

import "github.com/jinxing3114/xtrie"

var XT = new(xtrie.XTrie)
var storeFile,dictFile = "data/dat.data", "data/darts.txt"
XT.InitHandle(storeFile, dictFile)

示例

package main

import (
	"fmt"
	"github.com/jinxing3114/xtrie"
)

//创建XTrie
var XT = new(xtrie.XTrie)

func main() {
    var storeFile,dictFile = "data/dat.data", "data/darts.txt"

    XT.InitHandle(storeFile, dictFile)

    //词检索，查找词是否存在于词库中
    index, level, err := XT.Match("a", false)
    fmt.Println(index, level, err)
    
    //文本检索，检索文本中有哪些是词库已存在的词
    content := "文本检索test"
    searchResult := XT.Search(content)
    fmt.Println(searchResult)

    //前缀匹配，根据输入字符，查找满足该前缀的词
    prefixResult,err := XT.Prefix("b", 10)
    fmt.Println(prefixResult, err)

    //后缀匹配，根据输入字符，查找满足该后缀的词
    suffixResult,err := XT.Suffix("c", 10)
    fmt.Println(suffixResult, err)

    //模糊匹配，根据输入的文本任意拆解字符，如果库中存在返回查找到的词
    fuzzyContent := "模糊检索文本测试一下abc"
    fuzzyResult,err := XT.Fuzzy(fuzzyContent, 10)
    fmt.Println(fuzzyResult, err)

    //插入词，复杂度不等，视情况而定
    insertErr := XT.Insert("key", level)
    fmt.Println(insertErr)

    removeErr := XT.Remove("key")
    fmt.Println(removeErr)

}

LICENSE

Apache License 2.0

Documentation

Index

• type MatchResult
• type Node
• type XTrie
  • func (x *XTrie) DictAdd(key string, level int)
  • func (x *XTrie) DictRead() (bool, error)
  • func (x *XTrie) DictRemove(key string) error
  • func (x *XTrie) Fuzzy(key string, limit int) ([]MatchResult, error)
  • func (x *XTrie) InitHandle(storeFile string, dictFile string)
  • func (x *XTrie) Insert(key string, level int) error
  • func (x *XTrie) Load(path string) error
  • func (x *XTrie) Match(key string, forceBack bool) (int, int, error)
  • func (x *XTrie) Prefix(pre string, limit int) ([]MatchResult, error)
  • func (x *XTrie) Remove(key string) error
  • func (x *XTrie) Search(key string) []MatchResult
  • func (x *XTrie) Store(path string) error
  • func (x *XTrie) Suffix(key string, limit int) ([]MatchResult, error)

Types

type MatchResult

type MatchResult struct {
	Word  string `json:"word"`
	Level int    `json:"level"`
}

查询返回值结构体 使用结构体可以保证检索结果的顺序，使用map结构无法保证顺序

type Node

type Node struct {
	Code  int  // 字符对应code值
	Depth int  // 所处树的层级，正好对应子节点在key中索引
	Left  int  // 当前字符在key list中搜索的左边界索引 （包括）
	Right int  // 当前字符在key list中搜索的右边界索引（不包括）
	End   bool // 是否结束
}

构建trie树使用的节点

type XTrie

type XTrie struct {
	Fmd5      string         // 词典文件md5
	Size      int            // 切片长度
	Base      []int          // 基础切片，存储字符offset，正值和负值分别代表不同的状态
	Check     []int          // 检查字符状态数组，防止查找冲突以及确认多种状态
	Keys      [][]rune       // 所有词典转成rune切片
	StoreFile string         //dat结构体序列化结果集
	DictFile  string         //词典文件路径
	Keymap    map[string]int //所有词对应等级
}

x trie结构体 double array trie变种结构体 数据结构更紧凑

func (*XTrie) DictAdd

func (x *XTrie) DictAdd(key string, level int)

添加词 todo 写入需要判断最后的字符是不是换行

func (*XTrie) DictRead

func (x *XTrie) DictRead() (bool, error)

读取文件加载词库

func (*XTrie) DictRemove

func (x *XTrie) DictRemove(key string) error

移除词

func (*XTrie) Fuzzy

func (x *XTrie) Fuzzy(key string, limit int) ([]MatchResult, error)

模糊查找 命中规则，只要有字符是一样的就会返回，最少一个字符

func (*XTrie) InitHandle

func (x *XTrie) InitHandle(storeFile string, dictFile string)

初始化 double array 加载store文件，读取词典，编译dat，保存store等

func (*XTrie) Insert

func (x *XTrie) Insert(key string, level int) error

动态添加数据 复杂度：可能是O(1)也可能是O(root)

func (*XTrie) Load

func (x *XTrie) Load(path string) error

从指定路径加载DAT

func (*XTrie) Match

func (x *XTrie) Match(key string, forceBack bool) (int, int, error)

查找搜索的词是否在词库-精确查找 参数 key string 查找的词 返回 最后一个字符的索引，偏移量，等级，error

func (*XTrie) Prefix

func (x *XTrie) Prefix(pre string, limit int) ([]MatchResult, error)

前缀查找 匹配搜索词所有相同前缀的词，算法复杂度较高，词不多的时候可以使用

func (*XTrie) Remove

func (x *XTrie) Remove(key string) error

删除词 参数 key string 需要删除的词

func (*XTrie) Search

func (x *XTrie) Search(key string) []MatchResult

内容匹配模式查找 可传入一段文本，逐字查找是否在词库中存在

func (*XTrie) Store

func (x *XTrie) Store(path string) error

使用gob协议

func (*XTrie) Suffix

func (x *XTrie) Suffix(key string, limit int) ([]MatchResult, error)

后缀匹配词 返回查找到的字符串以及词等级 算法复杂度，对比前缀搜索要低。根据匹配到的字符依次查找，词越长，查找消耗越大