Question regarding OpBuilder: does it allow for efficient merging/splitting of Fsts?

[bzm3r]

Does OpBuilder allow for modification of an existing Fst? For example, if I have two lexicographically disjoint Fsts, can they be merged more efficiently using functionality OpBuilder builder provides, compared to simply building a new Fst from scratch?

[bzm3r]

I think I just answered my own question based on something I ran into in the docs under "Quirks":

Creating a set or a map requires inserting keys in lexicographic order. Often, keys are not already sorted, which can make constructing large sets or maps tricky. One way to do it is to sort pieces of the data and build a set/map for each piece. This can be parallelized trivially. Once done, they can be merged together into one big set/map if desired. A somewhat simplistic example of this procedure can be seen in fst-bin/src/merge.rs from the root of this crate’s repository.

I think the answer is "yes"?

https://github.com/BurntSushi/fst/blob/master/fst-bin/src/merge.rs#L263-L273

I wonder if it might be useful to provide APIs that easily allow for merging of disjoint FSTs, or allow for splitting of existing FSTs. Probably not, but it would be worthwhile at least to further highlight in the documentation that this is possible using OpBuilder, rather than a somewhat passing reference under Quirks?

[BurntSushi]

Does OpBuilder allow for modification of an existing Fst?

No. There are zero cases where an Fst can be mutated in place.

For example, if I have two lexicographically disjoint Fsts, can they be merged more efficiently using functionality OpBuilder builder provides, compared to simply building a new Fst from scratch?

No. OpBuilder only provides efficient implementations of some set operations on an arbitrary number of FSTs. The result of those set operations can be used to produce a new FST. Producing a new FST is done in the exact same way as you would do it by hand: you feed it a lexicographically sorted sequence of keys with corresponding values. Once the sequence is complete, the builder turns the result into an immutable FST. The "magic" is in how the sequence is generated from an arbitrary number of FSTs. That is, it works by using a heap.

I wonder if it might be useful to provide APIs that easily allow for merging of disjoint FSTs,

I don't think so. I don't see the issue with folks using the existing OpBuilder APIs to create streams and then generate FSTs from them. They are completely orthogonal APIs.

Improvements to the docs are always welcome.

[bzm3r]

Thanks @BurntSushi, that makes sense to me!

Producing a new FST is done in the exact same way as you would do it by hand: you feed it a lexicographically sorted sequence of keys with corresponding values.

What's the reason why we can't "re-use" the structure of the two FSTs if they are lexicographically disjoint? Due to the lexicographic disjointed-ness, we can still use the technique of "freezing" the preceding FST while connecting in the succeeding FST?

[BurntSushi]

To be clear, I'm assuming here that "lexicographically disjoint" means that given fst1 and fst2, they are lexicographically disjoint when the overlap between the intervals of the min and max values of each of fst1 and fst2 is empty.

The answer to your question lies in the construction process. The construction process has state that isn't carried through to the FST. That state, crucially, is a map of the essential characteristics of each state (or some subset of states) in the FST to the ID of that state. When attempting to add a new state, it is first checked whether a state with those characteristics exists, and if so, the state is reused. Otherwise, the new state is added to the map (and possibly kicks out another state). Once the FST is constructed, this map is thrown away.

If you don't have this map, then combining two FSTs won't result in good compression. Just because their keys are lexicographically disjoint doesn't mean they don't share suffixes in common, for example. Your idea really only works, I believe, in the case of tries where the only compression happening is based on shared prefixes. In the case of a trie, if you know there is no shared prefixes at all, then there's no compression you can get. But FSTs do more than that. From my blog post on the topic:

A trie can be thought of as a deterministic acyclic finite state acceptor. Therefore, everything you learned in the previous section on ordered sets applies equally well to them. The only difference between a trie and the FSAs shown in this article is that a trie permits the sharing of prefixes between keys while an FSA permits the sharing of both prefixes and suffixes.

Now, is it theoretically possible to re-design the FST format to include that map or perhaps even provide a way to efficiently re-compute it? Maybe. And if you had that, could you then combine two FSTs more efficiently than just re-building a new FST from a sorted sequence of keys? Maybe? I'm not sure. I wrote this crate 8 years ago, so I'm not terribly immersed in the specific details of the implementation. But I can't think of anything that would make it impossible. (Although it's certainly not something I'm planning on exploring any time soon. You'd at minimum need to convince me that the existing process for combining FSTs is meaningfully slow.)

[bzm3r]

To be clear, I'm assuming here that "lexicographically disjoint" means that given fst1 and fst2, they are lexicographically disjoint when the overlap between the intervals of the min and max values of each of fst1 and fst2 is empty.

Ah, hmm. I might mean something slightly different. Not entirely sure yet, it depends on how I parse your definition. The property I was trying to refer to is: "all the keys in fst1 are lexicographically 'smaller' than all the keys in fst2" (i.e. forall (keyA, keyB): keyA < keyB). Let's call this particular property "fst1 is lexicographically smaller than fst2"?

If minKeyA, maxKeyA is the interval of fstA, and minKeyB, maxKeyB is the interval of fstB, then if fstA is lexicographically smaller than fstB, it does mean that the two intervals are also disjoint (the intersection is empty)...so I think we mean the same thing?

Your idea really only works, I believe, in the case of tries where the only compression happening is based on shared prefixes.

That was my guess initially too! But then I got confused with this little example I played with:

Suppose that we have ($ is the root node, and ! is the final node, while --"a"--> represents a transition associated with value "a"):

fstA: $ --"m"--> x --"o"--> x --"n"--> !

and

fstB: $ --"z"--> x --"o"--> x --"n"--> !

fstA "lexicographically smaller" than fstB, but the keys of both FSTs share a suffix. Still, because fstA is lexicographically smaller, we can treat it as frozen while adding in fstB. The benefit here, compared to rebuilding fst(A+B) (the "merged" FST) from scratch is that we can re-use the construction of fstA (so, "suffixes are re-used as much as possible from the original construction of fstA, while the prefixes are irrelevant")?

So, shared suffixes don't matter, because that's where we are re-computing the FST. The main thing is that we are taking advantage of shared prefixes?

Maybe this can also apply in reverse ("prefixes are re-used as much as possible from the lexicographically larger FST"), if we imagine the transitions not as uni-directional, but bi-directional? Instead of going from root node to final node, we can also traverse from final to root? (i.e. we reverse the input sequences, so that whatever is the "suffix" is now the "prefix")?

(Although it's certainly not something I'm planning on exploring any time soon. You'd at minimum need to convince me that the existing process for combining FSTs is meaningfully slow.)

Yup, totally fair! Actually, if you thought it was useful, I was going to propose if I could try submitting a PR for it 😅

=== the following is totally optional reading! ===

A slight bit of context: I am a little interested in this because I want to encode a large number of file/directory paths, and frequently update the corresponding FST too (because it's a file index, and files/directories change regularly). Because I am attracted to the idea of using FSTs, I am wondering how I can take advantage of the additional bit of structure in this situation, which is that often times, prefixes are very similar due to the natural hierarchy between keys.

Another way I am considering the same problem is to essentially "omit the prefixes, since we know they are the same". The way I could do this---maybe?---is by using a "collection of FSTs"?

Suppose we have two keys like: "hello/kitty/pet" and another like "hello/puppy/pet".

A "collection of FSTs" would generate three separate strings sequences from the above keys:

0. ["hello", "hello"], (stored in fst0)
1. ["kitty", "puppy"]: (stored in fst2)
2. ["pet", "pet"]: (stored in fst2)

When given a new string such as "sleepy/puppy/pet", it would split input into 3 parts, and test each part with the corresponding fst. If all pass, then the string is in the "collection of FSTs".

This idea (significantly?) dilutes the potential for compression-via-redundancy-by-FST because we're breaking larger strings into substrings, and processing each substring in a separate FST. But, if you know for a fact that many of the FSTs will never change (e.g. because most files are added to a particular directory, so they all share the same prefix), then you only have to build some of the FSTs from scratch, which restrict the burden of re-calculating the encoding FST only to those FSTs which do need a change?

It potentially also increases the "lookup/search" speed by allowing parallelization over the collection of FSTs? Finally, I think one could be somewhat judicious in choosing when to break things into separate FSTs, and when not to (for example, if there is a group of path-parts that rarely change, or if there is a large group of path-parts that are all very short strings, we might as well store them all together with other path-parts in a single FST).

[BurntSushi]

Ah, hmm. I might mean something slightly different. Not entirely sure yet, it depends on how I parse your definition. The property I was trying to refer to is: "all the keys in fst1 are lexicographically 'smaller' than all the keys in fst2" (i.e. forall (keyA, keyB): keyA < keyB). Let's call this particular property "fst1 is lexicographically smaller than fst2"?

I believe our formulations are equivalent, but stated a little differently. Technically, you might need to preface your formulation with, "without loss of generality" to be equivalent to mine, but otherwise I think they are? If not, perhaps there's a counter-example lurking somewhere.

That was my guess initially too! But then I got confused with this little example I played with:

Suppose that we have ($ is the root node, and ! is the final node, while --"a"--> represents a transition associated with value "a"):

fstA: $ --"m"--> x --"o"--> x --"n"--> !

and

fstB: $ --"z"--> x --"o"--> x --"n"--> !

fstA "lexicographically smaller" than fstB, but the keys of both FSTs share a suffix. Still, because fstA is lexicographically smaller, we can treat it as frozen while adding in fstB. The benefit here, compared to rebuilding fst(A+B) (the "merged" FST) from scratch is that we can re-use the construction of fstA (so, "suffixes are re-used as much as possible from the original construction of fstA, while the prefixes are irrelevant")?

So, shared suffixes don't matter, because that's where we are re-computing the FST. The main thing is that we are taking advantage of shared prefixes?

mon and zon share the same suffix though. So when doing fst(A + B), you'd need a way for those two entries to share the same suffix. The only way to do that is with the state used by the FST construction process that I discussed in my previous comment.

It potentially also increases the "lookup/search" speed by allowing parallelization over the collection of FSTs?

Yes, this is how Lucene (and consequently, Elasticsearch/Opensearch/SOLR) work. They don't work by aggressively merging FSTs (and associated index structures) into a single thing. They balance the number of FSTs through a merging process. fst-bin implements a simplistic version of this.