This document goes into moderate depth on the actual operation of the eXtensible Text Framework (XTF.) This document is not an overview of the XTF system, but rather delves into some nitty-gritty details of how the system performs its tasks. The reader is encouraged to first read the XTF Deployment Guide and have a solid understanding of how data flows through the XTF servlets, both crossQuery and dynaXML, as well as through the textIndexer tool.

• Document Processing
• Query Operations and What They Do
• Term and Hit Marking
• Text Hit Scoring
• Spelling Correction
• Lazy Trees
• More Like This

When processing the source document, the textIndexer increments the position for each term it encounters in the source document. However, at sentence boundaries it incremented by five (this default can be changed), which gives the effect of penalizing matches that cross sentence boundaries. Additionally, special index pre-filter tags can increase the position (see the XTF Programming Guide for details.)

Depending on the particular wildcard, hundreds or even thousands of terms might match, so care should be taken when using these. To avoid allowing such queries to occupy the engine for long periods of time, XTF allows queries to specify a limit on the maximum number of terms to match (controlled by the workLimit attribute.) Queries that exceed the limit produce an error.

AND Query on Text

What does it mean to search for “man AND war” in the full text of all documents? Perhaps the most obvious answer would be to search for any document containing both words. But consider a document where “man” appeared in Chapter 1 and “war” appeared in Chapter 7. Would that be a document the user really wanted to find? Probably not. More likely they’d be interested in a document where “man” and “war” appear close together.

Thus XTF interprets AND queries on the full text as NEAR queries instead, with the slop factor set to the maximum for that index.

More formally, when used with terms, the AND query will match any section of text that contains all of the terms, in any order, as long as they are close together (that is, within the maximum proximity defined for the index, or 20 words in the default configuration.)

When used to group sub-queries together, AND will match text where all of the sub-queries match, in any order, as long as the matches are close together (i.e. within the maximum proximity for the index.)

OR Query on Text

When used to group terms, an OR query matches each occurrence of every term contained within it. If used to group sub-queries together, the OR query matches each occurrence of every sub-query.

PHRASE Query on Text

A PHRASE query generally contains two or more terms, and it matches any span of text where all the terms appear together, in order, with no other terms between them.

Less frequently, it can be used to group sub-queries. It matches a span of text where all of the sub-queries match, in order, without any intervening non-matching terms.

Note that a PHRASE query is equivalent to a NEAR query with a slop factor of zero.

NEAR Query on Text

Each NEAR query requires a “slop” factor. In rough terms, this factor can be thought of as limiting the amount of sloppiness when matching. A slop of zero indicates very tight control; in fact, a NEAR query with zero slop is equivalent to a PHRASE query. A large slop value indicates that terms may appear far apart, or out of order, or both. Note however that the slop value is silently constrained to the maximum proximity defined by the chunk overlap of an index.

For more details on how slop is computed, see the section on Proximity and Slop. For information on chunk overlap and how it relates to proximity searching, see the section on Chunking.

The NEAR query, when used with terms, matches a span of text containing all of the terms, where the match’s slop is less than or equal to the slop factor specified for the query.

When used to group sub-queries, it matches a span of text where all of the sub-queries match, and the complete match’s slop is less than or equal to the slop factor specified for the NEAR query.

NOT Clause on Text

A NOT clause may be specified as a sub-query of any boolean query (OR, AND, PHRASE, or NEAR). Any matches in the NOT clause will suppress outer matches within the maximum proximity of the index. This can be thought of as a “kill zone”: each match within the NOT clause kills off nearby matches.

Meta-data Query Operations

The following query operations can be applied to any meta-data field. Queries are applied to meta-data and full text in like fashion, with a few exceptions: AND queries are not proximity-based in meta-data fields, NOT clauses on meta-data can eliminate whole documents, and a new operator, RANGE, is available on meta-data fields.

TERM and Wildcard Queries on Meta-data

A TERM query matches every occurrence of the specified term in the meta-data field. Upper-case vs. lower-case distinctions are ignored. Additionally, the term may contain special wildcard characters:

Depending on the particular wildcard, hundreds or even thousands of terms might match, so care should be taken when using these. To avoid allowing such queries to occupy the engine for long periods of time, XTF allows queries to specify a limit on the maximum number of terms to match (controlled by the workLimit attribute.) Queries that exceed the limit produce an error.

RANGE Queries on Meta-data

A RANGE query is similar to a wildcard term query in that it matches a (possibly large) number of terms. Lower and upper bounding terms are specified, and every term that appears in the index lexicographically between the two bounds is matched.

For example, if the lower bound were “1895” and the upper bound were “1900”, a range query would match any of the terms 1895, 1896, 1897, 1898, 1899, and 1900. Optionally, the query can exclude the bounds, in which case it wouldn’t match 1895 nor 1900.

As in the case of wildcard queries, care must be taken to avoid searching a huge number of terms. This can happen easily: in the case of the example above, if dates were encoded in the index in the form YYYY-MM-DD, then all the days from 1895 to 1900 would match… potentially 2,190 of them. And of course a range query from A to Z would match practically every term in the index. Again, each query can specify a limit on the maximum number of terms to match, to avoid bogging down the engine.

However, when searching numeric data (for example, file time and date stamps) the above wildcard approach simply is not sufficient. To handle this, XTF provides a special numeric range searching capability. This is specified as an attribute to the normal <range> query operator, but it tells XTF that the data is numeric, and in a rigid format (such as YYYY-MM-DD:HH-MM-SS; any rigid format is acceptable). When the first such query is made, XTF loads a table of all the data values and converts them to 64-bit integers. This table is then cached in memory, and range queries on that field are processed very quickly, avoiding any wildcard-like expansion.

AND Query on Meta-data

Unlike in full-text queries, an AND query on meta-data implies no proximity restrictions. When used with terms, it matches documents where every term appears somewhere in the field, in any order.

When used to group sub-queries, it matches documents where all of the sub-queries match (note that the sub-queries may be on several different fields.)

OR Query on Meta-data

When used to group terms, an OR query matches a document where any of the terms occurs within the meta-data field.

If used to group sub-queries together, the OR query matches documents that match by any of the sub-queries (note that the sub-queries may involve several different fields.)

PHRASE Query on Meta-data

A PHRASE query generally contains two or more terms, and it matches any document where the terms appear together in the field, in order, with no other terms between them.

Less frequently, it can be used to group sub-queries. It matches any document where all of the sub-queries match, in order, without any intervening non-matching terms.

Note that a PHRASE query is equivalent to a NEAR query with a slop factor of zero.

NEAR Query on Meta-data

Each NEAR query requires a “slop” factor. In rough terms, this factor can be thought of as limiting the amount of sloppiness when matching. A slop of zero indicates very tight control; in fact, a NEAR query with zero slop is equivalent to a PHRASE query. A large slop value indicates that terms (or sub-queries) may appear far apart, or out of order, or both. There is no upper bound on the slop factor. For more details on how slop is computed, see the section on Proximity and Slop. The NEAR query, when used with terms, matches any document where all of the terms appear in the field and their group slop is less than or equal to the slop factor specified for the query.

When used to group sub-queries, it matches any document where all of the sub-queries match, and the complete match’s slop is less than or equal to the slop factor specified for the NEAR query.

NOT Clause on Meta-data

A NOT clause may be specified as a sub-query of any boolean query (OR, AND, PHRASE, or NEAR). Any documents matching the NEAR clause will be removed from the outer set of matches.

Stop Words in Queries

If a query contains one or more stop words, the query will be internally rewritten to work properly with the bi-gram system. Recall from the section on Stop Words and Bi-grams that using bi-grams allows XTF to support queries containing stop words while avoiding the usual severe impact on performance that they might have.

Here are some details on how stop words are handled in various query situations:

• In the absence of any grouping operator, querying for a single stop word in a TERM query will produce an empty result set.
• Wildcards queries will skip stop words; for example, searching for th? would not match “the” (which is a stop word), but would still match “thy”.
• Stop words are stripped out of OR queries and NOT clauses.
• By contrast, PHRASE queries retain all stop words, because users would be dismayed if a query on “man of war” returned matches on “man in war”.
• In AND and NEAR queries, stop words are joined with adjacent words to form bi-grams. The resulting query will effectively prefer matches containing the stop words in the correct places, but will allow matches where they don’t appear.

The <hit><term>dog</term> chewed on the


<term>skeleton's</term> leg <term>bone</term></hit>

The hungry
<hit hitNum="1" continues="yes">

  <term>plant</term> yearned for
</hit>
<i>
  <more hitNum="1" continues="no">

    <term>human</term>

  </more> flesh
</i>
to fill its bottomless gullet.

The hungry
<hit hitNum="1" continues="yes">

  <term>plant</term> yearned for
</hit>
<i>
  <more hitNum="1" continues="yes">

    human flesh
  </more>

</i>
<more hitNum="1" continues="no">
  to fill its <term>bottomless</term>
</more> gullet.

You can observe the scoring engine in action by enabling the explainScores attribute on the <query> element produced by your Query Parser stylesheet. See the Tag Reference for more information on how to enable this.

The following sections break down XTF’s scoring calculation like this: first we cover the common aspects shared by both meta-data and text chunk scoring, then talk about the differences, and finally take a look at how the final combined score for a document is computed.

Individual Hit Scoring

Whether a hit (another name for a single match) is in a meta-data field or within the full text of a document, the scoring for that particular hit is the same. How the scores are combined differs, and those differences are covered in later sections.

For those intimately familiar with Lucene, it will be helpful to know that XTF makes extensive use of Lucene’s “span” queries, to enable the exact identification of particular matches within a large document. XTF’s implementation of spans includes enhancements that calculate the score of each span in addition to its “slop”.

Queries on the contents of an XTF index are scored using an enhanced version of Lucene’s standard formula. The structure of the scoring formula is fixed, but one can override the calculation of the various factors by providing a Java implementation of the Similarity interface.

Plain English

• If a term appears many times in a field or chunk of a document, the match will rank higher; if it only appears a few times, the match will rank lower.
• Rare terms are given more weight than common terms.
• Any field or section of text in the document can be boosted at index time; hits in boosted sections will rank higher.
• For AND and NEAR queries, more exact matches will rank higher than sloppy matches. That is, a hit where the terms appear in order without intervening words will rank higher than an out-of-order match with many other words interspersed.
• Matches in short fields are ranked higher than those in long fields.
• In an OR query, hits that match many of the terms will rank higher than those that only match a few.

Mathematical Details

For a given query q, the score for a matching span s consisting of terms t, in field (or text chunk) f of document d, is calculated as follows:

spanScore(q,s) = sloppyFreq(s) * boost(f,d) * lengthNorm(f,d) * coord(q,s) * (sum for t in s: idf(t))

where

• sloppyFreq(s) is a factor that decreases as the sloppiness of the matching span increases. The effect is to favor more exact matches. Default implementation: 1 / (slop + 1). In the special case of OR queries, or AND queries where proximity has been disabled, slop is ignored and 1.0 is used instead.
• boost(f,d) is the boost factor (if any) applied to the field (or section of text) containing the match.
• lengthNorm(f,d) is a factor that decreases as the amount of text in the field or text chunk increases, since matches in longer fields are generally less precise. Default implementation: square root of the number of terms in the field/chunk.
• coord(q,s) is a factor based on the fraction of all query terms that are matched by the span. Spans with a higher ratio of matching terms will be ranked higher. Default implementation: number of terms matched / number of terms in query.
• idf(t) is a factor based on the number of documents or text chunks containing t. Terms that occur in fewer documents/chunks are better indicators of topic, so idf is high when t appears seldom in the index, and low when t appears often in the index. Default implementation: log(number of docs or chunks in index / number of docs or chunks containing t)

Text Hit Scoring

The full text of a document might contain thousands of individual matching spans, each of which will be scored according to the method above. How are these scores combined into a single score for the text?

Plain English

• Documents with more matches will score higher than those with few matches.
• Matches in short texts are ranked higher than those in long texts.

Mathematical Details

For a given query q, the score for all matching spans s in all text chunks of document d is calculated as follows:

textScore(q,d) = lengthNorm(d,text) * tf( sum for s in d: spanScore(q,s) )

where

• lengthNorm(d,text) is a factor that decreases as the amount of text in the document increases, since matches in longer texts are generally less precise. Default implementation: square root of the number of chunks in the document.
• tf(…) is a score factor that helps to equalize the scoring between documents with many matches and those with few matches. Default implementation: square root of the total score of the matches in d.

Meta-data Hit Scoring

The scores for multiple hits within a single meta-data field are combined in a similar manner to text hits, above.

Plain English

• Fields with more matches will score higher than those with few matches.
• Matches in short fields are ranked higher than those in long fields.

Mathematical Details

For a given query q, the score for all matching spans s in field f of document d is calculated as follows:

metaScore(q,d,f) = lengthNorm(d,f) * tf( sum for s in d.f: spanScore(q,s) )

where

• lengthNorm(d,f) is a factor that decreases as the length of the field increases, since matches in longer fields are generally less precise. Default implementation: square root of the number of terms in the field.
• tf(…) is a score factor that helps to equalize the scoring between fields with many matches and those with few matches. Default implementation: square root of the total score of the matches in d.f.

Combined Document Score

The final type of scoring XTF performs is to combine the scores of all text hits with a document with that document’s meta-data scores, to form the final score for that document. Again, the structure of this computation is fixed, but the calculations can be overridden by providing a Java implementation of the Similarity interface.

Plain English

• A document’s score is based on the sum of all the text hits within it, plus its meta-data field scores.

Mathematical Details

For a given query q consisting of meta-data queries qmf on fields f, and a text query qt, the score for a specific document d is as follows:

docScore(q,d) = textScore(qt,d) + (sum for f in d: metaScore(qmf,d,f))

where metaScore and textScore are computed as outlined in the previous two sections.

In the following sections, we’ll discuss the guts of XTF’s spelling correction system, detailing some strategies that were considered and the final strategy selected, the methods that XTF uses to come up with high-quality suggestions, and how the dictionary is created and stored. If you’re looking for information on configuring and using the system, see the Programming Guide.

Choosing an Index-based Strategy

We considered three strategies for spelling correction, each deriving suggestions from a different kind of source data.

1. Fixed Dictionary: Available software, such as GNU Aspell, makes spelling corrections based on one or more fixed, pre-constructed dictionaries. But the bibliographic data in our test bed and our sample queries from a live university library catalog were multilingual and contained a substantial proportion of proper nouns (e.g. names of people or places). This ruled out a fixed dictionary, since many of these proper nouns and foreign words wouldn’t be present in any standard dictionary.
2. Query Logs: In this method, we would compare the user’s query to an extensive set of prior queries, and suggest alternative queries which resulted in more hits. Unfortunately, our test system had a limited number of users, and there was no feasible way to get hold of the millions of representative queries this strategy would require, so it was ruled out as well.
3. Index-based Dictionary: Here we would make suggestions using an algorithm that draws on terms and term frequency data from the XTF index itself. It resembles the first approach except that the dictionary is dynamically derived from the actual documents and their text.

Because of the issues identified with the other strategies, we opted to pursue the index-based approach. We feel it is best for most collections in most situations, as it adapts to the documents most germane to the application and users, and doesn’t require a long query history to become effective.

We set ourselves a goal of getting the correct suggestion in the #1 position 80% of the time, which seemed a good threshold for the system to be truly useful. With several iterations and many tweaks to the algorithm, we were able to achieve this goal for our sample data set and our sample queries (drawn from real query logs). We have a fair degree of confidence that the algorithm is quite general and should be applicable to many other data sets and types of queries.

Correction Algorithm

XTF builds a spelling correction dictionary at index-time. If a query is sent to crossQuery and results in only a small number of hits (the threshold is configurable), XTF consults the dictionary to make an alternative spelling suggestion. Here is a brief outline of the algorithm for making a suggestion:

1. For each word in the query, make a list of candidate suggestions.
2. Rank the suggestions and pick the best one (details below).
3. For multi-word queries, consider pair frequencies to improve quality.
4. Suppress near-identical suggestions, and ensure that the final suggestion increases the number of hits.

Each of these will be considered in more detail below.

Which Words to Consider?

This algorithm relies (as most other spelling algorithms do) on a sort of “shot-gun” approach: for each potentially misspelled word in the query, they make a long list of “candidate” words, that is, words that could be suggested as a correction for the original misspelled word. Then the list of candidates is ranked using some sort of scoring formula, and finally the top-ranked candidate is presented to the user.

One might naively attempt to scan every word in the dictionary as a candidate. Unfortunately, the cost of scoring each one becomes prohibitive when the dictionary grows beyond about ten thousand words. So a strategy is needed to quickly come up with a list of a few hundred pretty good candidates. XTF uses a novel approach that gives good speed and accuracy.

We began with a base of existing Java spelling correction code that had been contributed to the Lucene project (written by Nicolas Maisonneuve, based on code originally contributed by David Spencer). The base Lucene algorithm first breaks up the word we’re looking for into 2, 3, or 4-character n-grams (for instance, the word primer might end up as: ~pri prim rime imer mer~ ). Next, it performs a Lucene OR query on the dictionary (also built with n-grams), retaining the top 100 hits (where a hit represents a correctly spelled word that shares some n-grams with the target word). Finally, it ranks the suggestions according to their edit distance to the original misspelled word. Those that are closest appear at the top. (“Edit distance” is a standard numerical measure of how far two words are from each other and is defined as the number of insert, replace, and delete operations needed to transform one word into the other.)

Unfortunately, the base method was quite slow, and often didn’t find the correct word, especially in the case of short words. However, we made one critical observation: In perhaps 85-90% of the cases we examined, the correct word had an edit distance of 1 or 2 from the misspelled query word; another 5-10% had an edit distance of 3, and the extra edit was usually toward the end of the word. This observation intuitively rings true: the suggested word should be relatively “close” to the query word and those that are “far” away needn’t even be considered.

Still, one wouldn’t want to consider all possible one- and two-letter edits as it would still take a long time to check if all those possible edits were actually in the dictionary. Instead, XTF checks all words in which four of the first six characters match in order. This effectively checks for an edit distance of two or less at the start of the word.

Take for example the word GLOBALISM. Here are the 15 keys that can be created by deleting two of the first six characters:

• OBAL

  (deleted characters 1 and 2)

• LBAL
  (deleted characters 1 and 3)

• LOAL
  (deleted characters 1 and 4)

• LOBL
  (deleted characters 1 and 5)
• LOBA
  (deleted characters 1 and 6)
• GBAL
  (deleted characters 2 and 3)

• GOAL
  (deleted characters 2 and 4)
• GOBL

  (deleted characters 2 and 5)

• GOBA
  (deleted characters 2 and 6)

• GLAL
  (deleted characters 3 and 4)

• GLBL
  (deleted characters 3 and 5)
• GLBA
  (deleted characters 3 and 6)
• GLOL
  (deleted characters 4 and 5)

• GLOA
  (deleted characters 4 and 6)
• GLOB

  (deleted characters 5 and 6)

So, XTF checks each of the 15 possible 4-letter keys for a given query word, and makes a merged list of all the words that share those same keys. This combined list is usually only a few hundred words long, and almost always contains within it the golden “correct” word we’re looking for.

Ranking the Candidates

Given a list of candidate words, how does one find the “right” suggestion? This is the heart of most spelling algorithms and the area that needs the most “tweaking” to achieve good results. XTF’s ranking algorithm is no exception, and makes decisions by assigning a score to each candidate word. The score is a sum of the following factors:

1. Edit distance. The base score is calculated from the edit distance between the query word and the candidate word. The usual edit distance algorithm (which considers only insertion, deletion, and replacement) is supplemented by reducing the “cost” of transposition and double-letter errors. Those types of errors are very common spelling mistakes, and reducing their cost was shown by our testing to improve suggestion accuracy. In math terms, the base score is calculated as:

1.0 – (editDistance / queryWord.length).

1. Metaphone. Originally developed by Lawrence Philips, the Double Metaphone algorithm is a simple phonetic mapping that transforms any English word into a 4 character code (called a “metaphone”). Words that have the same code are assumed to be phonetically similar. In XTF’s spelling system, if the metaphone of the candidate word matches that of the query word, the score is nudged upward by 0.1. (Note: Philips’ algorithm actually produces two codes, primary and secondary, for a given input word; XTF only compares the primary code.)
2. First/last letter. If the first and last letters of the candidate word match those of the query word, then the score is nudged upward by 0.1. Again, testing showed that this approach boosted overall accuracy.
3. Frequency. Because the indexes do contain misspelled words, we further boost the score if the suggested word is very common. The boost ranges from 0.01 to 0.2, and is arrived at by a slightly complex method, but basically more frequent candidate words get higher boosts. This has the effect of favoring common words over uncommon words (other factors being equal), which helps to avoid ridiculous suggestions.

The original query word itself is always considered as one of the candidates. This is to reduce the problem of suggesting replacements for correctly spelled words. However, the score of the query word is reduced slightly in case a more common word is found that is very similar.

In summary, for a single-word query, the list of all candidates is ranked by score, and the one with the highest score wins and is considered the “best” suggestion for the user.

Multi-word Correction

But what about queries with multiple words? Testing showed that considering each word of a phrase independently and concatenating the result got plenty of important cases wrong. For instance, consider the query untied states. Actually, each of these words is spelled correctly, but it’s clear the user probably meant to query for united states. Also, consider the word harrypotter… the best single-word replacement might be hairy, but that’s not what the user meant. How do we go beyond single-word suggestions?

We need to know more than just the frequency of the words in the index; we need to know how often they occur together. So when XTF builds the spelling dictionary, it additionally tracks the frequency of each pair of words as they occur in sequence.
Using the pair frequency data, we can take a more sophisticated approach to multi-word correction. Specifically, XTF tries the following additional strategies to see if they yield better suggestions:

1. For each single word (e.g. harrypotter) we consider splitting it up into pairs and see if any of those pairs has a high frequency. For example we’d check <har rypotter>, <harr ypotter>, <harry potter>, etc. and get a solid hit on that last one. That “hitting” takes the form of a higher score boost based on the pair frequency.
2. For each consecutive pair of words, we fetch the top 100 single-word suggestions for both words in the pair. Then we consider all possible combinations of a word from the first list vs. a word from the second list (that’s 10,000 combinations) to see if any of the combinations are high-frequency pairs. So in the example of <untied states>, one of the suggestions for untied will certainly be united and we’ll discover that <united states> as a pair has a high frequency. So we boost the score for united, and it ends up winning out against the other candidates.
3. Finally, we consider joining each pair of words together. So if a user accidentally queries for <uni lateralism>, we have a good chance of suggesting unilateralism.

All of these strategies are attempted and, just as in single-word candidate selection, each phrase candidate is scored and ranked. The highest scoring phrase wins.

Sanity Checks

Despite all the above efforts, sometimes the spelling system makes bad suggestions. A couple of methods are used to minimize these.

First, a filter is applied to avoid suggesting “equivalent” words. In XTF, the indexer performs several mapping functions, such as converting plural words to singular words, and mapping accented characters to their unaccented equivalents. It would be silly for the spelling system to suggest cat if the user entered cats, even if cat would normally be considered a better suggestion because it has higher frequency. The final suggestion is checked, and if it’s equivalent (i.e. maps to the same words) to the user’s initial query, no suggestion is made.

Second, it’s quite possible for the spelling correction system to make a suggestion that will yield fewer results than the user’s original query. While this isn’t common, it happens often enough that it could be annoying. So after the spelling system comes up with a suggestion, XTF automatically runs the resulting modified query, and if fewer results are obtained, the suggestion is simply suppressed.

Dictionary Creation

Now we turn to the dictionary used by the algorithm above to produce suggestions. How is it created during the XTF indexing process? Let’s find out.

Incremental Approach

One of the best features of the XTF indexer is incremental indexing, the ability to quickly add a few documents to an existing index. So we needed an incremental spelling dictionary build process to stay true to the indexer’s design. To do this we phase the work, with a low-overhead collection pass added to the main indexing process, and then a phase of intensive dictionary generation, optimized as much as possible.

During the main index run, XTF simply collects information on which words are present, their frequencies, and the frequency of pairs. Data is collected in a fairly small RAM cache and periodically sorted and written to disk. Two filters assure that we avoid accumulating counts for rare words and rare word pairs. Words that occur only once or twice are disregarded (though this limit is configurable); likewise, pairs that occur only once or twice are not written to disk. Collection adds minimal CPU overhead to indexing.

Then comes the dictionary creation phase, which processes the queued word and pair counts to form the final dictionary (this can optionally be delayed until another index run). Here are the processing steps:

1. Read in the list of words and their frequencies, merging any existing list with new words added since the last dictionary build.
2. Sort the word list and sum up frequency counts for identical words.
3. Sample the frequency distribution of the words. This enables the correction algorithm to quickly decide how much boost a given word should receive by ranking its frequency in relation to the rest of the words in the dictionary.
4. Create the “edit map” file. For each word, calculate each of the 15 edit keys, and add the word to the list for that key. Key calculation was discussed above. This edit map file is created and then sorted on disk with lists for duplicate entries being merged together.
5. Finally, any existing pair data from a previous dictionary creation run is read in and then new pairs are added from the most recent main index phase. Unlike the other parts of dictionary creation, this work is all done in RAM, for reasons outlined in the next section covering data structures.

Data Structures

The data structures used to store the dictionary are motivated by the needs of the spelling correction algorithm. In particular, it needs the following information to make good suggestions:

1. The list of words that are “similar” to a given word (i.e. whose beginning is an edit distance of 2 or less.)
2. The frequency of a given candidate word (i.e. how often that word occurs within the documents in an index.)
3. The frequency of a given pair of words (i.e. how often the two words appear together, in sequence, in the index.)

To support these needs, the dictionary consists of three main data structures, each of which is discussed below.

Edit Map

Since at most 15 keys need to be read for a given input word, this data structure is mainly disk-based (it’s never read entirely into RAM.) The disk file consists of one line per 4-letter key, listing all the words that share that key. At the end of the file is an index giving the length (in bytes) for each key, so that the correction engine can quickly and randomly access the entries.

The words in each list are prefix-compressed to conserve disk space. This is a way of compressing a list of words when many of them share prefixes. For example, say we have three words in the list for a key:
apple application aplomb

We always store the first word in its entirety; each word after that is stored as the number of characters it has in common with the previous word, plus the characters it doesn’t share. For long lists of similar words, the compression becomes quite significant. In our example the compressed list is:

apple 4ication 2lomb

Here are some lines from a real edit map file, with the keys in bold:

abrd|aboard|2road|2surd|6ist|7ty|6ly

abre|abbreviated|9ions|0fabre|0laborer|7s

abrg|aboriginal

abrh|abraham|7son

abri|aboriginal|4tion|8s|0cambridge|0fabric|6ated|0labyrinth

… and the random-access index at the end of the file …

abrd|37

abre|42

abrg|16

abrh|18

abri|61

Word Frequency Table On disk this is stored as a simple text file with one line per word giving its frequency. The lines are sorted in ascending word order. This structure is read completely into RAM by the correction engine, as we need to potentially evaluate tens of thousands of candidate words per second in a high-volume application.

Here are some lines from a real word frequency file:

aboard|10

abolished|19

abolishing|9

abolish|8

abolition|34

abomination|6

Pair Frequency Table

The correction engine needs to check the frequency of hundreds of thousands of word pairs per second. This implies a need for extremely fast access, so we need to pull the entire data structure into RAM and search it very quickly.

The table exists only in binary (rather than text) form, in a very simple structure. A “hash code” is computed for each pair of words. The hash code is a 64-bit integer that does a good job of characterizing the pair; for two different pairs, the chance of getting the same hash code is vanishingly small. The structure consists of a large array of the all the pairs’ hash codes, sorted numerically, plus a frequency count per pair. This sorted data is amenable to a fast in-memory binary search.

Here’s the disk layout:

As you can see, we store each pair with exactly 12 bytes: 8 bytes for the 64-bit hash code, and 4 bytes for the 32-bit count. Working with fixed-size chunks makes the code simple, and also keeps the pair data file (and corresponding RAM footprint) relatively small.

<front>

  <titlePage>The opening of the Apartheid Mind</titlePage>
  blah. blah. blah.

</front>
  <div1 id="ack">
  <head>Acknowledgements</head>

  <p>I would like to thank.</p>
  <!-- blah, blah, blah -->

  <!-- blah, blah, blah -->
</div1>

<?NOTE: The "ch1" div1 element is needed for this request... ?>

<div1 id="ch1">
  <head>Chapter 1</head>
  <p>It is now conventional wisdom that.</p>

  <p>See Hanlon (1981) for an overview. <ref target="bib12"/></p>

  <!-- blah, blah, blah -->
  <!-- blah, blah, blah -->
</div1>

<div1 id="ch2">

  <head>Chapter 2</head>

  <p>One of the more striking aspects of contemporary.</p>
  <!-- blah, blah, blah -->
  <!-- blah, blah, blah -->
</div1>

<div1 id="bib">
  <bibl id="bib1">  <author>Adams, Heribert</author> </bibl>

  <!-- blah, blah, blah -->
  <!-- blah, blah, blah -->

  <?NOTE: This "bib12" element is also needed... ?>
  <bibl id="bib12"> <author>Hanlon, Joseph</author> </bibl>

  <!-- blah, blah, blah -->

  <!-- blah, blah, blah -->
</div1>
      

Even the overhead of building XSL keys at runtime can be avoided by having the textIndexer do that work. This is accomplished simply by specifying the displayStyle attribute in the docSelector.xsl stylesheet used by the indexer. If specified, the stylesheet referenced by displayStyle will be scanned for <xsl:key> declarations, and all of the keys will be pre-built at index time. See the Document Selector Programming section in the XTF Programming Guide.
One final note: a good way to locate parts of the stylesheet that need to be optimized is to use dynaXML‘s stylesheet profiling configuration option. When enabled, a summary of how many XML document nodes were accessed by each line of the stylesheet will be printed. Find a particular request that runs unacceptably long, examine the
profile, and take aim at the lines which access the most nodes.

To activate the similar documents query, replace your main query output from the Query Parser with a <moreLike> tag. The XTF Tag Reference has more information on this tag.