String Functions

This module contains functions for string operations and computations: measuring the similarity of two strings, finding the most similar candidates in a sequence of strings, splitting a string into character n-grams, encoding words phonetically, and formatting values.

Conventions

All functions and errors are in the http://basex.org/modules/string namespace, to which the string prefix is statically bound.

Similarity Measures

The similarity measures of this section all answer the same question: How similar are two strings? They all return a normalized xs:double in the range 0–1: 1 means identical, 0 means maximally different. They differ in the kind of difference they tolerate.

The following table lists what each measure is suited for…

…and how it rates some typical pairs of strings:

• Typo: 'flower', 'flowers'
• Order: 'Ishida Yutei', 'Yutei Ishida'
• Extra: 'Fortuny y Marsal', 'Fortuny Marsal'
• Transliteration: 'night', 'nacht'
• Other: 'Rembrandt', 'Vermeer'

Most measures are based on the edit distance of two strings: the number of insertions, deletions, substitutions, and transpositions of adjacent characters that are required to turn one string into the other.

The algorithm is the optimal string alignment: no substring is edited more than once. The distance of CA and ABC is thus 3, and not 2, as with the Damerau-Levenshtein distance. The same algorithm is used for fuzzy querying.

Options

All functions of this section and string:ngrams share the case, diacritics, stemming and language options of ft:tokenize, and process their input accordingly. Only the defaults differ: nothing is folded and nothing is stemmed, so strings are compared literally unless you request otherwise:

string:levenshtein('Rubens', 'rubens')  (: 0.8333333333333334 :),
string:levenshtein('Rubens', 'rubens', { 'case': 'insensitive' }) (: 1 :)

If any option is specified, the input is tokenized with the full-text lexer. For string:token-sort-ratio and string:token-set-ratio this has a second effect: the input is no longer split on whitespace, but on word boundaries, so punctuation no longer influences the result.

string:token-set-ratio('Tanguy, Yves', 'Yves Tanguy') (: 0.916 :),
string:token-set-ratio('Tanguy, Yves', 'Yves Tanguy', { 'case': 'insensitive' }) (: 1 :)

string:levenshtein

Updated: New $options parameter.

string:levenshtein(
  $value1   as xs:string,
  $value2   as xs:string,
  $options  as map(*)?  := {}
) as xs:double

string:levenshtein('flower', 'flowers')

string:levenshtein('HOUSES', 'house', { 'stemming': true(), 'case': 'insensitive' })

string:levenshtein-distance

Added: New function.

string:levenshtein-distance(
  $value1   as xs:string,
  $value2   as xs:string,
  $options  as map(*)?  := {}
) as xs:integer?

string:levenshtein-distance('flower', 'flowers')

string:levenshtein-distance('kitten', 'sitting')

string:levenshtein-distance('kitten', 'sitting', { 'max': 2 })

string:jaro-winkler

Updated: New $options parameter.

Updated: The common prefix is limited to 4 characters.

string:jaro-winkler(
  $value1   as xs:string,
  $value2   as xs:string,
  $options  as map(*)?  := {}
) as xs:double

string:jaro-winkler('flower', 'flowers')

string:jaro-winkler(
  'Müller',
  'MULLER',
  { 'case': 'insensitive', 'diacritics': 'insensitive' }
)

string:token-sort-ratio

Added: New function.

string:token-sort-ratio(
  $value1   as xs:string,
  $value2   as xs:string,
  $options  as map(*)?  := {}
) as xs:double

string:token-sort-ratio('Ishida Yūtei', 'Yūtei Ishida')

string:token-set-ratio

Added: New function.

string:token-set-ratio(
  $value1   as xs:string,
  $value2   as xs:string,
  $options  as map(*)?  := {}
) as xs:double

string:token-set-ratio('Fortuny y Marsal', 'Fortuny Marsal')

string:ngram-similarity

Added: New function.

string:ngram-similarity(
  $value1   as xs:string,
  $value2   as xs:string,
  $options  as map(*)?  := {}
) as xs:double

string:ngram-similarity('Ishida Yūtei', 'Yūtei Ishida')

string:ngram-similarity('Massys', 'Metsys')

string:ngram-similarity('night', 'nacht', { 'n': 3 })

string:ngram-similarity('night', 'nacht', { 'padding': true() })

string:partial-ratio

Added: New function.

string:partial-ratio(
  $value1   as xs:string,
  $value2   as xs:string,
  $options  as map(*)?  := {}
) as xs:double

string:partial-ratio('Rembrandt', 'Rembrandt van Rijn (1606-1669)')

string:partial-ratio('Rembrant', 'Rembrandt van Rijn')

string:closest

Added: New function.

string:closest(
  $value       as xs:string,
  $candidates  as xs:string*,
  $options     as map(*)?  := {}
) as map(*)*

string:closest('Rembrant', ('Rembrandt', 'Rubens', 'Vermeer'))

string:closest(
  'Jan Steen',
  ('Steen, Jan', 'Jan Vermeer'),
  { 'measure': string:token-set-ratio#2, 'threshold': 0.9, 'limit': 0 }
)?value

string:closest('night', ('nacht'), { 'measure': string:ngram-similarity#2, 'n': 3 })

let $candidates := ft:tokens('db', 'rembrandt', { 'fuzzy': true(), 'errors': 2 })
return string:closest('rembrandt', $candidates, { 'limit': 0 })

Tokenization

string:ngrams

Added: New function.

string:ngrams(
  $value    as xs:string,
  $options  as map(*)?  := {}
) as xs:string*

string:ngrams('flower')

string:ngrams('flower', { 'n': 3 })

string:ngrams('ab', { 'n': 3, 'padding': true() })

Phonetic Encodings

The functions of this section encode a word as a code that reflects its pronunciation: two words are considered similar if their codes are equal. Case and diacritics are folded, and each function is bound to a single language, so the codes of different algorithms cannot be compared with each other. Words with a similar meaning are found with ft:thesaurus.

A single word is encoded. Strings with multiple words are encoded as if the whitespace was absent, and the resulting code is usually meaningless. Encode the words one by one instead, and sort the codes if the word order is irrelevant:

declare function soundex-key($name as xs:string) as xs:string* {
  sort(ft:tokenize($name) ! string:soundex(.))
};
deep-equal(soundex-key('Jacob van Ruisdael'), soundex-key('van Ruisdael, Jacob'))

Result: true

string:soundex

Updated: A string without letters yields an empty string.

string:soundex(
  $value  as xs:string
) as xs:string

string:soundex('Michael')

string:soundex('OBrien') = string:soundex("O'Brien")

string:cologne-phonetic

string:cologne-phonetic(
  $value  as xs:string
) as xs:string

string:cologne-phonetic('Michael')

every $s in ('Mayr', 'Maier', 'Meier')
satisfies string:cologne-phonetic($s) = '67'

Examples

Finding Duplicates

The following query groups the spelling variants of a list of names. It combines the building blocks of this module: options fold case, diacritics and punctuation, string:token-set-ratio tolerates reordered and omitted words, the threshold keeps unrelated names apart, and string:closest supplies all matches of a name in one call. The first name of each group serves as its representative:

let $names := (
  'Ruisdael, Jacob van',
  'Jacob van Ruisdael',
  'Rembrandt van Rijn',
  'Rembrandt van Rhijn',
  'Johannes Vermeer'
)
let $options := {
  'measure': string:token-set-ratio#2,
  'case': 'insensitive',
  'diacritics': 'insensitive',
  'threshold': 0.9,
  'limit': 0
}
for $name in $names
group by $group := sort(string:closest($name, $names, $options)?value) => head()
return $group || ': ' || string-join($name, ' | ')

Result:

Jacob van Ruisdael: Ruisdael, Jacob van | Jacob van Ruisdael
Rembrandt van Rhijn: Rembrandt van Rijn | Rembrandt van Rhijn
Johannes Vermeer: Johannes Vermeer

With larger inputs, the vocabulary of a database is a better source of candidates than the input itself: see ft:tokens.

Ranking Similar Names

Comparing a string with all candidates is expensive, as the similarity measures inspect every character. A phonetic code is much cheaper, and it can be used to discard the candidates that do not even sound alike. The remaining ones are ranked with string:closest, and the result is tabulated with string:format:

let $names := (
  'Meier', 'Maier', 'Mayr', 'Meyer', 'Major',
  'Schmidt', 'Schmitt', 'Müller'
)
let $query := 'Meyr'
let $code := string:cologne-phonetic($query)
let $candidates := $names[string:cologne-phonetic(.) = $code]
for $match in string:closest($query, $candidates,
  { 'measure': string:jaro-winkler#2, 'limit': 0 })
return string:format('%-6s %.2f', $match?value, $match?similarity)

Result:

Meyer  0.95
Mayr   0.85
Meier  0.83
Maier  0.63
Major  0.63

Schmidt, Schmitt and Müller are not compared at all: their phonetic codes differ from the one of the query.

N-gram Index

A phonetic code only discards candidates that sound different. string:ngrams allows you to be more selective: if you index the n-grams of your candidates once, you can restrict the comparison to the candidates that share at least one n-gram with the query. This is how you can search a long list of strings without a full-text index:

let $names := ('Rembrandt', 'Rubens', 'Vermeer')
let $index := map:merge(
  for $name in $names, $gram in distinct-values(string:ngrams($name))
  group by $gram
  return { $gram: $name }
)
let $query := 'Rembrant'
let $candidates := distinct-values(string:ngrams($query) ! $index(.))
return string:closest($query, $candidates)

Result:

{ 'value': 'Rembrandt', 'similarity': 0.8888888888888888e0 }

The index maps each bigram to the names that contain it. Rubens and Vermeer share no bigram with the query, so they are never compared. The larger the list, the more you save; the price is the memory for the index and the effort of keeping it up to date.

ft:tokens narrows the candidates in a comparable way, but the two are not interchangeable: it is bound to the vocabulary of a full-text index, it returns single tokens (never a name such as Rembrandt van Rijn), and its fuzzy option selects the candidates by edit distance, not by shared n-grams.

Errors

Changelog

• Added: string:closest, string:levenshtein-distance, string:partial-ratio, string:token-sort-ratio, string:token-set-ratio, string:ngram-similarity, string:ngrams
• Updated: The similarity functions and string:ngrams adopt the $options of ft:tokenize (case, diacritics, stemming, language).
• Updated: string:soundex: a string without letters yields an empty string (before: 0000).
• Removed: string:format in favor of fn:pad-string.

• Added: string:jaro-winkler for computing the Jaro-Winkler similarity.
• Removed: string:tab, string:nl and string:cr in favor of fn:char.

• Updated: Renamed from Strings Module to String Module. The namespace URI has been updated as well.
• Updated: string:format, string:cr, string:nl and string:tab adopted from the obsolete Output Module.

• Added: New module added. Functions were adopted from the obsolete Utility and Output Modules.