Package org.apache.lucene.analysis.compound.hyphenation

Class TernaryTree

  • All Implemented Interfaces:
    java.lang.Cloneable
    Direct Known Subclasses:
    HyphenationTree
    public class TernaryTree
extends java.lang.Object
implements java.lang.Cloneable

    Ternary Search Tree.

    A ternary search tree is a hybrid between a binary tree and a digital search tree (trie). Keys are limited to strings. A data value of type char is stored in each leaf node. It can be used as an index (or pointer) to the data. Branches that only contain one key are compressed to one node by storing a pointer to the trailer substring of the key. This class is intended to serve as base class or helper class to implement Dictionary collections or the like. Ternary trees have some nice properties as the following: the tree can be traversed in sorted order, partial matches (wildcard) can be implemented, retrieval of all keys within a given distance from the target, etc. The storage requirements are higher than a binary tree but a lot less than a trie. Performance is comparable with a hash table, sometimes it outperforms a hash function (most of the time can determine a miss faster than a hash).

    The main purpose of this java port is to serve as a base for implementing TeX's hyphenation algorithm (see The TeXBook, appendix H). Each language requires from 5000 to 15000 hyphenation patterns which will be keys in this tree. The strings patterns are usually small (from 2 to 5 characters), but each char in the tree is stored in a node. Thus memory usage is the main concern. We will sacrifice 'elegance' to keep memory requirements to the minimum. Using java's char type as pointer (yes, I know pointer it is a forbidden word in java) we can keep the size of the node to be just 8 bytes (3 pointers and the data char). This gives room for about 65000 nodes. In my tests the english patterns took 7694 nodes and the german patterns 10055 nodes, so I think we are safe.

    All said, this is a map with strings as keys and char as value. Pretty limited!. It can be extended to a general map by using the string representation of an object and using the char value as an index to an array that contains the object values.

    This class has been taken from the Apache FOP project (http://xmlgraphics.apache.org/fop/). They have been slightly modified.

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      class  TernaryTree.Iterator  

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void balance()
      Balance the tree for best search performance
      TernaryTree clone()  
      int find​(char[] key, int start)  
      int find​(java.lang.String key)  
      void insert​(char[] key, int start, char val)  
      void insert​(java.lang.String key, char val)
      Branches are initially compressed, needing one node per key plus the size of the string key.
      java.util.Enumeration<java.lang.String> keys()  
      boolean knows​(java.lang.String key)  
      void printStats​(java.io.PrintStream out)  
      int size()  
      static int strcmp​(char[] a, int startA, char[] b, int startB)
      Compares 2 null terminated char arrays
      static int strcmp​(java.lang.String str, char[] a, int start)
      Compares a string with null terminated char array
      static void strcpy​(char[] dst, int di, char[] src, int si)  
      static int strlen​(char[] a)  
      static int strlen​(char[] a, int start)  
      void trimToSize()
      Each node stores a character (splitchar) which is part of some key(s).

      • Methods inherited from class java.lang.Object

        equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Method Detail

      • insert

        public void insert​(java.lang.String key,
                   char val)
        Branches are initially compressed, needing one node per key plus the size of the string key. They are decompressed as needed when another key with same prefix is inserted. This saves a lot of space, specially for long keys.

      • insert

        public void insert​(char[] key,
                   int start,
                   char val)

      • strcmp

        public static int strcmp​(char[] a,
                         int startA,
                         char[] b,
                         int startB)
        Compares 2 null terminated char arrays

      • strcmp

        public static int strcmp​(java.lang.String str,
                         char[] a,
                         int start)
        Compares a string with null terminated char array

      • strcpy

        public static void strcpy​(char[] dst,
                          int di,
                          char[] src,
                          int si)

      • strlen

        public static int strlen​(char[] a,
                         int start)

      • strlen

        public static int strlen​(char[] a)

      • find

        public int find​(java.lang.String key)

      • find

        public int find​(char[] key,
                int start)

      • knows

        public boolean knows​(java.lang.String key)

      • size

        public int size()

      • balance

        public void balance()
        Balance the tree for best search performance

      • trimToSize

        public void trimToSize()
        Each node stores a character (splitchar) which is part of some key(s). In a compressed branch (one that only contain a single string key) the trailer of the key which is not already in nodes is stored externally in the kv array. As items are inserted, key substrings decrease. Some substrings may completely disappear when the whole branch is totally decompressed. The tree is traversed to find the key substrings actually used. In addition, duplicate substrings are removed using a map (implemented with a TernaryTree!).

      • keys

        public java.util.Enumeration<java.lang.String> keys()

      • printStats

        public void printStats​(java.io.PrintStream out)