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).
262 lines
10 KiB
Python
Executable File
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:])
|