Hacker News Reader

Weird because POS tagging takes linear time in the number of words.

Anything that uses the standard decoding strategy (Viterbi) is quadratic in the number of "states" (i.e., tags), though, and that easily dominates.

(Nowadays, many people just use greedy---linear in the number of states---decoding because it rarely is much worse.)

That's assuming a lot... there are many, many ways to do part of speech tagging. You could imagine a slow implementation that exhaustively considered every possible POS tagging for an input sequence (would be O(k^N) where k is # of parts of speech)

There's not really that much assumption. Given the fact that good and simple linear time algorithms exist for decades it's very unlikely that they use some ridiculous permutation enumeration algorithm.

Even a Microsoft Research project has a fairly complex reductions implementation of a POS tagger that is blazingly fast and production ready (learning to search interface). [1]

[1]: https://github.com/JohnLangford/vowpal_wabbit/wiki

You could imagine a slow implementation that exhaustively considered every possible POS tagging for an input sequence (would be O(k^N) where k is # of parts of speech)

You could.. if you were crazy. No sane implementation would do that, and POS tagging isn't some brand new thing where people make that kind of mistake.

Reply on news.ycombinator.com