Modulealfred-margaret-2.1.1.1Haskell2010

Data.Text.BoyerMooreCI.Automaton

An efficient implementation of the Boyer-Moore string search algorithm. http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140 https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm

This is case insensitive variant of the algorithm which, unlike the case sensitive variant, has to be aware of the unicode code points that the bytes represent.

4 types
5 values

Packagealfred-margaret-2.1.1.1
Exports9
LanguageHaskell2010
LicenceBSD-3-Clause
SourceAutomaton.hs

datadata Automaton

A Boyer-Moore automaton is based on lookup-tables that allow skipping through the haystack. This allows for sub-linear matching in some cases, as we do not have to look at every input character.

NOTE: Unlike the AcMachine, a Boyer-Moore automaton only returns non-overlapping matches. This means that a Boyer-Moore automaton is not a 100% drop-in replacement for Aho-Corasick.

Returning overlapping matches would degrade the performance to O(nm) in pathological cases like finding aaaa in aaaaa....aaaaaa as for each match it would scan back the whole m characters of the pattern.

Instances8Eq, Show, Generic, NFData, Hashable, FromJSON, …

Eq AutomatonDefined in alfred-margaret-2.1.1.1 · Data.Text.BoyerMooreCI.Automaton
Show AutomatonDefined in alfred-margaret-2.1.1.1 · Data.Text.BoyerMooreCI.Automaton
Generic AutomatonDefined in alfred-margaret-2.1.1.1 · Data.Text.BoyerMooreCI.Automaton
NFData AutomatonDefined in alfred-margaret-2.1.1.1 · Data.Text.BoyerMooreCI.Automaton
Hashable AutomatonDefined in alfred-margaret-2.1.1.1 · Data.Text.BoyerMooreCI.Automaton
FromJSON AutomatonDefined in alfred-margaret-2.1.1.1 · Data.Text.BoyerMooreCI.Automaton
ToJSON AutomatonDefined in alfred-margaret-2.1.1.1 · Data.Text.BoyerMooreCI.Automaton
type Rep Automaton = D1 ('MetaData "Automaton" "Data.Text.BoyerMooreCI.Automaton" "alfred-margaret-2.1.1.1-LmqCjvAcVEl7fSX12XT7qq" 'False) (C1 ('MetaCons "Automaton" 'PrefixI 'True) ((S1 ('MetaSel ('Just "automatonPattern") 'NoSourceUnpackedness 'SourceStrict 'DecidedUnpack) (Rec0 (PrimArray CodePoint)) :*: S1 ('MetaSel ('Just "automatonPatternHash") 'NoSourceUnpackedness 'SourceStrict 'DecidedUnpack) (Rec0 Int)) :*: (S1 ('MetaSel ('Just "automatonSuffixTable") 'NoSourceUnpackedness 'SourceStrict 'DecidedUnpack) (Rec0 SuffixTable) :*: (S1 ('MetaSel ('Just "automatonBadCharLookup") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 BadCharLookup) :*: S1 ('MetaSel ('Just "automatonMinPatternSkip") 'NoSourceUnpackedness 'SourceStrict 'DecidedUnpack) (Rec0 CodeUnitIndex)))))Defined in alfred-margaret-2.1.1.1 · Data.Text.BoyerMooreCI.Automaton

datadata CaseSensitivity

CaseSensitive IgnoreCase

Instances8Eq, Show, Generic, NFData, Hashable, FromJSON, …

Eq CaseSensitivityDefined in alfred-margaret-2.1.1.1 · Data.Text.CaseSensitivity
Show CaseSensitivityDefined in alfred-margaret-2.1.1.1 · Data.Text.CaseSensitivity
Generic CaseSensitivityDefined in alfred-margaret-2.1.1.1 · Data.Text.CaseSensitivity
NFData CaseSensitivityDefined in alfred-margaret-2.1.1.1 · Data.Text.CaseSensitivity
Hashable CaseSensitivityDefined in alfred-margaret-2.1.1.1 · Data.Text.CaseSensitivity
FromJSON CaseSensitivityDefined in alfred-margaret-2.1.1.1 · Data.Text.CaseSensitivity
ToJSON CaseSensitivityDefined in alfred-margaret-2.1.1.1 · Data.Text.CaseSensitivity
type Rep CaseSensitivity = D1 ('MetaData "CaseSensitivity" "Data.Text.CaseSensitivity" "alfred-margaret-2.1.1.1-LmqCjvAcVEl7fSX12XT7qq" 'False) (C1 ('MetaCons "CaseSensitive" 'PrefixI 'False) U1 :+: C1 ('MetaCons "IgnoreCase" 'PrefixI 'False) U1)Defined in alfred-margaret-2.1.1.1 · Data.Text.CaseSensitivity

newtypenewtype CodeUnitIndex

An index into the raw UTF-8 data of a Text. This is not the code point index as conventionally accepted by Text, so we wrap it to avoid confusing the two. Incorrect index manipulation can lead to surrogate pairs being sliced, so manipulate indices with care. This type is also used for lengths.

Constructors

CodeUnitIndex
- codeUnitIndex :: Int

Instances12Bounded, Eq, Num, Ord, Show, Generic, …

Bounded CodeUnitIndexDefined in alfred-margaret-2.1.1.1 · Data.Text.Utf8
Eq CodeUnitIndexDefined in alfred-margaret-2.1.1.1 · Data.Text.Utf8
Num CodeUnitIndexDefined in alfred-margaret-2.1.1.1 · Data.Text.Utf8
Ord CodeUnitIndexDefined in alfred-margaret-2.1.1.1 · Data.Text.Utf8
Show CodeUnitIndexDefined in alfred-margaret-2.1.1.1 · Data.Text.Utf8
Generic CodeUnitIndexDefined in alfred-margaret-2.1.1.1 · Data.Text.Utf8
NFData CodeUnitIndexDefined in alfred-margaret-2.1.1.1 · Data.Text.Utf8
Hashable CodeUnitIndexDefined in alfred-margaret-2.1.1.1 · Data.Text.Utf8
Prim CodeUnitIndexDefined in alfred-margaret-2.1.1.1 · Data.Text.Utf8
FromJSON CodeUnitIndexDefined in alfred-margaret-2.1.1.1 · Data.Text.Utf8
ToJSON CodeUnitIndexDefined in alfred-margaret-2.1.1.1 · Data.Text.Utf8
type Rep CodeUnitIndex = D1 ('MetaData "CodeUnitIndex" "Data.Text.Utf8" "alfred-margaret-2.1.1.1-LmqCjvAcVEl7fSX12XT7qq" 'True) (C1 ('MetaCons "CodeUnitIndex" 'PrefixI 'True) (S1 ('MetaSel ('Just "codeUnitIndex") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Int)))Defined in alfred-margaret-2.1.1.1 · Data.Text.Utf8

datadata Next a

Constructors

Done !a
Step !a

valuebuildAutomaton :: Text -> Automaton

valuepatternLength :: Automaton -> CodeUnitIndex

Length of the matched pattern measured in UTF-8 code units (bytes).

valuepatternText :: Automaton -> Text

Return the pattern that was used to construct the automaton, O(n).

valuerunText

:: a
-> a -> CodeUnitIndex -> CodeUnitIndex -> Next a
-> Automaton
-> Text
-> a

Finds all matches in the text, calling the match callback with the first and last byte index of each match of the pattern.

valueminimumSkipForCodePoint :: CodePoint -> CodeUnitIndex

Number of bytes that we can skip in the haystack if we want to skip no more than 1 pattern codepoint.

It must always be a low (safe) estimate, otherwise the algorithm can miss matches. It must account for any variation of upper/lower case characters that may occur in the haystack. In most cases, this is the same number of bytes as for the given codepoint

minimumSkipForCodePoint a == 1 minimumSkipForCodePoint д == 2 minimumSkipForCodePoint ⓟ == 3 minimumSkipForCodePoint 🎄 == 4