it.unimi.dsi.mg4j.util

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.

Instances of this class represent a set of character sequences or primitive-type arrays (with false positives) using a Bloom filter.

MG4J uses often flyweight copies to implement multithreading on read-only (but maybe stateful) classes.

This class stores a list of strings using front-coding compression (of course, the compression will be reasonable only if the list is sorted, but you could also use instances of this class just as a handy way to manage a large amount of strings).

Instance of this class are built starting from a lexicographically ordered list of cern.colt.bitvector.BitVector s representing binary words.

A prefix dictionary is a data structure that stores efficiently a lexicographically ordered list of character sequences so that it is possible to obtain, given a character sequence s, its position in the sequence, and also the (possibly empty) interval of the sequence composed by character sequences that are extensions of s.

Instances of this class map transparently strings into a binary trie.

Instances of this class represent a set of integers (with false positives) using a Bloom filter.

This class source exemplifies a signed minimal perfect hash table that signes each term with the term itself, thus avoiding false positives.

Given a list of terms without duplicates, the constructors of this class finds an order-preserving minimal perfect hash function for the list.

Motivation

The classical Java string classes, java.lang.String and java.lang.StringBuffer , lie at the extreme of a spectrum (immutable and mutable).

However, large-scale text indexing requires some features that are not provided by these classes: in particular, the possibility of using a mutable string, once frozen, in the same optimised way of an immutable string.

It may happen that a list of strings compresses very well using front coding, but unfortunately alphabetical order is not the right order for the strings in the list.

This class provides a simple way to log progress information about long-lasting activities.

To use this class, you first create a new instance by passing a , a org.apache.log4j.Priority and a time interval in millisecond (you can use constants such as ProgressLogger.ONE_MINUTE ). Information will be logged about the current state of affairs no more often than the given time interval.

This class provides a simple way to display progress information about long-lasting activities.

All accessors defined in org.apache.commons.configuration.PropertiesConfiguration have a polymorphic counterpart taking an java.lang.Enum instead of a string: java.lang.Enum.name and java.lang.String.toLowerCase are applied before delegating to the corresponding string-based method.

Minimal perfect hash tables will always return a result, even for terms that were not present in the collection indexed by the table.

Ternary search trees are a data structure used to store words over an alphabet; they are a useful alternatives to tries when the alphabet is large.

Ternary interval search trees have the additional properties of being able to locate quickly intervals of words extending a given prefix (where “quickly” means that no more successful character comparisons than the prefix length are performed).

The of the Java API are a powerful tool; however, when searching for a constant pattern many algorithms can increase of orders magnitude the speed of a search.

This class provides constant-pattern text search facilities by implementing Sunday's QuickSearch (a simplified but very effective variant of the Boyer—Moore search algorithm) using compact approximators, a randomised data structure that can accomodate in a small space (but in an approximated way) the bad-character shift table of a large alphabet such as Unicode.

Since a large subset of US-ASCII is used in all languages (e.g., whitespace, punctuation, etc.), this class caches separately the shifts for the first 128 Unicode characters, resulting in very good performance even on text in pure US-ASCII.

Note that the MutableString.indexOf(MutableString) indexOf methods of MutableString use a even more simplified variant of QuickSearch which is less efficient, but has a smaller setup time and does not generate any object.