Olivier -- Olivier Austina <olivier.austina@gmail.com> writes:
I try to use pattern matching approach for a dataset with multilevel tags. Suppose we have 2 sets of features: F and H with the following tags F={f0, f1, f2, f3} and H={h0, h1, h2, h3, h4} to describe a set of elements E={e1, e2, e3.....en}. We have in a table a sequence of E elements describe as following:
E e1 e2 e3 e4 e5 e6 e7 e8 ...........en F f3 f0 f0 f0 f2 f3 f0 f2 f0 H h4 h0 h4 h1 h0 h2 h3 h2 h1
The order in which e1, e2 e3...... appear is important as words in a sentence.
Suppose we have the following RE with f3 and f0 as following: f3f0+ . It will match the corresponding sequence e1, e2, e3, e4 and e6, e7 in E. Now we want to add additional constraint as the last f0 should map a h1 in H. In this case the final result will be only the sequence e1, e2, e3, e4 because in the last sequence e6, e7 the f0 map h3 in H.The final result is always E sequences but the RE and constraint can be based on E, F or H.
May be it becomes a bit clear. Thank for your help.
This does make more sense. I suspect that what you will want to do is to use a regex iterator for each constraint that you're trying to apply. Each time a given iterator matches, it will make a sequence (begin+end) available; you can then apply whatever other constraints you need, to determine whether you want to save (or otherwise note) the match. Are F and H distinct types? If so, it gets ugly, because you need a different regex template for each type you're trying to match against, and those templates are not related (so you can't easily store an arbitrary list of them). Maybe variant would help. If you really only have two tags, a cheap-and-dirty trick is to try to fit them into bitfields, then match on character sets. E.g., f0 = 0x00 h0 = 0x00 f1 0x10 h1 0x01 f2 0x20 h2 0x02 ... ... f15 0xf0 h15 0x0f So your sample vector becomes: element: e1 e2 e3 e4 e5 ... tags: 0x 34 00 04 01 20 ... And you can do your matches by slicing the bitfield either way: f3f0+ [\x30-\x3f][\x00-\x0f]+ "last f0 should also be h1" .*?(:>\x01[^\x00-\x0f]) Or something like that, it's easier if you know that will always come after the first filter, or you can combine them: f3f0+ where last f0 should also be h1 [\x30-\x3f][\x00-\x0f]*\x01 But this is insane, of course, and probably not applicable. (And "\x00" in a string literal is just asking for trouble.) You could play games with fixed-width representations as well, depending on your exact requirements. Instead of having two rows, you interleave the tags: E e1 e2 e3 e4 e5 e6 e7 e8 ...........en FH f3h4f0h0f0h4f0h1f2h0f3h2f0h3f2h2 f0h1 And you can then use the same tricks as above, but with '.' as a "don't care" value: "f3f0+" becomes "(?:f3..)(?:f0..)+" And the additional constraint is even more straightforward: "(?:f3..)(?:f0..)*(?:f0h1)" This will probably be a bit less efficient, but... If you really do want to use the regex machinery on the raw tag types, I think you need to do all of this: 1. Create a boost::regex instantiation that knows about your tags, which probably means at least creating a traits class for each of your tags: http://www.boost.org/doc/libs/1_54_0/libs/regex/doc/html/boost_regex/ref/con... 2. Build something that will turn an iterator across your table into an iterator across just one row of that table, and vice-versa. 3. Make a struct or class that manages those two for a given tag type and row; 4. Make all those structs related by inheritance to a base struct (or use some sort of type erasure technique, or lambdas maybe.) Whether it's worth all that work would depend on how many criteria you want to express, IMHO. (And even then, I'm not sure it will work gracefully, since regex mingles data (regular characters) with control (meta characters). Since your tags aren't really "characters" in this sense, I'm not sure this will work.) It might be that using Spirit might be easier, or doing the state machine explicitly.