3 ms·

Nitpick: as I understand them, transducers translate strings to strings, not strings to integers. There is a ~17 lines long algorithm for building FSM's from l

by mci 10y ago

Nitpick: as I understand them, transducers translate strings to strings, not strings to integers. There is a ~17 lines long algorithm for building FSM's from lexicographically ordered strings: http://sun.aei.polsl.pl/~mciura/publikacje/lexicon.pdf http://sun.aei.polsl.pl/~mciura/publikacje/lexicon.pdf (Figure 8). Extending it to map the strings to integers, also in lexicographic order, is an exercise for the reader. Full disclosure: I am a co-author of that paper.

burntsushi 10y ago
There's no typed restriction on what "transducer" means. Having a second tape in your FSM is enough. e.g., In the formal definition of an FSM, in addition to the input alphabet Σ, you also have an output alphabet Γ. FSTs are commonly seen in morphological analysis (e.g., your paper?) and in those cases it's probably string-to-string, but FSTs have other use cases as well. :-) Lucene, for example, uses a string->int FST as part of its inverted index (where the strings are terms and the ints are ~docids, IIRC).
burntsushi 10y ago
I skimmed your paper. It's good stuff! The implementation in the OP is loosely based off this paper: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.3698&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.... --- The algorithm in your paper is roughly similar, but the key difference is the observation that the output tape of the transducer can itself be compressed---so long as your outputs follow a certain algebra.[1] There are two other critical pieces to a non-toy implementation that most papers don't cover, particularly with respect to very large sets (billions of entries): 1. Representation of the FST itself. To squeeze the most juice, you ideally want most states to occupy no more than 1 byte. Anything by Jan Daciuk[2] in this space is excellent. 2. The hash map used during construction of the FST is universally glossed over, but it is absolutely critical. A standard hash map will store all states, which means you'll need to fit your entire FST into memory. Throwing away the hash map means that your FST isn't compressed very well. So you need something in between that's bounded and tuned to give the best bang for your buck. All of these considerations make FSTs like these non-trivial to implement. :-) [1] - https://docs.rs/fst/0.1.38/fst/raw/struct.Output.html https://docs.rs/fst/0.1.38/fst/raw/struct.Output.html [2] - http://www.cs.put.poznan.pl/dweiss/site/publications/download/fsacomp.pdf http://www.cs.put.poznan.pl/dweiss/site/publications/downloa...

by mci 10y ago

burntsushi 10y ago

There's no typed restriction on what "transducer" means. Having a second tape in your FSM is enough. e.g., In the formal definition of an FSM, in addition to the input alphabet Σ, you also have an output alphabet Γ. FSTs are commonly seen in morphological analysis (e.g., your paper?) and in those cases it's probably string-to-string, but FSTs have other use cases as well. :-) Lucene, for example, uses a string->int FST as part of its inverted index (where the strings are terms and the ints are ~docids, IIRC).

burntsushi 10y ago

I skimmed your paper. It's good stuff! The implementation in the OP is loosely based off this paper: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.3698&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.... --- The algorithm in your paper is roughly similar, but the key difference is the observation that the output tape of the transducer can itself be compressed---so long as your outputs follow a certain algebra.[1] There are two other critical pieces to a non-toy implementation that most papers don't cover, particularly with respect to very large sets (billions of entries): 1. Representation of the FST itself. To squeeze the most juice, you ideally want most states to occupy no more than 1 byte. Anything by Jan Daciuk[2] in this space is excellent. 2. The hash map used during construction of the FST is universally glossed over, but it is absolutely critical. A standard hash map will store all states, which means you'll need to fit your entire FST into memory. Throwing away the hash map means that your FST isn't compressed very well. So you need something in between that's bounded and tuned to give the best bang for your buck. All of these considerations make FSTs like these non-trivial to implement. :-) [1] - https://docs.rs/fst/0.1.38/fst/raw/struct.Output.html https://docs.rs/fst/0.1.38/fst/raw/struct.Output.html [2] - http://www.cs.put.poznan.pl/dweiss/site/publications/download/fsacomp.pdf http://www.cs.put.poznan.pl/dweiss/site/publications/downloa...