Package fim

Class CloMaxTree

java.lang.Object
fim.CloMaxTree

public class CloMaxTree extends Object
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

    Fields
    Modifier and Type
    Field
    Description
    static final int
    target pattern subtype: closed frequent item patterns; to be combined with or SEQUENCE
    protected int
    the direction of the item order
    static final int
    target pattern subtype: simple frequent item patterns
    protected util.IdMap
    the underlying item base
    protected int
    the associated item (for a prefix tree chain)
    protected int[]
    the item buffer for collecting/reporting the patterns
    static 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 with SEQUENCE
    protected PatternReceiver
    the pattern receiver for collecting the result patterns
    protected fim.CloMaxNode
    the root node of the prefix tree
    protected 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 or MAXIMAL
    protected int
    the target type of the filtering; SEQUENCE as the main target pattern type and either FREQUENT, CLOSED or MAXIMAL as the target pattern subtype
    static 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

    Constructors
    Constructor
    Description
    CloMaxTree(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 Type
    Method
    Description
    final 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 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
    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).
    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.
    Report closed or maximal item patterns (type is determined by the parameters passed to the constructor).
    report(int s_base)
    Report closed or maximal item patterns (type is determined by the parameters passed to the constructor).
    report(int s_base, int zmin, int zmax)
    Report closed or maximal item patterns (type is determined by the parameters passed to the constructor).
    Report closed or maximal item patterns (type is determined by the parameters passed to the constructor).
    report(PatternReceiver patrec, int s_base)
    Report closed or maximal item patterns (type is determined by the parameters passed to the constructor).
    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 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(Pattern pat, boolean prune)
    Update the prefix tree with a new item pattern.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • SUBTYPEMASK

      public static final int SUBTYPEMASK
      target pattern subtype mask; to extract the target pattern subtype, that is, CLOSED or MAXIMAL
      See Also:
    • TYPEMASK

      public static final int TYPEMASK
      target pattern type mask; to extract the main target pattern type, that is, SEQUENCE
      See Also:
    • ITEMSET

      public static final int ITEMSET
      target pattern type: item sets (item order is ignored)
      See Also:
    • SEQUENCE

      public static final int SEQUENCE
      target pattern type: paths represent (general) sequences (with and without repetition)
      See Also:
    • FREQUENT

      public static final int FREQUENT
      target pattern subtype: simple frequent item patterns
      See Also:
    • CLOSED

      public static final int CLOSED
      target pattern subtype: closed frequent item patterns; to be combined with or SEQUENCE
      See Also:
    • MAXIMAL

      public static final int MAXIMAL
      target pattern subtype: maximal frequent item patterns; to be combined with SEQUENCE
      See Also:
    • ibase

      protected util.IdMap ibase
      the underlying item base
    • target

      protected int target
      the target type of the filtering; SEQUENCE as the main target pattern type and either FREQUENT, CLOSED or MAXIMAL as the target pattern subtype
    • dir

      protected int dir
      the direction of the item order
    • item

      protected int item
      the associated item (for a prefix tree chain)
    • root

      protected fim.CloMaxNode root
      the root node of the prefix tree
    • last

      protected int[] last
      the (last) positions of the items in an item pattern (-1 if an item does not occur)
    • items

      protected int[] items
      the item buffer for collecting/reporting the patterns
    • zmin

      protected int zmin
      the minimum length of a pattern (number of items)
    • zmax

      protected int zmax
      the maximum length of a pattern (number of items)
    • s_base

      protected int s_base
      the base support (support of empty item pattern/database size)
    • patrec

      protected PatternReceiver 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 base
      target - the target pattern type of the prefix tree (main target pattern type SEQUENCE and target pattern subtype CLOSED or MAXIMAL)
      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 base
      target - the target pattern type of the prefix tree (main target pattern type SEQUENCE and target pattern subtype CLOSED or MAXIMAL)
      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 add
      cnt - the number of items in the pattern to add
      supp - 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 add
      offset - the offset to the first item to consider
      cnt - the number of items in the pattern to add (counted from 0, not from offset)
      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 support
      cnt - 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 support
      offset - the offset to the first item to consider
      cnt - the number of items in the pattern (counted from 0, not from offset)
      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 check
      cnt - the number of items in the pattern
      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)
    • 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 check
      offset - the offset to the first item to consider
      cnt - the number of items in the pattern (counted from 0, not from offset)
      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 merge
      src - 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 merge
      src - 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

      public final CloMaxTree project(int item, CloMaxTree dst)
      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 to
      dst - the destination prefix tree in which to store the projection
      Returns:
      the given destination prefix tree, or a new prefix tree if dst is null
      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 prune
      items - the item pattern to prune with
      offset - the offset to the first item to consider
      cnt - the number of items in the pattern
      supp - 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 prune
      items - the item pattern to prune with
      offset - the offset to the first item to consider
      cnt - 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 with
      cnt - the number of items in the pattern
      supp - 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 with
      offset - the offset to the first item to consider
      cnt - the number of items in the pattern (counted from 0, not from offset)
      supp - the support of the pattern to prune with
      Since:
      2017.06.22 (Christian Borgelt)
    • update

      public final boolean update(Pattern pat)
      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 and false otherwise
      Since:
      2017.06.22 (Christian Borgelt)
    • update

      public final boolean update(Pattern pat, boolean prune)
      Update the prefix tree with a new item pattern.
      Parameters:
      pat - the item pattern to update with
      prune - whether to prune sub- or super-patterns (depending on the target type) from the prefix tree
      Returns:
      true if the prefix tree was modified and false 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 with
      cnt - the number of items in the pattern (counted from 0, not from offset)
      supp - the support of the pattern to update with
      Returns:
      true if the prefix tree was modified and false 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 with
      cnt - the number of items in the pattern (counted from 0, not from offset)
      supp - the support of the pattern to update with
      prune - whether to prune sub- or super-patterns (depending on the target type) from the prefix tree
      Returns:
      true if the prefix tree was modified and false 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 with
      offset - the offset to the first item to consider
      cnt - the number of items in the pattern (counted from 0, not from offset)
      supp - the support of the pattern to update with
      Returns:
      true if the prefix tree was modified and false 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 with
      offset - the offset to the first item to consider
      cnt - the number of items in the pattern (counted from 0, not from offset)
      supp - the support of the pattern to update with
      prune - whether to prune sub- or super-patterns (depending on the target type) from the prefix tree
      Returns:
      true if the prefix tree was modified and false 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 tree
      size - 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 tree
      size - the current size of the item pattern (depth in tree)
      Since:
      2017.06.22 (Christian Borgelt)
    • report

      public final PatternSet 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

      public final PatternSet report(int s_base)
      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

      public 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).
      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
      zmin - 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

      public final PatternReceiver report(PatternReceiver patrec)
      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 is null
      Since:
      2017.06.22 (Christian Borgelt)
    • report

      public final PatternReceiver report(PatternReceiver patrec, int s_base)
      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
      s_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 is null
      Since:
      2017.06.22 (Christian Borgelt)
    • report

      public 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).
      Parameters:
      patrec - the receiver for collecting the item patterns
      s_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
      zmin - 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 is null
      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)