Skip to content

stdlib.text

Text: Diff

Generated from v0.60.1. 3 source files, 42 documented symbols.

diff.xi

type DiffOp

A diff operation. data encodes the operation as "<op>:<text>" where <op> is = (equal/kept), + (insert/added) or - (delete/removed). A single string field is used because multi-field structs returned inside vectors mislay their fields when crossing module boundaries in this build; use diffop_kind/diffop_text to decode.

Field Type
data Str

Derives: Clone

fn diffop_kind(op: DiffOp) -> Str

Read the operation kind of a DiffOp ("eq", "ins" or "del"). Complexity: O(1).

fn diffop_text(op: DiffOp) -> Str

Read the operation text of a DiffOp. Complexity: O(len(data)).

fn diffop_kind_at(ops: &Vec[DiffOp], i: Int) -> Str

Read the operation kind of element i of a diff result. This reads the Vec's backing memory directly, so it is reliable for cross-module results (passing a DiffOp by value can mislay its layout in this build). Complexity: O(1).

fn diffop_text_at(ops: &Vec[DiffOp], i: Int) -> Str

Read the operation text of element i of a diff result. Complexity: O(len(data)).

fn diff_myers(a: &Vec[Str], b: &Vec[Str]) -> Vec[DiffOp]

Compute an optimal line diff with the longest-common-subsequence method (equivalent result to Myers' algorithm for the edit script). Complexity: O(|a| * |b|).

fn diff_myers_lines(a: Str, b: Str) -> Vec[DiffOp]

Split a and b into lines and diff them. Complexity: O(|a| * |b|) over the line counts.

fn diff_lcs(a: &Vec[Str], b: &Vec[Str]) -> Vec[DiffOp]

Compute a diff via the longest common subsequence. Complexity: O(|a| * |b|).

fn diff_unified(a: Str, b: Str, context: Int) -> Str

Render a unified diff of the lines of a and b. context is reserved (a single hunk covering the whole change is emitted; context-line trimming is not applied). The header uses --- a / +++ b. Complexity: O(|a| * |b|) for the diff plus O(ops) rendering.

fn diff_patch(a: Str, b: Str) -> Str

Render a compact patch text from a to b: one line per operation with a - / + / prefix. Diffable with diff_apply. Complexity: O(|a| * |b|).

fn diff_apply(a: Str, patch: Str) -> Result[Str, Str]

Apply a patch produced by diff_patch to a. Returns Err on a malformed patch or a context/deletion mismatch. Complexity: O(|patch lines| * |a lines|).

fn diff_similarity(a: Str, b: Str) -> Float64

Normalized similarity in [0,1]: length of the longest common byte subsequence divided by the longer input. Complexity: O(|a| * |b|).

fn diff_ratio(a: Str, b: Str) -> Float64

2 * matches / (len_a + len_b) where matches is the longest common byte subsequence length. Returns 1.0 when both inputs are empty. Complexity: O(|a| * |b|).

fn diff_word_level(a: Str, b: Str) -> Vec[DiffOp]

Diff a and b tokenized into words (alphanumeric runs and punctuation characters). Complexity: O(|tokens|^2).

fn diff_byte_level(a: &Vec[UInt8], b: &Vec[UInt8]) -> Vec[DiffOp]

Diff two byte sequences. Complexity: O(|a| * |b|).

similarity.xi

fn levenshtein(a: Str, b: Str) -> Int

Levenshtein edit distance between a and b (insertions, deletions, substitutions each cost 1). Classic two-row DP; ASCII byte comparison. Complexity: O(|a| * |b|) time, O(|b|) space.

fn damerau_levenshtein(a: Str, b: Str) -> Int

Damerau-Levenshtein distance using the optimal string alignment (OSA) variant: one transposition of adjacent characters counts as one edit. Two-row DP plus the row two steps back for the transposition term. Complexity: O(|a| * |b|) time, O(|b|) space.

fn jaro(a: Str, b: Str) -> Float64

Jaro similarity in [0, 1]. Match window is floor(max(|a|,|b|)/2) - 1 (clamped to 0); transpositions are mismatched match pairs divided by 2. Returns 0.0 when there are no matches (including empty inputs).

fn jaro_winkler(a: Str, b: Str) -> Float64

Jaro-Winkler similarity: Jaro plus a prefix bonus of prefix_len * 0.1 * (1 - jaro), where prefix_len is capped at 4 and at the length of the shorter string.

fn ngram_similarity(a: Str, b: Str, n: Int) -> Float64

Jaccard similarity over the set of character n-grams (as djb2 hash codes) of a and b. Returns 0.0 when either side has no n-grams. O(|a|*|b|).

fn cosine_similarity(a: Str, b: Str) -> Float64

Cosine similarity over per-character frequency vectors. Character-level (unigram) frequencies are used -- rather than bigram frequencies -- so that words sharing letters but no bigrams (e.g. "hello" and "world") still score a non-zero, sub-1 similarity. Returns 0.0 when either vector has zero length.

  • Precondition: true
fn longest_common_subsequence(a: Str, b: Str) -> Int

Length of the longest common subsequence of a and b. Two-row DP. Complexity: O(|a| * |b|) time, O(|b|) space.

fn longest_common_substring(a: Str, b: Str) -> Int

Length of the longest common contiguous substring of a and b. Two-row DP, resetting to 0 on mismatch. O(|a| * |b|) time, O(|b|) space.

fn hamming(a: Str, b: Str) -> Option[Int]

Hamming distance: number of differing byte positions. Returns None when the byte lengths differ; Some(0) for empty == empty.

fn metaphone(word: Str) -> Str

Metaphone-LITE: a deliberately simplified Metaphone variant (it is NOT guaranteed to match the real Metaphone algorithm). Uppercases the input, keeps the first letter (with a few start-of-word rules), drops vowels, maps the remaining consonants, then removes consecutive duplicate codes and any H/W that are not the leading letter.

fn soundex(word: Str) -> Str

Classic American Soundex code: keeps the first letter (uppercased), maps the remaining letters to digit codes, drops adjacent duplicates (same code as the previously emitted code) unless separated by a vowel, then pads with '0' to exactly 4 characters.

fn ngram_extract(s: Str, n: Int) -> Vec[Str]

All contiguous n-grams of s (n = 1 -> single chars). Empty input or n < 1 -> empty Vec. O(len) with O(len) output.

fn jaccard_similarity(a: Str, b: Str, n: Int) -> Float64

Jaccard similarity over n-grams: |A & B| / |A | B| in Float64 (0 when both inputs have no n-grams, 1 when identical). O(|a|-|b|) naive set comparison -- the compiler's Set is not usable for Str elements here.

fn longest_common_prefix(a: Str, b: Str) -> Int

Length of the longest common prefix of a and b. O(min(|a|,|b|)).

fn longest_common_suffix(a: Str, b: Str) -> Int

Length of the longest common suffix of a and b. O(min(|a|,|b|)).

transliterate.xi

fn transliterate(s: Str) -> Str

Best-effort transliteration of s to Latin script: strips accents and maps known scripts (Cyrillic, Greek, Arabic, Hebrew, Devanagari, kana, hangul and a few CJK characters). Complexity: O(len(s)).

fn transliterate_cyrillic(s: Str) -> Str

Transliterate Cyrillic text to Latin. Complexity: O(len(s)).

fn transliterate_greek(s: Str) -> Str

Transliterate Greek text to Latin. Complexity: O(len(s)).

fn transliterate_arabic(s: Str) -> Str

Transliterate Arabic text to Latin (best-effort; see header). Complexity: O(len(s)).

fn transliterate_hebrew(s: Str) -> Str

Transliterate Hebrew text to Latin (best-effort; see header). Complexity: O(len(s)).

fn transliterate_devanagari(s: Str) -> Str

Transliterate Devanagari text to Latin (best-effort; see header). Complexity: O(len(s)).

fn transliterate_chinese_pinyin(s: Str) -> Str

Convert Chinese characters to pinyin where known (only a few characters map; everything else passes through). Complexity: O(len(s)).

fn transliterate_japanese_romaji(s: Str) -> Str

Convert Japanese kana to romaji (best-effort; see header). Complexity: O(len(s)).

fn transliterate_korean_roman(s: Str) -> Str

Romanize Korean hangul (best-effort; see header). Complexity: O(len(s)).

fn transliterate_accented(s: Str) -> Str

Strip accents from Latin letters (e -> e, u -> u, ...). Complexity: O(len(s)).

fn transliterate_to_ascii(s: Str) -> Str

Reduce any script to a pure ASCII approximation: accent stripping plus the script tables (Cyrillic, Greek, Arabic, Hebrew, Devanagari, kana, hangul, CJK). Unmapped characters pass through unchanged. Complexity: O(len(s)).

fn transliterate_custom(s: Str, table: &Vec[(Char, Str)]) -> Str

Apply a custom transliteration table; each tuple is (char, replacement). Characters in s matching a table char are replaced; everything else is kept unchanged. Complexity: O(len(s) * table).