levenshteinSSE Namespace Reference

Classes
class	AlignmentAllocator
class	AlignmentAllocator< T, 1 >
struct	has_data_and_size
struct	LevenshteinContainer
struct	LevenshteinContainer< false >
struct	LevenshteinContainer< true >
struct	LevenshteinIteration
struct	LevenshteinIteration< std::vector< std::uint32_t, Alloc1 >, std::vector< std::uint32_t, Alloc2 >, const T *, const T * >
struct	LevenshteinIteration< std::vector< std::uint32_t, Alloc1 >, std::vector< std::uint32_t, Alloc2 >, T *, T * >
struct	LevenshteinIterationBase
struct	LevenshteinIterationSIMD
struct	LevenshteinIterationSIMDWrap

Functions
template<typename Iterator1 , typename Iterator2 >
std::size_t	levenshtein (Iterator1 a, Iterator1 aEnd, Iterator2 b, Iterator2 bEnd)
template<typename Container1 , typename Container2 >
std::size_t	levenshtein (const Container1 &a, const Container2 &b)
template<typename T , typename Iterator1 , typename Iterator2 >
T	levenshteinDiagonal (Iterator1 a, Iterator1 aEnd, Iterator2 b, Iterator2 bEnd)
template<typename T , typename Iterator1 , typename Iterator2 >
T	levenshteinRowBased (Iterator1 a, Iterator1 aEnd, Iterator2 b, Iterator2 bEnd)
template<typename Iterator1 , typename Iterator2 >
std::size_t	levenshtein (Iterator1 a, Iterator1 aEnd, Iterator2 b, Iterator2 bEnd, std::random_access_iterator_tag, std::random_access_iterator_tag)
template<typename Iterator1 , typename Iterator2 >
std::size_t	levenshtein (Iterator1 a, Iterator1 aEnd, Iterator2 b, Iterator2 bEnd, std::bidirectional_iterator_tag, std::bidirectional_iterator_tag)

Variables
constexpr std::size_t	alignment = 1

Detailed Description

The MIT License (MIT)

Copyright (c) 2016 Anna Henningsen sqrt@.nosp@m.entl.nosp@m.ess.o.nosp@m.rg

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Function Documentation

levenshtein() [1/4]

template<typename Iterator1 , typename Iterator2 >

std::size_t levenshteinSSE::levenshtein	(	Iterator1	a,
		Iterator1	aEnd,
		Iterator2	b,
		Iterator2	bEnd
	)

Public methods Compute the Levenshtein distances of [a, aEnd) and [b, bEnd). Both types of iterators need to be bidirectional, e.g. fulfill the requirements of BidirectionalIterator, but may just be pointers.

For pointers to types where SIMD instructions make sense, these are used when available.

levenshtein() [2/4]

template<typename Container1 , typename Container2 >

std::size_t levenshteinSSE::levenshtein	(	const Container1 &	a,
		const Container2 &	b
	)

Compute the Levenshtein distances of a and b. Both containers need to support bidirectional start and end iterators (via std::begin() and std::end()).

If both containers provide .data() and .size(), these are used to get pointers to the start and past-end elements. This holds true for std::string, std::vector, std::array and possibly more, but if you want to use this with custom container types, bear in mind that this also means that the available memory area needs to be contiguous.

levenshtein() [3/4]

template<typename Iterator1 , typename Iterator2 >

std::size_t levenshteinSSE::levenshtein	(	Iterator1	a,
		Iterator1	aEnd,
		Iterator2	b,
		Iterator2	bEnd,
		std::random_access_iterator_tag	,
		std::random_access_iterator_tag
	)

Preable for edge cases and skipping common prefixes/suffixes, random access version.

levenshtein() [4/4]

template<typename Iterator1 , typename Iterator2 >

std::size_t levenshteinSSE::levenshtein	(	Iterator1	a,
		Iterator1	aEnd,
		Iterator2	b,
		Iterator2	bEnd,
		std::bidirectional_iterator_tag	,
		std::bidirectional_iterator_tag
	)

Preable for edge cases and skipping common prefixes/suffixes, non-random access version.

levenshteinDiagonal()

template<typename T , typename Iterator1 , typename Iterator2 >

T levenshteinSSE::levenshteinDiagonal	(	Iterator1	a,
		Iterator1	aEnd,
		Iterator2	b,
		Iterator2	bEnd
	)

Outer loop of the diagonal algorithm variant.

levenshteinRowBased()

template<typename T , typename Iterator1 , typename Iterator2 >

T levenshteinSSE::levenshteinRowBased	(	Iterator1	a,
		Iterator1	aEnd,
		Iterator2	b,
		Iterator2	bEnd
	)

Outer loop of the row-based variant, used for non-random-access iterators.

based on https://github.com/sindresorhus/leven

Variable Documentation

alignment

constexpr std::size_t levenshteinSSE::alignment = 1