3  Algorithms under the hood

This chapter explains why the package is built the way it is, not just what each function does (that’s Chapter 5). Skip it if you just want to call functions; read it if a benchmark number surprises you, or if you’re deciding whether to trust the package’s behaviour on a pattern or input shape you care about.

3.1 Regex, fixed literals, and a safety net

R’s default regex engine is TRE, which doesn’t support lookaround, possessive quantifiers, or atomic groups. perl = TRUE switches to PCRE, which does — at the cost of being a backtracking engine, which means certain patterns (nested quantifiers over ambiguous alternations, mainly) can exhibit catastrophic exponential-time backtracking on adversarial input.

fast.string uses PCRE2 for regex (full modern syntax, via Rcpp, not base::grepl(perl = TRUE)) and a prepared, byte-oriented searcher for the fixed = TRUE literal-matching path. The fixed pattern is prepared once per call: for searching, an empty pattern matches every non-NA string; a one-byte pattern uses memchr; two- and three-byte patterns use memchr followed by memcmp; and longer patterns use Boyer–Moore–Horspool. Case-insensitive fixed matching folds bytes through a precomputed 256-entry table as they are compared, so it doesn’t allocate a lowercased copy of every input. The pattern is never interpreted as regex syntax on this path, so there is no regex backtracking risk.

The catch with PCRE2 is that it remains a backtracking engine for genuine regex patterns. What fast.string adds is a syntax safety net, not a backtracking guarantee: every regex-accepting function scans the pattern for PCRE-only syntax before taking the fast regex path —

.has_pcre_only_syntax <- function(pattern) {
    base::grepl(
        paste0(
            "\\(\\?[=!]",       # (?= lookahead   (?! negative lookahead
            "|\\(\\?<[=!]",     # (?<= lookbehind  (?<! negative lookbehind
            "|\\(\\?>",         # (?> atomic group
            "|[*+?]\\+",        # *+  ++  ?+  possessive quantifiers
            "|\\(\\?P[=<]",     # (?P=  (?P<  named backref / group
            "|\\\\k[<']",       # \k<name>  \k'name'  named backreference
            "|\\(\\?R\\)",      # (?R) full-pattern recursion
            "|\\(\\?[0-9]",     # (?1) (?2) … numbered group recursion
            "|\\(\\?&"          # (?&name) named group recursion
        ),
        pattern, perl = TRUE
    )
}

— and if it finds any, and the caller didn’t explicitly pass perl = TRUE, the call transparently delegates to base::grepl()/ base::gsub() with perl = TRUE instead of running it through fast.string’s own PCRE2 path, with a cli::cli_inform() notice explaining why:

fgrepl("(?<=foo)bar", c("foobar", "bazbar"), perl = FALSE)

[1]  TRUE FALSE

This exists because fast.string’s PCRE2 binding and base R’s PCRE binding are two different code paths with two different sets of supported constructs at the edges — the safety net means a pattern either runs correctly on the fast path, or falls back to a path R has already battle- tested for that exact syntax. It never silently mismatches.

fcount() inherits the same net, plus one of its own. Counting means looping the match, so it also has to define what happens at the boundaries: matches are counted non-overlapping (fcount("aa", "aaaa") is 2), and an empty pattern — whose base R semantics are counted in characters, while the fixed engine works in bytes — is delegated to base::gregexpr() outright rather than answered in bytes for UTF-8 input.

3.2 Parallelism: RcppParallel, not parallel/future

parallel::mclapply() and future::plan(multisession) parallelise across R processes: each worker is a separate R session, so every call pays process-management and (for anything that isn’t fork-based) serialisation overhead — typically milliseconds at minimum, often more. That’s negligible if each task takes seconds; it dominates if each task is “trim this one string.”

fast.string instead uses RcppParallel’s parallelFor, which partitions a single C++ loop across an Intel TBB thread pool inside one R call, with no process boundary and no serialisation step — the per-call dispatch overhead is microseconds, not milliseconds. The trade-off is that this parallelism lives entirely inside the C++ implementation: it’s not something you can apply to arbitrary R code, only to the specific loops this package has written in C++.

Because even microsecond dispatch overhead isn’t free, every parallel function applies a size threshold before bothering: typically n >= 1000 elements for pairwise vector operations, n * m >= 10000 cells for matrix operations (jaro_winkler_matrix()). Below the threshold, the function just runs the loop on the calling thread — measurably faster than paying thread-pool dispatch cost for, say, ten comparisons. Chapter 6 shows this crossover explicitly with small-n timings.

Functions that expose nthreads treat it as a per-call cap, without changing RcppParallel’s process-wide options. NULL leaves scheduling to the RcppParallel default, an explicit value limits that call to at most that many threads, and nthreads = 1 runs strictly serially. Dispatch also limits concurrency to the useful work available, so asking for 16 threads doesn’t create 16-way overhead for a range with only a few useful chunks. String-utility, date, and phonetic functions preserve their public signatures and use the default scheduler for their own calls.

3.3 Jaro and Jaro-Winkler similarity

Jaro similarity between strings \(s_1\) (length \(l_1\)) and \(s_2\) (length \(l_2\)) is:

\[ \text{Jaro}(s_1, s_2) = \frac{1}{3}\left(\frac{m}{l_1} + \frac{m}{l_2} + \frac{m - t}{m}\right) \]

where \(m\) is the number of matching characters — characters common to both strings within a sliding window of \(\lfloor \max(l_1, l_2)/2 \rfloor - 1\) positions — and \(t\) is the number of transpositions (matched characters that appear in a different relative order) divided by two. Jaro-Winkler adds a bonus for a shared prefix (up to 4 characters), scaled by p (default 0.1, the standard value):

\[ \text{JW}(s_1, s_2) = \text{Jaro}(s_1, s_2) + \ell \cdot p \cdot (1 - \text{Jaro}(s_1, s_2)) \]

where \(\ell\) is the length of the common prefix, capped at 4. This is why jaro_winkler("SMITH", "SMYTH", p = 0.1) scores higher than the same pair with p = 0 — SM is a shared prefix that the Winkler boost rewards, on the reasoning that people are more likely to make typos later in a word than at the start.

The bit-parallel trick

The textbook Jaro algorithm, for each character in \(s_1\), linearly scans the matching window in \(s_2\) for the first unclaimed equal character — an \(O(l_1 \times \text{window})\) double loop. fast.string instead maintains, per worker thread, a 256-entry table of 64-bit bitmasks: char_mask[c] has bit \(j\) set if s2[j] == c. Finding the first unclaimed match for s1[i] then becomes:

uint64_t cand = char_mask[(unsigned char)s1[i]] & window_mask & ~used_mask;
if (cand) {
    int j = ctz64(cand);  // lowest set bit = leftmost match
    ...
}

— a handful of bitwise operations and one count-trailing-zeros instruction, replacing the inner linear scan entirely. This turns the \(O(l_1 \times \text{window})\) comparison into \(O(l_1 + l_2)\), and applies to any pair of strings up to 64 bytes each (covering the overwhelming majority of names and addresses). Longer strings fall back to a straightforward bool[]-array scalar implementation — still correct, just without the bitmask speedup.

The char_mask table itself is thread_local and persists across calls within a worker thread (only the handful of bytes actually touched per call get cleared afterward), so the steady-state per-call setup cost is \(O(l_2)\), not \(O(256)\).

Token-aware comparison: jaro_winkler_tokens()

Plain Jaro-Winkler compares strings as one ordered sequence of characters, so "Kyle John Haynes" vs. "John Kylie Haynes" scores badly — the characters moved, even though the words are almost all present. jaro_winkler_tokens() scores every pair two different ways and keeps whichever is higher:

1. Token alignment. Split both strings on whitespace, score every token in a against every token in b, then greedily pair off tokens in descending order of similarity (repeatedly pick the best remaining unused pair). This is a cheap approximation of an optimal bipartite assignment — not guaranteed optimal in the general case, but for the 2-5 tokens typical of a name or address, it agrees with the true optimum for all but pathological inputs. By default, the summed score divides by max(n_tokens_a, n_tokens_b), so missing/extra tokens dilute the result; the extra_penalty argument switches to a scheme that instead averages over only the matched tokens and subtracts a fixed penalty per unmatched token — see Chapter 5 for the worked example with a stray middle initial.
2. Collapsed. Both strings with whitespace removed, compared as one string. This catches cases where the only difference is where the token boundary falls — "OBrien" vs. "O Brien" — which token alignment alone would under-score (one token vs. two, diluting the average) even though they’re clearly the same name.

jaro_winkler_tokens("Kyle John Haynes", "John Kylie Haynes")  # token alignment wins

[1] 0.9844444

jaro_winkler_tokens("OBrien", "O Brien")                      # collapsed framing wins

[1] 1

Both framings reuse the same underlying Jaro-Winkler primitive and the same parallelised, per-row execution as jaro_winkler() itself — tokenising, building the token similarity matrix, the greedy assignment, and the collapsed comparison all happen in one C++ pass over the whole input vector.

3.4 Soundex and NYSIIS

Both are phonetic encoding schemes: they map a name to a short code such that names that sound alike (even if spelled differently) tend to map to the same code. They’re used as blocking keys — group records by phonetic code first, then only run the expensive Jaro-Winkler comparison within a group, instead of against every other record in the dataset.

Soundex (American/Census Bureau rules, implemented here) keeps the first letter verbatim, then maps the remaining consonants to digits (B,F,P,V → 1; C,G,J,K,Q,S,X,Z → 2; D,T → 3; L → 4; M,N → 5; R → 6), drops vowels, and pads/truncates to exactly 4 characters. Adjacent letters mapping to the same digit collapse to one — and H/W are transparent for that adjacency check, not just dropped. That transparency rule is the entire reason "Ashcraft" encodes as A261 and not A2261: the S and C are separated by an H, but H doesn’t break their adjacency, so they collapse to a single 2.

soundex(c("Ashcraft", "Ashcroft", "Robert", "Rupert"))

[1] "A261" "A261" "R163" "R163"

cat("fast.string::soundex:  ", fast.string::soundex("Ashcraft"), "(treats H as transparent)\n")

fast.string::soundex:   A261 (treats H as transparent)

cat("RecordLinkage::soundex:", RecordLinkage::soundex("Ashcraft"), "\n")

RecordLinkage::soundex: A226 

This H/W-transparency rule is exactly the kind of edge case where Soundex implementations genuinely disagree — some treat H/W as transparent (the canonical Census Bureau / Knuth TAOCP rule, and what fast.string follows), others drop them like any other consonant-adjacent vowel and get a different code for words like "Ashcraft". Neither is “more correct” in any normative sense — Soundex was never formally standardised down to this level of detail — but it’s worth knowing which rule a given package follows before assuming two Soundex columns from different tools are comparable.

NYSIIS is more aggressive: it applies leading/trailing letter transforms first (e.g. a name starting with MAC becomes MCC, one ending in a vowel + Y drops the Y), then a per-letter substitution table with adjacent-duplicate collapsing, then truncates to 6 characters. It tends to produce fewer false-positive collisions than Soundex on typical English surnames, at the cost of a heavier per-element rule table — which is the direct explanation for why nysiis() benchmarks slower than soundex() in Chapter 6 despite both running through the same parallel dispatch.

Refined Soundex and Cologne

Both are answers to the same complaint about classic Soundex — a four-character code is very coarse — from opposite directions.

Refined Soundex (the US-English mapping from Apache Commons Codec) keeps the first letter verbatim, then emits a class digit for every letter of the name — the first one included, and vowels included, which classic Soundex drops outright. Adjacent identical digits still collapse to one, but nothing is truncated or padded, so the code grows with the name. The mapping is nine consonant classes rather than Soundex’s six (B,P → 1; F,V → 2; C,K,S → 3; G,J → 4; Q,X,Z → 5; D,T → 6; L → 7; M,N → 8; R → 9), with vowels and H/W/Y sharing 0. "Robert" therefore encodes as R901096, not R163: two names must now agree in phonetic class at every position to collide, not just in their first three significant consonants.

Cologne phonetic (Kölner Phonetik, Postel 1969) is built for German rather than English. Its distinguishing feature for linkage work is explicit umlaut folding — Ä/Ö/Ü map to their base vowels and ß/ẞ to SS, decoded from UTF-8 before encoding — so "Müller" and "Mueller" reach the same code by rule rather than by accident. Every other scheme in this package is ASCII-oriented and simply skips the umlaut byte pair, which is why refined_soundex() gives "Müller" and "Mueller" different codes.

The practical consequence is block size. Over a list of surnames chosen to stress each scheme:

surnames <- c("Smith", "Smyth", "Schmidt", "Schmitt", "Sneath", "Sandy",
              "Robert", "Rupert", "Rubert", "Ashcraft", "Ashcroft",
              "Lee", "Law", "Loewe", "Baker", "Barker", "Hansen", "Hanson",
              "Jackson", "Jaxon", "Tymczak", "Pfister", "Meier", "Meyer",
              "Mayer", "Mueller", "Müller", "Miller", "Moller", "Malloy")

vapply(
    list(soundex = soundex, refined_soundex = refined_soundex,
         cologne = cologne, nysiis = nysiis),
    function(f) length(unique(f(surnames))),
    integer(1)
)

        soundex refined_soundex         cologne          nysiis 
             13              17              14              21 

More distinct codes over the same input means smaller blocks, fewer candidate pairs, and more missed matches — the recall/precision dial, in one number. Soundex puts all six of "Smith"/"Smyth"/"Schmidt"/"Schmitt"/"Sneath"/"Sandy" in a single block; Refined Soundex splits them three ways:

s <- c("Smith", "Smyth", "Schmidt", "Schmitt", "Sneath", "Sandy")
data.frame(name = s, soundex = soundex(s), refined = refined_soundex(s),
           cologne = cologne(s))

     name soundex refined cologne
1   Smith    S530  S38060     862
2   Smyth    S530  S38060     862
3 Schmidt    S530  S30806     862
4 Schmitt    S530  S30806     862
5  Sneath    S530  S38060     862
6   Sandy    S530  S30860     862

Neither setting is correct in the abstract. The strategy that usually works is to run more than one and union the candidate blocks, which buys a coarse scheme’s recall while keeping a fine scheme’s precision on the records the coarse one over-merges — Chapter 4 does exactly that with refined_soundex() and cologne() together.

Two cross-package notes, in the same spirit as the Soundex H/W disagreement above. Both matter if you are comparing a fast.string phonetic column against one produced by another tool.

• refined_soundex() does not truncate. phonics::refinedSoundex() caps the code at 10 characters by default (maxCodeLen = 10L), so long names produce a shorter, coarser key there. Raise maxCodeLen and the two agree exactly; leave it at the default and phonics will merge records this package keeps apart.
• Cologne’s specification leaves two rules open, and implementations read them differently. cologne() agrees with phonics::cologne() on the canonical reference names ("Müller-Lüdenscheidt", "Wikipedia", "Breschnew", the "Meier"/"Mayr"/"Maier"/"Meyer" group), but the two diverge on a few per cent of random uppercase strings — mainly where an H sits between two letters that code to the same digit. This package treats the skipped H as still separating them (cologne("BHB") is "11", and this is pinned in tests/testthat/test-phonetic-extended.R), where phonics collapses them to "1". phonics::cologne() also returns NA with a warning on umlauts rather than folding them.

As with Soundex, neither reading is normatively “correct” — the point is to know which one your column was built with before joining on it.

3.5 Double Metaphone and Caverphone

soundex()/nysiis() were designed around English/American surnames; double_metaphone() and caverphone() are the package’s answer for names that fall outside that design target.

Double Metaphone (Lawrence Philips, 2000) returns two codes per word — primary and secondary — because some spellings genuinely have more than one plausible pronunciation: a C could be a hard K sound or a soft S sound depending on context, a G could be hard or soft, and so on. Rather than guessing one and risking a missed match, the algorithm emits both, and two names are usually considered a phonetic match if any of one side’s codes equals any of the other’s. This package’s implementation is ported from the structure of the widely-used Apache Commons Codec Java implementation and cross-checked against its published unit-test vectors (tests/testthat/test-double_metaphone.R) rather than hand-derived, since the ruleset is large (dozens of context-sensitive branches per letter) and easy to get subtly wrong from a written description alone.

double_metaphone(c("Catherine", "Kathryn", "Smith", "Schmidt"))

  primary secondary
1    K0RN      KTRN
2    K0RN      KTRN
3     SM0       XMT
4     XMT       SMT

"Catherine"/"Kathryn" sharing a code despite no letters lining up positionally is the kind of match Soundex/NYSIIS — which work letter-by-letter from the start of the word — structurally can’t catch.

One implementation detail worth calling out: unlike soundex()/nysiis(), which strip the input down to letters only before encoding, Double Metaphone keeps internal whitespace and punctuation (only the ends are trimmed, and the text uppercased). The algorithm’s own rules key off literal multi-character fragments like "VAN "/"SAN "/"SCH", including the space — stripping it first would silently break those rules.

Caverphone 2.0 (Caversham Project, University of Otago, 2004) takes a completely different shape: instead of a branching per-letter ruleset, it’s a long fixed chain of substring transforms (originally specified as a sequence of regex replacements) — strip non-letters, handle a handful of silent-letter prefixes, replace c/q/x/v/d/b/z with their phonetic equivalents, collapse vowel runs to a placeholder digit, then clean up trailing consonants — always producing exactly 10 characters (padded with 1s). It was designed for, and is still widely used on, New Zealand electoral-roll names, but works as a general-purpose alternative blocking key anywhere. This package’s implementation is ported step-for-step from Apache Commons Codec’s Caverphone2 (again cross-checked against its published test vectors, tests/testthat/test-caverphone.R) including a documented quirk in the original 2004 specification — the "enough"/"trough" prefix rules are applied in an order that looks like a copy-paste duplication in the original paper — preserved here rather than “corrected”, since the point of implementing a named phonetic algorithm is to match what every other implementation of that algorithm produces.

caverphone(c("Peter", "Tedder", "Stevenson"))

[1] "PTA1111111" "TTA1111111" "STFNSN1111"

Trying more than one phonetic key (Soundex and NYSIIS and Double Metaphone and Caverphone, unioning the candidate blocks each produces) is a reasonable strategy when recall matters more than a small increase in block size — different rulesets group different near-miss spellings together, so one catches matches another misses.

3.6 Edit distance: Levenshtein, OSA, and Damerau-Levenshtein

levenshtein(), osa_distance(), and damerau_levenshtein() are classic distance metrics — minimum number of single-character edits to turn one string into another. The textbook algorithm is an \(O(l_1 \times l_2)\) dynamic-programming table; stringdist (and most other implementations) use exactly that.

levenshtein() instead uses Myers’ (1999) bit-vector algorithm: the same family of trick as this package’s bit-parallel Jaro (Chapter 3’s earlier section) — pack the shorter string’s character positions into 64-bit masks (one mask per distinct byte value), then scan the longer string against those masks using a handful of bitwise operations per character instead of an inner loop over the DP row. That turns the usual \(O(l_1 \times l_2)\) table into \(O(l_1)\) word operations whenever the shorter string fits in 64 bits — true for the overwhelming majority of names/addresses. Pairs where even the shorter string exceeds 64 bytes fall back to a conventional rolling-row DP.

osa_distance() additionally treats an adjacent-character transposition ("ab" → "ba") as a single edit rather than two substitutions — useful for typos, which are disproportionately adjacent swaps. There’s no equivalently compact bit-parallel formulation for the transposition case that this package implements, so it uses a three-rolling-row DP (transposition needs to look back two rows, not one, unlike plain Levenshtein’s one-row recurrence). This matches stringdist::stringdist(method = "osa"): no substring is edited more than once. damerau_levenshtein() uses the unrestricted Lowrance-Wagner recurrence, matching stringdist(method = "dl"); it tracks the last row in which each symbol occurred so multiple edits may involve the same substring.

levenshtein("kitten", "sitting")

[1] 3

osa_distance("ca", "abc")         # 3

[1] 3

damerau_levenshtein("ca", "abc")  # 2

[1] 2

The compatibility default is byte comparison. With use_bytes = FALSE, inputs are converted and validated as UTF-8 on the calling R thread, then workers compare immutable code-point arrays. ASCII inputs still use the original bit-parallel byte kernels. Code-point mode does not normalize canonically equivalent spellings and does not combine grapheme clusters.

3.7 Q-gram similarity: Jaccard, Dice, Tversky, cosine

A different family of similarity entirely: instead of an alignment between two character sequences, split each string into its overlapping length-q substrings (“q-grams” — bigrams for the default q = 2) and compare those. This is insensitive to where a difference occurs, which makes it a useful complementary signal to edit-distance-style metrics rather than a replacement for them.

jaccard_index(), dice_coefficient(), and tversky_index() all reduce to the same underlying triple — |A|, |B|, |A ∩ B| — combined three different ways:

• Jaccard: \(|A \cap B| / |A \cup B|\)
• Dice: \(2|A \cap B| / (|A| + |B|)\) — always \(\geq\) Jaccard for the same pair
• Tversky: \(|A \cap B| / (|A \cap B| + \alpha|A \setminus B| + \beta|B \setminus A|)\), which reduces to Jaccard at \(\alpha = \beta = 1\) and Dice at \(\alpha = \beta = 0.5\)

The speed advantage over stringdist::stringdist(method = "jaccard") comes from two things: for q-gram lengths up to 8 bytes (covering the default q = 2 and the overwhelming majority of practical use), each q-gram packs exactly into a uint64_t — one shift-and-OR per byte — so the q-gram set is built and deduplicated as plain sorted integers, with no string allocation and no hash table. stringdist instead tabulates q-grams generically (to support arbitrary q, including very long ones) through R-level dispatch per pair.

jaccard_index("night", "nacht")

[1] 0.1428571

dice_coefficient("night", "nacht")

[1] 0.25

Cosine: profiles, not sets

cosine_similarity() breaks the pattern above. The other three reduce each string to a set — a q-gram that occurs four times counts exactly as much as one that occurs once. Cosine keeps the counts, treats each string as a vector in q-gram space, and returns the cosine of the angle between them:

\[\cos(A, B) = \frac{\sum_g A_g B_g}{\sqrt{\sum_g A_g^2}\sqrt{\sum_g B_g^2}}\]

where \(A_g\) is the number of times q-gram \(g\) occurs in the first string. Implementation-wise this is the same sorted-packed-integer machinery, with one change: the q-gram vector is sorted but not deduplicated, and the merge pass counts run lengths on each side to accumulate \(\sum A_g^2\), \(\sum B_g^2\), and the dot product in a single sweep. Where the set metrics normalise by set sizes, cosine normalises by the product of the two profile magnitudes.

a <- c("aaaa", "BANANA", "night")
b <- c("aaab", "BANANAS", "nacht")
data.frame(a, b,
           jaccard = jaccard_index(a, b),
           dice    = dice_coefficient(a, b),
           cosine  = cosine_similarity(a, b))

       a       b   jaccard      dice    cosine
1   aaaa    aaab 0.5000000 0.6666667 0.8944272
2 BANANA BANANAS 0.7500000 0.8571429 0.9486833
3  night   nacht 0.1428571 0.2500000 0.2500000

"aaaa" and "aaab" share exactly one of two distinct bigrams, so Jaccard reports 0.5 and cannot say more. Cosine sees three occurrences of "aa" against two and scores the pair far higher. Which behaviour you want is a data question: for names, near-duplicate q-grams are rare and the metrics mostly agree; for the numeric identifiers, codes, and padded fields that sit alongside names in a linkage file, repetition is the norm and the set metrics are throwing away most of the signal.

Because they are computed from different information, cosine and Jaro-Winkler make a reasonable pair of features for a linkage decision — Chapter 4 scores candidates on both and treats a wide disagreement between them as something to look at rather than average away.

3.8 fuzzywuzzy-style ratios: Ratcliff/Obershelp matching blocks

fuzz_ratio(), fuzz_partial_ratio(), fuzz_token_sort_ratio(), and fuzz_token_set_ratio() port Python’s fuzzywuzzy package — useful when migrating a matching pipeline from Python, or when you specifically want fuzzywuzzy’s flavour of scoring rather than edit distance or Jaro-Winkler.

The core of all four is the Ratcliff/Obershelp algorithm — the same algorithm behind Python’s difflib.SequenceMatcher, which is what fuzzywuzzy itself falls back to whenever the optional python-Levenshtein C extension isn’t installed (this package implements that always-available reference behaviour, not the optional Levenshtein-based shortcut). It works by recursively finding the longest common contiguous matching block between two strings, then recursing into the unmatched left and right remainders on each side — repeating until no more matches are found. The total length of every matched block, M, gives a similarity ratio of 2*M / (len(a) + len(b)). This is a meaningfully different notion of “similar” from edit distance: it rewards long shared runs rather than penalising every single-character difference equally, so a short insertion in the middle of an otherwise-identical string costs far less here than under Levenshtein.

fuzz_ratio("this is a test", "this is a test!")

[1] 100

fuzz_partial_ratio("fuzzy wuzzy was a bear", "wuzzy fuzzy was a bear")

[1] 91

fuzz_partial_ratio() builds on the same matching-blocks primitive: align the shorter string against every position the longer one offers (via those same matching blocks) and keep the best full-ratio alignment — useful when one string is plausibly a true substring of the other, padded with unrelated text on either side. fuzz_token_sort_ratio() and fuzz_token_set_ratio() layer tokenisation on top (sort-and-rejoin, or set-intersection-and-leftovers respectively) before running the same ratio underneath, the same way jaro_winkler_tokens() layers tokenisation on top of plain Jaro-Winkler.

3.9 Fast, fixed-format dates

format_date()/fas.Date() deliberately don’t replicate base::format.Date()/base::as.Date()’s full generality. Base R’s date functions go through strptime()/strftime(), which are locale-aware and support arbitrary %-format strings — flexibility that costs real time when you’re formatting the same fixed shape (say, ISO YYYY-MM-DD) for five million rows. fast.string’s date functions instead support exactly four fixed formats (iso, compact, dmy, ymd_slash) implemented as direct digit-to-character writes with zero-padding — no locale lookup, no calendar-math beyond what’s needed to validate month (1-12) and day (1-31) ranges. There’s deliberately no days-in-month or leap-year check, so fas.Date("2024-02-30", "iso") parses without error — trading strictness for speed, on the assumption that upstream data has already been validated or that downstream code will catch the implausible date some other way. If you need full calendar validation, base::as.Date() is still the right tool; fas.Date() is for when you already trust the input shape and just want it parsed fast.

Timestamps: fas.POSIXct() and format_datetime()

The timestamp pair applies the same fixed-shape principle one level up. base::as.POSIXct() carries the same locale-aware strptime() machinery as as.Date(), plus timezone resolution on top. fas.POSIXct() works entirely in UTC seconds since the epoch, converting the calendar fields arithmetically, and supports exactly four shapes (iso, rfc3339, compact, iso_offset).

Two design choices are worth knowing before relying on them.

These functions validate more than the date functions, not less. Where fas.Date() checks only that month and day fall in range, fas.POSIXct() validates the full calendar — days-in-month and leap years included — and returns NA for anything impossible. The asymmetry is deliberate: a timestamp column is usually a load/event stamp that a pipeline reasons about (ordering, watermarks, retention windows), so a silently rolled-over value is a worse failure there than in a date-of-birth field that a human will eyeball.

fas.Date("2023-02-29", "iso")        # rolls over

[1] "2023-03-01"

fas.POSIXct("2023-02-29 00:00:00")   # NA

[1] NA

"iso_offset" is an offset, not a timezone. On input, an offset is subtracted to normalise the value to UTC; on output, format_datetime() adds one fixed offset to every element. There is no daylight-saving rule anywhere in this path, and no zone name is ever resolved. For stamping a batch whose offset you know, that is exactly right and very cheap. For a series that crosses a DST boundary, or for anything that must round-trip through a named zone like "Australia/Sydney", use base::format() and base::as.POSIXct() — this is a case where the fast version isn’t a drop-in replacement, it’s a different (narrower) contract.

fas.POSIXct("2024-06-18T09:15:00+10:00", "iso_offset")   # stored as UTC

[1] "2024-06-17 23:15:00 UTC"

format_datetime(fas.POSIXct("2024-06-18 09:15:00"),
                "iso_offset", offset = "+10:00")          # written back out

[1] "2024-06-18T19:15:00+10:00"