hex/ios/HEXShared/FullKeyboard/TypingDecoder.swift
Dax fc86748476
ios keyboard: read a missed space with a slip, and run-together words (#2244)
* ios keyboard: read a missed space with a slip, and three or more run-together words

* ios keyboard: keep a likelier reading over the missed-space fallback

* ios keyboard: make the dictionary guard test depend on the guard
2026-11-21 16:15:02 -05:00

1074 lines
54 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, read in place from the mapped file (Swipe typing reads
/// thousands a swipe).
@inline(__always) func withCodes<R>(_ i: Int, _ body: (UnsafeRawBufferPointer) -> R) -> R {
let s = start(i)
return body(UnsafeRawBufferPointer(start: base.advanced(by: blobAt + s), count: start(i + 1) - s))
}
/// 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)
}
/// Whether the model has `second` following `first` as a pair.
func hasPair(_ first: String, _ second: String) -> Bool {
guard let a = index(of: first), let b = index(of: second) else { return false }
return bigramCost(a, b) != nil
}
/// -ln P(word | previous) with the decoder's backoff to the unigram (0.92 nats), or nil
/// when the model lacks the word.
func cost(of word: String, after previous: String?) -> Double? {
guard let i = index(of: word) else { return nil }
let backoff = 0.92 + unigramCost(i)
guard let previous, let a = index(of: previous), let pair = bigramCost(a, i) else { return backoff }
return min(pair, backoff)
}
/// The three most probable allowed continuations of a completed word. Scan just its
/// mapped bigram row and keep three entries, even for a word with thousands of followers.
func nextWords(after previous: String, allowing: (String) -> Bool) -> [String] {
guard let a = index(of: previous) else { return [] }
let start = Int(base.loadUnaligned(fromByteOffset: pairRowsAt + 4 * a, as: UInt32.self))
let end = Int(base.loadUnaligned(fromByteOffset: pairRowsAt + 4 * (a + 1), as: UInt32.self))
guard start <= end, end <= bigramCount else { return [] }
var best: [(rank: Int, text: String)] = []
for i in start..<end {
let cost = Int(base.load(fromByteOffset: pairCostsAt + i, as: UInt8.self))
let b = Int(base.loadUnaligned(fromByteOffset: pairWordsAt + 4 * i, as: UInt32.self))
guard b < wordCount else { continue }
// Prefer the commoner word when two pair probabilities quantize to the same byte.
let rank = cost * 256 + Int(base.load(fromByteOffset: unigramAt + b, as: UInt8.self))
if best.count == 3, rank >= best[2].rank { continue }
let text = word(b)
guard allowing(text) else { continue }
let at = best.firstIndex { rank < $0.rank } ?? best.count
best.insert((rank, text), at: at)
if best.count > 3 { best.removeLast() }
}
return best.map(\.text)
}
/// Complete a short prefix with the word frequencies, backed by the previous word's
/// bigrams when available. Word indices and each bigram row have the same sort order:
/// walk only the matching prefix range, creating strings only for contenders.
func completions(of prefix: String, after previous: String?, allowing: (String) -> Bool) -> [String] {
guard let codes = encode(prefix), (1...3).contains(codes.count) else { return [] }
var lo = 0, hi = wordCount
for (depth, code) in codes.enumerated() {
(lo, hi) = narrow(lo, hi, depth: depth, byte: Int(code))
if lo == hi { return [] }
}
var link = 0, end = 0
if let previous, let a = index(of: previous) {
link = Int(base.loadUnaligned(fromByteOffset: pairRowsAt + 4 * a, as: UInt32.self))
end = Int(base.loadUnaligned(fromByteOffset: pairRowsAt + 4 * (a + 1), as: UInt32.self))
guard link <= end, end <= bigramCount else { return [] }
var upper = end
while link < upper {
let mid = (link + upper) / 2
if follower(mid) < lo { link = mid + 1 } else { upper = mid }
}
}
var best: [(rank: Int, text: String)] = []
var next = link < end ? follower(link) : hi
for i in lo..<hi {
let unigram = Int(base.load(fromByteOffset: unigramAt + i, as: UInt8.self))
var cost = unigram + 7 // 0.92 nats of unigram backoff, in eighths of a nat.
if i == next {
cost = min(cost, Int(base.load(fromByteOffset: pairCostsAt + link, as: UInt8.self)))
link += 1
next = link < end ? follower(link) : hi
}
let rank = cost * 256 + unigram
guard length(i) > codes.count, length(i) <= codes.count + 8,
best.count < 2 || rank < best[1].rank else { continue }
let text = word(i)
guard allowing(text) else { continue }
let at = best.firstIndex { rank < $0.rank } ?? best.count
best.insert((rank, text), at: at)
if best.count > 2 { best.removeLast() }
}
return best.map(\.text)
}
@inline(__always) private func follower(_ link: Int) -> Int {
Int(base.loadUnaligned(fromByteOffset: pairWordsAt + 4 * link, as: UInt32.self))
}
/// How much of the word list's frequency continues `prefix` with each letter, by letter
/// code. Nil when no word starts with `prefix`, or one ends there and none goes on.
func continuations(after prefix: [UInt8]) -> [Double]? {
var lo = 0, hi = wordCount
for (depth, b) in prefix.enumerated() {
(lo, hi) = narrow(lo, hi, depth: depth, byte: Int(b))
if lo >= hi { return nil }
}
var mass = [Double](repeating: 0, count: characters.count)
let depth = prefix.count
var any = false
for i in lo..<hi {
let code = byte(i, depth)
guard code > 0, code != Int(apostropheCode ?? 0) else { continue }
mass[code] += Self.frequency[Int(base.load(fromByteOffset: unigramAt + i, as: UInt8.self))]
any = true
}
return any ? mass : nil
}
/// exp(-cost) for each stored unigram cost byte (cost = byte / 8 nats).
private static let frequency: [Double] = (0..<256).map { exp(-Double($0) / 8) }
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
/// A tap on the bottom row's upper half read as a space the finger missed ("ofbthe"):
/// this, plus `spaceTapWeight` times how much nearer its letter row than the space bar
/// it landed (the bar's Gaussian likelihood against the row's). Below the row's centre
/// such a tap costs `spaceOmissionCost`.
var spaceTapCost = 5.0
var spaceTapWeight = 0.25
/// A space tap is read as a letter meant on the row above ("deli ate" for "delicate")
/// only when the row is at most this many nats less likely than the space bar for it:
/// within about the bar's top fifth, a little deeper than the system keyboard merges.
var mergeReach = 3.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 }
// Spanish's many one- and two-letter words ("a", "es", "va") make a letter read as
// a space too cheap a split ("vaxes" -> "va es"): there, only below the row's centre.
if language == "es" { p.spaceTapCost = .infinity }
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
/// The space bar's keycap as on the unsplit keyboard (both bars on a split one), or
/// nil when unknown: a bottom-row tap above it may have been meant for space.
var space: CGRect?
init(centres: [Character: CGPoint], pitch: CGSize, bottomRowY: CGFloat, space: CGRect? = nil) {
self.centres = centres
self.pitch = pitch
self.bottomRowY = bottomRowY
self.space = space
}
/// 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
var space: CGRect?
for key in layout.keys where key.kind == .space {
let minX = layout.unsplitX(key.frame.minX), maxX = layout.unsplitX(key.frame.maxX)
let bar = CGRect(x: minX, y: key.frame.minY, width: max(0, maxX - minX), height: key.frame.height)
space = space.map { $0.union(bar) } ?? bar
}
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
// A split layout's halves are pushed together, so a letter on both halves (G, V)
// has one centre, where the unsplit keyboard has it.
centres[letter] = CGPoint(x: layout.unsplitX(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.isSplit ? SplitGeometry.pitch : layout.letterWidth + m.gap,
height: m.keyHeight + m.rowGap
),
bottomRowY: bottom,
space: space
)
}
}
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 for the suggestion strip, best first: better than what you typed, or a
/// missed-space fallback that costs more than the flat cost of a word nothing knows.
var readings: [Reading]
var literalCost: Double
}
/// Model words and two-word readings never offered (`OffensiveWords`): still scored as
/// words, so what you typed is read right, but never a reading or a replacement.
struct NeverSuggest: Equatable, Sendable {
struct Pair: Hashable, Sendable {
var first: Int
var second: Int
}
var words: Set<Int> = []
var pairs: Set<Pair> = []
init() {}
/// Whether `word` after `previous` makes a blocked two-word expression.
func follows(_ word: Int, after previous: Int?) -> Bool {
guard let previous, !pairs.isEmpty else { return false }
return pairs.contains(Pair(first: previous, second: word))
}
/// `blocked`'s words and two-word phrases that are in `model`.
init(_ blocked: [String], model: TypingDecoderModel) {
for entry in blocked {
let parts = entry.split(separator: " ").map(String.init)
switch parts.count {
case 1:
if let i = model.index(of: entry) { words.insert(i) }
case 2:
if let a = model.index(of: parts[0]), let b = model.index(of: parts[1]) {
pairs.insert(Pair(first: a, second: b))
}
default:
break
}
}
}
}
let model: TypingDecoderModel
var parameters = Parameters()
/// Your own words, searched beside the model's.
var userWords = UserWords()
/// Words never offered; set by `AutocorrectEngine` for the language and Suggest swear words.
var neverSuggest = NeverSuggest()
/// 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, skipping: neverSuggest.words)
where word != literalIndex && !neverSuggest.follows(word, after: prev) {
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, letters: letters, 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 }
}
// Nothing above could read a word that is no word and no dictionary's: a missed
// space may still explain it, with a slip in the second word or three or more
// words run together. Never second-guess a dictionary word, one of yours, or a
// likelier reading that only missed the margin. German is left out: its model is
// lowercase and its nouns take their capital in the single-word path.
if replacement == nil, literalIndex == nil, !literalIsValid, !literalIsYours,
model.language != "de", parameters.splits, letters.count >= 5,
let fallback = missedSpaceReading(costs: costs, letters: letters, prev: prev, literalCost: literalCost) {
let best = readings.first
if best == nil || fallback.cost <= best!.cost
|| best!.text.lowercased() == fallback.text.lowercased() {
replacement = fallback.text
readings.removeAll { $0.text.lowercased() == fallback.text.lowercased() }
readings.insert(fallback, at: 0)
}
}
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),
/// leaving out `skipping` (searched through, never found).
private func search<Words: TypingDecoderWords>(
_ words: Words, _ costs: [[Double]], range: Range<Int>, limit: Int, maxEdits: Int, skipping: Set<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) }
}
// Dropping a clearly aimed, distinct tap needs more evidence than dropping an
// accidental repeat or a tap between keys. Accents share their physical key.
let extraTapCosts: [Double] = maxEdits == 0 ? [] : letterChoices.indices.map { tap in
guard let code = letterChoices[tap].first?.0 else { return parameters.insertionCost }
let key = model.baseCodes[code]
for neighbor in [tap - 1, tap + 1] where letterChoices.indices.contains(neighbor) {
if let other = letterChoices[neighbor].first?.0, model.baseCodes[other] == key {
return parameters.insertionCost
}
}
let gap = letterChoices[tap].first { model.baseCodes[$0.0] != key }?.1 ?? parameters.maxTapCost
return parameters.insertionCost + min(4, gap)
}
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, !skipping.contains(lo) {
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 + extraTapCosts[tap])))
}
// 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; around a tap on
/// the bottom row's upper half read as a space ("ofbthe"), only as the letters typed, so
/// a name's middle letter ("rima") is never a space with slips around it.
private func splitReadings(_ costs: [[Double]], taps: [CGPoint], letters: [UInt8], keys: Keys, prev: Int?) -> [Reading] {
let n = costs.count
var out: [Reading] = []
func pair(left: Range<Int>, right: Range<Int>, extra: Double, exact: Bool = false) {
guard !left.isEmpty, !right.isEmpty else { return }
let never = neverSuggest
func halves(_ range: Range<Int>) -> [(Int, Double)] {
guard exact else { return search(model, costs, range: range, limit: 3, maxEdits: 0, skipping: never.words) }
guard let word = model.index(ofCodes: Array(letters[range])), !never.words.contains(word) else { return [] }
return [(word, range.reduce(0) { $0 + costs[$1][Int(letters[$1])] })]
}
let lefts = halves(left).filter { canStandAlone($0.0) }
guard !lefts.isEmpty else { return }
let rights = halves(right).filter { canStandAlone($0.0) }
for (l, ls) in lefts {
let lcost = ls + parameters.lmWeight * lmCost(l, after: prev)
for (r, rs) in rights where !never.follows(r, after: l) {
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)
guard k < n - 1 else { continue }
if taps[k].y > keys.bottomRowY {
pair(left: 0..<k, right: (k + 1)..<n, extra: parameters.spaceOmissionCost)
} else if let extra = spaceCost(of: taps[k], keys: keys) {
pair(left: 0..<k, right: (k + 1)..<n, extra: extra, exact: true)
}
}
return out
}
/// The cost of reading a tap on the bottom row's upper half as a space the finger missed,
/// or nil when it can't be one: above the space bar, priced by how much nearer the row's
/// centre than the bar's it landed.
private func spaceCost(of tap: CGPoint, keys: Keys) -> Double? {
guard parameters.spaceTapCost.isFinite, let bar = keys.space, bar.width > 0 else { return nil }
let slack = keys.pitch.width / 2
guard tap.x >= bar.minX - slack, tap.x <= bar.maxX + slack,
tap.y > keys.bottomRowY - keys.pitch.height / 2 else { return nil }
let sy = Double(keys.pitch.height) * parameters.sigmaY
let toBar = (Double(tap.y) - Double(bar.midY)) / sy
let toRow = (Double(tap.y) - Double(keys.bottomRowY)) / sy
let likelierRow = max(0, 0.5 * (toBar * toBar - toRow * toRow))
return parameters.spaceTapCost + parameters.spaceTapWeight * likelierRow
}
/// How much likelier the space bar than the bottom letter row a space tap was, in nats
/// (0 when the row is likelier), or nil when it isn't above a bottom-row letter.
private func rowCost(of tap: CGPoint, keys: Keys) -> Double? {
guard let bar = keys.space, bar.width > 0 else { return nil }
let slack = keys.pitch.width / 2
guard tap.x >= bar.minX - slack, tap.x <= bar.maxX + slack else { return nil }
let sy = Double(keys.pitch.height) * parameters.sigmaY
let toBar = (Double(tap.y) - Double(bar.midY)) / sy
let toRow = (Double(tap.y) - Double(keys.bottomRowY)) / sy
return max(0, 0.5 * (toRow * toRow - toBar * toBar))
}
/// One word where a space was tapped for a letter on the row above ("deli ate" for
/// "delicate", "a out" for "about"): the likeliest reading of the first word's taps, the
/// space tap as a letter and the second word's taps, when it beats the two words as they
/// read by the margin and the tap was near enough the row (`mergeReach`). Nil to keep them.
func merge(
first: String, firstTaps: [CGPoint], space: CGPoint, second: String, secondTaps: [CGPoint],
previous: String?, firstIsValid: Bool, secondIsValid: Bool, keys: Keys
) -> String? {
guard firstTaps.count == first.count, secondTaps.count == second.count, !second.isEmpty,
let firstCodes = model.encode(first.lowercased()), let secondCodes = model.encode(second.lowercased()),
let reach = rowCost(of: space, keys: keys), reach <= parameters.mergeReach else { return nil }
let taps = firstTaps + [space] + secondTaps
let centres = codeCentres(keys)
let costs = taps.map { tapCosts($0, centres: centres, keys: keys) }
let prev = previous.flatMap { model.index(of: $0) }
// The two words as space would leave them: each as typed or its likeliest reading
// ("i dkdnt" is "I didn't", never "obedient").
func reading(_ codes: [UInt8], at range: Range<Int>, after before: Int?, valid: Bool) -> (cost: Double, word: Int?) {
let typed = model.index(ofCodes: codes)
var spatial = 0.0
for (i, code) in codes.enumerated() { spatial += costs[range.lowerBound + i][Int(code)] }
var best = (cost: spatial + parameters.lmWeight * (typed.map { lmCost($0, after: before) }
?? (valid ? parameters.unknownValidCost : parameters.unknownCost)), word: typed)
for (word, s) in search(model, costs, range: range, limit: 3, maxEdits: parameters.maxEdits, skipping: neverSuggest.words) {
let cost = s + parameters.lmWeight * lmCost(word, after: before)
if cost < best.cost { best = (cost, word) }
}
return best
}
let firstRange = 0..<firstCodes.count
let firstReading = reading(firstCodes, at: firstRange, after: prev, valid: firstIsValid)
let secondReading = reading(secondCodes, at: (firstCodes.count + 1)..<taps.count, after: firstReading.word, valid: secondIsValid)
let split = firstReading.cost + secondReading.cost
guard split.isFinite else { return nil }
var best: (word: Int, cost: Double)?
for (word, spatial) in search(model, costs, range: 0..<costs.count, limit: 3, maxEdits: parameters.maxEdits, skipping: neverSuggest.words)
where model.length(word) > max(first.count, second.count) && !neverSuggest.follows(word, after: prev) {
let cost = spatial + parameters.lmWeight * lmCost(word, after: prev) + reach
if cost < best?.cost ?? .infinity { best = (word, cost) }
}
guard let best else { return nil }
let margin = firstIsValid && secondIsValid ? parameters.validMargin : parameters.autoMargin
return split - best.cost >= margin ? model.word(best.word) : nil
}
/// 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
}
/// What a missed space can still make of taps nothing above could read. `decide` asks
/// only when the word is not a word, not a dictionary word and not one of yours, so this
/// may take a reading the ordinary margin would not: the taps are no word at all, and a
/// word or three are likelier than a spelling nobody knows. The missed spaces are the
/// hypothesis, not evidence: a reading is taken only when its words, without them, cost
/// no more than the run nothing knows does.
private func missedSpaceReading(costs: [[Double]], letters: [UInt8], prev: Int?, literalCost: Double) -> Reading? {
let slipped = slippedSecondWord(costs, letters: letters, prev: prev)
let segmented = exactSegmentation(costs, letters: letters, prev: prev)
func affordable(_ reading: Reading?) -> Reading? {
guard let reading else { return nil }
let words = reading.text.split(separator: " ").count
let wordsCost = reading.cost - parameters.spaceOmissionCost * Double(words - 1)
return wordsCost <= literalCost ? reading : nil
}
switch (affordable(slipped), affordable(segmented)) {
case let (slipped?, segmented?): return segmented.cost < slipped.cost ? segmented : slipped
case let (slipped?, nil): return slipped
case let (nil, segmented?): return segmented
case (nil, nil): return nil
}
}
/// The first letters as a word and the rest read as one word after it, when the rest is
/// one slip from a word and clears the margin it would get typed after that first word
/// ("specialchsracter" -> "special character"). A rest that is already a word is left to
/// `splitReadings`: there is nothing there to fix. The first word is at least two letters:
/// a lone "i" with a slip after it would read almost any run as two words.
private func slippedSecondWord(_ costs: [[Double]], letters: [UInt8], prev: Int?) -> Reading? {
let n = letters.count
guard n >= 5 else { return nil }
var best: Reading?
for k in 2...(n - 3) {
guard let left = model.index(ofCodes: Array(letters[0..<k])),
canStandAlone(left), !neverSuggest.words.contains(left),
!neverSuggest.follows(left, after: prev),
model.index(ofCodes: Array(letters[k...])) == nil else { continue }
var leftSpatial = 0.0, rightLiteral = 0.0
for i in 0..<k { leftSpatial += costs[i][Int(letters[i])] }
for i in k..<n { rightLiteral += costs[i][Int(letters[i])] }
rightLiteral += parameters.lmWeight * parameters.unknownCost
let leftCost = leftSpatial + parameters.lmWeight * lmCost(left, after: prev)
for (right, spatial) in search(model, costs, range: k..<n, limit: 5, maxEdits: parameters.maxEdits, skipping: neverSuggest.words)
where !neverSuggest.follows(right, after: left) {
let rightCost = spatial + parameters.lmWeight * lmCost(right, after: left)
guard rightLiteral - rightCost >= parameters.autoMargin else { continue }
let cost = leftCost + rightCost + parameters.spaceOmissionCost
if best == nil || cost < best!.cost {
best = Reading(text: model.word(left) + " " + model.word(right), cost: cost)
}
}
}
return best
}
private struct SegmentPath {
var words: [Int]
var cost: Double
}
private struct SegmentKey: Hashable {
var last: Int
var count: Int
}
/// Three to six words typed with no spaces, every one spelled as typed
/// ("seeyoutomorrow" -> "see you tomorrow"). Dynamic programming keeps the cheapest
/// path per end position, last word and word count: two paths there can only continue
/// through that last word, and only their count decides whether one can still grow.
private func exactSegmentation(_ costs: [[Double]], letters: [UInt8], prev: Int?) -> Reading? {
let n = letters.count
guard n >= 5, n <= 32 else { return nil }
var spatial = [Double](repeating: 0, count: n + 1)
for i in 0..<n { spatial[i + 1] = spatial[i] + costs[i][Int(letters[i])] }
var states = [[SegmentKey: SegmentPath]](repeating: [:], count: n + 1)
states[0][SegmentKey(last: -1, count: 0)] = SegmentPath(words: [], cost: 0)
var best: SegmentPath?
for start in 0..<n {
guard !states[start].isEmpty else { continue }
// Every word that starts here, found by narrowing the model's list one letter at
// a time: the prefix walk stops as soon as no word carries those letters.
var ends: [(end: Int, word: Int)] = []
var lo = 0, hi = model.wordCount
for end in (start + 1)...n {
(lo, hi) = model.narrow(lo, hi, depth: end - start - 1, byte: Int(letters[end - 1]))
guard lo < hi else { break }
if model.length(lo) == end - start, canStandAlone(lo), !neverSuggest.words.contains(lo) {
ends.append((end, lo))
}
}
guard !ends.isEmpty else { continue }
for (key, path) in states[start] {
for (end, word) in ends {
if neverSuggest.follows(word, after: key.last >= 0 ? key.last : prev) { continue }
var words = path.words
words.append(word)
let cost = path.cost + (spatial[end] - spatial[start])
+ parameters.lmWeight * lmCost(word, after: key.last >= 0 ? key.last : prev)
+ (key.count == 0 ? 0 : parameters.spaceOmissionCost)
if end == n {
if words.count >= 3, words.count <= 6, best == nil || cost < best!.cost {
best = SegmentPath(words: words, cost: cost)
}
continue
}
guard words.count < 6 else { continue }
let next = SegmentKey(last: word, count: words.count)
if let known = states[end][next], known.cost <= cost { continue }
states[end][next] = SegmentPath(words: words, cost: cost)
}
}
}
return best.map { Reading(text: $0.words.map { model.word($0) }.joined(separator: " "), cost: $0.cost) }
}
}
extension TypingDecoder {
/// Whether `decide` with `keys` would put `reading` (one word) in place of what you typed:
/// it beats the literal by the margin. Nil for a two-word reading, which only `decide` can
/// tell. Adaptive touch asks with the centres read without it, so a correction it applies
/// is one the keyboard would apply anyway.
func replaces(with reading: String, taps: [CGPoint], typed: String, previous: String?, literalIsValid: Bool, keys: Keys) -> Bool? {
guard !reading.contains(" ") else { return nil }
guard taps.count == typed.count, !typed.isEmpty, let letters = model.encode(typed),
!letters.contains(where: { $0 == model.apostropheCode }),
let codes = model.encode(reading.lowercased()) else { return false }
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 false }
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 readingLM = Double.infinity
if let index = model.index(ofCodes: codes), !neverSuggest.words.contains(index) {
readingLM = lmCost(index, after: prev)
}
if userWords.index(of: codes) != nil { readingLM = min(readingLM, parameters.userWordCost) }
guard readingLM.isFinite else { return false }
var margin = (literalIndex != nil || literalIsValid || literalIsYours) ? parameters.validMargin : parameters.autoMargin
if margin > parameters.accentMargin, Self.withoutAccents(reading.lowercased()) == Self.withoutAccents(typed) {
margin = parameters.accentMargin
}
// Usually one alignment the search would also try already clears it: no search then.
if let bound = alignedCost(codes, costs), literalCost - (bound + parameters.lmWeight * readingLM) >= margin {
return true
}
guard let spatial = search(OneWord(codes: codes), costs, range: 0..<costs.count, limit: 1, maxEdits: parameters.maxEdits).first?.1
else { return false }
return literalCost - (spatial + parameters.lmWeight * readingLM) >= margin
}
/// The cost of `codes` read letter for letter from the taps, or with one letter you didn't
/// type at its cheapest place: never below what the search finds, so a bound to clear.
/// Nil when neither fits (another edit, a tap past `maxTapCost`).
private func alignedCost(_ codes: [UInt8], _ costs: [[Double]]) -> Double? {
let n = costs.count
var letters: [Int] = []
letters.reserveCapacity(codes.count)
for (depth, code) in codes.enumerated() {
if code == model.apostropheCode {
guard depth > 0 else { return nil }
continue
}
letters.append(Int(code))
}
func tap(_ i: Int, _ code: Int) -> Double? {
let c = costs[i][code]
return c <= parameters.maxTapCost ? c : nil
}
if letters.count == n {
var total = 0.0
for i in 0..<n {
guard let c = tap(i, letters[i]) else { return nil }
total += c
}
return total
}
guard letters.count == n + 1, parameters.maxEdits >= 1 else { return nil }
var prefix = [Double](repeating: .infinity, count: n + 1)
prefix[0] = 0
for i in 0..<n {
guard let c = tap(i, letters[i]) else { break }
prefix[i + 1] = prefix[i] + c
}
var best = Double.infinity
var suffix = 0.0
for j in stride(from: n, through: 0, by: -1) {
if j < n {
guard let c = tap(j, letters[j + 1]) else { break }
suffix += c
}
best = min(best, prefix[j] + suffix)
}
return best.isFinite ? best + parameters.deletionCost : nil
}
/// One word, searched as a word list.
private struct OneWord: TypingDecoderWords {
let codes: [UInt8]
var wordCount: Int { 1 }
func length(_ i: Int) -> Int { codes.count }
func byte(_ i: Int, _ depth: Int) -> Int { depth < codes.count ? Int(codes[depth]) : -1 }
}
}