feat(developer, web): Improve predictive text load performance and file size with binary string Trie model encoding and lazy-initialization 💾

Related issue: #7006
Related community post: https://community.software.sil.org/t/text-suggestion-not-working-in-some-cases/6490
- There are probably others, but this is the one I could most easily find.

## The Short Version

Rather than just shortening the property names of the compiled `Trie` data structure, I propose that we instead radically change how Tries are compiled and loaded at runtime.

Notable aspects:
1. Tries could be compiled into a single, giant string with all data encoded within it. This should require minimal startup parsing and JS in-browser compilation costs.
2. At run-time, we could use a lazy decoding strategy to just-in-time decode whatever _part_ of the Trie we need.
3. Once a part is decoded, we can store it instead of the original encoded form, progressively decoding the structure as needed.

A later section - **Proposal** - will provide details that could accomplish this goal.

## History

The most relevant excerpt from the [linked Community post](https://community.software.sil.org/t/text-suggestion-not-working-in-some-cases/6490):
> The lexical model contains about 160 000 words and it loads in 10-12 seconds.

That is _certainly_ not an ideal start-up time. It likely results from the process of parsing and compiling the JS comprising a lexical model. For comparison, let's consider our baseline `nrc.en.mtnt` model, which features 24249 words:


This was profiled on my development laptop, which is likely much faster than a phone - and it took 78.2 ms just to compile the model script's file when loaded... let alone any post-processing. It's not 100% clear if it was _just_ compile time, or if that also includes _parse_ time, but either way - it's not the fastest thing out there.

After a bit of digging, I believe the post's model to be `dotland.hy.armenian` within the lexical-models repo - it has a commit 2 years ago labeled "[Removed rare words to reduce load time](https://github.com/keymanapp/lexical-models/commit/781a206d2760b770ea2dd7af77fff1f878cc6282)", and the timeline matches reasonably. History shows that the initial submission had 166835 words in total - so, "approximately 160000 words". Using the _current_ version of that model on the same machine...


I also found part of where one of the (anonymous) blocks lines up to...


The figure's not an exact match, but I figure "close enough" applies here - 107.8 ms vs 108.1 ms.

Restoring the model to its [original submission](https://github.com/keymanapp/lexical-models/commit/6742b2da656b136d26c4f961b37ae520f521852c)...



It's quite clear that simply parsing and loading the model, given its present structure, requires a lot of start-up time.

## Proposal

After analysis of the data types representing a compiled Trie, here are the details of one potential design for lazy-init friendly encoding I've identified.

**Principle 0**: Anything fixed-length for an object should be stored before anything variable-length. I'm pretty sure that's generally implied for tasks and proposals like this, but I figured I'd make it explicit here.

**Principle 1**: Monolithic string encoding. All data types will be encoded within a string in one form or another.

Numbers will be encoded via code units. Each character in JS may represent 2 bytes, representing 65536 possible values. 2 chars thus gives 4*10^9 possible values, etc. As we don't aim to support models anywhere near 4 GB (or greater) in size, a fixed field of 2 characters should be enough to represent large numbers within the encoded string.

**Principle 2**: Each encoded object is prefixed with a char-length header whose value matches the length of the remainder of its encoded form. This makes it easy to extract the object's encoding string (via `substring`) and find the starting index of its next sibling.

### Entry

This is enough to talk about the lowest-level object: a lexical `Entry`:

https://github.com/keymanapp/keyman/blob/f0c8ae9eddbfd2978e27b4a9e15d24a72dd41ff2/common/models/templates/src/trie-model.ts#L355-L364

Proposed encoding components:
1. size prefix (2 chars)
- Probably "overkill" here, but you never know.
- Is consistent with the "size prefix" from the other encoding patterns.
2. `weight` (2 chars)
3. ~~key length (1 char) - the length of the `key` string.~~
4. content length (1 char) - the length of the `content` string.
- ~~I feel like, in general, these _should_ always match... but "better safe than sorry." It's also not a high cost penalty, so... 🤷~~
5. ~~`key` - a raw dump of the existing `key` string. No null-termination needed.~~
6. `content` - a raw dump of the existing `content` string. No null-termination needed.

(A later iteration: `key`s are no longer included within the encoded string - they can be rebuilt later.)

For the two higher-level objects, there's one extra detail worth noting:

https://github.com/keymanapp/keyman/blob/f0c8ae9eddbfd2978e27b4a9e15d24a72dd41ff2/common/models/templates/src/trie-model.ts#L336-L338

https://github.com/keymanapp/keyman/blob/f0c8ae9eddbfd2978e27b4a9e15d24a72dd41ff2/common/models/templates/src/trie-model.ts#L349-L351

Both objects share a couple of common, important properties. Also, for `type`, those are the only two valid properties.

**Principle 3**: To facilitate lazy initialization, we'll start both objects with a common header structure - first, the "size prefix", then a flag for the object's type. These two values are enough to pass the remainder of the encoded object to the "correct" method for string decoding.
- If we instead put the object-type flag first, we _could_ allow variation between the "size prefix" width allotted to the two objects. I don't suggest this (for consistency reasons), but I thought it worth noting as an alternative.

### Leaf

https://github.com/keymanapp/keyman/blob/f0c8ae9eddbfd2978e27b4a9e15d24a72dd41ff2/common/models/templates/src/trie-model.ts#L348-L353

Proposed encoding components:
1. size prefix (2 chars)
- Probably "overkill" here, but you never know.
- Is consistent with the "size prefix" from the other encoding patterns.
2. `weight` (2 chars)
3. `type` (1 char) - `L` (to indicate 'leaf')
4. entries count (1 char) - the length of the `entries` array (when decoded).
- We should never surpass 100 entries here, let alone ~~65536~~ 0x7FFF (32,767) of them.
- Later revision: `type` and `count` are overlaid, with `type` using the high bit.
5. `entries` - the concatenation of the encoded form for all `Entry` objects for the array.

### InternalNode

https://github.com/keymanapp/keyman/blob/f0c8ae9eddbfd2978e27b4a9e15d24a72dd41ff2/common/models/templates/src/trie-model.ts#L331-L347

Proposed encoding components:
1. size prefix (2 chars)
- The highest-level internal nodes could certainly reach a length greater than would be representable by a single char.
2. `weight` (2 chars)
3. `type` (1 char) - `I` (to indicate 'internal')
4. values count (1 char) - the length of the `values` array / string.
- As the entries are also the keys of the `children` Map, it also suffices to indicate the number of objects in `children`.
- Later revision: `type` and `count` are overlaid, with `type` using the high bit.
- `count` should never come close to approaching 0x7fff (that is, 32,767)
5. `values` (string) - the concatenation of each code unit in the decoded `values` array, in original order.
6. `children` - the concatenation of the encoded form for all `InternalNode` / `Leaf` child `Node`s, in the same order as their keys appear within `values`.

**Principle 4**: Upon visiting an `InternalNode`, the object is decoded, but _not_ its `children`. Children are only decoded when the field is externally accessed.

To accomplish this, the compiled Trie would need to include an internal class that provides `children` as a read-only property calculated at run-time. The first access would decode each child, then replace the encoded form with the decoded result of each.

**Principle 5**: To prevent escape-bloat (due to `\` and `"` escaping effects), `JSON.stringify` - to "escape" strings - will only be applied _once_ - for the full string representing the `Trie`'s root `InternalNode`.

This string always gets decoded upon model init, but only for the upper layer; lower layers get decoded as `predict` and/or the `traverseFromRoot` object seeks access to them.
- We _could_ always setup a background lazy-inflation queue to decode the lexicon in the background when no predictions are active, rather than waiting for the first prediction attempt to access a node to decode it.
- Use of `Promise`s + `async`/`await` should allow the process to "background" itself when a prediction request comes through.
- Though, a resolution to #3580 would likely use a similar trick, which would (naively) allow the queue to make progress again.
- There should be a way to handle this caveat, though - especially if _this_ proposal either happens first or simultaneously with that one.
- Fulfilling lazy-initialization at prediction / correction time does come with a cost to that process for each "first pass", after all.

### Initialization

So, what would the initialization / model-load process impacts be?

There would need to be some embedded JS code to facilitate decoding of the new Trie format to the original, existing Trie format within the model. This is necessary to maintain backward-compatibility with older versions of Keyman, after all. However, for any substantial model, the cost of this code would easily be paid for by the reduction of space needed for property names in the JSON format (as noted by #7006). We could probably even _minify_ the decompression methods and class for even greater savings.

After that... the wordlist-Trie itself would simply be one large, monolithic JS string. There would be no need for JSON-related parsing & compilation - it'd be "just a string", something that should be far simpler and less complicated to load on startup.

We'd then need to run a single, first pass of the decompressor on the root Node to initialize the model. This pass would stop _at_ the root Node, not even decompressing the first layer's children. Again, this is far superior to parsing a mass of nested JSON objects for the whole Trie.

### Implementation

There is little reason to believe we can't just re-use the existing Trie compiler as the first pass for the new Trie encoding format. After all, all specifications above are based upon the _existing_ format; let's just re-use that and do a post-processing run on it to obtain the encoded string needed to represent the compiled model.