Text.PhonotacticLearner.DFST

Implementations of deterministic finite state transducers containing both a polymorphic DFST functor and a typeclass for fast specialized types (with several implementations provided). Input alphabets are assumed to be finite rectangles inside Ix types. Trandsuction functions are provided for both Monoid and Semiring output types. DFSTs may be created directly, generated from globs, or from smaller DFSTs using the product construction.

Optimized C functions for common output types (Sum Int, Multicount, Expectation Vec, and Expectation Double) are included which use the PackedDFA typeclass to convert to and from the generic type. The specialized types additionally support the following operations.

• Packing strings into a compact format (PackedText)
• Transducing packed strings into integer counts and Multicounts
• Summing over all paths of expectation transducers
• Applying maxent weights to vector counts to get expectations

Documentation

fnArray :: (Ix i, IArray a e) => (i, i) -> (i -> e) -> a i e

Create an array by caching a function over a rectangle. Depending on the array type used, this can be used to memoise or precompute.

xbd :: (a, a) -> (b, b) -> ((a, b), (a, b))

Turn a pair of interval tuples into an interval of pairs. Used to compute array bounds for a cartesian product.

Polymorphic DFSTs

data DFST q sigma k

Polymorphic type for deterministic finite state transducers. For an efficient implementation, the set of states and input characters are both limited to be Ix rectangles and their product is the array bounds. This type is a functor over its output type (note that transduction is only possible into a Monoid or Semiring).

Constructors

DFST

Fields

• initialState :: q
• transitionMatrix :: Array (q, sigma) (q, k)
• finalWeights :: Array q k

Instances

(Ix q, Ix sigma) => Functor (DFST q sigma)

Methods

fmap :: (a -> b) -> DFST q sigma a -> DFST q sigma b

(<$) :: a -> DFST q sigma b -> DFST q sigma a

(Show k, Show sigma, Show q, Ix sigma, Ix q) => Show (DFST q sigma k)

Methods

showsPrec :: Int -> DFST q sigma k -> ShowS

show :: DFST q sigma k -> String

showList :: [DFST q sigma k] -> ShowS

(NFData q, NFData sigma, NFData k) => NFData (DFST q sigma k)

Methods

rnf :: DFST q sigma k -> ()

stateBounds :: (Ix q, Ix sigma) => DFST q sigma w -> (q, q)

bounds for state labels

segBounds :: (Ix q, Ix sigma) => DFST q sigma k -> (sigma, sigma)

boounds for accepted segments (characters)

transition :: (Ix q, Ix sigma) => DFST q sigma k -> q -> sigma -> (q, k)

advance by one state and get weight output

transduceM :: (Ix q, Ix sigma, Monoid k) => DFST q sigma k -> [sigma] -> k

Transduce a string of segments where and output the product of the weights (as a Monoid).

transduceR :: (Ix q, Ix sigma, Semiring k) => DFST q sigma k -> [sigma] -> k

Transduce a string of segments where and output the product of the weights (as a Ring).

Specialized DFSTs

class PackedDFA pd k | pd -> k where

Typeclass for converting speaiclized DFSTs to and from polymorphic ones. This is used by several optimized versions for various output types that can be manupulated by fast C functions.

Minimal complete definition

numStates, psegBounds, unpackDFA, packDFA

Methods

numStates :: Ix sigma => pd sigma -> Int

Number fo states in DFA

psegBounds :: Ix sigma => pd sigma -> (sigma, sigma)

Bounds of input rectangle

unpackDFA :: Ix sigma => pd sigma -> DFST Int sigma k

umpack

packDFA :: forall sigma. Ix sigma => Int16 -> Int16 -> (sigma, sigma) -> ((Int16, sigma) -> Int16) -> ((Int16, sigma) -> k) -> (Int16 -> k) -> pd sigma

Pack a DFA from its component functions. Use pruneAndPack to convert a polymorphic DFST.

Instances

PackedDFA MulticountDFST Multicount

Methods

numStates :: Ix sigma => MulticountDFST sigma -> Int

psegBounds :: Ix sigma => MulticountDFST sigma -> (sigma, sigma)

unpackDFA :: Ix sigma => MulticountDFST sigma -> DFST Int sigma Multicount

packDFA :: Ix sigma => Int16 -> Int16 -> (sigma, sigma) -> ((Int16, sigma) -> Int16) -> ((Int16, sigma) -> Multicount) -> (Int16 -> Multicount) -> MulticountDFST sigma

PackedDFA ExpDoubleDFST (Expectation Double)

Methods

numStates :: Ix sigma => ExpDoubleDFST sigma -> Int

psegBounds :: Ix sigma => ExpDoubleDFST sigma -> (sigma, sigma)

unpackDFA :: Ix sigma => ExpDoubleDFST sigma -> DFST Int sigma (Expectation Double)

packDFA :: Ix sigma => Int16 -> Int16 -> (sigma, sigma) -> ((Int16, sigma) -> Int16) -> ((Int16, sigma) -> Expectation Double) -> (Int16 -> Expectation Double) -> ExpDoubleDFST sigma

PackedDFA ExpVecDFST (Expectation Vec)

Methods

numStates :: Ix sigma => ExpVecDFST sigma -> Int

psegBounds :: Ix sigma => ExpVecDFST sigma -> (sigma, sigma)

unpackDFA :: Ix sigma => ExpVecDFST sigma -> DFST Int sigma (Expectation Vec)

packDFA :: Ix sigma => Int16 -> Int16 -> (sigma, sigma) -> ((Int16, sigma) -> Int16) -> ((Int16, sigma) -> Expectation Vec) -> (Int16 -> Expectation Vec) -> ExpVecDFST sigma

PackedDFA ShortDFST (Sum Int)

Methods

numStates :: Ix sigma => ShortDFST sigma -> Int

psegBounds :: Ix sigma => ShortDFST sigma -> (sigma, sigma)

unpackDFA :: Ix sigma => ShortDFST sigma -> DFST Int sigma (Sum Int)

packDFA :: Ix sigma => Int16 -> Int16 -> (sigma, sigma) -> ((Int16, sigma) -> Int16) -> ((Int16, sigma) -> Sum Int) -> (Int16 -> Sum Int) -> ShortDFST sigma

pruneUnreachable :: forall q sigma k. (Ix q, Ix sigma) => DFST q sigma k -> DFST Int sigma k

Remove unreachable states and renumber as integers (starting from 1) using a mark-sweep algorithm. Result is polymorphic.

pruneAndPack :: forall q sigma pd k. (Ix q, Ix sigma, PackedDFA pd k) => DFST q sigma k -> pd sigma

Prune unreachable states and pack into a specialized implementation

rawIntersection :: (Ix q1, Ix q2, Ix sigma) => (k1 -> k2 -> k3) -> DFST q1 sigma k1 -> DFST q2 sigma k2 -> DFST (q1, q2) sigma k3

Lifts a weight combining function into one that combines DFAs. Performs no pruning and new states are all pairs of old ones. For boolean weights, use (&&) for intersection and (||) for union.

dfaProduct :: (Ix l1, Ix l2, Ix sigma) => (w1 -> w2 -> w3) -> DFST l1 sigma w1 -> DFST l2 sigma w2 -> DFST Int sigma w3

Product construction with pruning.

nildfa :: (Ix sigma, Monoid k) => (sigma, sigma) -> DFST Int sigma k

Given input bounds, Construct a DFST which always returns mempty for any string.

data PackedText sigma

Structure holding text and word frequencies as a flat array of segment indices (in the input rectangle) for fast transduction.

packSingleText :: Ix sigma => (sigma, sigma) -> [sigma] -> PackedText sigma

Pack a single string

packMultiText :: Ix sigma => (sigma, sigma) -> [([sigma], Int)] -> PackedText sigma

Pack a list of string, fewquency pairs

data ShortDFST sigma

Optimized DFST specialized to transduce integers

Instances

PackedDFA ShortDFST (Sum Int)

Methods

numStates :: Ix sigma => ShortDFST sigma -> Int

psegBounds :: Ix sigma => ShortDFST sigma -> (sigma, sigma)

unpackDFA :: Ix sigma => ShortDFST sigma -> DFST Int sigma (Sum Int)

packDFA :: Ix sigma => Int16 -> Int16 -> (sigma, sigma) -> ((Int16, sigma) -> Int16) -> ((Int16, sigma) -> Sum Int) -> (Int16 -> Sum Int) -> ShortDFST sigma

Show sigma => Show (ShortDFST sigma)

Methods

showsPrec :: Int -> ShortDFST sigma -> ShowS

show :: ShortDFST sigma -> String

showList :: [ShortDFST sigma] -> ShowS

NFData sigma => NFData (ShortDFST sigma)

Methods

rnf :: ShortDFST sigma -> ()

transducePackedShort :: Ix sigma => ShortDFST sigma -> PackedText sigma -> Int

Fast transduction of integers. For multiple words, returns the sum of all transductions.

data MulticountDFST sigma

Optimized DFST specialized to transduce into Multicount mnd count multiple quantities in parallel.

Instances

PackedDFA MulticountDFST Multicount

Methods

numStates :: Ix sigma => MulticountDFST sigma -> Int

psegBounds :: Ix sigma => MulticountDFST sigma -> (sigma, sigma)

unpackDFA :: Ix sigma => MulticountDFST sigma -> DFST Int sigma Multicount

packDFA :: Ix sigma => Int16 -> Int16 -> (sigma, sigma) -> ((Int16, sigma) -> Int16) -> ((Int16, sigma) -> Multicount) -> (Int16 -> Multicount) -> MulticountDFST sigma

Show sigma => Show (MulticountDFST sigma)

Methods

showsPrec :: Int -> MulticountDFST sigma -> ShowS

show :: MulticountDFST sigma -> String

showList :: [MulticountDFST sigma] -> ShowS

NFData sigma => NFData (MulticountDFST sigma)

Methods

rnf :: MulticountDFST sigma -> ()

transducePackedMulti :: Ix sigma => MulticountDFST sigma -> PackedText sigma -> Multicount

Fast transduction of Multicount. For multiple words, returns the sum of all transductions.

data ExpVecDFST sigma

Optimized DFST form calculating verctor expectations over the entire probability distribution defined by the DFA.

Instances

PackedDFA ExpVecDFST (Expectation Vec)

Methods

numStates :: Ix sigma => ExpVecDFST sigma -> Int

psegBounds :: Ix sigma => ExpVecDFST sigma -> (sigma, sigma)

unpackDFA :: Ix sigma => ExpVecDFST sigma -> DFST Int sigma (Expectation Vec)

packDFA :: Ix sigma => Int16 -> Int16 -> (sigma, sigma) -> ((Int16, sigma) -> Int16) -> ((Int16, sigma) -> Expectation Vec) -> (Int16 -> Expectation Vec) -> ExpVecDFST sigma

Show sigma => Show (ExpVecDFST sigma)

Methods

showsPrec :: Int -> ExpVecDFST sigma -> ShowS

show :: ExpVecDFST sigma -> String

showList :: [ExpVecDFST sigma] -> ShowS

weightExpVec :: Ix sigma => MulticountDFST sigma -> Vec -> ExpVecDFST sigma

Assign maxent weights to the counts in a Multicount to get expectations (which include probabilities).

expsByLengthVec :: Ix sigma => ExpVecDFST sigma -> Int -> Array Int (Expectation Vec)

Get the total expectations over each length of string up to a maximum

data ExpDoubleDFST sigma

Optimized DFST form calculating scalar expectations over the entire probability distribution defined by the DFA.

Instances

PackedDFA ExpDoubleDFST (Expectation Double)

Methods

numStates :: Ix sigma => ExpDoubleDFST sigma -> Int

psegBounds :: Ix sigma => ExpDoubleDFST sigma -> (sigma, sigma)

unpackDFA :: Ix sigma => ExpDoubleDFST sigma -> DFST Int sigma (Expectation Double)

packDFA :: Ix sigma => Int16 -> Int16 -> (sigma, sigma) -> ((Int16, sigma) -> Int16) -> ((Int16, sigma) -> Expectation Double) -> (Int16 -> Expectation Double) -> ExpDoubleDFST sigma

Show sigma => Show (ExpDoubleDFST sigma)

Methods

showsPrec :: Int -> ExpDoubleDFST sigma -> ShowS

show :: ExpDoubleDFST sigma -> String

showList :: [ExpDoubleDFST sigma] -> ShowS

weightExpPartial :: Ix sigma => MulticountDFST sigma -> Vec -> Vec -> ExpDoubleDFST sigma

Assign maxent weights to the counts in a Multicount to and apply a covector to the resulting expectations.

expsByLengthDouble :: Ix sigma => ExpDoubleDFST sigma -> Int -> Array Int (Expectation Double)

Get the total expectations over each length of string up to a maximum

Glob recognition

data GlobReps

Type for Glob quantifiers

Constructors

GSingle

GPlus

GStar

Instances

Enum GlobReps

Methods

succ :: GlobReps -> GlobReps

pred :: GlobReps -> GlobReps

toEnum :: Int -> GlobReps

fromEnum :: GlobReps -> Int

enumFrom :: GlobReps -> [GlobReps]

enumFromThen :: GlobReps -> GlobReps -> [GlobReps]

enumFromTo :: GlobReps -> GlobReps -> [GlobReps]

enumFromThenTo :: GlobReps -> GlobReps -> GlobReps -> [GlobReps]

Eq GlobReps

Methods

(==) :: GlobReps -> GlobReps -> Bool

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

Ord GlobReps

Methods

compare :: GlobReps -> GlobReps -> Ordering

(<) :: GlobReps -> GlobReps -> Bool

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

(>) :: GlobReps -> GlobReps -> Bool

(>=) :: GlobReps -> GlobReps -> Bool

max :: GlobReps -> GlobReps -> GlobReps

min :: GlobReps -> GlobReps -> GlobReps

Read GlobReps

Methods

readsPrec :: Int -> ReadS GlobReps

readList :: ReadS [GlobReps]

readPrec :: ReadPrec GlobReps

readListPrec :: ReadPrec [GlobReps]

Show GlobReps

Methods

showsPrec :: Int -> GlobReps -> ShowS

show :: GlobReps -> String

showList :: [GlobReps] -> ShowS

NFData GlobReps

Methods

rnf :: GlobReps -> ()

type SegSet sigma = UArray sigma Bool

Fast reperesentation of a set of segments by its characteristic function over an enclosing rectangle of segments.

data ListGlob sigma

Glob of segment lists, nore generalized version of ngrams allowing for repeated classes as well as single ones. The two boolean parameters restrict the glob to match a prefixes or suffixes only.

Constructors

ListGlob Bool Bool [(GlobReps, SegSet sigma)]

Instances

Ix sigma => Eq (ListGlob sigma)

Methods

(==) :: ListGlob sigma -> ListGlob sigma -> Bool

(/=) :: ListGlob sigma -> ListGlob sigma -> Bool

Ix sigma => Ord (ListGlob sigma)

Methods

compare :: ListGlob sigma -> ListGlob sigma -> Ordering

(<) :: ListGlob sigma -> ListGlob sigma -> Bool

(<=) :: ListGlob sigma -> ListGlob sigma -> Bool

(>) :: ListGlob sigma -> ListGlob sigma -> Bool

(>=) :: ListGlob sigma -> ListGlob sigma -> Bool

max :: ListGlob sigma -> ListGlob sigma -> ListGlob sigma

min :: ListGlob sigma -> ListGlob sigma -> ListGlob sigma

Show (ListGlob Char)

Globs are displayed in regex format

Methods

showsPrec :: Int -> ListGlob Char -> ShowS

show :: ListGlob Char -> String

showList :: [ListGlob Char] -> ShowS

(NFData sigma, Ix sigma) => NFData (ListGlob sigma)

Methods

rnf :: ListGlob sigma -> ()

matchCounter :: forall sigma. Ix sigma => ListGlob sigma -> ShortDFST sigma

Create a DFST countign the violations of a ListGlob. Each SegSet in the glob must have the same bounds and the glob must not be empty.

Orphan instances

(IArray UArray e, NFData i, Ix i) => NFData (UArray i e)

Methods

rnf :: UArray i e -> ()