0
$\begingroup$

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?

$\endgroup$

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.