Suppose we solve dictionary matching problem for $d$ patterns with the Aho-Corasick algorithm. Then our main data structure consists of a trie with $n$ vertices and auxiliary structures. I want to estimate the dictionary size $d$ via $n$. It seems reasonable that $d = o(n)$, but maybe there is some research, that provides more accurate estimation of dictionary size based on real data.

So, what estimation for $d$ via trie size $n$ fit reality the best?

  • $\begingroup$ It seems like you want to estimate $n$ given $d$, and not the other way around. $\endgroup$ – Yuval Filmus Oct 12 '17 at 9:05
  • $\begingroup$ @YuvalFilmus I prefer estimation of $d$ via $n$ (for example $d = o(\frac{n}{\log n}))$, because I want to know how much smaller $d$ than $n$ for analyzing bottlenecks in algorithm space overhead. But estimation in reverse direction can be helpful too. $\endgroup$ – Nikita Sivukhin Oct 12 '17 at 12:13
  • $\begingroup$ In one part of the question you define $d$ as the number of patterns; in another place you define $d$ as the dictionary size. Are those the same? Is dictionary size = number of patterns? $\endgroup$ – D.W. Oct 12 '17 at 17:59
  • $\begingroup$ @D.W. yes, dictionary size = number of patterns $\endgroup$ – Nikita Sivukhin Oct 13 '17 at 3:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.