liblevenshtein::distance::MergeAndSplitDistance Class Reference

Computes the standard Levenshtein distance extended with two additional elementary operations: (1) merge and (2) split. More...

#include <merge_and_split_distance.h>

Inheritance diagram for liblevenshtein::distance::MergeAndSplitDistance:

Collaboration diagram for liblevenshtein::distance::MergeAndSplitDistance:

Public Member Functions
auto	between (std::string v, std::string w) -> std::size_t override
	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

Computes the standard Levenshtein distance extended with two additional elementary operations: (1) merge and (2) split.

This is most useful for correcting OCR errors (optical character recognition).

Definition at line 15 of file merge_and_split_distance.h.

Member Function Documentation

between()

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

overridevirtual

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.

Implements liblevenshtein::distance::Distance.

Definition at line 6 of file merge_and_split_distance.cpp.

                 {
  const SymmetricPair key(v, w);
 
  std::size_t distance;
  if (get(key, distance)) {
    return distance;
  }
 
  if (v.empty()) {
    return set(key, w.length());
  }
 
  if (w.empty()) {
    return set(key, v.length());
  }
 
  char a = v[0];
  std::string x = v.substr(1);
  char b = w[0];
  std::string y = w.substr(1);
 
  // Discard identical characters
  while (a == b && !(x.empty() || y.empty())) {
    a = x[0];
    v = x;
    x = v.substr(1);
    b = y[0];
    w = y;
    y = w.substr(1);
  }
 
  // x.empty() || y.empty()
  if (a == b) {
    if (x.empty()) {
      return set(key, y.length());
    }
    return set(key, x.length());
  }
 
  distance = between(x, w);
  if (0 == distance) {
    return set(key, 1);
  }
 
  std::size_t min_distance = distance;
 
  distance = between(v, y);
  if (0 == distance) {
    return set(key, 1);
  }
 
  if (distance < min_distance) {
    min_distance = distance;
  }
 
  distance = between(x, y);
  if (0 == distance) {
    return set(key, 1);
  }
 
  if (distance < min_distance) {
    min_distance = distance;
  }
 
  if (w.length() > 1) {
    distance = between(x, f(w, 1));
 
    if (0 == distance) {
      return set(key, 1);
    }
 
    if (distance < min_distance) {
      min_distance = distance;
    }
  }
 
  if (v.length() > 1) {
    distance = between(f(v, 1), y);
 
    if (0 == distance) {
      return set(key, 1);
    }
 
    if (distance < min_distance) {
      min_distance = distance;
    }
  }
 
  return set(key, 1 + min_distance);
}

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

Here is the call graph for this function:

f()

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

staticprotectedinherited

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

protectedinherited

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

protectedinherited

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

privateinherited

Memoized distances between pairs of terms.

Definition at line 57 of file memoized_distance.h.

mutex

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

mutableprivateinherited

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/merge_and_split_distance.h
• src/liblevenshtein/distance/merge_and_split_distance.cpp