Balisage Paper: Text Retrieval for XML-Encoded Corpora: A Lexical Approach

Introduction

The W3C XML Query Working Group has published a specification for performing full-text queries over instances of the XPath and XQuery Data Model using an extension of the XQuery syntax. This is a text retrieval facility that operates on an abstract representation of XML trees, rather than on text files that happen to contain markup. Elements and their attributes are reified into hierarchies of nodes, text leaps into the lacunæ and swims between them, and not a pointy bracket in sight.

This paper compares the XQuery Full Text Facility with a more traditional open source text retrieval system, lq-text, and also explores the work done to make lq-text become more suitable to the processing needs of people who work with XML.

Disadvantage and advantages of the two approaches are discussed.

A Brief Description of the Full Text Facility

Although this paper is primarily concerned with a lexical approach, an understanding of the XPath 2 and XQuery approach is useful, and will be taken as a baseline for comparison.

Informally, a full text search is a search to find all documents in a collection, or all elements of some specific type (for example) containing one or more specific words. For example, one might want to find all occurrences of the phrase “warm socks” in a multi-gigabyte corpus of text. The underlying assumption of full text is that the implementation uses an index that has been constructed separately in advance, although this is not necessarily true.

A Brief Description of lq-text

Lq-text is an open source text retrieval package that was first released in 1989. It has had sporadic development since then. Its main claims to fame are high precision, good performance (particularly when the data does not fit into available virtual memory), flexible concordance generation and an open, extensible, multi-process architecture.

Lq-text operates on text files. It makes an index to the files; this index stores the location of each occurrence of each natural-language word in all of the files. The resulting index is stored efficiently, and generally takes between a quarter and three quarters of the storage size of the original documents. The index is an adjunct; lq-text also refers to the original files, although these can be compressed to save space if needed. The package is designed to work best with many small files rather than a few large ones.

When lq-text indexes files, it can run a format-specific filter on each file before indexing it. The list of filters is currently built in to the software (but since it is open source, you can in fact change it if you wish).

A suite of separate Unix programs operate on the index for retrieval; some of these will be described in this paper. They are used in conjunction with each other, using a documented text-based format to communicate.

It is this open architecture that can be exploited to enable XML-specific searches, and that is the primary work described in this paper.

Commonalities Between The Approaches

An underlying assumption is that some sort of indexing will have been performed before queries are run; this is of course for all full-text systems, and although in some cases the constructed indexes do not persist between invocations of the query software, usually the indexes are kept and re-used.

Although the Full-Text facility operates on trees and lq-text operates on flat text files, in practice both systems are matching sequence of tokens against an index, and returning matches based on text content.

The XQuery Update Facility allows queries to update documents, and, as a result, implementations must be able to re-index documents efficiently. Lq-text can also re-index documents, most efficiently when both the original and the new version are available.

Lq-text and XML: Objectives

The author wanted to experiment to understand what work would be needed to make lq-text be useful for people working with XML documents. Some goals of this work included:

Although lq-text was not (at the start of the work) XML-aware, it has the ability to run a format-specific filter program when indexing any given document. There was already an SGML filter, but all it did was ensure that element and attribute names were not indexed. This filter was re-used for XML, modified to allow indexing of elements and attributes. But at that point the work had only begun.

The following use cases were determined sufficient for experiments:

This of course is much less than one might want in a full XML-aware text retrieval system. On the other hand, the XPath-based approach taken by the Full-Text facility does not support highlighting of matches or generation of concordances, and the author felt this to be essential functionality, both for research and for industrial or commercial use.

The approach taken was to extend lqkwic, the concordance program, so the paper will describe the lq-text architecture and then lqkwic, and then explain the extensions that were added. After that, an example program will be shown that uses lqkwic to solve one of the use cases given above. At that point we will be able to compare an XQuery or XSLT 2 solution.

Support for a subset of XML (“just enough XML, Eh?”) was implemented; this subset will also be described, as it may be of interest for other people considering adding XML support to older software.

Lq-text Architecture in Detail

Before explaining how lq-text was extended, it is necessary to give at least an abbreviated account of how lq-text works.

Lq-text builds and maintains a separate index for each set of documents, which it calls a database. When building the index, lq-text applies simple stemming, by reducing words to a root. Currently, only plural and possessive forms are recognised and recorded, and other forms are indexed separately. This code is specific to the English language, and may be removed in a future version, with stemming instead being done by term expansion at query time.

Lq-text comprises a suite of separate programs, and each program always uses a single database. For the sake of simplicity in this paper we will assume that only a single lq-text database is in use at any time, unless otherwise stated.

Some of the programs included with lq-text are listed for reference in the table. Only a few of them will be discussed further in this paper, but the table may give the reader a clearer sense of the software.

Once an index is built (for example with lqaddfile), it can be used. A sample search might be as follows:

$ lqquery "on his face" | lqkwic

For one small corpus (Brewer's Dictionary of Phrase and Fable, with about 17,000 files) the results are as follows:

==== Document 1: xml/1251.xml: Balafré ====
1:t which left a frightful scar on his face (1550–1588).  So Ludovic Lesly, an
==== Document 2: xml/3720.xml: Cloud ====
2: He [Antony] has a cloud on his face.
==== Document 3: xml/6070.xml F ====
3: F is written on his face. “Rogue” is written on his face
4: face. “Rogue” is written on his face. The letter F used to be branded n
==== Document 4: xml/8745.xml Ill Omens ====
5: he happened to trip and fall on his face. This would have been considered a
6: shore at Bulverhythe he fell on his face, and a great cry went forth that i

Here, the matched text is shown with a few words of context on either side, giving rise to the term key word in context, KWIC, index.

Two lq-text programs, lqquery and lqkwic, were combined in the search, using a Unix pipe; that is, both programs were run concurrently, with the output of one being fed as the input to the other. This is a usual way of working with lq-text, and although it sometimes requires some thought, it does mean that lq-text exploits multi-processor systems well, and also works well with Unix and Linux, which were designed to run pipelines of small programs very efficiently.

This description begs the question, exactly what output is passed from lqquery to lqkwic in the example? The answer to this question exposes the underlying index architecture, and can be seen by running just the first program without the second:

$ lqquery "on his face"
3 0 41 2792 1251.xml
3 0 55 11703 3720.xml
3 0 15 14314 6070.xml
3 0 21 14314 6070.xml
3 0 75 17285 8745.xml
3 1 8 17285 8745.xml

The format, as can be determined by inspection, is a sequence of lines of text, and, in each line, a number of space-separated fields. Each line represents a single match, and just as there were six results before, there are six matches here. The fields are, from left to right, the number of words matched, the block in the file, the word in the block, the file number and (optionally) the filename.

The lq-text index does not store exact locations for matches. Instead, the location to the nearest block number, and the word within the block, are stored. Blocks are by default 128 bytes in size. The result of this is that a match location within a file is usually represented by a pair of fairly small integers, but that finding the actual intended words to highlight requires accessing the file and counting words. This is a trade-off: a lq-text index is often much smaller than the indexed files, because the average English word is about 5 characters long (depending somewhat on the corpus), and it only takes 2 bytes in most cases to store the information about a match.

Lines in the match list starting with a # are considered to be comments, and lines of the form { variable = value } are used by lqkwic to set values that can be used later, as we shall see.

Lq-text programs generally both accept this match format as input and produce it as output, so that they can be combined. In particular, the lqkwic program can both read and produce this format, as we shall see in the next section.

The lq-text lqkwic program

The lqkwic program takes lq-text matches as input, and prints them using a user-supplied format, or a built-in format. Matches are grouped by file, and another format is used to print the start of each group of documents, and yet another can be supplied to be used at the end of each group.

The format takes the form of a string with embedded variables that are interpolated each time the format is used. An example may clarify the format:

$ lqquery "on his fa*" |
    lqkwic -S '' -A '' -s '${MatchNumber} ${MatchedText}\n'
1 on his father
2 on his face
3 on his favourite
4 on his face
5 on his father
6 on his face
7 on his face
8 on his father
9 on his favourite
10 on his face
11 on his face

Here, the formats for the start and end of each group of matches have been set to the empty string with -S '' and -A '' respectively. The per-match format is set to a string in which for each match the match number is printed, followed by a space, followed by the matched text and (indicated by \n in the grand Unix tradition) a newline. The single quotes are used to surround the strings to prevent the Unix shell from seeing the dollar signs and treating them as references to shell variables.

Although the MatchedText variable is obviously useful for testing, one would normally use it in conjunction with other variables, such as TextBefore and TextAfter. The purpose of this section is not to document lqkwic, but to give the reader an understanding of the sorts of things one can print, since lqkwic has uses that are far removed from concordance generation, and since we will shortly be taking advantage of such uses.

The following table shows some of the variables available. In many cases, lqkwic must read the actual matched documents (or at least part of them), in order to evaluate the variables.

There are also constructs for formatting variables, for padding them to a given width (measured in Unicode characters, not bytes), and for filtering them through routines that delete punctuation, convert punctuation to spaces, perform case conversion and so forth.

Extending lqkwic

The following XML-specific variables were added as an experiment to try to understand how viable the approach would be:

It is not clear that this is sufficient to answer our use case of finding multiple phrases in the same XML element. To do that, we would need a way to identify parent elements and compare them.

One could use the File number and the byte offset of the matched text (${StartByte}), but this is not sufficient, because there may be close and open tags between matches of two phrases.

One approach to finding phrases with a common containing element named (of type) E would be to find all of the start and end tags for E, and then use the file, block and word within block numbers to perform range algebra.

But it would be more efficient if this were not needed. In a corpus of many files, it is likely that the element E will occur in many files, perhaps many times, and searching for them all will be too slow.

If lqkwic could print the location of the parent tag, a much simpler faster algorithm would be possible.

The notation ->startbyte or ->endbyte was added; after any XML variable name, it generates the corresponding byte offset in the matched file.

In addition, the notation XML.parent.Tag.e was added, to be similar to the XPath notation ancestor::e; it is possible that a future version of lqkwic will use the XPath notation, as long as there is no danger that users will be confused into thinking that lq-text is using a node-based model internally.

The search for a parent tag is implemented by reading the matched document at the block containing the match, and for some distance beforehand. lqkwic then searches backwards from the match to find an open tag which has no corresponding close tag in the intervening distance. It is worth noting that this sort of approach is not generally possible with SGML, where empty elements have no end tag. The syntactic innovation of XML was to require empty tags to have a trailing slash, as in <p/> or <p id="p301" />, and this enables the software to skip empty elements reliably. Start and end tags can be skipped more easily of course, although the algorithm used for backwards parsing does rely on attributes not containing unquoted < or > signs.

Unfortunately, backwards parsing suffers from a major drawback: the search for the parent tag will fail if it is too far away. Although lqkwic could in theory read arbitrarily back in the file, this could mean that presenting matches in a dictionary would be very expensive, with every match processed necessitating a search back to the start of a large document.

In practice, an in-memory cache may be sufficient to achieve reasonable performance in most cases. Another possibility might be to store parent pointers in the index. For now, lq-text is primarily intended for working with many thousands of small files; use XSLT to split large files before indexing them.

A sample program

We are now in a position to find all elements E that contain all of a set of phrases P0 ... Pn, as follows:

First, match the phrases, and, for each match, use a format of the form ${xml.contentbefore.E->endbyte} to find the end byte of the start tag of the parent element of type E; that is, the location just after the > at the end of the start tag. If two matches have the same value for the start tag, and are in the same file, then they share the same XML ancestor E.

We can match the phrases with a single invocation of lqrank except for one difficulty: there is no way to determine, for a given match, to which phrase it corresponds, so we cannot determine whether an element contains all of the phrases.

The lqrank program has the ability (when instructed with the -g option) to output a line, { q = N } where N is an integer, to identify to which result set the following matches correspond. This is available to lqkwic formats as the variable g.q (the g stands for glue, the unpublished and unfinished lq-text integration language).

Using this, it becomes a relatively simple matter in a language such as Perl, Python or even the Unix shell, to run

print phrases one per line |
    lqrank -r all -g -F - |
    lqkwic -s '${FID} ${g.q}
    ${xml.contentbefore.E->endbyte} ${Match}\n'

Each match is in this way prefixed by the numeric identifier of the document in the index (FID), the phrase number and the byte offset of the end of the nearest ancestor E element's end tag. The -F - option makes lqrank read the list of phrases to match from its input, rather than expecting them as command-line arguments; one could also use the Unix xargs program for this purpose.

Next we must group the matches by file identifier and startbyte, and if every different phrase occurred at least once, we print all the matches for that file identifier and startbyte.

The result can then be fed to lqkwic to generate a concordance, or perhaps to fetch information about the parent element, or both.

The program outlined here (and given in full in the appendix, in the Perl programming language) is intended as an example of the sort of flexibility that might be achieved as lq-text becomes more XML aware.

Unicode

In 1988, the use of 8-bit character sets was pretty usual; lq-text is at least 8-bit clean for data, so that conversion to UTF-8 seemed a simple matter, and also has some locale awareness. There were two tricky parts to the process of adding UTF-8 support. The first was to ensure that characters, rather than bytes, were counted when formatting, and of course that a UTF-8 octet sequence was never split part-way through.

The second difficulty was much harder: making sure that combining characters are never split from their corresponding base character. This last is not yet complete, but initial work using the GNOME glibc library is promising. This is the main issue preventing lq-text from being shipped, at present, and may have been completed by the time this paper is presented in August 2008.

Software cannot tell by inspecting a singly byte (or octet, as standards people say, in case 9-bit systems should reoccur) whether that octet forms part of a longer UTF-8 sequence. One needs to scan backwards to check, because the first octet is the one that indicates the number of octets to follow in the sequence that constitutes a single character. This is of course easy to deal with as long as one can scan backwards a little. For diacritical marks and other combining characters, however, one must consult a database. The author could not help but wish that a single bit in the character representation could have been reserved for this purpose, but that would have prevented Unicode from being backwards-compatible with ISO 8859-1, a goal at the time Unicode was designed. A future version of lq-text may use its own database, with only the character properties that lq-text needs, perhaps created automatically at the same time as each database so as to take locale information into account.

Comparing with XQuery 1.0 or XSLT 2 + Full Text

The published draft of Full-Text does not support concordance generation, although some implementations in practice (such as MarkLogic) do appear to offer the necessary functionality through product-specific extensions. The author of this paper considers match highlighting to be essential functionality in practice. A future version of Full-Text may well include it.

Let us then assume, as we must, that we are using an XQuery or XSLT implementation that supports in some way identifying match locations, and hence allows highlighting.