adict-0.4.1: Approximate dictionary searching

Safe HaskellNone




Alternative cost representation with individual cost components divided into groups with respect to operation weights.



data Group a Source

A Group describes a weight of some edit operation in which a character satistying the predicate is involved. This data structure is meant to collect all characters which determine the same operation weight.




predic :: a -> Bool

The predicate determines which characters belong to the group.

weight :: Weight

Weight of the edit operation in which a character satisfying the predicate is involved.

data CostDiv a Source

Cost function with edit operations divided with respect to weight. Two operations of the same type and with the same weight should be assigned to the same group.




insert :: [Group a]

Cost of the character insertion divided into groups with respect to operation weights.

delete :: a -> Weight

Cost of the character deletion.

subst :: a -> [Group a]

Cost of the character substitution. For each source character there can be a different list of groups involved.

posMod :: Pos -> Weight

Cost of each edit operation is multiplied by the position modifier. For example, the cost of 'a' character deletion on position 3 is computed as delete 'a' * posMod 3.

costDefault :: Eq a => CostDiv aSource

Default cost with all edit operations having the unit weight.

Helper functions for CostDiv construction

type Sub a = Map Weight (Set a)Source

Substition description for some unspecified source character.

mkSub :: Ord a => [(a, Weight)] -> Sub aSource

Construct the substitution descrition from the list of (character y, substition weight from x to y) pairs for some unspecified character x. Characters will be grouped with respect to weight.

unSub :: Ord a => Sub a -> [Group a]Source

Extract the list of groups (each group with unique weight) from the substitution description.

type SubMap a = Map a (Sub a)Source

A susbtitution map which covers all substition operations.

subOn :: Ord a => a -> SubMap a -> Sub aSource

Substitution description for the given character in the substitution map. In other words, the function returns information how the input character can be replaced with other characters from the alphabet.

mkSubMap :: Ord a => [(a, a, Weight)] -> SubMap aSource

Construct the substitution map from the list of (x, y, weight of x -> y substitution) tuples.

Conversion to standard representation

toCost :: Double -> CostDiv a -> Cost aSource

Transform CostDiv to plain Cost function using the default weight value for all operations unspecified in the input cost.

toCostInf :: CostDiv a -> Cost aSource

Transform CostDiv to plain Cost function with default weight value set to +Infinity.