# 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
Finally, transpositions always have a fixed cost and are the reverse operations of themselves if their fuzzy match operator is symmetric. Because this operator, as stated in Equation (19), is fully determined by the similarity scores at level \(i\), it is also symmetric. By showing that the four edit operations always have a reversed operation with the same cost, it follows that the node-based edit distance and consequently the node-based similarity are symmetric. The calculation of the proposed node-based similarity measure is now illustrated in Example 3. **Example 3**. : _Consider a set of two slightly different texts_

\[T=\{\text{``This is a {test} sentence too.'', ''Is this a {test} sentence?''}\}\text{,}\]

_with a hierarchical decomposition into \(L=[\texttt{{Word}},\texttt{{Sentence}}]\) and a typo for the word \"test\" in the second text. The graph-based text representation for this small corpus is displayed in Figure 4. The relevant similarity scores between words have already been determined. In this example, we assume that the costs for the edit operations, the similarity threshold and the fuzzy match threshold for the node-based edit distance are all set equal to \(1\)._

_To calculate the similarity, it is necessary to first determine the edit distance between the child nodes. Based on the edit operation costs, the minimum edit distance for this example is found by (i) a transposition between the first two nodes, with a cost of \(1\), (ii) a replacement of the word \"test\" with the word \"test\", with a cost equal to the dissimilarity between those words (i.e., \(0.25\)), and (iii) an insertion (or deletion) of the last node, with a cost of \(1\). As a result, the edit distance equals \(2.25\), and the similarity, as per Equation (23), equals \(0.625\)._

_Now imagine another scenario where the similarity threshold \(t\) is \(0.75\) leading to a replacement cost of \(0\) between the words \"test\" and \"test\". Therefore, the similarity score between the two sentences results in \(0.666\ldots\)._

The time complexity of a single node-based edit distance calculation between node \(n_{1}\) and \(n_{2}\) is related to the length of both lists of child nodes and is equal to \(\mathcal{O}(|\text{child}(n_{1})|\cdot|\text{child}(n_{2})|)\). Since the amount of child nodes at any level of the hierarchy depends on the hierarchical decomposition of the considered texts, the execution time can be kept within reasonable bounds by adopting a hierarchical decomposition that results

Figure 4: A visual representation of the two sentences in Example 3. The yellow nodes (with id) represent Sentence nodes, whereas the green nodes (with text) represent the Word nodes. The values of the rank property are shown on the directed edges between different levels of the graph, and the similarity values are indicated on the undirected edges between the same level text elements. Only the relevant similarity scores between word nodes are displayed. in a short list of child nodes. Additionally, much like the string-based similarity measure, the time complexity of calculating the similarities on all nodes in \(N_{l_{i}}\), with \(0<i<|L|\) and \(m\) equal to the amount of nodes in \(N_{l_{i}}\), is \(\mathcal{O}(m^{2})\). The space requirements of the node-based edit distance are equal to the space complexities of the string-based edit distance, as described in Section 5.1, except for the space complexity of a single node-based edit distance calculation, which now relates to the length of two child node lists instead of to the length of two strings. ### Graph-Based Text Model with Similarities

With the various components of our similarity measure in place, we can now describe our proposed hierarchical orthographic similarity measure in full. The procedure for the computation of the similarity values between all text elements, and most importantly between all full texts, is provided in Algorithm 3.