Wildcard Queries

How a dictionary answers patterns such as mon*, *mon, m*n and m*n*r. Hash tables against search trees and B-trees for prefix lookup, a tree and a reverse tree for trailing and leading wildcards, the permuterm index with its rotation rule for each query form, and the k-gram index with its Boolean query and post-filtering step. Every technique worked on twenty Reuters terms, both indexes built and measured on the whole Reuters-21578 vocabulary, and what a wildcard costs in terms and postings.

Suppose the thesis student, searching the Reuters-21578 stories, is unsure whether the wire wrote monitor, monitors or monitoring, and types mon*. The collection's dictionary, the list of its 29,187 distinct terms, holds 70 that begin with mon, from monarch to mony. The query is a request for all of them at once. How does a system find every term a pattern stands for without testing the pattern against all 29,187? It keeps the dictionary in a structure where the wanted terms lie next to each other, or it indexes the terms by the short strings they contain.

A wildcard query is a pattern in which the symbol * stands for any string of characters, including the empty one. The pattern mon* has a trailing wildcard and *mon a leading one. m*n has one wildcard in the middle, and m*n*r has two. Searchers use wildcards when they are unsure of a spelling (col*r for color and colour), when they want every variant of a word without trusting a stemmer, and when they know only part of a name. The truncation operators of professional search services, such as employ!, are trailing wildcards under another notation; Boolean Search in Practice describes them.

Here is the route, following Manning, Raghavan, and Schütze (2008, §§3.1–3.2). First we see which dictionary structures can find terms by prefix: hash tables cannot, and search trees can. Then a tree and a reversed tree answer trailing and leading wildcards. Next come the two general tools, the permuterm index and the k-gram index, each worked on twenty terms. Finally we build both for the whole Reuters vocabulary, compare their sizes and candidate sets, and count what a wildcard costs once its terms are found.

This article is the home of dictionary lookup by prefix and of both wildcard indexes. Spelling Correction and Phonetic Matching introduced the k-gram index as a filter for spelling candidates, and the same index is used here for a different purpose. Binary search in a sorted dictionary, used below, is traced step by step in The Inverted Index, the next article of the topic.

What a wildcard query asks for

Answering a wildcard query takes two steps. The first finds the dictionary terms that match the pattern. The second runs an ordinary query for those terms, joined by OR, against the index. This article is about the first step, and its last section returns to the second.

Twenty terms carry the examples. All are in the Reuters-21578 vocabulary (Lewis, 1997), lowercased and split into runs of letters as in term statistics:

amount  common  main     major  man    manner  margin   miner   minor    monday
money   monitor month    motion red    reduce  retired  salmon  salomon  simon

Testing every term against each pattern gives the answers that every method below must reproduce:

Pattern Matching terms
mon* monday, money, monitor, month
*mon common, salmon, salomon, simon
m*n main, man, margin, motion
m*n*r manner, miner, minor, monitor
*mon* common, monday, money, monitor, month, salmon, salomon, simon
red* red, reduce
ma*an none

That test, one pattern match per term, is the baseline. It costs 20 matches here, 29,187 on Reuters, and millions on a web-scale dictionary, for every query. The structures below find the same terms while looking at far fewer.

Dictionaries: hash tables and search trees

Whether a pattern can be answered quickly depends first on how the dictionary is stored. The course text names two families of structures (Manning, Raghavan, and Schütze, 2008, §3.1).

A hash table computes from each term an integer, its hash, and stores the term's entry at the position the integer names. Looking up a term means hashing it and going to that position, which takes constant expected time however large the dictionary is. What a hash table cannot do follows from the same design:

  • No prefix lookup. Similar terms receive unrelated integers, so monday and money are stored far apart. Nothing in the table leads from one term beginning with mon to the next. A pattern can only be answered by examining every entry.
  • No near matches. For the same reason the table cannot find the terms just before or after a string that is not in it, which a spelling corrector or a range query needs.
  • Growth. A hash function sized for today's vocabulary may not suit a much larger one, and the vocabulary of a growing collection keeps growing (Heaps' law), so the table must be rebuilt from time to time.

A search tree keeps the terms in sorted order. In a binary tree each node holds a term; smaller terms are in its left subtree and larger ones in its right. A lookup starts at the root and goes left or right at each node. If the tree is balanced, so that the two subtrees of every node hold nearly equal numbers of terms, a lookup among $M$ terms takes about $\log_2 M$ comparisons. Keeping a binary tree balanced while terms are inserted and deleted is the cost of the design.

A B-tree eases that cost by letting the number of children of a node vary. Every internal node has between $a$ and $b$ children, for fixed integers $a$ and $b$, and holds the keys that separate them. An insertion that overfills a node splits it, and the change spreads upward only when a parent overfills in turn (Bayer and McCreight, 1972). The course text's example has $a = 2$ and $b = 4$. On disk, $a$ and $b$ are chosen so that one node fills one disk block. A lookup then reads one block per level, and a tree with hundreds of children per node has very few levels. A search tree requires only that the characters of the terms have an agreed order.

What a tree offers that a hash table does not is that terms with a common prefix are neighbors.

Claim. Let $p$ be a nonempty string whose last character is not the largest character of the alphabet, and let $p^{+}$ be $p$ with its last character replaced by the next character of the alphabet. A term $t$ begins with $p$ if and only if $p \le t < p^{+}$ in dictionary order.

Proof. Suppose $t$ begins with $p$. Then $t \ge p$, since a string is never smaller than its own prefix. And $t < p^{+}$, because $t$ and $p^{+}$ agree before the last position of $p$ and there $t$ has the smaller character.

Conversely, suppose $p \le t < p^{+}$ and $t$ does not begin with $p$. Since $t \ge p$, $t$ is not a proper prefix of $p$, so the two strings first differ at some position $i$ of $p$, and $t$ has the larger character there. If $i$ is before the last position of $p$, then $p^{+}$ agrees with $p$ up to and at position $i$, so $t > p^{+}$, which contradicts $t < p^{+}$. If $i$ is the last position of $p$, the character of $t$ there is larger than the last character of $p$, so it is at least the last character of $p^{+}$. Then $t \ge p^{+}$, again a contradiction. $\blacksquare$

Prefixes that end in the largest character. With the alphabet a to z, the prefix mz has no $p^{+}$ of this kind, since nothing follows z. Write such a prefix as $p = q z^m$, where $q$ does not end in z and $m \ge 1$. If $q$ is not empty, the upper end is $q^{+}$: a term begins with $p$ if and only if $p \le t < q^{+}$. For mz that is mz $\le t <$ n. If $q$ is empty, as for the prefix z, there is no upper end, and the terms are those with $t \ge p$, to the end of the dictionary.

Proof. A term that begins with $p$ is at least $p$. It also begins with $q$, so it is below $q^{+}$ by the claim. Conversely, let $t \ge p$, and let $t < q^{+}$ if $q$ is not empty. Since $q \le p \le t$, the claim gives that $t$ begins with $q$, which holds trivially if $q$ is empty. Write $t = q w$. Then $t \ge q z^m$ means $w \ge z^m$. A string that is not below $z^m$ must begin with $z^m$: if it differed from $z^m$ at one of the first $m$ positions it would have a smaller character there, since z is the largest, and if it were a proper prefix of $z^m$ it would be smaller as well. So $w$ begins with $z^m$ and $t$ begins with $p$. $\blacksquare$

So the terms with a given prefix form one unbroken run of the sorted order, and two lookups find its ends. The script checks both rules against a plain test of every term for 609 prefixes of the Reuters vocabulary, more than 300 of them ending in z.

The prefix lookup worked

In the sorted list of the twenty terms, numbered from 0, the prefix $p$ is mon and $p^{+}$ is moo. A binary search for mon ends at position 9, the first term not smaller than it, which is monday. A binary search for moo ends at position 13, which is motion. The terms at positions 9 to 12 are the answer: monday, money, monitor, month. The term before the run is minor and the term after it is motion.

The same lookup in a small B-tree shows what a disk-based dictionary does. The tree below holds the twenty terms in leaves of three, with at most four children per node. Internal nodes hold separators, each the smallest term of the subtree to its right. This layout, with all the terms in the leaves and each leaf linked to the next, is the variant usually called a B+-tree (Comer, 1979).

root:    [ month ]
level 2: [ major | margin | monday ]                      [ reduce | salomon ]
leaves:  (amount common main) (major man manner)          (month motion red)
         (margin miner minor) (monday money monitor)      (reduce retired salmon) (salomon simon)

The search for mon makes these steps:

Node Comparison Move to
Root, separator month mon is before month the left child
Level 2, separators major, margin, monday mon is after major and margin, before monday the third leaf
Leaf (margin, miner, minor) all three are before mon the next leaf
Leaf (monday, money, monitor) all three begin with mon the next leaf
Leaf (month, motion, red) month begins with mon; motion is not before moo stop

Two internal nodes and three leaves are read, and the four answers are collected in order. The work is one descent of the tree plus a walk along the leaves that hold the answers.

On the Reuters vocabulary the same two binary searches land at positions 16,772 and 16,842 of the sorted dictionary. The 70 terms between them are the answer to mon*, preceded by momentum and followed by mood. Each search takes at most 15 steps, since $2^{14} \le 29{,}187 < 2^{15}$.

Trailing and leading wildcards: a tree and a reverse tree

A trailing wildcard is exactly the prefix lookup just worked. A leading wildcard is the same problem read backwards.

Leading wildcards. Keep a second tree, the reverse tree, that holds every term written backwards. A term ends with mon exactly when its reversal begins with nom. The twenty reversed terms, sorted, are

der     deriter  ecuder  htnom   nam     niam     nigram  noitom  nomis   nomlas
nommoc  nomolas  renim   rennam  rojam   ronim    rotinom tnuoma  yadnom  yenom

and the prefix nom selects positions 8 to 11: nomis, nomlas, nommoc, nomolas. Reversed again, they are simon, salmon, common, salomon, the answer to *mon.

One wildcard in the middle. For m*n, use both trees and intersect. The forward tree gives the terms that begin with m, twelve of the twenty. The reverse tree gives the terms that end with n: common, main, man, margin, motion, salmon, salomon, simon. Four terms are in both sets: main, man, margin, motion. The course text describes the method with the pattern se*mon: a B-tree finds the terms with prefix se, a reverse B-tree those with suffix mon, and the two sets are intersected (Manning, Raghavan, and Schütze, 2008, §3.2).

The intersection is correct only with one further test.

Example (a common misstatement). "The terms matching X*Y are the terms with prefix X and suffix Y" is false when the prefix and the suffix can overlap. The pattern ma*an asks for ma, then anything, then an, so a matching term has at least four letters. The term man begins with ma and ends with an, and it has three letters: its a serves as the end of the prefix and the start of the suffix. The intersection of the two trees' answers is therefore man, and the true answer on the twenty terms is empty. The precise statement is that a term matches X*Y exactly when it begins with X, ends with Y, and has at least as many characters as X and Y together. A term with those three properties is X, then its middle characters, then Y. On the Reuters vocabulary the two trees return 14 terms for ma*an, and the length test removes one, man, leaving the 13 that match, such as malaysian and manhattan.

The intersection has a cost that the answer does not show. For m*n on Reuters the forward tree returns 1,708 terms and the reverse tree 2,689, to produce 159 matches. Both sets must be enumerated in full before they are intersected. A pattern with two wildcards, such as m*n*r, can use the trees only for its first and last pieces and must then test each survivor against the whole pattern. The two indexes that follow were designed to do better.

The permuterm index

Here is the idea in one sentence. If every term is stored in all its rotations, then any pattern with one wildcard can be rotated until the wildcard is at the end, and the query becomes a prefix lookup.

Construction. Add the symbol $ to the end of each term to mark where it ends. A rotation moves characters from the front of the string to the back. The term man becomes man$, which has four rotations:

man$   an$m   n$ma   $man

and money has six: money$, oney$m, ney$mo, ey$mon, y$mone, $money. The permuterm index is a search tree that holds every rotation of every term, each pointing back to the term it came from. A term of $n$ letters contributes $n + 1$ rotations. The twenty terms have 109 letters and so 129 rotations.

The rotation rule. Write the query pattern with $ at its end and rotate it until the * is the last character. What stands before the * is the prefix to look up:

Query form Example Look up the rotations that begin with
X (no wildcard) money money$, as a whole key
X* mon* $mon
*X *mon mon$
X*Y m*n n$m
*X* *mon* mon
X*Y*Z m*n*r r$m, then test each term found

For m*n, the pattern with its end marker is m*n$, and rotating it to bring the * to the end gives n$m*.

Why the rule is correct for one wildcard. Take the form X*Y; the forms X* and *Y are the cases where Y or X is empty.

Proof. Suppose the term $t$ matches X*Y, so that $t$ is X, then some string $u$, then Y. Its marked form is X $u$ Y $, and the rotation that starts at Y is Y $ X $u$, which begins with Y$X.

Conversely, suppose some rotation of the marked form of $t$ begins with Y$X. The rotation is the last part of $t$, then $, then the first part of $t$, and it contains only one $. So the $ of the key is that $: the last part of $t$ is exactly Y, and the first part of $t$ begins with X. Hence $t$ is a string beginning with X followed by Y, which matches X*Y. $\blacksquare$

The proof also shows that no length test is needed: the part of $t$ before Y and the part that is Y are separate pieces of $t$.

For *X*, a rotation begins with X exactly when X occurs somewhere in the term. The key contains no $, so it lies inside the term and cannot run across the end marker.

Worked on the twenty terms. For m*n the key is n$m. In the sorted list of 129 rotations, four begin with it:

Rotation Term
n$ma man
n$mai main
n$margi margin
n$motio motion

These are the four answers, found by one prefix lookup, with no second set to enumerate.

For ma*an the key is an$ma. The term man has the rotation an$m, which is shorter than the key and does not begin with it. No rotation does, and the lookup returns nothing, which is the correct answer.

For *mon* the key is mon, and eight rotations begin with it: mon$com, mon$sal, mon$salo, mon$si, monday$, money$, monitor$, month$. They point to the eight terms of the table above. A term that contains the key twice is reached twice. For *m*, the term common is reached through mmon$co and through mon$com, so the 18 rotations found point to 17 distinct terms, and duplicates must be removed.

Several wildcards. For m*n*r, rotate so that the last wildcard is at the end and ignore what lies between the first and the last: the key is r$m, the lookup for m*r. It returns major, manner, miner, minor and monitor. Each is then tested against the full pattern, and major, which has no n between its m and its r, is dropped. The course text's example is fi*mo*er: the lookup for er$fi returns terms such as fishmonger and filibuster, and the test for mo in the middle keeps the first and rejects the second (Manning, Raghavan, and Schütze, 2008, §3.2.1).

The size cost. The permuterm index holds one key for every letter of every term, and one more per term. On the Reuters vocabulary that is $203{,}992 + 29{,}187 = 233{,}179$ rotations, 7.99 for each term. If every rotation is stored in full, the keys take 2,079,293 characters, 10.2 times the 203,992 characters of the terms themselves. The course text names this as the index's disadvantage (§3.2.1) and puts the increase for a dictionary of English terms at almost tenfold (§3.2.2), close to the 10.2 measured here. It credits Garfield (1976) with one of the first complete descriptions. Garfield's Permuterm Subject Index permuted pairs of title words, not the characters of a term, and the character-rotation index of this article borrows its name. Ferragina and Venturini (2007) show how to store a permuterm index in compressed form.

The k-gram index

The second tool needs no rotations. Here is the idea in one sentence. A term that matches a pattern must contain every short piece of the pattern, so an index from short pieces to terms narrows the search to a few candidates, which are then checked.

Construction. A k-gram is a sequence of $k$ characters. Write each term with $ at both ends and take every run of $k$ consecutive characters. With $k = 2$, the term man, written $man$, has the bigrams $m, ma, an, n$. With $k = 3$, the term money has the trigrams $mo, mon, one, ney, ey$. The k-gram index maps each k-gram to the sorted list of terms that contain it. It is an inverted index whose "documents" are the dictionary's terms. For the twenty terms the bigram index has 60 distinct bigrams and 128 postings, and the trigram index has 75 trigrams and 109 postings. Spelling correction builds the same structure and uses it to count shared k-grams.

The Boolean query. Write the pattern with $ at both ends, cut it at each *, and take the k-grams of each piece. The pattern mon* becomes $mon and an empty piece. With bigrams the query is

$m AND mo AND on

The three postings lists on the twenty terms are:

Bigram Terms
$m main, major, man, manner, margin, miner, minor, monday, money, monitor, month, motion
mo amount, common, monday, money, monitor, month, motion, salmon, salomon, simon
on common, monday, money, monitor, month, motion, salmon, salomon, simon

Their intersection has five terms: monday, money, monitor, month and motion.

Why a post-filtering step is needed. Motion does not begin with mon. It is in the intersection because it begins with m, contains mo at its start, and contains on at its end. The Boolean query says that each k-gram occurs somewhere in the term. It does not say that they occur next to each other, in order, at the place the pattern requires. Every candidate must therefore be checked against the original pattern by an ordinary string match, and those that fail are discarded. This is the post-filtering step. The candidates are few, so the check is cheap, but it cannot be left out.

The course text's example uses trigrams. The pattern red* gives the query $re AND red. The term retired contains both: $re at its start and red at its end. It is returned by the Boolean query and does not match red* (Manning, Raghavan, and Schütze, 2008, §3.2.2). On the twenty terms the trigram query returns red, reduce and retired, and the filter keeps the first two. On the whole Reuters vocabulary it returns 70 terms, of which 54 begin with red. The 16 false candidates are retired and fifteen others of the same shape, among them required, referred, recovered and restored.

For mon* the two values of $k$ behave differently on Reuters. The bigram query returns 90 candidates for 70 matches. Its 20 false candidates include motion, morton and morrison, each beginning with mo and containing on later. The trigram query $mo AND mon returns exactly the 70 matches. That is an observation about this vocabulary, not a guarantee: a term such as mormon, which is not in the collection, contains both trigrams and does not begin with mon.

Short pieces. A piece of the pattern shorter than $k$ yields no k-gram. For m*n the pieces are $m and n$, two characters each. With bigrams the query is $m AND n$, which returns exactly main, man, margin and motion. With trigrams there is no query at all, and every term of the dictionary is a candidate. A larger $k$ filters better when the pieces are long and cannot be used when they are short.

Overlap. The pattern ma*an gives the bigram query $m AND ma AND an AND n$. The term man has all four bigrams and is returned. The post-filter removes it, for the reason given in the misstatement above. The k-gram index never needs a separate length test, because the string match already makes it.

The two indexes measured

Both indexes were built for the whole Reuters-21578 vocabulary by the script tools/experiments/textproc/wildcard_queries.py, which also answers every pattern with a forward and a reverse sorted dictionary. Every answer is compared with a brute-force regular-expression match over all 29,187 terms.

Size

Structure Keys Entries Bytes Relative to the terms as one string
Permuterm, rotations stored in full 233,179 233,179 3,012,009 5.7
Permuterm, as (term, offset) pairs 233,179 233,179 1,165,895 2.2
Bigram index 699 231,108 928,626 1.8
Trigram index 9,059 203,831 878,737 1.7

The byte counts follow a simple model, not a real file format: one byte per character, four bytes for a pointer or a term number, and no compression.

  • A rotation stored in full costs its characters plus a 4-byte pointer to its term.
  • A rotation stored as a pair costs a 4-byte term number and a 1-byte offset, and a comparison must then read the term.
  • A k-gram index costs 4 bytes per posting, plus $k$ characters and a pointer for each distinct k-gram.

The last column divides by 525,049 bytes, the size of the dictionary laid out as one string with pointers, the layout derived in Dictionary Compression.

Two things stand out. First, the permuterm index and the bigram index hold almost the same number of entries, 233,179 against 231,108. A term of $n$ letters has $n + 1$ rotations and also $n + 1$ bigrams, fewer when a bigram repeats within the term. The indexes differ in what an entry is: a string key in a sorted structure, or an integer in a postings list. Second, the bigram index needs only 699 keys, of the $27^2 = 729$ pairs of the 26 letters and $, and the trigram index 9,059 of 19,683. The longest postings lists are those of s$, with 4,854 terms, and ed$, with 2,043. Under this model the permuterm index with full rotations is 3.2 times the size of the bigram index, and with pairs 1.26 times.

Candidates

For the patterns of this article, the number of terms each index hands to the final check:

Pattern Matches Permuterm candidates Bigram candidates Trigram candidates
mon* 70 70 90 70
*mon 16 16 40 22
m*n 159 159 159 29,187
m*n*r 31 119 119 29,187
*mon* 162 162 197 162
red* 54 54 235 70
ma*an 13 13 22 14

The permuterm index returns exactly the matches for every pattern with one wildcard, as the proof says it must. For m*n*r it returns the 119 terms that match m*r and relies on the check. The k-gram indexes return supersets that are close when the pieces are long enough to give several k-grams, and the trigram index returns the whole dictionary when no piece has three characters.

A larger sample gives the same picture. The script cuts 1,000 patterns of five forms out of randomly chosen Reuters terms, 200 of each form, with random seed 790; some mix pieces of two terms so that they match nothing. All four methods return exactly the regular expression's answer for every one of the 1,000.

Form Mean matches Mean candidates, permuterm Mean candidates, bigram Patterns with no trigram
X* 475.4 475.4 482.8 46 of 200
*X 905.9 905.9 923.2 46 of 200
X*Y 29.0 29.0 30.0 26 of 200
X*Y*Z 15.1 157.5 33.1 200 of 200
*X* 462.2 462.2 476.4 64 of 200

For the forms with one wildcard, the permuterm candidates are the matches, and 97 to 98 percent of the bigram candidates match. For two wildcards the order reverses. The permuterm lookup uses only the first and last pieces, and 10 percent of its candidates match. The bigram query uses all three pieces, and 46 percent of its candidates match. The trigram index could not be used for 382 of the 1,000 patterns, including all 200 with two wildcards, because the pieces of these patterns are short, one to four characters. Where it could be used on a pattern with a single piece, it returned almost only matches: 100 percent, after rounding, for the forms X*, *X and *X*. These shares describe this sample of short patterns on this vocabulary and are not general constants.

What wildcard queries cost in practice

Finding the terms is the smaller part of the work. Each matching term then has its own postings list, the list of documents that contain it, and the query is the OR of all of them. On Reuters-21578, with 725,793 postings in all:

Pattern Matching terms Postings to read Share of the index Distinct documents
mon* 70 2,946 0.4% 2,222
*mon 16 781 0.1% 770
m*n 159 6,148 0.8% 5,474
m*n*r 31 788 0.1% 747
s* 2,990 72,247 10.0% 10,342
*s 4,854 121,279 16.7% 10,679
*e* 16,373 348,202 48.0% 10,719

A selective pattern costs little. A careless one, such as a single letter and a *, reads a tenth of the index and returns 10,342 of the 10,788 stories, an answer of no use to anyone. The cost is set by how many terms the pattern expands to, and the searcher rarely knows that number in advance.

Systems respond in three ways.

  • They limit where the wildcard may stand. Lucene's documentation of its wildcard query warns that the query can be slow because it must iterate over many terms, and advises against patterns that begin with * (Apache Software Foundation, Lucene documentation). Solr offers a filter that also indexes each term reversed, so that a leading wildcard becomes a trailing one, which is the reverse tree of this article (Apache Software Foundation, Solr Reference Guide).
  • They limit the expansion. This site's own search accepts a trailing wildcard only, after at least two letters. It finds the matching words by binary search in a sorted list, as in the prefix lookup above, and keeps the index terms of the most frequent of them, at most 64 (16 in the instant results shown while a query is typed).
  • They keep the feature out of the way. The course text observes that engines which support wildcards combined with Boolean operators tend to place them behind an advanced interface that most users never see, because exposing them encourages users to type wildcards they do not need, such as a prefix followed by *, which increases the load on the engine (Manning, Raghavan, and Schütze, 2008, §3.2.2).

One more point follows from where the pattern is matched. A wildcard is matched against the dictionary's terms, so on an index of stems it matches stems, not the words of the text. The Reuters vocabulary of this article is unstemmed. A system that stems and also offers wildcards on whole words keeps the unstemmed words as well, as this site's search does with its sorted list of surface words.

Worked problems

The first four problems are exercises from chapter 3 of the course text (Manning, Raghavan, and Schütze, 2008), restated and solved in our own words. The fifth is posed on this article's twenty terms. The script checks every answer.

Problem 1 (Exercise 3.1 of the course text). In the permuterm index each rotation points to the term or terms it was derived from. How many terms can one rotation point to?

Solution. Exactly one. A rotation of a marked term contains the end marker $ once, since terms contain no $. Let the rotation be $u$, then $, then $v$. It arose by moving a front part of the marked term to the back, so the marked term is $v$, then $u$, then $, and the term is $v$ followed by $u$. The rotation therefore determines its term: move everything up to and including the $ to the back and remove the marker. Two different terms cannot share a rotation. The script confirms that the 233,179 rotations of the Reuters vocabulary are all distinct.

Problem 2 (Exercise 3.2). Write down the permuterm index entries generated by the term mama.

Solution. There are five: mama$, ama$m, ma$ma, a$mam, $mama. The marked term mama$ has five characters, and each rotation moves one more character from the front to the back. All five are different strings, although mama repeats itself, because the single $ falls in a different place in each.

Problem 3 (Exercise 3.3). Which key is looked up in a permuterm index for the query s*ng?

Solution. The key ng$s: all rotations that begin with it. The query has the form X*Y with X the letter s and Y the letters ng. Its marked form is s*ng$, and rotating the * to the end gives ng$s*. A rotation beginning with ng$s belongs to a term that ends with ng and begins with s. On the Reuters vocabulary the lookup returns 219 terms, among them saying, selling and samsung, and they are exactly the terms the regular expression finds.

Problem 4 (Exercise 3.5). For the query fi*mo*er, give the Boolean query on a bigram index. Then name a term that the permuterm lookup for this query returns but that does not satisfy the Boolean query.

Solution. The Boolean query is $f AND fi AND mo AND er AND r$, and filibuster is such a term. The pattern with its markers is $fi*mo*er$. Its three pieces $fi, mo and er$ give the bigrams $f, fi; mo; and er, r$. The permuterm lookup uses the key er$fi, which finds every term that begins with fi and ends with er. Filibuster is one, and it contains no mo, so it lacks the bigram mo and fails the Boolean query. Fishmonger passes both. On the Reuters vocabulary the permuterm lookup returns 16 candidates, filibuster among them, and its check rejects them all; the bigram query returns none. Both methods reach the same empty answer, and the bigram index does so without a check, because it used the middle piece.

Problem 5. Answer s*on on the twenty terms with the two trees, with the permuterm index, and with the bigram index.

Solution. All three give salmon, salomon, simon.

Trees. The forward tree gives the terms beginning with s: salmon, salomon, simon. The reverse tree, with the prefix no, gives the terms ending with on: common, motion, salmon, salomon, simon. The intersection is the first set. Each of its terms has at least three letters, the length of s and on together, so the length test removes nothing.

Permuterm. The key is on$s. Three rotations begin with it: on$salm, on$salom and on$sim, pointing to salmon, salomon and simon.

Bigram index. The pieces $s and on$ give the query $s AND on AND n$. The list of $s has 3 terms, that of n$ has 8, and that of on has 9. Intersecting them, starting with the shortest, leaves salmon, salomon, simon. Each is checked against the pattern and passes.

What we have learned

A wildcard query is answered in the dictionary before any document is touched. A hash table cannot help, because it scatters similar terms. A search tree can, because the terms with a given prefix form one run of the sorted order, between the prefix and the next string after it. A forward tree answers trailing wildcards, a reverse tree leading ones, and their intersection one wildcard in the middle, provided the term is long enough for the prefix and suffix not to overlap. The permuterm index turns every pattern with one wildcard into a single prefix lookup, at the price of one key for every letter of every term: 233,179 keys for the 29,187 Reuters terms. The k-gram index turns a pattern into a Boolean query over short pieces, which returns a superset that a string match must filter, as retired shows for red*. On 1,000 random patterns every method agreed with a brute-force match. The cost that matters most comes afterwards: a pattern such as s* expands to 2,990 terms and a tenth of the index.

The dictionary has now been searched by exact term, by prefix and by pattern. The next article, The Inverted Index, establishes what each dictionary entry points to: the postings lists that record which documents contain each term.

References

  • Apache Software Foundation. Apache Lucene core API documentation: WildcardQuery. https://lucene.apache.org/core/ record · 4 pages
  • Apache Software Foundation. Apache Solr Reference Guide: Filters, Reversed Wildcard Filter. https://solr.apache.org/guide/ record
  • Bayer, R., and McCreight, E. (1972). Organization and maintenance of large ordered indexes. Acta Informatica, 1(3), 173–189. record
  • Comer, D. (1979). The ubiquitous B-tree. ACM Computing Surveys, 11(2), 121–137. record
  • Ferragina, P., and Venturini, R. (2007). Compressed permuterm index. In Proceedings of SIGIR 2007, 535–542. record
  • Garfield, E. (1976). The permuterm subject index: An autobiographical review. Journal of the American Society for Information Science, 27(5–6), 288–291. record
  • Lewis, D. D. (1997). Reuters-21578 text categorization test collection, distribution 1.0. record · 9 pages
  • Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, sections 3.1–3.2. Cambridge University Press. record · 93 pages