German stemming algorithm

Compound words

Famously, German allows for the formation of long compound words, written without spaces. For retrieval purposes, it is useful to be able to search on the parts of such words, as well as the on the complete words themselves. This is not just peculiar to German: Dutch, Danish, Norwegian, Swedish, Icelandic and Finnish have the same property. To split up compound words cannot be done without a dictionary, and the purely algorithmic stemmers presented here do not attempt it.

We would suggest, however, that the need for compound word splitting in these languages has been somewhat overstated. In the case of German:

1. There are many English compounds one would see no advantage in splitting,

   blackberry

   blackboard

   rainbow

   coastguard

   ....

   Many German compounds are like this,

   Bleistift (pencil)		=		Blei (lead) + Stift (stick)
   Eisenbahn (railway)		=		Eisen (iron) + Bahn (road)
   Unterseeboot (submarine)		=		under + sea + boat

2. Other compounds correspond to what in English one would want to do by phrase searching, so they are ready made for that purpose,

   Gesundheitspflege		=		‘health care’
   Fachhochschule		=		‘technical college’
   Kunstmuseum		=		‘museum of fine art’

3. In any case, longer compounds, especially involving personal names, are frequently hyphenated,

   Heinrich-Heine-Universität

4. It is possible to construct participial adjectives of almost any length, but they are little used in contemporary German, and regarded now as poor style.

History of functional changes to the algorithm

• Snowball 2.0.0 (2009-12-11): Extra rule for -nisse ending added
• Snowball 2.3.0: Handle ASCII transliterations of umlauts (merging the "german2" variant into the standard algorithm).
• Snowball 2.3.0: Special case for -system added.
• Snowball 2.3.0: Replace -ln and -lns with l.
• Snowball 2.3.0: Remove -erin and -erinnen.
• Snowball 2.3.0: Remove -et when safe to do so.

The stemming algorithm

German includes the following accented forms,

ä   ö   ü

and a special letter, ß, equivalent to double s.

The following letters are vowels:

a   e   i   o   u   y   ä   ö   ü

First put u and y between vowels into upper case, and then do the following mappings,

(a) replace ß with ss,
(a) replace ae with ä,
(a) replace oe with ö,
(a) replace ue with ü unless preceded by q.

(The rules here for ae, oe and ue were added in Snowball 2.3.0, but were previously present as a variant of the algorithm termed "german2"). The condition on the replacement of ue prevents the unwanted changing of quelle. Also note that feuer is not modified because the first part of the rule changes it to feUer, so ue is not found.)

R1 and R2 are first set up in the standard way (see the note on R1 and R2), but then R1 is adjusted so that the region before it contains at least 3 letters.

Define a valid s-ending as one of b, d, f, g, h, k, l, m, n, r or t.

Define a valid st-ending as the same list, excluding letter r.

Define a valid et-ending as one of d, f, g, k, l, m, n, r, s, t, U, z or ä.

Do each of steps 1, 2 and 3.

Step 1:

Search for the longest among the following suffixes,

(a) em (not preceded by syst [condition added in Snowball 2.3.0])
(b) ern   er
(c) e   en   es
(d) s (preceded by a valid s-ending)
(e) erin   erinnen [added in Snowball 2.3.0]
(f) ln   lns [added in Snowball 2.3.0]

and if in R1 then delete (for (a) to (e)) or replace with l (for (f)). (Note that only the suffix needs to be in R1, the letter of the valid s-ending is not required to be.)

If an ending of group (c) is deleted, and the ending is preceded by niss, delete the final s.

(For example, äckern → äck, ackers → acker, armes → arm, bedürfnissen → bedürfnis)

Search for the longest among the following suffixes,

(a) en   er   est
(b) st (preceded by a valid st-ending, itself preceded by at least 3 (c) et (preceded by a valid et-ending, itself not preceded any of geordn, intern, plan, tick or tr).

and delete the suffix if in R1.

(For example, derbsten → derbst by step 1, and derbst → derb by step 2, since b is a valid st-ending, and is preceded by just 3 letters)

Search for the longest among the following suffixes, and perform the action indicated.

end   ung

delete if in R2

if preceded by ig, delete if in R2 and not preceded by e

ig   ik   isch

delete if in R2 and not preceded by e

lich   heit

delete if in R2

if preceded by er or en, delete if in R1

keit

delete if in R2

if preceded by lich or ig, delete if in R2

Finally,

turn U and Y back into lower case, and remove the umlaut accent from a, o and u.

The same algorithm in Snowball

/*
    Extra rule for -nisse ending added 11 Dec 2009
*/

routines (
           prelude postlude
           mark_regions
           R1 R2
           standard_suffix
)

externals ( stem )

integers ( p1 p2 x )

groupings ( v et_ending s_ending st_ending )

stringescapes {}

/* special characters */

stringdef a"   '{U+00E4}'
stringdef o"   '{U+00F6}'
stringdef u"   '{U+00FC}'
stringdef ss   '{U+00DF}'

define v 'aeiouy{a"}{o"}{u"}'

define et_ending 'dfgklmnrstUz{a"}'
define s_ending  'bdfghklmnrt'
define st_ending s_ending - 'r'

define prelude as (

    test repeat goto (
        v [('u'] v <- 'U') or
           ('y'] v <- 'Y')
    )

    repeat (
        [substring] among(
            '{ss}' (<- 'ss')
            'ae'   (<- '{a"}')
            'oe'   (<- '{o"}')
            'ue'   (<- '{u"}')
            'qu'   ()
            ''     (next)
        )
    )

)

define mark_regions as (

    $p1 = limit
    $p2 = limit

    test(hop 3 setmark x)

    gopast v  gopast non-v  setmark p1
    try($p1 < x  $p1 = x)  // at least 3
    gopast v  gopast non-v  setmark p2

)

define postlude as repeat (

    [substring] among(
        'Y'    (<- 'y')
        'U'    (<- 'u')
        '{a"}' (<- 'a')
        '{o"}' (<- 'o')
        '{u"}' (<- 'u')
        ''     (next)
    )

)

backwardmode (

    define R1 as $p1 <= cursor
    define R2 as $p2 <= cursor

    define standard_suffix as (
        do (
            [substring] R1 among(
                'em'
                (   not 'syst' // don't remove -em from words ending -system
                    delete
                )
                'ern' 'er'
                'erin' 'erinnen' // conflate female versions of nouns
                (   delete
                )
                'e' 'en' 'es'
                (   delete
                    try (['s'] 'nis' delete)
                )
                's'
                (   s_ending delete
                )
                'ln' 'lns'
                (   <- 'l'
                )
            )
        )
        do (
            [substring] R1 among(
                'en' 'er' 'est'
                (   delete
                )
                'st'
                (   st_ending hop 3 delete
                )
                'et'
                (   test et_ending
                    not among (
                        'geordn' // Still conflate untergeordnet/untergeordnetere, etc.
                        'intern' // Don't conflate Internet and internes.
                        'plan' // Don't conflate Plan and Planet.
                        'tick' // Don't conflate Tick and Ticket.
                        'tr'   // Still conflate Vertreter/Vertretung, etc.
                    )
                    delete
                )
            )
        )
        do (
            [substring] R2 among(
                'end' 'ung'
                (   delete
                    try (['ig'] not 'e' R2 delete)
                )
                'ig' 'ik' 'isch'
                (   not 'e' delete
                )
                'lich' 'heit'
                (   delete
                    try (
                        ['er' or 'en'] R1 delete
                    )
                )
                'keit'
                (   delete
                    try (
                        [substring] R2 among(
                            'lich' 'ig'
                            (   delete
                            )
                        )
                    )
                )
            )
        )
    )
)

define stem as (
    do prelude
    do mark_regions
    backwards
        do standard_suffix
    do postlude
)