I have read Crossword Puzzles and Constraint Satisfaction by Connor, Duchi and Lo and I am trying to implement this variation of crossword solving algorithm. I can't understand the bit array data structure described on page 3, under "Lexicon". Could someone please give me an example?

PS: I have already implemented an efficient crossword solving algorithm but now I want to get even more serious in this difficult task.


Suppose we are looking for the set of all words of length 5 with a in first position and b in second position (an example is the word about).

Our lexicon contains up to $N = 2000$ words of each length. For each length, for each position in the word, and for each possible letter, we store the set of words of given length in which the letter at the given position is the given letter.

For example, suppose that there are 100 words of length 5. We identify these words with the numbers 1,2,...,100. There is an array of length 100 in which the $i$'th value is 1 if the $i$'th word starts with a, and 0 otherwise. There is another array of length 100 in which the $i$'th value is 1 if the second letter of the $i$'th word is b, and 0 otherwise. We can take these two arrays and compute their entrywise AND: $$ \begin{array}{l|l} \text{First array} & 01110010\ldots \\ \text{Second array} & 11010011\ldots \\\hline \text{Result} & 01010010\ldots \end{array} $$ The $i$'th value of the new array is 1 iff the $i$'th word starts with ab.

Bit arrays are a space-efficient way to store Boolean arrays like the two arrays considered above, which also support fast operations like bitwise AND. The idea is simple – you store every value as one bit.


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.