de.folt.fuzzy
Class FuzzyNode<K,T>

java.lang.Object
  java.util.Observable
      de.folt.fuzzy.FuzzyDataStructureElement<K,T>
          de.folt.fuzzy.FuzzyNode<K,T>

All Implemented Interfaces:

java.io.Serializable

Direct Known Subclasses:

StringFuzzyNode

public class FuzzyNode<K,T>
extends FuzzyDataStructureElement<K,T>
implements java.io.Serializable

This class implements a KD-TREE.
A fuzzy node consists of a n-dimensional fuzzy key FuzzyNodeKey where each element of the n-dim vector is a number. This number is normally generated based on a tri-gram index for strings, but essentially can be computed in whatever way is convenient or necessary. Each node has a left and right son (which can be null if there is none). The insert algorithms ensures that the left son is always lower than the right son. It has also a vector of values associated with it which contain the real data of the node (ids, objects or whatever). The values are typed. The normal usage of the class is that it is sub classed where <T> gets a specific instantiation. For an example see of this see MonoLingualFuzzyNode

Basic fuzzy search mechanism works as follows:

 int percentDiff = 100 - similarity; // the difference percentage value
 Vector<FuzzyNodeSearchResult<K, T>> matches = new Vector<FuzzyNodeSearchResult<K, T>>();
 Stack<FuzzyNode<K, T>> stack = new Stack<FuzzyNode<K, T>>(); // the stack for the search
 // use the minimum of the key sum now
 int minkeysum = this.getFuzzyNodeKey().getKeysum();
 // difference allowed between search node and node inspected
 float dist = 0;
 if (percentDiff > 0)
 {
     dist = (int) ((minkeysum * percentDiff) / 100) + 2;
 }
 
 stack.push(this);
 while (stack.size() > 0)
 {
     FuzzyNode<K, T> currentFuzzyNode = stack.pop(); // node to inspect
     int difference = currentFuzzyNode.computeKeyDistance(fuzzyCompareKey);
     boolean compval = (dist >= difference);
     if (compval)
     {
         FuzzyNodeSearchResult<K, T> result = new FuzzyNodeSearchResult<K, T>(percentdiffreal, similarity, dist, difference, currentFuzzyNode, NODESSEARCHED, NODESMATCHED, NODESPUSHED);
         matches.add(result);
     }
 
     int currentNodeLevelSum = currentFuzzyNode.getFuzzyNodeKey().computeKeySumTillLevel(currentFuzzyNode.LEVEL);
     int compareNodeLevelSum = fuzzyCompareKey.getFuzzyNodeKey().computeKeySumTillLevel(currentFuzzyNode.LEVEL);
 
     if (currentNodeLevelSum >= (compareNodeLevelSum - dist))
     {
         FuzzyNode<K, T> entry = currentFuzzyNode.getLeftSon() != null ? currentFuzzyNode.getLeftSon() : null;
         if (entry != null)
         {
             stack.push(entry);
         }
     }
 
     if (currentNodeLevelSum <= (compareNodeLevelSum + dist))
     {
         FuzzyNode<K, T> entry = currentFuzzyNode.getRightSon() != null ? currentFuzzyNode.getRightSon() : null;
         if (entry != null)
         {
             stack.push(entry);
             fuzzyCompareKey.NODESPUSHED = fuzzyCompareKey.NODESPUSHED + 1;
         }
     }
 }
 

Pattern used: Factory

Author:

klemens

See Also:

Serialized Form

Nested Class Summary

static class

FuzzyNode.FUZZYNODESTATUS

Constructor Summary

FuzzyNode()
This is the default constructor, basically does nothing.

Method Summary

int	computeKeyDistance(FuzzyNode<K,T> fuzzyNode) computeKeyDistance computes the distance between two fuzzy nodes based on its keys For the implementation see FuzzyNodeKey
int	countNodes() countNodes count all the values below the actual nodes (the actual node is not included!)
int	countSons() countSons count the number of sons
int	countValues() countValues return the number of values of a node
java.lang.String	format() format formats a FuzzyNode and returns a formatted string of the fuzzy node this + ":" + this.nodeID + "(" + this.maxID + "):" + ":" + this.status + " LE:" + this.LEVEL + " :LS(" + ils + " " + this.leftSon + "):RS(" + irs + " " + this.rightSon + "):" + this.fuzzyNodeKey.format()
java.lang.String	formatTree() formatTree formats a FuzzyNode and its children and returns a formatted string of the fuzzy nodes
java.lang.String	formatTree(boolean bShortFormat) formatTree formats a FuzzyNode and its children and returns a formatted string of the fuzzy nodes
int	getDepth() getDepth get the depth of the KD-TREE fuzzy node
FuzzyNodeKey	getFuzzyNodeKey() Get the FuzzyNodeKey associated with the FuzzyNode
FuzzyNode<K,T>	getLeftSon() Get the left son of the FuzzyNode
long	getMaxID() Get the maximum number of FuzzyNodes associated with this FuzzyNode
static int	getNGram() Get the NGrams associated with the FuzzyNode (for FuzzyNodes based on Strings!)
long	getNodeID() Get the unique identifier of the FuzzyNode
int	getNODESMATCHED()
int	getNODESPUSHED()
int	getNODESSEARCHED()
FuzzyNode<K,T>	getRightSon() Set the right son of the FuzzyNode
FuzzyNode.FUZZYNODESTATUS	getStatus() Get the status of the node
java.util.Vector<T>	getValues() Get the values associated with the FuzzyNode.
int	iBalance() iBalance determine the height depth) difference in the nodes sons
boolean	insertFuzzyNode(FuzzyNode<K,T> fuzzyNodeToAdd) insertFuzzyNode inserts a new FuzzyNode in the current FuzzyNode - which is actually a tree
boolean	insertFuzzyNode(FuzzyNode<K,T> fuzzyNodeToAdd, boolean bInsertMode) insertFuzzyNode insert a Fuzzy Node at a specific position in the tree applying a KDTREE insert algorithm.
boolean	isAVLTree() isAVLTree check if AVL tree
boolean	isBInsertMode() Get the insermode of the FuzzyNode
void	remove(java.lang.Object value) remove remove for a fuzzy node based on the value of a node and removes this value from the value list.
boolean	removeValue(FuzzyNode<K,T> fuzzyCompareKey) removeValue removes a value from the value list of the values of the node based on a key.
boolean	removeValue(java.lang.Object value) removeValue removes a value from the value list of the values of the node
boolean	removeValue(java.util.Vector<java.lang.Object> values) removeValue removes a vector of values from the value list of the values of the node
java.util.Vector<FuzzyNodeSearchResult<K,T>>	search(FuzzyNode<K,T> fuzzyCompareKey, int similarity) search searches FuzzyNode and its sons with a given similarity and returns a Vector of matching keys.
java.util.Vector<FuzzyNode<K,T>>	search(java.lang.Object value) search search for a fuzzy node based on the value of a node
void	setBInsertmode(boolean insertmode) Set the insert mode of the FuzzyNode.
void	setFuzzyNodeKey(FuzzyNodeKey fuzzyNodeKey) Set the FuzzyNodeKey associated with the FuzzyNode
void	setLeftSon(FuzzyNode<K,T> leftSon) Set the left son of the FuzzyNode
void	setMaxID(long maxID) Set the maximum number of nodes for a given FuzzyNode.
void	setNodeID(long nodeID) Set the uneque identifier of the FuzzyNode
void	setRightSon(FuzzyNode<K,T> rightSon) Set the left son of the FuzzyNode
void	setStatus(FuzzyNode.FUZZYNODESTATUS status) Set the status of the node
void	setValues(java.util.Vector<T> values) Set the values associated with the FuzzyNode.
java.lang.String	shortFormat() shortformat formats a FuzzyNode and returns a formatted string of the fuzzy node in a more compact way than format()
boolean	updateFuzzyNode(FuzzyNode<K,T> fuzzyNodeToAdd, boolean bInsertMode) updateFuzzyNode updates an existing fuzzy node with the value of the fuzzyNodeToAdd.

Methods inherited from class java.util.Observable

addObserver, countObservers, deleteObserver, deleteObservers, hasChanged, notifyObservers, notifyObservers

Methods inherited from class java.lang.Object

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

Constructor Detail

FuzzyNode

public FuzzyNode()

This is the default constructor, basically does nothing. Use the set functions for adding a FuuzyNodeKey and the left and right son.

Method Detail

getNGram

public static int getNGram()

Get the NGrams associated with the FuzzyNode (for FuzzyNodes based on Strings!)

Returns:

the nGram

computeKeyDistance

public int computeKeyDistance(FuzzyNode<K,T> fuzzyNode)

computeKeyDistance computes the distance between two fuzzy nodes based on its keys
For the implementation see FuzzyNodeKey

Parameters:

fuzzyNode - the fuzzy node to compare against the actual fuzzy node

Returns:

the distance

countNodes

public int countNodes()

countNodes count all the values below the actual nodes (the actual node is not included!)

Returns:

the number of all nodes left and right (0, 1 or 2)

countSons

public int countSons()

countSons count the number of sons

Returns:

the number of direct sons (0, 1 or 2)

countValues

public int countValues()

countValues return the number of values of a node

Returns:

the number of values in a node

format

public java.lang.String format()

format formats a FuzzyNode and returns a formatted string of the fuzzy node

 this + ":" + this.nodeID + "(" + this.maxID + "):" + ":" + this.status + " LE:" + this.LEVEL + " :LS(" + ils + " " + this.leftSon + "):RS(" + irs + " " + this.rightSon + "):"
         + this.fuzzyNodeKey.format()
 

Returns:

formatted FuzzyNode

formatTree

public java.lang.String formatTree()

formatTree formats a FuzzyNode and its children and returns a formatted string of the fuzzy nodes

Returns:

formatted FuzzyNode and its children

formatTree

public java.lang.String formatTree(boolean bShortFormat)

formatTree formats a FuzzyNode and its children and returns a formatted string of the fuzzy nodes

Parameters:

bShortFormat - true = use a short format display for node / false = long format

Returns:

formatted FuzzyNode and its children

getDepth

public int getDepth()

getDepth get the depth of the KD-TREE fuzzy node

Returns:

the depth of the node

getFuzzyNodeKey

public FuzzyNodeKey getFuzzyNodeKey()

Get the FuzzyNodeKey associated with the FuzzyNode

Returns:

the fuzzyNodeKey

getLeftSon

public FuzzyNode<K,T> getLeftSon()

Get the left son of the FuzzyNode

Returns:

the leftSon

getMaxID

public long getMaxID()

Get the maximum number of FuzzyNodes associated with this FuzzyNode

Returns:

the maxID

getNodeID

public long getNodeID()

Get the unique identifier of the FuzzyNode

Returns:

the nodeID

getNODESMATCHED

public int getNODESMATCHED()

Returns:

the nODESMATCHED number of matching nodes for the search

getNODESPUSHED

public int getNODESPUSHED()

Returns:

the nODESPUSHED number of nodes pushed for the search

getNODESSEARCHED

public int getNODESSEARCHED()

Returns:

the nODESSEARCHED number of search nodes for the search

getRightSon

public FuzzyNode<K,T> getRightSon()

Set the right son of the FuzzyNode

Returns:

the rightSon

getStatus

public FuzzyNode.FUZZYNODESTATUS getStatus()

Get the status of the node

Returns:

the status

getValues

public java.util.Vector<T> getValues()

Get the values associated with the FuzzyNode. The value basically is a vector. Values with produce the same FuzzyNodeKey are added to the vector.

Returns:

the values

iBalance

public int iBalance()

iBalance determine the height depth) difference in the nodes sons

Returns:

the difference between heigth left and right branch

insertFuzzyNode

public boolean insertFuzzyNode(FuzzyNode<K,T> fuzzyNodeToAdd)

insertFuzzyNode inserts a new FuzzyNode in the current FuzzyNode - which is actually a tree

Parameters:

fuzzyNodeToAdd - the fuzzy node to add

Returns:

true if successfully inserted

insertFuzzyNode

public boolean insertFuzzyNode(FuzzyNode<K,T> fuzzyNodeToAdd,
                               boolean bInsertMode)

insertFuzzyNode insert a Fuzzy Node at a specific position in the tree applying a KDTREE insert algorithm.

Parameters:

fuzzyNodeToAdd - the node to add to the fuzzy node

bInsertMode - if true the entry is added even if the node exists (values added), if false the found node has a value and only one value per node is allowed

Returns:

true if successfully inserted

isAVLTree

public boolean isAVLTree()

isAVLTree check if AVL tree

Returns:

true if yes otherwise false

isBInsertMode

public boolean isBInsertMode()

Get the insermode of the FuzzyNode

Returns:

the bInsertmode

remove

public void remove(java.lang.Object value)

remove remove for a fuzzy node based on the value of a node and removes this value from the value list. It searches thru all nodes to find the (Objec) value

Parameters:

value -

removeValue

public boolean removeValue(FuzzyNode<K,T> fuzzyCompareKey)

removeValue removes a value from the value list of the values of the node based on a key. The values of the key are the objects to remove from the list

Parameters:

fuzzyCompareKey - the key containing the value to remove

Returns:

true when successfully removed, otherwise false

removeValue

public boolean removeValue(java.lang.Object value)

removeValue removes a value from the value list of the values of the node

Parameters:

value - the object to remove

Returns:

true when successfully removed, otherwise false

removeValue

public boolean removeValue(java.util.Vector<java.lang.Object> values)

removeValue removes a vector of values from the value list of the values of the node

Parameters:

values - the vector of object values to remove

Returns:

true when successfully removed, otherwise false

search

public java.util.Vector<FuzzyNodeSearchResult<K,T>> search(FuzzyNode<K,T> fuzzyCompareKey,
                                                           int similarity)

search searches FuzzyNode and its sons with a given similarity and returns a Vector of matching keys.

Parameters:

fuzzyCompareKey - the node to search for in the current node and its sons

similarity - the similarity in % (100% = perfect match)

Returns:

a vector of FuzzyNodeSearchResult

search

public java.util.Vector<FuzzyNode<K,T>> search(java.lang.Object value)

search search for a fuzzy node based on the value of a node

Parameters:

value -

Returns:

return all the matching FuzzyNodes in a vector

setBInsertmode

public void setBInsertmode(boolean insertmode)

Set the insert mode of the FuzzyNode. "true" will add a value to the existing values list, "false" will ignore the (new) value if one exists.

Parameters:

insertmode - the bInsertmode to set

setFuzzyNodeKey

public void setFuzzyNodeKey(FuzzyNodeKey fuzzyNodeKey)

Set the FuzzyNodeKey associated with the FuzzyNode

Parameters:

fuzzyNodeKey - the fuzzyNodeKey to set

setLeftSon

public void setLeftSon(FuzzyNode<K,T> leftSon)

Set the left son of the FuzzyNode

Parameters:

leftSon - the leftSon to set

setMaxID

public void setMaxID(long maxID)

Set the maximum number of nodes for a given FuzzyNode.

Parameters:

maxID - the maxID to set

setNodeID

public void setNodeID(long nodeID)

Set the uneque identifier of the FuzzyNode

Parameters:

nodeID - the nodeID to set

setRightSon

public void setRightSon(FuzzyNode<K,T> rightSon)

Set the left son of the FuzzyNode

Parameters:

rightSon - the rightSon to set

setStatus

public void setStatus(FuzzyNode.FUZZYNODESTATUS status)

Set the status of the node

Parameters:

status - the status to set

setValues

public void setValues(java.util.Vector<T> values)

Set the values associated with the FuzzyNode. Oerwrites the current values.

Parameters:

values - the values to set

shortFormat

public java.lang.String shortFormat()

shortformat formats a FuzzyNode and returns a formatted string of the fuzzy node in a more compact way than format()

Returns:

formatted FuzzyNode

updateFuzzyNode

public boolean updateFuzzyNode(FuzzyNode<K,T> fuzzyNodeToAdd,
                               boolean bInsertMode)

updateFuzzyNode updates an existing fuzzy node with the value of the fuzzyNodeToAdd.

Parameters:

fuzzyNodeToAdd - the fuzzy node from which the value should be added

bInsertMode - if true the entry is added even if the node exists (values added), if false the found node has a value and only one value per node is allowed

Returns:

true if added otherwise false