1
$\begingroup$

Suppose that I want to enumerate all English language words of length 5. If I've got nothing more than a check of whether an arbitrary string is an English word, I have to do 5^26 calculations. However, suppose that I can check a partial specification to see if there are any words consistent with it. By partial specification I mean an assignment of some letters to some positions, with the others free to vary. E.g. "is there a word that starts with "HO" and ends with "Y" (but has any of the 2^26 configurations of third and fourth letter)?

An obvious algorithm would be to formulate it as a 26-tree, and traverse it depth-first, stopping once a pattern was deemed not "good" (e.g. as far as I'm aware there are no five letter words in English that start with "AAA", so we can skip checking "AAAAA", "AAAAB", ..., "AAAZZ").

Is it possible to do any better (average, worst case)? How about under additional assumptions on the distribution of letters (any such learning would need to be part of the algorithm, since my actual problem is not about natural language)? As another view on the second question: what sorts of heuristics are helpful?

$\endgroup$
0
1
$\begingroup$

If I've got nothing more than a check of whether an arbitrary string is an English word, I have to do 5^26 calculations. $5^{26}$ is of order $10^{18}$, while the actual number of English words is of order $10^5$. So, depending on your application, simply enumerating all words and checking whether they satisfy the constraints may already be sufficiently efficient.

If we are talking about words of a sufficiently small length, then you can just precompute the answer in advance. I.e. word cut will be in an answer for masks ___, c__, _u_, cu_, etc. For words of length at most 5, it'll result in $\le 2^5 \cdot10^5$ memory, which is of order of few MBs.

If the length is big, then you can split the mask into two parts. For each part, we find all the answers, and then intersect them. For example, we treat mask a_b_c_d_e_ as an intersection of a_b_c|_____ and _____|_d_e_. For both submasks, we find the set of words containing this submask, and then intersect them. If the final answer is small, then, hopefully, the result for at least one of these submasks will be small. You can also try to select the positions to include into each submask randomly.

For even bigger lengths, you can split the mask into more than $2$ parts. However, you can probably use that there are not many very large words and simply enumerate them all.

$\endgroup$
1
  • $\begingroup$ Sorry if this wasn't clear, but: the actual problem isn't about English words. My question is about how to enumerate a set, but your solution seems to answer the related question of "given a set, which masks will they match"? This link lays out a notion of enumeration problems as "problems where you would like to list a finite set of typically combinatorially related elements." which seems to describe my goal. $\endgroup$
    – user39430
    Feb 4 at 20:45
0
$\begingroup$

The following paper considers your task in the general case:

Partial-Match Retrieval Algorithms. Ronald L. Rivest. SIAM Journal Computing, vol 5 no 1, March 1976.

It yields a data structure with a running time that is slightly better than enumerating all words in the dictionary and checking each to see if it meets the conditions.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.