levenshtein_automatont Struct Reference

Simple automaton that can detect whether a string can be transformed into another with a limited number of deletions, insertions or substitutions. More...

#include <edit_distance.h>

Collaboration diagram for levenshtein_automatont:

Public Member Functions
	levenshtein_automatont (const std::string &string, std::size_t allowed_errors=2)
bool	matches (const std::string &string) const
std::optional< std::size_t >	get_edit_distance (const std::string &string) const
void	dump_automaton_dot_to (std::ostream &out)

Private Types
using	state_labelt = nfat< char >::state_labelt

Private Attributes
nfat< char >	nfa
std::vector< state_labelt >	final_states

Detailed Description

Simple automaton that can detect whether a string can be transformed into another with a limited number of deletions, insertions or substitutions.

Not a very fast implementation, but should be good enough for small strings.

Definition at line 24 of file edit_distance.h.

Member Typedef Documentation

state_labelt

using levenshtein_automatont::state_labelt = nfat<char>::state_labelt

private

Definition at line 28 of file edit_distance.h.

Constructor & Destructor Documentation

levenshtein_automatont()

levenshtein_automatont::levenshtein_automatont	(	const std::string &	string,
		std::size_t	allowed_errors = 2
	)

Definition at line 8 of file edit_distance.cpp.

Member Function Documentation

dump_automaton_dot_to()

void levenshtein_automatont::dump_automaton_dot_to ( std::ostream &  out )

inline

Definition at line 39 of file edit_distance.h.

get_edit_distance()

std::optional< std::size_t > levenshtein_automatont::get_edit_distance

(

const std::string &

string

)

const

Definition at line 58 of file edit_distance.cpp.

matches()

bool levenshtein_automatont::matches

(

const std::string &

string

)

const

Definition at line 52 of file edit_distance.cpp.

Member Data Documentation

final_states

std::vector<state_labelt> levenshtein_automatont::final_states

private

Definition at line 29 of file edit_distance.h.

nfa

nfat<char> levenshtein_automatont::nfa

private

Definition at line 27 of file edit_distance.h.

---

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

• /home/runner/work/cbmc/cbmc/src/util/edit_distance.h
• /home/runner/work/cbmc/cbmc/src/util/edit_distance.cpp