What successive munches over ONE subject have learnt, so that tokenizing the whole subject costs O(states × length) instead of O(length²) (Reps, "Maximal-munch tokenization in linear time", 1998). More...

#include <dfa.hpp>

Public Member Functions
	dfa_munch_memo (std::size_t subject_size)
	An empty memo for one subject.

std::size_t	transitions () const noexcept
	DFA transitions taken by every munch so far – the work the bound is stated in.

bool	armed () const noexcept
	Whether a walk over this subject has run more than short_stretch steps past its last accept, so later walks consult the memo; until then it holds nothing and costs nothing.

Static Public Attributes
static constexpr std::size_t	short_stretch {32}
	The longest stretch after a walk's last accept that is left unmarked. A later walk reaching one of its pairs dies within that many steps on its own, so the bound stays linear (O(length x (states + short_stretch))). The first longer stretch also arms the memo: until then no walk consults it, so an ordinary tokenization pays nothing for it.

Private Attributes
std::size_t	size_
	The subject's length.

std::vector< std::vector< bool > >	dead_after_
	[state][position]: no accept follows.

std::vector< std::uint8_t >	marked_
	[state]: dead_after_[state] holds a mark.

bool	marks_from_open_walks_ {}
	A mark came from a walk alive at the subject's end: dead for this subject only.

std::size_t	transitions_ {0}
	See transitions().

const void *	owner_ {nullptr}
	The dfa's tables this memo describes.

Friends
class	dfa

Detailed Description

What successive munches over ONE subject have learnt, so that tokenizing the whole subject costs O(states × length) instead of O(length²) (Reps, "Maximal-munch tokenization in linear time", 1998).

A munch walks the DFA until it dies or the subject ends, then answers its last accepting position. Every (state, position) visited after that position leads to no accept, so a later munch reaching the same pair can stop there with the answer it holds. Without this, a rule like a*b beside a rescans the rest of aaa… from every position.

Bound to one dfa and one subject: pass it to dfa::match(std::string_view, std::size_t, dfa_munch_memo&) const with the same pair every time. Memory is one bit per remembered state per subject position, allocated on a state's first mark; a walk replays its dead stretch to mark it rather than holding it.

Constructor & Destructor Documentation

◆ dfa_munch_memo()

real::dfa_munch_memo::dfa_munch_memo ( std::size_t subject_size )

inlineexplicit

An empty memo for one subject.

Parameters

[in] subject_size The subject's length in bytes.

Member Function Documentation

◆ armed()

bool real::dfa_munch_memo::armed ( ) const

inlinenoexcept

Whether a walk over this subject has run more than short_stretch steps past its last accept, so later walks consult the memo; until then it holds nothing and costs nothing.

Returns: True once armed.

◆ transitions()

std::size_t real::dfa_munch_memo::transitions ( ) const

inlinenoexcept

DFA transitions taken by every munch so far – the work the bound is stated in.

Returns: The count, summed over every call that used this memo.

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

include/real/dfa.hpp

Public Member Functions

Static Public Attributes