Text.AhoCorasick

Aho-Corasick string matching algorithm

Simplest example

example1 = mapM_ print $ findAll simpleSM "ushers" where
    simpleSM = makeSimpleStateMachine ["he","she","his","hers"]

Position {pIndex = 1, pLength = 3, pVal = "she"}
Position {pIndex = 2, pLength = 2, pVal = "he"}
Position {pIndex = 2, pLength = 4, pVal = "hers"}

With data

example2 = mapM_ print $ findAll sm "ushers" where
    sm = makeStateMachine [("he",0),("she",1),("his",2),("hers",3)]

Position {pIndex = 1, pLength = 3, pVal = 1}
Position {pIndex = 2, pLength = 2, pVal = 0}
Position {pIndex = 2, pLength = 4, pVal = 3}

Step-by-step state machine evaluation

example3 = mapM_ print $ next sm "ushers" where
    sm = makeSimpleStateMachine ["he","she","his","hers"]
    next _ [] = []
    next sm (s:n) = let (SMStepRes match nextSM) = stateMachineStep sm s in
        (s, match) : next nextSM n

('u',[])
('s',[])
('h',[])
('e',[(3,"she"),(2,"he")])
('r',[])
('s',[(4,"hers")])

Basic interface

makeStateMachine :: (Eq keySymb, Hashable keySymb) => [([keySymb], val)] -> StateMachine keySymb val

Associate custom values with the search keys

makeSimpleStateMachine :: (Eq keySymb, Hashable keySymb) => [[keySymb]] -> StateMachine keySymb [keySymb]

Returns search keys as values

findAll :: (Eq keySymb, Hashable keySymb) => StateMachine keySymb val -> [keySymb] -> [Position val]

data Position val

Constructors

Position

Fields

• pIndex :: Int
• pLength :: Int
• pVal :: val

Instances

Show val => Show (Position val)

Defined in Text.AhoCorasick

Methods

showsPrec :: Int -> Position val -> ShowS

show :: Position val -> String

showList :: [Position val] -> ShowS

Low-level interface

stateMachineStep :: (Eq keySymb, Hashable keySymb) => StateMachine keySymb val -> keySymb -> SMStepRes keySymb val

data (Eq keySymb, Hashable keySymb) => SMStepRes keySymb val

Constructors

SMStepRes

Fields

• smsrMatch :: [(KeyLength, val)]
• smsrNextSM :: StateMachine keySymb val

Instances

(Eq keySymb, Hashable keySymb, Show keySymb, Show val) => Show (SMStepRes keySymb val)

Defined in Text.AhoCorasick

Methods

showsPrec :: Int -> SMStepRes keySymb val -> ShowS

show :: SMStepRes keySymb val -> String

showList :: [SMStepRes keySymb val] -> ShowS

resetStateMachine :: (Eq keySymb, Hashable keySymb) => StateMachine keySymb val -> StateMachine keySymb val

Types

data (Eq keySymb, Hashable keySymb) => StateMachine keySymb val

Instances

(Eq keySymb, Hashable keySymb, Show keySymb, Show val) => Show (StateMachine keySymb val)

Defined in Text.AhoCorasick

Methods

showsPrec :: Int -> StateMachine keySymb val -> ShowS

show :: StateMachine keySymb val -> String

showList :: [StateMachine keySymb val] -> ShowS

type KeyLength = Int