Skip to main content

Add place autocomplete

Outcome. A search box returns ranked place completions as the user types, served from a file you already have, with a measured per-keystroke cost.

Autocomplete here completes place namestoponymA proper name for a geographic place. — localities, boroughsboroughAn administrative or historical division of a city — e.g. the five boroughs of New York City. May be postal, legal, or both, and complicates the locality hierarchy., counties, neighborhoods — from a finite-state transducerFST (finite-state transducer). A compact automaton that reads an input sequence and emits an output sequence. Mailwoman encodes gazetteer names and street affixes as FSTs for fast prefix matching and prior injection without search overhead. built over the gazetteergazetteerA geographical index that maps place names and postcodes to real-world coordinates. Mailwoman uses a custom-built Who's On First (WOF) SQLite database as its gazetteer — the 'atlas' half of the grammar/atlas architecture.. It does not complete streetstreetThe named linear feature along which house numbers are ordered. Decomposes into a name plus street affixes; one of the Tier 2 fine labels. addresses or house numbers, and it is a different index from the one forward geocodinggeocodingThe process of converting an address into geographic coordinates (latitude and longitude). Mailwoman geocodes in a multi-tier cascade: exact address-point match → street interpolation → locality centroid. Each tier is progressively coarser but more widely available. uses.

Prerequisites​

  • The library install from Install and first parse. The FSTFST (finite-state transducer). A compact automaton that reads an input sequence and emits an output sequence. Mailwoman encodes gazetteer names and street affixes as FSTs for fast prefix matching and prior injection without search overhead. ships inside @mailwoman/neural-weights-en-us as fst-en-us.bin, 21.8 MB, so you already have it.
  • @mailwoman/resolver-wof-sqlite for the library path. The autocomplete functions live on deep subpaths of that package rather than on its root — see step 2.
  • No gazetteergazetteerA geographical index that maps place names and postcodes to real-world coordinates. Mailwoman uses a custom-built Who's On First (WOF) SQLite database as its gazetteer — the 'atlas' half of the grammar/atlas architecture. database. The FSTFST (finite-state transducer). A compact automaton that reads an input sequence and emits an output sequence. Mailwoman encodes gazetteer names and street affixes as FSTs for fast prefix matching and prior injection without search overhead. is self-contained.

1. Try it from the command line​

The CLI needs to be told where the FSTFST (finite-state transducer). A compact automaton that reads an input sequence and emits an output sequence. Mailwoman encodes gazetteer names and street affixes as FSTs for fast prefix matching and prior injection without search overhead. is. Its built-in default is a staging path that will not exist on your machine, so pass --fst or set $MAILWOMAN_FST_BIN:

export MAILWOMAN_FST_BIN="$PWD/node_modules/@mailwoman/neural-weights-en-us/fst-en-us.bin"
npx mailwoman autocomplete "san franc" --limit 5
 1. San Francisco [+francisco]  (locality, wof:85922583, imp:0.6901)
 2. San Francisco [+francisco]  (county, wof:102087579, imp:0.6901)
 3. San Francisco Township [+francisco]  (localadmin, wof:404511703, imp:0.0641)
 4. San Francisco [+francisco]  (locality, wof:1125799349, imp:0.0000)
 5. San Francisco Plaza [+francisco plaza]  (locality, wof:1226462397, imp:0.0000)

[+francisco] is the completion the FSTFST (finite-state transducer). A compact automaton that reads an input sequence and emits an output sequence. Mailwoman encodes gazetteer names and street affixes as FSTs for fast prefix matching and prior injection without search overhead. supplied for the partial tokentokenOne word or subword in the tokenized input. For the neural classifier, tokens come from SentencePiece (subword units); for the rule classifiers, tokens are whitespace- and punctuation-separated words. you typed. imp is the place's importance scoreimportance scoreA precomputed per-place prominence score (blending Wikipedia importance with population) used to rank same-name gazetteer candidates., which is the ranking key — results come back importance-descending.

--json emits the same list as an array of { name, placetype, wofID, importance, completionTokens }, which is the shape to build a dropdown from.

One correction to the tool's own error text: if the FSTFST (finite-state transducer). A compact automaton that reads an input sequence and emits an output sequence. Mailwoman encodes gazetteer names and street affixes as FSTs for fast prefix matching and prior injection without search overhead. is missing, it tells you to run mailwoman fst build. There is no such command. The builder is mailwoman gazetteer build fst, and you should not need it — the shipped file is the same artifact.

Three functions, all on deep subpaths of @mailwoman/resolver-wof-sqlite. They are not re-exported from the package root, so import them by subpath:

import { readFileSync } from "node:fs"

import { resolveWeights } from "@mailwoman/neural/weights"
import { autocomplete } from "@mailwoman/resolver-wof-sqlite/fst-autocomplete"
import { deserializeFST } from "@mailwoman/resolver-wof-sqlite/fst-serialize"

// resolveWeights finds the installed weights package, so you never hard-code a node_modules path.
// It is synchronous — there is nothing to await.
const { fstPath } = resolveWeights({ locale: "en-US" })

// fstPath is optional: it is only set when the index file is actually present in the resolved
// package, so a weights bundle without one gives you `undefined` rather than an error.
if (!fstPath) throw new Error("no FST index in the resolved weights package — autocomplete is unavailable")

// Deserialize once, at startup. The returned object IS the matcher — do not wrap it.
const fst = deserializeFST(readFileSync(fstPath))

export function suggest(query) {
	return autocomplete(fst, query, { maxSuggestions: 10, dedupeByName: true }).suggestions
}

deserializeFST returns the matcher directly. Wrapping its result in new FSTMatcher(...) produces an object that answers every query with zero suggestions and no error, which is a long afternoon.

dedupeByName: true is what a dropdown wants and is off by default. It collapses same-name places to the highest-importance one:

dedupeByName: false
  Brooklyn (borough, imp 0.806)
  Brookline (locality, imp 0.431)
  Brookline (localadmin, imp 0.429)
  Brooklyn (neighbourhood, imp 0.364)
  Brooklyn Center (locality, imp 0.359)
dedupeByName: true
  Brooklyn (borough, imp 0.806)
  Brookline (locality, imp 0.431)
  Brooklyn Center (locality, imp 0.359)
  Brooklyn Heights (neighbourhood, imp 0.318)
  Brookleigh (neighbourhood, imp 0.297)

Five slots showing three distinct places, or five. The CLI leaves it off because a person auditing the gazetteergazetteerA geographical index that maps place names and postcodes to real-world coordinates. Mailwoman uses a custom-built Who's On First (WOF) SQLite database as its gazetteer — the 'atlas' half of the grammar/atlas architecture. wants to see that New York is both a citylocalityThe city / town / settlement component of an address: a populated place sitting between region and neighborhood in the hierarchy. and a county.

3. Measure the keystroke cost​

Load is once and cheap. Queries are not uniformly cheap, and the spread between the cheapest and the dearest keystroke is three orders of magnitude. Measure it before you decide whether to debounce:

node autocomplete-bench.mjs
load 0.26 s   rss 265 MB
keystroke shape        n     p50 µs   p95 µs
complete token         760          8        67
partial first token    680       8370     10512
partial later token    400          6        19

Measured on an AMD Ryzen 9 8945HS, 16 logical cores, Node.js 26.2.0, mailwoman 8.7.0, over every keystroke of four typed queries (san francisco, brooklyn, washington dc, cambridge ma), 40 samples per prefix, after a warm-up pass. The machine was shared, so treat these absolutes as one host's figures: your numbers will differ, and the ratios below are what transfers. Resident set after load moved between 241 MB and 293 MB across runs, so read that one as a scale rather than a constant.

Three shapes, and the middle one is the whole story:

  • Complete tokentokenOne word or subword in the tokenized input. For the neural classifier, tokens come from SentencePiece (subword units); for the rule classifiers, tokens are whitespace- and punctuation-separated words. — what you typed is a whole word the index knows (san, brook). The walk lands on a state and reads its entries. 8 µs.
  • Partial later tokentokenOne word or subword in the tokenized input. For the neural classifier, tokens come from SentencePiece (subword units); for the rule classifiers, tokens are whitespace- and punctuation-separated words. — a complete first word plus a fragment (san fr, washington d). The walk fails, so the code walks the complete prefix and prefix-filters that state's continuation edges. That state has 100 of them. 6 µs.
  • Partial first tokentokenOne word or subword in the tokenized input. For the neural classifier, tokens come from SentencePiece (subword units); for the rule classifiers, tokens are whitespace- and punctuation-separated words. — a fragment and nothing else (sa, br, brookl). The same prefix-filter runs, but the state is the root, and the root has 53,904 continuation edges. Every one is scanned. 8.4 ms.

So the expensive keystrokes are the first few of the first word, and the cost collapses the moment a space is typed.

Size those two costs against a parseaddress parsingThe process of decomposing a free-text postal address string into structured components — house number, street name, locality, region, postcode, and country — so a geocoder can resolve them to coordinates. rather than against a clock, because the ratio is what survives a change of machine. classifier.parse over the same twenty addresses on the same host, same session, measured p50 6,086 µs. So a complete-tokentokenOne word or subword in the tokenized input. For the neural classifier, tokens come from SentencePiece (subword units); for the rule classifiers, tokens are whitespace- and punctuation-separated words. completion is roughly three orders of magnitude cheaper than one parseaddress parsingThe process of decomposing a free-text postal address string into structured components — house number, street name, locality, region, postcode, and country — so a geocoder can resolve them to coordinates., and a partial-first-tokentokenOne word or subword in the tokenized input. For the neural classifier, tokens come from SentencePiece (subword units); for the rule classifiers, tokens are whitespace- and punctuation-separated words. completion costs about as much as one parseaddress parsingThe process of decomposing a free-text postal address string into structured components — house number, street name, locality, region, postcode, and country — so a geocoder can resolve them to coordinates.. Those two statements are the design input: the index is nearly free to query except at the root, where it is a modelneural classifierThe machine learning model at the core of Mailwoman's parser — a transformer encoder (~30M parameters) trained from scratch to do BIO token classification over addresses. It learns the 'grammar' of address formats; the gazetteer supplies the 'atlas.'-sized cost.

Two consequences for the front end follow from the ratio, not from the microseconds. Debounce input rather than querying on every keydown, since the root-scan keystrokes are the ones a fast typist generates most of. And keep the query off the main threadthreadA parallel workstream within a release. Threads compose; they are not sequential milestones like phases. of a browser tab: on this host 8.4 ms is more than a frame at 60 Hz, and on a slower one the margin only widens.

Verify​

npx mailwoman autocomplete "brookl" --limit 3 --json
[
  {
    "name": "Brooklyn",
    "placetype": "borough",
    "wofID": 421205765,
    "importance": 0.8064998388290405,
    "completionTokens": [
      "brooklyn"
    ]
  },
  {
    "name": "Brookline",
    "placetype": "locality",
    "wofID": 85950817,
    "importance": 0.4307776987552643,
    "completionTokens": [
      "brookline"
    ]
  },
  {
    "name": "Brookline",
    "placetype": "localadmin",
    "wofID": 404476429,
    "importance": 0.42851021885871887,
    "completionTokens": [
      "brookline"
    ]
  }
]

Every suggestion carries a wofID. That is the Who's On FirstWOF (Who's On First). An open-source gazetteer of places maintained by Mapzen/whosonfirst. Mailwoman builds a custom SQLite database from WOF GeoJSON repos, extended with postcode data, importance scores, and coincident-role relations. identifier, so a selected suggestion can be resolved to coordinates and a hierarchy without a second text query — which is the point of building the dropdown on this index rather than on repeated geocodes.

Limits​

  • Places only. No streetsstreetThe named linear feature along which house numbers are ordered. Decomposes into a name plus street affixes; one of the Tier 2 fine labels., no house numbershouse numberThe numeric or alphanumeric identifier of a building on a street. Mailwoman's house_number component; its position relative to the street name flips between locales., no points of interest. A user typing 1275 Pennsylv gets nothing useful from this index.
  • One localelocaleThe combination of language and country an address comes from. en-US and fr-FR are the locales Mailwoman ships weights for. per file. fst-en-us.bin ships with the en-US weightsparameterA single learned number inside a model — one weight or bias. Mailwoman's encoder has roughly 30 million of them; training is the search for good values.; @mailwoman/neural-weights-fr-fr carries its own. There is no cross-localelocaleThe combination of language and country an address comes from. en-US and fr-FR are the locales Mailwoman ships weights for. merge, so a multi-market box loads several and merges the result lists itself.
  • Resident set is a few hundred megabytes after load — 241 MB to 293 MB across the runs above — and the file is memory-resident rather than memory-mapped. One process per localelocaleThe combination of language and country an address comes from. en-US and fr-FR are the locales Mailwoman ships weights for. is the budget to plan against.
  • Ranking is importance, not proximity. There is no near parameterparameterA single learned number inside a model — one weight or bias. Mailwoman's encoder has roughly 30 million of them; training is the search for good values.. A user in Boston typing brookl gets Brooklyn first because Brooklyn is more important, not because it is closer. Re-rank on your side with the coordinates the wofID resolves to.
  • The CLI's default FSTFST (finite-state transducer). A compact automaton that reads an input sequence and emits an output sequence. Mailwoman encodes gazetteer names and street affixes as FSTs for fast prefix matching and prior injection without search overhead. path is a staging directory. Set $MAILWOMAN_FST_BIN in any environment where you rely on the command.