I have a set of words $D$, and I make compound words by concatenating a fixed number $n$ of words from $D$ (repetitions are allowed). Let's call such words $n$-compounds. I want to know how many distinct compound words can be formed, and how many $n$-compounds can be formed in $a$ ways for each value of $a$. For example, if $D$ is {hell, hello, open, pen} and $n=2$, the compound word hellopen can be formed as hell + open or hello + pen, so there are 16 distinct pairs of words in $D$, but only 15 distinct 2-compound words over $D$.

Formally, let $\mathscr A$ be a finite alphabet of size $\ge 2$, $D$ a finite set of words of length $\ge 2$ over $\mathscr A$, and $n \ge 2$ an integer. The set of valid $n$-compound word is $C = \{ u_1 \ldots u_n \mid (u_1, \ldots, u_n) \in D^n \}$. Let's call ambiguity of a word $w$ the number of $n$-tuples $(u_1, \ldots, u_n) \in D^n$ such that $u_1 \ldots u_n = w$. (So an ambiguity of 0 means that the word is not in $C$, an ambiguity of 1 means that the word can be decomposed uniquely, and larger ambiguities mean words that can be formed in multiple ways.)

I would like to calculate the number of distinct compound words, i.e. the size of $C$. I'm also interested in the number of words with ambiguity $a$ for each value of $a$, and especially the number of unambiguous compounds ($a=1$). This can obviously be done by enumerating all $|D|^n$ combinations and storing their multiplicity in a multiset structure, but that has a huge memory and time cost. Is there a better way? I have a feeling it would help to build a set of prefixes and suffixes, but I can't figure out how to chain those together.

If the exact calculation is impractical, I would be satisfied with an estimate. How can I sample my dictionary to get a reliable estimate? Also, if there's a method that works well except in some pathological cases, and it's possible to avoid those pathological cases by removing a few words from $D$, that's still fine for my application.

I am specifically interested in the following practical use case: $D$ is a set of a few thousand common English words (all lowercase), and $n$ is about 3 to 8. The application is the generation of “correct horse battery staple” style passwords: how much bias is introduced if you don't put spaces between words?


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.