我試圖在Github中使用這個包進行字符串匹配。我的字典是 4 MB。創建 Trie 時，我得到了fatal error: runtime: out of memory. 我正在使用具有 8 GB RAM 和 Golang 版本 1.4.2 的 Ubuntu 14.04。似乎錯誤來自第 99 行（現在）：m.trie = make([]node, max)程序停在這一行。這是錯誤：fatal error: runtime: out of memoryruntime stack:runtime.SysMap(0xc209cd0000, 0x3b1bc0000, 0x570a00, 0x5783f8) /usr/local/go/src/runtime/mem_linux.c:149 +0x98runtime.MHeap_SysAlloc(0x57dae0, 0x3b1bc0000, 0x4296f2) /usr/local/go/src/runtime/malloc.c:284 +0x124runtime.MHeap_Alloc(0x57dae0, 0x1d8dda, 0x10100000000, 0x8) /usr/local/go/src/runtime/mheap.c:240 +0x66goroutine 1 [running]:runtime.switchtoM() /usr/local/go/src/runtime/asm_amd64.s:198 fp=0xc208518a60 sp=0xc208518a58runtime.mallocgc(0x3b1bb25f0, 0x4d7fc0, 0x0, 0xc20803c0d0) /usr/local/go/src/runtime/malloc.go:199 +0x9f3 fp=0xc208518b10 sp=0xc208518a60runtime.newarray(0x4d7fc0, 0x3a164e, 0x1) /usr/local/go/src/runtime/malloc.go:365 +0xc1 fp=0xc208518b48 sp=0xc208518b10runtime.makeslice(0x4a52a0, 0x3a164e, 0x3a164e, 0x0, 0x0, 0x0) /usr/local/go/src/runtime/slice.go:32 +0x15c fp=0xc208518b90 sp=0xc208518b48github.com/mf/ahocorasick.(*Matcher).buildTrie(0xc2083c7e60, 0xc209860000, 0x26afb, 0x2f555) /home/go/ahocorasick/ahocorasick.go:104 +0x28b fp=0xc208518d90 sp=0xc208518b90github.com/mf/ahocorasick.NewStringMatcher(0xc208bd0000, 0x26afb, 0x2d600, 0x8) /home/go/ahocorasick/ahocorasick.go:222 +0x34b fp=0xc208518ec0 sp=0xc208518d90main.main()這是 main 函數的內容（取自同一個 repo：test 文件）var dictionary = InitDictionary() var bytes = []byte(""Partial invoice (€100,000, so roughly 40%) for the consignment C27655 we shipped on 15th August to London from the Make Believe Town depot. INV2345 is for the balance.. Customer contact (Sigourney) says they will pay this on the usual credit terms (30 days).") var precomputed = ahocorasick.NewStringMatcher(dictionary)// line 66 herefmt.Println(precomputed.Match(bytes))
3 回答
慕斯709654
TA貢獻1840條經驗 獲得超5個贊
您的結構在內存方面非常低效，讓我們看看內部結構。但在此之前，快速提醒一些 go 類型所需的空間：
布爾值：1 個字節
整數：4 字節
uintptr：4 字節
[N]類型：N*sizeof(type)
[]type: 12 + len(slice)*sizeof(type)
現在，讓我們看看你的結構：
type node struct {
root bool // 1 byte
b []byte // 12 + len(slice)*1
output bool // 1 byte
index int // 4 bytes
counter int // 4 bytes
child [256]*node // 256*4 = 1024 bytes
fails [256]*node // 256*4 = 1024 bytes
suffix *node // 4 bytes
fail *node // 4 bytes
}
好的，你應該猜到這里發生了什么：每個節點的重量都超過 2KB，這是巨大的！最后，我們將查看用于初始化 trie 的代碼：
func (m *Matcher) buildTrie(dictionary [][]byte) {
max := 1
for _, blice := range dictionary {
max += len(blice)
}
m.trie = make([]node, max)
// ...
}
你說你的字典是 4 MB。如果總共是 4MB，那么就意味著在 for 循環結束時，max = 4MB. 它包含 4 MB 不同的單詞，然后max = 4MB*avg(word_length).
我們將采用第一個場景，最好的一個。您正在初始化一個 4M 節點的切片，每個節點使用 2KB。是的，這需要一個不錯的 8GB。
您應該查看如何構建您的 trie。從與 Aho-Corasick 算法相關的維基百科頁面中，每個節點包含一個字符，因此從根開始最多有 256 個字符，而不是 4MB。
一些使其正確的材料：https ://web.archive.org/web/20160315124629/http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf
阿晨1998
TA貢獻2037條經驗 獲得超6個贊
該node類型的內存大小為2084字節。我寫了一個小程序來演示內存使用情況：https: //play.golang.org/p/szm7AirsDB
如您所見，三個字符串（大小為 11(+1) 個字節）dictionary := []string{"fizz", "buzz", "123"}需要 24 MB 內存。
如果您的字典有 4 MB 的長度，您將需要大約4000 * 2084 = 8.1 GB內存。
因此，您應該嘗試減小字典的大小。
- 3 回答
- 0 關注
- 691 瀏覽
添加回答
舉報
0/150
提交
取消