liblevenshtein-cpp/sorted__dawg_8h_source.html

#ifndef LIBLEVENSHTEIN_COLLECTION_SORTED_DAWG_H

#define LIBLEVENSHTEIN_COLLECTION_SORTED_DAWG_H


#include <stack>

#include <unordered_map>

#include <unordered_set>


#include "liblevenshtein/collection/dawg.h"

#include "liblevenshtein/collection/dawg_node.h"

#include "liblevenshtein/collection/transition.h"


namespace liblevenshtein {


class SortedDawg : public Dawg {

public:

  using Dawg::Dawg;


  ~SortedDawg() override;


  auto add(const std::string &term) -> bool override;


  auto remove(const std::string &term) -> bool override;


  void init();


  void clean_up();


  void finish();


  void minimize(std::size_t lower_bound);


  auto minimized_node(DawgNode *key) const -> DawgNode *;


private:


  std::stack<Transition> *unchecked_transitions = nullptr;


  std::unordered_map<DawgNode, DawgNode *> *minimized_nodes = nullptr;


  std::unordered_set<DawgNode *> *floating_nodes = nullptr;


  std::string _prev_term;

};


template <class IterType>

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


} // namespace liblevenshtein


#endif // LIBLEVENSHTEIN_COLLECTION_SORTED_DAWG_H

liblevenshtein::DawgNode
Represents a position within one or more terms of a DAWG dictionary.
Definition dawg_node.h:20

liblevenshtein::Dawg
A Directed Acyclic Word Graph (DAWG) maps sequences of characters to form words; the collection of wo...
Definition dawg.h:23

liblevenshtein::Dawg::Dawg
Dawg()
Constructs an empty DAWG with a default root node (there are no outgoing edges or reachable terms fro...
Definition dawg.cpp:17

liblevenshtein::SortedDawg
A specific type of Dawg that is constructed over lexicographically sorted terms.
Definition sorted_dawg.h:20

liblevenshtein::SortedDawg::floating_nodes
std::unordered_set< DawgNode * > * floating_nodes
Nodes that have not been added to this Dawg.
Definition sorted_dawg.h:95

liblevenshtein::SortedDawg::~SortedDawg
~SortedDawg() override
Cleans up any residual intermediate members used to construct the Dawg.
Definition sorted_dawg.cpp:11

liblevenshtein::SortedDawg::add
auto add(const std::string &term) -> bool override
Adds a new term to this dictionary.
Definition sorted_dawg.cpp:15

liblevenshtein::SortedDawg::minimized_node
auto minimized_node(DawgNode *key) const -> DawgNode *
Returns a DawgNode whose following suffix is equivalent to the following suffix of the given DawgNode...
Definition sorted_dawg.cpp:61

liblevenshtein::SortedDawg::minimized_nodes
std::unordered_map< DawgNode, DawgNode * > * minimized_nodes
Mapping of suffixes to DawgNodes that have been minimized.
Definition sorted_dawg.h:92

liblevenshtein::SortedDawg::remove
auto remove(const std::string &term) -> bool override
Removes a term from this dictionary.
Definition sorted_dawg.cpp:88

liblevenshtein::SortedDawg::_prev_term
std::string _prev_term
Previous term inserted into this Dawg.
Definition sorted_dawg.h:98

liblevenshtein::SortedDawg::minimize
void minimize(std::size_t lower_bound)
Minimizes the suffixes of the unchecked paths until there are no more than lower_bound unchecked tran...
Definition sorted_dawg.cpp:69

liblevenshtein::SortedDawg::init
void init()
Prepares this dictionary for initialization.
Definition sorted_dawg.cpp:92

liblevenshtein::SortedDawg::finish
void finish()
Specifies the dictionary has been fully initialized.
Definition sorted_dawg.cpp:57

liblevenshtein::SortedDawg::clean_up
void clean_up()
Cleans up any intermediate members used to initialize this Dawg.
Definition sorted_dawg.cpp:98

liblevenshtein::SortedDawg::unchecked_transitions
std::stack< Transition > * unchecked_transitions
Transitions whose redundancies have not been checked.
Definition sorted_dawg.h:89

dawg.h

dawg_node.h

query
void query(ll::Dawg *dawg, const std::string &query_term, std::size_t max_distance)
Definition main.cpp:25

liblevenshtein
Various utilities regarding Levenshtein transducers.
Definition namespaces.dox:9

liblevenshtein::sorted_dawg
auto sorted_dawg(IterType iter, IterType end) -> SortedDawg *
Factory function that initializes a new SortedDawg using the terms yielded from an iterator.
Definition sorted_dawg.cpp:124

transition.h