FINITE-STATE TRANSDUCER

fragments.fst

358,197,569 bytes5,782,731 fragments264,040,981 statesbuilt 24 Nov 2025

I pulled 5,782,731 dialogue fragments out of the Internet Archive subtitle database that feeds the Loom of the Abundance, and built them into one weighted finite-state transducer with the Rust fstcrate. That produced 358,197,569 bytes nobody had ever looked inside, me included, until I wrote a probe that walks it. Every number below I measured off that real file, and the instrument in the middle of the page is a working transducer your own browser builds out of 40,181 of those fragments carrying their real weights, one arc per keystroke.

I had expected compression, because close to six million short lines of transcribed speech share so much of their beginnings and their endings that the automaton ought to fold them into something far smaller than the text, and what it does instead is very nearly refuse. Minimisation removes7.85% of the trie, 98.91% of the finished states have exactly one way out and the index lands at 96.38% the size of the plain text it indexes, while gzip of that same text gets to 33.65%. What the shape buys instead is that a lookup costs one step per byte of your query and never once asks how many fragments there are, which is the part you can feel in your fingers.

walk it

01 the file

Three files, and one of them is 277 bytes.

There is no schema in here, no readable header block, no index of the index. The first eight bytes are 03 00 00 00 00 00 00 00, the format version the fst crate writes, eight more carry a type tag that is entirely zero, and then it is states until the last twenty bytes, which hold the address of the root, a CRC32 and the one number the file states plainly about itself: 5,782,731 keys. Everything else I know about the contents I know because I traversed them.

file	bytes	what it is
fragments.fst	358,197,569	the automaton, and the only file the search actually opens
fragments.terms.txt.gz	125,077,196	gzip of the same 5,782,731 lines, kept for reference
fragments_metadata.json	277	twelve lines of JSON, printed whole below
total	483,275,042	for a source text of 371,646,864 bytes

{
  "indices": {
    "fragments": {
      "total_terms": 5782731,
      "index_type": "fragments",
      "created_at": "2025-11-24T18:28:08.122384+00:00",
      "source_file": "fragments.txt"
    }
  },
  "total_indices": 1,
  "created_at": "2025-11-24T18:28:08.122374+00:00"
}

fragments_metadata.json, entire: 277 bytes to describe 483,275,042 of them. It records how many keys went in, from which file and when, and nothing whatever about the shape of what came out.

SELECT DISTINCT phrase FROM subtitles
WHERE phrase IS NOT NULL AND phrase != "" ORDER BY phrase

The fragments come out of the subtitle database in one statement.export_fragments_for_fst.py, line 32

let mut builder = MapBuilder::memory();
for (fragment, weight) in weighted_entries {
    builder.insert(fragment, weight)?;
}

// Serialize FST to bytes and write to disk
let map = builder.into_map();
let data = map.as_fst().as_bytes();
fs::write(output_dir.join(format!("{}.fst", name)), data)?;

And the whole index is built by these lines, which take the sorted pairs one at a time and write out all 358,197,569 bytes of it.rust-services/src/bin/build_fragment_fst.rs, lines 275–283

The weight attached to each key is not a count of that fragment but a count of how often it occurs as a word-boundary prefix across the whole corpus, lower-cased, so"the man walked" contributes to "the", "the man" and"the man walked" alike. That is why the heaviest weight in the file, 912,430, sits on two keys at once, A and a, while the mean weight is 3.33, and why not one of the 5,782,731 keys carries a weight of zero.build_fragment_fst.rs, lines 15 and 152–180

02 the walk

Type, and every character is exactly one transition.

Your browser is building its own minimal transducer out of 40,181 real fragments and their real weights, in three stages: lay down the trie, push the outputs back towards the root, then merge every pair of states that have the same future. That lands on the same automaton the Rust crate's MapBuilder produces, by a slower road. Mine comes out at 48,664 states and 83,746 transitions. Each keystroke below takes one arc, so a walk that gets through costs exactly as many states as you typed characters, while the count of fragments still reachable falls away underneath it.

building the automaton…

query

the fan ahead

0states walkedone for every byte the walk consumes

—fragments still reachablecompletions of this exact prefix

The weights it hands back are real, taken key by key out of the 358,197,569-byte file with zero misses, but they are prefix frequencies over all 5,782,731 fragments, not counts inside this sample of 40,181. So walking a lot of lands on 42,985 while only 42,317 fragments in the whole index actually begin a lot of , and far fewer than that are short enough to be in here.

03 a whole automaton

38 fragments, drawn entire.

The browser build is far too big to draw and the real index is absurd, so here is one small enough to put on the page complete. I took every key in the index that begins a , ends of and runs to eight or nine characters, which comes to 38 fragments. Their trie is 230 states; minimised it is 55 states and 91 transitions. The fan opens after a and closes again into the single tail that all 38 walk through. Hover or focus a box and it names the real prefixes that arrive there.

drawing…

state, with its id in my constructionarc that emits part of the weightarc that emits nothing

One of the 38 is a the of, weight 1, almost certainly a mistranscription, and the automaton carries it as faithfully as it carries a lot of at 42,985. Nothing in the build looks at whether a fragment is a sentence, only at whether it sorts.

04 what it cost

The index is 96.38% the size of the text it indexes.

Decompressing fragments.terms.txt.gz gives a file byte-for-byte identical to the fragments.txt that went in, so the three bars below measure the same 5,782,731 fragments three ways. Shared prefixes and shared suffixes bought a little over three and a half percent against raw text, while gzip, which knows nothing about automata, bought two thirds.

fragments.txt371,646,864 100%

fragments.fst358,197,569 96.38%

the same text, gzipped125,077,196 33.65%

minimisation

7.85%

The keys total 365,864,133 bytes and the longest common prefixes between neighbouring sorted keys total 79,328,419, so a plain trie over them needs 286,535,715 states. The real automaton has 264,040,981. Merging every suffix that spells and pays the same removed 22,494,734 states, and that is all it removed.

states with one way out

98.91%

261,167,586 of the 264,040,981 states have exactly one outgoing transition. 1,927,875 have two, which is another 0.73%. Exactly one state in the whole file has none, and the busiest has 122. Almost all of this object is corridor.

where fragments stop resembling each other

13.72bytes

Mean longest common prefix between adjacent fragments in sort order, against a mean fragment length of 63.27 bytes. Half of all adjacent pairs share 12 bytes or fewer. Two neighbouring lines of dialogue agree for about two words and then go their own way, which is exactly the corpus refusing to share.

what a byte of the file holds

1.33bytes / arc

358,197,569 bytes over 269,611,370 transitions, or 61.94 bytes per key against a mean raw key of 63.27, with the weights carried along the arcs on top of that. The file is 2.86 times the size of the gzip, and unlike the gzip you can jump into the middle of it.

One step per byte, whoever is asking

Five queries walked through the real index, every bar the true out-degree of a state the walk reaches, measured on the 358,197,569-byte file itself. They spike while the corpus is still deciding and collapse where it has already committed: two states in a row along because have exactly one way out, because all 13,227 fragments that reach becau go on to spell se and not one of them stops there. What none of it depends on is how many fragments are waiting at the far end: a lot of has 42,317 of them and costs nine steps, while i think has 239 and costs eight, so the difference between those two walks is the length of what I typed rather than the size of what I typed it into.

a␣lot␣of␣42,317 fragments begin with it

41a64␣8l18o7t44␣13o5f49␣

because␣12,928 fragments begin with it

24b28e4c6a1u1s5e53␣

you␣know␣9,181 fragments begin with it

13y14o13u52␣4k2n2o5w52␣

thank␣you␣4,165 fragments begin with it

25t13h9a8n8k38␣2y1o6u49␣

i␣think␣239 fragments begin with it

27i33␣5t3h1i1n1k19␣

Carrying the weights costs states too. The same 40,181 fragments built as a plain unweighted automaton need 43,799 states and 77,255 transitions; as a transducer they need 48,664 and 83,746, which is 4,865 states and 6,491 transitions more. Two suffixes that spell the same are not the same suffix if they hand back different numbers.

05 apparatus

What I measured, what I sampled and where the documentation is wrong.

†

The two automata

The index on disk has 264,040,981 states and I never shipped a byte of it here. The one you typed into has 48,664, built in your browser from 40,181 fragments, which is 0.69% of the index. Its trie was 184,870 states and merging took 136,206 of them away, 73.7%, because a sample this small and this short shares far more of itself than the whole corpus does, where minimisation only ever got 7.85%. The corridors go the same way: 65.7% of the browser's states have one way out, against 98.91% on disk.

‡

Whose construction

The browser builds the canonical minimal subsequential transducer by trie, then output-push, then suffix-merge, which is the same object MapBuilderproduces. That the two agree is a property of the canonical form rather than something I measured, since I never built this sample with the crate to compare it state for state. It is my JavaScript in any case, not fst 0.4.7 compiled to wasm, so every state id you see is mine. I ran the identical code offline under Node before shipping it and got the same 48,664 states and 83,746 transitions, then ran it again with every output forced to zero for the unweighted figures above, so none of these counts is an artefact of a single run.

The sampling rule, which is a choice about people

The sample is every key in the index that is 6 to 14 bytes long and made only of lower-case letters, spaces and apostrophes: 40,181 fragments, 439,863 characters. The corpus is transcribed speech, and a good deal of it is public meetings: 1,512 fragments begin Council , 823 begin Supervisor , 360 begin Councilman and 7,438 begin Thank you , which in a council chamber is mostly followed by somebody's name. Requiring lower-case throws every capitalised proper noun out automatically, which is why I chose that rule rather than a length cut on its own. Nothing longer than 14 characters is reproduced anywhere on this page, which holds every fragment here to five short words at the outside.

Where my own documentation is wrong

FRAGMENT_AUTOCOMPLETE_README.md describes the index as Compressed FST structure, efficient storage with O(log n) prefix lookup, very fast, and says the search Continues until 1000 results found or no more words to remove. The file is 96.38% the size of the text and 2.86 times the size of its own gzip, so compressed is generous. The prefix walk costs one step per byte of the query and does not depend on n at all, so O(log n) is the wrong shape entirely. And the code says const MAX_RESULTS: usize = 5000;. I am leaving the discrepancy on the page rather than quietly correcting either side.FRAGMENT_AUTOCOMPLETE_README.md lines 67 and 192–193, against fragment_autocomplete.rs line 440

‖

What the fragments are

They are the phrase column of an SQLite table, described in the source project as The spoken dialogue text, extracted by a tool that pulls dialogue phrases with timestamps from Internet Archive movies within a specified date range. The flat file carries no timestamps, no titles and no urls, only the distinct phrases in sorted order, which is all the index ever sees. 212,050 of them are a strict prefix of another fragment. The longest is 606 characters, 98.65% are 100 or shorter and only 1.04% are 10 or shorter. What the Loom of the Abundance does with them afterwards is that piece's subject, not this one's.database.py line 200, README.md lines 3 and 93

the first character of every fragment, by script

5,673,740ASCII letter or digit
65,356ASCII punctuation or symbol
17,431Arabic
10,839other
7,693CJK
4,016accented Latin
1,864Cyrillic
1,781Armenian
7Hangul
3Hebrew
1Thai

Which is why the root of the real automaton has 122 outgoing bytes rather than the couple of dozen you would guess. The root of the one in your browser has 26, one for each lower-case letter, because every fragment the sampling rule lets through starts with one of those. The buckets come from a classifier I wrote rather than from a Unicode standard, and that shows: the ASCII, Arabic, Cyrillic, Armenian, Hangul, Hebrew and Thai counts come out identical however I write it, but CJK, accented Latin and other are residuals whose boundaries I chose, and a second classifier written from scratch moved close to ninety fragments between the last two. Those three are the only numbers on this page that turn on a line I drew rather than only on what is in the file.