The paper presents an unsupervised and knowledge-free approach to compound splitting. Although the research is focused on German compounds, the method is expected to be extensible to other compounding languages. The approach is based on the annotated suffix tree (AST) method proposed and modified by Mirkin et al. To the best of our knowledge, annotated suffix trees have not yet been used for compound splitting. The main idea of the approach is to match all the substrings of a word (suffixes and prefixes separately) against an AST, determining the longest and sufficiently frequent substring to perform a candidate split. A simplification considers only the suffixes (or prefixes) and splits a word at the beginning of the selected suffix (the longest and sufficiently frequent one). The results are evaluated by precision and recall.
The Germanic languages, in particular German, often use a large number of compounds, i.e. words consisting of several parts. Such word combinations result in larger vocabulary. Moreover, the word base may eventually expand further even without the formation of completely new words, only through compounding the existing ones.
This especially complicates machine translation and search engine development. For examlpla, without compound splitting it is necessary to store all the words Sommer (summer ), Winter (winter ), Wetter (weather ), Märchen (fairy tale), Sommerwetter (summer weather ), Winterwetter (winter weather ), Wintermärchen (winter’s tale) to translate them correctly. In contrast, a system equipped with compound splitting tool needs only four words (Sommer, Winter, Wetter, Märchen) to represent the entire group. What is more, such system will easily translate the previously unseen word, Sommermärchen. In terms of search engines, compounds prevent search result diversity. For instance, to find results containing Regenmantel (raincoat ) by query Regenschirm (umbrella) it is useful to split the compounds as well.
Section 2 reviews different approaches to this problem. Due to the space limitation, the review is brief and incomplete yet sufficient to provide a general outline of the problem. Section 3 introduces the proposed algorithm for compound splitting. Section 4 is devoted to the experiment results. Section 5 concludes.
This paper combines two aspects: German compound splitting and annotated suffix tree method. To correctly split a compound, it is necessary to study both areas. 2.1
In [
The work [
However, as mentioned in [
Building upon previous research, F. Holz and C. Biemann [
Next, the authors improve the results by introducing periphrase detection. They illustrate the idea with an example: Schweine-schnitzel is a pork cutlet, while Kinder-schnitzel means a cutlet for children. Despite the same structure, the meanings are strictly different. To avoid terminological ambiguities, the authors look for periphrases in the source text. Given that periphrases contain different prepositions (Schnitzel vom Schwein and Schnitzel für Kinder ), the authors include the prepositions into splits and thus facilitate understanding. This approach however goes beyond the scope of our paper.
One more alternative approach is described in [
Moving on to the annotated suffix trees, the paper [
The paper [
To avoid terminological ambiguities, we use the term “annotated prefix tree” (APT) to denote an annotated suffix tree constructed from the inverted words. For instance, the prefixes of Zeit (time) are represented in an annotated tree as the suffixes of a dummy word tieZ, namely, Z, eZ, ieZ, tieZ. The examples of both AST and APT created from word Freizeit (free time) are illustrated on Fig.1 (left and right respectively).
Now we describe our algorithm in details. At the current stage, it aims to split the simplest compounds formed by a direct connection of two words. Thus, we consider such compounds as Kraftwerk (power station), which is formed by Kraft (power ) and Werk (factory ), but avoid the more complex ones: Kleidungsstück (item of clothing ) which includes not only Kleidung (clothing ) and Stück (item) but also a connecting letter s, or Kirchturm (church steeple), which omits the letter e from the word Kirche (church). Further development of the algorithm should address the difficulties mentioned above as well as splitting the words formed from more than two parts.
Therefore, the algorithm is as follows: Step 1. Create an AST and an APT from a large raw list of (compound) words. Step 2. For each suffix (prefix) of each word to be split, determine the frequency from the AST (APT). The frequency of a suffix (prefix) is defined by the frequency of the corresponding leaf, that is, the last element of the suffix (prefix) in the AST (APT). Then pick the longest suffix (prefix) with frequency above a certain cutoff value. For our evaluation set, the optimal cutoff frequencies are calculated as the geometric mean of the suffix and prefix frequencies divided by the multiplication of the suffix and prefix lengths. The next step can be done in two ways.
Step 3a. The compound is split using either the AST or the APT. The suffix obtained at the previous step is proposed as the second part of the compound, and the remainder becomes the first one. The case of prefix splitting (using APT) is handled similarly.
Step 3b. AST and APT results are handled jointly, producing a combined split. Since in Step 3a prefix splitting shows better results, it is applied in most cases. However, if the frequency of the prefix obtained from prefix splitting is lower than that of every part of suffix splitting, the latter is selected.
The Step 3b is justified by the experiment presented in the following section. However, even without particular experiments the superior results of prefix splitting can be explained from a linguistic point of view. German has a fixed set of common word endings. Let us proceed with an example: if two words which share an ending (e.g. Sommer and Winter ) are the prefixes of some compounds with the same second part (Sommerwetter and Winterwetter ), the frequency of the erroneous suffix (erwetter ) increases. That may lead to wrong suffix splitting, but does not affect the prefix frequencies.
In the next section, we present the results produced by an implementation of the three options (prefix, suffix and combined splitters) and evaluate these by precision and recall. 4
To build AST and APT we use a list from Wiktionary, Category: German compound words. It consists of 7144 words, but we use 6740 of them with welldescribed etymology. An example of well-described etymology is, for Apfelblüte (apple blossom), Apfel + Blüte. Availability of etymology has no effect on splitting quality, but allows checking its correctness.
Since the algorithm only handles two-part compounds with no connecting letters, the experiment is conducted on an appropriate 4619-word subset of the original list. The split may consist of one part, which makes it unsuccessful. However, in presence of non-compounds this might be the correct answer; such cases should be taken into account when calculating precision. Precision is measured as the ratio of number of correct determined splits to number of all words which splits were found. The numerator of recall is the same while the denominator is the number of all compounds in the evaluating set.
The splitting examples of two different words are shown in Table 1. Using AST provides precision and recall of about 48%, while using APT improves these to 57%. The combined method further improves precision and recall up to 63%. It is also necessary to point out that in 78% of the cases at least one split (obtained either by AST or APT) is correct. That means that if the algorithm contains a manual post-processing component, we would have easily reached such value. 5
In this paper, we have proposed an algorithm for compound splitting based on the annotated suffix tree method. Precision and recall of more than 60% provide a good starting point. With manual post-processing precision can reach 78%, which suggests a prospective direction of further work if automating of the heuristics is applied.
At the current stage, the algorithm only splits simple compounds, which account for two-thirds of the total Wiktionary list. A minor modification of the algorithm should allow it to handle connecting letters or an independent third (middle) stem. However, such modifications have not been implemented yet. Additionally, the extensions may consider the more advanced cases, such as the removal of certain ending letters from the parts in compounds.
Finally, it is also necessary to carry out the experiments on other word lists, containing non-compounds, both at tree-construction and splitting stages.