liblevenshtein Namespace Reference

Various utilities regarding Levenshtein transducers. More...

Namespaces
namespace	demo
namespace	distance
	Memoized, recursive distance metrics typically used to evaluate the correctness of Levenshtein automata.

Classes
class	Dawg
	A Directed Acyclic Word Graph (DAWG) maps sequences of characters to form words; the collection of words is known as a dictionary. More...
class	DawgIterator
	Iterates over all the terms in a DAWG dictionary. More...
class	DawgNode
	Represents a position within one or more terms of a DAWG dictionary. More...
class	Intersection
	Represents an Intersection between a dictionary automaton and Levenshtein automaton, guided by the query term. More...
class	LazyIterator
	Lazily traverses the intersection between the dictionary automaton and Levenshtein automaton, guided by the query term, and yields each spelling candidate as it is matched. More...
class	LazyQuery
	Lazily traverses the intersection between the dictionary automaton and Levenshtein automaton, guided by the query term, and yields each spelling candidate as it is matched. More...
class	Position
	Represents a location within the Levenshtein automaton. More...
class	Prefix
	Represents the prefix of a dictionary term. More...
class	SortedDawg
	A specific type of Dawg that is constructed over lexicographically sorted terms. More...
class	State
	Consists of a closure of Position nodes within the Levenshtein automaton. More...
class	StateIterator
	Iterates over the Position nodes in the linked-list of a Levenshtein State. More...
class	StateTransition
	Transitions Levenshtein States given a characteristic vector. More...
class	Transducer
	Constructs a Levenshtein Transducer that, when given a dictionary automaton, query term, and maximum edit distance, n, is able to match all spelling candidates in the dictionary automaton for the query term whose edit distances are no larger than n. More...
class	Transition
	Represents an edge from one DawgNode to another, annotated with a character label from the current position of the dictionary term. More...
class	UnsubsumeFn
	Removes (unsubsumes) all Positions from a State that are subsumed by another Position within the same State. More...

Typedefs
using	TransitionFn = std::function<State *(State *, std::vector<bool> &)>
	Returns the Levenshtein State mapped-to by another State and characteristic vector.
using	DistanceFn = std::function<std::size_t(State *, std::size_t)>
	Infers the Levenshtein distance from a final Levenshtein State and the length of the query term.
using	Comparator = std::function<int(Position *, Position *)>
using	PositionTransitionFn
	Transitions Position nodes.
using	CompareFn = std::function<int(Position *, Position *)>
	Compares Position nodes.
using	MergeFn = std::function<void(State *, std::vector<Position *>)>
	Merges Position nodes into a State.
using	Candidate = std::pair<std::string, std::size_t>
	Spelling candidate that includes both the dictionary term and its edit distance from the query term.
using	SubsumesFn = std::function<bool(Position *, Position *, std::size_t)>
	Determines whether one Position subsumes another given the maximum edit distance to consider.

Enumerations
enum class	Algorithm { STANDARD , TRANSPOSITION , MERGE_AND_SPLIT }
	Enumerates the available Levenshtein distance algorithms. More...

Functions
auto	operator<< (std::ostream &out, const Dawg &dawg) -> std::ostream &
auto	operator<< (std::ostream &out, const DawgNode &node) -> std::ostream &
auto	operator<< (std::ostream &out, const Prefix &prefix) -> std::ostream &
template<class IterType >
auto	sorted_dawg (IterType iter, IterType end) -> SortedDawg *
	Factory function that initializes a new SortedDawg using the terms yielded from an iterator.
template auto	sorted_dawg (std::list< std::string >::iterator iter, std::list< std::string >::iterator end) -> SortedDawg *
template auto	sorted_dawg (std::vector< std::string >::iterator iter, std::vector< std::string >::iterator end) -> SortedDawg *
template auto	sorted_dawg (std::set< std::string >::iterator iter, std::set< std::string >::iterator end) -> SortedDawg *
auto	serialize_protobuf (Dawg *dawg, const fs::path &path) -> bool
	Serializes the given Dawg to protobuf at the given path.
auto	serialize_protobuf (Dawg *dawg, const std::string &path) -> bool
	Serializes the given Dawg to protobuf at the given path.
auto	serialize_protobuf (Dawg *dawg, const char *path) -> bool
	Serializes the given Dawg to protobuf at the given path.
auto	serialize_protobuf (Dawg *dawg, std::ostream &output) -> bool
	Serializes the given Dawg to protobuf into the given output stream.
auto	deserialize_protobuf (const fs::path &path) -> Dawg *
	Deserializes the protobuf containing a Dawg at the given path or returns nullptr if none exists.
auto	deserialize_protobuf (const std::string &path) -> Dawg *
	Deserializes the protobuf containing a Dawg at the given path or returns nullptr if none exists.
auto	deserialize_protobuf (const char *path) -> Dawg *
	Deserializes the protobuf containing a Dawg at the given path or returns nullptr if none exists.
auto	deserialize_protobuf (std::istream &input) -> Dawg *
	Deserializes the protobuf containing a Dawg from the given input stream or returns nullptr if none exists.
void	collect_nodes (DawgNode *source, std::set< uint64_t > &node_ids, std::set< uint64_t > &final_node_ids)
	Collects the DawgNode IDs and final DawgNode IDs of all nodes reachable from the source.
void	collect_edges (DawgNode *source, std::map< std::pair< uint64_t, char >, uint64_t > &edges)
	Collects the transitions from each source to its destination, and the respective character labels.
auto	to_protobuf (Dawg *dawg) -> llp::Dictionary *
	Serializes a Dawg to its protobuf equivalent.
auto	from_protobuf (const llp::Dictionary &dict_proto) -> Dawg *
	Deserializes a Dawg from its protobuf equivalent.
template<>
auto	compare< Algorithm::STANDARD > (Position *lhs, Position *rhs) -> int
	Compares two Positions for the standard Levenshtein transducer.
template<>
auto	compare< Algorithm::TRANSPOSITION > (Position *lhs, Position *rhs) -> int
	Compares two Positions for the standard Levenshtein transducer extended with transposition.
template<>
auto	compare< Algorithm::MERGE_AND_SPLIT > (Position *lhs, Position *rhs) -> int
	Compares two Positions for the standard Levenshtein transducer extended with merge and split.
template<Algorithm Type>
auto	compare (Position *lhs, Position *rhs) -> int
	Compares two Positions within the Levenshtein transducer.
template<>
auto	compare< Algorithm::STANDARD > (Position *lhs, Position *rhs) -> int
	Compares two Positions for the standard Levenshtein transducer.
template<>
auto	compare< Algorithm::TRANSPOSITION > (Position *lhs, Position *rhs) -> int
	Compares two Positions for the standard Levenshtein transducer extended with transposition.
template<>
auto	compare< Algorithm::MERGE_AND_SPLIT > (Position *lhs, Position *rhs) -> int
	Compares two Positions for the standard Levenshtein transducer extended with merge and split.
template<>
auto	distance< Algorithm::STANDARD > (State *state, std::size_t query_length) -> std::size_t
	Infers the Levenshtein distance from the given State and query length for the standard Levenshtein distance, which includes the elementary operations of insertion, deletion, and substitution.
template<>
auto	distance< Algorithm::TRANSPOSITION > (State *state, std::size_t query_length) -> std::size_t
	Infers the Levenshtein distance from the given State and query length for the standard Levenshtein distance extended with the elementary operation of transposition.
template<>
auto	distance< Algorithm::MERGE_AND_SPLIT > (State *state, std::size_t query_length) -> std::size_t
	Infers the Levenshtein distance from the given State and query length for the standard Levenshtein distance extended with the elementary operations of merge and split.
template<Algorithm Type>
auto	distance (State *state, std::size_t query_length) -> std::size_t
	Infers the Levenshtein distance from the given State and query length.
template<>
auto	distance< Algorithm::STANDARD > (State *state, std::size_t query_length) -> std::size_t
	Infers the Levenshtein distance from the given State and query length for the standard Levenshtein distance, which includes the elementary operations of insertion, deletion, and substitution.
template<>
auto	distance< Algorithm::TRANSPOSITION > (State *state, std::size_t query_length) -> std::size_t
	Infers the Levenshtein distance from the given State and query length for the standard Levenshtein distance extended with the elementary operation of transposition.
template<>
auto	distance< Algorithm::MERGE_AND_SPLIT > (State *state, std::size_t query_length) -> std::size_t
	Infers the Levenshtein distance from the given State and query length for the standard Levenshtein distance extended with the elementary operations of merge and split.
auto	operator<< (std::ostream &out, const Intersection &intersection) -> std::ostream &
void	insert_after (State *state, Position *curr, Position *next)
	Inserts one Position after another.
template<>
void	merge< Algorithm::STANDARD > (State *state, const std::vector< Position * > &positions)
template<>
void	merge< Algorithm::TRANSPOSITION > (State *state, const std::vector< Position * > &positions)
template<>
void	merge< Algorithm::MERGE_AND_SPLIT > (State *state, const std::vector< Position * > &positions)
template<Algorithm Type>
void	merge (State *state, const std::vector< Position * > &positions)
	Merges a list of Positions into the Levenshtein state.
auto	index_of (std::vector< bool > &characteristic_vector, std::size_t k, std::size_t i) -> std::size_t
	Returns the first index of the desired character in the characteristic vector, beginning at the offset \(i\).
template<>
auto	position_transition< Algorithm::STANDARD > (std::size_t n, Position *position, std::vector< bool > &characteristic_vector, std::size_t offset) -> std::vector< Position * >
	Returns the closure over possible next Positions that are reachable from the current Position by advancing the location in the dictionary by one.
template<>
auto	position_transition< Algorithm::TRANSPOSITION > (std::size_t n, Position *position, std::vector< bool > &characteristic_vector, std::size_t offset) -> std::vector< Position * >
	Returns the closure over possible next Positions that are reachable from the current Position by advancing the location in the dictionary by one.
template<>
auto	position_transition< Algorithm::MERGE_AND_SPLIT > (std::size_t n, Position *position, std::vector< bool > &characteristic_vector, std::size_t offset) -> std::vector< Position * >
	Returns the closure over possible next Positions that are reachable from the current Position by advancing the location in the dictionary by one.
template<Algorithm Type>
auto	position_transition (std::size_t n, Position *position, std::vector< bool > &characteristic_vector, std::size_t offset) -> std::vector< Position * >
	Returns the closure over possible next Positions that are reachable from the current Position by advancing the location in the dictionary by one.
template<>
auto	position_transition< Algorithm::STANDARD > (std::size_t n, Position *position, std::vector< bool > &characteristic_vector, std::size_t offset) -> std::vector< Position * >
	Returns the closure over possible next Positions that are reachable from the current Position by advancing the location in the dictionary by one.
template<>
auto	position_transition< Algorithm::TRANSPOSITION > (std::size_t n, Position *position, std::vector< bool > &characteristic_vector, std::size_t offset) -> std::vector< Position * >
	Returns the closure over possible next Positions that are reachable from the current Position by advancing the location in the dictionary by one.
template<>
auto	position_transition< Algorithm::MERGE_AND_SPLIT > (std::size_t n, Position *position, std::vector< bool > &characteristic_vector, std::size_t offset) -> std::vector< Position * >
	Returns the closure over possible next Positions that are reachable from the current Position by advancing the location in the dictionary by one.
template<>
auto	subsumes< Algorithm::STANDARD > (Position *lhs, Position *rhs, std::size_t n) -> bool
	Returns whether lhs subsumes rhs according to the subsumption rules of standard Levenshtein distance, which consists of the elementary operations of insertion, deletion, and substitution.
template<>
auto	subsumes< Algorithm::TRANSPOSITION > (Position *lhs, Position *rhs, std::size_t n) -> bool
	Returns whether lhs subsumes rhs according to the subsumption rules of standard Levenshtein distance extended with the elementary operation of transposition.
template<>
auto	subsumes< Algorithm::MERGE_AND_SPLIT > (Position *lhs, Position *rhs, std::size_t n) -> bool
	Returns whether lhs subsumes rhs according to the subsumption rules of standard Levenshtein distance extended with the elementary operations of merge and split.
template<Algorithm Type>
auto	subsumes (Position *lhs, Position *rhs, std::size_t n) -> bool
	Returns whether Position lhs subsumes Position rhs, given the maximum edit distance n.
template<>
auto	subsumes< Algorithm::STANDARD > (Position *lhs, Position *rhs, std::size_t n) -> bool
	Returns whether lhs subsumes rhs according to the subsumption rules of standard Levenshtein distance, which consists of the elementary operations of insertion, deletion, and substitution.
template<>
auto	subsumes< Algorithm::TRANSPOSITION > (Position *lhs, Position *rhs, std::size_t n) -> bool
	Returns whether lhs subsumes rhs according to the subsumption rules of standard Levenshtein distance extended with the elementary operation of transposition.
template<>
auto	subsumes< Algorithm::MERGE_AND_SPLIT > (Position *lhs, Position *rhs, std::size_t n) -> bool
	Returns whether lhs subsumes rhs according to the subsumption rules of standard Levenshtein distance extended with the elementary operations of merge and split.

Detailed Description

Various utilities regarding Levenshtein transducers.

The classes of interest, to most, will be the various dictionaries, transducer implementations, and serializers. The remaining classes are likely of little interest to anyone but maintainers and the curiously minded.

Typedef Documentation

Candidate

using liblevenshtein::Candidate = std::pair<std::string, std::size_t>

Spelling candidate that includes both the dictionary term and its edit distance from the query term.

Definition at line 17 of file transducer.h.

Comparator

using liblevenshtein::Comparator = std::function<int(Position *, Position *)>

Definition at line 12 of file state.h.

CompareFn

using liblevenshtein::CompareFn = std::function<int(Position *, Position *)>

Compares Position nodes.

Definition at line 20 of file state_transition.h.

DistanceFn

using liblevenshtein::DistanceFn = std::function<std::size_t(State *, std::size_t)>

Infers the Levenshtein distance from a final Levenshtein State and the length of the query term.

Definition at line 23 of file lazy_query.h.

MergeFn

using liblevenshtein::MergeFn = std::function<void(State *, std::vector<Position *>)>

Merges Position nodes into a State.

Definition at line 23 of file state_transition.h.

PositionTransitionFn

using liblevenshtein::PositionTransitionFn

Initial value:

 
  std::function<std::vector<Position *>(std::size_t, Position *,
                      std::vector<bool>&, std::size_t)>

Transitions Position nodes.

Definition at line 15 of file state_transition.h.

SubsumesFn

using liblevenshtein::SubsumesFn = std::function<bool(Position *, Position *, std::size_t)>

Determines whether one Position subsumes another given the maximum edit distance to consider.

Definition at line 14 of file unsubsume.h.

TransitionFn

using liblevenshtein::TransitionFn = std::function<State *(State *, std::vector<bool> &)>

Returns the Levenshtein State mapped-to by another State and characteristic vector.

Definition at line 19 of file lazy_query.h.

Enumeration Type Documentation

Algorithm

enum class liblevenshtein::Algorithm

strong

Enumerates the available Levenshtein distance algorithms.

Enumerator
STANDARD	Standard Levenshtein distance, including the elementary operations of insertion, deletion, and substitution.
TRANSPOSITION	Standard Levenshtein distance extended with the elementary operation of transposition.
MERGE_AND_SPLIT	Standard Levenshtein distance extended with the elementary operations of merge and split.

Definition at line 9 of file algorithm.h.

                     {
 
  STANDARD,
 
  TRANSPOSITION,
 
  MERGE_AND_SPLIT
};

Function Documentation

collect_edges()

void liblevenshtein::collect_edges	(	DawgNode *	source,
		std::map< std::pair< uint64_t, char >, uint64_t > &	edges )

Collects the transitions from each source to its destination, and the respective character labels.

Parameters

source	Initial node for the transition.
edges	Transition mapping of source DawgNode IDs and labels to their respective target DawgNode IDs.

Definition at line 82 of file serializer.cpp.

                                                                     {
  auto source_id = reinterpret_cast<uint64_t>(source);
  source->for_each_edge([&](char label, DawgNode *target) {
    std::pair<uint64_t, char> key = std::make_pair(source_id, label);
    if (!edges.contains(key)) {
      auto target_id = reinterpret_cast<uint64_t>(target);
      edges[key] = target_id;
      collect_edges(target, edges);
    }
  });
}

References collect_edges(), liblevenshtein::DawgNode::for_each_edge(), and query().

Referenced by collect_edges(), and to_protobuf().

Here is the call graph for this function:

Here is the caller graph for this function:

collect_nodes()

void liblevenshtein::collect_nodes	(	DawgNode *	source,
		std::set< uint64_t > &	node_ids,
		std::set< uint64_t > &	final_node_ids )

Collects the DawgNode IDs and final DawgNode IDs of all nodes reachable from the source.

Parameters

source	DawgNode whose ID is to be collected.
node_ids	DawgNode IDs reachable from the source.
final_node_ids	Final DawgNode IDs reachable from the source.

Definition at line 68 of file serializer.cpp.

                                                     {
  auto source_id = reinterpret_cast<uint64_t>(source);
  if (!node_ids.contains(source_id)) {
    node_ids.insert(source_id);
    if (source->is_final()) {
      final_node_ids.insert(source_id);
    }
    source->for_each_edge([&](char label, DawgNode *target) {
      collect_nodes(target, node_ids, final_node_ids);
    });
  }
}

References collect_nodes(), liblevenshtein::DawgNode::for_each_edge(), liblevenshtein::DawgNode::is_final(), and query().

Referenced by collect_nodes(), and to_protobuf().

Here is the call graph for this function:

Here is the caller graph for this function:

compare()

template<Algorithm Type>

auto liblevenshtein::compare	(	Position *	lhs,
		Position *	rhs ) -> int

Compares two Positions within the Levenshtein transducer.

Parameters

lhs	First Position to compare.
rhs	Second Position to compare.

Returns

A negative value if \(lhs < rhs\), a positive value if \(lhs > rhs\), or zero if \(lhs = rhs\).

Referenced by liblevenshtein::State::merge(), liblevenshtein::State::merge_sort(), liblevenshtein::StateTransition::operator()(), and liblevenshtein::State::sort().

Here is the caller graph for this function:

compare< Algorithm::MERGE_AND_SPLIT >() [1/2]

template<>

auto liblevenshtein::compare< Algorithm::MERGE_AND_SPLIT >	(	Position *	lhs,
		Position *	rhs ) -> int

Compares two Positions for the standard Levenshtein transducer extended with merge and split.

Parameters

lhs	First Position to compare.
rhs	Second Position to compare.

Returns

A negative value if \(lhs < rhs\), a positive value if \(lhs > rhs\), or zero if \(lhs = rhs\).

Definition at line 53 of file comparator.cpp.

                                                                            {
  if (lhs->term_index() < rhs->term_index()) {
    return -1;
  }
 
  if (lhs->term_index() > rhs->term_index()) {
    return 1;
  }
 
  if (lhs->num_errors() < rhs->num_errors()) {
    return -1;
  }
 
  if (lhs->num_errors() > rhs->num_errors()) {
    return 1;
  }
 
  return static_cast<int>(lhs->is_special()) -
         static_cast<int>(rhs->is_special());
}

References query().

Here is the call graph for this function:

compare< Algorithm::MERGE_AND_SPLIT >() [2/2]

template<>

auto liblevenshtein::compare< Algorithm::MERGE_AND_SPLIT >	(	Position *	lhs,
		Position *	rhs ) -> int

Compares two Positions for the standard Levenshtein transducer extended with merge and split.

Parameters

lhs	First Position to compare.
rhs	Second Position to compare.

Returns

A negative value if \(lhs < rhs\), a positive value if \(lhs > rhs\), or zero if \(lhs = rhs\).

Definition at line 53 of file comparator.cpp.

                                                                            {
  if (lhs->term_index() < rhs->term_index()) {
    return -1;
  }
 
  if (lhs->term_index() > rhs->term_index()) {
    return 1;
  }
 
  if (lhs->num_errors() < rhs->num_errors()) {
    return -1;
  }
 
  if (lhs->num_errors() > rhs->num_errors()) {
    return 1;
  }
 
  return static_cast<int>(lhs->is_special()) -
         static_cast<int>(rhs->is_special());
}

References query().

Here is the call graph for this function:

compare< Algorithm::STANDARD >() [1/2]

template<>

auto liblevenshtein::compare< Algorithm::STANDARD >	(	Position *	lhs,
		Position *	rhs ) -> int

Compares two Positions for the standard Levenshtein transducer.

Parameters

lhs	First Position to compare.
rhs	Second Position to compare.

Returns

A negative value if \(lhs < rhs\), a positive value if \(lhs > rhs\), or zero if \(lhs = rhs\).

Definition at line 10 of file comparator.cpp.

                                                                     {
  if (lhs->term_index() < rhs->term_index()) {
    return -1;
  }
 
  if (lhs->term_index() > rhs->term_index()) {
    return 1;
  }
 
  if (lhs->num_errors() < rhs->num_errors()) {
    return -1;
  }
 
  if (lhs->num_errors() > rhs->num_errors()) {
    return 1;
  }
 
  return 0;
}

References query().

Here is the call graph for this function:

compare< Algorithm::STANDARD >() [2/2]

template<>

auto liblevenshtein::compare< Algorithm::STANDARD >	(	Position *	lhs,
		Position *	rhs ) -> int

Compares two Positions for the standard Levenshtein transducer.

Parameters

lhs	First Position to compare.
rhs	Second Position to compare.

Returns

A negative value if \(lhs < rhs\), a positive value if \(lhs > rhs\), or zero if \(lhs = rhs\).

Definition at line 10 of file comparator.cpp.

                                                                     {
  if (lhs->term_index() < rhs->term_index()) {
    return -1;
  }
 
  if (lhs->term_index() > rhs->term_index()) {
    return 1;
  }
 
  if (lhs->num_errors() < rhs->num_errors()) {
    return -1;
  }
 
  if (lhs->num_errors() > rhs->num_errors()) {
    return 1;
  }
 
  return 0;
}

References query().

Here is the call graph for this function:

compare< Algorithm::TRANSPOSITION >() [1/2]

template<>

auto liblevenshtein::compare< Algorithm::TRANSPOSITION >	(	Position *	lhs,
		Position *	rhs ) -> int

Compares two Positions for the standard Levenshtein transducer extended with transposition.

Parameters

lhs	First Position to compare.
rhs	Second Position to compare.

Returns

A negative value if \(lhs < rhs\), a positive value if \(lhs > rhs\), or zero if \(lhs = rhs\).

Definition at line 31 of file comparator.cpp.

                                                                          {
  if (lhs->term_index() < rhs->term_index()) {
    return -1;
  }
 
  if (lhs->term_index() > rhs->term_index()) {
    return 1;
  }
 
  if (lhs->num_errors() < rhs->num_errors()) {
    return -1;
  }
 
  if (lhs->num_errors() > rhs->num_errors()) {
    return 1;
  }
 
  return static_cast<int>(lhs->is_special()) -
         static_cast<int>(rhs->is_special());
}

References query().

Here is the call graph for this function:

compare< Algorithm::TRANSPOSITION >() [2/2]

template<>

auto liblevenshtein::compare< Algorithm::TRANSPOSITION >	(	Position *	lhs,
		Position *	rhs ) -> int

Compares two Positions for the standard Levenshtein transducer extended with transposition.

Parameters

lhs	First Position to compare.
rhs	Second Position to compare.

Returns

A negative value if \(lhs < rhs\), a positive value if \(lhs > rhs\), or zero if \(lhs = rhs\).

Definition at line 31 of file comparator.cpp.

                                                                          {
  if (lhs->term_index() < rhs->term_index()) {
    return -1;
  }
 
  if (lhs->term_index() > rhs->term_index()) {
    return 1;
  }
 
  if (lhs->num_errors() < rhs->num_errors()) {
    return -1;
  }
 
  if (lhs->num_errors() > rhs->num_errors()) {
    return 1;
  }
 
  return static_cast<int>(lhs->is_special()) -
         static_cast<int>(rhs->is_special());
}

References query().

Here is the call graph for this function:

deserialize_protobuf() [1/4]

auto liblevenshtein::deserialize_protobuf

(

const char *

path

)

-> Dawg *

Deserializes the protobuf containing a Dawg at the given path or returns nullptr if none exists.

Parameters

path	Path to the serialization file.

Returns

A pointer to the deserialized Dawg or nullptr if none exists.

Definition at line 52 of file serializer.cpp.

                                                      {
  std::fstream input(path, std::fstream::in | std::fstream::binary);
  Dawg *dawg = deserialize_protobuf(input);
  input.close();
  return dawg;
}

References deserialize_protobuf(), and query().

Here is the call graph for this function:

deserialize_protobuf() [2/4]

auto liblevenshtein::deserialize_protobuf

(

const fs::path &

path

)

-> Dawg *

Deserializes the protobuf containing a Dawg at the given path or returns nullptr if none exists.

Parameters

path	Path to the serialization file.

Returns

The deserialized Dawg or nullptr if none exists.

Definition at line 44 of file serializer.cpp.

                                                        {
  return deserialize_protobuf(path.generic_string());
}

References deserialize_protobuf(), and query().

Referenced by deserialize_protobuf(), deserialize_protobuf(), deserialize_protobuf(), and main().

Here is the call graph for this function:

Here is the caller graph for this function:

deserialize_protobuf() [3/4]

auto liblevenshtein::deserialize_protobuf

(

const std::string &

path

)

-> Dawg *

Deserializes the protobuf containing a Dawg at the given path or returns nullptr if none exists.

Parameters

path	Path to the serialization file.

Returns

The deserialized Dawg or nullptr if none exists.

Definition at line 48 of file serializer.cpp.

                                                           {
  return deserialize_protobuf(path.c_str());
}

References deserialize_protobuf(), and query().

Here is the call graph for this function:

deserialize_protobuf() [4/4]

auto liblevenshtein::deserialize_protobuf

(

std::istream &

input

)

-> Dawg *

Deserializes the protobuf containing a Dawg from the given input stream or returns nullptr if none exists.

Parameters

path	input Input stream containing the serialized Dawg.

Returns

A pointer to the deserialized Dawg or nullptr if none exists.

Definition at line 59 of file serializer.cpp.

                                                       {
  Dawg *dawg = nullptr;
  llp::Dictionary dict_proto;
  if (dict_proto.ParseFromIstream(&input)) {
    dawg = from_protobuf(dict_proto);
  }
  return dawg;
}

References from_protobuf(), and query().

Here is the call graph for this function:

distance()

template<Algorithm Type>

auto liblevenshtein::distance	(	State *	state,
		std::size_t	query_length ) -> std::size_t

Infers the Levenshtein distance from the given State and query length.

Parameters

state	Levenshtein transducer final State from which we may infer the respective distance.
query_length	Length of the query term which is necessary for inferring the distance from the given State.

Returns

The Levenshtein distance from the given State and query length.

References distance().

Referenced by liblevenshtein::LazyQuery< Result >::advance(), liblevenshtein::distance::MergeAndSplitDistance::between(), liblevenshtein::distance::StandardDistance::between(), liblevenshtein::distance::TranspositionDistance::between(), distance(), distance< Algorithm::MERGE_AND_SPLIT >(), distance< Algorithm::STANDARD >(), distance< Algorithm::TRANSPOSITION >(), liblevenshtein::distance::MemoizedDistance::get(), liblevenshtein::distance::MemoizedDistance::set(), and liblevenshtein::LazyQuery< Result >::update_candidate().

Here is the call graph for this function:

Here is the caller graph for this function:

distance< Algorithm::MERGE_AND_SPLIT >() [1/2]

template<>

auto liblevenshtein::distance< Algorithm::MERGE_AND_SPLIT >	(	State *	state,
		std::size_t	query_length ) -> std::size_t

Infers the Levenshtein distance from the given State and query length for the standard Levenshtein distance extended with the elementary operations of merge and split.

Parameters

state	Levenshtein transducer final State from which we may infer the respective distance.
query_length	Length of the query term which is necessary for inferring the distance from the given State.

Returns

The Levenshtein distance from the given State and query length.

Definition at line 42 of file distance.cpp.

                 {
  std::size_t min_distance = SIZE_MAX;
  for (Position *position : *state) {
    if (!position->is_special()) {
      std::size_t i = position->term_index();
      std::size_t e = position->num_errors();
      std::size_t distance = query_length - i + e;
      if (distance < min_distance) {
        min_distance = distance;
      }
    }
  }
  return min_distance;
}

References distance(), and query().

Here is the call graph for this function:

distance< Algorithm::MERGE_AND_SPLIT >() [2/2]

template<>

auto liblevenshtein::distance< Algorithm::MERGE_AND_SPLIT >	(	State *	state,
		std::size_t	query_length ) -> std::size_t

Infers the Levenshtein distance from the given State and query length for the standard Levenshtein distance extended with the elementary operations of merge and split.

Parameters

state	Levenshtein transducer final State from which we may infer the respective distance.
query_length	Length of the query term which is necessary for inferring the distance from the given State.

Returns

The Levenshtein distance from the given State and query length.

Definition at line 42 of file distance.cpp.

                 {
  std::size_t min_distance = SIZE_MAX;
  for (Position *position : *state) {
    if (!position->is_special()) {
      std::size_t i = position->term_index();
      std::size_t e = position->num_errors();
      std::size_t distance = query_length - i + e;
      if (distance < min_distance) {
        min_distance = distance;
      }
    }
  }
  return min_distance;
}

References distance(), and query().

Here is the call graph for this function:

distance< Algorithm::STANDARD >() [1/2]

template<>

auto liblevenshtein::distance< Algorithm::STANDARD >	(	State *	state,
		std::size_t	query_length ) -> std::size_t

Infers the Levenshtein distance from the given State and query length for the standard Levenshtein distance, which includes the elementary operations of insertion, deletion, and substitution.

Parameters

state	Levenshtein transducer final State from which we may infer the respective distance.
query_length	Length of the query term which is necessary for inferring the distance from the given State.

Returns

The Levenshtein distance from the given State and query length.

Definition at line 10 of file distance.cpp.

                 {
  std::size_t min_distance = SIZE_MAX;
  for (Position *position : *state) {
    std::size_t i = position->term_index();
    std::size_t e = position->num_errors();
    std::size_t distance = query_length - i + e;
    if (distance < min_distance) {
      min_distance = distance;
    }
  }
  return min_distance;
}

References distance(), and query().

Here is the call graph for this function:

distance< Algorithm::STANDARD >() [2/2]

template<>

auto liblevenshtein::distance< Algorithm::STANDARD >	(	State *	state,
		std::size_t	query_length ) -> std::size_t

Infers the Levenshtein distance from the given State and query length for the standard Levenshtein distance, which includes the elementary operations of insertion, deletion, and substitution.

Parameters

state	Levenshtein transducer final State from which we may infer the respective distance.
query_length	Length of the query term which is necessary for inferring the distance from the given State.

Returns

The Levenshtein distance from the given State and query length.

Definition at line 10 of file distance.cpp.

                 {
  std::size_t min_distance = SIZE_MAX;
  for (Position *position : *state) {
    std::size_t i = position->term_index();
    std::size_t e = position->num_errors();
    std::size_t distance = query_length - i + e;
    if (distance < min_distance) {
      min_distance = distance;
    }
  }
  return min_distance;
}

References distance(), and query().

Here is the call graph for this function:

distance< Algorithm::TRANSPOSITION >() [1/2]

template<>

auto liblevenshtein::distance< Algorithm::TRANSPOSITION >	(	State *	state,
		std::size_t	query_length ) -> std::size_t

Infers the Levenshtein distance from the given State and query length for the standard Levenshtein distance extended with the elementary operation of transposition.

Parameters

state	Levenshtein transducer final State from which we may infer the respective distance.
query_length	Length of the query term which is necessary for inferring the distance from the given State.

Returns

The Levenshtein distance from the given State and query length.

Definition at line 25 of file distance.cpp.

                 {
  std::size_t min_distance = SIZE_MAX;
  for (Position *position : *state) {
    if (!position->is_special()) {
      std::size_t i = position->term_index();
      std::size_t e = position->num_errors();
      std::size_t distance = query_length - i + e;
      if (distance < min_distance) {
        min_distance = distance;
      }
    }
  }
  return min_distance;
}

References distance(), and query().

Here is the call graph for this function:

distance< Algorithm::TRANSPOSITION >() [2/2]

template<>

auto liblevenshtein::distance< Algorithm::TRANSPOSITION >	(	State *	state,
		std::size_t	query_length ) -> std::size_t

Infers the Levenshtein distance from the given State and query length for the standard Levenshtein distance extended with the elementary operation of transposition.

Parameters

state	Levenshtein transducer final State from which we may infer the respective distance.
query_length	Length of the query term which is necessary for inferring the distance from the given State.

Returns

The Levenshtein distance from the given State and query length.

Definition at line 25 of file distance.cpp.

                 {
  std::size_t min_distance = SIZE_MAX;
  for (Position *position : *state) {
    if (!position->is_special()) {
      std::size_t i = position->term_index();
      std::size_t e = position->num_errors();
      std::size_t distance = query_length - i + e;
      if (distance < min_distance) {
        min_distance = distance;
      }
    }
  }
  return min_distance;
}

References distance(), and query().

Here is the call graph for this function:

from_protobuf()

auto liblevenshtein::from_protobuf

(

const llp::Dictionary &

dict_proto

)

-> Dawg *

Deserializes a Dawg from its protobuf equivalent.

Parameters

dict_proto

Protobuf containing the serialized information necessary for reconstructing the Dawg.

Returns

A pointer to the deserialized Dawg.

Definition at line 128 of file serializer.cpp.

                                                              {
  std::set<uint64_t> final_node_ids;
  for (int index = 0; index < dict_proto.final_node_id_size(); index += 1) {
    uint64_t final_node_id = dict_proto.final_node_id(index);
    final_node_ids.insert(final_node_id);
  }
 
  std::map<uint64_t, DawgNode *> nodes;
  for (int index = 0; index < dict_proto.node_id_size(); index += 1) {
    uint64_t node_id = dict_proto.node_id(index);
    if (!nodes.contains(node_id)) {
      bool is_final = final_node_ids.contains(node_id);
      auto *node = new DawgNode(is_final);
      nodes[node_id] = node;
    }
  }
 
  for (int index = 0; index < dict_proto.edge_size(); index += 1) {
    const llp::Dictionary_Edge &edge_proto = dict_proto.edge(index);
    uint64_t source_id = edge_proto.source_id();
    char label = (char)edge_proto.label();
    uint64_t target_id = edge_proto.target_id();
    DawgNode *source = nodes[source_id];
    DawgNode *target = nodes[target_id];
    source->add_edge(label, target);
  }
 
  DawgNode *root = nodes[dict_proto.root_id()];
  auto *dawg = new SortedDawg(root, dict_proto.size());
  return dawg;
}

References liblevenshtein::DawgNode::add_edge(), liblevenshtein::Dawg::contains(), and query().

Referenced by deserialize_protobuf().

Here is the call graph for this function:

Here is the caller graph for this function:

index_of()

auto liblevenshtein::index_of	(	std::vector< bool > &	characteristic_vector,
		std::size_t	k,
		std::size_t	i ) -> std::size_t

Returns the first index of the desired character in the characteristic vector, beginning at the offset \(i\).

The characteristic vector represents a sort of moving window over the characters of the query term, and flags the locations within that window whose corresponding query term characters match the desired character from the dictionary term.

Parameters

characteristic_vector	Moving window over the which query term characters match the desired one from the dictionary term.
k	Upper bound of the characteristic vector.
i	Beginning index (offset) to seek the desired character.

Returns

The first index from the characteristic vector matching the desired character.

Definition at line 6 of file position_transition.cpp.

                                        {
  for (std::size_t j = 0; j < k; j += 1) {
    if (characteristic_vector[i + j]) {
      return j;
    }
  }
  return SIZE_MAX;
}

References query().

Referenced by position_transition< Algorithm::STANDARD >(), and position_transition< Algorithm::TRANSPOSITION >().

Here is the call graph for this function:

Here is the caller graph for this function:

insert_after()

void liblevenshtein::insert_after	(	State *	state,
		Position *	curr,
		Position *	next )

Inserts one Position after another.

Parameters

state	Levenshtein State whose positions are being merged.
curr	Position whose follow Position is being updated.
next	Position to insert after curr.

Definition at line 8 of file merge.cpp.

                                                                {
  if (curr == nullptr) {
    state->head(next);
  }
  else {
    state->insert_after(curr, next);
  }
}

References liblevenshtein::State::head(), liblevenshtein::State::insert_after(), and query().

Referenced by merge< Algorithm::MERGE_AND_SPLIT >(), merge< Algorithm::STANDARD >(), and merge< Algorithm::TRANSPOSITION >().

Here is the call graph for this function:

Here is the caller graph for this function:

merge()

template<Algorithm Type>

void liblevenshtein::merge	(	State *	state,
		const std::vector< Position * > &	positions )

Merges a list of Positions into the Levenshtein state.

This operation greatly speeds up the matching of spelling candidates.

Parameters

state	Levenshtein State whose positions are to be merged with the others.
positions	Positions to merge into the State.

Referenced by liblevenshtein::State::merge_sort(), and liblevenshtein::StateTransition::operator()().

Here is the caller graph for this function:

merge< Algorithm::MERGE_AND_SPLIT >()

template<>

void liblevenshtein::merge< Algorithm::MERGE_AND_SPLIT >	(	State *	state,
		const std::vector< Position * > &	positions )

Definition at line 108 of file merge.cpp.

                                                          {
  for (Position *a : positions) {
    std::size_t i = a->term_index();
    std::size_t e = a->num_errors();
    bool s = a->is_special();
 
    StateIterator iter = state->begin();
    StateIterator iter_end = state->end();
    Position *p = nullptr;
 
    while (iter != iter_end) {
      Position *b = *iter;
      std::size_t j = b->term_index();
      std::size_t f = b->num_errors();
      bool t = b->is_special();
 
      if (e < f || e == f && (i < j || i == j && !s && t)) {
        p = b;
        ++iter;
      }
      else {
        break;
      }
    }
 
    if (iter != iter_end) {
      Position *b = *iter;
      ++iter;
 
      std::size_t j = b->term_index();
      std::size_t f = b->num_errors();
      bool t = b->is_special();
 
      if (j != i || f != e || t != s) {
        insert_after(state, p, a);
      }
      else {
        delete a;
      }
    }
    else {
      insert_after(state, p, a);
    }
  }
}

References liblevenshtein::State::begin(), liblevenshtein::State::end(), insert_after(), query(), and liblevenshtein::Position::term_index().

Here is the call graph for this function:

merge< Algorithm::STANDARD >()

template<>

void liblevenshtein::merge< Algorithm::STANDARD >	(	State *	state,
		const std::vector< Position * > &	positions )

Definition at line 18 of file merge.cpp.

                                                                        {
  for (Position *a : positions) {
    std::size_t i = a->term_index();
    std::size_t e = a->num_errors();
 
    StateIterator iter = state->begin();
    StateIterator iter_end = state->end();
    Position *p = nullptr;
 
    while (iter != iter_end) {
      Position *b = *iter;
      std::size_t j = b->term_index();
      std::size_t f = b->num_errors();
 
      if ((e < f) || (e == f) && (i < j)) {
        p = b;
        ++iter;
      } else {
        break;
      }
    }
 
    if (iter != iter_end) {
      Position *b = *iter;
      std::size_t j = b->term_index();
      std::size_t f = b->num_errors();
 
      if ((j != i) || (f != e)) {
        insert_after(state, p, a);
      }
      else {
        delete a;
      }
    }
    else {
      insert_after(state, p, a);
    }
  }
}

References liblevenshtein::State::begin(), liblevenshtein::State::end(), insert_after(), query(), and liblevenshtein::Position::term_index().

Here is the call graph for this function:

merge< Algorithm::TRANSPOSITION >()

template<>

void liblevenshtein::merge< Algorithm::TRANSPOSITION >	(	State *	state,
		const std::vector< Position * > &	positions )

Definition at line 60 of file merge.cpp.

                                                                             {
  for (Position *a : positions) {
    std::size_t i = a->term_index();
    std::size_t e = a->num_errors();
    bool s = a->is_special();
 
    StateIterator iter = state->begin();
    StateIterator iter_end = state->end();
    Position *p = nullptr;
 
    while (iter != iter_end) {
      Position *b = *iter;
      std::size_t j = b->term_index();
      std::size_t f = b->num_errors();
      bool t = b->is_special();
 
      if (e < f || e == f && (i < j || i == j && !s && t)) {
        p = b;
        ++iter;
      }
      else {
        break;
      }
    }
 
    if (iter != iter_end) {
      Position *b = *iter;
      ++iter;
 
      std::size_t j = b->term_index();
      std::size_t f = b->num_errors();
      bool t = b->is_special();
 
      if (j != i || f != e || t != s) {
        insert_after(state, p, a);
      }
      else {
        delete a;
      }
    }
    else {
      insert_after(state, p, a);
    }
  }
}

References liblevenshtein::State::begin(), liblevenshtein::State::end(), insert_after(), query(), and liblevenshtein::Position::term_index().

Here is the call graph for this function:

operator<<() [1/4]

auto liblevenshtein::operator<<	(	std::ostream &	out,
		const Dawg &	dawg ) -> std::ostream &

Definition at line 67 of file dawg.cpp.

                                                                   {
  out << "Dawg{size=" << dawg._size << ", root=" << dawg._root << "}";
  return out;
}

operator<<() [2/4]

auto liblevenshtein::operator<<	(	std::ostream &	out,
		const DawgNode &	node ) -> std::ostream &

Definition at line 77 of file dawg_node.cpp.

                                                                       {
  out << "DawgNode{is_final=" << (node.is_final() ? "true" : "false") << ", edges={";
  int index = 0;
  node.for_each_edge([&](char label, DawgNode *target) {
    if (index > 0) {
      out << ", ";
    }
    out << "'" << label << "':DawgNode{...}";
    index += 1;
  });
  out << "}}";
  return out;
}

References query().

Here is the call graph for this function:

operator<<() [3/4]

auto liblevenshtein::operator<<	(	std::ostream &	out,
		const Intersection &	intersection ) -> std::ostream &

Definition at line 31 of file intersection.cpp.

                    {
  if (intersection._parent != nullptr) {
    out << *(intersection._parent) << intersection._label;
  }
  return out;
}

operator<<() [4/4]

auto liblevenshtein::operator<<	(	std::ostream &	out,
		const Prefix &	prefix ) -> std::ostream &

Definition at line 40 of file prefix.cpp.

                                                                       {
  if (prefix._parent != nullptr) {
    out << *(prefix._parent) << prefix._label;
  }
  return out;
}

position_transition()

template<Algorithm Type>

auto liblevenshtein::position_transition	(	std::size_t	n,
		Position *	position,
		std::vector< bool > &	characteristic_vector,
		std::size_t	offset ) -> std::vector< Position * >

Returns the closure over possible next Positions that are reachable from the current Position by advancing the location in the dictionary by one.

Parameters

n	Maximum edit distance to consider when matching spelling candidates.
position	Current Position within the Levenshtein automaton.
characteristic_vector	Moving window over matching characters of the query term.
offset	Where to begin examining the chracteristic_vector.

Returns

The closure over the next Positions reachable from the current Position by advancing the location in the dictionary by one.

position_transition< Algorithm::MERGE_AND_SPLIT >() [1/2]

template<>

auto liblevenshtein::position_transition< Algorithm::MERGE_AND_SPLIT >	(	std::size_t	n,
		Position *	position,
		std::vector< bool > &	characteristic_vector,
		std::size_t	offset ) -> std::vector< Position * >

Returns the closure over possible next Positions that are reachable from the current Position by advancing the location in the dictionary by one.

This covers transitions within the standard Levenshtein distance, extended with the elementary operations of merge and split.

Parameters

n	Maximum edit distance to consider when matching spelling candidates.
position	Current Position within the Levenshtein automaton.
characteristic_vector	Moving window over matching characters of the query term.
offset	Where to begin examining the chracteristic_vector.

Returns

The closure over the next Positions reachable from the current Position by advancing the location in the dictionary by one.

Definition at line 232 of file position_transition.cpp.

                                               {
 
  std::size_t i = position->term_index();
  std::size_t e = position->num_errors();
  bool s = position->is_special();
  std::size_t h = i - offset;
  std::size_t w = characteristic_vector.size();
 
  if (e == 0 && 0 < n) {
    if (h + 2 <= w) {
      if (characteristic_vector[h]) {
        return {
          new Position(i + 1, e)
        };
      }
 
      return {
        new Position(i, e + 1),
        new Position(i, e + 1, true),
        new Position(i + 1, e + 1),
        new Position(i + 2, e + 1)
      };
    }
 
    if (h + 1 == w) {
      if (characteristic_vector[h]) {
        return {
          new Position(i + 1, e)
        };
      }
 
      return {
        new Position(i, e + 1),
        new Position(i, e + 1, true),
        new Position(i + 1, e + 1)
      };
    }
 
    return {
      new Position(i, e + 1)
    };
  }
 
  if (e < n) {
    if (h + 2 <= w) {
      if (!s) {
        if (characteristic_vector[h]) {
          return {
            new Position(i + 1, e)
          };
        }
 
        return {
          new Position(i, e + 1),
          new Position(i, e + 1, true),
          new Position(i + 1, e + 1),
          new Position(i + 2, e + 1)
        };
      }
 
      return {
        new Position(i + 1, e)
      };
    }
 
    if (h + 1 == w) {
      if (!s) {
        if (characteristic_vector[h]) {
          return {
            new Position(i + 1, e)
          };
        }
 
        return {
          new Position(i, e + 1),
          new Position(i, e + 1, true),
          new Position(i + 1, e + 1)
        };
      }
 
      return {
        new Position(i + 1, e)
      };
    }
 
    return {
      new Position(i, e + 1)
    };
  }
 
  if (h + 1 <= w) {
    if (!s) {
      if (characteristic_vector[h]) {
        return {
          new Position(i + 1, n)
        };
      }
 
      return {};
    }
 
    return {
      new Position(i + 1, e)
    };
  }
 
  return {};
}

References query(), and liblevenshtein::Position::term_index().

Here is the call graph for this function:

position_transition< Algorithm::MERGE_AND_SPLIT >() [2/2]

template<>

auto liblevenshtein::position_transition< Algorithm::MERGE_AND_SPLIT >	(	std::size_t	n,
		Position *	position,
		std::vector< bool > &	characteristic_vector,
		std::size_t	offset ) -> std::vector< Position * >

Returns the closure over possible next Positions that are reachable from the current Position by advancing the location in the dictionary by one.

This covers transitions within the standard Levenshtein distance, extended with the elementary operations of merge and split.

Parameters

n	Maximum edit distance to consider when matching spelling candidates.
position	Current Position within the Levenshtein automaton.
characteristic_vector	Moving window over matching characters of the query term.
offset	Where to begin examining the chracteristic_vector.

Returns

The closure over the next Positions reachable from the current Position by advancing the location in the dictionary by one.

Definition at line 232 of file position_transition.cpp.

                                               {
 
  std::size_t i = position->term_index();
  std::size_t e = position->num_errors();
  bool s = position->is_special();
  std::size_t h = i - offset;
  std::size_t w = characteristic_vector.size();
 
  if (e == 0 && 0 < n) {
    if (h + 2 <= w) {
      if (characteristic_vector[h]) {
        return {
          new Position(i + 1, e)
        };
      }
 
      return {
        new Position(i, e + 1),
        new Position(i, e + 1, true),
        new Position(i + 1, e + 1),
        new Position(i + 2, e + 1)
      };
    }
 
    if (h + 1 == w) {
      if (characteristic_vector[h]) {
        return {
          new Position(i + 1, e)
        };
      }
 
      return {
        new Position(i, e + 1),
        new Position(i, e + 1, true),
        new Position(i + 1, e + 1)
      };
    }
 
    return {
      new Position(i, e + 1)
    };
  }
 
  if (e < n) {
    if (h + 2 <= w) {
      if (!s) {
        if (characteristic_vector[h]) {
          return {
            new Position(i + 1, e)
          };
        }
 
        return {
          new Position(i, e + 1),
          new Position(i, e + 1, true),
          new Position(i + 1, e + 1),
          new Position(i + 2, e + 1)
        };
      }
 
      return {
        new Position(i + 1, e)
      };
    }
 
    if (h + 1 == w) {
      if (!s) {
        if (characteristic_vector[h]) {
          return {
            new Position(i + 1, e)
          };
        }
 
        return {
          new Position(i, e + 1),
          new Position(i, e + 1, true),
          new Position(i + 1, e + 1)
        };
      }
 
      return {
        new Position(i + 1, e)
      };
    }
 
    return {
      new Position(i, e + 1)
    };
  }
 
  if (h + 1 <= w) {
    if (!s) {
      if (characteristic_vector[h]) {
        return {
          new Position(i + 1, n)
        };
      }
 
      return {};
    }
 
    return {
      new Position(i + 1, e)
    };
  }
 
  return {};
}

References query(), and liblevenshtein::Position::term_index().

Here is the call graph for this function:

position_transition< Algorithm::STANDARD >() [1/2]

template<>

auto liblevenshtein::position_transition< Algorithm::STANDARD >	(	std::size_t	n,
		Position *	position,
		std::vector< bool > &	characteristic_vector,
		std::size_t	offset ) -> std::vector< Position * >

Returns the closure over possible next Positions that are reachable from the current Position by advancing the location in the dictionary by one.

This covers transitions within the standard Levenshtein distance, which includes the elementary operations of insertion, deletion, and substituion.

Parameters

n	Maximum edit distance to consider when matching spelling candidates.
position	Current Position within the Levenshtein automaton.
characteristic_vector	Moving window over matching characters of the query term.
offset	Where to begin examining the chracteristic_vector.

Returns

The closure over the next Positions reachable from the current Position by advancing the location in the dictionary by one.

Definition at line 17 of file position_transition.cpp.

                                               {
 
  std::size_t i = position->term_index();
  std::size_t e = position->num_errors();
  std::size_t h = i - offset;
  std::size_t w = characteristic_vector.size();
 
  if (e < n) {
    if (h + 2 <= w) {
      std::size_t a = (n - e < SIZE_MAX)
        ? n - e + 1
        : SIZE_MAX;
      std::size_t b = w - h;
      std::size_t k = (a < b) ? a : b;
      std::size_t j = index_of(characteristic_vector, k, h);
 
      if (j == 0) {
        return {
          new Position(i + 1, e)
        };
      }
 
      if (j != SIZE_MAX) {
        return {
          new Position(i, e + 1),
          new Position(i + 1, e + 1),
          new Position(i + j + 1, e + j)
        };
      }
 
      return {
        new Position(i, e + 1),
        new Position(i + 1, e + 1)
      };
    }
 
    if (h + 1 == w) {
      if (characteristic_vector[h]) {
        return {
          new Position(i + 1, e)
        };
      }
 
      return {
        new Position(i, e + 1),
        new Position(i + 1, e + 1)
      };
    }
 
    return {
      new Position(i, e + 1)
    };
  }
 
  if (e == n && h + 1 <= w && characteristic_vector[h]) {
    return {
      new Position(i + 1, n)
    };
  }
 
  return {};
}

References index_of(), and query().

Here is the call graph for this function:

position_transition< Algorithm::STANDARD >() [2/2]

template<>

auto liblevenshtein::position_transition< Algorithm::STANDARD >	(	std::size_t	n,
		Position *	position,
		std::vector< bool > &	characteristic_vector,
		std::size_t	offset ) -> std::vector< Position * >

Returns the closure over possible next Positions that are reachable from the current Position by advancing the location in the dictionary by one.

This covers transitions within the standard Levenshtein distance, which includes the elementary operations of insertion, deletion, and substituion.

Parameters

n	Maximum edit distance to consider when matching spelling candidates.
position	Current Position within the Levenshtein automaton.
characteristic_vector	Moving window over matching characters of the query term.
offset	Where to begin examining the chracteristic_vector.

Returns

The closure over the next Positions reachable from the current Position by advancing the location in the dictionary by one.

Definition at line 17 of file position_transition.cpp.

                                               {
 
  std::size_t i = position->term_index();
  std::size_t e = position->num_errors();
  std::size_t h = i - offset;
  std::size_t w = characteristic_vector.size();
 
  if (e < n) {
    if (h + 2 <= w) {
      std::size_t a = (n - e < SIZE_MAX)
        ? n - e + 1
        : SIZE_MAX;
      std::size_t b = w - h;
      std::size_t k = (a < b) ? a : b;
      std::size_t j = index_of(characteristic_vector, k, h);
 
      if (j == 0) {
        return {
          new Position(i + 1, e)
        };
      }
 
      if (j != SIZE_MAX) {
        return {
          new Position(i, e + 1),
          new Position(i + 1, e + 1),
          new Position(i + j + 1, e + j)
        };
      }
 
      return {
        new Position(i, e + 1),
        new Position(i + 1, e + 1)
      };
    }
 
    if (h + 1 == w) {
      if (characteristic_vector[h]) {
        return {
          new Position(i + 1, e)
        };
      }
 
      return {
        new Position(i, e + 1),
        new Position(i + 1, e + 1)
      };
    }
 
    return {
      new Position(i, e + 1)
    };
  }
 
  if (e == n && h + 1 <= w && characteristic_vector[h]) {
    return {
      new Position(i + 1, n)
    };
  }
 
  return {};
}

References index_of(), and query().

Here is the call graph for this function:

position_transition< Algorithm::TRANSPOSITION >() [1/2]

template<>

auto liblevenshtein::position_transition< Algorithm::TRANSPOSITION >	(	std::size_t	n,
		Position *	position,
		std::vector< bool > &	characteristic_vector,
		std::size_t	offset ) -> std::vector< Position * >

Returns the closure over possible next Positions that are reachable from the current Position by advancing the location in the dictionary by one.

This covers transitions within the standard Levenshtein distance extended with the elementary operation, transposition.

Parameters

n	Maximum edit distance to consider when matching spelling candidates.
position	Current Position within the Levenshtein automaton.
characteristic_vector	Moving window over matching characters of the query term.
offset	Where to begin examining the chracteristic_vector.

Returns

The closure over the next Positions reachable from the current Position by advancing the location in the dictionary by one.

Definition at line 84 of file position_transition.cpp.

                                               {
 
  std::size_t i = position->term_index();
  std::size_t e = position->num_errors();
  bool t = position->is_special();
  std::size_t h = i - offset;
  std::size_t w = characteristic_vector.size();
 
  if (e == 0 && 0 < n) {
    if (h + 2 <= w) {
      std::size_t a = (n - e < SIZE_MAX)
        ? n - e + 1
        : SIZE_MAX;
      std::size_t b = w - h;
      std::size_t k = (a < b) ? a : b;
      std::size_t j = index_of(characteristic_vector, k, h);
 
      switch (j) {
      case 0:
        return {
          new Position(i + 1, 0)
        };
      case 1:
        return {
          new Position(i, 1),
          new Position(i, 1, true),
          new Position(i + 1, 1),
          new Position(i + 2, 1)
        };
      case SIZE_MAX:
        return {
          new Position(i, 1),
          new Position(i + 1, 1)
        };
      default:
        return {
          new Position(i, 1),
          new Position(i + 1, 1),
          new Position(i + j + 1, j)
        };
      }
    }
 
    if (h + 1 == w) {
      if (characteristic_vector[h]) {
        return {
          new Position(i + 1, 0)
        };
      }
 
      return {
        new Position(i, 1),
        new Position(i + 1, 1)
      };
    }
 
    return {
      new Position(i, 1)
    };
  }
 
  if (1 <= e && e < n) {
    if (h + 2 <= w) {
      if (!t) {
        std::size_t a = (n - e < SIZE_MAX)
          ? n - e + 1
          : SIZE_MAX;
        std::size_t b = w - h;
        std::size_t k = (a < b) ? a : b;
        std::size_t j = index_of(characteristic_vector, k, h);
 
        switch (j) {
        case 0:
          return {
            new Position(i + 1, e)
          };
        case 1:
          return {
            new Position(i, e + 1),
            new Position(i, e + 1, true),
            new Position(i + 1, e + 1),
            new Position(i + 2, e + 1)
          };
        case SIZE_MAX:
          return {
            new Position(i, e + 1),
            new Position(i + 1, e + 1)
          };
        default:
          return {
            new Position(i, e + 1),
            new Position(i + 1, e + 1),
            new Position(i + j + 1, e + j)
          };
        }
      }
 
      if (characteristic_vector[h]) {
        return {
          new Position(i + 2, e)
        };
      }
 
      return {};
    }
 
    if (h + 1 == w) {
      if (characteristic_vector[h]) {
        return {
          new Position(i + 1, e)
        };
      }
 
      return {
        new Position(i, e + 1),
        new Position(i + 1, e + 1)
      };
    }
 
    return {
      new Position(i, e + 1)
    };
  }
 
  if (h + 1 <= w && !t) {
    if (characteristic_vector[h]) {
      return {
        new Position(i + 1, n)
      };
    }
 
    return {};
  }
 
  if (h + 2 <= w && t && characteristic_vector[h]) {
    return {
      new Position(i + 2, n)
    };
  }
 
  return {};
}

References index_of(), query(), and liblevenshtein::Position::term_index().

Here is the call graph for this function:

position_transition< Algorithm::TRANSPOSITION >() [2/2]

template<>

auto liblevenshtein::position_transition< Algorithm::TRANSPOSITION >	(	std::size_t	n,
		Position *	position,
		std::vector< bool > &	characteristic_vector,
		std::size_t	offset ) -> std::vector< Position * >

Returns the closure over possible next Positions that are reachable from the current Position by advancing the location in the dictionary by one.

This covers transitions within the standard Levenshtein distance extended with the elementary operation, transposition.

Parameters

n	Maximum edit distance to consider when matching spelling candidates.
position	Current Position within the Levenshtein automaton.
characteristic_vector	Moving window over matching characters of the query term.
offset	Where to begin examining the chracteristic_vector.

Returns

The closure over the next Positions reachable from the current Position by advancing the location in the dictionary by one.

Definition at line 84 of file position_transition.cpp.

                                               {
 
  std::size_t i = position->term_index();
  std::size_t e = position->num_errors();
  bool t = position->is_special();
  std::size_t h = i - offset;
  std::size_t w = characteristic_vector.size();
 
  if (e == 0 && 0 < n) {
    if (h + 2 <= w) {
      std::size_t a = (n - e < SIZE_MAX)
        ? n - e + 1
        : SIZE_MAX;
      std::size_t b = w - h;
      std::size_t k = (a < b) ? a : b;
      std::size_t j = index_of(characteristic_vector, k, h);
 
      switch (j) {
      case 0:
        return {
          new Position(i + 1, 0)
        };
      case 1:
        return {
          new Position(i, 1),
          new Position(i, 1, true),
          new Position(i + 1, 1),
          new Position(i + 2, 1)
        };
      case SIZE_MAX:
        return {
          new Position(i, 1),
          new Position(i + 1, 1)
        };
      default:
        return {
          new Position(i, 1),
          new Position(i + 1, 1),
          new Position(i + j + 1, j)
        };
      }
    }
 
    if (h + 1 == w) {
      if (characteristic_vector[h]) {
        return {
          new Position(i + 1, 0)
        };
      }
 
      return {
        new Position(i, 1),
        new Position(i + 1, 1)
      };
    }
 
    return {
      new Position(i, 1)
    };
  }
 
  if (1 <= e && e < n) {
    if (h + 2 <= w) {
      if (!t) {
        std::size_t a = (n - e < SIZE_MAX)
          ? n - e + 1
          : SIZE_MAX;
        std::size_t b = w - h;
        std::size_t k = (a < b) ? a : b;
        std::size_t j = index_of(characteristic_vector, k, h);
 
        switch (j) {
        case 0:
          return {
            new Position(i + 1, e)
          };
        case 1:
          return {
            new Position(i, e + 1),
            new Position(i, e + 1, true),
            new Position(i + 1, e + 1),
            new Position(i + 2, e + 1)
          };
        case SIZE_MAX:
          return {
            new Position(i, e + 1),
            new Position(i + 1, e + 1)
          };
        default:
          return {
            new Position(i, e + 1),
            new Position(i + 1, e + 1),
            new Position(i + j + 1, e + j)
          };
        }
      }
 
      if (characteristic_vector[h]) {
        return {
          new Position(i + 2, e)
        };
      }
 
      return {};
    }
 
    if (h + 1 == w) {
      if (characteristic_vector[h]) {
        return {
          new Position(i + 1, e)
        };
      }
 
      return {
        new Position(i, e + 1),
        new Position(i + 1, e + 1)
      };
    }
 
    return {
      new Position(i, e + 1)
    };
  }
 
  if (h + 1 <= w && !t) {
    if (characteristic_vector[h]) {
      return {
        new Position(i + 1, n)
      };
    }
 
    return {};
  }
 
  if (h + 2 <= w && t && characteristic_vector[h]) {
    return {
      new Position(i + 2, n)
    };
  }
 
  return {};
}

References index_of(), query(), and liblevenshtein::Position::term_index().

Here is the call graph for this function:

serialize_protobuf() [1/4]

auto liblevenshtein::serialize_protobuf	(	Dawg *	dawg,
		const char *	path ) -> bool

Serializes the given Dawg to protobuf at the given path.

Parameters

dawg	Dawg to serialize.
path	Path to the serialization file.

Returns

Whether the Dawg was successfully serialized to the given path.

Definition at line 29 of file serializer.cpp.

                                                              {
  std::fstream output(path, std::fstream::out | std::fstream::trunc |
                                std::fstream::binary);
  bool serialized = serialize_protobuf(dawg, output);
  output.close();
  return serialized;
}

References query(), and serialize_protobuf().

Here is the call graph for this function:

serialize_protobuf() [2/4]

auto liblevenshtein::serialize_protobuf	(	Dawg *	dawg,
		const fs::path &	path ) -> bool

Serializes the given Dawg to protobuf at the given path.

Parameters

dawg	Dawg to serialize.
path	Path to the serialization file.

Returns

Whether the Dawg was successfully serialized to the given path.

Definition at line 21 of file serializer.cpp.

                                                                {
  return serialize_protobuf(dawg, path.generic_string());
}

References query(), and serialize_protobuf().

Referenced by serialize_protobuf(), serialize_protobuf(), and serialize_protobuf().

Here is the call graph for this function:

Here is the caller graph for this function:

serialize_protobuf() [3/4]

auto liblevenshtein::serialize_protobuf	(	Dawg *	dawg,
		const std::string &	path ) -> bool

Serializes the given Dawg to protobuf at the given path.

Parameters

dawg	Dawg to serialize.
path	Path to the serialization file.

Returns

Whether the Dawg was successfully serialized to the given path.

Definition at line 25 of file serializer.cpp.

                                                                   {
  return serialize_protobuf(dawg, path.c_str());
}

References query(), and serialize_protobuf().

Here is the call graph for this function:

serialize_protobuf() [4/4]

auto liblevenshtein::serialize_protobuf	(	Dawg *	dawg,
		std::ostream &	output ) -> bool

Serializes the given Dawg to protobuf into the given output stream.

Parameters

dawg	Dawg to serialize.
output	Output stream to write the serialized protobuf.

Returns

Whether the Dawg was successfully serialized to the output stream.

Definition at line 37 of file serializer.cpp.

                                                                {
  llp::Dictionary *dict_proto = to_protobuf(dawg);
  bool serialized = dict_proto->SerializeToOstream(&output);
  delete dict_proto;
  return serialized;
}

References query(), and to_protobuf().

Here is the call graph for this function:

sorted_dawg() [1/4]

template<class IterType >

auto liblevenshtein::sorted_dawg	(	IterType	iter,
		IterType	end ) -> SortedDawg *

Factory function that initializes a new SortedDawg using the terms yielded from an iterator.

Parameters

iter	Iterator that yields lexicographically sorted terms.
end	Iterator representing the end of the terms.

Returns

A new SortedDawg containing all the terms from the iterator.

Definition at line 124 of file sorted_dawg.cpp.

                                                              {
  auto *dawg = new SortedDawg();
  dawg->init();
 
  while (iter != end) {
    const std::string &term = *iter;
    if (!dawg->add(term)) {
      delete dawg;
      return nullptr;
    }
    ++iter;
  }
 
  dawg->finish();
  dawg->clean_up();
  return dawg;
}

References query().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

sorted_dawg() [2/4]

template auto liblevenshtein::sorted_dawg	(	std::list< std::string >::iterator	iter,
		std::list< std::string >::iterator	end ) -> SortedDawg *

sorted_dawg() [3/4]

template auto liblevenshtein::sorted_dawg	(	std::set< std::string >::iterator	iter,
		std::set< std::string >::iterator	end ) -> SortedDawg *

sorted_dawg() [4/4]

template auto liblevenshtein::sorted_dawg	(	std::vector< std::string >::iterator	iter,
		std::vector< std::string >::iterator	end ) -> SortedDawg *

subsumes()

template<Algorithm Type>

auto liblevenshtein::subsumes	(	Position *	lhs,
		Position *	rhs,
		std::size_t	n ) -> bool

Returns whether Position lhs subsumes Position rhs, given the maximum edit distance n.

We say that lhs subsumes rhs if the set of spelling candidates reachable from rhs is a subset of the spelling candidates reachable from lhs. As such, if lhs subsumes rhs, then rhs is redundant and may be removed from the set of candidate Positions. In fact, it must be removed for the current set of algorithms to perform correctly.

Parameters

lhs	Position to compare against rhs.
rhs	Position to compare against lhs.
n	Maximum edit distance to consider when matching spelling candidates.

Returns

Whether lhs subsumes rhs, given the maximum edit distance n.

subsumes< Algorithm::MERGE_AND_SPLIT >() [1/2]

template<>

auto liblevenshtein::subsumes< Algorithm::MERGE_AND_SPLIT >	(	Position *	lhs,
		Position *	rhs,
		std::size_t	n ) -> bool

Returns whether lhs subsumes rhs according to the subsumption rules of standard Levenshtein distance extended with the elementary operations of merge and split.

Parameters

lhs	Position to compare against rhs.
rhs	Position to compare against lhs.
n	Maximum edit distance to consider when matching spelling candidates.

Returns

Whether lhs subsumes rhs, given the maximum edit distance n.

Definition at line 42 of file subsumes.cpp.

                                                               {
  std::size_t i = lhs->term_index();
  std::size_t e = lhs->num_errors();
  bool s = lhs->is_special();
  std::size_t j = rhs->term_index();
  std::size_t f = rhs->num_errors();
  bool t = lhs->is_special();
 
  if (s && !t) {
    return false;
  }
 
  return ((i < j) ? (j - i) : (i - j)) <= (f - e);
}

References query().

Here is the call graph for this function:

subsumes< Algorithm::MERGE_AND_SPLIT >() [2/2]

template<>

auto liblevenshtein::subsumes< Algorithm::MERGE_AND_SPLIT >	(	Position *	lhs,
		Position *	rhs,
		std::size_t	n ) -> bool

Returns whether lhs subsumes rhs according to the subsumption rules of standard Levenshtein distance extended with the elementary operations of merge and split.

Parameters

lhs	Position to compare against rhs.
rhs	Position to compare against lhs.
n	Maximum edit distance to consider when matching spelling candidates.

Returns

Whether lhs subsumes rhs, given the maximum edit distance n.

Definition at line 42 of file subsumes.cpp.

                                                               {
  std::size_t i = lhs->term_index();
  std::size_t e = lhs->num_errors();
  bool s = lhs->is_special();
  std::size_t j = rhs->term_index();
  std::size_t f = rhs->num_errors();
  bool t = lhs->is_special();
 
  if (s && !t) {
    return false;
  }
 
  return ((i < j) ? (j - i) : (i - j)) <= (f - e);
}

References query().

Here is the call graph for this function:

subsumes< Algorithm::STANDARD >() [1/2]

template<>

auto liblevenshtein::subsumes< Algorithm::STANDARD >	(	Position *	lhs,
		Position *	rhs,
		std::size_t	n ) -> bool

Returns whether lhs subsumes rhs according to the subsumption rules of standard Levenshtein distance, which consists of the elementary operations of insertion, deletion, and substitution.

Parameters

lhs	Position to compare against rhs.
rhs	Position to compare against lhs.
n	Maximum edit distance to consider when matching spelling candidates.

Returns

Whether lhs subsumes rhs, given the maximum edit distance n.

Definition at line 6 of file subsumes.cpp.

            {
  std::size_t i = lhs->term_index();
  std::size_t e = lhs->num_errors();
  std::size_t j = rhs->term_index();
  std::size_t f = rhs->num_errors();
  return ((i < j) ? (j - i) : (i - j)) <= (f - e);
}

References query().

Here is the call graph for this function:

subsumes< Algorithm::STANDARD >() [2/2]

template<>

auto liblevenshtein::subsumes< Algorithm::STANDARD >	(	Position *	lhs,
		Position *	rhs,
		std::size_t	n ) -> bool

Returns whether lhs subsumes rhs according to the subsumption rules of standard Levenshtein distance, which consists of the elementary operations of insertion, deletion, and substitution.

Parameters

lhs	Position to compare against rhs.
rhs	Position to compare against lhs.
n	Maximum edit distance to consider when matching spelling candidates.

Returns

Whether lhs subsumes rhs, given the maximum edit distance n.

Definition at line 6 of file subsumes.cpp.

            {
  std::size_t i = lhs->term_index();
  std::size_t e = lhs->num_errors();
  std::size_t j = rhs->term_index();
  std::size_t f = rhs->num_errors();
  return ((i < j) ? (j - i) : (i - j)) <= (f - e);
}

References query().

Here is the call graph for this function:

subsumes< Algorithm::TRANSPOSITION >() [1/2]

template<>

auto liblevenshtein::subsumes< Algorithm::TRANSPOSITION >	(	Position *	lhs,
		Position *	rhs,
		std::size_t	n ) -> bool

Returns whether lhs subsumes rhs according to the subsumption rules of standard Levenshtein distance extended with the elementary operation of transposition.

Parameters

lhs	Position to compare against rhs.
rhs	Position to compare against lhs.
n	Maximum edit distance to consider when matching spelling candidates.

Returns

Whether lhs subsumes rhs, given the maximum edit distance n.

Definition at line 16 of file subsumes.cpp.

                                                             {
  std::size_t i = lhs->term_index();
  std::size_t e = lhs->num_errors();
  bool s = lhs->is_special();
 
  std::size_t j = rhs->term_index();
  std::size_t f = rhs->num_errors();
  bool t = lhs->is_special();
 
  if (s) {
    if (t) {
      return (i == j);
    }
 
    return (f == n) && (i == j);
  }
 
  if (t) {
    return ((j < i) ? (i - j - 1) : (j - i + 1)) <= (f - e);
  }
 
  return ((i < j) ? (j - i) : (i - j)) <= (f - e);
}

References query().

Here is the call graph for this function:

subsumes< Algorithm::TRANSPOSITION >() [2/2]

template<>

auto liblevenshtein::subsumes< Algorithm::TRANSPOSITION >	(	Position *	lhs,
		Position *	rhs,
		std::size_t	n ) -> bool

Returns whether lhs subsumes rhs according to the subsumption rules of standard Levenshtein distance extended with the elementary operation of transposition.

Parameters

lhs	Position to compare against rhs.
rhs	Position to compare against lhs.
n	Maximum edit distance to consider when matching spelling candidates.

Returns

Whether lhs subsumes rhs, given the maximum edit distance n.

Definition at line 16 of file subsumes.cpp.

                                                             {
  std::size_t i = lhs->term_index();
  std::size_t e = lhs->num_errors();
  bool s = lhs->is_special();
 
  std::size_t j = rhs->term_index();
  std::size_t f = rhs->num_errors();
  bool t = lhs->is_special();
 
  if (s) {
    if (t) {
      return (i == j);
    }
 
    return (f == n) && (i == j);
  }
 
  if (t) {
    return ((j < i) ? (i - j - 1) : (j - i + 1)) <= (f - e);
  }
 
  return ((i < j) ? (j - i) : (i - j)) <= (f - e);
}

References query().

Here is the call graph for this function:

to_protobuf()

auto liblevenshtein::to_protobuf

(

Dawg *

dawg

)

-> llp::Dictionary *

Serializes a Dawg to its protobuf equivalent.

Parameters

dawg	Dawg to serialize.

Returns

A pointer to the serialized Dawg.

Definition at line 95 of file serializer.cpp.

                                                {
  auto *dict_proto = new llp::Dictionary();
  DawgNode *root = dawg->root();
 
  std::set<uint64_t> node_ids;
  std::set<uint64_t> final_node_ids;
  collect_nodes(root, node_ids, final_node_ids);
  for (const uint64_t &node_id : node_ids) {
    dict_proto->add_node_id(node_id);
  }
  for (const uint64_t &final_node_id : final_node_ids) {
    dict_proto->add_final_node_id(final_node_id);
  }
 
  std::map<std::pair<uint64_t, char>, uint64_t> edges;
  collect_edges(root, edges);
  for (const auto &edge : edges) {
    uint64_t source_id = edge.first.first;
    char label = edge.first.second;
    uint64_t target_id = edge.second;
    llp::Dictionary_Edge *edge_proto = dict_proto->add_edge();
    edge_proto->set_source_id(source_id);
    edge_proto->set_label(label);
    edge_proto->set_target_id(target_id);
  }
 
  auto root_id = reinterpret_cast<uint64_t>(root);
  dict_proto->set_root_id(root_id);
  dict_proto->set_size(dawg->size());
 
  return dict_proto;
}

References collect_edges(), collect_nodes(), and query().

Referenced by serialize_protobuf().

Here is the call graph for this function:

Here is the caller graph for this function: