PBP (pattern-based potentials), version 1.0.

Implementation of some of the techniques from

Ye, Nan, Lee, Wee Sun, Chieu, Hai Leong, and Wu, Dan. 
"Conditional random fields with high-order features for sequence labeling."
NIPS 2009.


Rustem Takhanov and Vladimir Kolmogorov.
"Inference algorithms for pattern-based CRFs on sequence data."
ICML 2013.

Library is located in pattern.h and pattern.cpp.






=== Example ===
In pbp.cpp there is an example of how library can be used.

g++ pbp.cpp pattern.cpp -o pbp
./pbp

=== Constructor ===
Constructor of class potential has 3 arguments: number of chain variables, cardinality of alphabet and maximal number of words in a set of pattern words Pi. We assume that if cardinality of alphabet is D, then our alphabet is {1,2,3,...,D}. 

=== Pattern ===
In our paper we define weighted pattern as a triple [i,j,alpha] with weight. It is reflected in our struct Cost:
struct Cost
{
	int i,j;
	wchar_t* alpha;
	double cost;
};
Here alpha is over alphabet of {1,2,3,...,D} casted to wchar_t. Note that as in our paper, we index i,j from 1 to N (number of chain variables).

=== Adding patterns ===
Using function add_pattern(Cost* p) you can add patterns with weights.

=== Words preprocessing ===
In words_preprocess() our algorithm initialized a prefix tree for your set of pattern words. If at some point you call words_preprocess(), then after this you cannot add patterns with NEW words, but you can add any patterns with already known words. 

=== Weights preprocess ===
After weights_preprocess() you can call functions compute_stat_sum(), compute_stat_sum_back(), wchar_t* compute_map(), compute_marginals(),sample() etc. 

=== Access to messages ===
Among public variables we have: stat_messages_forward, stat_messages_forward_log, stat_messages_backward, stat_messages_backward_log, map_messages, marginals. They all have type double**. For each of them T[i,id] is interpreted the following way: it is a message that corresponds to a pattern with interval that ends at i and a word with internal identifier id.
In order to access, for example, marginal p(x_{i:j}="121") you have to call: 

	whar_t* alpha = L"121";
	double probability = marginals[j,word_to_id_hash[alpha]];

=== Zeroing all weights === 
If you need to zero pattern weights, then auf_null() is a function that makes it. After using auf_null() you don`t have to call again words_preprocess(), because this function preserve old prefix tree.

=== Complexities === 
N=length of chain
L=sum of words lengths
l=maximum of words lengths
D=cardinality of alphabet

Our implemented algorithms have the following complexities:
Computing all marginals: O( N*L*l )
Partition function: O( N*L )
MAP: O( N*L*D ) (it could be done in O( N*L*log l ), but we did not implement it)
Sampling: O( N*L*D ) (it could be done faster with preprocessing, but we did not implement it)

