feat(web): improve correction-search handling of complex context changes
- Dominant language
- Pascal
- Stars
- 534
- Forks
- 143
- Avg merge
- 2d 10h
- Merged PRs (30d)
- 113
Description
### Is your feature request related to a problem? Please describe.
Within the existing correction-search algorithm component of predictive-text, we have a maximum edit-distance threshold applied that seeks to prevent the search from straying too far from the original input. Even before teaching this threshold, search penalties are applied based on the required edit-distance. This applies at each stage of modeling input keystrokes and works well for simple, straightforward input - in particular, input where `Transform`s consistently have `.deleteLeft == 0`.
For example, suppose the user's target word - the suggestion they want to see - is 'apple', but their keyboard is "unique" and typing accuracy isn't so great, leading to the following transform sequence:
- insert: 'a', deleteLeft: 0
- insert: 'p', deleteLeft: 0
- insert: 't', deleteLeft: 0 // Yes, this one's a stretch compared to base English - please just roll with it.
- insert: 'k', deleteLeft: 0
- insert: 'le', deleteLeft: 1 // Even more of a stretch, but it helps the rest of the example flow.
With a max edit-distance threshold of 2 major non-input edits, note what happens:
- 'a' (distance 0)
- 'ap' (distance 0)
- 'apt' (distance 1 - 't' vs 'p')
- 'aptk' (distance 2 - also 'k' vs 'l')
With the penalization from having a distance of 2 here, there's a strong chance that the search will completely miss the next & final transform:
- 'aptle' (distance 1 - just 't' vs 'p')
This transform has less edit-distance, and ideally would be considered before its parent!
In fact, if the threshold is under 2 (fractional values are possible due via fat-finger probabilities), this `.deleteLeft > 0` input will be locked behind the threshold.
----
In technical computer science terms:
Note that our correction-search uses the [A* search heuristic](https://en.wikipedia.org/wiki/A*_search_algorithm) at its core. Sadly, yes, **_[heuristic](https://en.wikipedia.org/wiki/Heuristic)_**, not _algorithm_ - and it's because of the issue noted above. To explain this point more thoroughly: the fact that edit-distance (our heuristic) can _drop_ when following the edge from one input node to one of its successors prevents us from meeting the "[admissibility](https://en.wikipedia.org/wiki/Admissible_heuristic)" requirement needed to say our correction-search (and use of A*) is an _algorithm_ that will work optimally, and get us the best answer, for all cases. (If it did, that's an algorithm - but it doesn't, so it's a heuristic.)
### Describe the solution you'd like
When processing actual input transforms, they pass through buildDeletionEdges when being matched against the lexicon. When a currently-processing input `Transform` has `.deleteLeft > 0`, the method is able to adjust backward for the deletion - but only once it's being processed - when the correction-search algorithm has already reached that search-graph edge.
But... what if we performed a lookahead for upcoming `.deleteLeft > 0` transforms when processing a new edge? This idea is close to, and inspired by, that of "quantum tunneling" (as used by physics and also the machine learning field) - to jump past barriers of higher cost and reach those of similar or lower cost on the other side.
Roughly speaking:
- after processing a new keystroke for a path taken during correction-search, if another keystroke is available but not yet included in the search, filter for all its fat-finger alternatives (possibly including the keystroke itself) that have a `.deleteLeft > 0`.
- If such transforms are found, _immediately_ include _those_ in the search graph - but not any that did not pass the `.deleteLeft > 0` filter.
- _Maybe_ apply this recursively if _that_ keystroke's successor _also_ has `.deleteLeft` potential?
- Motivation: LDML keyboards with significant 'reorder' rule influence could easily have a number of these in sequence.
- Also `khmer_angkor`, given its many 'reorder'-like rules
Caveats:
- This may result in duplicate search nodes should if the original, base input `Transform` is actually of lower cost. The correction-search algorithm already has built-in duplicate handling, though.
- It'll likely somewhat increase the active search heap size during correction-search, which may slightly lower overall performance for cases where following the `.deleteLeft` path was not, in fact, necessary.
Implementing this change would get us notably closer to being the proper A* _algorithm_ that we desire, as it would allow us to, essentially, construct path edges that bypasses the edit-distance peaks.
The "_maybe_" point above gets us even closer to true admissibility (as it would eliminate progressively more cases where admissibility is violated), but I fear there are complications down that path - we should probably do the simple extension of just one look-ahead and get that correct first. It may also not be worth pursuing admissibility for rare, niche edge cases at the cost of further worsening performance for common cases.
### Describe alternatives you've considered
- Increase the maximum edit-distance threshold
- This does nothing to let those paths be searched earlier than their penalization would allow.
- Most other ideas I've brainstormed while writing this issue quickly prove to require _far_ more significant changes to the correction-search algorithm and its design.
### Related issues
_No response_
### Keyman apps
- [ ] Keyman for Android
- [ ] Keyman for iPhone and iPad
- [ ] Keyman for Linux
- [ ] Keyman for macOS
- [ ] Keyman for Windows
- [ ] Keyman Developer
- [x] KeymanWeb
- [ ] Other - give details at bottom of form
### Keyman version
19.0.84
### Operating system
_No response_
### Device
_No response_
### Target application
_No response_
### Browser
_No response_
### Keyboard name
_No response_
### Keyboard version
_No response_
### Language name
_No response_
### Additional context
_No response_
Contributor guide
Assessment
This issue has not been assessed yet.