User:TJones (WMF)/Notes/Slovak Stemmer Analysis

From MediaWiki.org
Jump to navigation Jump to search

March 2018 — See TJones_(WMF)/Notes for other projects. See also T178929. For help with the technical jargon used in the Analysis Chain Analysis, check out the Language Analysis section of the Search Glossary.

Intro—Of Licenses and Code[edit]

After my experience with Serbian, I decided to begin with a closer review of the licensing and code quality of the potential stemmers.

I had previously identified (see T178929) two potential stemmer candidates. (Note that Czech comes up a lot in the following discussion because Czech and Slovak are quite similar. Czech stemming is readily adaptable to Slovak stemming.) The two candidate stemmers are:

  • stemm-sk: written in Python, MIT License, adapted from a Czech stemmer in Python that was adapted from a Czech stemmer written in Java.
  • Stemmer-sk: written in Java, wrapped into a Lucene analyzer, with a confusing license situation.
    • The license information in the README says you can chose from Affero GPL3, CC BY-SA 4.0 International, or GNU Free Documentation License 1.3, but the License.txt file seems to be a screen-scrape of a GitHub page for a different repo by the same user, and includes the text of GPLv2+, LGPLv2+, Mozilla Public License 1.1, CC BY-SA 4.0 International, GNU Free Documentation License 1.3.
    • The code claims to be based on a paper called "Indexing and stemming approaches for the Slovak language", but I think that's global replace error. The Lucene Czech stemmer is very similar, especially after a global replacement of Czech with Slovak (including being based on the paper "Indexing and stemming approaches for the Czech language"). It is not clear to me (I am not a lawyer) that the code is properly licensed from the Lucene repo (which is Apache 2.0).

It turns out that both stemmers eventually go back to the same paper on Czech stemming, which points to the website of one of the authors, which includes "light" and "aggressive" versions of the Czech stemmer, licensed under the BSD license.

The stemming algorithm itself is very straightforward, largely consisting of stripping suffixes, with some minimal normalization after removal of some suffixes (in a function called "palatalise()" in the original implementation and Python implementation).

All of the implementations seem unnecessarily inefficient to me. They all take substrings of the word to be stemmed and compare them to lists of suffixes. Some take the same substring of the word repeatedly, which seems particularly inefficient. (The Lucene Czech stemmer does that, too, so I guess we're using that for the Czech-language wikis.) (UPDATE: A linguistically interesting but computationally annoying detail is that suffixes of the same length can differ not only in whether the stem gets normalized after removal, but also in how much of the suffix gets removed. There's some pattern—suffixes that get partially removed are the ones that get normalized—but it makes it hard to find a single simple generalization for everything. The Python implementation is looking more reasonable.)

It seems straightforward to take the Czech-to-Slovak converted suffixes from the Python implementation (with the MIT License) and re-implement it in a more efficient manner in Java, for use in a Elasticsearch stemmer in the search/extra plugin (with the Apache 2.0 License).

Data[edit]

I created corpora of 10,000 Slovak Wikipedia articles and 10,000 Slovak Wiktionary entries as test data. I removed extra markup and deduplicated individual lines (to reduce the number of instances of the wiki-specific words, such as the equivalent of "References", "See also", "Noun", etc.)

The Wiktionary corpus has 60,893 tokens and 26,372 pre-analysis types in it. The Wikipedia corpus has 1,611,909 tokens and 221,174 pre-analysis types in it.

Note that types refer to unique tokens (in English, the only counts once), and tokens refer to all instances of a word (so, the would count many, many times).

Side Quest: Tools Update[edit]

For Serbian I used Elasticsearch to tokenize my corpora, and then processed unique tokens with the stemmer. I wrote a little script to convert the results into the output format that my analysis chain analyzer uses, but all token counts became 1, since there was only one instance of each unique token.

Since I'm hoping to repeat this process, I've updated my analyzer analysis tools to tokenize and normalize (e.g., lowercase and/or ICU normalize) an input corpus using Elasticsearch and generate a file with one unique token per line (e.g., "music"), which can be fed to a stemmer, and a separate file with original token count information on corresponding lines (e.g., "MUSIC 2 Music 3 muSIC 1 music 32"). Most stemmers I've worked with are able to generate an output file also with one token per line for such input—and if one couldn't it can probably be coerced into doing so. I've also updated my tools to merge the one-token-per-line stemmed file and original token count file into the normal analyzer analysis output format, to go back into the normal analysis analysis flow.

Changes are in review.

Prefixes[edit]

I noticed that Stemmer-sk also stripped the prefix naj-, which looks to be cognate with Polish naj-, which I'd encountered when working with the Stempel analyzer. naj- is used to mark the superlative in Slovak (and Polish), and is roughly equivalent to -est in English. Stempel strips a number of other prefixes as well (see the link above, they have rough meanings of -less, anti-, super- and un-), most of which are acceptable, but not ideal for stemming in my mind.

I checked Wiktionary for Slovak prefixes and found only three, including bez- (which looks to be cognate with Polish bez-; both mean un-). French Wiktionary has a more complete list, but most are numerical (meaning uni-, bi-, or metric prefixes). The others don't seem like great candidates to me: meaning inter-, un-, and under-).

Out of all of them, naj- seems like it is worth testing (we would certainly want -est to be stripped in English if it didn't cause too many false positives), so I'll include a separate batch of stemmed groups that show up when stripping naj- as a prefix in my list of groups for speaker review.

Comparison Plan[edit]

I'm using the light stemmer as the baseline, as it is literally the least stemming we can do, and I'll compare differences between the light stemming and adding stripping the naj- prefix, and between the light stemming baseline and aggressive stemming.

Stemming Groups for Review[edit]

Below are some stemming groupings for review by speakers of Slovak. These are tokens that would be indexed together, so searching for one would find the others. The format is <stemmed_form> - [<count> <token>][<count> <token>].... The <stemmed_form> is the internal representation of all the other tokens. It's sometimes meaningful, and sometimes not, depending on the tokens being considered. The <token> is a token found by the language analyzer (more or less a word) and <count> is the number of times it was found in the sample. While accuracy is important, frequency of errors also matters. Some errors are expected, because language is messy.

Largest Groups (Light Stemmer)[edit]

These are the largest groups from the Wikipedia and Wiktionary corpora. They aren't necessarily bad, but some errors sometimes show up in the largest groups. The most common problem is a group that is two or more words that have overlapping forms. In English, this might be something like do and doe being in the same group because they both share the form does. Problems can also come from names that get stemmed.

The first 8 groups are groups from Wikipedia with more than 20 words in the group. The next 6 are groups from Wiktionary with 10 or more items in the group. The druh and rusk groups appear in both.

Wikipedia:

  • druh - [6 Druh][14 Druhej][6 Druhou][2 Druhovo][3 Druhové][6 Druhy][54 Druhá][18 Druhé][5 Druhého][10 Druhú][51 Druhý][14 Druhým][2 Družina][249 druh][2 druha][436 druhej][27 druhmi][1 druho][141 druhom][53 druhou][237 druhov][1 druhovej][3 druhovo][1 druhovom][1 druhové][1 druhovému][1 druhovú][1 druhový][145 druhy][113 druhá][72 druhé][105 druhého][12 druhému][5 druhí][50 druhú][216 druhý][21 druhých][64 druhým][2 druhými][4 družina][3 družine][1 družinou][7 družiny][1 družinám]
  • horn - [7 Horn][1 Horne][14 Hornej][1 Hornina][10 Horniny][9 Hornom][1 Horny][90 Horná][43 Horné][22 Horného][1 Hornému][27 Horní][1 Horních][1 Horního][10 Hornú][14 Horný][2 Horných][2 Horným][1 horn][1 horne][46 hornej][12 hornina][25 horninami][2 hornine][2 horninou][1 horninové][51 horniny][11 horninách][38 hornom][5 hornou][12 horná][13 horné][10 horného][1 horní][7 hornú][19 horný][11 horných][6 horným]
  • list - [38 List][3 Lista][3 Liste][5 Listina][1 Listiny][1 Listom][1 Listov][1 Listový][21 Listy][58 list][1 lista][18 listami][12 liste][13 listina][23 listine][19 listiny][8 listinách][1 listinám][7 listoch][3 listom][47 listov][5 listovej][1 listovom][1 listovou][2 listová][7 listové][2 listového][1 listovému][1 listovú][2 listových][1 listovým][5 listovými][61 listy]
  • nov - [2 NOV][6 NOVA][1 NOVY][1 NOVÁ][10 Nov][30 Nova][1 Nove][142 Novej][6 Novi][4 Novo][93 Novom][6 Novou][187 Nová][182 Nové][79 Nového][2 Novému][3 Noví][28 Novú][138 Nový][20 Nových][10 Novým][2 nov][1 nova][126 novej][33 novo][37 novom][24 novou][2 novus][1 novy][83 nová][264 nové][166 nového][16 novému][6 noví][1 novích][82 novú][207 nový][161 nových][59 novým][22 novými][3 novším]
  • ostr - [2 Ostrej][2 Ostro][4 Ostrom][1 Ostrou][38 Ostrov][1 Ostrova][4 Ostrove][1 Ostrovom][10 Ostrovy][6 Ostrá][4 Ostré][3 Ostrého][1 Ostrému][1 Ostrú][12 Ostrý][2 ostrej][23 ostro][3 ostrou][191 ostrov][112 ostrova][131 ostrove][17 ostrovmi][30 ostrovoch][22 ostrovom][87 ostrovy][5 ostrá][21 ostré][1 ostrého][5 ostrí][4 ostrú][5 ostrý][6 ostrých][1 ostrým][3 ostrými]
  • ran - [3 Ran][1 Rana][1 Rances][1 Rany][1 Raná][1 Rané][2 Raní][3 Raný][1 ran][5 rana][4 ranami][2 rane][11 ranej][11 ranom][4 ranou][1 ranové][5 rany][6 raná][2 ranách][1 ranám][8 rané][10 raného][1 ranému][1 raní][2 ranú][21 raný][17 raných][3 raným][2 ranými]
  • rusk - [77 Ruska][63 Ruskej][1 Ruski][113 Rusko][21 Ruskom][1 Ruskou][8 Ruskov][1 Ruskova][3 Rusky][29 Ruská][17 Ruské][14 Ruského][3 Ruskému][1 Ruskí][1 Ruskú][5 Ruský][4 Ruským][1 Ruština][76 ruskej][13 rusko][19 ruskom][4 ruskou][43 rusky][32 ruská][30 ruské][51 ruského][2 ruskému][4 ruskí][3 ruskú][151 ruský][37 ruských][9 ruským][6 ruskými][9 ruština][9 ruštine][1 ruštinou][13 ruštiny]
  • svet - [18 Svet][1 Sveta][1 Svete][5 Sveti][26 Svetovej][8 Svetovom][1 Svetovou][22 Svetová][13 Svetové][27 Svetového][5 Svetovú][50 Svetový][6 Svetových][106 svet][1324 sveta][314 svete][2 svetmi][2 svetoch][23 svetom][5 svetov][378 svetovej][8 svetovo][29 svetovom][22 svetovou][1 svetovy][30 svetová][17 svetové][72 svetového][1 svetovému][19 svetovú][35 svetový][55 svetových][12 svetovým][4 svetovými][5 svety]

Wiktionary:

  • anglick - [1 Anglicka][1 Anglicko][1 Anglicky][1 Angličtiny][1 anglicky][1 anglická][5 anglické][4 anglického][1 anglický][2 anglickým][1 angličtin][16 angličtina][1 angličtine][1 angličtiny]
  • druh - [36 druh][3 druhej][1 druhom][1 druhov][1 druhová][1 druhy][5 druhá][1 druhé][1 druhého][1 druhému][1 druhú][1 druhý]
  • ktor - [1 Ktoré][9 ktorej][4 ktorom][2 ktorou][16 ktorá][26 ktoré][7 ktorého][1 ktorí][4 ktorú][41 ktorý][2 ktorým]
  • mal - [1 Mal][2 Mali][1 Malých][2 mal][1 mala][1 mali][1 malou][2 malá][4 malé][1 malého][1 malú][12 malý]
  • rusk - [1 Ruskej][1 Rusko][1 Ruská][1 Ruština][1 ruskej][1 ruskom][2 ruské][3 ruského][1 ruský][1 ruským][1 ruštin][8 ruština]
  • slovensk - [3 Slovenska][1 Slovenskej][1 Slovensko][1 Slovenská][1 Slovenské][1 Slovenského][16 slovenskej][1 slovenskom][1 slovensky][4 slovenská][3 slovenské][7 slovenského][5 slovenský][2 slovenským][7 slovenština]

Random Groups (Light Stemmer)[edit]

Below are 20 random groupings each from Wikipedia and Wiktionary. These are more representative of typical words.

Wikipedia:

  • adal - [1 Adala][1 adal]
  • exekučn - [1 exekučnom][1 exekučný]
  • félix - [21 Félix][7 Félixa][1 Félixovi]
  • jakob - [9 Jakob][1 Jakoba][1 jakoby]
  • kadeš - [1 Kadeš][1 Kadeša]
  • komponovani - [1 Komponovanie][1 komponovania][1 komponovanie]
  • lott - [1 Lotta][1 Lotte][1 Lotti][1 Lotto][1 Lottova][1 Lottove]
  • luccask - [3 Luccaskom][2 Luccaskou][2 Luccaské][2 Luccaského][1 Luccaský]
  • mia - [2 MIA][4 Mia][116 Miami][4 mia]
  • mohyl - [1 Mohyly][1 mohylami][1 mohylovej][2 mohylová][3 mohyly]
  • monografi - [1 Monografia][2 Monografie][6 monografia][3 monografie][1 monografii][3 monografií]
  • najdôležitejši - [2 Najdôležitejšia][7 Najdôležitejšie][3 najdôležitejšia][20 najdôležitejšie]
  • obytn - [1 Obytné][1 Obytný][4 obytnej][1 obytnom][3 obytnou][4 obytná][9 obytné][2 obytného][9 obytný][9 obytných]
  • opisuj - [5 Opisuje][19 opisuje][9 opisujú]
  • ragby - [2 ragbyovej][3 ragbyová]
  • religion - [5 Religion][1 Religione][2 religion]
  • sopdu - [4 Sopdu][2 Sopdua]
  • štart - [25 Štart][56 štart][25 štarte][20 štartom][1 štartov][1 štartovej][1 štartovom][2 štartové][1 štartového][1 štartovú][4 štarty]
  • stoker - [2 Stokera][1 Stokerovi][1 Stokerovým]
  • sulc - [1 sulcata][1 sulcus]

Wiktionary:

  • bakteriológi - [1 bakteriológia][1 bakteriológii][1 bakteriológiou]
  • brokát - [1 brokát][1 brokátom]
  • fak - [2 Face][2 face][3 fak]
  • fakult - [2 fakulta][1 fakulty][1 fakultách]
  • hrdzav - [1 hrdzavá][2 hrdzavý]
  • korózi - [1 korózia][1 korózii][1 koróziou]
  • mil - [1 mil][1 milý]
  • morč - [1 morča][1 morčí]
  • mužsk - [1 mužsky][4 mužské][66 mužského][1 mužskému][25 mužský][2 mužských]
  • neživotn - [1 neživotné][9 neživotný]
  • nórk - [1 Nórka][1 nórčina]
  • obr - [1 obr][1 obrat]
  • písmen - [3 písmen][18 písmeno][1 písmená]
  • prechodn - [1 prechodne][1 prechodné][1 prechodný]
  • sľud - [1 sľuda][1 sľudy]
  • španielsk - [1 Španielska][2 Španielsko][1 španielsky][2 španielské]
  • spojen - [6 Spojené][1 Spojených][1 spojená][3 spojených]
  • súvisl - [1 súvisle][3 súvislý]
  • zdrevnaten - [1 zdrevnatenou][1 zdrevnatené]
  • zlat - [1 zlato][3 zlatá][4 zlatý]

naj--stripping[edit]

Stripping naj- (from words of 6 letters or more) only caused new mergers for 0.082% of types and 0.013% of tokens in the Wiktionary corpus. In the Wikipedia corpus, it caused new collisions in 1.279% of types but only 0.154% of tokens, and splits on a very small 0.011% of types and 0.015% of tokens. So the effect size is pretty small, but not entirely trivial.

Below are a semi-random sample (approximately every 10th) of 15 Wikipedia groups with a word that has had naj- stripped off, followed by all 4 examples from the Wiktionary corpus.

Wikipedia:

  • bohatš - [1 Najbohatší][1 bohatšej][1 bohatšou][1 bohatší][1 bohatších][3 najbohatší][8 najbohatších]
  • efektívnejš - [1 efektívnejšej][1 efektívnejší][1 najefektívnejšou]
  • horši - [1 Horšie][2 Najhoršie][4 horšia][13 horšie][2 najhoršia][4 najhoršie]
  • južnejš - [1 Najjužnejší][1 južnejších][3 najjužnejšej][1 najjužnejšom][7 najjužnejší][3 najjužnejších]
  • lep - [1 LEP][1 Lep][1 Lepus][4 Najlepším][5 lepším][30 najlepším]
  • modernejši - [1 modernejšia][5 modernejšie][1 najmodernejšie]
  • prepracovanejš - [1 najprepracovanejších][1 prepracovanejšími]
  • rýchlejši - [1 Najrýchlejšie][1 najrýchlejšia][14 najrýchlejšie][8 rýchlejšia][45 rýchlejšie]
  • smutnejš - [1 najsmutnejších][1 smutnejší]
  • talentovanejš - [2 najtalentovanejších][2 talentovanejší]
  • vyšš - [1 Najvyššej][4 Najvyššom][1603 Najvyšší][1 Najvyššími][5 Vyššej][1 Vyššom][3 Vyšší][108 najvyššej][14 najvyššom][24 najvyššou][73 najvyšší][25 najvyšších][7 najvyššími][44 vyššej][5 vyššom][20 vyššou][31 vyšší][36 vyšších][7 vyššími][1 vyššý]
  • výkonnejši - [1 Najvýkonnejšie][1 najvýkonnejšia][2 najvýkonnejšie][2 výkonnejšia][1 výkonnejšie]
  • známejši - [2 Najznámejšia][9 Najznámejšie][13 najznámejšia][33 najznámejšie][3 známejšia][2 známejšie]
  • ďal - [3 najďalej][104 Ďalej][51 Ďalším][303 ďalej][58 ďalším]
  • ťažš - [1 najťažší][4 najťažších][1 najťažšími][1 ťažšou][1 ťažší][3 ťažších]

Wiktionary:

  • dôležitejši - [1 dôležitejšie][1 najdôležitejšia]
  • men - [2169 mena][2 menej][22 meno][2 menom][4 mená][1 menách][1 mení][2 najmenej]
  • menš - [1 menšina][1 menší][1 menších][1 najmenší‎]
  • väčš - [4 najväčší][3 väčšina][1 väčšine][1 väčšinou][3 väčší]
Improved naj- stripping[edit]

Update: I made an error when originally producing the list above. I stripped naj- from existing stemmed forms. However, because of the minimum length requirements, stripping naj- first prevents some other stemming from happening. None of the originally sampled groups above changed. However, for example, the group "[1 Najatý][3 najatí][2 najatý][3 najatých][1 najatým]"—which were previously stemmed to najat—got mostly split up into smaller words (atý, atí, atý, atých, atým) because after naj--stripping they are too short to be stemmed. This wouldn't change our sample above, but the difference was worth noting.

These small changes could be an argument for stripping naj- after other stemming takes place, rather than before.

pod- stripping[edit]

At the suggestion of Oldknee I looked into stripping the prefix pod-, which means something like "under-" or "sub-". (See the related Czech form on the English Wiktionary or the Slovak form on the French Wiktionary.)

As with naj- I had a minimum token length of 6 to allow the prefix to be removed, and prefix removal happened as the first step in stemming. (Since all of the stemming steps have minimum lengths, the order makes a difference for shorter words. Removing the prefix can prevent any other stemming. Or, if stemming happens first, it could prevent removing the prefix.)

Stripping pod- (from words of 6 letters or more) only caused new mergers for 0.019% of types but a much larger 3.273% of tokens in the Wiktionary corpus. In the Wikipedia corpus, it affected 0.765% of types and 0.459% of tokens.

Below are a the three groups in the Wikipedia corpus that were broken up by stripping pod- (shorter words remain in the group, longer ones leave the group), a sample of 20 random Wikipedia groups with new tokens after stripping pod-, and all 13 Wiktionary groups with new tokens after stripping pod-.

Wikipedia - broken up groups:

  • pod - [1 POD][135 Pod][1437 pod][3 podá] lost [4 podnes]
  • podal - [1 Podal][17 podal] lost [1 Podala][7 podala][3 podali][1 podalo]
  • podob - [1 podob] lost [1 Podoba][1 Podobou][1 Podoby][1 Podobá][34 podoba][122 podobe][9 podobou][40 podoby][15 podobá][5 podobách]

Wikipedia - new merged groups:

  • cast - [1 Casta][2 Castres] added [1 podcast][1 podcastom][1 podcastová]
  • čeľad - [1 čeľad][131 čeľade][3 čeľadi][5 čeľadí] added [14 podčeľade][1 podčeľadi][1 podčeľadí]
  • chyten - [2 chyteného][2 chytení][3 chytený][1 chytených] added [1 podchytená]
  • disciplín - [3 Disciplína][19 disciplín][20 disciplína][1 disciplínami][26 disciplíne][8 disciplínou][34 disciplíny] added [1 poddisciplíny]
  • drobnejši - [1 drobnejšie] added [1 poddrobnejšie]
  • hladin - [2 hladinových][1 hladinovým] added [1 Podhladinová][5 podhladinovom]
  • hor - [23 Hor][61 Hora][1 Horbes][23 Hore][1 Hori][13 Horom][1 Horos][5 Horou][1 Horovi][1 Horses][33 Hory][2 Horách][2 hor][29 hora][6 horami][66 hore][2 horou][72 hory][30 horách][1 horám][4 horí] added [1 Podhore][4 podhorí]
  • ještědsk - [2 Ještědsko] added [4 Podještědská]
  • les - [3 LES][118 Les][2 Lesom][8 Lesy][156 les][32 lesa][22 lese][7 lesmi][25 lesoch][9 lesom][39 lesy] added [4 Podlesí]
  • okenn - [3 okenné][6 okenných] added [1 podokenná]
  • písal - [12 Písal][3 Písala][40 písal][17 písala][10 písali][5 písalo] added [3 Podpísal][1 Podpísali][82 podpísal][21 podpísala][26 podpísali][8 podpísalo]
  • program - [95 Program][1 Programom][2 Programová][4 Programy][123 program][4 programami][48 programe][9 programoch][24 programom][41 programov][8 programovej][1 programovo][1 programovom][1 programová][3 programové][1 programovému][1 programovú][1 programových][46 programy] added [1 podprogramy][1 podprogram]
  • roben - [1 Robenová][2 robená][3 robené][1 robených] added [3 podrobená][6 podrobené][1 podrobení][2 podrobený]
  • skalk - [4 Skalka][1 Skalke][1 Skalkový][1 Skalky][2 skalky] added [1 Podskalke]
  • statu - [1 statu] added [17 podstatu]
  • stupň - [1 Stupňami][46 stupňa][6 stupňami][15 stupňoch][19 stupňom][32 stupňov][1 stupňovou][4 stupňová][1 stupňovú] added [1 podstupňa]
  • ujm - [1 ujme] added [1 podujme]
  • večer - [7 Večer][1 Večera][22 večer][14 večera][11 večere][5 večeri][1 večeroch][1 večery] added [1 podvečer]
  • žalúdk - [11 žalúdka][1 žalúdkom] added [1 Podžalúdková][2 podžalúdkovej][1 podžalúdková]
  • žánru - [27 žánru] added [1 podžánru]

Wiktionary - new merged groups:

  • dan - [1 danú] added [4 poddaných]
  • kožn - [2 kožná][1 kožných] added [1 podkožný]
  • mienk - [3 mienky] added [2 podmienka][1 podmienkovú][1 podmienky]
  • nik - [3 nik] added [2 podnik]
  • nos - [1 nos][1 nosom][1 nosí] added [1 podnos]
  • per - [1 pera][2 perami][1 pero][1 perou] added [4 podpera]
  • rodu - [249 rodu] added [1 podrodu]
  • stat - [1 stat][1 stato] added [2 podstate]
  • statn - [1 statní] added [1 Podstatné][8 podstatné][1960 podstatného][1 podstatných]
  • ušk - [1 uško] added [1 poduška]
  • vod - [1 vod][9 voda][1 vodou][3 vody] added [1 podvod]
  • vojn - [4 vojna][1 vojnové][1 vojnový][1 vojny] added [1 podvojné]
  • žalúdk - [2 žalúdka][1 žalúdkom] added [1 podžalúdková]

Largest Groups (Aggressive Stemmer)[edit]

UPDATE: It seems that the aggressive stemmer has lived up to its name and is too aggressive, so I'm only considering the light stemmer now.

These groups are definitely more aggressive than the light stemmer, and group a lot more words. (The largest group has 100 different words in it!)

Switching to aggressive stemming caused about 14% of types and about 5% of tokens in the Wiktionary corpus to end up in newly merged groups. Most of the new collisions are words, but a small number are pronunciations.

In Wikipedia, the effect is more pronounced, with about 31% of types and about 13% of tokens being in newly merged groups. Most of the new collisions are words, with a small number being alphanumerics (e.g., 110, 110E, and 110C); these mergers happen with the light stemmer, too (and in other languages, like English), and some are good (like 32bit and 32bitový) while others are probably not.

The first 11 groups are groups from Wikipedia with 55 or more words in the group, and the next 8 groups are Wiktionary groups with 15 or more words in them.

Wikipedia:

  • hor - [23 Hor][61 Hora][1 Horbes][23 Hore][1 Horeca][1 Hori][2 Horka][2 Horky][2 Horká][1 Horký][7 Horn][1 Horne][14 Hornej][1 Hornina][10 Horniny][9 Hornom][1 Horny][90 Horná][43 Horné][22 Horného][1 Hornému][27 Horní][1 Horních][1 Horního][2 Horník][2 Horníka][2 Horníček][10 Hornú][14 Horný][2 Horných][2 Horným][13 Horom][1 Horos][5 Horou][5 Horov][9 Horova][1 Horovi][2 Horovo][1 Horových][2 Horovým][1 Horses][1 Hort][6 Hortus][33 Hory][4 Horynová][2 Horách][1 Horčička][1 Horčík][2 hor][29 hora][6 horami][1 horca][1 horcom][66 hore][1 horec][1 horení][1 horiny][3 horka][3 horká][1 horkého][5 horkú][1 horký][2 horkých][1 horlí][1 horn][1 horne][46 hornej][12 hornina][25 horninami][2 hornine][2 horninou][1 horninové][51 horniny][11 horninách][38 hornom][5 hornou][12 horná][13 horné][10 horného][1 horní][7 hornú][19 horný][11 horných][6 horným][2 horou][3 horstva][1 horstvami][1 horstvo][1 horstvom][1 horstvá][72 hory][30 horách][1 horám][3 horára][3 horárne][6 horárni][4 horí][1 horček][2 horčeka][1 horčice][1 horčinka][7 horčík][3 horčíka][5 horčíkom][1 horčíková][1 horčíkové][1 horčíkový]
  • jed - [2 JEDEC][2 JEDIN][58 Jeden][14 Jedi][1 Jediho][1 Jedin][4 Jedine][8 Jedinou][4 Jediná][7 Jediné][1 Jediní][23 Jediný][13 Jediným][2 Jedlička][1 Jedličkovom][2 Jedličková][1 Jedlová][2 Jedlá][2 Jedlí][2 Jedlík][46 Jedna][1 Jednej][8 Jedno][1 Jednom][26 Jednou][3 Jedny][18 Jedná][6 Jedného][1 Jednému][34 Jedným][9 jed][2 jede][546 jeden][1 jedeno][1 jedenom][16 jedine][20 jedinec][31 jedinej][14 jedinom][38 jedinou][50 jediná][31 jediné][25 jediného][2 jedinému][2 jediní][20 jedinú][98 jediný][1 jediných][61 jediným][6 jedinými][14 jedla][1 jedle][2 jedlej][8 jedli][14 jedlo][1 jedlom][8 jedlá][1 jedlého][1 jedlí][1 jedn][264 jedna][229 jednej][3 jedni][186 jedno][122 jednom][143 jednou][1 jednuška][11 jedny][9 jedná][2 jedné][284 jedného][17 jednému][2 jedním][1 jednú][3 jedných][234 jedným][1 jednými][3 jedom][2 jedov][1 jedové][1 jedovú]
  • kon - [5 Kon][1 Kona][1 Konami][1 Konas][73 Koncom][1 Koncové][1 Kone][3 Konec][1 Konin][1 Konko][1 Konovo][1 Konta][2 Konto][5 Koná][1 Konáre][1 Konárik][4 Koník][1 Koníka][3 Končí][1 Končím][3 konanej][2 konanom][1 konaná][4 konané][3 konaného][11 konaní][2 konaný][3 konaných][1 konaným][2 konanými][1 konc][175 konca][6 konce][219 konci][3 koncoch][161 koncom][5 koncov][2 koncovej][1 koncovou][3 koncová][7 koncové][2 koncového][8 koncový][2 koncových][3 koncovým][1 koncovými][29 kone][2 konec][13 koni][1 kont][2 konta][8 konte][8 konto][4 kontá][49 koná][2 konár][1 konári][1 konárikov][1 konármi][62 koní][1 koník][2 koníka][2 koníky][2 končinách][75 končí]
  • let - [3 LET][30 Let][1 Leta][1 Letecko][6 Letecká][3 Letecké][1 Leteckí][2 Leteckú][1 Leteckým][6 Letka][1 Letko][1 Letnej][1 Letnice][3 Letná][22 Letné][4 Letný][56 Letných][4 Leto][3 Letovice][1 Letové][3 Letový][1 Letta][1 Lettich][3 Lettres][2 Lety][1 Letá][92 let][28 leta][5 letami][1 letci][2 letcom][4 letcov][135 lete][7 letec][26 leteckej][1 letecko][2 leteckom][2 leteckou][1 letecky][20 letecká][13 letecké][13 leteckého][9 leteckú][18 letecký][17 leteckých][9 leteckým][7 letka][1 letkou][4 letky][1 letmi][6 letnej][4 letnom][3 letnou][2 letná][20 letné][2 letného][1 letnému][1 letní][2 letnú][11 letný][12 letných][3 letným][2 letnými][13 leto][8 letoch][9 letom][2 letos][38 letov][10 letovej][1 letová][6 letové][2 letového][1 letoví][2 letovú][42 letový][8 letových][3 letovým][3 letušky][49 lety][24 letá][3 letí]
  • mar - [1 MARTA][10 Mar][11 Mara][1 Marar][8 Marat][4 Marata][39 Marc][16 Marca][1 Marci][8 Marcin][2 Marcinko][1 Marcinčin][1 Marck][44 Marco][1 Marcom][11 Marcos][1 Marcov][48 Marcus][1 Marcé][1 Marcínková][26 Mare][5 Marec][99 Marek][2 Mareka][1 Marekov][1 Mareková][1 Mari][1 Maric][5 Marica][1 Marici][1 Maries][9 Marika][2 Mariková][3 Marin][21 Marina][7 Marine][1 Marino][1 Marinou][2 Marinovej][1 Marinus][1 Marit][60 Marián][4 Mariána][2 Mariánom][1 Mariány][95 Mark][16 Marka][18 Marko][6 Markom][2 Markos][4 Markov][1 Markova][1 Markovi][1 Markovom][3 Marková][11 Markus][2 Marky][1 Marl][3 Marle][1 Marlin][1 Marlos][3 Marly][2 Marna][114 Marne][2 Marny][1 Marot][4 Mart][39 Marta][1 Martiho][444 Martin][101 Martina][61 Martine][1 Martini][1 Martiniho][2 Martinka][2 Martinko][4 Martinková][17 Martinom][1 Martinou][6 Martinovi][3 Martiny][2 Martou][1 Martovi][1 Martovom][6 Marty][1 Martí][1 Maruškina][43 Mary][2 Marín][13 Marína][1 Maríne][3 Maríno][1 Maríny][2 Marček][1 Marčenko][1 mar][2 mara][373 marca][110 marci][2 marcom][1 marcovej][1 marcová][1 marcové][1 marcovú][1 mare][369 marec][1 marista][1 mark][1 marka][3 marke][1 marky][1 martin]
  • mil - [6 Mil][1 Mila][158 Milan][24 Milana][1 Milani][1 Milano][3 Milanom][2 Milanovi][2 Milcová][3 Mile][5 Milena][1 Milenou][1 Milica][1 Milionár][3 Milk][2 Milka][4 Milkova][5 Mill][1 Milla][3 Milli][1 Milly][1 Milna][1 Milne][5 Milo][5 Milos][2 Milota][1 Milou][3 Milov][1 Milovy][1 Miloň][1 Milt][1 Milty][2 Milučký][5 Miluška][8 Milána][9 Miláne][24 Miláno][2 Milý][1 Milčo][67 mil][1 milej][1 milice][1 milionár][1 milionára][1 milionárka][1 milionárom][2 milk][1 milo][1 milos][5 milosti][1 milovníci][2 milovník][1 milovníka][1 milovníkom][3 milovníkov][3 milá][4 miláčik][1 miláčikov][1 milé][1 milú][1 milý][1 milým]
  • nov - [2 NOV][6 NOVA][1 NOVY][1 NOVÁ][10 Nov][30 Nova][7 Novara][2 Novare][1 Nove][142 Novej][6 Novi][1 Novice][1 Novina][1 Novinové][8 Noviny][1 Novinách][4 Novo][93 Novom][1 Novosti][1 Novota][1 Novotka][6 Novou][3 Novovek][2 Novoveká][1 Novoveké][187 Nová][1 Nováčik][26 Nováčikmi][19 Nováčikom][182 Nové][79 Nového][2 Novému][3 Noví][28 Novú][138 Nový][20 Nových][10 Novým][2 nov][1 nova][2 novara][126 novej][2 novicov][4 novin][5 novinami][1 novini][1 novinovom][1 novinového][1 novinový][4 novinových][64 noviny][46 novinách][5 novinám][33 novo][37 novom][1 novosti][1 novoty][24 novou][1 novovek][3 novovekej][1 novovekom][1 novoveká][2 novoveké][1 novovekí][3 novoveký][1 novovekých][2 novus][1 novy][83 nová][2 nováčik][2 nováčika][2 nováčikmi][5 nováčikom][1 nováčikovi][264 nové][166 nového][16 novému][6 noví][1 novích][92 novín][82 novú][207 nový][161 nových][59 novým][22 novými][3 novším]
  • pol - [1 Pol][1 Polan][1 Polar][11 Pole][1 Polenov][1 Polenova][7 Police][7 Policy][2 Polienko][1 Polina][1 Polit][3 Politici][8 Politik][7 Politika][1 Politikov][2 Polka][1 Poll][4 Polly][1 Polní][8 Polo][1 Poloczek][6 Polom][1 Polovci][2 Polus][1 Polynin][2 Polárka][3 Polárke][1 Polárky][7 Polárna][1 Polárny][1 Poláčik][1 Poláčková][72 pol][1 pola][93 pole][50 poli][2 police][2 policki][2 policy][13 politici][257 politik][62 politika][54 politike][7 politikmi][1 politikoch][8 politikom][13 politikou][18 politikov][3 politikovi][65 politiky][1 politk][4 politík][2 polka][2 polo][9 polos][1 poloveckým][120 polovice][217 polovici][1 polta][4 poly][1 polárkou][8 polárna][3 polárne][6 polárnej][2 polárnik][1 polárnom][3 polárnou][12 polárny][30 polí][1 polích][6 políčok]
  • rad - [33 Rad][32 Rada][1 Radan][4 Radar][2 Radary][4 Rade][11 Radek][3 Radián][1 Radičiná][2 Radka][1 Radkovy][1 Radlom][1 Radnice][1 Radnički][3 Rado][9 Radom][4 Radou][2 Radovka][1 Radová][1 Radovánky][1 Radula][55 Rady][5 Radíkov][138 rad][77 rada][3 radami][6 radar][1 radarmi][1 radaroch][2 radarom][2 radarovej][1 radarové][1 radarovú][4 radarový][3 radarovým][7 radca][3 radcom][82 rade][2 radená][3 radené][2 radený][12 radi][1 radián][6 radiánoch][2 radmi][12 radnice][5 radnici][1 rado][13 radoch][16 radom][2 radost][10 radosti][18 radou][16 radov][4 radovej][2 radové][1 radového][1 radoví][13 radový][4 radových][2 radovým][1 radovými][1 radulou][199 rady][3 radách][1 radám][31 radí]
  • star - [1 STAR][57 Star][2 Starci][1 Starcka][1 Stare][1 Starec][30 Starej][1 Stari][1 Starickom][1 Starikov][2 Stariny][1 Stark][1 Starne][1 Staro][17 Starom][7 Starosta][1 Starostkou][4 Starovek][3 Starovekom][2 Staroveká][5 Staroveké][2 Starovekého][1 Starovekí][18 Staroveký][1 Starovekým][5 Start][1 Stary][62 Stará][50 Staré][20 Starého][1 Starému][3 Starí][1 Starú][31 Starý][3 Starých][4 Starým][1 Starček][5 star][3 starca][2 starec][46 starej][1 stareny][2 starne][2 starnú][1 staroba][3 starobe][2 staroby][12 starom][14 starosta][27 starosti][2 starostka][10 starostom][1 starostov][7 starou][4 starovek][12 starovekej][29 starovekom][2 starovekou][3 staroveká][13 staroveké][20 starovekého][2 starovekému][4 starovekí][1 starovekú][9 staroveký][21 starovekých][5 starovekým][2 starovekými][3 start][1 staručkej][39 stará][62 staré][52 starého][4 starému][3 starí][3 starú][66 starý][46 starých][5 starým][5 starými][1 starčekov][1 starčekový][10 starším]
  • tur - [1 TURČAN][3 Turan][1 Turanmi][3 Turany][16 Turca][45 Turci][1 Turco][23 Turecka][3 Tureckej][29 Turecko][3 Tureckom][3 Turecká][1 Turecké][4 Turecký][4 Turej][3 Turek][1 Turečtina][1 Turisti][1 Turistik][5 Turistika][1 Turistom][16 Turkami][2 Turkménci][16 Turkom][29 Turkov][1 Turkove][2 Turn][2 Turne][4 Turnov][4 Turná][3 Turné][1 Turtles][3 Turul][1 Turula][5 Turá][1 Turíce][5 Turín][6 Turína][16 Turíne][1 Turč][2 Turčan][1 Turčanovej][2 Turčanová][1 Turčanovú][1 Turček][3 tur][2 tura][29 tureckej][3 turecko][5 tureckom][2 tureckou][3 turecky][18 turecká][17 turecké][23 tureckého][6 tureckému][4 tureckú][21 turecký][15 tureckých][8 tureckým][5 tureckými][1 turečtina][4 turečtine][2 turečtiny][3 turista][8 turistami][4 turisti][7 turistika][3 turistike][1 turistikou][6 turistiky][4 turistom][53 turistov][2 turkmenčina][1 turkménčine][1 turnikete][108 turné][2 turov]

Wiktionary:

  • angl - [1 Anglicka][1 Anglicko][1 Anglicky][1 Anglist][1 Anglistin][1 Angličtiny][1 anglicky][1 anglická][5 anglické][4 anglického][1 anglickém][1 anglický][2 anglickým][1 anglistika][1 angličtin][16 angličtina][1 angličtine][1 angličtiny]
  • druh - [36 druh][3 druhej][1 druhom][1 druhov][1 druhová][1 druhy][5 druhá][1 druhé][1 druhého][1 druhému][1 druhú][1 druhý][1 družica][2 družicová][1 družicový]
  • hor - [2 Hora][1 Hore][1 hor][3 hora][2 hore][2 horec][1 horen][1 horka][1 horkej][1 horké][1 horký][19 hornej][2 hornina][1 horninách][2 hornou][1 horstvo][2 horčík][1 horčíka][1 horčíkom][1 horčíkový]
  • jed - [1 Jediný][1 Jedným][3 jed][5 jeden][3 jedinec][1 jediný][2 jedla][1 jedle][1 jedlička][4 jedlo][2 jedlé][2 jedlý][4 jedna][5 jednej][1 jedničkový][1 jedné][2 jedného][1 jedový]
  • nem - [1 Nemec][3 Nemecko][1 Nemeckom][1 Nemka][8 nemecké][2 nemeckého][2 nemecký][1 nemine][1 nemo][1 nemota][4 nemá][1 nemý][1 nemým][15 nemčina][1 nemčinou][21 nemčiny][1 nemčinám]
  • slov - [10 Slovo][8 slov][19 slova][1 slovami][2 slovančina][2 slove][1 slovies][2 slovné][2 slovného][5 slovník][2 slovníkom][1 slovníkovej][2 slovný][11 slovo][2 slovom][2 slová][1 slovách]
  • star - [2 Starého][1 star][18 starej][2 starena][1 starká][2 starosti][1 starovekej][1 starovekom][1 staroveké][1 staroveký][2 starovekých][9 stará][1 starého][7 starý][2 starých][1 starším]
  • vod - [1 vod][9 voda][1 vodca][2 vodka][1 vodnej][1 vodnice][2 vodná][1 vodné][1 vodník][7 vodný][1 vodou][3 vodouš][1 vodová][3 vody][1 vodík][1 vodíka][1 vodíkom]

Random Groups (Aggressive Stemmer)[edit]

UPDATE: It seems that the aggressive stemmer has lived up to its name and is too aggressive, so I'm only considering the light stemmer now.

Below are 20 random groupings each from Wikipedia and Wiktionary. These are more representative of typical words.

Wikipedia:

  • cisárs - [1 Cisárska][1 Cisárske][3 Cisársky][4 cisárska][11 cisárske][8 cisárskej][1 cisársko][5 cisárskom][2 cisárskou][9 cisársky]
  • inf - [2 INF][1 Infa][2 Influence][3 Info][6 info]
  • kal - [1 KALINUS][1 Kal][1 Kala][2 Kale][1 Kali][7 Kalina][1 Kalininom][7 Kalinov][3 Kalinove][6 Kalinovo][1 Kalinová][3 Kalisto][2 Kalita][12 Kalkata][6 Kalkaty][1 Kalle][1 Kallom][1 Kallová][1 Kalnej][1 Kalná][2 Kalt][1 Kaly][1 Kalám][1 kal][1 kale][1 kalené][4 kalich][1 kalky][1 kalkyna][1 kallov][1 kalných][1 kalom]
  • kapitul - [1 kapitulnej][1 kapitulného][1 kapitulárny]
  • konstan - [1 Konstanca][1 Konstancou][20 Konstantin][2 Konstantina][1 Konstantine][3 Konstantinom][3 Konstantinos]
  • kra - [1 Kra][2 Krajinka][2 Krajíčka][14 Krakov][8 Krakova][10 Krakove][2 Krakovej][1 Krakovom][1 Kral][3 Kranich][6 Kraus][1 Kray][2 Kračany][1 krabičkách][1 krajinky][1 krami][2 kratším]
  • krajinotvor - [1 krajinotvornou][1 krajinotvorného][1 krajinotvorných][1 krajinotvorným]
  • nádraži - [1 nádražia][2 nádražie]
  • najhodnotnejši - [1 najhodnotnejšia][7 najhodnotnejšie]
  • nca - [1 NCA][1 NCAA]
  • obmedzeni - [1 Obmedzenie][22 obmedzenia][1 obmedzeniami][19 obmedzenie]
  • obsluhuj - [1 Obsluhuje][3 obsluhuje][6 obsluhujú]
  • piktograf - [5 piktografické][1 piktografického]
  • raš - [3 Raši][2 Rašického][1 Raška]
  • tábor - [26 Tábor][2 Tábora][1 Táboriti][1 Táborový][19 tábor][32 tábora][21 tábore][1 táboritmi][1 táboritov][10 táboroch][19 táborov][2 táborovým][13 tábory]
  • tanker - [1 Tanker][1 tanker][1 tankera][1 tankerom]
  • tih - [1 Tiho][2 Tiháni][2 Tižina]
  • veligrad - [11 Veligrad][1 Veligrade]
  • vyhrab - [1 vyhrabanej][1 vyhrabanými]
  • západoukrajins - [1 Západoukrajinskej][3 Západoukrajinská][1 Západoukrajinskí][2 západoukrajinská][1 západoukrajinského]

Wiktionary:

  • čarodej - [1 čarodejka][1 čarodejnice][2 čarodejník]
  • chorv - [1 Chorvátka][1 chorvátčina]
  • con - [1 con][1 conica]
  • cukr - [1 cukrovka][2 cukrový][1 cukrár][1 cukrárka]
  • dokona - [1 dokonalom][1 dokonalý]
  • erup - [1 erupti][1 erupčný]
  • gun - [2 gun][2 guna][3 guni]
  • infek - [2 infekčná][2 infekčné]
  • kra - [4 kra][1 krank]
  • krkav - [1 Krkavčí][2 krkavec][1 krkavčí]
  • nežidovs - [1 nežidovského][1 nežidovský]
  • novogré - [1 novogrécky][4 novogréčtina]
  • ohn - [1 ohna][1 ohne][1 ohnivo]
  • písom - [2 písomne][1 písomná]
  • plá - [2 plán][1 plánka][1 plány][1 plání]
  • smr - [1 smrek][3 smrekový][1 smrkový][2 smrt][1 smrtelných][7 smrti]
  • sněž - [1 sněžní][1 sněžný]
  • väzen - [1 väzenkyna][1 väzenstvo]
  • vče - [2 včela][1 včelí]
  • žijú - [1 žijúci][1 žijúcich]

Miscellaneous Stemming Observations[edit]

I'm noting these outside the "Groups for Review" section above because they don't really need speaker review.

  • There are no stemming groups without common beginnings or endings for the light stemmer, which is expected because of the way the stemmer works (chopping off suffixes).
  • The longest tokens in the Wiktionary corpus are Germanic-looking compounds and IPA pronunciations. The longest tokens in the Wikipedia corpus pieces of URLs and filenames, plus a few odd but reasonable tokens, like 1 followed for 100 zeros (from the googolplex article).

Next Steps[edit]

  • Get speaker review of the stemming groups above. I'll look for assistance from the Village Pump on Wikipedia and Wiktionary. (DONE, looks good)
    • Discussion so far is happening on the Wikipedia Village Pump and in comments on this page.
    • Looks like the light stemmer is okay, the aggressive stemmer is too aggressive, and naj--stripping is helpful. Still looking at pod--stripping.
  • Assuming some version of the stemmer is acceptable, re-implement it in Java, wrap it into an Elasticsearch filter, and fold it into search/extra. (DONE)
  • Deploy the updated version of search/extra, and re-index Slovak-language wikis. (DONE)