1.. |<->| unicode:: U+2194 .. left right arrow 2 3Stemming Algorithms 4=================== 5 6Xapian uses the `Snowball Stemming 7Algorithms <https://snowballstem.org/>`_. At present, these support 8Armenian, Basque, Catalan, Danish, Dutch, English, Finnish, French, German, 9Hungarian, Italian, Norwegian, Portuguese, Romanian, Russian, Spanish, Swedish, 10and Turkish. 11 12There are also implementations of Lovins' English stemmer, Porter's 13original English stemmer, the Kraaij-Pohlmann Dutch stemmer, and a 14variation of the German stemmer which normalises umlauts. 15 16We'd like to add stemmers for more languages - see the Snowball site for 17information on how to contribute. 18 19What is a stemming algorithm? 20----------------------------- 21 22A stemming algorithm is a process of linguistic normalisation, in which 23the variant forms of a word are reduced to a common form, for example, 24:: 25 26 connection 27 connections 28 connective ---> connect 29 connected 30 connecting 31 32It is important to appreciate that we use stemming with the intention of 33improving the performance of IR systems. It is not an exercise in 34etymology or grammar. In fact from an etymological or grammatical 35viewpoint, a stemming algorithm is liable to make many mistakes. In 36addition, stemming algorithms - at least the ones presented here - are 37applicable to the written, not the spoken, form of the language. 38 39For some of the world's languages, Chinese for example, the concept of 40stemming is not applicable, but it is certainly meaningful for the many 41languages of the Indo-European group. In these languages words tend to 42be constant at the front, and to vary at the end:: 43 44 -ion 45 -ions 46 connect-ive 47 -ed 48 -ing 49 50The variable part is the `ending`, or `suffix`. Taking these endings 51off is called `suffix stripping` or `stemming`, and the residual part 52is called the stem. 53 54Endings 55------- 56 57Another way of looking at endings and suffixes is to think of the suffix 58as being made up of a number of endings. For example, the French word 59:: 60 61 confirmatives 62 63can be thought of as `confirm` with a chain of endings, 64:: 65 66 -atif (adjectival ending - morphological) 67 plus -e (feminine ending - grammatical) 68 plus -s (plural ending - grammatical) 69 70-atif can also be thought of as -ate plus -if. Note that the addition of 71endings can cause respellings, so -e changes preceding `f` to `v`. 72 73Endings fall into two classes, grammatical and morphological. The 74addition of -s in English to make a plural is an example of a 75grammatical ending. The word remains of the same type. There is usually 76only one dictionary entry for a word with all its various grammatical 77endings. Morphological endings create new types of word. In English -ise 78or -ize makes verbs from nouns (`demon`, `demonise`), -ly makes 79adverbs from adjectives (`foolish`, `foolishly`), and so on. Usually 80there are separate dictionary endings for these creations. 81 82Language knowledge 83------------------ 84 85It is much easier to write a stemming algorithm for a language when you 86are familiar with it. If you are not, you will probably need to work 87with someone who is, and who can also explain details of grammar to you. 88Best is a professional teacher or translator. You certainly don't need 89to have a world authority on the grammar of the language. In fact too 90much expertise can get in the way when it comes to the very practical 91matter of writing the stemming algorithm. 92 93Vocabularies 94------------ 95 96Each stemmer is issued with a vocabulary in data/voc.txt, and its 97stemmed form in data/voc.st. You can use these for testing and 98evaluation purposes. 99 100Raw materials 101------------- 102 103A conventional grammar of a language will list all the grammatical 104endings, and will often summarise most of the morphological endings. A 105grammar, plus a dictionary, are therefore basic references in the 106development of a stemming algorithm, although you can dispense with them 107if you have an excellent knowledge of the language. What you cannot 108dispense with is a vocabulary to try the algorithm out on as it is being 109developed. Assemble about 2 megabytes of text. A mix of sources is best, 110and literary prose (conventional novels) usually gives an ideal mix of 111tenses, cases, persons, genders etc. Obviously the texts should be in 112some sense 'contemporary', but it is an error to exclude anything 113slightly old. The algorithm itself may well get applied to older texts 114once it has been written. For English, the works of Shakespeare in the 115customary modern spelling make a good test vocabulary. 116 117From the source text derive a control vocabulary of words in sorted 118order. Sample vocabularies in this style are part of our Open Source 119release. If you make a small change to the stemming algorithm you should 120have a procedure that presents the change as a three column table: 121column one is the control vocabulary, column 2 the stemmed equivalent, 122and column 3 the stemmed equivalent after the change has been made to 123the algorithm. The effects of the change can be evaluated by looking at 124the differences between columns two and three. 125 126The first job is to come up with a list of endings. This can be done by 127referring to the grammar, the dictionary, and also by browsing through 128the control vocabulary. 129 130Rules for removing endings 131-------------------------- 132 133If a word has an ending, E, when should E be removed? Various criteria 134come into play here. One is the knowledge we have about the word from 135other endings that might have been removed. If a word ends with a 136grammatical verb ending, and that has been removed, then we have a verb 137form, and the only further endings to consider are morphological endings 138that create verbs from other word types. At this level the system of 139endings gives rise to a small state table, which can be followed in 140devising the algorithm. In Latin derived languages, there is a state 141table of morphological endings that roughly looks like this:: 142 143 -IC (adj) -+-> -ATION (noun) 144 +-> -ITY (noun) 145 +-> -MENT (adv) 146 \-> -AT (verb) -+-> -IV (adj) -+-> -ITY (noun) 147 | \-> -MENT (adv) 148 \-> -OR (noun) 149 150 -ABLE (adj) -+-> -ITY (noun) 151 \-> -MENT (adv) 152 153 -OUS (adj) ---> -MENT (adv) 154 155The ending forms take different values in different languages. In 156French, -OR becomes `-eur` (m.) or `-rice` (f.), -AT disappears into 157the infinitive form of a verb. In English, -MENT becomes `-ly`, and 158then one can recognise, 159:: 160 161 -IC-ATION fortification 162 -IC-ITY electricity 163 -IC-MENT fantastically 164 -AT-IV contemplative 165 -AT-OR conspirator 166 -IV-ITY relativity 167 -IV-MENT instinctively 168 -ABLE-ITY incapability 169 -ABLE-MENT charitably 170 -OUS-MENT famously 171 172Trios, -IC-AT-IV etc., also occur, but sequences of length four, 173-IC-AT-IV-ITY and -IC-AT-IV-MENT, are absent (or occur very rarely). 174 175Sometimes the validity of an ending depends on the immediately preceding 176group of letters. In Italian, for example, certain pronouns and pronoun 177groups attach to present participle and infinitive forms of verbs, for 178example, 179:: 180 181 scrivendole = scrivendo (writing) + le (to her) 182 mandarglielo = mandare (to give) + glielo (it to him) 183 184If E is the ending, the possible forms are -andoE, -endoE, -arE, -erE, 185-irE, so E is removed in the context -Xndo or Yr, where X is a or e, and 186Y is a or e or i. See the ``attached_pronoun`` procedure in the Italian 187stemmer. 188 189The most useful criterion for removing an ending, however, is to base 190the decision on the syllable length of the stem that will remain. This 191idea was first used in the English stemming algorithm, and has been 192found to be applicable in the other stemming algorithms too. If C stands 193for a sequence of consonants, and V for a sequence of vowels, any word 194can be analysed as, 195:: 196 197 [C] V C ... V C [V] 198 199where [..] indicates arbitrary presence, and V C ... V C means V C 200repeated zero or more times. We can find successive positions 0, 1, 2 201... in a word corresponding to each vowel-consonant stretch V C, 202:: 203 204 t h u n d e r s t r i c k e n 205 0 1 2 3 4 206 207The closer E is to the beginning of the word, the more unwilling we 208should be remove it. So we might have a rule to remove E if at is after 209position 2, and so on. 210 211Developing the algorithm 212------------------------ 213 214Build the algorithm up bit by bit, trying out a small number of ending 215removals at a time. For each new ending plus rule added, decide whether, 216on average, the stemming process is improved or degraded. If it is 217degraded the rule is unhelpful and can be discarded. 218 219This sounds like common sense, but it is actually very easy to fall into 220the trap of endlessly elaborating the rules without looking at their 221true effect. What you find eventually is that you can be improving 222performance in one area of the vocabulary, while causing a similar 223degradation of performance in another area. When this happens 224consistently it is time to call a halt to development and to regard the 225stemming algorithm as finished. 226 227It is important to realise that the stemming process cannot be made 228perfect. For example, in French, the simple verb endings -ons and -ent 229of the present tense occur repeatedly in other contexts. -ons is the 230plural form of all nouns ending -on, and -ent is also a common noun 231ending. On balance it is best not to remove these endings. In practice 232this affects -ent verb endings more than -ons verb endings, since -ent 233endings are commoner. The result is that verbs stem not to a single 234form, but to a much smaller number of forms (three), among which the 235form given by the true stem of the verb is by far the commonest. 236 237If we define errors A and B by, 238 239- error A: removing an ending when it is not an ending 240- error B: not removing an ending when it is an ending 241 242Then removing -ent leads to error A; not removing -ent leads to error B. 243We must adopt the rule that minimises the number of errors - not the 244rule that appears to be the most elegant. 245 246Irregular forms 247--------------- 248 249Linguistic irregularities slip through the net of a stemming algorithm. 250The English stemmer stems `cows` to `cow`, but does not stem `oxen` 251to `ox`. In reality this matters much less than one might suppose. In 252English, the irregular plurals tend to be of things that were common in 253Anglo-Saxon England: oxen, sheep, mice, dice - and lice. Men, women and 254children are of course common today, but the very commonness of these 255words makes them of less importance in IR systems. Similar remarks may 256be said about irregular verbs in English, the total number of which is 257around 150. Here, the fact that verbs are used perhaps rather less than 258nouns and adjectives in IR queries helps account for the unimportance of 259verb irregularities in IR performance. There are in English more 260significant irregularities in morphological changes such as `receive` 261to `reception`, `decide` to `decision` etc., which correspond, 262ultimately, to irregularities in the Latin verbs from which these words 263derive. But again working IR systems are rarely upset by lack of 264resolution of these forms. 265 266An irregularity of English which does cause a problem is the word 267`news`. It is now a singular noun, and is never regarded as the plural 268of `new`. This, and a few more howlers, are placed in a table, 269``irregular_forms``, in the English stemming algorithm. Similar tables 270are provided in the other stemming algorithms, with some provisional 271entries. The non-English stemming algorithms have not been used enough 272for a significant list of irregular forms to emerge, but as they do, 273they can be placed in the ``irregular_forms`` table. 274 275Using stemming in IR 276-------------------- 277 278In earlier implementations of IR systems, the words of a text were 279usually stemmed as part of the indexing process, and the stemmed forms 280only held in the main IR index. The words of each incoming query would 281then be stemmed similarly. When the index terms were seen by the user, 282for example during query expansion, they would be seen in their stemmed 283form. It was important therefore that the stemmed form of a word should 284not be too unfamiliar in appearance. A user will be comfortable with 285seeing `apprehend`, which stands for `apprehending`, `apprehended` as 286well as `apprehend`. More problematical is `apprehens`, standing for 287`apprehension`, `apprehensive` etc., but even so, a trained user would 288not have a problem with this. In fact all the Xapian stemming algorithms 289are built on the assumption that it leave stemmed forms which it would 290not be embarrassing to show to real users, and we suggest that new 291stemming algorithms are designed with this criterion in mind. 292 293A superior approach is to keep each word, *W*, and its stemmed form, 294*s(W)*, as a two-way relation in the IR system. *W* is held in the index 295with its own posting list. *s(W)* could have its separate posting list, 296but this would be derivable from the class of words that stem to *s(W)*. 297The important thing is to have the *W* |<->| *s(W)* relation. From *W* we 298can derive *s(W)*, the stemmed form. From a stemmed form *s(W)* we can 299derive *W* plus the other words in the IR system which stem to *s(W)*. 300Any word can then be searched on either stemmed or unstemmed. If the 301stemmed form of a word needs to be shown to the user, it can be 302represented by the commonest among the words which stem to that form. 303 304Stopwords 305--------- 306 307It has been traditional in setting up IR systems to discard the very 308commonest words of a language - the stopwords - during indexing. A more 309modern approach is to index everything, which greatly assists searching 310for phrases for example. Stopwords can then still be eliminated from the 311query as an optional style of retrieval. In either case, a list of 312stopwords for a language is useful. 313 314Getting a list of stopwords can be done by sorting a vocabulary of a 315text corpus for a language by frequency, and going down the list picking 316off words to be discarded. 317 318The stopword list connects in various ways with the stemming algorithm: 319 320The stemming algorithm can itself be used to detect and remove 321stopwords. One would add into the ``irregular_forms`` table something 322like this, 323:: 324 325 "", /* null string */ 326 327 "am/is/are/be/being/been/" /* BE */ 328 "have/has/having/had/" /* HAD */ 329 "do/does/doing/did/" /* DID */ 330 ... /* multi-line string */ 331 332so that the words `am`, `is` etc. map to the null string (or some 333other easily recognised value). 334 335Alternatively, stopwords could be removed before the stemming algorithm 336is applied, or after the stemming algorithm is applied. In this latter 337case, the words to be removed must themselves have gone through the 338stemmer, and the number of distinct forms will be greatly reduced as a 339result. In Italian for example, the four forms 340:: 341 342 questa queste questi questo 343 344(meaning `that`) all stem to 345:: 346 347 quest 348 349.. FIXME: Nice idea, but currently these lists are fictitious: 350 In the xapian-data directory in the git repository, each language 351 represented in the stemming section has, in addition to a large test 352 vocabulary, a useful stopword list in both source and stemmed form. The 353 source form, in the file ``stopsource``, is carefully annotated, and the 354 derived file, ``stopwords``, contains an equivalent list of sorted, 355 stemmed, stopwords. 356