{'fraction_non_alphanumeric': 0.04322158971115328, 'fraction_numerical': 0.006852203246890154, 'mean_word_length': 4.201206140350878, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Preserving Trees in Minimal Automata

We present a method to store additional information in a minimal automaton so that it is possible to compute a corresponding tree node number for a state. The number can then be used to retrieve additional information. The method works for minimal (and any other) deterministic acyclic finite state automata (DFAs). We also show how to compute the inverse mapping.


Introduction
Deterministic finite state automata and transducers are widely used in natural language processing and computational linguistics. The most frequent uses include dictionaries (Daciuk et al., 2010), acoustic and language models (the latter indirectly, using perfect hashing to number words), as well as hidden Markov models used for tagging and chunking. Acyclic minimal automata recognize the same languages as automata in form of trees, but they take considerably less space. Therefore, minimization is an obligatory step in most applications. In LZ-style compression of automata (Ristov and Korencic, 2015), it is a trie (a letter-tree) that is compressed without going through minimization. However, the compression finds identical sequences of transitions, so it also finds isomorphic trees, which is what minimization does.
In speech recognition, trees are often used (Ortmanns et al., 1997) instead of minimal automata, because lookahead probabilities are computed for individual nodes of the trees. At a given moment in time represented by a node (a state) in a treelike automaton, one wants to know the probability of the most probable word that is recognized by going through that state. Minimal perfect hashing (Roche, 1995) can deliver a range of numbers for all words going through that state. It is then possible to use them to access probabilities of each word, and find the maximal one. This can be timeconsuming, especially close to the root of the tree.
What is needed for lookahead probabilities is a storage for the probability of the most probable word recognized by going through that state, i.e. one probability for each state. This is trivial to implement in a tree -one simply stores the probability in the state. In a minimal DFA, a state can represent many sets of words as it may be equivalent to several nodes in a tree. Therefore in a state of a minimal DFA, one must refer somehow to the corresponding node in the tree, or at least to a place associated with that node. The solution is to provide a dynamically computed mapping from prefixes of words to node numbers in the tree.

Definitions
A deterministic finite state automaton (DFA) is a 5-tuple M = (Q, Σ, δ, q 0 , F ), where Q is a finite set of states, Σ is a finite set of symbols called an alphabet, δ : Q × Σ → Q is a transition function, q 0 ∈ Q is the initial state, and F ⊆ Q is the set of final states. The size of an automaton |M | is the number |Q| of its states. We use incomplete automata, so our transition function is partial. When δ(q, σ) ∈ Q, we write δ(q, σ) = ⊥.
The transition function δ can be extended in the usual way so that δ * : Q × Σ * → Q: The language L(M ) of an automaton M is defined as all words that are recognized along paths from the initial state to any of the final states: Among all automata recognizing the same language there is one (up to isomorphism) that has the smallest number of states. It is called the minimal automaton M min .
The automata described throughout the paper are acyclic. This means there is no pair q ∈ Q and w ∈ Σ + such that δ * (q, w) = q. The language of an acyclic DFA is always a finite set of finite-length words.
Among all acyclic DFAs that recognize the same language, there is one in form of a tree. All states of such automaton, except for the initial state, have exactly one incoming transition, i.e. they are the target of exactly one transition. The initial state has no incoming transitions. We will use the name nodes for states of a tree, and we will use the name edges for its transitions.  Figure 1: A DFA as a tree recognizing words: car, cart, cat, clay, pat, pay, play, rat, ray, sat, say, and stay.

Counting Tree Nodes
A dynamically computed mapping from prefixes of words to node numbers in the tree can be achieved by counting states (nodes) in the tree. Let c(q) be the number of states reachable from state q including state q. For a given state q, c(q) can be computed as: If the automaton has a tree shape, and q is the root of a subtree, then c(q) is the number of nodes in that subtree. In a minimal acyclic DFA, the state q can represent several subtrees. However, those trees are isomorphic, and they have exactly the same number of nodes. By induction, equation (3) correctly counts the number of nodes in the corresponding subtree for a minimal acyclic DFA. Actually, it counts that number for any acyclic DFA. A state in a minimal DFA does not have a node number, as it can correspond to several nodes in the tree. Let uv = w ∈ L(M ). The prefix u denotes a single node in the tree; it also denotes a state q = δ * (q 0 , u) corresponding to that node (and perhaps to some other nodes). Nodes are numbered in postorder. Counting nodes from 0, the node number µ(u) for a prefix u can be calculated as the number of nodes with smaller node numbers. Those are (c(δ * (q 0 , u))−1) nodes reachable from δ * (q 0 , u) (excluding δ * (q 0 , u)), and all η(u) nodes visited while recognizing all words w ≺ w = uv that are not visited while recognizing the prefix u: where: and for a state q and a label σ ∈ Σ : δ(q, σ) = ⊥, let κ(q, σ) be: The inverse mapping is also easy to calculate. Let σ q,n be a label of a transition going out from state q such that κ(q, σ) < n ≤ κ(q, σ) + c(δ(q, σ)). Let λ(q, n) be the prefix corresponding to node number n in a subtree with a root q.

Edges Can Be Counted Too
Sometimes, it may be more beneficial to use edges of the tree instead of nodes. It is possible to provide equations very similar to those already given for states. However, they are not necessary. Let us look at Figure 1 again. An edge number is the number of the node that the edge leads to. Therefore, we can index the edges using exactly the same formulas as those given for nodes.

Implementation
To implement the mappings one needs to store the value of c(q) in states q, or the value of κ(q, σ) on the transition going out from states q and labeled with σ. The second solution is faster, but it requires more memory, as there are more transitions than states.
The first solution delivers smaller memory footprint than the second one as there are more transitions than states in a minimal DFA (unless the DFA is a tree). However, in many automata representations, states are implicit; there addresses are the addresses of their first outgoing transition. The additional number can be stored in front of the first transition, but that would impede storing one state inside another (a common compression technique). Superimposed coding (Liang, 1983) based on a sparse matrix representation technique (Tarjan and Yao, 1979;Dencker et al., 1984;Fredman et al., 1984) enforces fixed-length transitions belonging to overlapping states, which excludes storing something else before the first transition of a state. It is possible to provide an additional vector to store the desired values, but there is a problem with addressing them, as state numbers are not used for addressing a states in the DFA (transition numbers are used instead).
The mapping from prefixes (identifying nodes in a tree) to numbers is implemented as function Pref2N given below. In order to get the prefix number for prefix w, one calls Pref2N(M, w, q 0 ). Line 2 computes c(δ * (q 0 , u))−1. The for loop in lines 5 and 6 computes κ(δ(q 0 , x), a). Function Pref2N is called |w| times for each symbol a in the prefix. The for loop runs at most |Σ| times in each invocation of function Pref2N. This gives us overall time complexity of O(|w||Σ|) times, i.e. linear with regard of the prefix. With the values of κ(q, a) stored on transitions δ(q, a), we replace line 4 with s ← κ(q, a) and remove lines 5 and 6, making the function a bit faster.
The inverse mapping is implemented as function N2Pref. To get a prefix number n, one should call N2Pref(M, n, q 0 ). Function N2Pref is called as many times as there are symbols in the computed prefix. The for loop runs at most |Σ| times. As other operations take constant time, the time complexity of the function is O(|Σ||w max |), where w max is the longest word in the language of the DFA. Note that in the superimposed coding (sparse matrix) representation, the for loop must run for every symbol of the alphabet. In a list representation, the loop runs only on (symbols on) the outgoing transitions, which can be significantly faster. Having pre-computed values of κ on transitions saves us computing the sum in line 10; the κ value is used directly in line 7.

Conclusions
We have shown methods to store indexes of nodes or edges of a tree in a minimal (or pseudominimal) automaton. Trees are sometimes used in place of minimal DFAs because information associated with their nodes or edges is needed. The presented methods render such trees obsolete. The minimal DFA can provide indexes in vectors that would store tree-related data. As a minimal DFA is usually much smaller than a tree, the methods can save a lot of memory. We have also developed similar but more complicated methods for index-ing subtrees in a minimal, deterministic, bottomup tree automaton.