search

kylebgorman / pynini

Read-only mirror of Pynini
http://pynini.opengrm.org
Apache License 2.0
120 stars 26 forks source link

best way to calculate shortest distance final score? #26

Closed lxkain closed 4 years ago

lxkain commented 4 years ago

Hello,

if I know that the final state of my FST has ID=0, I can do float(ni.shortestdistance(out)[0]) + float(out.final(0)) to find the total score. Is there a better general solution, that doesn't rely on the assumption that the final state ID=0, and that also doesn't have to use shortestdistance if I already have a strictly left-to-right FST as determined by shortestpath?

kylebgorman commented 4 years ago

I would just get the FST start state using the .start method:

def single_shortest_distance(fst: pywrapfst.Fst) -> float:
     start = fst.start()
     assert start != pywrapfst.NO_STATE_ID, "no start state found"
     return float(pywrapfst.shortestdistance(fst, reverse=True)[start])

If you run this in reverse (as I'm doing above) then you don't need to include the final weight of the initial state, I believe, though you're welcome to check me on that.

I added that assertion because composition, by default, connects (i.e., trims) the states so composition failure produces an FST with no states, and an FST with no states has a start state of pywrapfst.NO_STATE_ID. (You can also check the number of states but not all FST types know how many states they have; in this case it would be a type-checking error because pywrapfst.Fst doesn't have a num_states method.)

At the C++ template level there is generic function to do what you have in mind:

http://www.openfst.org/doxygen/fst/html/shortest-distance_8h_source.html#l00325

(Note the bit that starts at line 340.)

K

On Wed, Mar 25, 2020 at 12:40 PM Alexander Kain notifications@github.com wrote:

Hello,

if I know that the final state of my FST has ID=0, I can do float(ni.shortestdistance(out)[0])

  • float(out.final(0)) to find the total score. Is there a better general solution, that doesn't rely on the assumption that the final state ID=0, and that also doesn't have to use shortestdistance if I already have a strictly left-to-right FST as determined by shortestpath?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/kylebgorman/pynini/issues/26, or unsubscribe https://github.com/notifications/unsubscribe-auth/AABG4OPBPLS3XOLMF7F62VDRJIXYLANCNFSM4LTS2ISA .

lxkain commented 4 years ago

Thank you so much! That seems to be a good approach.