Introduction

In data science and text analytics, determining the similarity between two strings is a fundamental task. Whether it's for deduplication, spell checking, recommendation systems, or natural language processing (NLP), quantifying how closely two strings resemble each other is crucial. This article explores the various metrics used in assessing string similarity, accompanied by technical explanations and illustrative examples.

Key Concepts in String Similarity

String similarity is broadly categorized into semantic and syntactic similarity. Semantic similarity captures the meaning of strings, while syntactic similarity focuses on the exact sequence of characters. Here, we will primarily delve into syntactic methods, which are more computationally straightforward and widely used.

Syntactic String Similarity Metrics

1. Hamming Distance
   • Definition: Measures the number of positions at which the corresponding symbols in two strings of equal length are different.
   • Equation: $d_H(s_1, s_2) = \sum (s_1[i] \neq s_2[i])$
   • Example: For strings "karin" and "karen":
     Differences are at indexes 2 and 3, so $d_H = 2$. Limitation: Only applicable to strings of equal length.
2. Levenshtein Distance (Edit Distance)
   • Definition: Calculates the minimum number of single-character edits (insertions, deletions, substitutions) required to change one string into another.
   • Equation: $d_L(s_1, s_2)$ is computed using dynamic programming.
   • Example: For "kitten" and "sitting":
   • Definition: Measures similarity between two strings, giving more favorable ratings to strings that match from the beginning for a set prefix length.
   • Equation:
   • Example: For "MARTHA" and "MARHTA", using a prefix length $l$ with weight $p$, $JaroWinkler$ yields a higher value if common prefixes exist.
   • Definition: Utilizes vector space models to measure the cosine of the angle between two vectors (derived from the strings).
   • Equation:
   • Example: Words are vectorized, e.g., using TF-IDF, and the vectors are then compared.
   • Definition: Compares the similarity and diversity of sample sets, expressed as the size of the intersection divided by the size of the union of the sample sets.
   • Equation:
   • Example: For sets of characters in "night" and "nacht":