Distance Algorithms

String distance and similarity measurements. More...

Functions
template<typename InputIt1 , typename InputIt2 >
size_t	rapidfuzz::hamming_distance (InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, bool pad_=true, size_t score_cutoff=std::numeric_limits< size_t >::max())
	Calculates the Hamming distance between two strings.
template<typename InputIt1 , typename InputIt2 >
double	rapidfuzz::hamming_normalized_similarity (InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, bool pad_=true, double score_cutoff=0.0)
	Calculates a normalized hamming similarity.
template<typename InputIt1 , typename InputIt2 >
size_t	rapidfuzz::levenshtein_distance (InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, LevenshteinWeightTable weights={1, 1, 1}, size_t score_cutoff=std::numeric_limits< size_t >::max(), size_t score_hint=std::numeric_limits< size_t >::max())
	Calculates the minimum number of insertions, deletions, and substitutions required to change one sequence into the other according to Levenshtein with custom costs for insertion, deletion and substitution.
template<typename InputIt1 , typename InputIt2 >
double	rapidfuzz::levenshtein_normalized_similarity (InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, LevenshteinWeightTable weights={1, 1, 1}, double score_cutoff=0.0, double score_hint=0.0)
	Calculates a normalized levenshtein distance using custom costs for insertion, deletion and substitution.
template<typename InputIt1 , typename InputIt2 >
Editops	rapidfuzz::levenshtein_editops (InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, size_t score_hint=std::numeric_limits< size_t >::max())
	Return list of EditOp describing how to turn s1 into s2.
template<typename InputIt1 , typename InputIt2 >
size_t	rapidfuzz::osa_distance (InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, size_t score_cutoff=std::numeric_limits< size_t >::max())
	Calculates the optimal string alignment (OSA) distance between two strings.
template<typename InputIt1 , typename InputIt2 >
double	rapidfuzz::osa_normalized_similarity (InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, double score_cutoff=0.0)
	Calculates a normalized hamming similarity.

Detailed Description

String distance and similarity measurements.

Function Documentation

hamming_distance()

template<typename InputIt1 , typename InputIt2 >

size_t rapidfuzz::hamming_distance	(	InputIt1	first1,
		InputIt1	last1,
		InputIt2	first2,
		InputIt2	last2,
		bool	pad_ = true,
		size_t	score_cutoff = std::numeric_limits<size_t>::max()
	)

#include <rapidfuzz/distance/Hamming.hpp>

Calculates the Hamming distance between two strings.

Both strings require a similar length

Template Parameters

Sentence1	This is a string that can be converted to basic_string_view<char_type>
Sentence2	This is a string that can be converted to basic_string_view<char_type>

Parameters

s1	string to compare with s2 (for type info check Template parameters above)
s2	string to compare with s1 (for type info check Template parameters above)
max	Maximum Hamming distance between s1 and s2, that is considered as a result. If the distance is bigger than max, max + 1 is returned instead. Default is std::numeric_limits<size_t>::max(), which deactivates this behaviour.

Returns

Hamming distance between s1 and s2

hamming_normalized_similarity()

template<typename InputIt1 , typename InputIt2 >

double rapidfuzz::hamming_normalized_similarity	(	InputIt1	first1,
		InputIt1	last1,
		InputIt2	first2,
		InputIt2	last2,
		bool	pad_ = true,
		double	score_cutoff = 0.0
	)

#include <rapidfuzz/distance/Hamming.hpp>

Calculates a normalized hamming similarity.

Both string require a similar length

Template Parameters

Sentence1	This is a string that can be converted to basic_string_view<char_type>
Sentence2	This is a string that can be converted to basic_string_view<char_type>

Parameters

s1	string to compare with s2 (for type info check Template parameters above)
s2	string to compare with s1 (for type info check Template parameters above)
score_cutoff	Optional argument for a score threshold as a float between 0 and 1.0. For ratio < score_cutoff 0 is returned instead. Default is 0, which deactivates this behaviour.

Returns

Normalized hamming distance between s1 and s2 as a float between 0 and 1.0

levenshtein_distance()

template<typename InputIt1 , typename InputIt2 >

size_t rapidfuzz::levenshtein_distance	(	InputIt1	first1,
		InputIt1	last1,
		InputIt2	first2,
		InputIt2	last2,
		LevenshteinWeightTable	weights = {1, 1, 1},
		size_t	score_cutoff = std::numeric_limits<size_t>::max(),
		size_t	score_hint = std::numeric_limits<size_t>::max()
	)

#include <rapidfuzz/distance/Levenshtein.hpp>

Calculates the minimum number of insertions, deletions, and substitutions required to change one sequence into the other according to Levenshtein with custom costs for insertion, deletion and substitution.

Template Parameters

Sentence1	This is a string that can be converted to basic_string_view<char_type>
Sentence2	This is a string that can be converted to basic_string_view<char_type>

Parameters

s1	string to compare with s2 (for type info check Template parameters above)
s2	string to compare with s1 (for type info check Template parameters above)
weights	The weights for the three operations in the form (insertion, deletion, substitution). Default is {1, 1, 1}, which gives all three operations a weight of 1.
max	Maximum Levenshtein distance between s1 and s2, that is considered as a result. If the distance is bigger than max, max + 1 is returned instead. Default is std::numeric_limits<size_t>::max(), which deactivates this behaviour.

Returns

returns the levenshtein distance between s1 and s2

Remarks

Depending on the input parameters different optimized implementation are used to improve the performance. Worst-case performance is O(m * n).

Insertion = Deletion = Substitution:

This is known as uniform Levenshtein distance and is the distance most commonly referred to as Levenshtein distance. The following implementation is used with a worst-case performance of O([N/64]M).

• if max is 0 the similarity can be calculated using a direct comparision, since no difference between the strings is allowed. The time complexity of this algorithm is O(N).
• A common prefix/suffix of the two compared strings does not affect the Levenshtein distance, so the affix is removed before calculating the similarity.
• If max is <= 3 the mbleven algorithm is used. This algorithm checks all possible edit operations that are possible under the threshold max. The time complexity of this algorithm is O(N).
• If the length of the shorter string is <= 64 after removing the common affix Hyyrös' algorithm is used, which calculates the Levenshtein distance in parallel. The algorithm is described by [hyrro_2002]. The time complexity of this algorithm is O(N).
• If the length of the shorter string is >= 64 after removing the common affix a blockwise implementation of Myers' algorithm is used, which calculates the Levenshtein distance in parallel (64 characters at a time). The algorithm is described by [myers_1999]. The time complexity of this algorithm is O([N/64]M).

Insertion = Deletion, Substitution >= Insertion + Deletion:

Since every Substitution can be performed as Insertion + Deletion, this variant of the Levenshtein distance only uses Insertions and Deletions. Therefore this variant is often referred to as InDel-Distance. The following implementation is used with a worst-case performance of O([N/64]M).

• if max is 0 the similarity can be calculated using a direct comparision, since no difference between the strings is allowed. The time complexity of this algorithm is O(N).
• if max is 1 and the two strings have a similar length, the similarity can be calculated using a direct comparision aswell, since a substitution would cause a edit distance higher than max. The time complexity of this algorithm is O(N).
• A common prefix/suffix of the two compared strings does not affect the Levenshtein distance, so the affix is removed before calculating the similarity.
• If max is <= 4 the mbleven algorithm is used. This algorithm checks all possible edit operations that are possible under the threshold max. As a difference to the normal Levenshtein distance this algorithm can even be used up to a threshold of 4 here, since the higher weight of substitutions decreases the amount of possible edit operations. The time complexity of this algorithm is O(N).
• If the length of the shorter string is <= 64 after removing the common affix Hyyrös' lcs algorithm is used, which calculates the InDel distance in parallel. The algorithm is described by [hyrro_lcs_2004] and is extended with support for UTF32 in this implementation. The time complexity of this algorithm is O(N).
• If the length of the shorter string is >= 64 after removing the common affix a blockwise implementation of Hyyrös' lcs algorithm is used, which calculates the Levenshtein distance in parallel (64 characters at a time). The algorithm is described by [hyrro_lcs_2004]. The time complexity of this algorithm is O([N/64]M).

Other weights:

The implementation for other weights is based on Wagner-Fischer. It has a performance of O(N * M) and has a memory usage of O(N). Further details can be found in [wagner_fischer_1974].

Examples

Find the Levenshtein distance between two strings:

// dist is 2
size_t dist = levenshtein_distance("lewenstein", "levenshtein");

Setting a maximum distance allows the implementation to select a more efficient implementation:

// dist is 2
size_t dist = levenshtein_distance("lewenstein", "levenshtein", {1, 1, 1}, 1);

It is possible to select different weights by passing a weight struct.

// dist is 3
size_t dist = levenshtein_distance("lewenstein", "levenshtein", {1, 1, 2});

levenshtein_editops()

template<typename InputIt1 , typename InputIt2 >

Editops rapidfuzz::levenshtein_editops	(	InputIt1	first1,
		InputIt1	last1,
		InputIt2	first2,
		InputIt2	last2,
		size_t	score_hint = std::numeric_limits<size_t>::max()
	)

#include <rapidfuzz/distance/Levenshtein.hpp>

Return list of EditOp describing how to turn s1 into s2.

Template Parameters

Sentence1	This is a string that can be converted to basic_string_view<char_type>
Sentence2	This is a string that can be converted to basic_string_view<char_type>

Parameters

s1	string to compare with s2 (for type info check Template parameters above)
s2	string to compare with s1 (for type info check Template parameters above)

Returns

Edit operations required to turn s1 into s2

levenshtein_normalized_similarity()

template<typename InputIt1 , typename InputIt2 >

double rapidfuzz::levenshtein_normalized_similarity	(	InputIt1	first1,
		InputIt1	last1,
		InputIt2	first2,
		InputIt2	last2,
		LevenshteinWeightTable	weights = {1, 1, 1},
		double	score_cutoff = 0.0,
		double	score_hint = 0.0
	)

#include <rapidfuzz/distance/Levenshtein.hpp>

Calculates a normalized levenshtein distance using custom costs for insertion, deletion and substitution.

Template Parameters

Sentence1	This is a string that can be converted to basic_string_view<char_type>
Sentence2	This is a string that can be converted to basic_string_view<char_type>

Parameters

s1	string to compare with s2 (for type info check Template parameters above)
s2	string to compare with s1 (for type info check Template parameters above)
weights	The weights for the three operations in the form (insertion, deletion, substitution). Default is {1, 1, 1}, which gives all three operations a weight of 1.
score_cutoff	Optional argument for a score threshold as a float between 0 and 1.0. For ratio < score_cutoff 0 is returned instead. Default is 0, which deactivates this behaviour.

Returns

Normalized weighted levenshtein distance between s1 and s2 as a double between 0 and 1.0

See also

levenshtein()

Remarks

The normalization of the Levenshtein distance is performed in the following way:

Examples

Find the normalized Levenshtein distance between two strings:

// ratio is 81.81818181818181
double ratio = normalized_levenshtein("lewenstein", "levenshtein");

Setting a score_cutoff allows the implementation to select a more efficient implementation:

// ratio is 0.0
double ratio = normalized_levenshtein("lewenstein", "levenshtein", {1, 1, 1}, 85.0);

It is possible to select different weights by passing a weight struct

// ratio is 85.71428571428571
double ratio = normalized_levenshtein("lewenstein", "levenshtein", {1, 1, 2});

osa_distance()

template<typename InputIt1 , typename InputIt2 >

size_t rapidfuzz::osa_distance	(	InputIt1	first1,
		InputIt1	last1,
		InputIt2	first2,
		InputIt2	last2,
		size_t	score_cutoff = std::numeric_limits<size_t>::max()
	)

#include <rapidfuzz/distance/OSA.hpp>

Calculates the optimal string alignment (OSA) distance between two strings.

Both strings require a similar length

Template Parameters

Sentence1	This is a string that can be converted to basic_string_view<char_type>
Sentence2	This is a string that can be converted to basic_string_view<char_type>

Parameters

s1	string to compare with s2 (for type info check Template parameters above)
s2	string to compare with s1 (for type info check Template parameters above)
max	Maximum OSA distance between s1 and s2, that is considered as a result. If the distance is bigger than max, max + 1 is returned instead. Default is std::numeric_limits<size_t>::max(), which deactivates this behaviour.

Returns

OSA distance between s1 and s2

osa_normalized_similarity()

template<typename InputIt1 , typename InputIt2 >

double rapidfuzz::osa_normalized_similarity	(	InputIt1	first1,
		InputIt1	last1,
		InputIt2	first2,
		InputIt2	last2,
		double	score_cutoff = 0.0
	)

#include <rapidfuzz/distance/OSA.hpp>

Calculates a normalized hamming similarity.

Both string require a similar length

Template Parameters

Sentence1	This is a string that can be converted to basic_string_view<char_type>
Sentence2	This is a string that can be converted to basic_string_view<char_type>

Parameters

s1	string to compare with s2 (for type info check Template parameters above)
s2	string to compare with s1 (for type info check Template parameters above)
score_cutoff	Optional argument for a score threshold as a float between 0 and 1.0. For ratio < score_cutoff 0 is returned instead. Default is 0, which deactivates this behaviour.

Returns

Normalized hamming distance between s1 and s2 as a float between 0 and 1.0