I am trying to implement a trigram HMM tagger for a language that has over 1000 tags. In my training data I have 459 tags. Now if we consider that states of the HMM are all possible bigrams of tags, that would leave us with $459^2$ states and $(459^2)^2$ transitions between them, which would require a massive amount of memory.
Are there any workarounds around this? What I thought of is considering only bigrams seen in the data, but it is still a lot of memory.
Actually, there are only $459^3$ transitions, not $459^4$ transitions. That helps a lot. This is because a state is a pair $(t,u)$ where $t,u$ are tags, and a transition has the form $(t,u)\to (u,v)$. In particular, you can't have $(t,u) \to (w,x)$ where $u \ne w$ (given that the state represents the last two tags). So, there are at most $459^3$ transitions, or at most about 100 million transitions. You should be able to store that a graph with 100 million edges in memory without too much difficulty.
My guess would be that not all transitions actually occur in the training set, so it's possible this might be a sparse graph, and that might reduce the graph size further.
