search

facebookresearch / gtn_applications

Applications using the GTN library and code to reproduce experiments in "Differentiable Weighted Finite-State Transducers"
MIT License
80 stars 7 forks source link

Dumb question for arc_sort func #16

Closed yuekaizhang closed 3 years ago

yuekaizhang commented 3 years ago

When should we set the arc_sort(true) ? For example, in https://github.com/facebookresearch/gtn_applications/blob/eb1cb83dda3d3887f980dbd6b697c2c2b6fd1d45/transducer.py#L265 arc_sort was given parameter True. If my understanding is correct, for FSA target, arc_sort(true) and arc_sort(false) would give the exact same result? How do we decide to set it true or false? (When we prefer sort it in olable and when ilabel? )

vineelpratap commented 3 years ago

Hi, It is done for doing compose operation more efficiently. Note that compose operation involves matching arcs of lhs graph with rhs graph such that output label of lhs is same as input label of rhs and having the labels sorted sorted will help in doing this operation in O(log N) time instead of O(N) for each arc. See https://github.com/facebookresearch/gtn/blob/master/gtn/functions/compose.cpp for implementation details. DoublySortedMatcher will be used if both lhs and rhs are sorted in particular order mentioned below.

For performing compose(A, B), call A.arc_sort(True) and A.arc_sort(False) for doing it efficiently.