# 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
Moreover, the texts undergo preprocessing involving the removal of punctuation and the transformation of uppercase letters into lowercase letters._```
1:procedureComputeChildNodes(\(t,i,p\))
2:\(S\leftarrow\textsc{Split}(t,i)\)\(\triangleright\) Text splitting is based on the current discourse unit
3:for\(j\gets 0,|S|-1\)do
4:if a node already exists on level \(i\) that represents \(s_{j}\)then
5: Define that existing node as \(n\)
6:else
7: Create node \(n\)
8:\(\lambda_{N}(n)\leftarrow\{l_{i}\}\)
9:if\(i>0\)then
10: ComputeChildNodes(\(s_{j},i-1,n\))
11:else
12:\(\sigma(n,\text{text})\gets s_{j}\)
13:endif
14:\(N\gets N\cup\{n\}\)
15:endif
16: Create edge \(e\)
17:\(\rho(e)\leftarrow(p,n)\)
18:\(\sigma(e,\text{rank})\gets j\)
19:\(\lambda_{E}(e)\leftarrow\textsc{CONTAINS}\)
20:\(\tilde{E}\gets E\cup\{e\}\)
21:\(\mu_{\tilde{E}}(e)\gets 1.0\)
22:endfor
23:endprocedure
```

**Algorithm 2** Recursive procedure to construct the different levels of the graph model. The first sentence of both texts (left) is represented by a single sentence node, signifying that both (preprocessed) sentences are orthographically identical. The second sentence on the other hand, differs by two words, resulting in a distinct sentence node for each text. In fact, when both texts consist of orthographically identical words, the graph's structure inherently provides an indication of the similarity between the texts. Figure 1: A graph-based text representation for the texts in Example 1. Word nodes are indicated in green and display their text property, whereas Sentence nodes are indicated in yellow, and Text nodes, including their numeric id property, are indicated in blue. The values of the rank property are displayed on the edges. Additional text documents can still be included into the graph after its initial construction. This can simply be achieved by re-executing Algorithm 1, with the set \(T\) consisting of one or more new text documents, and instead of creating a new graph, the algorithm should use the already constructed graph \(\tilde{G}\). ## 5 A Hierarchical Orthographic Similarity Measure for Graph-Based Text Representations

Now that a graph model is in place, representing an entire textual corpus, we propose a novel hierarchical orthographic similarity measure for these graph-based text representations. Analogous to the construction of the textual graph, as proposed in Section 4.2, the hierarchical computation is performed in a bottom-up manner. In Section 5.1, we first propose a string-based similarity measure that computes a pairwise similarity between all nodes representing the smallest textual components in the graph. Next, in Section 5.2, we propose a node-based similarity measure, where a similarity score is hierarchically determined between all nodes situated at the same level. This is achieved by utilising the similarity values between lower-level nodes, calculated in a preceding step. As a result, the graph model for texts is extended with relationships that denote the similarity between all text elements at the same level and between the full texts in the corpus. In Section 5.3, we describe the full computation of our proposed similarity measure and revisit our example from the previous section. A graphical overview of the proposed similarity measure is provided in Figure 2.

### String-Based Similarity Measure

A first step in the hierarchical calculation of the proposed similarity measure consists of calculating the pairwise similarity between all nodes that represent the smallest textual components in the graph. Since these nodes actually contain textual content, a string-based similarity measure is employed. As a similarity measure, we propose a character-based method that is based on the edit distance between two strings. Calculating this pairwise similarity measure between all lowest-level node pairs, \((n_{1},n_{2})\in N_{l_{0}}^{2}\) starts by determining the edit distance between the texts contained by those nodes.