Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#ifndef APPROXIMATE_ENHANCED_COVERS_COMPUTATION_H
#define APPROXIMATE_ENHANCED_COVERS_COMPUTATION_H
#include <alib/set>
#include <string/LinearString.h>
namespace stringology::cover {
struct Element {
unsigned depth, level;
Element ( ) = default;
Element ( unsigned d, unsigned l ) : depth ( d ), level ( l ) { }
};
struct State {
unsigned depth;
ext::vector < Element > elements;
};
class ApproximateEnhancedCoversComputation {
private:
static unsigned distEnhCov ( State const * q );
template < class SymbolType >
static State * constrFirstState ( const string::LinearString < SymbolType > & x, unsigned k );
template < class SymbolType >
static State * constrNextState ( const string::LinearString < SymbolType > & x, State const * previousState, unsigned k );
template < class SymbolType >
static void updateEnhCov ( State const * state, const string::LinearString < SymbolType > & x, ext::set < string::LinearString < SymbolType > > & enhCovers, unsigned & h );
public:
template < class SymbolType >
static ext::set < string::LinearString < SymbolType > > compute ( const string::LinearString < SymbolType > & x, unsigned k );
};
template < class SymbolType >
ext::set < string::LinearString < SymbolType > > ApproximateEnhancedCoversComputation::compute ( const string::LinearString < SymbolType > & x, unsigned k ) {
ext::set < string::LinearString < SymbolType > > result;
unsigned h = 0;
State * previousState = constrFirstState ( x, k );
State * nextState = nullptr;
for ( size_t i = 2; i < x.getContent ( ).size ( ); ++i ) {
nextState = constrNextState ( x, previousState, k );
if ( nextState->elements.size ( ) < 2 ) {
delete nextState;
}
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
delete previousState;
Element lastElement = nextState->elements[nextState->elements.size ( ) - 1];
if ( ( lastElement.depth == x.getContent ( ).size ( ) ) && ( lastElement.level == 0 ) && ( nextState->depth > k ) )
updateEnhCov ( nextState, x, result, h );
previousState = nextState;
}
delete previousState;
return result;
}
unsigned ApproximateEnhancedCoversComputation::distEnhCov ( State const * q ) {
unsigned r = 0;
unsigned m = q->elements[0].depth;
for ( size_t i = 2; i < q->elements.size ( ); ++i ) {
if ( q->elements[i].depth - q->elements[i - 1].depth < m )
r += q->elements[i].depth - q->elements[i - 1].depth;
else
r += m;
}
return r;
}
template < class SymbolType >
State * ApproximateEnhancedCoversComputation::constrFirstState ( const string::LinearString < SymbolType > & x, unsigned k ) {
auto * firstState = new State ( );
firstState->depth = 1;
for ( size_t i = 0; i < x.getContent ( ).size ( ); ++i ) {
if ( x.getContent ( )[0] == x.getContent ( )[i] )
firstState->elements.push_back ( Element ( i + 1, 0 ) );
else if ( k > 0 )
firstState->elements.push_back ( Element ( i + 1, 1 ) );
}
return firstState;
}
template < class SymbolType >
State * ApproximateEnhancedCoversComputation::constrNextState ( const string::LinearString < SymbolType > & x, State const * previousState, unsigned k ) {
auto * nextState = new State ( );
nextState->depth = previousState->depth + 1;
for ( const auto & element : previousState->elements )
if ( element.depth < x.getContent ( ).size ( ) ) {
if ( x.getContent ( )[previousState->depth] == x.getContent ( )[element.depth] )
nextState->elements.push_back ( Element ( element.depth + 1, element.level ) );
else if ( element.level < k )
nextState->elements.push_back ( Element ( element.depth + 1, element.level + 1 ) );
}
return nextState;
}
template < class SymbolType >
void ApproximateEnhancedCoversComputation::updateEnhCov ( State const * state, const string::LinearString < SymbolType > & x, ext::set < string::LinearString < SymbolType > > & enhCovers, unsigned & h ) {
unsigned hNext = distEnhCov ( state );
string::LinearString u ( ext::vector < SymbolType > ( x.getContent ( ).begin ( ), x.getContent ( ).begin ( ) + state->depth ) );
if ( hNext > h ) {
h = hNext;
enhCovers.clear ( );
}
if ( hNext == h )
enhCovers.insert ( u );
}
} /* namespace stringology::cover */
#endif /* APPROXIMATE_ENHANCED_COVERS_COMPUTATION_H */