mirror of
https://github.com/anomalyco/hex.git
synced 2026-11-21 17:56:51 +08:00
* iOS keyboard: Spatial autocorrect experiment (tap + bigram decoder), off by default
What: a noisy-channel word decoder (TypingDecoder) behind Settings ›
Experiments › Spatial autocorrect (experiments.spatialAutocorrect, off
by default; it needs the full keyboard with Autocorrect on). When on, for a layout whose
model is bundled (English, Spanish), it replaces UITextChecker's one-edit
guesses on space and in the strip:
- each tap is scored against every letter with a 2D Gaussian around the
key (sigma 0.29 x 0.26 of the key pitch), moved by Learn how I type's
average tap offsets for letters with 20+ taps;
- words come from a beam search over a memory-mapped, sorted word list
with substitutions, one insertion, deletion or transposition, free
apostrophes ("dont" -> "don't") and accented letters read from their
base key (é from e, +1 nat);
- a bigram language model on the word before (stupid backoff) weighs
them, and a missed space is tried by splitting the taps in two (or
treating a bottom-row tap as the space);
- what was typed is replaced only when the best reading beats it by 2
nats, or 7 when it is itself a word the model, UITextChecker, learned
words or the shorthand list know.
Text replacements, learned fixes, the English contraction/typo table and
words you kept still come first. FullKeyboardEngine now records each
letter's tap point for the word being typed (cleared on anything else).
scripts/build-typing-model.py writes the model format (v2: per-language
alphabet, sorted words, u8 costs, sorted bigram keys); models are kept
out of git (.gitignore). The English prototype model is built from
SymSpell's frequency lists (MIT; Google Books Ngram CC BY 3.0 and SCOWL),
the Spanish one from Tatoeba sentence counts (CC BY 2.0 FR). Typing logs
now record the setting.
Why: Record typing logs show short words and non-words left uncorrected
("tk" for "to"), missed spaces with a typo inside, and o/i taps landing
low on k/j. The UITextChecker path skips 1-2 letter words, never uses
the word before, and can't split a word that also has a substitution.
Verified (anomastudio, iPhone 18 Pro simulator, iOS 27.2): benchmark
harness (kept outside the repo) typing every tap through
FullKeyboardEngine. Synthetic held-out English, 13,870 words: output
word error rate 15.0% today vs 6.7% (6.3% with tap offsets); typos fixed
58% vs 83%; correct words wrongly changed 89 vs 97 of 9,203. Labelled
real typing logs, 172 words: 14.5% vs 4.7%. Spanish held-out, 13,301
words: 26.8% vs 8.1% (Spanish model and test from the same corpus, so
optimistic). Per letter p50 1.0 ms, p95 2.5 ms; mapping the model adds
no measurable phys_footprint. Full HEXMobileTests suite: 221 tests,
0 failures (1 skipped, as before); Release generic-iOS build with
CODE_SIGNING_ALLOWED=NO succeeds with both models bundled. No new tests.
* iOS keyboard: Spatial autocorrect models from Google Books Ngram v3
What: the English and Spanish models (HEXKeyboard/TypingModel/en.hextm,
es.hextm, 3.6 MB each) are now built from Google Books Ngram v3 (CC BY
3.0) word and word-pair counts summed over 1980-2019, keeping only
words SCOWL (sizes up to 70, lowercase, ASCII) or RLA-ES (LibreOffice's
es_ES and es_MX dictionaries, MPL 1.1) accept, and are committed.
- English: 86,133 words, 417,480 word pairs; Spanish: 110,000 words,
326,366 pairs. Pairs are the ones that tell most over the single-word
model (count x log of P(b|a) over 0.4 P(b)), as many as fit.
- Format v3: pairs grouped by first word (u32 row starts, u32 second
word, u8 cost), 5 bytes a pair instead of 9, so ~70% more pairs fit
in the same size. TypingDecoderModel reads v3 only.
- scripts/build-typing-model.py downloads, counts (each ngram file
deleted once counted, every stage cached for a resumable rerun) and
writes a model: python build-typing-model.py <en|es> <workdir> <out>.
- Tuning for the new models (dev sentences): English leans more on the
word before (lmWeight 1.5; Parameters.tuned(for:)); an accent-only
change ("esta" -> "está") needs a 2-nat margin instead of 7 (ñ for n
isn't one: "ano"/"año"); an accented letter also reads from its base
key when it has its own (ñ from n), whichever is cheaper.
- Settings › Acknowledgements (new row and sheet, AcknowledgementsView)
and ios/README.md credit Google Books Ngram (CC BY 3.0), SCOWL with its
and WordNet's notices, and RLA-ES (MPL 1.1).
- AutocorrectEngineTests: decoder ranking cases on the bundled models
("need t^o" -> "need to", a missed space with a slip -> "see how",
correct words kept, Spanish "aqui manana" -> "aquí mañana", "esta"
kept).
Why: Ryan's licence decision: CC BY with credit, no share-alike, no
non-commercial or GPL/LGPL data, and not SymSpell's word-pair list
(unverified provenance). The Spanish model was built from Tatoeba,
the same corpus as its test set.
Removed: the SymSpell- and Tatoeba-built prototype models and the v2
format (pairs as sorted u64 keys); models are no longer gitignored.
Verified (Mac Studio, iPhone 18 Pro simulator, iOS 27.2; benchmark
harness outside the repo; word error rate on words that aren't names):
English held-out test, 13,870 words: today's engine 13.0%, decoder
3.6% (3.4% with tap offsets), correct words broken 4 -> 2 of 7,716;
labelled real typing logs, 172 words: 14.5% -> 4.1%; the shared
example sentence decodes exactly; Spanish held-out Tatoeba test (no
source shared with the model), 13,301 words: 25.7% -> 8.0%, broken
16 -> 20 of 7,246. Per letter p50 1.0 ms, p95 2.6 ms.
AutocorrectEngineTests 19 passed.
* iOS keyboard: Spatial autocorrect knows your own words
What: the decoder also searches TypingDecoder.UserWords, a small sorted
in-memory list of your words, beside the model: Contacts names and
other UILexicon terms, one-word text replacement outputs, words you
kept twice (LearnedWordsStore) and typo fixes Learn how I type learned.
Each scores as a moderately common word (userWordCost 11 nats) and
comes back as you spell it ("Zorbix", not "zorbix"); typed exactly,
one counts as a word, so it needs the larger margin to change.
AutocorrectEngine rebuilds the list only when a source changes
(revision bumped by loadLexiconEntries, applyLearning, suppressAndKeep)
or the model changes. The search is now generic over TypingDecoderWords
(the model or your words); the model's own narrow moved to it.
Why: a name, brand or word you use that the model lacks could only be
left alone, never reached from a typo.
Verified (Mac Studio, iPhone 18 Pro simulator, iOS 27.2):
AutocorrectEngineTests 20 passed, including a new case: with "Zorbix"
in the lexicon, a slip "zorbiz" becomes "Zorbix" and "zorbix" typed
right stays. Benchmark unchanged (it has no user words).
* iOS keyboard: an accent or tilde is the cheapest autocorrect fix
What: AutocorrectEngine.singleEditKeyboardCost now scores a one-letter
substitution that only adds or changes an accent, diaeresis or tilde
(e/é, u/ü, n/ñ) at 0.15, below every other edit, instead of 1.15 (the
cost of two far-apart keys). New helper sameLetterIgnoringAccents.
Valid words are still never rewritten, so "esta" stays "esta".
Why: Spanish typed without accents was corrected into the wrong word,
because the accented guess cost more than any insertion, deletion or
neighbouring key: "aqui" -> "caqui", "podia" -> "odia", "manana" ->
"manaba". Now they become "aquí", "podía", "mañana".
Verified (Mac Studio, iPhone 18 Pro simulator, iOS 27.2, the
benchmark harness kept outside the repo, today's engine with Spatial
autocorrect off): Spanish held-out Tatoeba test, 13,301 words, output
word error rate 26.8% -> 24.7%, words changed into another wrong word
1,015 -> 743, correct words broken 16 -> 16 of 7,246 (names excluded).
English test (13,870 words) unchanged at 15.0%.
* iOS keyboard: fix two-letter typos toward very common two-letter words
What: cautiousReplacement fixes a two-letter non-word (UITextChecker
doesn't know it, not ALL CAPS, no apostrophe) when one neighbouring key
or one swap turns it into a very common two-letter word of the layout's
language (KeyboardLanguage.commonTwoLetterWords, commonest first: "tk"
-> "to", "ot" -> "to", Spanish "nl" -> "no", "ee" -> "de"). English and
Spanish have lists; Norwegian and German have none yet and keep
leaving two-letter words alone. The step numbering in the comments
moves by one.
Why: autocorrect skipped every word under three letters, and the
commonest words are two letters: typing logs show "tk" for "to" left
uncorrected again and again (the o key's taps land low, on k).
Verified (Mac Studio, iPhone 18 Pro simulator, iOS 27.2, benchmark
harness outside the repo, today's engine): English held-out test,
13,870 words, output word error rate 15.0% -> 13.2%; labelled real
typing logs, 172 words, 14.5% -> 10.5%; Spanish test 24.7% -> 22.9%;
correct words broken unchanged (4 of 7,716 English, 16 of 7,246
Spanish, names excluded).
562 lines
26 KiB
Swift
562 lines
26 KiB
Swift
import CoreGraphics
|
|
import Darwin
|
|
import Foundation
|
|
|
|
/// The spatial decoder's word list and bigram language model, memory-mapped read-only from
|
|
/// a file `scripts/build-typing-model.py` writes. Mapped pages are clean and file-backed, so
|
|
/// iOS can drop them under pressure instead of counting them against the keyboard.
|
|
nonisolated final class TypingDecoderModel: @unchecked Sendable {
|
|
let wordCount: Int
|
|
let bigramCount: Int
|
|
let byteCount: Int
|
|
/// The language it was built for ("en", "es").
|
|
let language: String
|
|
/// Letter codes (1…) by character, each letter's character, and its unaccented letter's code.
|
|
let codes: [Character: UInt8]
|
|
let characters: [Character]
|
|
let baseCodes: [UInt8]
|
|
let apostropheCode: UInt8?
|
|
private let base: UnsafeRawPointer
|
|
private let offsetsAt: Int
|
|
private let unigramAt: Int
|
|
private let pairRowsAt: Int
|
|
private let pairWordsAt: Int
|
|
private let pairCostsAt: Int
|
|
private let blobAt: Int
|
|
|
|
init?(url: URL) {
|
|
let fd = open(url.path, O_RDONLY)
|
|
guard fd >= 0 else { return nil }
|
|
defer { close(fd) }
|
|
var info = stat()
|
|
guard fstat(fd, &info) == 0, info.st_size >= 28 else { return nil }
|
|
let size = Int(info.st_size)
|
|
guard let mapped = mmap(nil, size, PROT_READ, MAP_PRIVATE, fd, 0), mapped != MAP_FAILED else { return nil }
|
|
let base = UnsafeRawPointer(mapped)
|
|
func u32(_ at: Int) -> Int { Int(base.loadUnaligned(fromByteOffset: at, as: UInt32.self)) }
|
|
let magic = base.loadUnaligned(as: UInt32.self)
|
|
guard magic == 0x4D54_5848, u32(4) == 3 else { munmap(mapped, size); return nil } // "HXTM" v3
|
|
let words = u32(8), bigrams = u32(12), blob = u32(16), letters = u32(20)
|
|
guard letters < 255, 28 + 8 * letters <= size else { munmap(mapped, size); return nil }
|
|
let languageBytes = (0..<4).map { base.load(fromByteOffset: 24 + $0, as: UInt8.self) }.filter { $0 != 0 }
|
|
var codes: [Character: UInt8] = [:]
|
|
var characters = [Character](repeating: " ", count: letters + 1)
|
|
var baseCodes = [UInt8](repeating: 0, count: letters + 1)
|
|
for i in 0..<letters {
|
|
let at = 28 + 8 * i
|
|
guard let scalar = Unicode.Scalar(u32(at)) else { munmap(mapped, size); return nil }
|
|
let code = Int(base.load(fromByteOffset: at + 4, as: UInt8.self))
|
|
let baseCode = base.load(fromByteOffset: at + 5, as: UInt8.self)
|
|
guard code >= 1, code <= letters, baseCode >= 1, Int(baseCode) <= letters else { munmap(mapped, size); return nil }
|
|
codes[Character(scalar)] = UInt8(code)
|
|
characters[code] = Character(scalar)
|
|
baseCodes[code] = baseCode
|
|
}
|
|
let offsetsAt = 28 + 8 * letters
|
|
let unigramAt = offsetsAt + 4 * (words + 1)
|
|
var rowsAt = unigramAt + words
|
|
rowsAt += (4 - rowsAt % 4) % 4
|
|
let pairWordsAt = rowsAt + 4 * (words + 1)
|
|
let pairCostsAt = pairWordsAt + 4 * bigrams
|
|
let blobAt = pairCostsAt + bigrams
|
|
guard blobAt + blob == size else { munmap(mapped, size); return nil }
|
|
self.base = base
|
|
self.byteCount = size
|
|
self.language = String(decoding: languageBytes, as: UTF8.self)
|
|
self.codes = codes
|
|
self.characters = characters
|
|
self.baseCodes = baseCodes
|
|
self.apostropheCode = codes["'"]
|
|
self.wordCount = words
|
|
self.bigramCount = bigrams
|
|
self.offsetsAt = offsetsAt
|
|
self.unigramAt = unigramAt
|
|
self.pairRowsAt = rowsAt
|
|
self.pairWordsAt = pairWordsAt
|
|
self.pairCostsAt = pairCostsAt
|
|
self.blobAt = blobAt
|
|
}
|
|
|
|
deinit {
|
|
munmap(UnsafeMutableRawPointer(mutating: base), byteCount)
|
|
}
|
|
|
|
@inline(__always) private func start(_ i: Int) -> Int {
|
|
Int(base.loadUnaligned(fromByteOffset: offsetsAt + 4 * i, as: UInt32.self))
|
|
}
|
|
|
|
@inline(__always) func length(_ i: Int) -> Int { start(i + 1) - start(i) }
|
|
|
|
/// The word's byte at `depth`, or -1 past its end.
|
|
@inline(__always) func byte(_ i: Int, _ depth: Int) -> Int {
|
|
let s = start(i)
|
|
guard depth < start(i + 1) - s else { return -1 }
|
|
return Int(base.load(fromByteOffset: blobAt + s + depth, as: UInt8.self))
|
|
}
|
|
|
|
func word(_ i: Int) -> String {
|
|
let s = start(i)
|
|
return String((s..<start(i + 1)).map { characters[Int(base.load(fromByteOffset: blobAt + $0, as: UInt8.self))] })
|
|
}
|
|
|
|
/// The word's letter codes, or nil when it has a letter the model doesn't.
|
|
func encode(_ word: String) -> [UInt8]? {
|
|
var out: [UInt8] = []
|
|
for c in word {
|
|
guard let code = codes[c] else { return nil }
|
|
out.append(code)
|
|
}
|
|
return out
|
|
}
|
|
|
|
/// -ln P(word), in nats.
|
|
@inline(__always) func unigramCost(_ i: Int) -> Double {
|
|
Double(base.load(fromByteOffset: unigramAt + i, as: UInt8.self)) / 8
|
|
}
|
|
|
|
/// -ln P(b | a), in nats, when the pair is in the model.
|
|
func bigramCost(_ a: Int, _ b: Int) -> Double? {
|
|
guard a >= 0, a < wordCount else { return nil }
|
|
var lo = Int(base.loadUnaligned(fromByteOffset: pairRowsAt + 4 * a, as: UInt32.self))
|
|
let end = Int(base.loadUnaligned(fromByteOffset: pairRowsAt + 4 * (a + 1), as: UInt32.self))
|
|
guard lo <= end, end <= bigramCount else { return nil }
|
|
var hi = end
|
|
let target = UInt32(b)
|
|
while lo < hi {
|
|
let mid = (lo + hi) / 2
|
|
if base.loadUnaligned(fromByteOffset: pairWordsAt + 4 * mid, as: UInt32.self) < target { lo = mid + 1 } else { hi = mid }
|
|
}
|
|
guard lo < end, base.loadUnaligned(fromByteOffset: pairWordsAt + 4 * lo, as: UInt32.self) == target else { return nil }
|
|
return Double(base.load(fromByteOffset: pairCostsAt + lo, as: UInt8.self)) / 8
|
|
}
|
|
|
|
func index(of word: String) -> Int? {
|
|
guard let bytes = encode(word) else { return nil }
|
|
return index(ofCodes: bytes)
|
|
}
|
|
|
|
func index(ofCodes bytes: [UInt8]) -> Int? {
|
|
var lo = 0, hi = wordCount
|
|
for (depth, b) in bytes.enumerated() {
|
|
(lo, hi) = narrow(lo, hi, depth: depth, byte: Int(b))
|
|
if lo >= hi { return nil }
|
|
}
|
|
return length(lo) == bytes.count ? lo : nil
|
|
}
|
|
|
|
}
|
|
|
|
/// A word list sorted by letter codes, searchable letter by letter: the model's, or yours.
|
|
nonisolated protocol TypingDecoderWords {
|
|
var wordCount: Int { get }
|
|
func length(_ i: Int) -> Int
|
|
/// The word's letter code at `depth`, or -1 past its end.
|
|
func byte(_ i: Int, _ depth: Int) -> Int
|
|
}
|
|
|
|
extension TypingDecoderWords {
|
|
/// The words in `lo..<hi` (which share their first `depth` codes) whose next code is `byte`.
|
|
func narrow(_ lo: Int, _ hi: Int, depth: Int, byte target: Int) -> (Int, Int) {
|
|
var a = lo, b = hi
|
|
while a < b {
|
|
let mid = (a + b) / 2
|
|
if byte(mid, depth) < target { a = mid + 1 } else { b = mid }
|
|
}
|
|
var c = a, d = hi
|
|
while c < d {
|
|
let mid = (c + d) / 2
|
|
if byte(mid, depth) <= target { c = mid + 1 } else { d = mid }
|
|
}
|
|
return (a, c)
|
|
}
|
|
}
|
|
|
|
extension TypingDecoderModel: TypingDecoderWords {}
|
|
|
|
extension TypingDecoder {
|
|
/// Your own words for the decoder (Contacts names and other `UILexicon` terms, text
|
|
/// replacements, words you kept, fixes Hex learned), as you spell them, each scored as a
|
|
/// moderately common word. Words with a letter the model lacks are left out.
|
|
struct UserWords: TypingDecoderWords, Sendable {
|
|
private(set) var codes: [[UInt8]] = []
|
|
private(set) var texts: [String] = []
|
|
private var lookup: [[UInt8]: Int] = [:]
|
|
|
|
init() {}
|
|
|
|
init(_ words: [String], model: TypingDecoderModel) {
|
|
var byCodes: [[UInt8]: String] = [:]
|
|
for word in words {
|
|
guard word.count >= 2, word.allSatisfy({ $0.isLetter || $0 == "'" }),
|
|
let encoded = model.encode(word.lowercased()) else { continue }
|
|
if byCodes[encoded] == nil { byCodes[encoded] = word }
|
|
}
|
|
codes = byCodes.keys.sorted { $0.lexicographicallyPrecedes($1) }
|
|
texts = codes.map { byCodes[$0]! }
|
|
for (i, c) in codes.enumerated() { lookup[c] = i }
|
|
}
|
|
|
|
var wordCount: Int { codes.count }
|
|
var isEmpty: Bool { codes.isEmpty }
|
|
func length(_ i: Int) -> Int { codes[i].count }
|
|
func byte(_ i: Int, _ depth: Int) -> Int { depth < codes[i].count ? Int(codes[i][depth]) : -1 }
|
|
func index(of encoded: [UInt8]) -> Int? { lookup[encoded] }
|
|
}
|
|
}
|
|
|
|
extension TypingDecoderModel {
|
|
/// The model for a language in the keyboard's bundle (`HEXKeyboard/TypingModel/<code>.hextm`,
|
|
/// built by `scripts/build-typing-model.py`), mapped once per process; nil when the build
|
|
/// has none. The app's keyboard preview finds it inside the embedded keyboard.
|
|
@MainActor static func bundled(_ language: String) -> TypingDecoderModel? {
|
|
if let cached = loaded[language] { return cached }
|
|
var url = Bundle.main.url(forResource: language, withExtension: "hextm")
|
|
if url == nil, let plugins = Bundle.main.builtInPlugInsURL,
|
|
let keyboard = Bundle(url: plugins.appendingPathComponent("HEXKeyboard.appex")) {
|
|
url = keyboard.url(forResource: language, withExtension: "hextm")
|
|
}
|
|
let model = url.flatMap { TypingDecoderModel(url: $0) }
|
|
loaded[language] = model
|
|
return model
|
|
}
|
|
|
|
@MainActor private static var loaded: [String: TypingDecoderModel?] = [:]
|
|
}
|
|
|
|
/// Experiment (Spatial autocorrect): a noisy-channel word decoder. Each tap is scored against
|
|
/// every letter with a 2D Gaussian around the key's centre (shifted by where you tend to tap,
|
|
/// when known), words are searched in the model's sorted word list with a beam, and a bigram
|
|
/// language model on the word before weighs them. A missed space is tried by splitting the
|
|
/// taps in two. What you typed is replaced only when the best reading beats it by a margin.
|
|
nonisolated struct TypingDecoder {
|
|
struct Parameters: Equatable, Sendable {
|
|
// Tuned on the benchmark's dev sentences (experiment folder 2026-11-20-hex-typing-logs),
|
|
// keeping wrong corrections of correctly typed words no higher than today's engine.
|
|
/// Touch spread as a share of the key pitch (key width plus gap; row height plus gap).
|
|
var sigmaX = 0.29
|
|
var sigmaY = 0.26
|
|
var lmWeight = 1.25
|
|
var deletionCost = 7.0
|
|
var insertionCost = 7.0
|
|
var transpositionCost = 5.0
|
|
var spaceOmissionCost = 6.0
|
|
var maxEdits = 1
|
|
var beam = 48
|
|
/// Nats the best reading must beat what you typed by to replace it on space.
|
|
var autoMargin = 2.0
|
|
/// The same when what you typed is itself a word.
|
|
var validMargin = 7.0
|
|
/// Language-model cost of a word the model lacks that the dictionary, your learned
|
|
/// words or the shorthand list accept, and of one nothing accepts.
|
|
var unknownValidCost = 15.0
|
|
var unknownCost = 22.0
|
|
var maxTapCost = 9.0
|
|
var splits = true
|
|
/// Extra cost of an accented letter typed as its base letter's key (é from e).
|
|
var accentCost = 1.0
|
|
/// A one-letter word stands alone in a split only when commoner than this (-ln p).
|
|
var oneLetterWordCost = 7.0
|
|
/// Language-model cost of one of your own words the model lacks (-ln p, about a word
|
|
/// ranked 10,000th).
|
|
var userWordCost = 11.0
|
|
/// The margin when the best reading only adds or moves accents on what you typed
|
|
/// ("esta" -> "está"); ñ for n isn't one ("ano", "año").
|
|
var accentMargin = 2.0
|
|
|
|
/// The settings tuned for a language's model on the benchmark's dev sentences: English
|
|
/// leans more on the word before (Google Books' English pairs are richer).
|
|
static func tuned(for language: String) -> Parameters {
|
|
var p = Parameters()
|
|
if language == "en" { p.lmWeight = 1.5 }
|
|
return p
|
|
}
|
|
}
|
|
|
|
struct Keys: Equatable, Sendable {
|
|
/// Each letter key's centre, shifted by your tap offsets when there are any.
|
|
var centres: [Character: CGPoint]
|
|
var pitch: CGSize
|
|
/// The bottom letter row's centre, below which a tap may have been meant for space.
|
|
var bottomRowY: CGFloat
|
|
|
|
init(centres: [Character: CGPoint], pitch: CGSize, bottomRowY: CGFloat) {
|
|
self.centres = centres
|
|
self.pitch = pitch
|
|
self.bottomRowY = bottomRowY
|
|
}
|
|
|
|
/// The letter keys of `layout` (nil off the letters page). `offsets` (in points, by
|
|
/// letter) moves a centre to where you tend to tap it.
|
|
init?(layout: KeyboardLayout, offsets: [Character: CGVector] = [:]) {
|
|
guard layout.layer == .letters else { return nil }
|
|
var centres: [Character: CGPoint] = [:]
|
|
var bottom: CGFloat = 0
|
|
for key in layout.keys {
|
|
guard let c = key.character, c.count == 1, let letter = c.first, letter.isLetter else { continue }
|
|
let shift = offsets[letter] ?? .zero
|
|
centres[letter] = CGPoint(x: key.frame.midX + shift.dx, y: key.frame.midY + shift.dy)
|
|
bottom = max(bottom, key.frame.midY)
|
|
}
|
|
let m = layout.metrics
|
|
self.init(
|
|
centres: centres,
|
|
pitch: CGSize(width: layout.letterWidth + m.gap, height: m.keyHeight + m.rowGap),
|
|
bottomRowY: bottom
|
|
)
|
|
}
|
|
}
|
|
|
|
struct Reading: Equatable, Sendable {
|
|
var text: String
|
|
var cost: Double
|
|
}
|
|
|
|
struct Decision: Equatable, Sendable {
|
|
/// What space should put in place of what you typed, or nil to keep it.
|
|
var replacement: String?
|
|
/// Readings better than what you typed, best first, for the suggestion strip.
|
|
var readings: [Reading]
|
|
var literalCost: Double
|
|
}
|
|
|
|
let model: TypingDecoderModel
|
|
var parameters = Parameters()
|
|
/// Your own words, searched beside the model's.
|
|
var userWords = UserWords()
|
|
|
|
/// Learn how I type's average tap offsets (in keycap widths and heights) as points, for
|
|
/// letters with 20 taps or more, shrunk toward the centre while there are few.
|
|
static func offsets(from stats: [String: TypingJournalKeyStats], layout: KeyboardLayout) -> [Character: CGVector] {
|
|
var out: [Character: CGVector] = [:]
|
|
for key in layout.keys {
|
|
guard let c = key.character, c.count == 1, let letter = c.first, letter.isLetter,
|
|
let s = stats[c], s.count >= 20 else { continue }
|
|
let weight = Double(s.count) / Double(s.count + 20)
|
|
let mean = s.meanOffset
|
|
out[letter] = CGVector(dx: mean.dx * key.frame.width * weight, dy: mean.dy * key.frame.height * weight)
|
|
}
|
|
return out
|
|
}
|
|
|
|
init(model: TypingDecoderModel, parameters: Parameters? = nil) {
|
|
self.model = model
|
|
self.parameters = parameters ?? Parameters.tuned(for: model.language)
|
|
}
|
|
|
|
/// `typed` is the lowercase letters the keys resolved, one per tap. Nil when the model
|
|
/// can't read it (a letter it lacks, or taps that don't match).
|
|
func decide(taps: [CGPoint], typed: String, previous: String?, literalIsValid: Bool, keys: Keys) -> Decision? {
|
|
guard taps.count == typed.count, !typed.isEmpty, let letters = model.encode(typed),
|
|
!letters.contains(where: { $0 == model.apostropheCode }) else { return nil }
|
|
let centres = codeCentres(keys)
|
|
let costs = taps.map { tapCosts($0, centres: centres, keys: keys) }
|
|
let prev = previous.flatMap { model.index(of: $0) }
|
|
|
|
var literalCost = 0.0
|
|
for (i, code) in letters.enumerated() {
|
|
let c = costs[i][Int(code)]
|
|
guard c.isFinite else { return nil }
|
|
literalCost += c
|
|
}
|
|
let literalIndex = model.index(ofCodes: letters)
|
|
let literalIsYours = userWords.index(of: letters) != nil
|
|
var literalLM = literalIndex.map { lmCost($0, after: prev) }
|
|
?? (literalIsValid ? parameters.unknownValidCost : parameters.unknownCost)
|
|
if literalIsYours { literalLM = min(literalLM, parameters.userWordCost) }
|
|
literalCost += parameters.lmWeight * literalLM
|
|
|
|
var readings: [Reading] = []
|
|
for (word, spatial) in search(model, costs, range: 0..<costs.count, limit: 5, maxEdits: parameters.maxEdits) where word != literalIndex {
|
|
readings.append(Reading(text: model.word(word), cost: spatial + parameters.lmWeight * lmCost(word, after: prev)))
|
|
}
|
|
if !userWords.isEmpty {
|
|
for (word, spatial) in search(userWords, costs, range: 0..<costs.count, limit: 3, maxEdits: parameters.maxEdits)
|
|
where userWords.codes[word] != letters {
|
|
readings.append(Reading(text: userWords.texts[word], cost: spatial + parameters.lmWeight * parameters.userWordCost))
|
|
}
|
|
}
|
|
if parameters.splits, letters.count >= 3 {
|
|
readings += splitReadings(costs, taps: taps, keys: keys, prev: prev)
|
|
}
|
|
readings.sort { $0.cost < $1.cost }
|
|
var seen = Set<String>()
|
|
readings = readings.filter {
|
|
$0.text.lowercased() != typed && $0.cost < literalCost && seen.insert($0.text.lowercased()).inserted
|
|
}
|
|
|
|
var replacement: String?
|
|
if let best = readings.first {
|
|
var margin = (literalIndex != nil || literalIsValid || literalIsYours) ? parameters.validMargin : parameters.autoMargin
|
|
if Self.withoutAccents(best.text.lowercased()) == Self.withoutAccents(typed) {
|
|
margin = min(margin, parameters.accentMargin)
|
|
}
|
|
if literalCost - best.cost >= margin { replacement = best.text }
|
|
}
|
|
return Decision(replacement: replacement, readings: Array(readings.prefix(3)), literalCost: literalCost)
|
|
}
|
|
|
|
/// The text with acute, grave, circumflex and diaeresis marks removed (é -> e, ü -> u),
|
|
/// keeping ñ.
|
|
static func withoutAccents(_ text: String) -> String {
|
|
let marks: ClosedRange<UInt32> = 0x300...0x308
|
|
let scalars = text.decomposedStringWithCanonicalMapping.unicodeScalars
|
|
.filter { !(marks.contains($0.value) && $0.value != 0x303) }
|
|
return String(String.UnicodeScalarView(scalars)).precomposedStringWithCanonicalMapping
|
|
}
|
|
|
|
/// -ln P(word | previous) with stupid backoff (0.4) to the unigram.
|
|
private func lmCost(_ word: Int, after prev: Int?) -> Double {
|
|
let backoff = 0.92 + model.unigramCost(word)
|
|
guard let prev, let bigram = model.bigramCost(prev, word) else { return backoff }
|
|
return min(bigram, backoff)
|
|
}
|
|
|
|
/// Key centres by the model's letter codes; nil for letters without a key.
|
|
private func codeCentres(_ keys: Keys) -> [CGPoint?] {
|
|
var out = [CGPoint?](repeating: nil, count: model.characters.count)
|
|
for (c, p) in keys.centres {
|
|
if let code = model.codes[c] { out[Int(code)] = p }
|
|
}
|
|
return out
|
|
}
|
|
|
|
/// Each letter code's cost for one tap, in nats above the likeliest letter's. An accented
|
|
/// letter costs at most its base letter's plus `accentCost` (é on an English or Spanish
|
|
/// layout, ñ typed with n); one with neither key is impossible (infinity).
|
|
private func tapCosts(_ p: CGPoint, centres: [CGPoint?], keys: Keys) -> [Double] {
|
|
let sx = Double(keys.pitch.width) * parameters.sigmaX
|
|
let sy = Double(keys.pitch.height) * parameters.sigmaY
|
|
var out = centres.map { centre -> Double in
|
|
guard let c = centre else { return .infinity }
|
|
let dx = (Double(p.x) - Double(c.x)) / sx
|
|
let dy = (Double(p.y) - Double(c.y)) / sy
|
|
return 0.5 * (dx * dx + dy * dy)
|
|
}
|
|
// Also from its base key even when it has its own (ñ from n on the Spanish layout):
|
|
// whichever is cheaper.
|
|
let raw = out
|
|
for code in out.indices where code > 0 {
|
|
let base = Int(model.baseCodes[code])
|
|
if base != code, raw[base].isFinite { out[code] = min(raw[code], raw[base] + parameters.accentCost) }
|
|
}
|
|
let best = out.filter(\.isFinite).min() ?? 0
|
|
for i in out.indices { out[i] -= best }
|
|
return out
|
|
}
|
|
|
|
private struct State {
|
|
var lo: Int32
|
|
var hi: Int32
|
|
var tap: Int16
|
|
var edits: Int8
|
|
var cost: Float
|
|
}
|
|
|
|
/// The best words of `words` for `costs[range]`, as (word index, spatial cost incl. edits).
|
|
private func search<Words: TypingDecoderWords>(
|
|
_ words: Words, _ costs: [[Double]], range: Range<Int>, limit: Int, maxEdits: Int
|
|
) -> [(Int, Double)] {
|
|
let n = range.count
|
|
let maxDepth = n + maxEdits + 2
|
|
var layers = [[State]](repeating: [], count: maxDepth + 2)
|
|
layers[0] = [State(lo: 0, hi: Int32(words.wordCount), tap: 0, edits: 0, cost: 0)]
|
|
var found: [Int: Double] = [:]
|
|
let letterChoices: [[(Int, Double)]] = range.map { i in
|
|
costs[i].enumerated().filter { $0.offset > 0 && $0.element <= parameters.maxTapCost }
|
|
.sorted { $0.element < $1.element }.map { ($0.offset, $0.element) }
|
|
}
|
|
let apostrophe = model.apostropheCode.map(Int.init)
|
|
let allCodes = (1..<model.characters.count).filter { $0 != apostrophe }
|
|
for depth in 0...maxDepth {
|
|
var layer = layers[depth]
|
|
if layer.count > parameters.beam {
|
|
layer.sort { $0.cost < $1.cost }
|
|
layer.removeLast(layer.count - parameters.beam)
|
|
}
|
|
var k = 0
|
|
while k < layer.count {
|
|
let s = layer[k]
|
|
k += 1
|
|
let lo = Int(s.lo), hi = Int(s.hi), tap = Int(s.tap)
|
|
if tap == n, words.length(lo) == depth {
|
|
let c = Double(s.cost)
|
|
if c < found[lo] ?? .infinity { found[lo] = c }
|
|
}
|
|
guard depth < maxDepth else { continue }
|
|
func push(_ code: Int, tap nextTap: Int, edits: Int8, cost: Double) {
|
|
let (a, b) = words.narrow(lo, hi, depth: depth, byte: code)
|
|
guard a < b else { return }
|
|
layers[depth + 1].append(State(lo: Int32(a), hi: Int32(b), tap: Int16(nextTap), edits: edits, cost: Float(cost)))
|
|
}
|
|
let base = Double(s.cost)
|
|
if tap < n {
|
|
for (code, c) in letterChoices[tap] {
|
|
push(code, tap: tap + 1, edits: s.edits, cost: base + c)
|
|
}
|
|
}
|
|
// Apostrophes are never typed: "dont" reads as "don't" for free.
|
|
if depth > 0, let apostrophe { push(apostrophe, tap: tap, edits: s.edits, cost: base) }
|
|
guard Int(s.edits) < maxEdits else { continue }
|
|
let e = s.edits + 1
|
|
// A letter you didn't type.
|
|
for code in allCodes {
|
|
push(code, tap: tap, edits: e, cost: base + parameters.deletionCost)
|
|
}
|
|
// A tap that isn't in the word.
|
|
if tap < n {
|
|
layer.append(State(lo: s.lo, hi: s.hi, tap: s.tap + 1, edits: e, cost: Float(base + parameters.insertionCost)))
|
|
}
|
|
// Two letters typed in the wrong order.
|
|
if tap + 1 < n, depth + 2 <= maxDepth {
|
|
for (a, ca) in letterChoices[tap + 1].prefix(3) {
|
|
let (lo2, hi2) = words.narrow(lo, hi, depth: depth, byte: a)
|
|
guard lo2 < hi2 else { continue }
|
|
for (b, cb) in letterChoices[tap].prefix(3) where b != a {
|
|
let (lo3, hi3) = words.narrow(lo2, hi2, depth: depth + 1, byte: b)
|
|
guard lo3 < hi3 else { continue }
|
|
layers[depth + 2].append(State(
|
|
lo: Int32(lo3), hi: Int32(hi3), tap: Int16(tap + 2), edits: e,
|
|
cost: Float(base + ca + cb + parameters.transpositionCost)
|
|
))
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return found.sorted { $0.value < $1.value }.prefix(limit).map { ($0.key, $0.value) }
|
|
}
|
|
|
|
/// Two words where the taps had no space, or one meant for space ("seehow", "seenhow").
|
|
/// Each half is read with substitutions only, which keeps this cheap.
|
|
private func splitReadings(_ costs: [[Double]], taps: [CGPoint], keys: Keys, prev: Int?) -> [Reading] {
|
|
let n = costs.count
|
|
var out: [Reading] = []
|
|
func pair(left: Range<Int>, right: Range<Int>, extra: Double) {
|
|
guard !left.isEmpty, !right.isEmpty else { return }
|
|
let lefts = search(model, costs, range: left, limit: 3, maxEdits: 0).filter { canStandAlone($0.0) }
|
|
guard !lefts.isEmpty else { return }
|
|
let rights = search(model, costs, range: right, limit: 3, maxEdits: 0).filter { canStandAlone($0.0) }
|
|
for (l, ls) in lefts {
|
|
let lcost = ls + parameters.lmWeight * lmCost(l, after: prev)
|
|
for (r, rs) in rights {
|
|
let cost = lcost + rs + parameters.lmWeight * lmCost(r, after: l) + extra
|
|
out.append(Reading(text: model.word(l) + " " + model.word(r), cost: cost))
|
|
}
|
|
}
|
|
}
|
|
for k in 1..<n {
|
|
pair(left: 0..<k, right: k..<n, extra: parameters.spaceOmissionCost)
|
|
if k < n - 1, taps[k].y > keys.bottomRowY {
|
|
pair(left: 0..<k, right: (k + 1)..<n, extra: parameters.spaceOmissionCost)
|
|
}
|
|
}
|
|
return out
|
|
}
|
|
|
|
/// A word that may stand alone in a split: two or more letters, or a common one-letter
|
|
/// word ("a" and "i" in English; "y", "a", "o" in Spanish).
|
|
private func canStandAlone(_ i: Int) -> Bool {
|
|
model.length(i) >= 2 || model.unigramCost(i) < parameters.oneLetterWordCost
|
|
}
|
|
}
|