liblevenshtein::SortedDawg Class Reference

A specific type of Dawg that is constructed over lexicographically sorted terms. More...

#include <sorted_dawg.h>

Inheritance diagram for liblevenshtein::SortedDawg:

Collaboration diagram for liblevenshtein::SortedDawg:

Public Member Functions
	~SortedDawg () override
	Cleans up any residual intermediate members used to construct the Dawg.
auto	add (const std::string &term) -> bool override
	Adds a new term to this dictionary.
auto	remove (const std::string &term) -> bool override
	Removes a term from this dictionary.
void	init ()
	Prepares this dictionary for initialization.
void	clean_up ()
	Cleans up any intermediate members used to initialize this Dawg.
void	finish ()
	Specifies the dictionary has been fully initialized.
void	minimize (std::size_t lower_bound)
	Minimizes the suffixes of the unchecked paths until there are no more than lower_bound unchecked transitions.
auto	minimized_node (DawgNode *key) const -> DawgNode *
	Returns a DawgNode whose following suffix is equivalent to the following suffix of the given DawgNode, or nullptr if none exist.
	Dawg (DawgNode *root, std::size_t size)
	Constructs a new DAWG with the given root node and number of dictionary terms (size).
	Dawg ()
	Constructs an empty DAWG with a default root node (there are no outgoing edges or reachable terms from the root, not even the empty string).
auto	contains (const std::string &term) const -> bool
	Determines whether the given term is contained within this dictionary.
auto	root () const -> DawgNode *
	Returns a pointer to the root node of this dictionary from which all its terms may be determined.
auto	size () const -> size_t
	Returns the number of terms in this dictionary.
auto	begin () const -> DawgIterator
	Returns an iterator pointing to the first term in this dictionary, from which all terms may be iterated over.
auto	end () const -> DawgIterator
	Returns an iterator representing the boundary following the final term in this dictionary.
auto	operator== (const Dawg &other) const -> bool
	Determines whether another DAWG is equivalent to this one.

Protected Member Functions
auto	all_nodes () const -> std::unordered_set< DawgNode * >
	Returns a set of all nodes reachable from the root, including the root.

Protected Attributes
DawgNode *	_root
	Root node of this DAWG from which all its terms may be reached.
std::size_t	_size
	Number of terms reachable from the root node.

Private Attributes
std::stack< Transition > *	unchecked_transitions = nullptr
	Transitions whose redundancies have not been checked.
std::unordered_map< DawgNode, DawgNode * > *	minimized_nodes = nullptr
	Mapping of suffixes to DawgNodes that have been minimized.
std::unordered_set< DawgNode * > *	floating_nodes = nullptr
	Nodes that have not been added to this Dawg.
std::string	_prev_term
	Previous term inserted into this Dawg.

Detailed Description

A specific type of Dawg that is constructed over lexicographically sorted terms.

The precondition that the terms are sorted, lexigraphically, in ascending order is a requirement by the algorithm used to construct this type of Dawg.

Definition at line 20 of file sorted_dawg.h.

Constructor & Destructor Documentation

~SortedDawg()

liblevenshtein::SortedDawg::~SortedDawg ( )

override

Cleans up any residual intermediate members used to construct the Dawg.

The super destructor is subsequently called to clean up the rest of its nodes.

Definition at line 11 of file sorted_dawg.cpp.

                        {
  clean_up();
}

References clean_up().

Here is the call graph for this function:

Member Function Documentation

add()

auto liblevenshtein::SortedDawg::add ( const std::string & term ) -> bool

overridevirtual

Adds a new term to this dictionary.

The term must be lexicographically larger than the previously added term.

Parameters

term	A term to add to this dictionary.

Returns

Wether the term was successfully added to this dictionary.

Implements liblevenshtein::Dawg.

Definition at line 15 of file sorted_dawg.cpp.

                                                  {
  if (term < _prev_term) {
    return false;
  }
 
  if (term.empty()) {
    _root->is_final(true);
    _prev_term = term;
    _size += 1;
    return true;
  }
 
  std::size_t upper_bound = std::min(term.length(), _prev_term.length());
 
  // Find the length of the longest common prefix between term and prev_term
  std::size_t i = 0;
  while (i < upper_bound && term[i] == _prev_term[i]) {
    i += 1;
  }
 
  // Check the unchecked nodes for redundancy from the last one down to
  // the common prefix size. Then, truncate the list at that point.
  minimize(i);
 
  // Add the suffix starting from the correct node min-way through the graph
  DawgNode *source = unchecked_transitions->empty()
    ? _root
    : unchecked_transitions->top().target();
 
  for (std::size_t k = term.length(); i < k; i += 1) {
    auto *target = new DawgNode();
    floating_nodes->insert(target);
    unchecked_transitions->emplace(term[i], source, target);
    source = target;
  }
 
  source->is_final(true);
  _prev_term = term;
  _size += 1;
  return true;
}

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

Here is the call graph for this function:

all_nodes()

auto liblevenshtein::Dawg::all_nodes ( ) const -> std::unordered_set<DawgNode *>

protectedinherited

Returns a set of all nodes reachable from the root, including the root.

Returns

The closure of nodes reachable from the root, including the root.

Definition at line 28 of file dawg.cpp.

                                                           {
  std::unordered_set<DawgNode *> nodes;
  std::queue<DawgNode *> pending;
  pending.push(_root);
  while (!pending.empty()) {
    DawgNode *node = pending.front();
    pending.pop();
    nodes.insert(node);
    node->for_each_edge([&](char label, DawgNode *target) {
      pending.push(target);
    });
  }
  return nodes;
}

References liblevenshtein::Dawg::_root, and query().

Referenced by clean_up(), and liblevenshtein::Dawg::~Dawg().

Here is the call graph for this function:

Here is the caller graph for this function:

begin()

auto liblevenshtein::Dawg::begin ( ) const -> DawgIterator

inherited

Returns an iterator pointing to the first term in this dictionary, from which all terms may be iterated over.

Returns

An iterator pointing to the first term in this dictionary.

Definition at line 59 of file dawg.cpp.

                                       {
  return {_root};
}

References liblevenshtein::Dawg::_root.

clean_up()

void liblevenshtein::SortedDawg::clean_up

(

)

Cleans up any intermediate members used to initialize this Dawg.

Definition at line 98 of file sorted_dawg.cpp.

                          {
  if (unchecked_transitions != nullptr) {
    delete unchecked_transitions;
    unchecked_transitions = nullptr;
  }
 
  if (minimized_nodes != nullptr) {
    delete minimized_nodes;
    minimized_nodes = nullptr;
  }
 
  if (floating_nodes != nullptr) {
    for (DawgNode *node : all_nodes()) {
      floating_nodes->erase(node);
    }
 
    for (DawgNode *node : *floating_nodes) {
      delete node;
    }
 
    delete floating_nodes;
    floating_nodes = nullptr;
  }
}

References liblevenshtein::Dawg::all_nodes(), floating_nodes, minimized_nodes, and unchecked_transitions.

Referenced by ~SortedDawg().

Here is the call graph for this function:

Here is the caller graph for this function:

contains()

auto liblevenshtein::Dawg::contains ( const std::string & term ) const -> bool

inherited

Determines whether the given term is contained within this dictionary.

Parameters

term	Query term whose membership in this dictionary must be determined.

Returns

Whether the term is contained within this dictionary.

Definition at line 43 of file dawg.cpp.

                                                       {
  DawgNode* node = _root;
  for (int i = 0; i < term.length() && node != nullptr; i += 1) {
    node = node->transition(term[i]);
  }
  return node != nullptr && node->is_final();
}

References liblevenshtein::DawgNode::is_final(), query(), and liblevenshtein::DawgNode::transition().

Referenced by liblevenshtein::from_protobuf().

Here is the call graph for this function:

Here is the caller graph for this function:

Dawg() [1/2]

liblevenshtein::Dawg::Dawg

(

)

Constructs an empty DAWG with a default root node (there are no outgoing edges or reachable terms from the root, not even the empty string).

Definition at line 41 of file dawg.cpp.

  : _root(new DawgNode()),
    _size(0)
{}

Dawg() [2/2]

liblevenshtein::Dawg::Dawg	(	DawgNode *	root,
		std::size_t	size )

Constructs a new DAWG with the given root node and number of dictionary terms (size).

The number of terms reachable by combining the subsequent outgoing edges from the root must be equal to the size.

Parameters

root	Node from which all dictionary terms may be reached by subsequently traversing its outgoing edges.
size	Number of terms in the dictionary.

Definition at line 35 of file dawg.cpp.

  : _root(root),
    _size(size)
{}

References query().

Here is the call graph for this function:

end()

auto liblevenshtein::Dawg::end ( ) const -> DawgIterator

inherited

Returns an iterator representing the boundary following the final term in this dictionary.

The value of the iterator is not a term, but represent a boundary that must not be crossed.

Returns

An iterator pointing to the boundary following the final term in this dictionary.

Definition at line 63 of file dawg.cpp.

                                     {
  return {_size};
}

References liblevenshtein::Dawg::_size.

finish()

void liblevenshtein::SortedDawg::finish

(

)

Specifies the dictionary has been fully initialized.

This is only called during initialization.

Definition at line 57 of file sorted_dawg.cpp.

                        {
  minimize(0);
}

References minimize().

Here is the call graph for this function:

init()

void liblevenshtein::SortedDawg::init

(

)

Prepares this dictionary for initialization.

This function is only called during initialization.

Definition at line 92 of file sorted_dawg.cpp.

                      {
  unchecked_transitions = new std::stack<Transition>();
  minimized_nodes = new std::unordered_map<DawgNode, DawgNode *>();
  floating_nodes = new std::unordered_set<DawgNode *>();
}

References floating_nodes, minimized_nodes, and unchecked_transitions.

minimize()

void liblevenshtein::SortedDawg::minimize

(

std::size_t

lower_bound

)

Minimizes the suffixes of the unchecked paths until there are no more than lower_bound unchecked transitions.

This is only called during initialization.

Parameters

lower_bound

Desired size of remaining unchecked transitions once the other have been minimized.

Definition at line 69 of file sorted_dawg.cpp.

                                               {
  // proceed from the leaf up to a certain point
  for (std::size_t j = unchecked_transitions->size(); j > lower_bound; j -= 1) {
    Transition transition = unchecked_transitions->top();
    unchecked_transitions->pop();
    char label = transition.label();
    DawgNode* source = transition.source();
    DawgNode* target = transition.target();
    DawgNode* existing = minimized_node(target);
    if (existing != nullptr) {
      source->add_edge(label, existing);
    }
    else {
      source->add_edge(label, target);
      (*minimized_nodes)[*target] = target;
    }
  }
}

References liblevenshtein::DawgNode::add_edge(), liblevenshtein::Transition::label(), minimized_node(), query(), liblevenshtein::Transition::source(), liblevenshtein::Transition::target(), and unchecked_transitions.

Referenced by finish().

Here is the call graph for this function:

Here is the caller graph for this function:

minimized_node()

auto liblevenshtein::SortedDawg::minimized_node

(

DawgNode *

key

)

const -> DawgNode *

Returns a DawgNode whose following suffix is equivalent to the following suffix of the given DawgNode, or nullptr if none exist.

This is used to determine whether the given DawgNode is redundant and may be discarded.

Parameters

key	DawgNode whose redundancy must be determined.

Returns

Either an existing DawgNode having an equivalent suffix to the key or nullptr if the key is thus far unique.

Definition at line 61 of file sorted_dawg.cpp.

                                                                 {
  auto iter = minimized_nodes->find(*key);
  if (iter != minimized_nodes->end()) {
    return iter->second;
  }
  return nullptr;
}

References query().

Referenced by minimize().

Here is the call graph for this function:

Here is the caller graph for this function:

operator==()

auto liblevenshtein::Dawg::operator== ( const Dawg & other ) const -> bool

inherited

Determines whether another DAWG is equivalent to this one.

Parameters

other

Dictionary (DAWG) to compare to this one.

Returns

Whether the other dictionary is equivalent to this one.

Definition at line 72 of file dawg.cpp.

                                                     {
  return size() == other.size() && *root() == *other.root();
}

References query().

Here is the call graph for this function:

remove()

auto liblevenshtein::SortedDawg::remove ( const std::string & term ) -> bool

overridevirtual

Removes a term from this dictionary.

Currently, this is just a placeholder and performs no action.

Parameters

The	term to remove from this dictionary.

Returns

Whether the term was removed from this dictionary.

Implements liblevenshtein::Dawg.

Definition at line 88 of file sorted_dawg.cpp.

                                                     {
  return false;
}

root()

auto liblevenshtein::Dawg::root ( ) const -> DawgNode *

inherited

Returns a pointer to the root node of this dictionary from which all its terms may be determined.

Returns

A pointer to the root node of this dictionary.

Definition at line 51 of file dawg.cpp.

                                    {
  return _root;
}

References liblevenshtein::Dawg::_root.

Referenced by query().

Here is the caller graph for this function:

size()

auto liblevenshtein::Dawg::size ( ) const -> size_t

inherited

Returns the number of terms in this dictionary.

Returns

The size of this dictionary.

Definition at line 55 of file dawg.cpp.

                                   {
  return _size;
}

References liblevenshtein::Dawg::_size.

Member Data Documentation

_prev_term

std::string liblevenshtein::SortedDawg::_prev_term

private

Previous term inserted into this Dawg.

Definition at line 98 of file sorted_dawg.h.

_root

DawgNode* liblevenshtein::Dawg::_root

protectedinherited

Root node of this DAWG from which all its terms may be reached.

Definition at line 126 of file dawg.h.

Referenced by liblevenshtein::Dawg::all_nodes(), liblevenshtein::Dawg::begin(), and liblevenshtein::Dawg::root().

_size

std::size_t liblevenshtein::Dawg::_size

protectedinherited

Number of terms reachable from the root node.

Definition at line 129 of file dawg.h.

Referenced by liblevenshtein::Dawg::end(), and liblevenshtein::Dawg::size().

floating_nodes

std::unordered_set<DawgNode *>* liblevenshtein::SortedDawg::floating_nodes = nullptr

private

Nodes that have not been added to this Dawg.

Definition at line 95 of file sorted_dawg.h.

Referenced by clean_up(), and init().

minimized_nodes

std::unordered_map<DawgNode, DawgNode *>* liblevenshtein::SortedDawg::minimized_nodes = nullptr

private

Mapping of suffixes to DawgNodes that have been minimized.

Definition at line 92 of file sorted_dawg.h.

Referenced by clean_up(), and init().

unchecked_transitions

std::stack<Transition>* liblevenshtein::SortedDawg::unchecked_transitions = nullptr

private

Transitions whose redundancies have not been checked.

Definition at line 89 of file sorted_dawg.h.

Referenced by clean_up(), init(), and minimize().

---

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

• src/liblevenshtein/collection/sorted_dawg.h
• src/liblevenshtein/collection/sorted_dawg.cpp