com.aliasi.dict
Class TrieDictionary<C>

java.lang.Object
  extended by java.util.AbstractCollection<E>
      extended by java.util.AbstractSet<DictionaryEntry<C>>
          extended by com.aliasi.dict.AbstractDictionary<C>
              extended by 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.