How do I represent a hidden markov model in data structure?
With 29 states and 841 possible transitions to track whilst reading a file with 2000 entries (word, tag), then you should not be experiencing a speed problem when using a dictionary of dictionaries.

Assuming your data structure as described called transition_counts, and receiving data in pairs, (this_pos, next_pos) then running 2000 times:

transition_counts[this_pos][next_pos] += 1


takes only a fraction of a second. This is similar for code that calculates $p(POS_{t+1}|POS_t)$:

total_from_pos_t =  sum(transition_counts[pos_t].values())
prob_pos_tplus_one = transition_counts[pos_t][pos_tplus_one] / total_from_pos_t  


This is very fast. Your problem is not with the representation.