Why lattice.shortest path slower than lattice.get_tot_scores ?

[tcourat]

Hi,

I am currently working on a project that uses WFST.

At some point, this involves computing a score corresponding to the probability of the shortest path in a lattice. This lattice can be constructed from either one word or several words.

When there is one word, I know that the shortest path will correspond to that particular word, so I just need the score, and hence call lattice.get_tot_scores . However, when several words are involved, my idea was that I can merge some computations when the words have a common prefixes by deriving the lattice from the union of the FSA of each word, instead of constructing one separate lattice per word. But in this case, I need to know what word correspond to the shortest_path that gives the best score.

The issue is that from my experiments, calling lattice.shortest_path (to get score+labels corresponding to the word) takes more time that calling lattice.get_tot_scores. I'd naively though that getting the best score would require to know the best path too, so the times should be similar.

[danpovey]

shortest_path requires keeping backpointers and following them, which requires extra bookkeeping and iterations. Arguably it shouldn't be that many times slower than tot_score, but it should be slower. It would require some debugging or dumping timing info to figure out what about the algorithm is slow.

[tcourat]

From what I see, it is ~20-30% slower on my examples. Is it within expectations ?