úÎj´d”7      !"#$%&'()*+,-./0123456 None789:;<7:;<789:;< Safe-Inferred=Priority queue. >>Non-empty list of adjacent nodes given in an ascending order. ?Is n node an ending node? @Adjacent list for a given node n. We assume, that the list ! is given in an ascending order. A8First element from the the adjacent list, which is also # a priority in the priority queue. B&Tail elements from the adjacent list. C7Remove minimal edge (from, weight, to) from the queue. D6Find the shortest path from the beginning node to one  of the ending nodes. =>EFG?H@ABCIJD?@D =>EFG?H@ABCIJDNone$A trie of words with character type a and entry type b.  It represents a K from [a] keys to b values. Value in the root node. -Edges to subtries annotated with characters. A  with L values in nodes. M<Decompose the trie into a pair of root value and edge list. NIChild of the trie following the edge annotated with the given character. OFReturn trie edges as a list of (annotation character, subtrie) pairs. P:Construct trie from the root value and the list of edges.  Empty trie. Q'Set the value in the root of the trie. RASubstitute subtrie attached to the edge annotated with the given 9 character (or add new edge if such edge did not exist). .Insert word with the given value to the trie. SSize of the trie. 6Follow the path determined by the input word starting  in the trie root. =Search for the value assigned to the given word in the trie. 9Construct the trie from the list of (word, value) pairs. 9Deconstruct the trie into a list of (word, value) pairs. ?Make the trie from the list of words. Annotate each word with  the () value. >Elminate common subtries. The result is algebraically a trie ) but is represented as a DAWG in memory. T5Serialize the trie and eliminate all common subtries  along the way. U'Construct the trie from the node list. V5Collect unique tries and assign identifiers to them. MNOPQRS TUVWXYMNOPQRS TUMNOPQRS TUVWXYNone A node in the DAWG. Value in the node. 5Edges to subnodes (represented by DAWG node indices)  annotated with characters. 2A directed acyclic word graph with character type a and dictionary  entry type b7. Each node is represented by a unique integer number A which is also an index of the node in the vector of DAWG nodes. Root (index) of the DAWG Vector of DAWG nodes  A DAWGM is a  with L values in nodes. 9Find and eliminate all common subtries in the input trie , and return the trie represented as a DAWG. 9Transform the DAWG to implicit DAWG in a form of a trie. ZSize of the DAWG. [Node by index. \1Value in the DAWG node represented by the index. ]<Edges starting from the DAWG node represented by the index. ^8Index of the node following the edge annotated with the  given character. _8Return the dictionary entry determined by following the  path of node indices. `8Determine the character on the edges between two nodes. a)Serialize the DAWG into a list of nodes. bBDeserialize the DAWG from a list of nodes. Assumptiom: root node $ is last in the serialization list.  Z[\]^_`abcde Z[\]^_` Z[\]^_`abcdeNone   None    NoneFCost represents a cost (or weight) of a symbol insertion, deletion or G substitution. It can depend on edit operation position and on symbol  values. <Cost of edit operation. It has to be a non-negative value! Position in a sentence. (A word parametrized with character type a. 7Simple cost function: all edit operations cost 1 unit. f f f None!GFind all words within a trie with restricted generalized edit distance  lower or equall to k. !g!!gNone";A susbtitution map which covers all substition operations. #>Substition description for some unspecified source character. $CCost function with edit operations divided with respect to weight. D Two operations of the same type and with the same weight should be  assigned to the same group. &9Cost of the character insertion divided into groups with  respect to operation weights. ' Cost of the character deletion. (?Cost of the character substitution. For each source character 4 there can be a different list of groups involved. )DCost 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. *GA Group describes a weight of some edit operation in which a character H satistying the predicate is involved. This data structure is meant to C collect all characters which determine the same operation weight. ,?The predicate determines which characters belong to the group. -AWeight of the edit operation in which a character satisfying the  predicate is involved. .>Default cost with all edit operations having the unit weight. /BConstruct the substitution descrition from the list of (character y,  substition weight from x to y') pairs for some unspecified character  x6. Characters will be grouped with respect to weight. 0DExtract the list of groups (each group with unique weight) from the  substitution description. 1JSubstitution description for the given character in the substitution map. N In other words, the function returns information how the input character can 6 be replaced with other characters from the alphabet. 21Construct the substitution map from the list of (x, y , weight of  x -> y substitution) tuples. 3HTransform CostDiv to plain Cost function using the default weight value 3 for all operations unspecified in the input cost. 4CTransform CostDiv to plain Cost function with default weight value  set to  +Infinity. "#$%&'()*+,-./01234"#$%&'()*+,-./01234*+,-$%&'().#/0"1234 "#$%&'()*+,-./01234 None5CWe can check, if CostDiv satisfies basic properties. On the other 2 hand, we do not do this for plain Cost function. hijklmnopqrst5uv5 hkjilmnopqrst5uv Nonew<Restricted generalized edit distance between two words with  given cost function. www None6GFind all words within a list with restricted generalized edit distance  from x lower or equall to k. 666None  !56   6!5x !" # #  $ % & ' ( ) *+,--$%./012)345678 9 :;<=>?@ABCDEF@GHIJKLMNOPQRSTUVWXYZ[\]W^_`abcXY;<d e f g , h i   j k l m C n o p q rs adict-0.3.0NLP.Adict.TrieNLP.Adict.DAWG NLP.AdictNLP.Adict.CostDivNLP.Adict.NodeNLP.Adict.GraphNLP.Adict.Trie.InternalNLP.Adict.DAWG.InternalNLP.Adict.CoreNLP.Adict.BasicNLP.Adict.NearestNLP.Adict.DistNLP.Adict.BruteTrie rootValueedgeMapTrieMemptyinsertfollowlookupfromListtoListfromLang implicitDAWGNodevalueInsubNodesDAWGrootnodesDAWGMfromTriefromDAWGCostdeletesubstWeightPosWord costDefaultfindAllSubMapSubCostDivposModGroupFilterpredicweightmkSubunSubsubOnmkSubMaptoCost toCostInf findNearest bruteSearchunNodemkNode nodeValue nodeEdgesPQAdjIsEndEdgesproxyfollsminViewminPathfromtoEdgepushcontainers-0.5.0.0 Data.Map.BaseMapbase Data.MaybeMaybeunTriechildanyChildmkTriesetValue substChildsize serialize deserializecollectcollect' $fBinaryTrie $fFunctorTrienodeByvalueByedgesedgeOnentrycharOn $fBinaryDAWG#searchWhichInsDelnodeIDnodePosnodeCharNodeIDweightOf mapWeight $fOrdNode$fEqNodeeditDist