/doublearray.go Secret
Created
March 25, 2021 11:11
Star
You must be signed in to star a gist
ダブル配列
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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