Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
KnuthMorrisPratt.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <alib/measure>
9
10#include <alib/set>
11#include <alib/vector>
12
13#include <tree/properties/BorderArray.h>
14#include <tree/properties/BorderArrayNaive.h>
15#include <tree/properties/SubtreeJumpTable.h>
16#include <tree/properties/ExactSubtreeRepeatsNaive.h>
17#include <tree/exact/ForwardOccurrenceTest.h>
18
19#include <tree/ranked/PrefixRankedBarTree.h>
20#include <tree/ranked/PrefixRankedBarPattern.h>
21#include <tree/ranked/PrefixRankedBarNonlinearPattern.h>
22#include <tree/ranked/PrefixRankedTree.h>
23#include <tree/ranked/PrefixRankedPattern.h>
24#include <tree/ranked/PrefixRankedExtendedPattern.h>
25#include <tree/ranked/PrefixRankedNonlinearPattern.h>
26
27namespace arbology {
28
29namespace exact {
30
35class KnuthMorrisPratt {
36public:
41 template < class SymbolType >
42 static ext::set < unsigned > match ( const tree::PrefixRankedBarTree < SymbolType > & subject, const tree::PrefixRankedBarTree < SymbolType > & pattern );
43 template < class SymbolType >
44 static ext::set < unsigned > match ( const tree::PrefixRankedBarTree < SymbolType > & subject, const tree::PrefixRankedBarPattern < SymbolType > & pattern );
45 template < class SymbolType >
46 static ext::set < unsigned > match ( const tree::PrefixRankedBarTree < SymbolType > & subject, const tree::PrefixRankedBarNonlinearPattern < SymbolType > & pattern );
47
48 template < class SymbolType >
49 static ext::set < unsigned > match ( const tree::PrefixRankedTree < SymbolType > & subject, const tree::PrefixRankedTree < SymbolType > & pattern );
50 template < class SymbolType >
51 static ext::set < unsigned > match ( const tree::PrefixRankedTree < SymbolType > & subject, const tree::PrefixRankedPattern < SymbolType > & pattern );
52 template < class SymbolType >
53 static ext::set < unsigned > match ( const tree::PrefixRankedTree < SymbolType > & subject, const tree::PrefixRankedExtendedPattern < SymbolType > & pattern );
54 template < class SymbolType >
55 static ext::set < unsigned > match ( const tree::PrefixRankedTree < SymbolType > & subject, const tree::PrefixRankedNonlinearPattern < SymbolType > & pattern );
56
57};
58
59template < class SymbolType >
60ext::set < unsigned > KnuthMorrisPratt::match ( const tree::PrefixRankedBarTree < SymbolType > & subject, const tree::PrefixRankedBarTree < SymbolType > & pattern ) {
61 return match ( subject, tree::PrefixRankedBarPattern < SymbolType > ( pattern ) );
62}
63
64template < class SymbolType >
65ext::set < unsigned > KnuthMorrisPratt::match ( const tree::PrefixRankedBarTree < SymbolType > & subject, const tree::PrefixRankedBarPattern < SymbolType > & pattern ) {
66 ext::set < unsigned > occ;
67 ext::vector < size_t > borderArray = tree::properties::BorderArray::construct ( pattern );
68
69 //measurements::start("Algorithm", measurements::Type::MAIN);
70
71 ext::vector < int > subjectSubtreeJumpTable = tree::properties::SubtreeJumpTable::compute ( subject );
72
73 unsigned firstUnknownPos = pattern.getContent ( ).size ( );
74 for ( unsigned i = 0; i < pattern.getContent ( ).size ( ); ++ i ) {
75 if ( pattern.getContent ( ) [ i ] == pattern.getSubtreeWildcard ( ) ) {
76 firstUnknownPos = i;
77 break;
78 }
79 }
80
81 // index to the subject
82 unsigned i = 0;
83 // index to the pattern
84 unsigned j = 0;
85
86 // main loop of the algorithm over all possible indexes where the pattern can start
87 while ( i + pattern.getContent ( ).size ( ) <= subject.getContent ( ).size ( ) ) {
88 j = tree::exact::ForwardOccurrenceTest::occurrence ( subject, subjectSubtreeJumpTable, pattern, i, j );
89
90 // match was found
91 if ( j >= pattern.getContent ( ).size ( ) ) occ.insert ( i );
92
93 if ( j == 0 ) {
94 i += 1;
95 } else {
96 unsigned shift = j - borderArray [ j ];
97 // shift heuristics
98 i += shift;
99 j = std::min ( firstUnknownPos, j ) - shift;
100 }
101 }
102
103 //measurements::end();
104
105 return occ;
106}
107
108template < class SymbolType >
109ext::set < unsigned > KnuthMorrisPratt::match ( const tree::PrefixRankedBarTree < SymbolType > & subject, const tree::PrefixRankedBarNonlinearPattern < SymbolType > & pattern ) {
110 ext::set < unsigned > occ;
111 ext::vector < size_t > borderArray = tree::properties::BorderArray::construct ( pattern );
112
113 //measurements::start("Algorithm", measurements::Type::MAIN);
114
115 ext::vector < int > subjectSubtreeJumpTable = tree::properties::SubtreeJumpTable::compute ( subject );
116 tree::PrefixRankedBarTree < unsigned > repeats = tree::properties::ExactSubtreeRepeatsNaive::repeats ( subject );
117
118 unsigned firstUnknownPos = pattern.getContent ( ).size ( );
119 for ( unsigned i = 0; i < pattern.getContent ( ).size ( ); ++ i ) {
120 if ( pattern.getContent ( ) [ i ] == pattern.getSubtreeWildcard ( ) || pattern.getNonlinearVariables ( ).contains ( pattern.getContent ( ) [ i ] ) ) {
121 firstUnknownPos = i;
122 break;
123 }
124 }
125
126 // index to the subject
127 unsigned i = 0;
128 // index to the pattern
129 unsigned j = 0;
130
131 // main loop of the algorithm over all possible indexes where the pattern can start
132 while ( i + pattern.getContent ( ).size ( ) <= subject.getContent ( ).size ( ) ) {
133 j = tree::exact::ForwardOccurrenceTest::occurrence ( subject, subjectSubtreeJumpTable, repeats, pattern, i, j );
134
135 // match was found
136 if ( j >= pattern.getContent ( ).size ( ) ) occ.insert ( i );
137
138 if ( j == 0 ) {
139 i += 1;
140 } else {
141 unsigned shift = j - borderArray [ j ];
142 // shift heuristics
143 i += shift;
144 j = std::min ( firstUnknownPos, j ) - shift;
145 }
146 }
147
148 //measurements::end();
149
150 return occ;
151}
152
153template < class SymbolType >
154ext::set < unsigned > KnuthMorrisPratt::match ( const tree::PrefixRankedTree < SymbolType > & subject, const tree::PrefixRankedTree < SymbolType > & pattern ) {
155 return match ( subject, tree::PrefixRankedPattern < SymbolType > ( pattern ) );
156}
157
158template < class SymbolType >
159ext::set < unsigned > KnuthMorrisPratt::match ( const tree::PrefixRankedTree < SymbolType > & subject, const tree::PrefixRankedPattern < SymbolType > & pattern ) {
160 return match ( subject, tree::PrefixRankedExtendedPattern < SymbolType > ( pattern ) );
161}
162
163template < class SymbolType >
164ext::set < unsigned > KnuthMorrisPratt::match ( const tree::PrefixRankedTree < SymbolType > & subject, const tree::PrefixRankedExtendedPattern < SymbolType > & pattern ) {
165 ext::set < unsigned > occ;
166 ext::vector < size_t > borderArray = tree::properties::BorderArrayNaive::construct ( pattern );
167
168 //measurements::start("Algorithm", measurements::Type::MAIN);
169
170 ext::vector < int > subjectSubtreeJumpTable = tree::properties::SubtreeJumpTable::compute ( subject );
171
172 unsigned firstUnknownPos = pattern.getContent ( ).size ( );
173 for ( unsigned i = 0; i < pattern.getContent ( ).size ( ); ++ i ) {
174 if ( pattern.getNodeWildcards ( ).contains ( pattern.getContent ( ) [ i ] ) || pattern.getContent ( ) [ i ] == pattern.getSubtreeWildcard ( ) ) {
175 firstUnknownPos = i;
176 break;
177 }
178 }
179
180 // index to the subject
181 unsigned i = 0;
182 // index to the pattern
183 unsigned j = 0;
184
185 // main loop of the algorithm over all possible indexes where the pattern can start
186 while ( i + pattern.getContent ( ).size ( ) <= subject.getContent ( ).size ( ) ) {
187 j = tree::exact::ForwardOccurrenceTest::occurrence ( subject, subjectSubtreeJumpTable, pattern, i, j );
188
189 // match was found
190 if ( j >= pattern.getContent ( ).size ( ) ) occ.insert ( i );
191
192 if ( j == 0 ) {
193 i += 1;
194 } else {
195 unsigned shift = j - borderArray [ j ];
196 // shift heuristics
197 i += shift;
198 j = std::max ( shift, std::min ( firstUnknownPos, j ) ) - shift;
199 }
200 }
201
202 //measurements::end();
203
204 return occ;
205}
206
207template < class SymbolType >
208ext::set < unsigned > KnuthMorrisPratt::match ( const tree::PrefixRankedTree < SymbolType > & subject, const tree::PrefixRankedNonlinearPattern < SymbolType > & pattern ) {
209 ext::set < unsigned > occ;
210 ext::vector < size_t > borderArray = tree::properties::BorderArray::construct ( pattern );
211
212 //measurements::start("Algorithm", measurements::Type::MAIN);
213
214 ext::vector < int > subjectSubtreeJumpTable = tree::properties::SubtreeJumpTable::compute ( subject );
215 tree::PrefixRankedTree < unsigned > repeats = tree::properties::ExactSubtreeRepeatsNaive::repeats ( subject );
216
217 unsigned firstUnknownPos = pattern.getContent ( ).size ( );
218 for ( unsigned i = 0; i < pattern.getContent ( ).size ( ); ++ i ) {
219 if ( pattern.getContent ( ) [ i ] == pattern.getSubtreeWildcard ( ) || pattern.getNonlinearVariables ( ).contains ( pattern.getContent ( ) [ i ] ) ) {
220 firstUnknownPos = i;
221 break;
222 }
223 }
224
225 // index to the subject
226 unsigned i = 0;
227 // index to the pattern
228 unsigned j = 0;
229
230 // main loop of the algorithm over all possible indexes where the pattern can start
231 while ( i + pattern.getContent ( ).size ( ) <= subject.getContent ( ).size ( ) ) {
232 j = tree::exact::ForwardOccurrenceTest::occurrence ( subject, subjectSubtreeJumpTable, repeats, pattern, i, j );
233
234 // match was found
235 if ( j >= pattern.getContent ( ).size ( ) ) occ.insert ( i );
236
237 if ( j == 0 ) {
238 i += 1;
239 } else {
240 unsigned shift = j - borderArray [ j ];
241 // shift heuristics
242 i += shift;
243 j = std::min ( firstUnknownPos, j ) - shift;
244 }
245 }
246
247 //measurements::end();
248
249 return occ;
250}
251
252} /* namespace exact */
253
254} /* namespace arbology */
255
arbology::exact::KnuthMorrisPratt
Definition: KnuthMorrisPratt.h:35
arbology::exact::KnuthMorrisPratt::match
static ext::set< unsigned > match(const tree::PrefixRankedBarTree< SymbolType > &subject, const tree::PrefixRankedBarTree< SymbolType > &pattern)
Definition: KnuthMorrisPratt.h:60
ext::set
Definition: set.hpp:44
ext::vector
Class extending the vector class from the standard library. Original reason is to allow printing of t...
Definition: vector.hpp:45
tree::PrefixRankedBarNonlinearPattern
Nonlinear tree pattern represented as linear sequece as result of preorder traversal with additional ...
Definition: PrefixRankedBarNonlinearPattern.h:91
tree::PrefixRankedBarNonlinearPattern::getNonlinearVariables
const ext::set< common::ranked_symbol< SymbolType > > & getNonlinearVariables() const &
Definition: PrefixRankedBarNonlinearPattern.h:277
tree::PrefixRankedBarNonlinearPattern::getSubtreeWildcard
const common::ranked_symbol< SymbolType > & getSubtreeWildcard() const &
Definition: PrefixRankedBarNonlinearPattern.h:259
tree::PrefixRankedBarNonlinearPattern::getContent
const ext::vector< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: PrefixRankedBarNonlinearPattern.h:434
tree::PrefixRankedBarPattern
Tree pattern represented as linear sequece as result of preorder traversal with additional bar symbol...
Definition: PrefixRankedBarPattern.h:85
tree::PrefixRankedBarPattern::getSubtreeWildcard
const common::ranked_symbol< SymbolType > & getSubtreeWildcard() const &
Definition: PrefixRankedBarPattern.h:202
tree::PrefixRankedBarPattern::getContent
const ext::vector< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: PrefixRankedBarPattern.h:334
tree::PrefixRankedBarTree
Tree structure represented as linear sequece as result of preorder traversal with additional bar symb...
Definition: PrefixRankedBarTree.h:78
tree::PrefixRankedBarTree::getContent
const ext::vector< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: PrefixRankedBarTree.h:273
tree::PrefixRankedExtendedPattern
Tree pattern represented as linear sequece as result of preorder traversal. The representation is so ...
Definition: PrefixRankedExtendedPattern.h:80
tree::PrefixRankedExtendedPattern::getContent
const ext::vector< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: PrefixRankedExtendedPattern.h:293
tree::PrefixRankedExtendedPattern::getNodeWildcards
const ext::set< common::ranked_symbol< SymbolType > > & getNodeWildcards() const &
Definition: PrefixRankedExtendedPattern.h:157
tree::PrefixRankedExtendedPattern::getSubtreeWildcard
const common::ranked_symbol< SymbolType > & getSubtreeWildcard() const &
Definition: PrefixRankedExtendedPattern.h:184
tree::PrefixRankedNonlinearPattern
Nonlinear tree pattern represented as linear sequece as result of preorder traversal....
Definition: PrefixRankedNonlinearPattern.h:82
tree::PrefixRankedNonlinearPattern::getNonlinearVariables
const ext::set< common::ranked_symbol< SymbolType > > & getNonlinearVariables() const &
Definition: PrefixRankedNonlinearPattern.h:208
tree::PrefixRankedNonlinearPattern::getContent
const ext::vector< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: PrefixRankedNonlinearPattern.h:333
tree::PrefixRankedNonlinearPattern::getSubtreeWildcard
const common::ranked_symbol< SymbolType > & getSubtreeWildcard() const &
Definition: PrefixRankedNonlinearPattern.h:190
tree::PrefixRankedPattern
Tree pattern represented as linear sequece as result of preorder traversal. The representation is so ...
Definition: PrefixRankedPattern.h:77
tree::PrefixRankedTree
Tree structure represented as linear sequece as result of preorder traversal. The representation is s...
Definition: PrefixRankedTree.h:71
tree::PrefixRankedTree::getContent
const ext::vector< common::ranked_symbol< SymbolType > > & getContent() const &
Definition: PrefixRankedTree.h:235
tree::exact::ForwardOccurrenceTest::occurrence
static size_t occurrence(const PrefixRankedBarTree< SymbolType > &subject, const ext::vector< int > &subjectSubtreeJumpTable, const PrefixRankedBarTree< SymbolType > &pattern, size_t subjectPosition, size_t patternStartIndex=0)
Definition: ForwardOccurrenceTest.h:42
tree::properties::BorderArrayNaive::construct
static ext::vector< size_t > construct(const T &pattern)
Definition: BorderArrayNaive.h:59
tree::properties::BorderArray::construct
static ext::vector< size_t > construct(const PrefixRankedPatternType &pattern)
Definition: BorderArray.h:47
tree::properties::SubtreeJumpTable::compute
static ext::vector< int > compute(const tree::PrefixRankedBarTree< SymbolType > &subject)
Definition: SubtreeJumpTable.h:49
arbology
Definition: BoyerMooreHorspool.h:22
automaton::properties::i
int i
Definition: AllEpsilonClosure.h:118
ext::max
constexpr const T & max(const T &a)
Root case of maximum computation. The maximum from one value is the value itself.
Definition: algorithm.hpp:278
ext::min
constexpr const T & min(const T &a)
Definition: algorithm.hpp:310
Generated on Mon Dec 27 2021 10:21:52 for Algorithms Library Toolkit by doxygen 1.9.2