# 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
In this paper, the edit distance is defined as the minimum cumulative cost of edit operations necessary to transform one string into another. The supported edit operations are the insertion, deletion and replacement of a single character, as well as the transposition between two consecutive characters. A formal definition of this string-based edit distance, which is inspired by the Damerau-Levenshtein distance [8], is provided in Definition 4. Figure 2: A graphical overview of the different steps to calculate the hierarchical similarity measure between textual components in the graph model. Starting from a textual corpus represented by our proposed graph model, a string-based similarity is calculated between the stored texts in the nodes representing the smallest textual components (green section). Next, the pairwise similarity between all other nodes of the same level are hierarchically computed using a node-based similarity measure (red section). As a result, a textual graph is achieved that is extended with similarity scores between all textual components sharing the same unit of discourse. **Definition 4** (string-based edit distance). : _Let insertions (I), deletions (D) and replacements (R) of a single character and transpositions (T) between two consecutive characters be the allowed edit operations. The edit distance between two character strings \(a\) and \(b\) is recursively defined by the function \(d_{a,b}^{s}(i,j)\), whose value is the minimum cost between the prefix of \(a\) up to the \(i\)-th character and the prefix of \(b\) up to the \(j\)



result, the space complexity of a single edit distance calculation is \(\mathcal{O}(\max(|s_{1}|,|s_{2}|))\). The space required to store all calculated similarities between all nodes in \(N_{l_{0}}\) is \(\mathcal{O}(m^{2})\), where \(m\) is equal to the amount nodes at that base level of the hierarchy. Finally, after calculating the similarity scores between all node pairs \((n_{1},n_{2})\), these similarities are also incorporated into the graph. For that purpose, a new fuzzy edge \(e\) is created with label \(\lambda_{E}(e)=\texttt{SIMLAR\_TO}\) for each obtained similarity score. The membership grade for this new edge is equal to the obtained similarity score

\[\mu_{E}(e)=\text{sim}^{s}(\sigma(n_{1},\text{text{text}}),\sigma(n_{2},\text{ text})). \tag{17}\]

This new edge is then associated with the related nodes \(\rho(e)=(n_{1},n_{2})\). Since this similarity measure is symmetric, this edge can be interpreted as an undirected edge and is only stored once. ### Node-Based Similarity Measure

As a next step in the calculation of our proposed similarity measure, we calculate the pairwise similarity scores between higher-level text elements in a hierarchical manner. The hierarchical computation follows the order of the hierarchical decomposition, as presented in Section 4.1, starting with all pairs \((n_{1},n_{2})\in N_{l_{1}}^{2}\). The similarity calculation between all pairs of nodes at the same hierarchical level is repeated for every subsequent level until the similarities between all node pairs \((n_{1},n_{2})\in N_{l_{n}}^{2}\) representing the entire texts are determined. Just like the string-based similarity measure proposed in the previous section, the node-based similarity measure is based on the edit distance principle. In fact, the node-based similarity measure diverges in only three aspects from the edit distance described in Definition 4. #### 5.2.1 Child Nodes Instead of Characters

A first difference compared to the edit distance calculation from the previous section is that the node-based edit distance defines its operations on the nodes in a subgraph rather than considering characters in a string. Consider a node \(n\in N_{l_{i}}\), \(0<i<|L|\).