Data.Text.Utf8.BoyerMoore.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 module contains a almost 1:1 translation from the C example code in the wikipedia article.

The algorithm here can be potentially improved by including the Galil rule (https:/en.wikipedia.orgwiki/Boyer%E2%80%93Moore_string-search_algorithm#The_Galil_rule)

Documentation

data 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.

Instances

Eq Automaton

Defined in Data.Text.Utf8.BoyerMoore.Automaton

Methods

(==) :: Automaton -> Automaton -> Bool

(/=) :: Automaton -> Automaton -> Bool

Show Automaton

Defined in Data.Text.Utf8.BoyerMoore.Automaton

Methods

showsPrec :: Int -> Automaton -> ShowS

show :: Automaton -> String

showList :: [Automaton] -> ShowS

Generic Automaton

Defined in Data.Text.Utf8.BoyerMoore.Automaton

Associated Types

type Rep Automaton :: Type -> Type

Methods

from :: Automaton -> Rep Automaton x

to :: Rep Automaton x -> Automaton

Hashable Automaton

Defined in Data.Text.Utf8.BoyerMoore.Automaton

Methods

hashWithSalt :: Int -> Automaton -> Int

hash :: Automaton -> Int

ToJSON Automaton

Defined in Data.Text.Utf8.BoyerMoore.Automaton

Methods

toJSON :: Automaton -> Value

toEncoding :: Automaton -> Encoding

toJSONList :: [Automaton] -> Value

toEncodingList :: [Automaton] -> Encoding

FromJSON Automaton

Defined in Data.Text.Utf8.BoyerMoore.Automaton

Methods

parseJSON :: Value -> Parser Automaton

parseJSONList :: Value -> Parser [Automaton]

NFData Automaton

Defined in Data.Text.Utf8.BoyerMoore.Automaton

Methods

rnf :: Automaton -> ()

type Rep Automaton

Defined in Data.Text.Utf8.BoyerMoore.Automaton

type Rep Automaton

data CaseSensitivity

Constructors

CaseSensitive

IgnoreCase

Instances

Eq CaseSensitivity

Defined in Data.Text.CaseSensitivity

Methods

(==) :: CaseSensitivity -> CaseSensitivity -> Bool

(/=) :: CaseSensitivity -> CaseSensitivity -> Bool

Show CaseSensitivity

Defined in Data.Text.CaseSensitivity

Methods

showsPrec :: Int -> CaseSensitivity -> ShowS

show :: CaseSensitivity -> String

showList :: [CaseSensitivity] -> ShowS

Generic CaseSensitivity

Defined in Data.Text.CaseSensitivity

Associated Types

type Rep CaseSensitivity :: Type -> Type

Methods

from :: CaseSensitivity -> Rep CaseSensitivity x

to :: Rep CaseSensitivity x -> CaseSensitivity

Hashable CaseSensitivity

Defined in Data.Text.CaseSensitivity

Methods

hashWithSalt :: Int -> CaseSensitivity -> Int

hash :: CaseSensitivity -> Int

ToJSON CaseSensitivity

Defined in Data.Text.CaseSensitivity

Methods

toJSON :: CaseSensitivity -> Value

toEncoding :: CaseSensitivity -> Encoding

toJSONList :: [CaseSensitivity] -> Value

toEncodingList :: [CaseSensitivity] -> Encoding

FromJSON CaseSensitivity

Defined in Data.Text.CaseSensitivity

Methods

parseJSON :: Value -> Parser CaseSensitivity

parseJSONList :: Value -> Parser [CaseSensitivity]

NFData CaseSensitivity

Defined in Data.Text.CaseSensitivity

Methods

rnf :: CaseSensitivity -> ()

type Rep CaseSensitivity

Defined in Data.Text.CaseSensitivity

type Rep CaseSensitivity = D1 ('MetaData "CaseSensitivity" "Data.Text.CaseSensitivity" "alfred-margaret-1.1.2.0-XY9PIx1ODVHYQ5PowYWXi" 'False) (C1 ('MetaCons "CaseSensitive" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "IgnoreCase" 'PrefixI 'False) (U1 :: Type -> Type))

newtype 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

Fields

• codeUnitIndex :: Int

Instances

Bounded CodeUnitIndex

Defined in Data.Text.Utf8

Methods

minBound :: CodeUnitIndex

maxBound :: CodeUnitIndex

Eq CodeUnitIndex

Defined in Data.Text.Utf8

Methods

(==) :: CodeUnitIndex -> CodeUnitIndex -> Bool

(/=) :: CodeUnitIndex -> CodeUnitIndex -> Bool

Num CodeUnitIndex

Defined in Data.Text.Utf8

Methods

(+) :: CodeUnitIndex -> CodeUnitIndex -> CodeUnitIndex

(-) :: CodeUnitIndex -> CodeUnitIndex -> CodeUnitIndex

(*) :: CodeUnitIndex -> CodeUnitIndex -> CodeUnitIndex

negate :: CodeUnitIndex -> CodeUnitIndex

abs :: CodeUnitIndex -> CodeUnitIndex

signum :: CodeUnitIndex -> CodeUnitIndex

fromInteger :: Integer -> CodeUnitIndex

Ord CodeUnitIndex

Defined in Data.Text.Utf8

Methods

compare :: CodeUnitIndex -> CodeUnitIndex -> Ordering

(<) :: CodeUnitIndex -> CodeUnitIndex -> Bool

(<=) :: CodeUnitIndex -> CodeUnitIndex -> Bool

(>) :: CodeUnitIndex -> CodeUnitIndex -> Bool

(>=) :: CodeUnitIndex -> CodeUnitIndex -> Bool

max :: CodeUnitIndex -> CodeUnitIndex -> CodeUnitIndex

min :: CodeUnitIndex -> CodeUnitIndex -> CodeUnitIndex

Show CodeUnitIndex

Defined in Data.Text.Utf8

Methods

showsPrec :: Int -> CodeUnitIndex -> ShowS

show :: CodeUnitIndex -> String

showList :: [CodeUnitIndex] -> ShowS

Generic CodeUnitIndex

Defined in Data.Text.Utf8

Associated Types

type Rep CodeUnitIndex :: Type -> Type

Methods

from :: CodeUnitIndex -> Rep CodeUnitIndex x

to :: Rep CodeUnitIndex x -> CodeUnitIndex

Hashable CodeUnitIndex

Defined in Data.Text.Utf8

Methods

hashWithSalt :: Int -> CodeUnitIndex -> Int

hash :: CodeUnitIndex -> Int

ToJSON CodeUnitIndex

Defined in Data.Text.Utf8

Methods

toJSON :: CodeUnitIndex -> Value

toEncoding :: CodeUnitIndex -> Encoding

toJSONList :: [CodeUnitIndex] -> Value

toEncodingList :: [CodeUnitIndex] -> Encoding

FromJSON CodeUnitIndex

Defined in Data.Text.Utf8

Methods

parseJSON :: Value -> Parser CodeUnitIndex

parseJSONList :: Value -> Parser [CodeUnitIndex]

NFData CodeUnitIndex

Defined in Data.Text.Utf8

Methods

rnf :: CodeUnitIndex -> ()

type Rep CodeUnitIndex

Defined in Data.Text.Utf8

type Rep CodeUnitIndex = D1 ('MetaData "CodeUnitIndex" "Data.Text.Utf8" "alfred-margaret-1.1.2.0-XY9PIx1ODVHYQ5PowYWXi" 'True) (C1 ('MetaCons "CodeUnitIndex" 'PrefixI 'True) (S1 ('MetaSel ('Just "codeUnitIndex") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Int)))

data Next a

Result of handling a match: stepping the automaton can exit early by returning a Done, or it can continue with a new accumulator with Step.

Constructors

Done !a

Step !a

buildAutomaton :: Text -> Automaton

patternLength :: Automaton -> CodeUnitIndex

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

patternText :: Automaton -> Text

Return the pattern that was used to construct the automaton.

runText :: forall a. a -> (a -> CodeUnitIndex -> Next a) -> Automaton -> Text -> a

Finds all matches in the text, calling the match callback with the *first* matched character of each match of the pattern.

NOTE: This is unlike Aho-Corasick, which reports the index of the character right after a match.

NOTE: In the UTF-16 version of this module, there is a function runLower which does lower-case matching. This function does not exist for the UTF-8 version since it is very tricky to skip code points going backwards without preprocessing the whole input first.

NOTE: To get full advantage of inlining this function, you probably want to compile the compiling module with -fllvm and the same optimization flags as this module.