Basic interfaces

The {@link it.unimi.dsi.mg4j.document.Document} interface

MG4J aims at indexing the content of entities called documents. The main classes that describe documents and sets of documents are included in the it.unimi.dsi.mg4j.document package. In particular, documents are instances of the {@link it.unimi.dsi.mg4j.document.Document} interface. A document is characterized abstractly by the following data:

• a title, a character sequence that represents the document; the document title is returned by the {@link it.unimi.dsi.mg4j.document.Document#title()} method;
• a URI, that somehow characterizes the document uniquely; the document URI is returned by the {@link it.unimi.dsi.mg4j.document.Document#uri()} method;
• a number of fields; every field is abstractly represented by a number, the field index; fields are numbered from 0, but the user should know how many fields a document exhibits, because this information is not available in the document itself. For every field, the document exhibits the following data:
  • the field content, that is an Object returned by the {@link it.unimi.dsi.mg4j.document.Document#content(int)} method; the type of object that this method returns must be known by the calling class in advance; in particular, for textual fields (see below), the content will be a {@link java.io.Reader};
  • for textual fields only, a {@linkplain it.unimi.dsi.mg4j.io.WordReader word reader}: an object that is able to split the field content (in this case: a sequence of characters) into a sequence of words; the word reader is returned by the {@link it.unimi.dsi.mg4j.document.Document#wordReader(int)} method (which must be called only for textual fields).

Users should always close a document after usage by calling the {@link it.unimi.dsi.mg4j.document.Document#close()} method: the method is responsible for relinquishing all resources that a document instantiated for its very existence.

The {@link it.unimi.dsi.mg4j.document.DocumentFactory} interface

Documents usually do not come alone, but they are grouped into collections: documents within a collection are of the same type, and this fact explains why the document structure (number and type of fields) are not contained in the document itself. Indeed, documents are produced by document factories.

A document factory is an instance of the {@link it.unimi.dsi.mg4j.document.DocumentFactory} interface, that in particular is able to produce a document. All documents produced by the same factory are of the same kind, and exhibit the same number and type of fields. A factory gives information about the documents it produces through the following methods:

• {@link it.unimi.dsi.mg4j.document.DocumentFactory#numberOfFields()}: returns the number of fields contained in each document produced by this factory; recall that fields are indexed starting from 0;
• {@link it.unimi.dsi.mg4j.document.DocumentFactory#fieldName(int)}: returns a mnemonic explanatory name for the given field;
• {@link it.unimi.dsi.mg4j.document.DocumentFactory#fieldIndex(String)}: returns the index of a field, given its mnemonic name;
• {@link it.unimi.dsi.mg4j.document.DocumentFactory#fieldType(int)}: returns (an integer representing) the type of the given field; possible types are static constants declared in the {@link it.unimi.dsi.mg4j.document.DocumentFactory.FieldType} interface; one of the possible types is {@link it.unimi.dsi.mg4j.document.DocumentFactory.FieldType#TEXT}, used for textual fields; note that the type of objects returned by the {@link it.unimi.dsi.mg4j.document.Document#content(int)} method of the {@link it.unimi.dsi.mg4j.document.Document} interface depend on the type of the field.

The abovementioned methods provide information about documents produced by the factory. The actual documents are produced by the {@link it.unimi.dsi.mg4j.document.DocumentFactory#getDocument(java.io.InputStream,it.unimi.dsi.fastutil.objects.Reference2ObjectMap) getDocument(rawContent,metadata)} method.

This method returns a new document from the factory. The rawContent parameter is the most important one: it is a stream of bytes that the factory uses to produce the document. The factory knows how the sequence of bytes should be interpreted to produce a document of the desired kind. Note that even though the interpretation of the sequence of bytes representing the raw document content is entirely left to implementors, often you might prefer to think of the input byte sequence as of a list of consecutive self-delimiting byte subsequences, one for each field: in this case, the {@link java.io.InputStream#reset()} method of the {@link java.io.InputStream} class is used to divide the subsequences from one another.

The metadata parameter is a map providing some basic data about the document as derived by the collection. The map is a reference map with suitable {@link java.util.Enum} keys, and as such must be queried using the keys in {@link it.unimi.dsi.mg4j.document.PropertyBasedDocumentFactory.MetadataKeys}, or other similar factory-specific keys. For instance, the key {@link it.unimi.dsi.mg4j.document.PropertyBasedDocumentFactory.MetadataKeys#TITLE} gives a suggested title to the document (but the factory may ignore it, if it has a better way to determine a title for the document), whereas {@link it.unimi.dsi.mg4j.document.PropertyBasedDocumentFactory.MetadataKeys#URI} specifies a suggested URI for the document (which, once more, may be ignored by the factory).

Usually, a factory is built using a list of properties that define default values for metadata such as charset encoding or MIME types. There properties can be passed in several ways, and usually the main method of a collection provides an option (typically, -p) that let the user specify default metadata for the factory. The property resolution algorithm is explained in the documentation for {@link it.unimi.dsi.mg4j.document.PropertyBasedDocumentFactory}.

The {@link it.unimi.dsi.mg4j.document.DocumentSequence} interface

Up to this point, we have interpreted documents and document factories in a very abstract manner, but we gave no importance on the way the byte sequences representing the raw data are produced.

Basically, a source of documents is a {@link it.unimi.dsi.mg4j.document.DocumentSequence}. More precisely, instances of this class represent sources that are able to generate documents. Typically, a document sequence is able to produce a stream of documents after one another, through a special kind of iterator, called {@link it.unimi.dsi.mg4j.document.DocumentIterator}, returned by the {@link it.unimi.dsi.mg4j.document.DocumentSequence#iterator()} method.

A document iterator is not really a Java {@link java.util.Iterator}: it is simply a class that exposes a method {@link it.unimi.dsi.mg4j.document.DocumentIterator#nextDocument()} that returns the next document, if any, or null when there are no more documents. Thus, document iterators can be lazy, which is preferrable in several circumstance (e.g., documents coming from an input stream).

The {@link it.unimi.dsi.mg4j.document.DocumentCollection} interface

In some cases, the documents only appear as an uninterrupted stream and applications do not have direct accesses to single documents; in particular, it might be the case that documents just disappear after being enumerated (as it happens when the document source is standard input). In all such situations, a {@link it.unimi.dsi.mg4j.document.DocumentSequence} provides the only way to get the documents, because it only guarantees sequential access.

Nonetheless, there are other cases where documents can be easily accessed in a direct fashion, and can be read many times (for example, when documents are files in the file system). In such cases, {@link it.unimi.dsi.mg4j.document.DocumentCollection} (an extension of {@link it.unimi.dsi.mg4j.document.DocumentSequence}) can be used.

Apart for the methods of a document sequence, a document collection provides the following additional access methods to the documents:

• {@link it.unimi.dsi.mg4j.document.DocumentCollection#size()}, that returns the collection size, i.e., the number of documents in the collection;
• {@link it.unimi.dsi.mg4j.document.DocumentCollection#document(int)}, that returns the document with given pointer; the document pointer is an integer representing uniquely a document within the collection: the i-th document produced by the collection's {@linkplain it.unimi.dsi.mg4j.document.DocumentCollection#iterator() document iterator} has pointer i−1 (so, document pointers range from 0, inclusive, to size(), exclusive);
• {@link it.unimi.dsi.mg4j.document.DocumentCollection#stream(int)}, that returns the {@link java.io.InputStream} of raw data that this collection would use to produce the document with given pointer.

After a document collection has been created, for example, starting from a set of files in the filesystem, it can usually be saved (serialized) on a file: the extension used for the filename is, by default, {@link it.unimi.dsi.mg4j.document.DocumentCollection#DEFAULT_EXTENSION}. Implementors of this interface should always specify explicitly which assumptions on the existence of external data are made for the consistency of a collection to be preserved. For example, a collection produced from a set of files will be consistent until no file has been changed or deleted; if the latter situation happens, the collection usually becomes inconsistent, and in any case you might expect that the indices thereof produced will no longer match the content of the collection.

Note that a document collection has very weak requirements (and thus very weak obligations) on the concurrent creation of several objects (documents, iterators, etc.). Please read carefully the {@link it.unimi.dsi.mg4j.document.DocumentCollection class description}.

Relations between document sequences/collections and document factories

As we explained above, document sequences/collections extract raw data (byte sequences) from some source and use a specified document factory to turn such data into documents. Hence, there exists a tight connection between each document sequence and the document factory it uses.

Typically, the document factory is provided to the document sequence at construction time, and this fact provides a form of flexibility, because different sources (e.g., the file system and the standard input) may be coupled with the same document factory (e.g., a document factory parsing HTML documents into text), or, conversely, the same document source may be used to produce documents with different formats.

Users should always be careful, however. Often, document sequences make assumptions about the factory they use, which reduces the number of possible combinations the user may adopt. Implementors of the {@link it.unimi.dsi.mg4j.document.DocumentSequence} interface should always clarify all the assumptions they make about the factories that can be used for the sequence.

Document factories

Recall that a document factory is an object that is capable of producing homogeneous documents (documents with the same number/type of fields). Every document is produced starting from a raw bytestream.

The {@link it.unimi.dsi.mg4j.document.IdentityDocumentFactory}

The simplest possible document factory is the {@link it.unimi.dsi.mg4j.document.IdentityDocumentFactory}: this factory produces documents with a single textual field, called text, that is actually obtained by transforming the byte sequence into a sequence of characters, using some default encoding. Actually, a document factory must also provide a way to break the text into words. With this aim, the identity factory may be provided with a {@link java.util.Locale} that is used to determine how words are best broken in the given locale's language.

Other examples of document factories

Other implementations of document factories that are provided with MG4J are:

• {@link it.unimi.dsi.mg4j.document.HtmlDocumentFactory}: a factory used to parse HTML documents; this factory produces documents by parsing HTML streams. Bytes are converted into characters using a specified encoding; the resulting HTML character sequence is parsed to extract text (that is returned as a textual field named text) and title (the HTML title element, returned as a textual field named title). The title, if present, is also used as document title (otherwise, the suggested title is used). Note that a document collection might have information about the charset encoding (e.g., by means of HTTP headers): in this case the metadata field of {@link it.unimi.dsi.mg4j.document.DocumentFactory#getDocument(java.io.InputStream,it.unimi.dsi.fastutil.objects.Reference2ObjectMap)} should pass this information.
• {@link it.unimi.dsi.mg4j.document.PdfDocumentFactory}: a factory used to parse PDF documents. Currently, a single textual field named text is exported.

Composing document factories

As we said, many document factories interpret the raw content data (an {@link java.io.InputStream}, i.e., a sequence of bytes) as if it is really made by a concatenation of many {@link java.io.InputStream}s, where each stream is typically parsed to a field; to pass from one stream to the next, the {@link java.io.InputStream#reset()} method is called.

Suppose you have n document factories D₁, …, D_n, with f₁, …, f_n fields, respectively. One may want to build a new factory with f₁+…+f_n fields, where each document is produced by composing the document factories D₁, …, D_n sequentially: in other words, the raw data are first passed to the first factory (that extracts f₁ fields, typically resetting the stream as many times), then it is passed to the second factory (that extracts f₂ fields) etc.

The {@link it.unimi.dsi.mg4j.document.CompositeDocumentFactory} does the job, and also allows one to change the field names (that are otherwise named as they were in the subfactories).

The class {@link it.unimi.dsi.mg4j.io.MultipleInputStream} is a useful tool to produce raw data for composite factories: it allows one to convert an array of input streams into a single input stream: each time the resulting stream is reset, the multiple input stream will offer you the next stream in the array.

A special form of composite document factory is obtained using {@link it.unimi.dsi.mg4j.document.ReplicatedDocumentFactory}, that allows one to compose sequentially the same document factory with itself a certain number of times.

Document collections and sequences

The {@link it.unimi.dsi.mg4j.document.InputStreamDocumentSequence}

This is the simplest kind of document sequence: it just breaks a single {@link java.io.InputStream} on the basis of a given separator character; each piece of the stream is interpreted as the raw data corresponding to a document, and it is passed to a factory (specified at construction time) for converting it into a {@link it.unimi.dsi.mg4j.document.Document}.

The {@link it.unimi.dsi.mg4j.document.FileSetDocumentCollection}

This kind of collection is built starting from a set of files in the file system. Each file is interpreted as a document, and passed to a factory (specified at construction time). The suggested title for a document is the corresponding filename, and the suggested URI is the URI of the file.

The {@link it.unimi.dsi.mg4j.document.ZipDocumentCollection} facility

There are cases in which one would like to turn a document sequence into a document collection. This may happen for one of the following reasons:

• the sequence is, by its very nature, volatile (e.g., it is coming from standard input, and cannot be re-produced), but we would like to make it into a resident non-volatile collection;
• the sequence is not amenable to be accessed at random;
• the documents in the sequence are difficult to parse, and it is not advisable to repeat the parsing process every time they are accessed.

In all such cases, it may be advisable to produce a compact copy of the sequence that is easily and efficiently accessible at random. To do this, one may use the {@link it.unimi.dsi.mg4j.document.ZipDocumentCollectionBuilder}, that takes a document sequence and produces a "zipped clone" of the documents in the sequence: there are some mild limitations to the sequences that can be used in this context, and the resulting collection is only a partial copy of the original one, but in most cases this is sufficient for all indexing purposes. The builder will save two files: one contains the essential data concerning the zipped collection, and the other contains the zipped version of the documents.

After this, the produced {@link it.unimi.dsi.mg4j.document.ZipDocumentCollection} may be used as any other collection.

Index generation and access.

This package contains the classes that handle index generation and access. The interval iterators defined in {@link it.unimi.dsi.mg4j.search} build upon the classes of this package to provide answer to queries using interval semantics, but it is also possible to access an index directly.

You can easily build indices using the tools in {@link it.unimi.dsi.mg4j.tool}. Once an index has been built, it can be opened using an {@link it.unimi.dsi.mg4j.index.Index} object, which gathers metadata that is necessary to access the index. You do not create an {@link it.unimi.dsi.mg4j.index.Index} with a constructor: rather, you use the static factory {@link it.unimi.dsi.mg4j.index.Index#getInstance(CharSequence)} (or one of its variants) to create an instance. This is necessary so that different kind of indices can be treated transparently: for example, the factory may return a {@link it.unimi.dsi.mg4j.index.cluster.IndexCluster} if the index is actually a cluster, but you do not need to know that.

From an {@link it.unimi.dsi.mg4j.index.Index}, you can easily obtain either an {@link it.unimi.dsi.mg4j.index.IndexReader}, which allows to scan sequentially or randomly the index. In turn from an {@link it.unimi.dsi.mg4j.index.IndexReader} you can obtain a {@link it.unimi.dsi.mg4j.index.IndexIterator} returning the documents containing a certain term and the position of the term within the document.

But there is more: an {@link it.unimi.dsi.mg4j.index.IndexIterator} is a kind of {@link it.unimi.dsi.mg4j.search.DocumentIterator}, and {@link it.unimi.dsi.mg4j.search.DocumentIterator}s can be combined in several ways using the classes of the package {@link it.unimi.dsi.mg4j.search}: for instance, you can combine document iterators using AND/OR. Note that you can combine document iterators on different indices, but of course the operation is meaningful only if the two indices contain different information about the same document collection (e.g., title and main text).

More importantly, if the index is full text (the default) for each document containing the term you can get interval iterators that return intervals representing extents of text satisfying the query: for instance, in case of an AND of two terms, the intervals will contain both terms.

Structure of an inverted index

An inverted index is made by a sequence of inverted lists (one inverted list for each term). Inverted lists are made by document records: each document record contains information about the occurrences of the term within a certain document.

More precisely, each inverted list starts with a suitably encoded integer, called the frequency, which is the number of document records that will follow (i.e., the number of documents in which the term appears). After that, there are exactly as many document records as the frequency.

Each document record is made by two parts:

• a suitably encoded integer, called the (document) pointer, which identifies the document within the collection;
• a (possibly empty) sequence of bits, called the data; the data have no special structure per se: the only assumption is that they are a self-delimiting bit sequence (i.e., one knows when the sequence is over).

As a basic and fundamental implementation, the classes of this package provide methods that write and read document data in a default form. In this default structure, each document data is a suitable coding of a (strictly increasing) sequence of integers, that correspond to the positions where the term occurs within the document. The length of the sequence (i.e., the number of positions in at which the term appears) is called the count (it is also common to call it “within-document frequency”, but we find this usage confusing).

Index partitioning and clustering.

This package contains the classes that provide the infrastructure for index partitioning and clustering. The tools the actually perform partitioning can be found in {@link it.unimi.dsi.mg4j.tool}.

An index cluster is a set of local indices that are viewed as a single index. In a {@linkplain it.unimi.dsi.mg4j.index.cluster.LexicalCluster lexical cluster} each local index has a disjoint set of terms, but the document pointers contained in each local index refer to the same documents. In a {@linkplain it.unimi.dsi.mg4j.index.cluster.DocumentalCluster documental cluster} each index contains postings referring to a disjoint subset of a collection.

Clustering indices requires mapping term number and document pointers back and forth between the global index and local indices. This mapping is provided by {@linkplain it.unimi.dsi.mg4j.index.cluster.DocumentalClusteringStrategy documental clustering strategies} and {@linkplain it.unimi.dsi.mg4j.index.cluster.LexicalClusteringStrategy lexical clustering strategies}.

Clusters are often generated by partitioning an index (albeit, for instance, {@link it.unimi.dsi.mg4j.tool.Scan} produces a cluster as output of the indexing process). In this case, a {@linkplain it.unimi.dsi.mg4j.index.cluster.DocumentalPartitioningStrategy documental partitioning strategy} or a {@linkplain it.unimi.dsi.mg4j.index.cluster.LexicalPartitioningStrategy lexical partitioning strategy} explain how to divide and remap term numbers and document pointers. Of course, the clustering and partitioning strategy must be suitably matched.

Package Specification

The classes in this package are extremely experimental and need considerable rework and optimisation to be actually useful. They are distributed with MG4J because excising them from the MG4J structure is rather complicated, and because they are fully usable: feedback is more than welcome.

Snowball-based {@linkplain it.unimi.dsi.mg4j.index.TermProcessor term processors}.

Package Specification

This package gathers a number of algorithmic stemmer (most notably, the famous {@link it.unimi.dsi.mg4j.index.snowball.PorterStemmer}) automatically generated from scripts written in Snowball—a string language developped by Martin Porter to describe easily algorithmic stemmers. Please refer to the documentation on the Snowball site for information about the stemmers.

The code in this package is distributed under the BSD License. It is Copyright (C) 2001 Martin Porter, and (for the Java developments) Copyright (C) 2002 Richard Boulton.

Bit-level I/O classes.

Package Specification

The standard Java API lacks bit-level I/O classes: to this purpose, MG4J provides {@link it.unimi.dsi.mg4j.io.InputBitStream} and {@link it.unimi.dsi.mg4j.io.OutputBitStream}, which can wrap any standard Java corresponding stream and make it work at the bit level; moreover, they provide support for several useful formats (such as unary, binary, minimal binary, γ, δ and Golomb encoding).

Compression can be achieved using self-delimiting formats supported by the classes above, or also by arithmetic coding, using the classes {@link it.unimi.dsi.mg4j.io.ArithmeticCoder} and {@link it.unimi.dsi.mg4j.io.ArithmeticDecoder}. Note that arithmetic coding is not very efficient in the present implementation, as it does not allow a varying number of symbols.

Bit input and output streams offer also efficient buffering and a way to reposition the bit stream in case the underlying byte stream is a file-based stream or a {@link it.unimi.dsi.fastutil.io.RepositionableStream}.

Conventions

All coding methods work on natural numbers. The encoding of zero is very natural for some techniques, and much less natural for others. To keep methods rationally organised, all methods are able to encode any natural number. If, for instance, you want to write positive numbers in unary encoding and you do not want to waste a bit, you have to decrement them first (i.e., instead of p you must encode p−1).

User interfaces for querying indices.

Most classes in this package are just suggestions or experiments. The {@link it.unimi.dsi.mg4j.query.Query} tool lets you query one or more indices on the command line or possibly using a browser. The displayed results can be linked to actual data (files, collections, etc.) using items such as {@link it.unimi.dsi.mg4j.query.GenericItem} or {@link it.unimi.dsi.mg4j.query.FileSystemItem}.

Composite representation for queries

This package contains the classes that represent queries as an abstract syntax tree, or, in design-pattern jargon, as a composite.

Warning: Before reading this overview, the reader is encouraged to consult the first part of the {@link it.unimi.dsi.mg4j.search} package documentation, where the notion of query is briefly presented.

The basic idea is to perform a complete decoupling of the query construction and resolution into three levels:

• String level: the query is a string, written in a suitable language where, for example, every operator has a certain syntax, uses a certain keyword etc.
• Tree level: the query is an abstract tree, that contains one internal node for each operator, but that has nothing to do with the actual way the query was written; for example, one may want to give the user the possibility to write the query by using a visual editor, in which case there will be some way to obtain the tree representation of the query without having any string-level representation for it.
• Iterator level: the document iterator that lazily solves the query over a certain index or set of indices; this is the semantic counterpart of a query, and it is discussed at large in the overview of the {@link it.unimi.dsi.mg4j.search} package.

This package overview shows how to pass from the string to the tree level using the built-in {@link it.unimi.dsi.mg4j.query.parser.QueryParser}, and explains what is needed to implement the tree level, as well as the basic instruments needed to convert the tree level into the iterator level.

In MG4J, a query parser is an implementation of {@link it.unimi.dsi.mg4j.query.parser.QueryParser}: essentially, an object with a method that transforms strings in {@linkplain it.unimi.dsi.mg4j.query.nodes.Query queries}. You can use any parser you like, or build your queries programmatically.

The parser provided with MG4J and whose syntax is described in the manual is currently generated using JavaCC: unfortunately, this tool produces some public classes that somehow clutter the package documentation. All the parsing logic is contained in the {@link it.unimi.dsi.mg4j.query.parser.SimpleParser} class, which is generated by the JavaCC source SimpleParser.jj.

Building a query tree out of a query string

MG4J allows one to perform queries on multiple indices; by saying so, we mean that you may have many indices concerning the same document collection, and you want to perform a query that may search on some of them. Think, for example, of a collection of emails. You might have generated a number of indices, to index their subjects, sender, recipient(s), body etc. All these indices can be thought of as individual entities, their only relation being that they index collections with the same number of documents, and that same-numbered documents conceptually "come" from the same source.

To get a query tree from a string representation, you must first build a {@link it.unimi.dsi.mg4j.query.parser.QueryParser} object. For instance, if you use the built-in {@link it.unimi.dsi.mg4j.query.parser.SimpleParser} you have to provide a map whose keys are index names (called index aliases) and with each index alias mapped to the corresponding {@link it.unimi.dsi.mg4j.index.Index}. Moreover, one of the aliases is taken to be the default index alias used for the queries.

In our example, we will assume that we have three index aliases (say, subject, from and body), and that subject is the default index alias. The parser would then be created as follows (here, we are stipulating that index with alias x has basename mail-x):

		Object2ReferenceMap<String,Index> indexAlias2Index = new Object2ReferenceOpenHashMap<String,Index>();
		Index defaultIndex;
		indexAlias2Index.put( "subject", defaultIndex = Index.getInstance( "mail-subject" ) );
		indexAlias2Index.put( "from", Index.getInstance( "mail-from" ) );
		indexAlias2Index.put( "body", Index.getInstance( "mail-body" ) );
		
		QueryParser parser = new QueryParser( indexAlias2Index.keySet(), "subject" );
		

			Query query = parser.parse( "meeting AND body:(schedule OR urgent)" );
			DocumentIteratorBuilderVisitor visitor = new DocumentIteratorBuilderVisitor( indexAlias2Index, defaultIndex, 0 );
			DocumentIterator it = query.accept( visitor );
			while ( it.hasNext() ) {
				System.out.println( "Document #: " + it.nextDocument() );
				System.out.print( "\tPositions:" );
				for ( Interval interval: it )
					System.out.print( " " + interval );
				System.out.println();
			}
		

Structure of a {@link it.unimi.dsi.mg4j.query.nodes.Query}

As explained above, in this package a {@link it.unimi.dsi.mg4j.query.nodes.Query} is simply an abstract tree: its leaves will correspond to ground queries, whereas internal nodes correspond to query operators.

Ground queries can be {@linkplain it.unimi.dsi.mg4j.query.nodes.Term term queries}, {@linkplain it.unimi.dsi.mg4j.query.nodes.Prefix prefix queries}, and {@linkplain it.unimi.dsi.mg4j.query.nodes.MultiTerm multiterm queries} (the latter usually generated by some query-expansion mechanism). Any other query is either a {@linkplain it.unimi.dsi.mg4j.query.nodes.Composite composite query} (e.g., a {@linkplain it.unimi.dsi.mg4j.query.nodes.And conjunctive query}, a {@linkplain it.unimi.dsi.mg4j.query.nodes.Or disjunctive query} etc.), that is, a query composed by other subqueries, or it is obtained by some other operator (e.g., a {@linkplain it.unimi.dsi.mg4j.query.nodes.LowPass low-pass query} etc.).

Every query has a method {@link it.unimi.dsi.mg4j.query.nodes.Query#accept(it.unimi.dsi.mg4j.query.nodes.QueryBuilderVisitor)} a {@link it.unimi.dsi.mg4j.query.nodes.QueryBuilderVisitor} object, through which you can visit the query tree. More precisely, when the accept method is invoked on a query, a recursive visit of the query tree is performed: at every node n of type Q (Q being any class implementing {@link it.unimi.dsi.mg4j.query.nodes.Query}), the following steps are performed:

• the visitor's visitPre(Q n) method is called; if the method returns false, the visit is interrupted; otherwise…
• the subtrees are recursively visited, obtaining an array of results T[] x; if at a certain point during this visit some call decides that the visit should be interrupted, we stop; otherwise…
• the visitor's visitPost(Q n, T[] x) method is called, and the result (of type T) is returned.

To make the idea of a visitor easier to understand, consider the following simple example of a visitor:

    	        static class PrinterVisitor extends AbstractQueryBuilderVisitor<String> {
                private static void appendArray( MutableString res, String t[], char sep ) {
                        for ( int i = 0; i < t.length - 1; i++ ) res.append( t[ i ] + sep );
                        res.append( t[ t.length - 1 ] );
                }
                public String[] newArray( int len ) { return new String[ len ]; }
                public String visitPost( OrderedAnd node, String[] t ) {
                        MutableString res = new MutableString();
                        res.append( "OAND(" );
                        appendArray( res, t, ',' );
                        res.append( ")" );
                        return res.toString();
                }
                public String visitPost( Or node, String[] t ) {
                        MutableString res = new MutableString();
                        res.append( "OR(" );
                        appendArray( res, t, ',' );
                        res.append( ")" );
                        return res.toString();
                }
                public String visitPost( And node, String[] t ) {
                        MutableString res = new MutableString();
                        res.append( "AND(" );
                        appendArray( res, t, ',' );
                        res.append( ")" );
                        return res.toString();
                }
                public String visitPost( Consecutive node, String[] t ) {
                        MutableString res = new MutableString();
                        res.append( "\"" );
                        appendArray( res, t, ' ' );
                        res.append( "\"" );
                        return res.toString();
                }
                public String visitPost( Not node, String t ) {
                        return "NOT(" + t + ")";
                }
                public String visitPost( LowPass node, String t ) {
                        return t + "~" + node.k;
                }
                public String visitPost( Select node, String t ) {
                        return node.index + ":" + t;
                }
                public String visit( Term node ) { return node.term.toString(); }
                public String visit( Prefix node ) { return node.prefix + "*"; }
        }
   	

Now, you can pass an instance of this visitor to a query, and as a result get a string (linear) representation of the query itself. (Of course, there is a simple way to get the same result, that is, calling the toString() method directly, but for this example is easy enough for illustrative purposes.)

Here is an example of how the above visitor can be used:

          public static void main( String arg[] ) throws Exception {
                Query qa = new Term( "a" );
                Query qb = new Prefix( "b" );
                Query qc = new Term( "c" );
                Query qd = new Term( "d" );

                Query q = new LowPass( new And( qa, new Select( "another_index", qb ), new Or( qc, qd ) ), 20 );

                System.out.println( q.accept( new PrinterVisitor() ) );
        }
  		

Building a document iterator out of a query

The interface {@link it.unimi.dsi.mg4j.query.nodes.Query} and its implementations provide the basic classes for the tree-level representation of a query. Building an iterator out of it can be thought of as a process of recursive instantiation of a query tree into an iterator tree; this is actually a sort of a copy visit, and it is indeed implemented as a special kind of visitor: the {@link it.unimi.dsi.mg4j.search.DocumentIteratorBuilderVisitor}. You can create one such visitor and use it to visit a query tree, obtaining as a result a document iterator that you can use to get the results.

To be more precise, let us recall the example presented in the last part of the {@linkplain it.unimi.dsi.mg4j.search overview of the search package}:

			Index subjectIndex = Index.getInstance( "mail-subject" );
			DocumentIterator it = AndDocumentIterator.getInstance( 
				subjectIndex.documents( "meeting" ), 
				subjectIndex.documents( "schedule" ), 
				subjectIndex.documents( "monday" ) 
			);
			while ( it.hasNext() ) {
					System.out.println( "Document #: " + it.nextDocument() );
					System.out.print( "\tPositions:" );
					for ( Interval interval: it )
						System.out.print( " " + interval );
					System.out.println();
			}
		

Here is an equivalent piece of code that uses the idea of decoupling the tree level from the iterator level.

			Index subjectIndex = Index.getInstance( "mail-subject" );
			Query q = new And( new Term( "meeting" ), new Term( "schedule" ), new Term( "monday" ) );
			DocumentIteratorBuilderVisitor visitor = new DocumentIteratorBuilderVisitor( null, subjectIndex, 0 );
			DocumentIterator it = q.accept( visitor );
			while ( it.hasNext() ) {
				System.out.println( "Document #: " + it.nextDocument() );
				System.out.print( "\tPositions:" );
				for ( Interval interval: it )
					System.out.print( " " + interval );
				System.out.println();
			}
		

A simple JavaCC-generated parser used by the {@link it.unimi.dsi.mg4j.query.Query} class. For details about the syntax, please consult the {@link it.unimi.dsi.mg4j.search} package documentation. If you need to know the relation between queries, syntax trees and document iterators please consult the {@link it.unimi.dsi.mg4j.query.nodes} package documentation.

Classes that compose {@linkplain it.unimi.dsi.mg4j.search.DocumentIterator iterators over documents}. Such iterators are returned, for instance, by {@link it.unimi.dsi.mg4j.index.IndexReader#documents(int)}.

Minimal-interval semantics

MG4J provides minimal-interval semantics. That is, if the index is full-text, a {@link it.unimi.dsi.mg4j.search.DocumentIterator} will provide a list of documents and, for each document, a list of minimal intervals. This intervals denote ranges of positions in the document that satisfy the iterator: for instance, if you compose two documents iterators using an {@link it.unimi.dsi.mg4j.search.AndDocumentIterator}, you will get as a result the intersection of the document lists of the underlying iterators. Moreover, for each document you will get the minimal set of intervals that contain one interval both from the first iterators and from the second one.

This information is of course very useful if you're going to assign a score to the document, as smaller intervals mean a more precise match. At the basic level (e.g., iterators returned by an index), the intervals returned upon a document are intervals of length one containing the term that was used to generate the iterator. Intervals for compound iterators are built in a natural way, preserving minimality. More details can be found in Charles L. A. Clarke and Gordon V. Cormack, Shortest-Substring Retrieval and Ranking (ACM Transactions on Information Systems, vol. 18, no. 1, Jan 2000, pages 44−78). Scorers for documents may be found in the {@link it.unimi.dsi.mg4j.search.score} package.

The algorithms used by classes in this package to compute minimal-interval operators are new: details can be found here.

Note that MG4J provides minimal-interval semantics for a set of indices. This extension is a significant improvement over single-index semantics. However, defining the exact meaning of a query is a nontrivial problem that will be fully dealt with in a forthcoming paper.

Searching with minimal-interval semantics

The aim of this section is to provide a minimal insight of how minimal-interval semantics works, and explain the basic syntax used by the {@link it.unimi.dsi.mg4j.query.Query} command-line tool. In this section we shall try to discuss this issue only through examples; we shall later explain how you can actually perform searches of this kind using MG4J.

Note that you do not have to understand the details of minimal-interval semantics to fruitfully use MG4J. Several natural operators (ordered conjunction, proximity limitation, etc.) are computed by MG4J very efficiently using minimal-interval semantics just under the hood.

MG4J solves queries on multiple indices; by saying so, we mean that you may have many indices concerning the same document collection, and you want to perform a query that may search on some of them. Think, for example, of a collection of emails: you might have generated a number of indices, to index their subjects, sender, recipient(s), body etc. All these indices can be thought of as individual entities, their only relation being that they index collections with the same number of documents, and that same-numbered documents conceptually "come" from the same source. The notion of multiple indices should not be new to the reader that is familiar with the {@link it.unimi.dsi.mg4j.document} package.

In our examples, we will assume that we have three indices (say, subject, from and body), and that subject is the used as default. Be warned that the actual syntax of queries in this section is immaterial (even though we shall stick to the syntax of {@link it.unimi.dsi.mg4j.query.parser.SimpleParser}).

Two different aspects should be taken into consideration when trying to determine which document actually match (i.e., satisfy) the query:

• first, one can consider this in a purely Boolean (true/false) setting: thus a document may either satisfy the query or not; this is actually the only information you can get for indices that do not contain positions;
• second, one can consider, for a document that matches the query in the above sense, which intervals (i.e., minimal sequences of consecutive words within the document) actually witness the match; this information will be available if the index contains positions.

In the following subsections, we shall give information about both kind of satisfiability.

Queries available on all indices

Simple queries

The simplest possible query consists in a single search term. The documents matching such a query are exactly those that contain the given term, with respect to the default index. In our example, the query

		 meeting
		 

		body: meeting
		 

Conjunctive queries

You can specify that more than one condition should be met in conjunction by using the AND operator. For example:

			meeting AND schedule
			

			schedule the meeting (should we schedule this meeting or not)?
			

The keyword AND can be subsituted with the symbol & or can even be omitted. So the above query is equivalent to:

			meeting & schedule
			

			meeting schedule
			

			body: meeting schedule
			

			body: meeting body: schedule
			

			body: (meeting schedule)
			

Disjunctive queries

You can also introduce a disjunctive (OR) query, like in

			meeting OR schedule
			

			meeting | schedule
			

Conjunctive and disjunctive operators can appear in the same query, with the rule that AND has higher priority than OR. So, for example:

			meeting AND schedule OR time
			

			meeting AND (schedule OR time)
			

Again, you can use index selectors, like in:

			body:meeting AND (schedule OR time)
			

			body:(meeting AND (schedule OR time))
			

Negative (NOT) queries

You can specify that you want to exclude documents containing a certain term, or, more in general, satisfying a certain query, by using the (unary, prefix) operator NOT. For example:

				body:(meeting AND NOT tomorrow) AND subject:schedule
				

				body:(meeting !tomorrow) subject:schedule
				

Negative queries are easily understood in a Boolean context, but may be more difficult as far as witnesses are concerned. Basically, the implementation of NOT works in such a way that NOT is actually used only for the Boolean match, but does not influence witnesses. In more detail, the only witness associated to a true NOT query is an empty interval.

Prefix and multiterm queries

A prefix query is a simple query that is matched by all terms starting from the same nonempty prefix. For example:

			   govern*
			   

To be true, the expansion of a prefix query does not really lead to an OR, but rather to what we call a multiterm query: a multiterm query is like an OR, but it can only contain terms as subquery, and behaves under many respects like a single term. It is unusual to specify manually a multiterm query—rather, some query expansion mechanism like prefixes should be used, but if you want to try manually, a multiterm query can be obtained using the + operator. For example:

			   house + houses + housing
			   

			   house OR houses OR housing
			   

Note, however, that trying to use + instead of OR does not work if the subqueries are not simple queries, or if they concern different indices. For example:

			   house + title:meeting
			   

You may wonder why multiterm queries are needed, if they are essentially the same as OR queries. The first answer is efficiency: a multiterm query should be more efficient than an OR query.

The second answer is more subtle, and has to do with scorers. A scorer is a way to assign a score to a document that satisfies a query. Many scorers actually work by summing up suitable partial scores that depend on the document and on one of the terms in the query. Such partial scores are often function of the count (number of times the term appears in the document) and on the frequency (number of documents where the term appears), and they are often really high when the term has a low frequency. The idea behind this is that if I write:

			   computer OR methacrylic
			   

Nonetheless, trying to use these scorers on automatically expanded queries may lead to many problems. For example, suppose you expanded

			   govern*
			   

			   government OR governance OR governor OR governing 
			   

			   government + governance + governor + governing 
			   

Queries available on indices with positions

Ordered conjunctive queries

The operator of ordered conjunction < works like AND, but requires the subqueries to be satisfied in the exact order in which they are specified, even though not necessarily consecutively. For example:

			meeting < schedule
			

			schedule the meeting (should we schedule this meeting or not)?
			

Note that the ordering between witnesses is strict: for instance, the query

			meeting < meeting
			

In this case, it makes no sense (and it is indeed forbidden) to select a different index for the subqueries to be matched.

Consecutivity (phrasal queries)

You can specify that you want that some terms appear consecutively by using " (quotes). For example:

				"meeting schedule"
				

				"meeting (schedule OR time)"
				

More precisely, the quotes operators is satisfied if there is a sequence of consecutive witnesses, with each witness coming from a different subquery, in the same order in which the queries appear.

Note that

				"meeting schedule OR time"
				

				body:"meeting schedule"
				

				"body:meeting subject:schedule"
				

The symbol $ (dollar) can be used to specify an arbitrary word in a consecutive query. For instance,

			meeting $ schedule
			

Proximity limit

As we have discussed, when a document matches a given query, there will be one or more witnesses within the document. Each such witness is a consecutive sequence of positions in the document that witness the matching. For example, consider the query

			  body:((meeting schedule) OR "John Smith") OR subject:alarm
			  

This query will be matched by documents that contain the term "alarm" in their subject, and by documents that contain either the terms "meeting" and "schedule" or the (exact) sentence "John Smith" in their body. For every document that matches the query, there will be two sets of matching intervals, one about the body and the other about the subject; at least one of these two sets will be nonempty (because of the OR keyword). Intervals concerning the subject will simply be intervals of length one that correspond to the positions where the term "alarm" appears in the subject. Intervals concerning the body will be either intervals of length two corresponding to the positions where the sentence "John Smith" appears in the body, or intervals of length two or more where both "meeting" and "schedule" appear.

You might want to accept only matching intervals up to a certain length; for example, suppose you don't want to take into considerations intervals that contain "meeting" and "schedule" too far apart, say at a distance greater than 10 words. You can do this by using the proximity limit operator ~. Just rewrite the previous query as

			  body:((meeting schedule)~10 OR "John Smith") OR subject:alarm
			  

This way, you are simply discarding the matching intervals that contain the terms "meeting" and "schedule" if their length (number of words) is greater than 10 (i.e., if "meeting" and "schedule" are separated by more than 8 words).

The proximity limit operator can be used at any point, and limits the length of all matching intervals of the query it is applied to. Note, however, that it may only be used on full-text indices.

Difference

The Brouwerian difference operator is specified using - (minus). It is a rather esoteric operator that is rarely met by the end user, and that, given two subqueries, kills the witnesses of the first query (the minuend) that contain one or more witnesses of the second query (the subtrahend). By definition, for documents that satisfy the minuend, but not the subtrahend, the witnesses are unchanged. For instance, the following query

				schedule < meeting - this
				

				schedule the meeting (should we schedule this meeting or not)?
				

				schedule < meeting - (this | the)
				

As an additional feature, you can specify a left and a right margin that will be used to enlarge the intervals of the subtrahend. For instance,

				"schedule < meeting - [[1,2]] this"
				

will kill intervals of the minuend that contain the whole fragment "schedule this meeting or" (so no interval will be killed at all).

Queries available on payload-based indices

Actually, the atomic queries discussed above (term, prefix, etc.) can be used with standard indices, that is, indices of fields containing text. For payload-based indices, which represent document metadata such as dates, the standard query available in MG4J is a range query in which the first and last valid values are specified by the user. The resulting query is satisfying by all documents whose field is in the range. Both the first and the last value can be omitted. for instance, the following query

				date:[ 20/2/2007 .. 23/2/2007 ]
				

				date:[ .. 23/2/2007 ]
				

Range queries must not be used as a generic query mechanism, but rather to refine the result of a query over document content: a ranked query composed uniquely by a range query will have to scan the whole payload-based index just to return a few results.

Building and composing document iterators

The {@link it.unimi.dsi.mg4j.search} package contains all the classes needed to build a query and to match it against a certain collection of indices. This is actually only the semantic counterpart to a query; for the syntactic aspects, please refer to the {@link it.unimi.dsi.mg4j.query.nodes} package.

Basic classes

An {@link it.unimi.dsi.mg4j.search.Interval} represents a consecutive set of natural numbers, that is, a witness within a document (in this case, numbers represent the positions within a document: 0 is the position of the first word, 1 is the position of the second and so on). An {@link it.unimi.dsi.mg4j.search.IntervalIterator} is an iterator that returns intervals: typically, an interval iterator will return all intervals witnessing a certain query for a certain document (and a certain index).

For example, the query

			  body:((meeting schedule)~10 OR "John Smith") OR subject:alarm
			  

It is always understood that intervals are returned in increasing order (of their left, or equivalently right, extreme).

A {@link it.unimi.dsi.mg4j.search.DocumentIterator} is used to scan a whole collection of indices for a query. At every given moment, the iterator will be able to return the next document matching the query, and, for full-text indices, you will also be able to {@linkplain it.unimi.dsi.mg4j.search.DocumentIterator#intervalIterator(it.unimi.dsi.mg4j.index.Index) get the interval iterators of the witnesses for that document and for a specific index}.

Obtaining and composing document iterators

The simplest kind of {@link it.unimi.dsi.mg4j.search.DocumentIterator} you can build is an {@link it.unimi.dsi.mg4j.index.IndexIterator}: it is a document iterator that scans a specific index for a specific term. You don't actually build an index iterator directly, but you rather obtain one by calling the {@link it.unimi.dsi.mg4j.index.Index#documents(CharSequence)} (or, equivalently, {@link it.unimi.dsi.mg4j.index.IndexReader#documents(CharSequence)}) method, that returns the set of documents containing a given term (and witnesses will be the single occurrences of such term).

Hence, for example, the following snippet opens a full-text index whose basename is mail-subject, and prints out all documents containing the word "meeting", each with the sequence of positions where the word appears (all intervals will be actually singletons). (Note that a document iterator over a single index is itself iterable, and the {@link it.unimi.dsi.mg4j.search.DocumentIterator#iterator()} method is actually an alias for {@link it.unimi.dsi.mg4j.search.DocumentIterator#intervalIterator()}).

			Index subjectIndex = Index.getInstance( "mail-subject" );
			DocumentIterator it = subjectIndex.documents( "meeting" );
			while ( it.hasNext() ) {
					System.out.println( "Document #: " + it.nextDocument() );
					System.out.print( "\tPositions:" );
					for ( Interval interval: it )
						System.out.print( " " + interval );
					System.out.println();
			}
		

A number of classes in this package can be used to compose iterators; more precisely, for each query operator discussed above there is a corresponding class in this package. Each such class has a factory method that allows one to build new document iterators by composing existing iterators.

For example, the following snippet shows how to search for mails containing the words "meeting", "schedule" and "monday".

			Index subjectIndex = Index.getInstance( "mail-subject" );
			DocumentIterator it = AndDocumentIterator.getInstance( 
				subjectIndex.documents( "meeting" ), 
				subjectIndex.documents( "schedule" ), 
				subjectIndex.documents( "monday" ) 
			);
			while ( it.hasNext() ) {
					System.out.println( "Document #: " + it.nextDocument() );
					System.out.print( "\tPositions:" );
					for ( Interval interval: it )
						System.out.print( " " + interval );
					System.out.println();
			}
		

The following table shows the correspondence between query operators and composition classes:

Note, however, that {@link it.unimi.dsi.mg4j.search.PayloadPredicateDocumentIterator} is actually a completely generic predicate-based class that just returns documents whose payload satisfis a predicate.

Queries and document iterators

Even though it is perfectly legal to build document iterators by using these classes directly, this is not the natural way to do that. One should rather build a syntactic object corresponding to a query, and then make it into a document iterator that is, in some sense, the semantic counterpart of the query itself. To have more information about how this works exaclty, please consult the overview of the {@link it.unimi.dsi.mg4j.query.nodes} package.

Classes for assigning scores to documents.

The content of this package has changed significantly in MG4J 1.1 (hopefully for the better). A {@link it.unimi.dsi.mg4j.search.score.Scorer} is an object that wraps an underlying {@link it.unimi.dsi.mg4j.search.DocumentIterator} and assigns scores to the documents returned by the underlying iterator. In general, once a scorer has {@linkplain it.unimi.dsi.mg4j.search.score.Scorer#wrap(it.unimi.dsi.mg4j.search.DocumentIterator) wrapped a document iterator} one just calls {@link it.unimi.dsi.fastutil.ints.IntIterator#nextInt() nextInt()} and {@link it.unimi.dsi.mg4j.search.score.Scorer#score()} to get scored documents (some iterators might support {@linkplain it.unimi.dsi.mg4j.search.score.Scorer#score(it.unimi.dsi.mg4j.index.Index) index-restricted scoring}, but this is optional).

If the scorer is a {@link it.unimi.dsi.mg4j.search.score.DelegatingScorer}, then by contract it just delegates all {@link it.unimi.dsi.fastutil.ints.IntIterator}'s methods to the underlying iterator. In this case, it is possible to advance manually the underlying iterator and call {@link it.unimi.dsi.mg4j.search.score.Scorer#score()}. While this behaviour is useless for general users, it is essential for {@linkplain it.unimi.dsi.mg4j.search.score.AbstractAggregator aggregated scorers}, which combine several delegating scorers and provide services such as equalisation and interval caching (in case more than one component scorer uses intervals). See, for instance, {@link it.unimi.dsi.mg4j.search.score.LinearAggregator}.

Visitors for composite {@linkplain it.unimi.dsi.mg4j.search.DocumentIterator document iterators}.

Composites and visitors

A {@link it.unimi.dsi.mg4j.search.DocumentIterator} (in particular, those provided by MG4J in the package {@link it.unimi.dsi.mg4j.search}) is usually structured as a composite, with operators as internal nodes and {@link it.unimi.dsi.mg4j.index.IndexIterator}s as leaves. A composite can be explored using a visitor: thus, the {@link it.unimi.dsi.mg4j.search.DocumentIterator} interface provides two methods, {@link it.unimi.dsi.mg4j.search.DocumentIterator#accept(it.unimi.dsi.mg4j.search.visitor.DocumentIteratorVisitor) accept(DocumentIteratorVisitor)} and {@link it.unimi.dsi.mg4j.search.DocumentIterator#acceptOnTruePaths(it.unimi.dsi.mg4j.search.visitor.DocumentIteratorVisitor) acceptOnTruePaths(DocumentIteratorVisitor)}, that let a {@link it.unimi.dsi.mg4j.search.visitor.DocumentIteratorVisitor} visit the composite structure.

A {@link it.unimi.dsi.mg4j.search.visitor.DocumentIteratorVisitor} provides methods for visiting in {@linkplain it.unimi.dsi.mg4j.search.visitor.DocumentIteratorVisitor#visitPre(it.unimi.dsi.mg4j.search.DocumentIterator) preorder} and in {@linkplain it.unimi.dsi.mg4j.search.visitor.DocumentIteratorVisitor#visitPost(it.unimi.dsi.mg4j.search.DocumentIterator) postorder} all internal nodes. Leaves have a {@linkplain it.unimi.dsi.mg4j.search.visitor.DocumentIteratorVisitor#visit(it.unimi.dsi.mg4j.index.IndexIterator) single visit method} instead. Note that a {@link it.unimi.dsi.mg4j.search.visitor.DocumentIteratorVisitor} must be (re)usable after each call to {@link it.unimi.dsi.mg4j.search.visitor.DocumentIteratorVisitor#prepare() prepare()}.

The abstract class {@link it.unimi.dsi.mg4j.search.visitor.AbstractDocumentIteratorVisitor} provides stubs implementing internal visits and {@link it.unimi.dsi.mg4j.search.visitor.DocumentIteratorVisitor#prepare() prepare()} as no-ops.

Counting term occurrences

An example of the utility of visitors for document iterators is given by term counting: using a number of coordinated visitors, it is possible to compute a count for each term appearing in a (no matter how complex) query. The count can be used as an input for counting-based scoring schemes, such as BM25 or cosine-based measures. For more information, please read the documentation of {@link it.unimi.dsi.mg4j.search.visitor.CounterCollectionVisitor}.

Line-command tools for index construction.

Package Specification

The classes in this package are completely general utility classes that may be useful outside of MG4J. In particular, {@link it.unimi.dsi.mg4j.util.MutableString} is a highly-tuned, versatile class for content-based mutable strings.

Another general-purpose important component is {@link it.unimi.dsi.mg4j.util.MinimalPerfectHash}, which implements state-of-the-art, hypergraph-based algorithms for the construction of ordered minimal perfect hash tables.

If minimal perfect hash tables are too large, a good alternative is an {@link it.unimi.dsi.mg4j.util.ImmutableExternalPrefixDictionary}, which keeps most data in compressed form on disk, and uses a small in-memory index to access those data.