# A Hierarchical Orthographic Similarity Measure for Interconnected Texts Represented by Graphs
## 2 Related Work  
A similarity score between two texts can be determined in several ways, including orthographically or semantically [5; 6]. Orthographic similarity is based on the resemblance between individual characters or tokens, without taking into account the meaning of the textual content or making assumptions on the used language [7]. Character-based orthographic methods, like (Damerau-)Levenshtein [8; 9], Jaro-(Winkler) [10; 11] and N-grams [12], determine the distance or similarity between two strings by comparing character sequences. Token-based orthographic methods on the other hand, like the Jaccard Similarity [13], Dice's Coefficient [14], the Cosine Similarity [6], the Overlap Coefficient [6] or even token-based adaptations of character-based methods, calculate a similarity between texts based on a sequence or set of entire tokens. Some of these orthographic techniques result in a distance rather than a similarity score. Since (normalised) distance and similarity are in fact inverse functions, these two types of measurements can be used interchangeably. Both character- and token-based similarity measures calculate the similarity score based on one specific text element, i.e., either tokens or characters. Few techniques have been proposed to combine both types of orthographic similarity measures into one. Such composite techniques, commonly referred to as soft (similarity) measures, consider two tokens to be equal not solely in a case of an exact match but also when the character-based similarity between the two tokens is at least as high as a predefined threshold [4; 5; 15; 16]. In fact, soft token-based measures do not apply an exact (or crisp) matching technique but rather a near (or approximate) matching technique. In the case of name matching for example, the soft cosine similarity, which combines both the cosine similarity and N-grams, outperforms each individual component [17]. Another study shows that leveraging the dissimilarity between two tokens, calculated using a character-based measure as the replacement cost in a soft token-based measure, has a great performance in search applications [18]. In contrast to orthographic similarity measures, semantic similarity measures do rely on the meaning of the textual content as well as assumptions made about the language in which the text is written. Semantic measures can be corpus-based, knowledge-based or a combination of both [19]. Corpus-based measures calculate a similarity value based on information obtained from analysing large corpora. In Latent Semantic Analysis (LSA) [20], for instance, a token-paragraph matrix is constructed to indicate the frequency of a specific token's usage in a given paragraph. Based on this matrix and the assumption that contextually similar tokens will occur in related pieces of text, a token vector is determined. Finally, the similarity score between two tokens is determined by computing the cosine of the angle between their respective token vectors. Other corpus-based techniques like Word2 vec [21] and Pairwise Mutual Information (PMI) [22] are based on the same principles. Knowledge-based methods on the other hand determine a similarity score between texts by utilising information derived from semantic networks. These semantic networks are large lexical databases that store semantic relations between their contents. In the case of the English language, WordNet [23] is one of the most popular semantic networks available. Consider the depth of a word as the number of semantic links between the root word of WordNet and that specific word. A possible method to determine a similarity score between two words is based on the depth of both words and the depth of their lowest common ancestor [24]. Since semantic methods rely on specific (large) corpora and/or on assumptions about a particular language, their applicability is limited, making them less general than orthographic measures.