<s> from collections import defaultdict , deque , OrderedDict <EOL> def _sort_transactions_by_freq ( <EOL> transactions , key_func , reverse_int = False , <EOL> reverse_ext = False , sort_ext = True ) : <EOL> key_seqs = [ { key_func ( i ) for i in sequence } for sequence in transactions ] <EOL> frequencies = get_frequencies ( key_seqs ) <EOL> asorted_seqs = [ ] <EOL> for key_seq in key_seqs : <EOL> if not key_seq : <EOL> continue <EOL> l = [ ( frequencies [ i ] , i ) for i in key_seq ] <EOL> l . sort ( reverse = reverse_int ) <EOL> asorted_seqs . append ( tuple ( l ) ) <EOL> if sort_ext : <EOL> asorted_seqs . sort ( reverse = reverse_ext ) <EOL> return ( asorted_seqs , frequencies ) <EOL> def get_frequencies ( transactions ) : <EOL> '''<STR_LIT>''' <EOL> frequencies = defaultdict ( int ) <EOL> for transaction in transactions : <EOL> for item in transaction : <EOL> frequencies [ item ] += <NUM_LIT:1> <EOL> return frequencies <EOL> def get_sam_input ( transactions , key_func = None ) : <EOL> '''<STR_LIT>''' <EOL> if key_func is None : <EOL> def key_func ( e ) : <EOL> return e <EOL> ( asorted_seqs , _ ) = _sort_transactions_by_freq ( transactions , key_func ) <EOL> sam_input = deque ( ) <EOL> visited = { } <EOL> current = <NUM_LIT:0> <EOL> for seq in asorted_seqs : <EOL> if seq not in visited : <EOL> sam_input . append ( ( <NUM_LIT:1> , seq ) ) <EOL> visited [ seq ] = current <EOL> current += <NUM_LIT:1> <EOL> else : <EOL> i = visited [ seq ] <EOL> ( count , oldseq ) = sam_input [ i ] <EOL> sam_input [ i ] = ( count + <NUM_LIT:1> , oldseq ) <EOL> return sam_input <EOL> def sam ( sam_input , min_support = <NUM_LIT:2> ) : <EOL> '''<STR_LIT>''' <EOL> fis = set ( ) <EOL> report = { } <EOL> _sam ( sam_input , fis , report , min_support ) <EOL> return report <EOL> def _sam ( sam_input , fis , report , min_support ) : <EOL> n = <NUM_LIT:0> <EOL> a = deque ( sam_input ) <EOL> while len ( a ) > <NUM_LIT:0> and len ( a [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] ) > <NUM_LIT:0> : <EOL> b = deque ( ) <EOL> s = <NUM_LIT:0> <EOL> i = a [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] [ <NUM_LIT:0> ] <EOL> while len ( a ) > <NUM_LIT:0> and len ( a [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] ) > <NUM_LIT:0> and a [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] [ <NUM_LIT:0> ] == i : <EOL> s = s + a [ <NUM_LIT:0> ] [ <NUM_LIT:0> ] <EOL> a [ <NUM_LIT:0> ] = ( a [ <NUM_LIT:0> ] [ <NUM_LIT:0> ] , a [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] [ <NUM_LIT:1> : ] ) <EOL> if len ( a [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] ) > <NUM_LIT:0> : <EOL> b . append ( a . popleft ( ) ) <EOL> else : <EOL> a . popleft ( ) <EOL> c = deque ( b ) <EOL> d = deque ( ) <EOL> while len ( a ) > <NUM_LIT:0> and len ( b ) > <NUM_LIT:0> : <EOL> if a [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] > b [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] : <EOL> d . append ( b . popleft ( ) ) <EOL> elif a [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] < b [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] : <EOL> d . append ( a . popleft ( ) ) <EOL> else : <EOL> b [ <NUM_LIT:0> ] = ( b [ <NUM_LIT:0> ] [ <NUM_LIT:0> ] + a [ <NUM_LIT:0> ] [ <NUM_LIT:0> ] , b [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] ) <EOL> d . append ( b . popleft ( ) ) <EOL> a . popleft ( ) <EOL> while len ( a ) > <NUM_LIT:0> : <EOL> d . append ( a . popleft ( ) ) <EOL> while len ( b ) > <NUM_LIT:0> : <EOL> d . append ( b . popleft ( ) ) <EOL> a = d <EOL> if s >= min_support : <EOL> fis . add ( i [ <NUM_LIT:1> ] ) <EOL> report [ frozenset ( fis ) ] = s <EOL> n = n + <NUM_LIT:1> + _sam ( c , fis , report , min_support ) <EOL> fis . remove ( i [ <NUM_LIT:1> ] ) <EOL> return n <EOL> def _new_relim_input ( size , key_map ) : <EOL> i = <NUM_LIT:0> <EOL> l = [ ] <EOL> for key in key_map : <EOL> if i >= size : <EOL> break <EOL> l . append ( ( ( <NUM_LIT:0> , key ) , [ ] ) ) <EOL> i = i + <NUM_LIT:1> <EOL> return l <EOL> def _get_key_map ( frequencies ) : <EOL> l = [ ( frequencies [ k ] , k ) for k in frequencies ] <EOL> l . sort ( reverse = True ) <EOL> key_map = OrderedDict ( ) <EOL> for i , v in enumerate ( l ) : <EOL> key_map [ v ] = i <EOL> return key_map <EOL> def get_relim_input ( transactions , key_func = None ) : <EOL> '''<STR_LIT>''' <EOL> if key_func is None : <EOL> def key_func ( e ) : <EOL> return e <EOL> ( asorted_seqs , frequencies ) = _sort_transactions_by_freq ( <EOL> transactions , key_func ) <EOL> key_map = _get_key_map ( frequencies ) <EOL> relim_input = _new_relim_input ( len ( key_map ) , key_map ) <EOL> for seq in asorted_seqs : <EOL> if not seq : <EOL> continue <EOL> index = key_map [ seq [ <NUM_LIT:0> ] ] <EOL> ( ( count , char ) , lists ) = relim_input [ index ] <EOL> rest = seq [ <NUM_LIT:1> : ] <EOL> found = False <EOL> for i , ( rest_count , rest_seq ) in enumerate ( lists ) : <EOL> if rest_seq == rest : <EOL> lists [ i ] = ( rest_count + <NUM_LIT:1> , rest_seq ) <EOL> found = True <EOL> break <EOL> if not found : <EOL> lists . append ( ( <NUM_LIT:1> , rest ) ) <EOL> relim_input [ index ] = ( ( count + <NUM_LIT:1> , char ) , lists ) <EOL> return ( relim_input , key_map ) <EOL> def relim ( rinput , min_support = <NUM_LIT:2> ) : <EOL> '''<STR_LIT>''' <EOL> fis = set ( ) <EOL> report = { } <EOL> _relim ( rinput , fis , report , min_support ) <EOL> return report <EOL> def _relim ( rinput , fis , report , min_support ) : <EOL> ( relim_input , key_map ) = rinput <EOL> n = <NUM_LIT:0> <EOL> a = relim_input <EOL> while len ( a ) > <NUM_LIT:0> : <EOL> item = a [ - <NUM_LIT:1> ] [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] <EOL> s = a [ - <NUM_LIT:1> ] [ <NUM_LIT:0> ] [ <NUM_LIT:0> ] <EOL> if s >= min_support : <EOL> fis . add ( item [ <NUM_LIT:1> ] ) <EOL> report [ frozenset ( fis ) ] = s <EOL> b = _new_relim_input ( len ( a ) - <NUM_LIT:1> , key_map ) <EOL> rest_lists = a [ - <NUM_LIT:1> ] [ <NUM_LIT:1> ] <EOL> for ( count , rest ) in rest_lists : <EOL> if not rest : <EOL> continue <EOL> k = rest [ <NUM_LIT:0> ] <EOL> index = key_map [ k ] <EOL> new_rest = rest [ <NUM_LIT:1> : ] <EOL> ( ( k_count , k ) , lists ) = b [ index ] <EOL> if len ( new_rest ) > <NUM_LIT:0> : <EOL> lists . append ( ( count , new_rest ) ) <EOL> b [ index ] = ( ( k_count + count , k ) , lists ) <EOL> n = n + <NUM_LIT:1> + _relim ( ( b , key_map ) , fis , report , min_support ) <EOL> fis . remove ( item [ <NUM_LIT:1> ] ) <EOL> rest_lists = a [ - <NUM_LIT:1> ] [ <NUM_LIT:1> ] <EOL> for ( count , rest ) in rest_lists : <EOL> if not rest : <EOL> continue <EOL> k = rest [ <NUM_LIT:0> ] <EOL> index = key_map [ k ] <EOL> new_rest = rest [ <NUM_LIT:1> : ] <EOL> ( ( k_count , k ) , lists ) = a [ index ] <EOL> if len ( new_rest ) > <NUM_LIT:0> : <EOL> lists . append ( ( count , new_rest ) ) <EOL> a [ index ] = ( ( k_count + count , k ) , lists ) <EOL> a . pop ( ) <EOL> return n <EOL> class FPNode ( object ) : <EOL> root_key = object ( ) <EOL> def __init__ ( self , key , parent ) : <EOL> self . children = { } <EOL> self . parent = parent <EOL> self . key = key <EOL> self . count = <NUM_LIT:0> <EOL> self . next_node = None <EOL> def add_path ( self , path , index , length , heads , last_insert ) : <EOL> if index >= length : <EOL> return <EOL> child_key = path [ index ] <EOL> index += <NUM_LIT:1> <EOL> try : <EOL> child = self . children [ child_key ] <EOL> except Exception : <EOL> child = self . _create_child ( child_key , heads , last_insert ) <EOL> child . count += <NUM_LIT:1> <EOL> heads [ child_key ] [ <NUM_LIT:1> ] += <NUM_LIT:1> <EOL> child . add_path ( path , index , length , heads , last_insert ) <EOL> def _create_child ( self , child_key , heads , last_insert ) : <EOL> child = FPNode ( child_key , self ) <EOL> self . children [ child_key ] = child <EOL> try : <EOL> last_child = last_insert [ child_key ] <EOL> last_child . next_node = child <EOL> except Exception : <EOL> heads [ child_key ] = [ child , <NUM_LIT:0> ] <EOL> last_insert [ child_key ] = child <EOL> return child <EOL> def get_cond_tree ( <EOL> self , child , count , visited , heads , last_insert , <EOL> dont_create = False ) : <EOL> key = self . key <EOL> if dont_create : <EOL> cond_node = None <EOL> else : <EOL> try : <EOL> cond_node = visited [ self ] <EOL> except Exception : <EOL> cond_node = self . _create_cond_child ( <EOL> visited , heads , last_insert ) <EOL> if self . parent is not None : <EOL> parent_node = self . parent . get_cond_tree ( <EOL> cond_node , count , visited , heads , last_insert , False ) <EOL> if cond_node is not None : <EOL> cond_node . count += count <EOL> heads [ key ] [ <NUM_LIT:1> ] += count <EOL> cond_node . parent = parent_node <EOL> return cond_node <EOL> def _create_cond_child ( self , visited , heads , last_insert ) : <EOL> key = self . key <EOL> cond_node = FPNode ( key , None ) <EOL> visited [ self ] = cond_node <EOL> try : <EOL> last_cond_node = last_insert [ key ] <EOL> last_cond_node . next_node = cond_node <EOL> except Exception : <EOL> if self . parent is not None : <EOL> heads [ key ] = [ cond_node , <NUM_LIT:0> ] <EOL> last_insert [ key ] = cond_node <EOL> return cond_node <EOL> def _find_ancestor ( self , heads , min_support ) : <EOL> ancestor = self . parent <EOL> while ancestor . key != FPNode . root_key : <EOL> support = heads [ ancestor . key ] [ <NUM_LIT:1> ] <EOL> if support >= min_support : <EOL> break <EOL> else : <EOL> ancestor = ancestor . parent <EOL> return ancestor <EOL> def prune_me ( <EOL> self , from_head_list , visited_parents , merged_before , <EOL> merged_now , heads , min_support ) : <EOL> try : <EOL> new_parent = merged_before [ self . parent ] <EOL> self . parent = new_parent <EOL> except KeyError : <EOL> pass <EOL> ancestor = self . _find_ancestor ( heads , min_support ) <EOL> self . parent = ancestor <EOL> try : <EOL> other_node = visited_parents [ ancestor ] <EOL> merged_now [ self ] = other_node <EOL> other_node . count += self . count <EOL> if from_head_list is not None : <EOL> from_head_list . next_node = self . next_node <EOL> self . next_node = None <EOL> except KeyError : <EOL> visited_parents [ ancestor ] = self <EOL> def __str__ ( self ) : <EOL> child_str = '<STR_LIT:U+002C>' . join ( [ str ( key ) for key in self . children ] ) <EOL> return '<STR_LIT>' . format ( <EOL> self . key , self . count , child_str , <EOL> self . next_node is not None ) <EOL> def __repr__ ( self ) : <EOL> return self . __str__ ( ) <EOL> def get_fptree ( transactions , key_func = None , min_support = <NUM_LIT:2> ) : <EOL> '''<STR_LIT>''' <EOL> if key_func is None : <EOL> def key_func ( e ) : <EOL> return e <EOL> asorted_seqs , frequencies = _sort_transactions_by_freq ( <EOL> transactions , key_func , True , False , False ) <EOL> transactions = [ <EOL> [ item [ <NUM_LIT:1> ] for item in aseq if item [ <NUM_LIT:0> ] >= min_support ] for <EOL> aseq in asorted_seqs ] <EOL> root = FPNode ( FPNode . root_key , None ) <EOL> heads = { } <EOL> last_insert = { } <EOL> for transaction in transactions : <EOL> root . add_path ( transaction , <NUM_LIT:0> , len ( transaction ) , heads , last_insert ) <EOL> sorted_heads = sorted ( heads . values ( ) , key = lambda v : ( v [ <NUM_LIT:1> ] , v [ <NUM_LIT:0> ] . key ) ) <EOL> new_heads = OrderedDict ( ) <EOL> for ( head , head_support ) in sorted_heads : <EOL> new_heads [ head . key ] = ( head , head_support ) <EOL> return ( root , new_heads ) <EOL> def _init_heads ( orig_heads ) : <EOL> new_heads = OrderedDict ( ) <EOL> for key in orig_heads : <EOL> new_heads [ key ] = ( None , <NUM_LIT:0> ) <EOL> return new_heads <EOL> def _create_cond_tree ( head_node , new_heads , pruning ) : <EOL> visited = { } <EOL> last_insert = { } <EOL> while head_node is not None : <EOL> head_node . get_cond_tree ( <EOL> None , head_node . count , visited , new_heads , <EOL> last_insert , True ) <EOL> head_node = head_node . next_node <EOL> return new_heads <EOL> def _prune_cond_tree ( heads , min_support ) : <EOL> merged_before = { } <EOL> merged_now = { } <EOL> for key in reversed ( heads ) : <EOL> ( node , head_support ) = heads [ key ] <EOL> if head_support > <NUM_LIT:0> : <EOL> visited_parents = { } <EOL> previous_node = None <EOL> while node is not None : <EOL> next_node = node . next_node <EOL> node . prune_me ( <EOL> previous_node , visited_parents , merged_before , <EOL> merged_now , heads , min_support ) <EOL> if node . next_node is not None : <EOL> previous_node = node <EOL> node = next_node <EOL> merged_before = merged_now <EOL> merged_now = { } <EOL> def fpgrowth ( fptree , min_support = <NUM_LIT:2> , pruning = False ) : <EOL> '''<STR_LIT>''' <EOL> fis = set ( ) <EOL> report = { } <EOL> _fpgrowth ( fptree , fis , report , min_support , pruning ) <EOL> return report <EOL> def _fpgrowth ( fptree , fis , report , min_support = <NUM_LIT:2> , pruning = True ) : <EOL> ( _ , heads ) = fptree <EOL> n = <NUM_LIT:0> <EOL> for ( head_node , head_support ) in heads . values ( ) : <EOL> if head_support < min_support : <EOL> continue <EOL> fis . add ( head_node . key ) <EOL> report [ frozenset ( fis ) ] = head_support <EOL> new_heads = _init_heads ( heads ) <EOL> _create_cond_tree ( head_node , new_heads , pruning ) <EOL> if pruning : <EOL> _prune_cond_tree ( new_heads , min_support ) <EOL> n = n + <NUM_LIT:1> + _fpgrowth ( <EOL> ( None , new_heads ) , fis , report , min_support , pruning ) <EOL> fis . remove ( head_node . key ) <EOL> return n </s>
