# Dictionary matching problem: dictionary size estimation

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?

• It seems like you want to estimate $n$ given $d$, and not the other way around. – Yuval Filmus Oct 12 '17 at 9:05
• @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. – Nikita Sivukhin Oct 12 '17 at 12:13
• 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? – D.W. Oct 12 '17 at 17:59
• @D.W. yes, dictionary size = number of patterns – Nikita Sivukhin Oct 13 '17 at 3:36