liblevenshtein::distance::MemoizedDistance Class Reference

Memoizes the distance between pairs of terms. More...

#include <memoized_distance.h>

Inheritance diagram for liblevenshtein::distance::MemoizedDistance:

Collaboration diagram for liblevenshtein::distance::MemoizedDistance:

Public Member Functions
virtual auto	between (std::string v, std::string w) -> std::size_t=0
	Measures the edit distance between two terms.
auto	operator() (const std::string &v, const std::string &w) -> std::size_t
	Measures the edit distance between two terms.

Protected Member Functions
auto	get (const SymmetricPair &key, std::size_t &distance) -> bool
	Collects the memoized distance between the pair of terms represented by the SymmetricPair if the distance has been previously determined.
auto	set (const SymmetricPair &key, const std::size_t &distance) -> std::size_t
	Memoizes the distance between the SymmetricPair of terms for future reference.

Static Protected Member Functions
static auto	f (const std::string &u, std::size_t t) -> std::string
	Returns the suffix of \(u\) from position \(t\).

Private Attributes
std::unordered_map< SymmetricPair, std::size_t >	memo
	Memoized distances between pairs of terms.
std::shared_mutex	mutex
	Coordinates memoization among threads.

Detailed Description

Memoizes the distance between pairs of terms.

Definition at line 16 of file memoized_distance.h.

Member Function Documentation

between()

virtual auto liblevenshtein::distance::Distance::between ( std::string v, std::string w ) -> std::size_t

pure virtualinherited

Measures the edit distance between two terms.

Parameters

v	First term to compare.
w	Second term to compare.

Returns

Edit distance between v and w.

Implemented in liblevenshtein::distance::MergeAndSplitDistance, liblevenshtein::distance::StandardDistance, and liblevenshtein::distance::TranspositionDistance.

f()

auto liblevenshtein::distance::MemoizedDistance::f ( const std::string & u, std::size_t t ) -> std::string

staticprotected

Returns the suffix of \(u\) from position \(t\).

If \(t \ge \left|u\right|\), then the empty string is returned.

Parameters

u	Term whose suffix is to be returned.
t	Beginning position in u for the substring.

Returns

The substring of u beginning at position t if \(t < \left|u\right|\), or the empty string otherwise.

Definition at line 26 of file memoized_distance.cpp.

                                                                           {
  if (t < u.length()) {
    return u.substr(1 + t);
  }
  return "";
}

References query().

Here is the call graph for this function:

get()

auto liblevenshtein::distance::MemoizedDistance::get ( const SymmetricPair & key, std::size_t & distance ) -> bool

protected

Collects the memoized distance between the pair of terms represented by the SymmetricPair if the distance has been previously determined.

Otherwise, the distance is not collected and false is returned.

Parameters

key	SymmetricPair of terms whose distance may have been memoized.
distance	Outgoing reference containing the memoized distance between the pair of terms, if the distance has been previously determined.

Returns

Whether the distance between the pair of terms has been previously determined.

Definition at line 9 of file memoized_distance.cpp.

                                                                                {
  std::shared_lock reader(mutex);
  auto iter = memo.find(key);
  if (iter != memo.end()) {
    distance = iter->second;
    return true;
  }
  return false;
}

References liblevenshtein::distance(), and query().

Here is the call graph for this function:

operator()()

auto liblevenshtein::distance::Distance::operator() ( const std::string & v, const std::string & w ) -> std::size_t

inherited

Measures the edit distance between two terms.

This is equivalent to calling between(v, w).

Parameters

v	First term to compare.
w	Second term to compare.

Returns

Edit distance between v and w.

Definition at line 5 of file distance.cpp.

                 {
  return between(v, w);
}

References query().

Here is the call graph for this function:

set()

auto liblevenshtein::distance::MemoizedDistance::set ( const SymmetricPair & key, const std::size_t & distance ) -> std::size_t

protected

Memoizes the distance between the SymmetricPair of terms for future reference.

Parameters

key	SymmetricPair of terms whose distance is to be memoized.
distance	Distance between the SymmetricPair of terms to memoize.

Returns

The distance once it has been memoized.

Definition at line 19 of file memoized_distance.cpp.

                                                                   {
  std::unique_lock writer(mutex);
  memo[key] = distance;
  return distance;
}

References liblevenshtein::distance(), and query().

Here is the call graph for this function:

Member Data Documentation

memo

std::unordered_map<SymmetricPair, std::size_t> liblevenshtein::distance::MemoizedDistance::memo

private

Memoized distances between pairs of terms.

Definition at line 57 of file memoized_distance.h.

mutex

std::shared_mutex liblevenshtein::distance::MemoizedDistance::mutex

mutableprivate

Coordinates memoization among threads.

Definition at line 60 of file memoized_distance.h.

---

The documentation for this class was generated from the following files:

• src/liblevenshtein/distance/memoized_distance.h
• src/liblevenshtein/distance/memoized_distance.cpp