com.aliasi.dict
Class TrieDictionary<C>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractSet<DictionaryEntry<C>>
          com.aliasi.dict.AbstractDictionary<C>
              com.aliasi.dict.TrieDictionary<C>

Type Parameters:

C - the type of object stored in this dictionary

All Implemented Interfaces:

Dictionary<C>, Compilable, Serializable, Iterable<DictionaryEntry<C>>, Collection<DictionaryEntry<C>>, Set<DictionaryEntry<C>>

public class TrieDictionary<C>
extends AbstractDictionary<C>
implements Serializable, Compilable

A TrieDictionary stores a dictionary using a character trie structure. This requires a constant amount of space for each entry and each prefix of an entry's string. Lookups take an amount of time proportional to the length of the string being looked up, with each character requiring a lookup in a map. The lookup is done with binary search in this implementation in time proportional to the log of the number of characters, for a total lookup time of O(n log c) where n is the number of characters in the string being looked up and c is the number of charactes.

Tries are a popular data structure; see the Wikipedia Trie topic for examples and references. Tries are also used in the language model classes TrieCharSeqCounter and TrieIntSeqCounter and the compiled forms of all of the language models.

Compilation and Serialization

The trie dictionary implements both the Java Serializable and LingPipe Compilable interfaces to write the contents of a trie dictionary to an object output. Both approaches produce the same result and the dictionary read back in will be an instance of TrieDictionary and equivalent to the dictionary that was serialized or compiled.

Since:

LingPipe2.1

Version:

3.8

Author:

Bob Carpenter

See Also:

Serialized Form

Constructor Summary

TrieDictionary()
Construct a trie-based dictionary.

Method Summary

void	addEntry(DictionaryEntry<C> entry) Equal entries will be ignored.
void	compileTo(ObjectOutput out) Compile the entries in this dictionary to the specified object output.
Iterator<DictionaryEntry<C>>	iterator() Returns an iterator over all of the dictionary entries for this dictioniary.
DictionaryEntry<C>[]	phraseEntries(String phrase) Deprecated.
Iterator<DictionaryEntry<C>>	phraseEntryIt(String phrase) Returns an iterator over the dictionary entries with the specified phrase.

Methods inherited from class com.aliasi.dict.AbstractDictionary

categoryEntries, categoryEntryIt, categoryEntryList, entries, entryList, phraseEntryList, size

Methods inherited from class java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

add, addAll, clear, contains, containsAll, isEmpty, remove, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Set

add, addAll, clear, contains, containsAll, equals, hashCode, isEmpty, remove, removeAll, retainAll, toArray, toArray

Constructor Detail

TrieDictionary

public TrieDictionary()

Construct a trie-based dictionary.

Method Detail

phraseEntries

@Deprecated
public DictionaryEntry<C>[] phraseEntries(String phrase)

Deprecated.

Description copied from class: AbstractDictionary

Returns the dictionary entries with the specified phrase.

Implementation Note: This implementation buffers the results of AbstractDictionary.phraseEntryIt(String) in a collection and then converts it to an array.

Specified by:

phraseEntries in interface Dictionary<C>

Overrides:

phraseEntries in class AbstractDictionary<C>

Parameters:

phrase - The phrase to look up.

Returns:

The entries with the specified phrase.

phraseEntryIt

public Iterator<DictionaryEntry<C>> phraseEntryIt(String phrase)

Description copied from class: AbstractDictionary

Returns an iterator over the dictionary entries with the specified phrase.

Implementation Note: This implementation filters the result of AbstractCollection.iterator() for entries with a matching phrase.

Specified by:

phraseEntryIt in interface Dictionary<C>

Overrides:

phraseEntryIt in class AbstractDictionary<C>

Parameters:

phrase - The phrase to look up.

Returns:

Iterator over the entries with the specified phrase.

addEntry

public void addEntry(DictionaryEntry<C> entry)

Equal entries will be ignored.

Specified by:

addEntry in interface Dictionary<C>

Overrides:

addEntry in class AbstractDictionary<C>

Parameters:

entry - Dictionary entry to add.

iterator

public Iterator<DictionaryEntry<C>> iterator()

Returns an iterator over all of the dictionary entries for this dictioniary. This is the implementation of the iterator view of this dictionary as a collection (set of entries).

Specified by:

iterator in interface Iterable<DictionaryEntry<C>>

Specified by:

iterator in interface Collection<DictionaryEntry<C>>

Specified by:

iterator in interface Set<DictionaryEntry<C>>

Specified by:

iterator in class AbstractCollection<DictionaryEntry<C>>

Returns:

An iterator over all of the dictionary entries for this dictioniary.

compileTo

public void compileTo(ObjectOutput out)
               throws IOException

Compile the entries in this dictionary to the specified object output.

Specified by:

compileTo in interface Compilable

Overrides:

compileTo in class AbstractDictionary<C>

Parameters:

out - Object output to which to write the dictionary.

Throws:

IOException - If there is an underlying I/O error during the write.