Skip to content

Instantly share code, notes, and snippets.

@snowhork
Created March 25, 2021 11:11
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save snowhork/b822bfa13d2ba69f48a1dc10d64458c1 to your computer and use it in GitHub Desktop.
ダブル配列
package main
import "fmt"
type codeInt uint8
type vocabulary struct {
offset codeInt
stopIndex codeInt
}
func newVocabulary(voc string) vocabulary {
return vocabulary{
offset: codeInt(voc[0]),
stopIndex: codeInt(voc[len(voc)-1] - voc[0] + 1),
}
}
func (v *vocabulary) codes(word string) []codeInt {
codes := make([]codeInt, len(word)+1)
for i := range word {
codes[i] = codeInt(word[i]) - v.offset
}
codes[len(word)] = v.stopIndex
return codes
}
func (v *vocabulary) toCode(c codeInt) byte {
return byte(c + v.offset)
}
type TrieTree struct {
vocabulary
root *trieNode
}
type trieNode struct {
code codeInt
children *[]trieNode // https://medium.com/veltra-engineering/is-the-golang-slice-a-pointer-or-not-a-pointer-99433f2cea17
}
func NewTrieTree(voc string) *TrieTree {
return &TrieTree{
vocabulary: newVocabulary(voc),
root: &trieNode{children: &[]trieNode{}},
}
}
func (t *TrieTree) Add(word string) {
codes := t.codes(word)
fmt.Printf("Add: %d\n", codes)
t.root.traverse(0, codes)
}
func (n *trieNode) traverse(i int, codes []codeInt) {
fmt.Printf("i: %d, n: %p, n.children: %p\n", i, n, n.children)
if i == len(codes) {
return
}
for _, child := range *n.children {
if child.code == codes[i] {
child.traverse(i+1, codes)
return
}
}
next := trieNode{code: codes[i], children: &[]trieNode{}}
*n.children = append(*n.children, next)
//fmt.Printf("add node: %p, children: %d\n", &next, len(n.children))
next.traverse(i+1, codes)
//fmt.Printf("add node: %p, children: %d\n", &next, len(n.children))
}
// -- Double Array --
type indexInt uint8
type doubleArray struct {
base []indexInt
check []indexInt
vocabulary
}
func NewDoubleArray(t *TrieTree) *doubleArray {
da := &doubleArray{
vocabulary: t.vocabulary,
base: make([]indexInt, 4),
check: make([]indexInt, 4),
}
da.build(indexInt(0), t.root)
return da
}
func (da *doubleArray) build(current indexInt, n *trieNode) {
fmt.Printf("current: %d\n", current)
fmt.Printf("base: %v\n", da.base)
fmt.Printf("check: %v\n", da.check)
offset := indexInt(1)
for !da.acceptable(*n.children, offset) {
offset++
}
da.base[current] = offset
for _, child := range *n.children {
next := offset + indexInt(child.code)
da.check[next] = current + 1
}
for _, child := range *n.children {
next := offset + indexInt(child.code)
da.build(next, &child)
}
}
func (da *doubleArray) acceptable(nodes []trieNode, offset indexInt) bool {
for _, child := range nodes {
next := offset + indexInt(child.code)
if len(da.check) <= int(next) {
da.extend()
}
if da.check[next] != 0 {
return false
}
}
return true
}
func (da *doubleArray) extend() {
newBase := make([]indexInt, cap(da.base)*2)
copy(newBase, da.base)
newCheck := make([]indexInt, cap(da.check)*2)
copy(newCheck, da.check)
da.base = newBase
da.check = newCheck
}
func (da *doubleArray) SearchPrefix(word string) []string {
var result []string
current := indexInt(0)
for _, code := range da.codes(word)[:len(word)] {
next := da.base[current] + indexInt(code)
if int(next) >= len(da.check) || current != da.check[next]-1 {
return result
}
current = next
}
da.dfs(current, []byte(word), &result)
return result
}
func (da *doubleArray) dfs(i indexInt, str []byte, result *[]string) {
next := da.base[i] + indexInt(da.stopIndex)
if int(next) < len(da.check) && i == da.check[next]-1 {
*result = append(*result, string(str))
}
for c := codeInt(0); c < da.stopIndex; c++ {
next := da.base[i] + indexInt(c)
if int(next) >= len(da.check) || i != da.check[next]-1 {
continue
}
da.dfs(next, append(str, da.toCode(c)), result)
}
}
func (da *doubleArray) search(word string) (int, indexInt) {
current := indexInt(0)
for i, code := range da.codes(word) {
next := da.base[current] + indexInt(code)
fmt.Printf("- search %d to %d\n", current, next)
if int(next) >= len(da.check) || current != da.check[next]-1 {
fmt.Printf("- search fail, %v\n", int(next) >= len(da.check))
return i, current
}
current = next
}
return len(word), current
}
func (da *doubleArray) Search(word string) bool {
res, _ := da.search(word)
return res == len(word)
}
func main() {
fmt.Printf("\n--------------\nBuildng Tree\n--------------\n")
voca := "abcde"
t := NewTrieTree(voca)
t.Add("ac")
t.Add("ac")
t.Add("ace")
t.Add("ad")
t.Add("ade")
t.Add("adea")
t.Add("adead")
t.Add("ada")
t.Add("bae")
t.Add("bca")
t.Add("dae")
t.Add("eee")
fmt.Printf("\n--------------\nBuildng DoubleArray\n--------------\n")
da := NewDoubleArray(t)
fmt.Printf("\n--------------\nSearching DoubleArray\n--------------\n")
fmt.Printf("base: %v\n", da.base)
fmt.Printf("check: %v\n", da.check)
fmt.Printf("%v\n", da.Search("ace")) // true
fmt.Printf("%v\n", da.Search("ade")) // true
fmt.Printf("%v\n", da.Search("dae")) // true
fmt.Printf("%v\n", da.Search("acb")) // false
fmt.Printf("%v\n", da.SearchPrefix("ad"))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment