# A Hierarchical Orthographic Similarity Measure for Interconnected Texts Represented by Graphs
## 4 Representing a Textual Corpus as a Graph
### Graph Representation of a Textual Corpus
The edit distance is calculated on the ordered list of child nodes of \(n\)

\[\text{child}(n)=K_{n}=[k_{0},k_{1},\dots,k_{m}], \tag{18}\]

where \(k_{j}\in N_{l_{i-1}}\) and \(\rho\big{(}e_{j}\big{)}=\big{(}n,k_{j}\big{)}\), with \(e_{j}\in\text{supp}\big{(}\hat{E}_{\texttt{CONTAINS}}\big{)}\) and \(j=\sigma\big{(}e_{j},\text{rank}\big{)}\). Additionally, the number of children \(m+1\) of \(n\) (i.e., \(|\text{child}(n)|\)) is equal to the number of relationships in \(\hat{E}_{\texttt{CONTAINS}}\) between the node \(n\) and individual elements of \(N_{l_{i-1}}\). #### 5.2.2 Fuzzy Transposition Matching

Another difference is related to how we determine whether or not a transposition between two consecutive elements actually occurs. In contrast to the string-based edit distance, where a transposition between two consecutive characters is detected in case of an exact match, the node-based edit distance identifies a transposition between two

Figure 3: A visual representation of the edit operations required to transform the string RELEVANT into the string ELEVANT. Deletions are indicated in red, replacements in orange, insertions in green and transpositions by crossing arrows. consecutive child nodes by means of a fuzzy match, according to a fixed threshold value \(r\in[0,1]\). Consider two nodes \(n_{1},n_{2}\in N_{l_{i}}\), \(0\leq i<|L|\). A fuzzy match between these nodes occurs when

\[\text{match}(n_{1},n_{2})=\mu_{\tilde{E}}(e)\geq r, \tag{19}\]

with the edge between both nodes \(e\in\tilde{E}_{\texttt{SIMILA\_TO}}\) and \(\rho(e)=(n_{1},n_{2})\). #### 5.2.3 Adaptive Replacement Costs

A third and final distinction from the string-based edit distance lies in how the cost of a replacement between child nodes is determined. In the string-based edit distance, a replacement between two characters has a fixed cost \(c_{R}\). The replacement cost in this node-based edit distance is determined by the dissimilarity between a child node and its replacement. This dissimilarity is acquired by subtracting the similarity between two nodes from 1. Additionally, we propose to introduce a similarity threshold \(t\in[0,1]\) as an additional way to deal with orthographic inconsistencies in a corpus. Before calculating the dissimilarity, the similarity between child nodes is assumed to be fully similar (i.e., a similarity score of 1) when the similarity is greater than or equal to the threshold \(t\). Consider two nodes \(n_{1},n_{2}\in N_{l_{i}},0\leq i<|L|\). The cost of a replacement between these two nodes is determined by the membership function between them

\[c_{R}(n_{1},n_{2})=1-(t\Rightarrow_{Go}\mu_{\tilde{E}}(e)), \tag{20}\]

where \(\rho(e)=(n_{1},n_{2})\) and \(e\in\tilde{E}_{\texttt{SIMILA\_TO}}\). The similarity threshold \(t\) is enforced by means of the Godel R-implication as defined in Equation (21) [49]. \[p\Rightarrow_{Go}q= \begin{cases}1&\text{if }p\leq q\\ q&\text{otherwise}\end{cases}  \tag{21}\]

#### 5.2.4 Node-Based Similarity Calculation

Based on the string-based edit distance, described in Section 5.1, and the adaptations described in the previous sections, a full definition for the node-based edit distance is proposed in Definition 5. This edit distance is computed as the minimum cumulative cost of the edit operations required to transform a text element, represented by its child nodes, into another. **Definition 5** (node-based edit distance). : _Let insertions (I), deletions (D) and replacements (R) of a single node and transpositions (T) between two consecutive nodes be the allowed edit operations. The node-based edit distance between two ordered lists of nodes a and b is recursively defined by the function \(d^{n}_{a,b}(i,j)\), the value of which is the minimum cost between the prefix of a up to the i-th node and the prefix of b up to the j-th node._

\[d^{n}_{a,b}(i,j)=