keymanapp / keymanapp/keyman

feat(web): improve correction-search handling of complex context changes

Open
#14,366 0 comments 0 reactions 1 assignee Claimed by @jahorton View on GitHub
feat web/ web/predictive-text/
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.