metric learning and information retrieval I am interested in parsing semi-structured text.
Assume that I have a text with labels of the kind: year_field, year_value, identity_field, identity_value, ..., address_field, address_value, and so on.

These fields and their associated values can be everywhere in the text, but usually they are near to each other, and more generally the text in organized in a (very) rough matrix, but rather often the value is just after the associated field with eventually some non-interesting information in between. 

The number of different format can be up to several dozens, and is not that rigid (do not count on spacing, moreover some information can be added and removed).

I am looking toward machine learning techniques to extract all those (field,value) of interest.

I think metric learning and/or conditional random fields (CRF) could be of a great help, but I have not practical experience with them.

Does anyone have already encounter a similar problem?

Any suggestion or literature on this topic?
Conditional Random Fields (CRFs) can be used for segmenting/labeling sequential problems. Try CRF++: Yet Another CRF toolkit,  a simple, customizable, and open source implementation of Conditional Random Fields (CRFs) 

You can label and create a tagged training corpus and use CRF++ 

You also need to create a feature template

Refer : http://taku910.github.io/crfpp/ for more details. 

Check the example from data for CoNLL shared task (PoS tagging).