bug(web): predictive-text should support true keystroke correction
- Dominant language
- Pascal
- Stars
- 534
- Forks
- 143
- Avg merge
- 2d 10h
- Merged PRs (30d)
- 113
Description
Thus far, the predictive-text engine has always performed text-correction based on the transforms that result when applying the actually-typed keys and keys near it to the actual, current context at the time of the keystroke. This has worked "well enough" for quite a while, but for complex keyboards, it's possible for corrections to fail for certain cases where a _previous_ keystroke should have been corrected.
**_Note_**: the amount of work needed to implement this may be large enough to merit treatment as an epic - say, `epic/true-correction`.
Keyman keyboard rules can trigger considerable changes in the context based on very specific, pre-existing contexts at the time of the keystroke. LDML keyboards support similar behavior in addition to reorder rules that may also notably rearrange the context's contents.
Should the a previous keystroke intended by the user not be the true keystroke and correspond to a complex context change making multiple character edits to the current word in the context, that correction may be out of range for the current correction-search process and thus not be made available to users.
----
Naturally, the biggest and most obvious obstacle to supporting true keystroke correction is that cross-thread communication is costly when it comes to predictive-text, and we have a limited span of time in which to generate predictions. To be explicit - the worker should absolutely **_not_** poll the Web engine for each possible correction.
Of course, it's also cost-prohibitive to actually compute every possible relevant context. Even if we filter down to only calculating contexts for the 8 most likely keys for each input, we have exponential growth in the number of contexts to consider as keystroke count rises. 8 ^ 3 = 2 ^ 9 = 512 possible contexts after just 3 keystrokes. After 10 keystrokes, we hit 2 ^ 30 ~= 1 billion possibilities, which is simply unfeasible.
However... how many of these cases would even be relevant? Some considerations and ideas:
- The worker can tell the web engine that certain paths / contexts are irrelevant - that no words exist based on that context or one near it.
- In essence, the worker can help 'prune' cached engine contexts.
- Branching is generally higher when there are few characters in the word; branching generally decreases dramatically as words lengthen.
- Trimming should already start to kick in by the time we reach 8^3 = 512 possible paths, as a great number of those will be either invalid or involve too many unlikely keystrokes.
- After that point, paths generally don't branch too heavily - and successfully going deeper on the most likely paths should help further prune remaining unlikely paths.
- When a wordbreaking boundary is reached, cached engine contexts can be cleared.
- Two recent PRs introduced a set of methods to the predictive-text worker that could help to communicate such data cross-thread more efficiently:
- #14581
- #14592
- The idea would be to recognize "similar" contexts and "similar" editing patterns made, on a per-keystroke basis.
- For cases that have specialized rules, we could note the specific contexts and edits as special cases
- Common-case keystroke rules would act generally to "most" contexts and would be specified as a "default" case for each key.
- The worker only needs to know about what transforms currently apply, for the current keystroke, based on each reasonably-likely context.
- For less likely paths, we can still fall back to our existing behavior for each key - just use the effects from the current context
- Or maybe even just the most common effect, per key, from currently-considered contexts?
- We could even model the latter idea by replacing the context text with sentinel chars so that no context-dependent rules apply.
For the current "best correction paths" at any point in time (when the most likely paths are few), we _may_ also want to include a one keystroke "look-ahead" operation to determine if any following (but currently "missing" / "deleted") keys would trigger a change in existing context that better matches words in the lexical model.
Further things that may help:
- Knowing the largest context range a rule in the keyboard might require (or a reorder may operate upon) would help restrict the amount of memory needed to model these corrections.
- Additionally, knowing maximum difference in before-and-after length for rules may prove useful - if a rule considers 3 context chars but only emits a single-char output, the resulting shift in length is relevant.
Contributor guide
Assessment
This issue has not been assessed yet.