keymanapp / keymanapp/keyman

change(web): improve optimization of prediction-generation

Open
#16,577 0 comments 0 reactions 1 assignee Claimed by @jahorton View on GitHub
change web/
Dominant language
Pascal
Stars
534
Forks
143
Avg merge
2d 10h
Merged PRs (30d)
113

Description

As noted on #16450, the "correction" portion of suggestion generation is susceptible to the host device's performance capabilities. Keeping the process well-optimized helps ensure that reasonably-expected corrections actually surface.

At present, correction and prediction operate as follows:

1. A _correction-search_ process searches for the best-fitting corrections for the existing context. The "optimization condition" is built from two parts:
1. The combined probability of the keystrokes selected at each stage, as taken in a vacuum. These probabilities are based upon the distance from the center of the key to the actual touch-point of the user's finger at the time of the key event.
2. A "probability" based directly upon the number of "edits" applied to the context in addition to the user's keystrokes - an "edit distance", if you will. Potential edits:
1. Insertion of an extra character that was never entered
2. Deletion of a character that was mistakenly entered
3. Wholesale replacement of an entered character
4. Reordering two keystrokes so that their text-edits are applied in inverse order
2. Once viable corrections are found, the engine _then_ generates predictions based upon them.
- Note that the frequency of predicted words, and thus their "probability", is not considered for the search.

Given that proper handling of transpositions must already overcome a notable penalty due to edit-distance cost, **we should probably include an aspect of "minimum prediction cost" within the correction-search optimization condition.** This way, transpositions toward high-frequency words gain stronger preference than edits toward lower-frequency words, helping to ensure that the highest-priority transposition corrections are able to surface more reliably.

This would result in an optimization condition built from three parts:
1. The combined probability of the keystrokes selected at each stage, as taken in a vacuum.
2. A "probability" based directly upon the number of "edits" applied to the context in addition to the user's keystrokes - the "edit distance".
3. The lexical probability of the most likely word prefixed by the corrected version of the text.

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.