String Similarity Metric

Edit distance metrics measure the minimum number of single-character operations required to transform one string into another. Levenshtein distance permits insertions, deletions, and substitutions, each with a uniform cost of 1. Damerau-Levenshtein adds transposition of adjacent characters, making it robust to common typing errors. These metrics are foundational for fuzzy string matching in ontology alignment, where minor spelling variations or morphological differences must be bridged. The computational complexity of O(n·m) using dynamic programming makes them practical for pairwise label comparison at scale.

Token-based metrics operate on sets of words or n-grams rather than individual characters. The Jaccard coefficient computes the ratio of intersection to union of token sets, while Dice's coefficient gives twice the intersection over the sum of set sizes. Overlap coefficient normalizes by the smaller set, making it sensitive to subset relationships. These metrics are particularly effective for multi-word entity labels where word order may vary. Preprocessing steps like lowercasing, stop word removal, and stemming significantly impact results by reducing surface-form variation.

N-gram metrics decompose strings into overlapping subsequences of length n, then compare the resulting sets. Character trigrams (n=3) capture sub-word patterns and are resilient to word reordering and minor spelling variations. The q-gram distance counts the number of n-grams not shared between strings. This approach bridges the gap between character-level and token-level methods, making it effective for matching abbreviated forms and acronyms. Common implementations use n=2 (bigrams) or n=3 (trigrams) with padding characters at string boundaries to weight prefixes and suffixes.

Raw similarity scores must be normalized to a consistent range and compared against acceptance thresholds. Normalized edit distance divides the raw distance by the length of the longer string, producing a value between 0 (identical) and 1 (completely dissimilar). Similarity thresholds determine when a candidate pair is retained for further processing. Setting thresholds too high misses true matches (false negatives); too low floods the pipeline with spurious candidates (false positives). Optimal thresholds are domain-specific and typically tuned using labeled reference alignments from benchmarks like the OAEI.

Phonetic algorithms encode strings by their pronunciation, enabling matching of homophones with divergent spellings. Soundex maps consonants to numeric codes and retains the first letter, producing a four-character key. Metaphone and Double Metaphone improve accuracy with rules for English and other languages, handling silent letters and consonant clusters. These methods are valuable when entity labels originate from speech-to-text pipelines or when matching proper names across transliteration variants. They are typically used as a preprocessing filter before applying edit distance or token-based metrics.

Single metrics rarely suffice for robust ontology alignment. Hybrid approaches combine multiple similarity measures into a weighted aggregate score. A typical pipeline applies:

• Normalization: lowercasing, diacritic removal, stemming
• Primary metric: edit distance or Jaccard for initial scoring
• Secondary metric: n-gram overlap for tie-breaking
• Phonetic filter: Soundex for candidate recall expansion Weights are learned via logistic regression or tuned through grid search on training data. This composition exploits the complementary strengths of each metric class, improving both precision and recall.

The foundational string metric measuring the minimum number of single-character edits—insertions, deletions, or substitutions—required to change one sequence into another.

• Normalized Edit Distance: Divides the raw distance by the length of the longer string to produce a 0–1 similarity score.
• Damerau-Levenshtein: Extends the basic metric by adding transposition of adjacent characters as a single operation, critical for typo-tolerant matching.
• Computational Cost: Standard dynamic programming implementation runs in O(m*n) time, making it practical for short entity labels but expensive for long text blocks.

A set-based metric that measures overlap between two sample sets by dividing the size of the intersection by the size of the union.

• Token-Level Application: Strings are tokenized into n-grams or word sets before comparison, making it robust to word order changes.
• Jaccard Distance: Defined as 1 - Jaccard similarity, providing a proper metric satisfying the triangle inequality.
• Thresholding: Values range from 0 (no overlap) to 1 (identical sets); thresholds of 0.7–0.9 are typical for entity label matching.

Measures the cosine of the angle between two non-zero vectors in a multi-dimensional space, treating strings as weighted term frequency vectors.

• TF-IDF Weighting: Rare terms receive higher weights via inverse document frequency, amplifying discriminative power for entity names.
• Magnitude Invariance: Cosine similarity ignores vector length, focusing purely on directional alignment—ideal when comparing short labels to longer descriptions.
• Soft Cosine Similarity: Incorporates word embedding similarity into the cosine formula to account for synonyms, bridging lexical and semantic matching.

Decompose strings into contiguous subsequences of length n and compare the resulting sets to produce robust, language-agnostic similarity scores.

• Dice Coefficient: Calculates 2 * |intersection| / (|set A| + |set B|), giving double weight to shared n-grams.
• Overlap Coefficient: Uses |intersection| / min(|set A|, |set B|), making it useful when one string is a substring of another.
• Character N-Grams (n=3): Tri-gram matching is particularly effective for catching morphological variations and compound word splits in entity labels.

A local sequence alignment algorithm that identifies the most similar substring regions between two sequences, rather than forcing a global end-to-end comparison.

• Affine Gap Penalties: Uses separate costs for opening and extending gaps, producing biologically-inspired alignments that handle abbreviation and acronym expansion.
• Scoring Matrix: Relies on a substitution matrix (e.g., identity matrix for exact character matching) to reward matches and penalize mismatches.
• Entity Label Use Case: Excels when matching a full entity name against a noisy text snippet containing the entity mention plus surrounding words.

Encode strings by their pronunciation rather than spelling, enabling matching of homophones and phonetically similar entity labels across transliteration variants.

• Soundex: Maps names to a letter-plus-three-digit code based on consonant groups, standard for historical record linkage.
• Metaphone & Double Metaphone: More sophisticated phonetic encodings that handle English spelling irregularities and produce variable-length keys.
• Caverphone: Designed specifically for name matching in genealogical datasets, handling a broader range of accents and phonetic patterns.