README
¶
一、说明
双数组检索树。
状态转移方程：
firstState = 1
父节点：
base[parentCode + parentState - 2] = childState
check[parentCode + parentState - 2] = parentState
子节点：
base[childCode + childState - 2] = grandchildState
check[childCode + childState - 2] = childState
......
终节点：
base[code + state - 2] < 0
code: 字符编码值。对应词汇中的一个字符。
state: 状态值，从 1 开始。
例子：
排好了序的词汇：
[]string{
0 AC
1 AD
2 ADG
3 ADH
4 ADHG
5 BEIZ
6 BEL
7 BF
8 DG
}
code A=1 B=2 C=3 D=4 E=5 F=6 G=7 H=8 I=9 L=10 Z=11
双数组值，负值表示为该节点对应词汇的下标：
base [3 7 -1 16 4 8 -2 -3 -4 -5 12 19 -6 9 10 11 -7 -8 -9 13 18 20 14]
check [1 1 4 1 3 3 8 9 10 11 7 7 14 8 8 10 18 19 20 12 12 16 13]
树结构：
depth
0 Root
⁰ ⁹
/ \ \
1 A B D
⁰ ⁵ ⁵ ⁷ ⁸ ⁹
/ / \ / \ \
2 C D D E F G
⁰ ¹ ¹ ⁵ ⁵ ⁷ ⁷ ⁷ ⁸ ⁹
/ / \ / \
3 G H H I L
² ³ ³ ⁵ ⁵ ⁶ ⁶ ⁷
\ /
4 G Z
⁴ ⁵ ⁵ ⁶
二、使用
go get gitee.com/ivfzhou/double-array-trie@latest
import dat "gitee.com/ivfzhou/double-array-trie"
// 需要被检索的数据
data := []string{
"/api/user/info",
"/api/user/register",
"/api/user/login",
}
// 构建双数组
d := dat.New(data)
// 获取有 /api 前缀的词。
array := d.HitKeys("/api")
// 判断是否存在与数据中
ok := d.Matches(word)
// 判断数据中是否有前缀和 path 匹配
ok := d.MatchPrefix(path)
// 获取 path 在字典中的索引
index := d.MatchesIndex(path)
key := d.GetKey(index)
// 返回所有匹配前缀 path 的数据
keys := d.ObtainPrefixes(path)
// 解析 sentence，返回数据中出现在 sentence 中的数据和其位置
keys, indexes := d.Analysis("sentence")
// 若匹配词汇，就返回对应 value。
d := dat.NewWithValue(map[string]any{
"/api/user/info": func() {},
"/api/user/register": func() {},
"/api/user/login": func() {},
})
value, ok := d.MatchGet(word)
if ok {
value()
}
Documentation
¶
Index ¶
- Variables
- type Dat
- func (d *Dat[T]) Analysis(sentence string) (keys []string, indexes []int)
- func (d *Dat[T]) Depth() int
- func (d *Dat[T]) DumpToFile(filePath string) error
- func (d *Dat[T]) GetKey(index int) string
- func (d *Dat[T]) HitKeys(prefix string) (hits []string)
- func (d *Dat[T]) Hollow() int
- func (d *Dat[T]) KeySize() int
- func (d *Dat[T]) MatchGet(word string) (value any, ok bool)
- func (d *Dat[T]) MatchIndex(word string) int
- func (d *Dat[T]) MatchPrefix(word string) bool
- func (d *Dat[T]) Matches(word string) bool
- func (d *Dat[T]) MatchesIndex(word string) intdeprecated
- func (d *Dat[T]) ObtainPrefixes(word string) (result []string)
- func (d *Dat[T]) Size() int
- func (d *Dat[T]) String() string
Examples ¶
Constants ¶
This section is empty.
Variables ¶
View Source
var ( // MinExpansiveFactor 适配 state 时，数组最小扩容系数。如果同层子节点 code 相差大，则该值该调大。 MinExpansiveFactor = 1.2 // InitArrayFactor 初始扩容系数。 InitArrayFactor = 2.5 )
Functions ¶
This section is empty.
Types ¶
type Dat ¶ added in v1.2.0
type Dat[T any] struct { // contains filtered or unexported fields }
func NewWithValues ¶ added in v1.3.0
NewWithValues 构建双数组树。不处理空串。可使用 Dat.MatchGet 根据 key 获取 value。不支持备份到文件。
func (*Dat[T]) Analysis ¶ added in v1.2.0
Analysis 分析 sentence，获取 sentence 中包含词库的词，和该词在 sentence 中的位置。
Example ¶
package main
import (
"fmt"
dat "gitee.com/ivfzhou/double-array-trie"
)
func main() {
d := dat.New([]string{"abc", "ab", "abg", "jkl"})
sentence := "abc ab"
hitKeys, indexes := d.Analysis(sentence)
for i, index := range indexes {
word := sentence[index : index+len(hitKeys[i])]
fmt.Println(word == hitKeys[i])
}
}
Output: true true
func (*Dat[T]) DumpToFile ¶ added in v1.2.0
DumpToFile 持久化检索树。
func (*Dat[T]) HitKeys ¶ added in v1.3.0
HitKeys 获取词库中前缀部分是 prefix 的词。包含 prefix 与词完全一样的情形。
Example ¶
package main
import (
"fmt"
dat "gitee.com/ivfzhou/double-array-trie"
)
func main() {
d := dat.New([]string{"abc", "def", "abdi", "jkl"})
fmt.Println(d.HitKeys("ab"))
}
Output: [abc abdi]
func (*Dat[T]) MatchGet ¶ added in v1.3.0
MatchGet 判断 word 是否在词库中，返回词对应的 value。
Example ¶
package main
import (
"fmt"
dat "gitee.com/ivfzhou/double-array-trie"
)
func main() {
keyToValue := map[string]any{
"abc": 1,
"afr": 2,
"kja": 3,
}
d := dat.NewWithValues(keyToValue)
fmt.Println(d.MatchGet("abc"))
fmt.Println(d.MatchGet("none"))
}
Output: 1 true <nil> false
func (*Dat[T]) MatchIndex ¶ added in v1.3.0
MatchIndex 检索 word 是否在词库中，并返回词位置，不存在返回 -1。
Example ¶
package main
import (
"fmt"
dat "gitee.com/ivfzhou/double-array-trie"
)
func main() {
d := dat.New([]string{"abc", "def", "ghi", "jkl"})
index := d.MatchIndex("abc")
fmt.Println(d.GetKey(index) == "abc")
}
Output: true
func (*Dat[T]) MatchPrefix ¶ added in v1.2.0
MatchPrefix 判断 word 是否是词库中任何一个词的前缀。包含 word 与词完全一样的情形。
Example ¶
package main
import (
"fmt"
dat "gitee.com/ivfzhou/double-array-trie"
)
func main() {
d := dat.New([]string{"abc", "def", "ghi", "jkl"})
fmt.Println(d.MatchPrefix("abc"))
fmt.Println(d.MatchPrefix("ab"))
fmt.Println(d.MatchPrefix("cab"))
}
Output: true true false
func (*Dat[T]) Matches ¶ added in v1.2.0
Matches 判断 word 是否存在于词库中。
Example ¶
package main
import (
"fmt"
dat "gitee.com/ivfzhou/double-array-trie"
)
func main() {
d := dat.New([]string{"abc", "def", "ghi", "jkl"})
fmt.Println(d.Matches("abc"))
fmt.Println(d.Matches("abcd"))
fmt.Println(d.Matches("ab"))
fmt.Println(d.Matches("jkl"))
}
Output: true false false true
func (*Dat[T]) MatchesIndex
deprecated
added in
v1.2.0
func (*Dat[T]) ObtainPrefixes ¶ added in v1.2.0
ObtainPrefixes 返回所有匹配 word 前缀的词。
Example ¶
package main
import (
"fmt"
dat "gitee.com/ivfzhou/double-array-trie"
)
func main() {
d := dat.New([]string{"abc", "ab", "abg", "jkl"})
fmt.Println(d.ObtainPrefixes("abc"))
}
Output: [ab abc]
Source Files
Click to show internal directories.
Click to hide internal directories.