App search & fuzzy matching

Matching apps by name

Typing in the drawer matches app names loosely, not only from the start of the name. Matches are ranked in six tiers, from strictest to most forgiving: an exact match ranks highest, then a match on the start of the full title, then a match on the start of any single word within the title (“sheets” finds Google Sheets, “store” finds Play Store), then a match against the title’s initials (“pm” finds Play Music), then an in-order match — where the letters you typed appear in the title in order, even with other letters in between (“gsheets” still finds Google Sheets) — and finally a typo-tolerant match as the last resort. The typo-tolerant tier catches swapped adjacent letters and other small slips, but only on longer queries, since a short query matches too much of the app list by chance otherwise.

tier(query, app_name) =
    exact          if query equals app_name
    title_prefix   if app_name starts with query
    word_prefix    if a word in app_name starts with query    # "sheets" → Google Sheets
    initials       if app_name's word initials start with query  # "pm" → Play Music
    subsequence    if every letter of query appears in app_name, in order
    typo_tolerant  if allowed_edits(query) ≥ edits_needed(query, app_name)
    no_match       otherwise

allowed_edits(query) =
    0   if length(query) < 4       # tier does not run at all
    1   if 4 ≤ length(query) ≤ 7
    2   if length(query) ≥ 8

# edits_needed is distance to the start of app_name, or to the start of any
# word in it — not to the whole name — so "chorme" still matches "Chrome Beta"

Limits

A query under four characters gets no typo tolerance at all — “cat” won’t find “Cap,” even though a single substituted letter would otherwise be within budget. App matches are ordered by name score alone, never by how often you launch an app.