'OType for a lexicographic tree, implementating a n-ary tree over a binary tree. XA node : item, next node (next in transaction), alternative node (other branch), weight  Void node 1Get the data as a long bytestring, parses it and : and executes LCM to discover closed frequent itemsets. pThe transaction database as a big string. Transactions are separated by newlines, items are separated by spaces 6Minimum frequency threshold for the frequent itemsets )Output: list of closed frequent itemsets 1Get the data as a matrix of Items, parses it and : and executes LCM to discover closed frequent itemsets. ;The transaction database as matrix of items (List of List) 6Minimum frequency threshold for the frequent itemsets )Output: list of closed frequent itemsets FUse for benchmarking, parallel strategy = parBuffer by Simon Marlow. , This strategy does not have space leak. /mWarning: outputs are unusable as is, because items are renamed internally, and in this function the reverse b renaming is not performed. It is trivial to have it back by copying the code from runLCMstring./ pThe transaction database as a big string. Transactions are separated by newlines, items are separated by spaces 6Minimum frequency threshold for the frequent itemsets value for parBuffer depth for cutting parallelism )Output: list of closed frequent itemsets TUse for benchmarking, parallel strategy = parMap from Control.Parallel.Strategies. /mWarning: outputs are unusable as is, because items are renamed internally, and in this function the reverse b renaming is not performed. It is trivial to have it back by copying the code from runLCMstring./ pThe transaction database as a big string. Transactions are separated by newlines, items are separated by spaces 6Minimum frequency threshold for the frequent itemsets depth for cutting parallelism )Output: list of closed frequent itemsets `Takes a list of itemsets and a permutation of items, an apply this permutation to the itemsets. A permutation of items TInput list of itemsets. An itemset is a list of items, starting with its frequency. NPermuted list of itemsets. Frequency at the head of the itemset is untouched. [Loads input datase as string into a database of transactions in lexicographic tree format.  Also reorders/%renames the item by their frequency. Q The permutation between old item values and new item values is also returned. Data as a long bytestring Minimum support threshold TReturn value : (Database, maximum item value after reduction, permutation of items) fLoads input datase as a matrix of Items into a database of transactions in lexicographic tree format.  Also reorders/%renames the item by their frequency. Q The permutation between old item values and new item values is also returned. Data as a matrix of Items Minimum support threshold TReturn value : (Database, maximum item value after reduction, permutation of items) +Converts the contents of a data string to / a transaction database and computes maxItem. List of transactions ;Return value : transactions as lists of items, and maxItem @Converts one transaction from string format to item format [Item]. #Transaction as extracted from file Result : list of items )For a transaction database of type [[Item]], compute the frequency 7 of each item and return an array (item, frequency). 1Bounds for resulting array, must be (0, maxItem) Transaction database 8Result : Array associating each item with its frequency 2Sorts a list of (Item, frequency of this item) in " decreasing ordrer of frequency. XXX PERF : seems unefficient. +Each item is associated with its frequency =Same list as input, but sorted in decreasing frequency order 1From an array of (item, frequency of this item), + computes an associative array X where X[i] is  the ith most frequent item. PXXX PERF : performance issue with conversions to and from list inside function. -Array associating to each item its frequency HResult : new array where items are ranked by frequency, and the reverse IRewrites an input transaction database by removing infrequent items and ` using reordered items (i.e. each item is replaced by its rank in decreasing frequency order). Original transaction database AArray of items sorted by decreasing frequency order (item, rank) AArray associating each item with its frequency (item, frequency) Minimum frequency threshold (Result : rewritten transaction database ACompute for each item of the transaction database its frequency. 4Transaction database (in lexicographic tree format) %Maximal item in transaction database 7Result : array associating each item to its frequency. IEfficient traversal of the transaction database as a lexicographic tree. , Items frequencies are updated on the fly. Transaction database KArray associating each item with its frequency. UPDATED by this function ! LFor a transaction database, a closed frequent itemset, and a candidate item J for extension of this closed frequent itemset, recursively computes all ; the successor closed frequent itemsets by PPC-extension. FCurrent depth in the search tree (for parallel optimisation purposes) Transaction database. Input closed frequent itemset. 7Candidate to extend the closed frequent itemset above. 3CoreI item relative to the closed frequent itemset /Array associating each item with its frequency  Maximal item Minimum suppport threshold Result : list of closed frequent itemsets. Each result is a list of items, the head of the list being the frequency of the item.  FCurrent depth in the search tree (for parallel optimisation purposes) Transaction database. Input closed frequent itemset. 7Candidate to extend the closed frequent itemset above. 3CoreI item relative to the closed frequent itemset /Array associating each item with its frequency  Maximal item Minimum suppport threshold Value for parBuffer Depth for cutting parallelism Result : list of closed frequent itemsets. Each result is a list of items, the head of the list being the frequency of the item.  FCurrent depth in the search tree (for parallel optimisation purposes) Transaction database. Input closed frequent itemset. 7Candidate to extend the closed frequent itemset above. 3CoreI item relative to the closed frequent itemset /Array associating each item with its frequency  Maximal item Minimum suppport threshold Depth for cutting parallelism Result : list of closed frequent itemsets. Each result is a list of items, the head of the list being the frequency of the item. 9For a given itemset being extended by a given candidate, X compute the closure of this itemset and compute the candidates for further extension. Minimum support thresold *Frequency of item selected for extension ( candidate) *List of items in the transaction database -Array associating to each item its frequency *Result : (100% frequent items = closure, 6 candidates for further extension, unfrequent items) GModifies an array associating items with their frequency, in order to 2 give a frequency of 0 to a given list of items. ZNB : for performance reasons, this is REALLY a modification, made with unsafe operations. -Array associating an item with its frequency List of 100% frequent items List of unfrequent items 7Initial array, with frequencies of 100% frequent items " and unfrequent items set to 0. ECreates a new, reduced transaction database by eliminating all items  greater than  candidate! item, and all infrequent items. Original transaction database 0Candidate item, on which the projection is made 3Array associating each item with its frequency in  original transaction database. &Result : Reduced transaction database HSuppress all infrequent items from a transaction database expressed as < lexicographic tree, and returns a new lexicographic tree. Original transaction database 3Array associating each item with its frequency in 2 original transaction database. In this setting, F an infrequent item as a frequency of 0 (because of preprocessing by  ). [Result : (transaction database without infrequent items, weight to report in parent nodes) 1Returns the maximal item of a lexicographic tree !BInserts a transaction in list format into the lexicographic tree. / Automatically merges identical transactions.  Performs suffix intersection. .Transaction to insert into lexicographic tree coreI item, for suffix intersection. %Weight of the transaction to inserct Input lexicographic tree @Result : a new lexicographic tree with the transaction inserted "VFrom a transaction and its weight, directly creates a path-shaped lexicographic tree.  Transaction Weight of the transaction CResult : a path-shaped lexicographic tree encoding the transaction # Perform the suffix intersection, operation with the suffix of a transaction 6 and the corresponding part of a lexicographic tree. For more details, see prefixIntersection in Takeaki Uno's papers about LCM. %Suffix of the transaction to insert. $Weight of the transaction to insert E(Sub-)lexicographic tree where the transaction must be inserted. The next part (see data type comments) S should be a simple path, it will be the target of intersection with the suffix. cResult : lexicographic tree where the suffix has been added, with correct intersections performed. $KIntersects a list-shaped transaction and a path-shaped lexicographic tree. Q The result is a path shaped lexicographic tree with weights correctly updated. Transaction as list  Weight of the above transaction Path-shaped lexicographic tree HResult : (path-shaped lexicographic tree representing the intersection 8 of transaction and input path , 0 if intersection not [] / sum of weights else) %DCollects all the nodes of lexicographic tree in a list of elements.  Path shaped lexicographic tree. MResult : (list of elements in the path, sum of weights of nodes in the path) &Merge two lexicographic trees. Tree 1 Tree 2 #Return : Tree 1 merged with Tree 2 '       !"#$%&'( hlcm-0.2.2HLCM FrequencyItem runLCMstring runLCMmatrixbenchLCM_parBufferbenchLCM_parMapLexicoTreeItemNodeNil TreeWeightWeightTid reversePermloadTransactionsStringloadTransactionsMatrixstringToTransDBconvertOneTrans histogramsortFrqpermut reorderMatoccurrenceDeliverLTtraverse traverse'lcmIterlcmIterParBuffer lcmIterParMapcomputeCandidates suppressItemsprojectAndReducefilterInfrequenttreeMaxinsertLT createPathsuffixIntersectionLT suffInterSuiv getLstSuiv mergeAlts