Instances of this class write on a dump stream the string in the domain * of the prefix map. More precisely, the dump stream is formed by blocks, and each * block (with user-definable length, possibly the size of a basic disk I/O operation) * is filled as much as possible with strings front coded and compressed with a * {@link it.unimi.dsi.compression.HuTuckerCodec}. * Each block starts with the length of the first string in unary, followed by the encoding of the * string. Then, for each string we write in unary the length of the common prefix (in characters) * with the previous string, the length of the remaining suffix (in characters) * and finally the encoded suffix. Note that if the encoding of a string is longer than a block, * the string will occupy more than one block. * *
We keep track using an {@link ImmutableBinaryTrie} * of the strings at the start of each block in {@link HuTuckerCodec Hu–Tucker coding}: * thus, we are able to retrieve the interval corresponding * to a given prefix by calling {@link ImmutableBinaryTrie#getApproximatedInterval(BooleanIterator) getApproximatedInterval()} * and scanning at most two blocks. * *
There are two kinds of external prefix maps: self-contained and non-self-contained. * In the first case, you get a serialised object that you can load at any time. The dump * stream is serialised with the object and expanded at each deserialisation in the Java temporary directory. * If you deserialise a map several times, you will get correspondingly many copies of * the dump stream in the temporary directory. The dump streams are deleted when the JVM * exits. This mechanism is not very efficient, but since this class implements several * interfaces it is essential that clients can make things work in a standard way. * *
Alternatively, you can give at creation time a filename for the dump stream. * The resulting non-self-contained external prefix map * can be serialised, but after deserialisation * you need to set the {@linkplain #setDumpStream(CharSequence) dump stream filename} * or even directly the {@linkplain #setDumpStream(InputBitStream) dump stream} (for instance, to * an {@linkplain it.unimi.dsi.io.InputBitStream#InputBitStream(byte[]) input bit stream * wrapping a byte array where the dump stream has been loaded}). You can deserialise many * copies of an external prefix map, letting all copies share the same dump stream. * *
This data structure is not synchronised, and concurrent reads may cause problems * because of clashes in the usage of the underlying input bit stream. It would not * be a good idea in any case to open a new stream for each caller, as that would * certainly lead to disk thrashing. * *
The {@linkplain #main(String[]) main method} of this class
* helps in building large external prefix maps.
*
* @author Sebastiano Vigna
* @since 0.9.3
*/
public class ImmutableExternalPrefixMap extends AbstractPrefixMap implements Serializable {
private final static boolean DEBUG = false;
public static final long serialVersionUID = 1L;
/** The standard block size (in bytes). */
public static final int STD_BLOCK_SIZE = 1024;
/** The maximum number of entry in the cache map. */
public static final int CACHE_MAX_SIZE = 1024;
/** The in-memory data structure used to approximate intervals.. */
final protected ImmutableBinaryTrie
* This constructor does not assume that {@link CharSequence} instances returned by
*
* This constructor does not assume that {@link CharSequence} instances returned by
*
* This constructor does not assume that {@link CharSequence} instances returned by
*
* This constructor does not assume that {@link CharSequence} instances returned by
* This method sets the dump file used by this map, and should be only
* called after deserialisation, providing exactly the file generated at
* creation time. Essentially anything can happen if you do not follow the rules.
*
* Note that this method will attempt to close the old stream, if present.
*
* @param dumpStreamFilename the name of the dump file.
* @see #setDumpStream(InputBitStream)
*/
public void setDumpStream(final CharSequence dumpStreamFilename) throws FileNotFoundException{
ensureNotSelfContained();
safelyCloseDumpStream();
iteratorIsUsable = false;
final long newLength = new File(dumpStreamFilename.toString()).length();
if (newLength != dumpStreamLength)
throw new IllegalArgumentException("The size of the new dump file (" + newLength + ") does not match the original length (" + dumpStreamLength + ")");
dumpStream = new InputBitStream(dumpStreamFilename.toString(), (int)(blockSize / 8));
}
/** Sets the dump stream of this external prefix map to a given input bit stream.
*
* This method sets the dump file used by this map, and should be only
* called after deserialisation, providing a repositionable stream containing
* exactly the file generated at
* creation time. Essentially anything can happen if you do not follow the rules.
*
* Using this method you can load an external prefix map in core memory, enjoying
* the compactness of the data structure, but getting much more speed.
*
* Note that this method will attemp to close the old stream, if present.
*
* @param dumpStream a repositionable input bit stream containing exactly the dump stream generated
* at creation time.
* @see #setDumpStream(CharSequence)
*/
public void setDumpStream(final InputBitStream dumpStream) {
ensureNotSelfContained();
safelyCloseDumpStream();
iteratorIsUsable = false;
this.dumpStream = dumpStream;
}
private void ensureStream() {
if (dumpStream == null) throw new IllegalStateException("This external prefix map has been deserialised, but no dump stream has been set");
}
@Override
public Interval getInterval(final CharSequence prefix) {
ensureStream();
// If prefix contains any character not coded by the prefix coder, we can return the empty interval.
if (! isEncodable(prefix)) return Intervals.EMPTY_INTERVAL;
// We recover the left extremes of the intervals where extensions of prefix could possibly lie.
final Interval interval = intervalApproximator.getApproximatedInterval(prefix);
// System.err.println("Approximate interval: " + interval + " , terms: [" + blockStart[interval.left] + ", " + blockStart[interval.right] + "]");
if (interval == Intervals.EMPTY_INTERVAL) return interval;
try {
dumpStream.position(blockOffset[interval.left] * blockSize);
dumpStream.readBits(0);
iteratorIsUsable = false;
final MutableString s = new MutableString();
int suffixLength, prefixLength = -1, count = blockStart[interval.left], blockEnd = blockStart[interval.left + 1], start = -1, end = -1;
/* We scan the dump file, stopping if we exhaust the block */
while(count < blockEnd) {
if (prefixLength < 0) prefixLength = 0;
else prefixLength = dumpStream.readUnary();
suffixLength = dumpStream.readUnary();
s.delete(prefixLength, s.length());
s.length(prefixLength + suffixLength);
for(int i = 0; i < suffixLength; i++) s.charAt(i + prefixLength, symbol2char[decoder.decode(dumpStream)]);
if (s.startsWith(prefix)) {
start = count;
break;
}
count++;
}
/* If we did not find our string, there are two possibilities: if the
* interval contains one point, there is no string extending prefix. But
* if the interval is larger, the first string of the second block in the
* interval must be an extension of prefix. */
if (start < 0 && interval.length() == 1) return Intervals.EMPTY_INTERVAL;
else start = count;
end = start + 1;
//assert dumpStream.readBits() <= blockSize;
/* If the interval contains more than one point, the last string with
* given prefix is necessarily contained in the last block, and we
* must restart the search process. */
if (interval.length() > 1) {
dumpStream.position(blockOffset[interval.right] * blockSize);
dumpStream.readBits(0);
s.length(0);
end = blockStart[interval.right];
blockEnd = blockStart[interval.right + 1];
prefixLength = -1;
}
while(end < blockEnd) {
if (prefixLength < 0) prefixLength = 0;
else prefixLength = dumpStream.readUnary();
suffixLength = dumpStream.readUnary();
s.delete(prefixLength, s.length());
s.length(prefixLength + suffixLength);
for(int i = 0; i < suffixLength; i++) s.charAt(i + prefixLength, symbol2char[decoder.decode(dumpStream)]);
if (! s.startsWith(prefix)) break;
end++;
}
return Interval.valueOf(start, end - 1);
} catch (final IOException rethrow) {
throw new RuntimeException(rethrow);
}
}
@Override
protected MutableString getTerm(final int index, final MutableString s) {
ensureStream();
// We perform a binary search to find the block to which s could possibly belong.
int block = Arrays.binarySearch(blockStart, index);
if (block < 0) block = - block - 2;
try {
dumpStream.position(blockOffset[block] * blockSize);
dumpStream.readBits(0);
iteratorIsUsable = false;
int suffixLength, prefixLength = -1;
for(int i = index - blockStart[block] + 1; i-- != 0;) {
if (prefixLength < 0) prefixLength = 0;
else prefixLength = dumpStream.readUnary();
suffixLength = dumpStream.readUnary();
s.delete(prefixLength, s.length());
s.length(prefixLength + suffixLength);
for(int j = 0; j < suffixLength; j++) s.charAt(j + prefixLength, symbol2char[decoder.decode(dumpStream)]);
}
return s;
}
catch(final IOException rethrow) {
throw new RuntimeException(rethrow);
}
}
private long getIndex(final Object o) {
final CharSequence term = (CharSequence)o;
final int cached = cache.getAndMoveToFirst(new MutableString(term));
if (cached != -1) return cached;
ensureStream();
// If term contains any character not coded by the prefix coder, we can return -1
if (! isEncodable(term)) return -1;
/* If term is in the map, any string extending term must follow term. Thus,
* term can be in the map only if it can be found in the left block
* of an approximated interval for itself. */
final Interval interval = intervalApproximator.getApproximatedInterval(term);
if (interval == Intervals.EMPTY_INTERVAL) return -1;
try {
dumpStream.position(blockOffset[interval.left] * blockSize);
dumpStream.readBits(0);
iteratorIsUsable = false;
final MutableString s = new MutableString();
int suffixLength, prefixLength = -1, count = blockStart[interval.left];
final int blockEnd = blockStart[interval.left + 1];
/* We scan the dump file, stopping if we exhaust the block */
while(count < blockEnd) {
if (prefixLength < 0) prefixLength = 0;
else prefixLength = dumpStream.readUnary();
suffixLength = dumpStream.readUnary();
s.delete(prefixLength, s.length());
s.length(prefixLength + suffixLength);
for(int i = 0; i < suffixLength; i++) s.charAt(i + prefixLength, symbol2char[decoder.decode(dumpStream)]);
if (s.equals(term)) {
if (cache.size() >= CACHE_MAX_SIZE) cache.removeFirstInt();
cache.put(s.copy(), count);
return count;
}
count++;
}
return -1;
}
catch (final IOException rethrow) {
throw new RuntimeException(rethrow);
}
}
@Override
public boolean containsKey(final Object term) {
return getIndex(term) != -1;
}
@Override
public long getLong(final Object o) {
final long result = getIndex(o);
return result == -1 ? defRetValue : result;
}
/** An iterator over the dump stream. It does not use the interval approximator—it just scans the file. */
private final class DumpStreamIterator implements ObjectIterator The iterator returned by this method scans directly the dump stream.
*
* Note that the returned iterator uses the same stream as all get methods. Calling such methods while
* the iterator is being used will produce an {@link IllegalStateException}.
*
* @return an iterator over the map that just scans the dump stream.
*/
public ObjectIteratorDumpStreamIterator was not
* followed by a call to any get method. */
protected transient boolean iteratorIsUsable;
/** A reference to the dump stream. */
protected transient InputBitStream dumpStream;
/** A cache for the most recent queries */
protected transient Object2IntLinkedOpenHashMapterms.iterator() will be distinct. Thus, it can be safely used with
* {@link FileLinesMutableStringIterable}.
*
* @param terms an iterable whose iterator will enumerate in lexicographical order the terms for the
* map.
* @param blockSizeInBytes the block size (in bytes).
* @param dumpStreamFilename the name of the dump stream, or {@code null} for a self-contained map.
*/
public ImmutableExternalPrefixMap(final Iterable terms, final int blockSizeInBytes, final CharSequence dumpStreamFilename) throws IOException {
this.blockSize = blockSizeInBytes * 8;
this.selfContained = dumpStreamFilename == null;
// First of all, we gather frequencies for all Unicode characters
int[] frequency = new int[Character.MAX_VALUE + 1];
int maxWordLength = 0;
CharSequence s;
int count = 0;
final MutableString prevTerm = new MutableString();
for(final Iterator i = terms.iterator(); i.hasNext();) {
s = i.next();
maxWordLength = Math.max(s.length(), maxWordLength);
for(int j = s.length(); j-- != 0;) frequency[s.charAt(j)]++;
final int cmp = prevTerm.compareTo(s);
if (count > 0 && cmp >= 0) throw new IllegalArgumentException("The provided term collection " + (cmp == 0 ? "contains duplicates" : "is not sorted") + " [" + prevTerm + ", " + s + "]");
count++;
prevTerm.replace(s);
}
size = count;
// Then, we compute the number of actually used characters
count = 0;
for(int i = frequency.length; i-- != 0;) if (frequency[i] != 0) count++;
/* Now we remap used characters in f, building at the same time maps from
* symbol to characters and from characters to symbols. */
int[] packedFrequency = new int[count];
symbol2char = new char[count];
char2symbol = new Char2IntOpenHashMap(count);
char2symbol.defaultReturnValue(-1);
for(int i = frequency.length, k = count; i-- != 0;)
if (frequency[i] != 0) {
packedFrequency[--k] = frequency[i];
symbol2char[k] = (char)i;
char2symbol.put((char)i, k);
}
char2symbol.trim();
// We now build the coder used to code the strings
final PrefixCoder prefixCoder;
final PrefixCodec codec;
final BitVector[] codeWord;
if (packedFrequency.length != 0) {
codec = new HuTuckerCodec(packedFrequency);
prefixCoder = codec.coder();
decoder = codec.decoder();
codeWord = prefixCoder.codeWords();
}
else {
// This handles the case of a collection without words
codec = null;
prefixCoder = null;
decoder = null;
codeWord = null;
}
packedFrequency = frequency = null;
// We now compress all strings using the given codec mixed with front coding
final OutputBitStream output;
if (selfContained) {
final File temp = File.createTempFile(this.getClass().getName(), ".dump");
temp.deleteOnExit();
tempDumpStreamFilename = temp.toString();
output = new OutputBitStream(temp, blockSizeInBytes);
}
else output = new OutputBitStream(tempDumpStreamFilename = dumpStreamFilename.toString(), blockSizeInBytes);
// This array will contain the delimiting words (the ones at the start of each block)
boolean isDelimiter;
int length, prevTermLength = 0, bits;
int prefixLength = 0, termCount = 0;
int currBuffer = 0;
final IntArrayList blockStarts = new IntArrayList();
final IntArrayList blockOffsets = new IntArrayList();
final ObjectArrayListterms.iterator() will be distinct. Thus, it can be safely used with
* {@link FileLinesMutableStringIterable}.
*
* @param terms a collection whose iterator will enumerate in lexicographical order the terms for
* the map.
* @param dumpStreamFilename the name of the dump stream, or {@code null} for a self-contained map.
*/
public ImmutableExternalPrefixMap(final Iterable terms, final CharSequence dumpStreamFilename) throws IOException {
this(terms, STD_BLOCK_SIZE, dumpStreamFilename);
}
/**
* Creates an external prefix map with specified block size.
*
* terms.iterator() will be distinct. Thus, it can be safely used with
* {@link FileLinesMutableStringIterable}.
*
* @param blockSizeInBytes the block size (in bytes).
* @param terms a collection whose iterator will enumerate in lexicographical order the terms for
* the map.
*/
public ImmutableExternalPrefixMap(final Iterable terms, final int blockSizeInBytes) throws IOException {
this(terms, blockSizeInBytes, null);
}
/**
* Creates an external prefix map with block size {@link #STD_BLOCK_SIZE}.
*
* terms.iterator() will be distinct. Thus, it can be safely used with
* {@link FileLinesMutableStringIterable}.
*
* @param terms a collection whose iterator will enumerate in lexicographical order the terms for
* the map.
*/
public ImmutableExternalPrefixMap(final Iterable terms) throws IOException {
this(terms, null);
}
private void safelyCloseDumpStream() {
try {
if (this.dumpStream != null) this.dumpStream.close();
}
catch (final IOException ignore) {}
}
private void ensureNotSelfContained() {
if (selfContained) throw new IllegalStateException("You cannot set the dump file of a self-contained external prefix map");
}
private boolean isEncodable(final CharSequence s) {
for(int i = s.length(); i-- != 0;) if (! char2symbol.containsKey(s.charAt(i))) return false;
return true;
}
/** Sets the dump stream of this external prefix map to a given filename.
*
*