Abstract: In this paper, a map matching algorithm based on the ideal Hidden Markov Model (HMM)was described, and a novel method to calculate the state transition probability was proposed, which meets the strict requirement of the Viterbi algorithm. The algorithm was tested on real datasets. The results demonstrated that in spite of its simplicity, the algorithm manages to achieve satisfying performance even under sparse and noisy road network data.