Use CRF for classifying/labeling.

http://crf.sourceforge.net/

Its extremely well written, easy to define features etc. Reasonably good support too.