Диссертация (1137435), страница 20
Текст из файла (страница 20)
s i z e ( ) ; ++j ) {Implication I ;I . n u m b e r _ o f _ a t t r i i b u t e s = m;I . l e f t = tr [ j ] ;s o r t ( I . l e f t . b e g i n ( ) , I . l e f t . end ( ) ) ;I . r i g h t = K. c l o s u r e ( I . l e f t ) ;J . push_back ( I ) ;}}return J ;}}1705.11.Приложение 2.1Файл shared_closure.h:#i f n d e f SHARED_CLOSURE_H#define SHARED_CLOSURE_H#include " mset . h"#include " c o n t e x t . h"#include <v e c t o r >#include <queue>#include < l i s t >#include <a l g o r i t h m >namespace s h a r e d _ c l o s u r e {mset c l o s u r e ( const s t d : : v e c t o r <s p a r s e _ c o n t e x t : : Context>& K,const mset& X) ;class PriorityQueue{public :P r i o r i t y Q u e u e ( int M = 0 ) ;void i n c r e a s e ( int a ) ;void d e c r e a s e _ a l l ( ) ;int get_min ( ) ;int extract_min ( ) ;void s e t ( int a , int key ) ;private :171s t d : : v e c t o r <s t d : : l i s t <int> > a t t r i b u t e s ;s t d : : v e c t o r <int> l i n k _ t o _ l i s t _ i n d e x ;s t d : : v e c t o r <s t d : : l i s t <int > : : c o n s t _ i t e r a t o r >link_to_list_item ;int no_deq ;int f i r s t ;};}#endifФайл shared_closure.cpp:#include " s h a r e d _ c l o s u r e .
h"namespace s h a r e d _ c l o s u r e {mset c l o s u r e ( const s t d : : v e c t o r <s p a r s e _ c o n t e x t : : Context>& K,const mset& X) {int m = K [ 0 ] .M;s t d : : v e c t o r <s t d : : v e c t o r <s t d : : v e c t o r <int> > > Kt ;f o r ( int t = 0 ; t < K. s i z e ( ) ; ++t ) {Kt .
push_back ( s t d : : v e c t o r <s t d : : v e c t o r <int >>(m,s t d : : v e c t o r <int >() ) ) ;f o r ( int i = 0 ; i < K[ t ] . o b j e c t s . s i z e ( ) ; ++i ) {172fo r ( int j = 0 ; j < K[ t ] . o b j e c t s [ i ] .s i z e ( ) ; ++j ) {int a = K[ t ] . o b j e c t s [ i ] [ j ] ;Kt [ t ] [ a ] . push_back ( i ) ;}}}s t d : : v e c t o r <bool> a d d e d _ a t t r i b u t e s (m, f a l s e ) ;f o r ( int i = 0 ; i < X. s i z e ( ) ; ++i )a d d e d _ a t t r i b u t e s [X[ i ] ] = true ;s t d : : v e c t o r <P r i o r i t y Q u e u e > PQ(K. s i z e ( ) , P r i o r i t y Q u e u e (m));s t d : : queue<int> s h a r e d _ a t t r i b u t e s ;s t d : : v e c t o r <s t d : : v e c t o r <int> > o b j e c t s (K.
s i z e ( ) ) ;f o r ( int t = 0 ; t < K. s i z e ( ) ; ++t ) {s t d : : v e c t o r <int> c n t (m, 0 ) ;f o r ( int i = 0 ; i < K[ t ] . o b j e c t s . s i z e ( ) ; ++i ) {i f ( i s _ s u b s e t (K[ t ] . o b j e c t s [ i ] , X) ) {o b j e c t s [ t ] .
push_back ( i ) ;fo r ( int j = 0 ; j < K[ t ] .o b j e c t s [ i ] . s i z e ( ) ; ++j ) {int a = K[ t ] . o b j e c t s [ i][ j ];++c n t [ a ] ;173}}}f o r ( int a = 0 ; a < m; ++a ) {i f ( o b j e c t s [ t ] . s i z e ( ) == c n t [ a ] && !added_attributes [ a ] ) {a d d e d _ a t t r i b u t e s [ a ] = true ;s h a r e d _ a t t r i b u t e s . push ( a ) ;} elsePQ[ t ] . s e t ( a , ( int ) o b j e c t s [ t ] .s i z e ( ) − cnt [ a ] ) ;}}mset r e t = X;while ( ! s h a r e d _ a t t r i b u t e s . empty ( ) ) {int j 0 = s h a r e d _ a t t r i b u t e s .
f r o n t ( ) ;s h a r e d _ a t t r i b u t e s . pop ( ) ;f o r ( int t = 0 ; t < K. s i z e ( ) ; ++t ) {int s z = o b j e c t s [ t ] . s i z e ( ) ;o b j e c t s [ j 0 ] = g e t _ i n t e r s e c t i o n ( Kt [ t ] [ j 0] , objects [ j0 ] ) ;s t d : : v e c t o r <int>& l i s t 0 = Kt [ t ] [ j 0 ] ;s t d : : v e c t o r <int>& l i s t 1 = o b j e c t s [ t ] ;174int i 0 = 0 , i 1 = 0 , obj_sz = 0 ;while ( i 0 < l i s t 0 . s i z e ( ) && i 1 < l i s t 1 .size () ) {i f ( l i s t 0 [ i 0 ] == l i s t 1 [ i 1 ] ) {o b j e c t s [ t ] [ obj_sz ] =l i s t 1 [ i1 ] ;++obj_sz ;++i 0 ;++i 1 ;} else i f ( l i s t 0 [ i0 ] < l i s t 1 [ i1]) {++i 0 ;} else {fo r ( int j = 0 ; j < K[ t] . objects [ i1 ] .
size (); ++j ) {int a = K[ t ] .objects [ i1 ] [j ];PQ[ t ] . i n c r e a s e (a) ;}PQ[ t ] . d e c r e a s e _ a l l ( ) ;++i 1 ;}}175while (PQ[ t ] . get_min ( ) == 0 ) {int a = PQ[ t ] . extract_min ( ) ;i f ( ! added_attributes [ a ] ) {added_attributes [ a ] =true ;s h a r e d _ a t t r i b u t e s . push (a) ;}}o b j e c t s [ t ] .
r e s i z e ( obj_sz ) ;}}return r e t ;}int P r i o r i t y Q u e u e : : get_min ( ) {while ( f i r s t < a t t r i b u t e s . s i z e ( ) ) {i f ( ! a t t r i b u t e s [ f i r s t ] . empty ( ) )break ;}i f ( f i r s t >= a t t r i b u t e s . s i z e ( ) )return −1;return f i r s t − no_deq ;}176int P r i o r i t y Q u e u e : : extract_min ( ) {i f ( get_min ( ) == −1)return −1;int a = a t t r i b u t e s [ f i r s t ] .
f r o n t ( ) ;a t t r i b u t e s [ f i r s t ] . erase ( a t t r i b u t e s [ f i r s t ] . begin () ) ;return a ;}void P r i o r i t y Q u e u e : : s e t ( int a , int key ) {a t t r i b u t e s [ key + no_deq ] . push_front ( a ) ;l i n k _ t o _ l i s t _ i n d e x [ a ] = key + no_deq ;l i n k _ t o _ l i s t _ i t e m [ a ] = a t t r i b u t e s [ key + no_deq ] . b e g i n ( );}void P r i o r i t y Q u e u e : : d e c r e a s e _ a l l ( ) {++no_deq ;}void P r i o r i t y Q u e u e : : i n c r e a s e ( int a ) {int i = l i n k _ t o _ l i s t _ i n d e x [ a ] ;++l i n k _ t o _ l i s t _ i n d e x [ a ] ;s t d : : l i s t <int > : : c o n s t _ i t e r a t o r i t = l i n k _ t o _ l i s t _ i t e m [ a];177attributes [ i ] .
erase ( it ) ;a t t r i b u t e s [ i + 1 ] . push_front ( a ) ;link_to_list_item [ a ] = a t t r i b u t e s [ i + 1 ] . begin () ;}P r i o r i t y Q u e u e : : P r i o r i t y Q u e u e ( int M = 0 ) : no_deq ( 0 ) , f i r s t ( 0 ) {a t t r i b u t e s . r e s i z e (M + M) ;l i n k _ t o _ l i s t _ i n d e x . a s s i g n (M + M, −1) ;l i n k _ t o _ l i s t _ i t e m . r e s i z e (M + M) ;}}5.12.Приложение 3.1Файл JSM_test.cpp:#include <i o s t r e a m >#include <a l g o r i t h m >#include <v e c t o r >#include <s e t >#include <s t r i n g >#include <sstream >#include " mset . h"#include " c o n t e x t . h"using namespace s t d ;using namespace s p a r s e _ c o n t e x t ;178void r e a d ( Context& K, s t r i n g fname ) {f r e o p e n ( fname .
c _ s t r ( ) , " r " , s t d i n ) ;K. o b j e c t s . r e s i z e ( 0 ) ;K.M = 0 ;string s ;while ( g e t l i n e ( c i n , s ) ) {istringstream is ( s ) ;mset row ;int a ;while ( i s >> a ) {row . push_back ( a ) ;K.M = max(K.M, a + 1 ) ;}K. o b j e c t s . push_back ( row ) ;}cin . clear () ;}void r e a d _ a l l ( v e c t o r <Context>& pK, v e c t o r <Context>& nK, bool t r = true ,int s u p p o r t = 3 5 ) {pK . r e s i z e ( 0 ) ;nK . r e s i z e ( 0 ) ;string suf = " tr " ;179if (! tr )suf = " tst " ;s t r i n g f o l d [ ] = {"MM/" , "FM/" , "MR/" , "FR/" } ;s t r i n g p = " data /" ;s t r i n g supp = " 035 " ;i f ( s u p p o r t == 2 )supp = " 002 " ;i f ( s u p p o r t == 5 )supp = " 005 " ;i f ( s u p p o r t == 1 0 )supp = " 01 " ;i f ( s u p p o r t == 3 0 )supp = " 03 " ;i f ( s u p p o r t == 2 0 )supp = " 02 " ;Context K;f o r ( int i = 0 ; i < 4 ; ++i ) {s t r i n g d i r = p + f o l d [ i ] + "db .
g r . f p . " + supp + "−v0−a t t r s −"+ s u f + "−P" ;r e a d (K, d i r ) ;pK . push_back (K) ;}f o r ( int i = 0 ; i < 4 ; ++i ) {180s t r i n g d i r = p + f o l d [ i ] + "db . g r . f p . " + supp + "−v0−a t t r s −"+ s u f + "−N" ;r e a d (K, d i r ) ;nK . push_back (K) ;}int M = 0 ;f o r ( int i = 0 ; i < pK .
s i z e ( ) ; ++i ) {M = max(M, pK [ i ] .M) ;M = max(M, nK [ i ] .M) ;}f o r ( int i = 0 ; i < pK . s i z e ( ) ; ++i ) {pK [ i ] .M = M;nK [ i ] .M = M;}}mset c l o s u r e ( const v e c t o r <Context>& K, mset X) {bool updated = true ;while ( updated ) {updated = f a l s e ;f o r ( int i = 0 ; i < K. s i z e ( ) ; ++i ) {int s z = X. s i z e ( ) ;X = K[ i ] .
c l o s u r e (X) ;i f (X. s i z e ( ) != s z )updated = true ;181i f (X. s i z e ( ) == K[ i ] .M)break ;}i f (K. s i z e ( ) == 1 )break ;}return X;}double s t a b i l i t y ( const mset& X, const Context& K) {int n = 5 0 , r e t = 0 ;mset s u b s e t ;f o r ( int i t = 0 ; i t < n ; ++i t ) {rand_subset (X, 0 . 5 , s u b s e t ) ;i f (K. c l o s u r e ( s u b s e t ) == X)++r e t ;}return ( double ) r e t / n ;}mset n e x t _ c l o s u r e ( const mset& X, const v e c t o r <Context>& K) {int m = K [ 0 ] .M;f o r ( int i = m − 1 ; i >=0 ; −−i ) {mset Y;bool ok = true ;f o r ( int j = 0 ; j < X. s i z e ( ) ; ++j ) {182i f (X[ j ] == i ) {ok = f a l s e ;break ;} e l s e i f (X[ j ] < i )Y.
push_back (X[ j ] ) ;elsebreak ;}i f ( ok ) {Y. push_back ( i ) ;Y = c l o s u r e (K, Y) ;ok = true ;int j = 0 , k = 0 ;while ( j < X. s i z e ( ) && k < Y. s i z e ( ) ) {i f (X[ j ] >= i | | Y[ k ] >= i )break ;i f (X[ j ] != Y[ k ] ) {ok = f a l s e ;break ;}++j ;++k ;}i f ( j < X. s i z e ( ) )i f (X[ j ] < i )ok = f a l s e ;183i f ( k < Y. s i z e ( ) )i f (Y[ k ] < i )ok = f a l s e ;i f ( ok )return Y;}}return X;}void maximize ( v e c t o r <mset>& x , bool minimize = f a l s e ) {s o r t ( x .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
