Package fim
Class CloMaxTree
java.lang.Object
fim.CloMaxTree
Class for a prefix tree to filter for closed and maximal item
sequences (also works for item sets, but is suboptimal for these).
- Since:
- 2016.10.24
-
Field Summary
FieldsModifier and TypeFieldDescriptionstatic final int
target pattern subtype: closed frequent item patterns; to be combined with orSEQUENCE
protected int
the direction of the item orderstatic final int
target pattern subtype: simple frequent item patternsprotected util.IdMap
the underlying item baseprotected int
the associated item (for a prefix tree chain)protected int[]
the item buffer for collecting/reporting the patternsstatic final int
target pattern type: item sets (item order is ignored)protected int[]
the (last) positions of the items in an item pattern (-1
if an item does not occur)static final int
target pattern subtype: maximal frequent item patterns; to be combined withSEQUENCE
protected PatternReceiver
the pattern receiver for collecting the result patternsprotected fim.CloMaxNode
the root node of the prefix treeprotected int
the base support (support of empty item pattern/database size)static final int
target pattern type: paths represent (general) sequences (with and without repetition)static final int
target pattern subtype mask; to extract the target pattern subtype, that is,CLOSED
orMAXIMAL
protected int
the target type of the filtering;SEQUENCE
as the main target pattern type and eitherFREQUENT
,CLOSED
orMAXIMAL
as the target pattern subtypestatic final int
target pattern type mask; to extract the main target pattern type, that is,SEQUENCE
protected int
the maximum length of a pattern (number of items)protected int
the minimum length of a pattern (number of items) -
Constructor Summary
ConstructorsConstructorDescriptionCloMaxTree
(util.IdMap ibase, int target) Create an empty prefix tree for closed/maximal filtering.CloMaxTree
(util.IdMap ibase, int target, int dir) Create an empty prefix tree for closed/maximal filtering. -
Method Summary
Modifier and TypeMethodDescriptionfinal void
add
(int[] items, int cnt, int supp) Add a new item pattern to this prefix tree.final void
add
(int[] items, int offset, int cnt, int supp) Add a new item pattern to a prefix tree.final void
clear()
Clear a prefix tree for closed/maximal filtering.final fim.CloMaxNode
clone
(fim.CloMaxNode src) Clone the subtree rooted at a given node (that is, clone the node itself and its descendants).protected final void
collectClo
(fim.CloMaxNode node, int size) Recursively collect closed item patterns from the tree.protected final void
collectMax
(fim.CloMaxNode node, int size) Recursively collect maximal item patterns from the tree.final int
Get the maximal support of any item pattern in the prefix tree.final int
getSupp()
Get the maximal support of any item pattern in the prefix tree.final int
getSupp
(int[] items, int cnt) Get the support of a given item pattern.final int
getSupp
(int[] items, int offset, int cnt) Get the support of a given item pattern.final boolean
hasSuper
(int[] items, int cnt, int supp) Check whether a super-pattern with at least a given support exists in this prefix tree.final boolean
hasSuper
(int[] items, int offset, int cnt, int supp) Check whether a super-pattern with at least a given support exists in this prefix tree.final void
mergeNeg
(fim.CloMaxNode dst, fim.CloMaxNode src) Merge a subtree rooted at a given node to the subtree rooted at this node (by cloning the nodes of the source tree).final void
mergePos
(fim.CloMaxNode dst, fim.CloMaxNode src) Merge a subtree rooted at a given node to the subtree rooted at this node (by cloning the nodes of the source tree).final CloMaxTree
project
(int item, CloMaxTree dst) Project a prefix tree to a given item.protected final void
project
(fim.CloMaxNode src) Project a prefix tree to a given item.final void
prune
(int[] items, int cnt, int supp) For a given item pattern, prune all sub- or super-patterns (depending on the target type of this tree) that are represented by paths of this prefix tree.final void
prune
(int[] items, int offset, int cnt, int supp) For a given item pattern, prune all sub- or super-patterns (depending on the target type of this tree) that are represented by paths of this prefix tree.protected final int
pruneClo
(fim.CloMaxNode root, int[] items, int offset, int cnt, int supp) For a given item pattern, prune all sub-patterns that are represented by paths of the prefix tree rooted at the given node and have at most the support of the given item pattern.protected final int
pruneMax
(fim.CloMaxNode root, int[] items, int offset, int cnt) For a given item pattern, prune all sub-patterns that are represented by paths of the prefix tree rooted at the given node.final PatternSet
report()
Report closed or maximal item patterns (type is determined by the parameters passed to the constructor).final PatternSet
report
(int s_base) Report closed or maximal item patterns (type is determined by the parameters passed to the constructor).final PatternSet
report
(int s_base, int zmin, int zmax) Report closed or maximal item patterns (type is determined by the parameters passed to the constructor).final PatternReceiver
report
(PatternReceiver patrec) Report closed or maximal item patterns (type is determined by the parameters passed to the constructor).final PatternReceiver
report
(PatternReceiver patrec, int s_base) Report closed or maximal item patterns (type is determined by the parameters passed to the constructor).final PatternReceiver
report
(PatternReceiver patrec, int s_base, int zmin, int zmax) Report closed or maximal item patterns (type is determined by the parameters passed to the constructor).final void
show()
Show a closed/maximal filter prefix tree (for debugging purposes).final void
show
(int indent) Show a closed/maximal filter prefix tree (for debugging purposes).final boolean
update
(int[] items, int cnt, int supp) Update the prefix tree with a new item pattern.final boolean
update
(int[] items, int cnt, int supp, boolean prune) Update the prefix tree with a new item pattern.final boolean
update
(int[] items, int offset, int cnt, int supp) Update the prefix tree with a new pattern.final boolean
update
(int[] items, int offset, int cnt, int supp, boolean prune) Update the prefix tree with a new pattern.final boolean
Update the prefix tree with a new item pattern.final boolean
Update the prefix tree with a new item pattern.
-
Field Details
-
SUBTYPEMASK
public static final int SUBTYPEMASKtarget pattern subtype mask; to extract the target pattern subtype, that is,CLOSED
orMAXIMAL
- See Also:
-
TYPEMASK
public static final int TYPEMASKtarget pattern type mask; to extract the main target pattern type, that is,SEQUENCE
- See Also:
-
ITEMSET
public static final int ITEMSETtarget pattern type: item sets (item order is ignored)- See Also:
-
SEQUENCE
public static final int SEQUENCEtarget pattern type: paths represent (general) sequences (with and without repetition)- See Also:
-
FREQUENT
public static final int FREQUENTtarget pattern subtype: simple frequent item patterns- See Also:
-
CLOSED
public static final int CLOSEDtarget pattern subtype: closed frequent item patterns; to be combined with orSEQUENCE
- See Also:
-
MAXIMAL
public static final int MAXIMALtarget pattern subtype: maximal frequent item patterns; to be combined withSEQUENCE
- See Also:
-
ibase
protected util.IdMap ibasethe underlying item base -
target
protected int targetthe target type of the filtering;SEQUENCE
as the main target pattern type and eitherFREQUENT
,CLOSED
orMAXIMAL
as the target pattern subtype -
dir
protected int dirthe direction of the item order -
item
protected int itemthe associated item (for a prefix tree chain) -
root
protected fim.CloMaxNode rootthe root node of the prefix tree -
last
protected int[] lastthe (last) positions of the items in an item pattern (-1
if an item does not occur) -
items
protected int[] itemsthe item buffer for collecting/reporting the patterns -
zmin
protected int zminthe minimum length of a pattern (number of items) -
zmax
protected int zmaxthe maximum length of a pattern (number of items) -
s_base
protected int s_basethe base support (support of empty item pattern/database size) -
patrec
the pattern receiver for collecting the result patterns
-
-
Constructor Details
-
CloMaxTree
public CloMaxTree(util.IdMap ibase, int target) Create an empty prefix tree for closed/maximal filtering.- Parameters:
ibase
- the underlying item basetarget
- the target pattern type of the prefix tree (main target pattern typeSEQUENCE
and target pattern subtypeCLOSED
orMAXIMAL
)- Since:
- 2017.06.22 (Christian Borgelt)
-
CloMaxTree
public CloMaxTree(util.IdMap ibase, int target, int dir) Create an empty prefix tree for closed/maximal filtering.- Parameters:
ibase
- the underlying item basetarget
- the target pattern type of the prefix tree (main target pattern typeSEQUENCE
and target pattern subtypeCLOSED
orMAXIMAL
)dir
- the direction of the item order- Since:
- 2017.06.22 (Christian Borgelt)
-
-
Method Details
-
clear
public final void clear()Clear a prefix tree for closed/maximal filtering.- Since:
- 2017.06.22 (Christian Borgelt)
-
add
public final void add(int[] items, int cnt, int supp) Add a new item pattern to this prefix tree.- Parameters:
items
- the item pattern to addcnt
- the number of items in the pattern to addsupp
- the support of the item pattern to add- Since:
- 2017.06.22 (Christian Borgelt)
-
add
public final void add(int[] items, int offset, int cnt, int supp) Add a new item pattern to a prefix tree.- Parameters:
items
- the item pattern to addoffset
- the offset to the first item to considercnt
- the number of items in the pattern to add (counted from 0, not fromoffset
)supp
- the support of the pattern to add- Since:
- 2017.06.22 (Christian Borgelt)
-
getMaxSupp
public final int getMaxSupp()Get the maximal support of any item pattern in the prefix tree.- Returns:
- the maximal support of any item pattern in the prefix tree
- Since:
- 2017.06.22 (Christian Borgelt)
-
getSupp
public final int getSupp()Get the maximal support of any item pattern in the prefix tree.- Returns:
- the maximal support of any item pattern in the prefix tree
- Since:
- 2017.06.22 (Christian Borgelt)
-
getSupp
public final int getSupp(int[] items, int cnt) Get the support of a given item pattern.- Parameters:
items
- the item pattern for which to get the supportcnt
- the number of items in the pattern- Returns:
- the support of the item pattern
- Since:
- 2017.06.22 (Christian Borgelt)
-
getSupp
public final int getSupp(int[] items, int offset, int cnt) Get the support of a given item pattern.- Parameters:
items
- the item pattern for which to get the supportoffset
- the offset to the first item to considercnt
- the number of items in the pattern (counted from 0, not fromoffset
)- Returns:
- the support of the item pattern
- Since:
- 2017.06.22 (Christian Borgelt)
-
hasSuper
public final boolean hasSuper(int[] items, int cnt, int supp) Check whether a super-pattern with at least a given support exists in this prefix tree.- Parameters:
items
- the item pattern to checkcnt
- the number of items in the patternsupp
- the support of the item pattern to check- Returns:
- whether a super-pattern with at least the given support exists
- Since:
- 2017.06.22 (Christian Borgelt)
-
hasSuper
public final boolean hasSuper(int[] items, int offset, int cnt, int supp) Check whether a super-pattern with at least a given support exists in this prefix tree.- Parameters:
items
- the item pattern to checkoffset
- the offset to the first item to considercnt
- the number of items in the pattern (counted from 0, not fromoffset
)supp
- the support of the item pattern to check- Returns:
- whether a super-pattern with at least the given support exists
- Since:
- 2017.06.22 (Christian Borgelt)
-
clone
public final fim.CloMaxNode clone(fim.CloMaxNode src) Clone the subtree rooted at a given node (that is, clone the node itself and its descendants).- Parameters:
src
- the root node of the source subtree- Returns:
- the root node of the created subtree clone
- Since:
- 2017.06.22 (Christian Borgelt)
-
mergePos
public final void mergePos(fim.CloMaxNode dst, fim.CloMaxNode src) Merge a subtree rooted at a given node to the subtree rooted at this node (by cloning the nodes of the source tree).This function is for positive/ascending item direction. For negative/descending item direction, use
mergeNeg()
.- Parameters:
dst
- the root node of the destination subtree to mergesrc
- the root node of the source subtree to merge- Since:
- 2017.06.22 (Christian Borgelt)
-
mergeNeg
public final void mergeNeg(fim.CloMaxNode dst, fim.CloMaxNode src) Merge a subtree rooted at a given node to the subtree rooted at this node (by cloning the nodes of the source tree).This function is for negative/descending item direction. For postive/ascending item direction, use
mergePos()
.- Parameters:
dst
- the root node of the destination subtree to mergesrc
- the root node of the subtree to merge to this subtree- Since:
- 2017.06.22 (Christian Borgelt)
-
project
protected final void project(fim.CloMaxNode src) Project a prefix tree to a given item.- Parameters:
src
- the node of the source tree from which to project- Since:
- 2017.06.22 (Christian Borgelt)
-
project
Project a prefix tree to a given item.The result is a prefix tree that represents all suffixes in the source tree that start with the given item. The support values associated with these suffixes are the maxima over all corresponding suffixes in the source prefix tree.
- Parameters:
item
- the item to project the prefix tree todst
- the destination prefix tree in which to store the projection- Returns:
- the given destination prefix tree, or a new prefix tree if
dst
isnull
- Since:
- 2017.06.22 (Christian Borgelt)
-
pruneClo
protected final int pruneClo(fim.CloMaxNode root, int[] items, int offset, int cnt, int supp) For a given item pattern, prune all sub-patterns that are represented by paths of the prefix tree rooted at the given node and have at most the support of the given item pattern.- Parameters:
root
- the root node of the subtree to pruneitems
- the item pattern to prune withoffset
- the offset to the first item to considercnt
- the number of items in the patternsupp
- the support of the item pattern to prune with- Returns:
- the maximum support of a child node (of
root
- Since:
- 2017.06.22 (Christian Borgelt)
-
pruneMax
protected final int pruneMax(fim.CloMaxNode root, int[] items, int offset, int cnt) For a given item pattern, prune all sub-patterns that are represented by paths of the prefix tree rooted at the given node.- Parameters:
root
- the root node of the subtree to pruneitems
- the item pattern to prune withoffset
- the offset to the first item to considercnt
- the number of items in the pattern- Returns:
- the maximum support of a child node (of
root
) - Since:
- 2017.06.22 (Christian Borgelt)
-
prune
public final void prune(int[] items, int cnt, int supp) For a given item pattern, prune all sub- or super-patterns (depending on the target type of this tree) that are represented by paths of this prefix tree.- Parameters:
items
- the item pattern to prune withcnt
- the number of items in the patternsupp
- the support of the item pattern to prune with- Since:
- 2017.06.22 (Christian Borgelt)
-
prune
public final void prune(int[] items, int offset, int cnt, int supp) For a given item pattern, prune all sub- or super-patterns (depending on the target type of this tree) that are represented by paths of this prefix tree.- Parameters:
items
- the item pattern to prune withoffset
- the offset to the first item to considercnt
- the number of items in the pattern (counted from 0, not fromoffset
)supp
- the support of the pattern to prune with- Since:
- 2017.06.22 (Christian Borgelt)
-
update
Update the prefix tree with a new item pattern.- Parameters:
pat
- the item pattern to update with- Returns:
true
if the prefix tree was modified andfalse
otherwise- Since:
- 2017.06.22 (Christian Borgelt)
-
update
Update the prefix tree with a new item pattern.- Parameters:
pat
- the item pattern to update withprune
- whether to prune sub- or super-patterns (depending on the target type) from the prefix tree- Returns:
true
if the prefix tree was modified andfalse
otherwise- Since:
- 2017.06.22 (Christian Borgelt)
-
update
public final boolean update(int[] items, int cnt, int supp) Update the prefix tree with a new item pattern.- Parameters:
items
- the item pattern to update withcnt
- the number of items in the pattern (counted from 0, not fromoffset
)supp
- the support of the pattern to update with- Returns:
true
if the prefix tree was modified andfalse
otherwise- Since:
- 2017.06.22 (Christian Borgelt)
-
update
public final boolean update(int[] items, int cnt, int supp, boolean prune) Update the prefix tree with a new item pattern.- Parameters:
items
- the item pattern to update withcnt
- the number of items in the pattern (counted from 0, not fromoffset
)supp
- the support of the pattern to update withprune
- whether to prune sub- or super-patterns (depending on the target type) from the prefix tree- Returns:
true
if the prefix tree was modified andfalse
otherwise- Since:
- 2017.06.22 (Christian Borgelt)
-
update
public final boolean update(int[] items, int offset, int cnt, int supp) Update the prefix tree with a new pattern.- Parameters:
items
- the item pattern to update withoffset
- the offset to the first item to considercnt
- the number of items in the pattern (counted from 0, not fromoffset
)supp
- the support of the pattern to update with- Returns:
true
if the prefix tree was modified andfalse
otherwise- Since:
- 2017.06.22 (Christian Borgelt)
-
update
public final boolean update(int[] items, int offset, int cnt, int supp, boolean prune) Update the prefix tree with a new pattern.- Parameters:
items
- the item pattern to update withoffset
- the offset to the first item to considercnt
- the number of items in the pattern (counted from 0, not fromoffset
)supp
- the support of the pattern to update withprune
- whether to prune sub- or super-patterns (depending on the target type) from the prefix tree- Returns:
true
if the prefix tree was modified andfalse
otherwise- Since:
- 2017.06.22 (Christian Borgelt)
-
collectClo
protected final void collectClo(fim.CloMaxNode node, int size) Recursively collect closed item patterns from the tree.- Parameters:
node
- the current node of the prefix treesize
- the current size of the item pattern (depth in tree)- Since:
- 2017.06.22 (Christian Borgelt)
-
collectMax
protected final void collectMax(fim.CloMaxNode node, int size) Recursively collect maximal item patterns from the tree.- Parameters:
node
- the current node of the prefix treesize
- the current size of the item pattern (depth in tree)- Since:
- 2017.06.22 (Christian Borgelt)
-
report
Report closed or maximal item patterns (type is determined by the parameters passed to the constructor).- Returns:
- the set of closed or maximal item patterns
- Since:
- 2017.06.22 (Christian Borgelt)
-
report
Report closed or maximal item patterns (type is determined by the parameters passed to the constructor).- Parameters:
s_base
- the base support (support of the empty item pattern); if-1
, the root node is used, if-2
, the item pattern support is used- Returns:
- the set of closed or maximal item patterns
- Since:
- 2017.06.22 (Christian Borgelt)
-
report
Report closed or maximal item patterns (type is determined by the parameters passed to the constructor).- Parameters:
s_base
- the base support (support of the empty item pattern); if-1
, the root node is used, if-2
, the item pattern support is usedzmin
- the minimum size of an item pattern (number of items)zmax
- the maximum size of an item pattern (number of items)- Returns:
- the set of closed or maximal item patterns
- Since:
- 2017.06.22 (Christian Borgelt)
-
report
Report closed or maximal item patterns (type is determined by the parameters passed to the constructor).- Parameters:
patrec
- the receiver for collecting the item patterns- Returns:
- the argument
patset
, or a new pattern set if this argument isnull
- Since:
- 2017.06.22 (Christian Borgelt)
-
report
Report closed or maximal item patterns (type is determined by the parameters passed to the constructor).- Parameters:
patrec
- the receiver for collecting the item patternss_base
- the base support (support of the empty item pattern); if-1
the root node support is used, if-2
, the item pattern support is used- Returns:
- the argument
patset
, or a new pattern set if this argument isnull
- Since:
- 2017.06.22 (Christian Borgelt)
-
report
Report closed or maximal item patterns (type is determined by the parameters passed to the constructor).- Parameters:
patrec
- the receiver for collecting the item patternss_base
- the base support (support of the empty item pattern); if-1
the root node support is used, if-2
, the item pattern support is usedzmin
- the minimum size of an item pattern (number of items)zmax
- the maximum size of an item pattern (number of items)- Returns:
- the argument
patset
, or a new pattern set if this argument isnull
- Since:
- 2017.06.22 (Christian Borgelt)
-
show
public final void show()Show a closed/maximal filter prefix tree (for debugging purposes).- Since:
- 2017.06.22 (Christian Borgelt)
-
show
public final void show(int indent) Show a closed/maximal filter prefix tree (for debugging purposes).- Parameters:
indent
- the indentation level- Since:
- 2017.06.22 (Christian Borgelt)
-