We will explain the Hidden Markov Model as it is used in algebraic statistics and its connection to Google's "Did you mean"-feature. This turns out to be equivalent to the evaluation of a tropical polynomial which can be done efficiently by Minkowski decomposition of a newton polytope.