adict-0.4.1: Approximate dictionary searching

Description

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

Synopsis

# CostDiv

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.

Constructors

 Filter Fieldspredic :: a -> BoolThe predicate determines which characters belong to the group. weight :: WeightWeight 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.

Constructors

 CostDiv Fieldsinsert :: [Group a]Cost of the character insertion divided into groups with respect to operation weights. delete :: a -> WeightCost 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 -> WeightCost 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`.