Generated on for Gecode by doxygen 1.17.0

Example: constrained frequent subsequences of unknown length More...

Public Types

enum  { SEARCH_BAB , SEARCH_DFS }

Public Member Functions

 CommonPattern (const CommonPatternOptions &opt)
IntVar cost (void) const override
 CommonPattern (CommonPattern &s)
Space * copy (void) override
void print (std::ostream &os) const override
 Print a solution to os.
Public Member Functions inherited from Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< IntMaximizeSpace > >
 ScriptBase (const Options &opt)
 Constructor.
 ScriptBase (ScriptBase &e)
 Constructor used for cloning.
virtual void compare (const Space &home, std::ostream &os) const
 Compare with s.
Public Member Functions inherited from Gecode::Driver::IgnoreStepOption< BaseSpace >
 IgnoreStepOption (const Options &)
 Constructor.
 IgnoreStepOption (BaseSpace &e)
 Constructor used for cloning.

Protected Attributes

OpenIntVarList pattern
IntVar frequency
PatternMining::Database database
bool letters

(Note that these are not member symbols.)

int main (int argc, char *argv[])
 Main-function.

Additional Inherited Members

Static Public Member Functions inherited from Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< IntMaximizeSpace > >
static std::ostream & select_ostream (const char *sn, std::ofstream &ofs)
 Choose output stream according to sn.
static void run (const Options &opt, Script *s=nullptr)

Detailed Description

Example: constrained frequent subsequences of unknown length

A pattern must occur in at least -support percent of the input sequences. Matching preserves order and may skip items; repeated items match distinct positions. Each supporting record counts once, including duplicate records. By default the inputs ABCBC, BABC, ABDC must all support the pattern, which must start with A and end with C. AC and ABC are feasible; ABC is longest.

Ordinary length and regular constraints restrict the pattern, not the matching positions in the input records. By default, DFS enumerates every qualifying pattern; -search bab finds a longest one.

An OpenIntVarList constructs pattern positions as needed, without an end marker or unused suffix variables. Pattern languages therefore describe just the pattern, without padding transitions. The private frequency constraint maintains supporting suffixes after the assigned prefix and removes items with insufficient support. The method follows Amina Kemmar, Samir Loudni, Yahia Lebbah, Patrice Boizumault, and Thierry Charnois, "PREFIX-PROJECTION Global Constraint for Sequential Pattern Mining", CP 2015, pp. 226-243, https://doi.org/10.1007/978-3-319-23219-5_17. The supporting suffix lengths also bound how many items can follow the assigned prefix. Projection can be combined with the pattern's length, item, and language restrictions. OpenRoute is the simpler introduction to open lists.

The paper's Table 1 can be mined with: -sequences ABCBC,BABC,AB,BCD -support 50 -language none. -min-length and -required constrain length and item membership. -language also accepts motif (A, any items, C), re10, re14, re2 (expressions from the paper). Their letters mean item IDs A=1 through Z=26; integer data must use the corresponding mapping for these named expressions.

-file reads one sequence per line in -format letters, integers, or spmf. Integer IDs are positive and preserved in output. SPMF records must have singleton itemsets: "1 -1 2 -1 3 -1 -2" is the sequence ABC. Multi-item itemsets are rejected because they define a different mining problem. No gap or time restrictions are supported.

Definition at line 189 of file common-pattern.cpp.

Member Enumeration Documentation

◆ anonymous enum

anonymous enum
Enumerator
SEARCH_BAB 
SEARCH_DFS 

Definition at line 196 of file common-pattern.cpp.

Constructor & Destructor Documentation

◆ CommonPattern() [1/2]

CommonPattern::CommonPattern ( const CommonPatternOptions & opt)
inline

Definition at line 198 of file common-pattern.cpp.

◆ CommonPattern() [2/2]

CommonPattern::CommonPattern ( CommonPattern & s)
inline

Definition at line 215 of file common-pattern.cpp.

Member Function Documentation

◆ cost()

IntVar CommonPattern::cost ( void ) const
inlineoverride

Definition at line 213 of file common-pattern.cpp.

◆ copy()

Space * CommonPattern::copy ( void )
inlineoverride

Definition at line 221 of file common-pattern.cpp.

◆ print()

void CommonPattern::print ( std::ostream & os) const
inlineoverridevirtual

Print a solution to os.

Reimplemented from Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< IntMaximizeSpace > >.

Definition at line 223 of file common-pattern.cpp.

◆ main()

int main ( int argc,
char * argv[] )
related

Main-function.

Definition at line 248 of file common-pattern.cpp.

Member Data Documentation

◆ pattern

OpenIntVarList CommonPattern::pattern
protected

Definition at line 191 of file common-pattern.cpp.

◆ frequency

IntVar CommonPattern::frequency
protected

Definition at line 192 of file common-pattern.cpp.

◆ database

PatternMining::Database CommonPattern::database
protected

Definition at line 193 of file common-pattern.cpp.

◆ letters

bool CommonPattern::letters
protected

Definition at line 194 of file common-pattern.cpp.


The documentation for this class was generated from the following file: