search

hankcs / AhoCorasickDoubleArrayTrie

An extremely fast implementation of Aho Corasick algorithm based on Double Array Trie.
http://www.hankcs.com/program/algorithm/aho-corasick-double-array-trie.html
951 stars 290 forks source link

some confusion about about the double array #30

Open MountainHolder opened 5 years ago

MountainHolder commented 5 years ago

As I know the double array can be simplified as follows: base[r] + c = s check[s] = r but in you code it is implement like this: base[r] + c = s check[s] = base[r] the corespondding code is check[begin + sibling.getKey()] = begin; is it right?

hankcs commented 5 years ago

It's a variant. As long as you use the same formula in both building and searching phases, it is right.

https://github.com/hankcs/pyhanlp/blob/49202d2210d97b075e35c90aa20b9cbe3b31f413/tests/book/ch02/dat.py#L32