Files
hex/ios/scripts/build-typing-model.py
Ryan Vogel c14df5a4f0 iOS: spatial autocorrect experiment with Google Books models, plus accent and two-letter fixes (#2059)
* 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).
2026-11-20 16:18:07 +00:00

262 lines
10 KiB
Python
Executable File

#!/usr/bin/env python3
"""Builds a Spatial autocorrect model (HEXKeyboard/TypingModel/<lang>.hextm) from Google
Books Ngram v3 (2020-02-17, CC BY 3.0) word and word-pair counts, keeping only words a
word list knows: SCOWL (sizes up to 70) for English, RLA-ES (LibreOffice's es_ES and
es_MX Hunspell dictionaries, used under their MPL 1.1 option) for Spanish. Counts are summed over 1980-2019.
python3 -m venv /tmp/venv && /tmp/venv/bin/pip install spylls # Spanish only
/tmp/venv/bin/python scripts/build-typing-model.py es <workdir> HEXKeyboard/TypingModel/es.hextm
Needs about 7 GB free in <workdir> while it runs (English downloads ~240 GB of ngrams,
Spanish ~50 GB, each file deleted once counted) and a fast connection; every stage is
cached in <workdir>, so a rerun resumes. Deterministic for the same inputs.
Format v3 (little-endian), memory-mapped by TypingDecoder.swift:
"HXTM" u32 version=3, u32 words N, u32 pairs B, u32 blob bytes, u32 alphabet size A,
char[4] language
A x (u32 Unicode scalar, u8 code, u8 base code, u16 0) codes 1..A by scalar; base is
the unaccented letter's code (é -> e) or the letter's own
u32[N+1] word offsets into the blob (words sorted by code bytes), u8[N] word cost,
padding to 4, u32[N+1] first pair of each word, u32[B] second words (sorted within
each first word), u8[B] pair cost, blob (one code byte per letter)
Costs are -ln(p) in eighths of a nat, clamped to 255: P(word), and P(second | first).
"""
import gzip, math, multiprocessing, os, re, struct, subprocess, sys, tarfile, unicodedata, urllib.request
BASE = "https://storage.googleapis.com/books/ngrams/books/20200217"
FILES = {"en": ("eng", 24, 589), "es": ("spa", 3, 73)}
SCOWL = "https://downloads.sourceforge.net/project/wordlist/SCOWL/2020.12.07/scowl-2020.12.07.tar.gz"
RLA_ES = "https://raw.githubusercontent.com/LibreOffice/dictionaries/master/es/"
RLA_ES_LOCALES = ("es_ES", "es_MX")
FIRST_YEAR = 1980
MAX_WORDS = {"en": 90_000, "es": 110_000}
MAX_BYTES = 3_600_000 # the whole model
MIN_PAIR = 2_000 # pairs rarer than this (1980-2019) can't make the cut
LETTERS = {"en": "abcdefghijklmnopqrstuvwxyz'", "es": "abcdefghijklmnopqrstuvwxyzñáéíóúü"}
def urls(lang, n):
code, ones, twos = FILES[lang]
count = ones if n == 1 else twos
return [f"{BASE}/{code}/{n}-{i:05d}-of-{count:05d}.gz" for i in range(count)]
def fetch(url, path):
if not os.path.exists(path):
subprocess.run(["curl", "-sSfL", "--http1.1", "--retry", "8", "--retry-all-errors", "-o", path + ".part", url], check=True)
os.replace(path + ".part", path)
def lines(path):
proc = subprocess.Popen(["gzip", "-dc", path], stdout=subprocess.PIPE, bufsize=1 << 20)
yield from proc.stdout
proc.wait()
def years(fields):
total = 0
for f in fields:
y, c, _ = f.split(b",")
if int(y) >= FIRST_YEAR:
total += int(c)
return total
def lower(token):
if token.isascii():
return token.lower()
return token.decode("utf-8", "replace").lower().encode("utf-8")
def count_unigrams(job):
lang, url, work = job
out = os.path.join(work, "uni", os.path.basename(url) + ".tsv")
if os.path.exists(out):
return out
raw = os.path.join(work, "raw", os.path.basename(url))
fetch(url, raw)
word = re.compile(("^[" + LETTERS[lang] + "]+$").encode("utf-8"))
counts = {}
for line in lines(raw):
parts = line.rstrip(b"\n").split(b"\t")
w = lower(parts[0])
if b"_" in w or not word.match(w):
continue
counts[w] = counts.get(w, 0) + years(parts[1:])
with open(out + ".part", "wb") as f:
for w, c in counts.items():
if c:
f.write(w + b"\t" + str(c).encode() + b"\n")
os.replace(out + ".part", out)
os.remove(raw)
return out
VOCAB = set()
def load_vocab(path):
global VOCAB
VOCAB = {line.split("\t", 1)[0].encode("utf-8") for line in open(path, encoding="utf-8")}
def count_pairs(job):
lang, url, work = job
out = os.path.join(work, "bi", os.path.basename(url) + ".tsv")
if os.path.exists(out):
return out
raw = os.path.join(work, "raw", os.path.basename(url))
fetch(url, raw)
vocab = VOCAB
counts = {}
for line in lines(raw):
tab = line.find(b"\t")
ngram = line[:tab]
space = ngram.find(b" ")
a, b = lower(ngram[:space]), lower(ngram[space + 1:])
if a in vocab and b in vocab:
key = a + b" " + b
counts[key] = counts.get(key, 0) + years(line[tab + 1:].rstrip(b"\n").split(b"\t"))
with open(out + ".part", "wb") as f:
for k, c in counts.items():
if c >= MIN_PAIR // 4:
f.write(k + b"\t" + str(c).encode() + b"\n")
os.replace(out + ".part", out)
os.remove(raw)
return out
def word_list(lang, work):
"""The words the word list accepts, as a predicate on lowercase strings."""
if lang == "en":
path = os.path.join(work, "scowl.tar.gz")
fetch(SCOWL, path)
words = set()
with tarfile.open(path) as t:
for m in t.getmembers():
name = os.path.basename(m.name)
kind, _, size = name.rpartition(".")
if kind in ("english-words", "american-words", "british-words", "english-contractions") \
and size.isdigit() and int(size) <= 70:
for w in t.extractfile(m).read().decode("latin-1").split():
if w == w.lower():
words.add(w)
return words.__contains__
from spylls.hunspell import Dictionary
dictionaries = []
for locale in RLA_ES_LOCALES:
for ext in ("dic", "aff"):
fetch(f"{RLA_ES}{locale}.{ext}", os.path.join(work, f"{locale}.{ext}"))
dictionaries.append(Dictionary.from_files(os.path.join(work, locale)))
return lambda w: any(d.lookup(w) for d in dictionaries)
def check_words(args):
lang, work, words = args
accept = word_list(lang, work)
return [w for w in words if accept(w)]
def cost(p):
return max(0, min(255, round(-math.log(max(p, 1e-30)) * 8)))
def main(lang, work, out_path):
for d in ("raw", "uni", "bi"):
os.makedirs(os.path.join(work, d), exist_ok=True)
workers = int(os.environ.get("WORKERS", "12"))
with multiprocessing.Pool(workers) as pool:
uni_files = pool.map(count_unigrams, [(lang, u, work) for u in urls(lang, 1)])
counts = {}
for p in uni_files:
for line in open(p, "rb"):
w, c = line.rstrip(b"\n").split(b"\t")
counts[w] = counts.get(w, 0) + int(c)
total = sum(counts.values())
vocab_path = os.path.join(work, "vocab.tsv")
if not os.path.exists(vocab_path):
ranked = sorted(counts, key=lambda w: (-counts[w], w))[: MAX_WORDS[lang] * 4]
texts = [w.decode("utf-8") for w in ranked]
word_list(lang, work) # downloads the list once, before the workers read it
chunks = [texts[i::workers] for i in range(workers)]
with multiprocessing.Pool(workers) as pool:
ok = set().union(*map(set, pool.map(check_words, [(lang, work, c) for c in chunks])))
kept = [w for w in texts if w in ok][: MAX_WORDS[lang]]
with open(vocab_path, "w", encoding="utf-8") as f:
for w in kept:
f.write(f"{w}\t{counts[w.encode('utf-8')]}\n")
vocab = {}
for line in open(vocab_path, encoding="utf-8"):
w, c = line.rstrip("\n").split("\t")
vocab[w] = int(c)
with multiprocessing.Pool(workers, initializer=load_vocab, initargs=(vocab_path,)) as pool:
bi_files = pool.map(count_pairs, [(lang, u, work) for u in urls(lang, 2)])
pairs = {}
for p in bi_files:
for line in open(p, "rb"):
k, c = line.rstrip(b"\n").split(b"\t")
pairs[k] = pairs.get(k, 0) + int(c)
write_model(lang, vocab, total, pairs, out_path)
def write_model(lang, vocab, total, pairs, out_path):
scalars = sorted({c for w in vocab for c in w})
code = {c: i + 1 for i, c in enumerate(scalars)}
def base(c):
b = unicodedata.normalize("NFD", c)[0]
return code.get(b, code[c])
enc = {w: bytes(code[c] for c in w) for w in vocab}
words = sorted(vocab, key=lambda w: enc[w])
index = {w: i for i, w in enumerate(words)}
blob = b"".join(enc[w] for w in words)
fixed = 28 + 8 * len(scalars) + 4 * (len(words) + 1) + len(words) + 3 + 4 * (len(words) + 1) + len(blob)
budget = (MAX_BYTES - fixed) // 5
# Keep the pairs that tell the most over the single-word model (backoff 0.4):
# count x log(P(b | a) / (0.4 P(b))), positive only, best first, as many as fit.
scored = []
for k, c in pairs.items():
if c < MIN_PAIR:
continue
a, b = k.decode("utf-8").split(" ")
p = c / vocab[a]
gain = c * math.log(p / (0.4 * vocab[b] / total))
if gain > 0:
scored.append((gain, index[a], index[b], min(p, 1.0)))
scored.sort(reverse=True)
kept = sorted((a, b, p) for _, a, b, p in scored[:budget])
rows = [0] * (len(words) + 1)
for a, _, _ in kept:
rows[a + 1] += 1
for i in range(len(words)):
rows[i + 1] += rows[i]
offsets, at = [], 0
for w in words:
offsets.append(at)
at += len(enc[w])
offsets.append(at)
out = bytearray(b"HXTM")
out += struct.pack("<IIIII", 3, len(words), len(kept), len(blob), len(scalars))
out += lang.encode("ascii").ljust(4, b"\0")
for c in scalars:
out += struct.pack("<IBBH", ord(c), code[c], base(c), 0)
out += struct.pack(f"<{len(offsets)}I", *offsets)
out += bytes(cost(vocab[w] / total) for w in words)
out += b"\0" * (-len(out) % 4)
out += struct.pack(f"<{len(rows)}I", *rows)
out += struct.pack(f"<{len(kept)}I", *(b for _, b, _ in kept))
out += bytes(cost(p) for _, _, p in kept)
out += blob
with open(out_path, "wb") as f:
f.write(out)
print(f"{out_path}: {lang}, {len(words)} words, {len(kept)} pairs of {len(scored)} useful, "
f"{len(scalars)} letters, {len(out) / 1e6:.2f} MB")
if __name__ == "__main__":
if len(sys.argv) != 4 or sys.argv[1] not in FILES:
sys.exit(__doc__)
main(*sys.argv[1:])