+++ /dev/null
-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
-<html>
-<head>
- <meta content="text/html; charset=UTF-8" http-equiv="content-type">
- <title>Stempel - Algorithmic Stemmer for Polish Language</title>
- <meta content="Andrzej Bialecki" name="author">
- <meta name="keywords"
- content="stemming, stemmer, algorithmic stemmer, Polish stemmer">
- <meta
- content="This page describes a software package consisting of high-quality stemming tables for Polish, and a universal algorithmic stemmer, which operates using these tables."
- name="description">
-</head>
-<body style="font-family: Arial,SansSerif;">
-<h1><i>Stempel</i> - Algorithmic Stemmer for Polish Language</h1>
-<h2>Introduction</h2>
-<p>A method for conflation of different inflected word forms is an
-important component of many Information Retrieval systems. It helps to
-improve the system's recall and can significantly reduce the index
-size. This is especially true for highly-inflectional languages like
-those from the Slavic language family (Czech, Slovak, Polish, Russian,
-Bulgarian, etc).</p>
-<p>This page describes a software package consisting of high-quality
-stemming tables for Polish, and a universal algorithmic stemmer, which
-operates using these tables. The stemmer code is taken virtually
-unchanged from the <a href="http://www.egothor.org">Egothor project</a>.</p>
-<p>The software distribution includes stemmer
-tables prepared using an extensive corpus of Polish language (see
-details below).</p>
-<p>This work is available under Apache-style Open Source license - the
-stemmer code is covered by Egothor License, the tables and other
-additions are covered by Apache License 2.0. Both licenses allow to use
-the code in Open Source as well as commercial (closed source) projects.</p>
-<h3>Terminology</h3>
-<p>A short explanation is in order about the terminology used in this
-text.</p>
-<p>In the following sections I make a distinction between <b>stem</b>
-and <b>lemma</b>.</p>
-<p>Lemma is a base grammatical form (dictionary form, headword) of a
-word. Lemma is an existing, grammatically correct word in some human
-language.</p>
-<p>Stem on the other hand is just a unique token, not necessarily
-making any sense in any human language, but which can serve as a unique
-label instead of lemma for the same set of inflected forms. Quite often
-stem is referred to as a "root" of the word - which is incorrect and
-misleading (stems sometimes have very little to do with the linguistic
-root of a word, i.e. a pattern found in a word which is common to all
-inflected forms or within a family of languages).</p>
-<p>For an IR system stems are usually sufficient, for a morphological
-analysis system obviously lemmas are a must. In practice, various
-stemmers produce a mix of stems and lemmas, as is the case with the
-stemmer described here. Additionally, for some languages, which use
-suffix-based inflection rules many stemmers based on suffix-stripping
-will produce a large percentage of stems equivalent to lemmas. This is
-however not the case for languages with complex, irregular inflection
-rules (such as Slavic languages) - here simplistic suffix-stripping
-stemmers produce very poor results.</p>
-<h3>Background</h3>
-<p>Lemmatization is a process of finding the base, non-inflected form
-of a word. The result of lemmatization is a correct existing word,
-often in nominative case for nouns and infinitive form for verbs. A
-given inflected form may correspond to several lemmas (e.g. "found"
--> find, found) - the correct choice depends on the context.<br>
-<br>
-Stemming is concerned mostly with finding a unique "root" of a word,
-which not necessarily results in any existing word or lemma. The
-quality of stemming is measured by the rate of collisions (overstemming
-- which causes words with different lemmas to be incorrectly conflated
-into one "root"), and the rate of superfluous word "roots"
-(understemming - which assigns several "roots" to words with the same
-lemma). <br>
-<br>
-Both stemmer and lemmatizer can be implemented in various ways. The two
-most common approaches are:<br>
-</p>
-<ul>
- <li>dictionary-based: where the stemmer uses an extensive dictionary
-of morphological forms in order to find the corresponding stem or lemma</li>
- <li>algorithmic: where the stemmer uses an algorithm, based on
-general morphological properties of a given language plus a set of
-heuristic rules<br>
- </li>
-</ul>
-There are many existing and well-known implementations of stemmers for
-English (Porter, Lovins, Krovetz) and other European languages
-(<a href="http://snowball.tartarus.org">Snowball</a>). There are also
-good quality commercial lemmatizers for Polish. However, there is only
-one
-freely available Polish stemmer, implemented by
-<a
- href="http://www.cs.put.poznan.pl/dweiss/xml/projects/lametyzator/index.xml?lang=en">Dawid
-Weiss</a>, based on the "ispell" dictionary and Jan Daciuk's <a
- href="http://www.eti.pg.gda.pl/%7Ejandac/">FSA package</a>. That
-stemmer is dictionary-based. This means that even
-though it can achieve
-perfect accuracy for previously known word forms found in its
-dictionary, it
-completely fails in case of all other word forms. This deficiency is
-somewhat mitigated by the comprehensive dictionary distributed with
-this stemmer (so there is a high probability that most of the words in
-the input text will be found in the dictionary), however the problem
-still remains (please see the page above for more detailed description).<br>
-<br>
-The implementation described here uses an algorithmic method. This
-method
-and particular algorithm implementation are described in detail in
-[1][2].
-The main advantage of algorithmic stemmers is their ability to process
-previously
-unseen word forms with high accuracy. This particular algorithm uses a
-set
-of
-transformation rules (patch commands), which describe how a word with a
-given pattern should be transformed to its stem. These rules are first
-learned from a training corpus. They don't
-cover
-all possible cases, so there is always some loss of precision/recall
-(which
-means that even the words from the training corpus are sometimes
-incorrectly stemmed).<br>
-<h2>Algorithm and implementation<span style="font-style: italic;"></span></h2>
-The algorithm and its Java implementation is described in detail in the
-publications cited below. Here's just a short excerpt from [2]:<br>
-<br>
-<center>
-<div style="width: 80%;" align="justify">"The aim is separation of the
-stemmer execution code from the data
-structures [...]. In other words, a static algorithm configurable by
-data must be developed. The word transformations that happen in the
-stemmer must be then encoded to the data tables.<br>
-<br>
-The tacit input of our method is a sample set (a so-called dictionary)
-of words (as keys) and their stems. Each record can be equivalently
-stored as a key and the record of key's transformation to its
-respective stem. The transformation record is termed a patch command
-(P-command). It must be ensured that P-commands are universal, and that
-P-commands can transform any word to its stem. Our solution[6,8] is
-based on the Levenstein metric [10], which produces P-command as the
-minimum cost path in a directed graph.<br>
-<br>
-One can imagine the P-command as an algorithm for an operator (editor)
-that rewrites a string to another string. The operator can use these
-instructions (PP-command's): <span style="font-weight: bold;">removal </span>-
-deletes a sequence of characters starting at the current cursor
-position and moves the cursor to the next character. The length of this
-sequence is the parameter; <span style="font-weight: bold;">insertion </span>-
-inserts a character ch, without moving the cursor. The character ch is
-a parameter; <span style="font-weight: bold;">substitution </span>
-- rewrites a character at the current cursor position to the character
-ch and moves the cursor to the next character. The character ch is a
-parameter; <span style="font-weight: bold;">no operation</span> (NOOP)
-- skip a sequence of characters starting at the current cursor
-position. The length of this sequence is the parameter.<br>
-<br>
-The P-commands are applied from the end of a word (right to left). This
-assumption can reduce the set of P-command's, because the last NOOP,
-moving the cursor to the end of a string without any changes, need not
-be stored."</div>
-</center>
-<br>
-Data structure used to keep the dictionary (words and their P-commands)
-is a trie. Several optimization steps are applied in turn to reduce and
-optimize the initial trie, by eliminating useless information and
-shortening the paths in the trie.<br>
-<br>
-Finally, in order to obtain a stem from the input word, the word is
-passed once through a matching path in the trie (applying at each node
-the P-commands stored there). The result is a word stem.<br>
-<h2>Corpus</h2>
-<p><i>(to be completed...)</i></p>
-<p>The following Polish corpora have been used:</p>
-<ul>
- <li><a
- href="http://sourceforge.net/project/showfiles.php?group_id=49316&package_id=65354">Polish
-dictionary
-from ispell distribution</a></li>
- <li><a href="http://www.mimuw.edu.pl/polszczyzna/">Wzbogacony korpus
-słownika frekwencyjnego</a></li>
-<!--<li><a href="http://www.korpus.pl">Korpus IPI PAN</a></li>-->
-<!--<li>The Bible (so called "Warsaw Bible" or "Brytyjka")</li>--><li>The
-Bible (so called "TysiÄ…clecia") - unauthorized electronic version</li>
- <li><a
- href="http://www.mimuw.edu.pl/polszczyzna/Debian/sam34_3.4a.02-1_i386.deb">Analizator
-morfologiczny SAM v. 3.4</a> - this was used to recover lemmas
-missing from other texts</li>
-</ul>
-<p>This step was the most time-consuming - and it would probably be
-even more tedious and difficult if not for the
-help of
-<a href="http://www.python.org/">Python</a>. The source texts had to be
-brought to a common encoding (UTF-8) - some of them used quite ancient
-encodings like Mazovia or DHN - and then scripts were written to
-collect all lemmas and
-inflected forms from the source texts. In cases when the source text
-was not
-tagged,
-I used the SAM analyzer to produce lemmas. In cases of ambiguous
-lemmatization I decided to put references to inflected forms from all
-base forms.<br>
-</p>
-<p>All grammatical categories were allowed to appear in the corpus,
-i.e. nouns, verbs, adjectives, numerals, and pronouns. The resulting
-corpus consisted of roughly 87,000+ inflection sets, i.e. each set
-consisted of one base form (lemma) and many inflected forms. However,
-because of the nature of the training method I restricted these sets to
-include only those where there were at least 4 inflected forms. Sets
-with 3 or less inflected forms were removed, so that the final corpus
-consisted of ~69,000 unique sets, which in turn contained ~1.5 mln
-inflected forms. <br>
-</p>
-<h2>Testing</h2>
-<p>I tested the stemmer tables produced using the implementation
-described above. The following sections give some details about
-the testing setup.
-</p>
-<h3>Testing procedure</h3>
-<p>The testing procedure was as follows:
-</p>
-<ul>
- <li>the whole corpus of ~69,000 unique sets was shuffled, so that the
-input sets were in random order.</li>
- <li>the corpus was split into two parts - one with 30,000 sets (Part
-1), the other with ~39,000 sets (Part 2).</li>
- <li>Training samples were drawn in sequential order from the Part 1.
-Since the sets were already randomized, the training samples were also
-randomized, but this procedure ensured that each larger training sample
-contained all smaller samples.</li>
- <li>Part 2 was used for testing. Note: this means that the testing
-run used <em>only</em> words previously unseen during the training
-phase. This is the worst scenario, because it means that stemmer must
-extrapolate the learned rules to unknown cases. This also means that in
-a real-life case (where the input is a mix between known and unknown
-words) the F-measure of the stemmer will be even higher than in the
-table below.</li>
-</ul>
-<h3>Test results</h3>
-<p>The following table summarizes test results for varying sizes
-of training samples. The meaning of the table columns is
-described below:
-</p>
-<ul>
- <li><b>training sets:</b> the number of training sets. One set
-consists of one lemma and at least 4 and up to ~80 inflected forms
-(including pre- and suffixed forms).</li>
- <li><b>testing forms:</b> the number of testing forms. Only inflected
-forms were used in testing.</li>
- <li><b>stem OK:</b> the number of cases when produced output was a
-correct (unique) stem. Note: quite often correct stems were also
-correct lemmas.</li>
- <li><b>lemma OK:</b> the number of cases when produced output was a
-correct lemma.</li>
- <li><b>missing:</b> the number of cases when stemmer was unable to
-provide any output.</li>
- <li><b>stem bad:</b> the number of cases when produced output was a
-stem, but already in use identifying a different set.</li>
- <li><b>lemma bad:</b> the number of cases when produced output was an
-incorrect lemma. Note: quite often in such case the output was a
-correct stem.</li>
- <li><b>table size:</b> the size in bytes of the stemmer table.</li>
-</ul>
-<div align="center">
-<table border="1" cellpadding="2" cellspacing="0">
- <tbody>
- <tr bgcolor="#a0b0c0">
- <th>Training sets</th>
- <th>Testing forms</th>
- <th>Stem OK</th>
- <th>Lemma OK</th>
- <th>Missing</th>
- <th>Stem Bad</th>
- <th>Lemma Bad</th>
- <th>Table size [B]</th>
- </tr>
- <tr align="right">
- <td>100</td>
- <td>1022985</td>
- <td>842209</td>
- <td>593632</td>
- <td>172711</td>
- <td>22331</td>
- <td>256642</td>
- <td>28438</td>
- </tr>
- <tr align="right">
- <td>200</td>
- <td>1022985</td>
- <td>862789</td>
- <td>646488</td>
- <td>153288</td>
- <td>16306</td>
- <td>223209</td>
- <td>48660</td>
- </tr>
- <tr align="right">
- <td>500</td>
- <td>1022985</td>
- <td>885786</td>
- <td>685009</td>
- <td>130772</td>
- <td>14856</td>
- <td>207204</td>
- <td>108798</td>
- </tr>
- <tr align="right">
- <td>700</td>
- <td>1022985</td>
- <td>909031</td>
- <td>704609</td>
- <td>107084</td>
- <td>15442</td>
- <td>211292</td>
- <td>139291</td>
- </tr>
- <tr align="right">
- <td>1000</td>
- <td>1022985</td>
- <td>926079</td>
- <td>725720</td>
- <td>90117</td>
- <td>14941</td>
- <td>207148</td>
- <td>183677</td>
- </tr>
- <tr align="right">
- <td>2000</td>
- <td>1022985</td>
- <td>942886</td>
- <td>746641</td>
- <td>73429</td>
- <td>14903</td>
- <td>202915</td>
- <td>313516</td>
- </tr>
- <tr align="right">
- <td>5000</td>
- <td>1022985</td>
- <td>954721</td>
- <td>759930</td>
- <td>61476</td>
- <td>14817</td>
- <td>201579</td>
- <td>640969</td>
- </tr>
- <tr align="right">
- <td>7000</td>
- <td>1022985</td>
- <td>956165</td>
- <td>764033</td>
- <td>60364</td>
- <td>14620</td>
- <td>198588</td>
- <td>839347</td>
- </tr>
- <tr align="right">
- <td>10000</td>
- <td>1022985</td>
- <td>965427</td>
- <td>775507</td>
- <td>50797</td>
- <td>14662</td>
- <td>196681</td>
- <td>1144537</td>
- </tr>
- <tr align="right">
- <td>12000</td>
- <td>1022985</td>
- <td>967664</td>
- <td>782143</td>
- <td>48722</td>
- <td>14284</td>
- <td>192120</td>
- <td>1313508</td>
- </tr>
- <tr align="right">
- <td>15000</td>
- <td>1022985</td>
- <td>973188</td>
- <td>788867</td>
- <td>43247</td>
- <td>14349</td>
- <td>190871</td>
- <td>1567902</td>
- </tr>
- <tr align="right">
- <td>17000</td>
- <td>1022985</td>
- <td>974203</td>
- <td>791804</td>
- <td>42319</td>
- <td>14333</td>
- <td>188862</td>
- <td>1733957</td>
- </tr>
- <tr align="right">
- <td>20000</td>
- <td>1022985</td>
- <td>976234</td>
- <td>791554</td>
- <td>40058</td>
- <td>14601</td>
- <td>191373</td>
- <td>1977615</td>
- </tr>
- </tbody>
-</table>
-</div>
-<p>I also measured the time to produce a stem (which involves
-traversing a trie,
-retrieving a patch command and applying the patch command to the input
-string).
-On a machine running Windows XP (Pentium 4, 1.7 GHz, JDK 1.4.2_03
-HotSpot),
-for tables ranging in size from 1,000 to 20,000 cells, the time to
-produce a
-single stem varies between 5-10 microseconds.<br>
-</p>
-<p>This means that the stemmer can process up to <span
- style="font-weight: bold;">200,000 words per second</span>, an
-outstanding result when compared to other stemmers (Morfeusz - ~2,000
-w/s, FormAN (MS Word analyzer) - ~1,000 w/s).<br>
-</p>
-<p>The package contains a class <code>org.getopt.stempel.Benchmark</code>,
-which you can use to produce reports
-like the one below:<br>
-</p>
-<pre>--------- Stemmer benchmark report: -----------<br>Stemmer table: /res/tables/stemmer_2000.out<br>Input file: ../test3.txt<br>Number of runs: 3<br><br> RUN NUMBER: 1 2 3<br> Total input words 1378176 1378176 1378176<br> Missed output words 112 112 112<br> Time elapsed [ms] 6989 6940 6640<br> Hit rate percent 99.99% 99.99% 99.99%<br> Miss rate percent 00.01% 00.01% 00.01%<br> Words per second 197192 198584 207557<br> Time per word [us] 5.07 5.04 4.82<br></pre>
-<h2>Summary</h2>
-<p>The results of these tests are very encouraging. It seems that using
-the
-training corpus and the stemming algorithm described above results in a
-high-quality stemmer useful for most applications. Moreover, it can
-also
-be used as a better than average lemmatizer.</p>
-<p>Both the author of the implementation
-(Leo Galambos, <leo.galambos AT egothor DOT org>) and the author
-of this
-compilation (Andrzej Bialecki <ab AT getopt DOT org>) would
-appreciate any
-feedback and suggestions for further improvements.</p>
-<h2>Bibliography</h2>
-<ol>
- <li>Galambos, L.: Multilingual Stemmer in Web Environment, PhD
-Thesis,
-Faculty of Mathematics and Physics, Charles University in Prague, in
-press.</li>
- <li>Galambos, L.: Semi-automatic Stemmer Evaluation. International
-Intelligent Information Processing and Web Mining Conference, 2004,
-Zakopane, Poland.</li>
- <li>Galambos, L.: Lemmatizer for Document Information Retrieval
-Systems in JAVA.<span style="text-decoration: underline;"> </span><a
- class="moz-txt-link-rfc2396E"
- href="http://www.informatik.uni-trier.de/%7Eley/db/conf/sofsem/sofsem2001.html#Galambos01"><http://www.informatik.uni-trier.de/%7Eley/db/conf/sofsem/sofsem2001.html#Galambos01></a>
-SOFSEM 2001, Piestany, Slovakia. <br>
- </li>
-</ol>
-<br>
-<br>
-</body>
-</html>
fnp / pylucene.git / blobdiff