0
$\begingroup$

I am looking for the optimal string distance metric to indicate similarity/difference between possibly truncated words. For example, I would like to find the distance metric between the name "Richard" and possible variations of it (and other names as well)

Variations: Richard | Rihcard | Richard Smith | Rich? | R?ard | ?rd | Joe

, where "?" stands for truncation. For example, the metric should indicate smaller distance between "Richard" and "?rd" or "Richard Smith" than "Richard" and "Joe".

I would really appreciate any help.

$\endgroup$
4
  • $\begingroup$ Are you measuring the distance between two strings or the distance between two sets of strings? We can certainly measure the distance between the string "Richard" and the string "Rikard" using something like the Levenshtein Distance. However, I have no idea how you would measure the distance between "Richard" and "?rd" if ? is a special meta-character representing truncation. If question marks represent truncation, then "?rd" does not represent a string. Instead, "?rd" represents a set of strings. What set is "?rd"? $\endgroup$ Sep 20, 2022 at 1:26
  • $\begingroup$ Are you using the notation "?rd" to refer to the set of all strings which begin with zero or more characters and end in "rd"? $\endgroup$ Sep 20, 2022 at 1:29
  • $\begingroup$ A string cannot internally hold something as abstract as truncation. A string is a function which takes a number $1, 2, 3, \dots$ as input and the string outputs a character*. The set of all characters is usually taken to be the space character along with back-tick and !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[]^_abcdefghijklmnop qrstuvwxyz{|}~ Those are the ASCII characters beggining at 32 and ending at 126. That includes 32 and 126. I could be wrong, but maybe you are using the notation "?rd" to represent the set of all strings which end in "rd"? $\endgroup$ Sep 20, 2022 at 1:42
  • $\begingroup$ All string metrics I have seen treat the characters literally. For example, "?" is a question mark, not a meta-character for truncation. You seem to be asking for a metric which compares two sets of strings for similarity. The sets of strings could be notated using something like regular expressions. $\endgroup$ Sep 20, 2022 at 1:44

2 Answers 2

3
$\begingroup$

It is quite hard to propose an "optimal" string distance metric, especially when the specification is only specified by an example.

There are many possibilities for you to try:

  1. Levenshtein or Edit distance (wiki): allows insertions, deletions and replacements.
  2. Hamming distance (wiki): allows only replacements.
  3. Episode distance: allows only insertions.
  4. Longest Common Subsequence (LCS) distance (wiki): allows only insertions and deletions.
  5. Damerau–Levenshtein distance (wiki): allows insertion, deletion, or substitution of a single character, or a transposition of two adjacent characters.
  6. Smith Waterman similarity (wiki), Needleman–Wunsch similarity: determining similar regions between two strings.

The paper "A Guided Tour to Approximate String Matching" is also informative.


By the way, Mathematica contains most of the distance metrics listed above as built-in functions. For example, to calculate the edit distances:

Map[EditDistance["Richard", #] &, {"Richard", "Rihcard", "Richard Smith", "Rich", "Rard", "rd", "Joe"}]

You get:

{0, 2, 6, 3, 3, 5, 7}

This result meets your requirement of the metric should indicate smaller distance between "Richard" and "?rd" or "Richard Smith" than "Richard" and "Joe". Be prudent, however.

$\endgroup$
2
  • $\begingroup$ Thanks. I know that I didn't define "optimality" at all, it is due to my lack of understanding of string metrics. I guess what I wanted to ask was that: is there a string metric that indicates closer proximity if all of the characters in one string are repeated in the other string and the first string does not contain any other characters that do not occur in the second string? E.g., Map[EditDistance["Richard", #] &, {"Quad", "rd"}] {5, 5} indicates an equal distance but "rd" could be a truncated version of "Richard" while "Quad" could not be. $\endgroup$
    – Adam
    Feb 6, 2015 at 8:29
  • 2
    $\begingroup$ 1) Careful: the list of string metrics on Wikipedia contains functions that are not metrics. 2) Edit distance is related to local or semi-global alignments which fit truncation perfectly. $\endgroup$
    – Raphael
    Mar 5, 2015 at 9:14
2
$\begingroup$

I know this is an old question, but since Google brought me here, maybe it will bring some future beings here as well...

I would recommend using the Jaro-Winkler Distance which is defined in terms of the Jaro Distance $d_j$, the common prefix length of the two strings $l$ (bounded by some maximum value, let's say $b$), and a prefix scaling factor $p$. It is important that you select the parameters $b$ and $p$ such that their product does not exceed one.

$d_{jw} = d_j + lp(1-d_j) = lp + d_j(1-lp)$

Conceptually, it's probably easiest to think of it as a convex combination (weighted average where the weights sum to one) of the Jaro distance and one with weights $1-lp$ and $lp$, respectively. Thus we see that it is important to bound $lp$ to the range $[0, 1]$, otherwise this expression is no longer a convex combination, so we may obtain values outside the range of the Jaro distance: $[0, 1]$.

Obligatory note about the word metric: when we speak of string distance metrics in general, the word "metric" doesn't carry its formal mathematical definition, but rather its basic English definition: "a means by which to measure something."

$\endgroup$
1
  • $\begingroup$ Welcome to the site! There's nothing at all wrong with answering old questions, as long as you're bringing somethng new to the party. You seem to be doing that so thanks! As you say, people will find this in the future with search engines. $\endgroup$ Apr 24, 2017 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.