Save This Page
Home » lucene-3.0.1-src » org.apache » lucene » analysis » [javadoc | source]
    1   package org.apache.lucene.analysis;
    2   
    3   /**
    4    * Licensed to the Apache Software Foundation (ASF) under one or more
    5    * contributor license agreements.  See the NOTICE file distributed with
    6    * this work for additional information regarding copyright ownership.
    7    * The ASF licenses this file to You under the Apache License, Version 2.0
    8    * (the "License"); you may not use this file except in compliance with
    9    * the License.  You may obtain a copy of the License at
   10    *
   11    *     http://www.apache.org/licenses/LICENSE-2.0
   12    *
   13    * Unless required by applicable law or agreed to in writing, software
   14    * distributed under the License is distributed on an "AS IS" BASIS,
   15    * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   16    * See the License for the specific language governing permissions and
   17    * limitations under the License.
   18    */
   19   
   20   /*
   21   
   22      Porter stemmer in Java. The original paper is in
   23   
   24          Porter, 1980, An algorithm for suffix stripping, Program, Vol. 14,
   25          no. 3, pp 130-137,
   26   
   27      See also http://www.tartarus.org/~martin/PorterStemmer/index.html
   28   
   29      Bug 1 (reported by Gonzalo Parra 16/10/99) fixed as marked below.
   30      Tthe words 'aed', 'eed', 'oed' leave k at 'a' for step 3, and b[k-1]
   31      is then out outside the bounds of b.
   32   
   33      Similarly,
   34   
   35      Bug 2 (reported by Steve Dyrdahl 22/2/00) fixed as marked below.
   36      'ion' by itself leaves j = -1 in the test for 'ion' in step 5, and
   37      b[j] is then outside the bounds of b.
   38   
   39      Release 3.
   40   
   41      [ This version is derived from Release 3, modified by Brian Goetz to
   42        optimize for fewer object creations.  ]
   43   
   44   */
   45   
   46   
   47   import java.io;
   48   
   49   /**
   50    *
   51    * Stemmer, implementing the Porter Stemming Algorithm
   52    *
   53    * The Stemmer class transforms a word into its root form.  The input
   54    * word can be provided a character at time (by calling add()), or at once
   55    * by calling one of the various stem(something) methods.
   56    */
   57   
   58   class PorterStemmer
   59   {
   60     private char[] b;
   61     private int i,    /* offset into b */
   62       j, k, k0;
   63     private boolean dirty = false;
   64     private static final int INC = 50; /* unit of size whereby b is increased */
   65     private static final int EXTRA = 1;
   66   
   67     public PorterStemmer() {
   68       b = new char[INC];
   69       i = 0;
   70     }
   71   
   72     /**
   73      * reset() resets the stemmer so it can stem another word.  If you invoke
   74      * the stemmer by calling add(char) and then stem(), you must call reset()
   75      * before starting another word.
   76      */
   77     public void reset() { i = 0; dirty = false; }
   78   
   79     /**
   80      * Add a character to the word being stemmed.  When you are finished
   81      * adding characters, you can call stem(void) to process the word.
   82      */
   83     public void add(char ch) {
   84       if (b.length <= i + EXTRA) {
   85         char[] new_b = new char[b.length+INC];
   86         System.arraycopy(b, 0, new_b, 0, b.length);
   87         b = new_b;
   88       }
   89       b[i++] = ch;
   90     }
   91   
   92     /**
   93      * After a word has been stemmed, it can be retrieved by toString(),
   94      * or a reference to the internal buffer can be retrieved by getResultBuffer
   95      * and getResultLength (which is generally more efficient.)
   96      */
   97     @Override
   98     public String toString() { return new String(b,0,i); }
   99   
  100     /**
  101      * Returns the length of the word resulting from the stemming process.
  102      */
  103     public int getResultLength() { return i; }
  104   
  105     /**
  106      * Returns a reference to a character buffer containing the results of
  107      * the stemming process.  You also need to consult getResultLength()
  108      * to determine the length of the result.
  109      */
  110     public char[] getResultBuffer() { return b; }
  111   
  112     /* cons(i) is true <=> b[i] is a consonant. */
  113   
  114     private final boolean cons(int i) {
  115       switch (b[i]) {
  116       case 'a': case 'e': case 'i': case 'o': case 'u':
  117         return false;
  118       case 'y':
  119         return (i==k0) ? true : !cons(i-1);
  120       default:
  121         return true;
  122       }
  123     }
  124   
  125     /* m() measures the number of consonant sequences between k0 and j. if c is
  126        a consonant sequence and v a vowel sequence, and <..> indicates arbitrary
  127        presence,
  128   
  129             <c><v>       gives 0
  130             <c>vc<v>     gives 1
  131             <c>vcvc<v>   gives 2
  132             <c>vcvcvc<v> gives 3
  133             ....
  134     */
  135   
  136     private final int m() {
  137       int n = 0;
  138       int i = k0;
  139       while(true) {
  140         if (i > j)
  141           return n;
  142         if (! cons(i))
  143           break;
  144         i++;
  145       }
  146       i++;
  147       while(true) {
  148         while(true) {
  149           if (i > j)
  150             return n;
  151           if (cons(i))
  152             break;
  153           i++;
  154         }
  155         i++;
  156         n++;
  157         while(true) {
  158           if (i > j)
  159             return n;
  160           if (! cons(i))
  161             break;
  162           i++;
  163         }
  164         i++;
  165       }
  166     }
  167   
  168     /* vowelinstem() is true <=> k0,...j contains a vowel */
  169   
  170     private final boolean vowelinstem() {
  171       int i;
  172       for (i = k0; i <= j; i++)
  173         if (! cons(i))
  174           return true;
  175       return false;
  176     }
  177   
  178     /* doublec(j) is true <=> j,(j-1) contain a double consonant. */
  179   
  180     private final boolean doublec(int j) {
  181       if (j < k0+1)
  182         return false;
  183       if (b[j] != b[j-1])
  184         return false;
  185       return cons(j);
  186     }
  187   
  188     /* cvc(i) is true <=> i-2,i-1,i has the form consonant - vowel - consonant
  189        and also if the second c is not w,x or y. this is used when trying to
  190        restore an e at the end of a short word. e.g.
  191   
  192             cav(e), lov(e), hop(e), crim(e), but
  193             snow, box, tray.
  194   
  195     */
  196   
  197     private final boolean cvc(int i) {
  198       if (i < k0+2 || !cons(i) || cons(i-1) || !cons(i-2))
  199         return false;
  200       else {
  201         int ch = b[i];
  202         if (ch == 'w' || ch == 'x' || ch == 'y') return false;
  203       }
  204       return true;
  205     }
  206   
  207     private final boolean ends(String s) {
  208       int l = s.length();
  209       int o = k-l+1;
  210       if (o < k0)
  211         return false;
  212       for (int i = 0; i < l; i++)
  213         if (b[o+i] != s.charAt(i))
  214           return false;
  215       j = k-l;
  216       return true;
  217     }
  218   
  219     /* setto(s) sets (j+1),...k to the characters in the string s, readjusting
  220        k. */
  221   
  222     void setto(String s) {
  223       int l = s.length();
  224       int o = j+1;
  225       for (int i = 0; i < l; i++)
  226         b[o+i] = s.charAt(i);
  227       k = j+l;
  228       dirty = true;
  229     }
  230   
  231     /* r(s) is used further down. */
  232   
  233     void r(String s) { if (m() > 0) setto(s); }
  234   
  235     /* step1() gets rid of plurals and -ed or -ing. e.g.
  236   
  237              caresses  ->  caress
  238              ponies    ->  poni
  239              ties      ->  ti
  240              caress    ->  caress
  241              cats      ->  cat
  242   
  243              feed      ->  feed
  244              agreed    ->  agree
  245              disabled  ->  disable
  246   
  247              matting   ->  mat
  248              mating    ->  mate
  249              meeting   ->  meet
  250              milling   ->  mill
  251              messing   ->  mess
  252   
  253              meetings  ->  meet
  254   
  255     */
  256   
  257     private final void step1() {
  258       if (b[k] == 's') {
  259         if (ends("sses")) k -= 2;
  260         else if (ends("ies")) setto("i");
  261         else if (b[k-1] != 's') k--;
  262       }
  263       if (ends("eed")) {
  264         if (m() > 0)
  265           k--;
  266       }
  267       else if ((ends("ed") || ends("ing")) && vowelinstem()) {
  268         k = j;
  269         if (ends("at")) setto("ate");
  270         else if (ends("bl")) setto("ble");
  271         else if (ends("iz")) setto("ize");
  272         else if (doublec(k)) {
  273           int ch = b[k--];
  274           if (ch == 'l' || ch == 's' || ch == 'z')
  275             k++;
  276         }
  277         else if (m() == 1 && cvc(k))
  278           setto("e");
  279       }
  280     }
  281   
  282     /* step2() turns terminal y to i when there is another vowel in the stem. */
  283   
  284     private final void step2() {
  285       if (ends("y") && vowelinstem()) {
  286         b[k] = 'i';
  287         dirty = true;
  288       }
  289     }
  290   
  291     /* step3() maps double suffices to single ones. so -ization ( = -ize plus
  292        -ation) maps to -ize etc. note that the string before the suffix must give
  293        m() > 0. */
  294   
  295     private final void step3() {
  296       if (k == k0) return; /* For Bug 1 */
  297       switch (b[k-1]) {
  298       case 'a':
  299         if (ends("ational")) { r("ate"); break; }
  300         if (ends("tional")) { r("tion"); break; }
  301         break;
  302       case 'c':
  303         if (ends("enci")) { r("ence"); break; }
  304         if (ends("anci")) { r("ance"); break; }
  305         break;
  306       case 'e':
  307         if (ends("izer")) { r("ize"); break; }
  308         break;
  309       case 'l':
  310         if (ends("bli")) { r("ble"); break; }
  311         if (ends("alli")) { r("al"); break; }
  312         if (ends("entli")) { r("ent"); break; }
  313         if (ends("eli")) { r("e"); break; }
  314         if (ends("ousli")) { r("ous"); break; }
  315         break;
  316       case 'o':
  317         if (ends("ization")) { r("ize"); break; }
  318         if (ends("ation")) { r("ate"); break; }
  319         if (ends("ator")) { r("ate"); break; }
  320         break;
  321       case 's':
  322         if (ends("alism")) { r("al"); break; }
  323         if (ends("iveness")) { r("ive"); break; }
  324         if (ends("fulness")) { r("ful"); break; }
  325         if (ends("ousness")) { r("ous"); break; }
  326         break;
  327       case 't':
  328         if (ends("aliti")) { r("al"); break; }
  329         if (ends("iviti")) { r("ive"); break; }
  330         if (ends("biliti")) { r("ble"); break; }
  331         break;
  332       case 'g':
  333         if (ends("logi")) { r("log"); break; }
  334       }
  335     }
  336   
  337     /* step4() deals with -ic-, -full, -ness etc. similar strategy to step3. */
  338   
  339     private final void step4() {
  340       switch (b[k]) {
  341       case 'e':
  342         if (ends("icate")) { r("ic"); break; }
  343         if (ends("ative")) { r(""); break; }
  344         if (ends("alize")) { r("al"); break; }
  345         break;
  346       case 'i':
  347         if (ends("iciti")) { r("ic"); break; }
  348         break;
  349       case 'l':
  350         if (ends("ical")) { r("ic"); break; }
  351         if (ends("ful")) { r(""); break; }
  352         break;
  353       case 's':
  354         if (ends("ness")) { r(""); break; }
  355         break;
  356       }
  357     }
  358   
  359     /* step5() takes off -ant, -ence etc., in context <c>vcvc<v>. */
  360   
  361     private final void step5() {
  362       if (k == k0) return; /* for Bug 1 */
  363       switch (b[k-1]) {
  364       case 'a':
  365         if (ends("al")) break;
  366         return;
  367       case 'c':
  368         if (ends("ance")) break;
  369         if (ends("ence")) break;
  370         return;
  371       case 'e':
  372         if (ends("er")) break; return;
  373       case 'i':
  374         if (ends("ic")) break; return;
  375       case 'l':
  376         if (ends("able")) break;
  377         if (ends("ible")) break; return;
  378       case 'n':
  379         if (ends("ant")) break;
  380         if (ends("ement")) break;
  381         if (ends("ment")) break;
  382         /* element etc. not stripped before the m */
  383         if (ends("ent")) break;
  384         return;
  385       case 'o':
  386         if (ends("ion") && j >= 0 && (b[j] == 's' || b[j] == 't')) break;
  387         /* j >= 0 fixes Bug 2 */
  388         if (ends("ou")) break;
  389         return;
  390         /* takes care of -ous */
  391       case 's':
  392         if (ends("ism")) break;
  393         return;
  394       case 't':
  395         if (ends("ate")) break;
  396         if (ends("iti")) break;
  397         return;
  398       case 'u':
  399         if (ends("ous")) break;
  400         return;
  401       case 'v':
  402         if (ends("ive")) break;
  403         return;
  404       case 'z':
  405         if (ends("ize")) break;
  406         return;
  407       default:
  408         return;
  409       }
  410       if (m() > 1)
  411         k = j;
  412     }
  413   
  414     /* step6() removes a final -e if m() > 1. */
  415   
  416     private final void step6() {
  417       j = k;
  418       if (b[k] == 'e') {
  419         int a = m();
  420         if (a > 1 || a == 1 && !cvc(k-1))
  421           k--;
  422       }
  423       if (b[k] == 'l' && doublec(k) && m() > 1)
  424         k--;
  425     }
  426   
  427   
  428     /**
  429      * Stem a word provided as a String.  Returns the result as a String.
  430      */
  431     public String stem(String s) {
  432       if (stem(s.toCharArray(), s.length()))
  433         return toString();
  434       else
  435         return s;
  436     }
  437   
  438     /** Stem a word contained in a char[].  Returns true if the stemming process
  439      * resulted in a word different from the input.  You can retrieve the
  440      * result with getResultLength()/getResultBuffer() or toString().
  441      */
  442     public boolean stem(char[] word) {
  443       return stem(word, word.length);
  444     }
  445   
  446     /** Stem a word contained in a portion of a char[] array.  Returns
  447      * true if the stemming process resulted in a word different from
  448      * the input.  You can retrieve the result with
  449      * getResultLength()/getResultBuffer() or toString().
  450      */
  451     public boolean stem(char[] wordBuffer, int offset, int wordLen) {
  452       reset();
  453       if (b.length < wordLen) {
  454         char[] new_b = new char[wordLen + EXTRA];
  455         b = new_b;
  456       }
  457       System.arraycopy(wordBuffer, offset, b, 0, wordLen);
  458       i = wordLen;
  459       return stem(0);
  460     }
  461   
  462     /** Stem a word contained in a leading portion of a char[] array.
  463      * Returns true if the stemming process resulted in a word different
  464      * from the input.  You can retrieve the result with
  465      * getResultLength()/getResultBuffer() or toString().
  466      */
  467     public boolean stem(char[] word, int wordLen) {
  468       return stem(word, 0, wordLen);
  469     }
  470   
  471     /** Stem the word placed into the Stemmer buffer through calls to add().
  472      * Returns true if the stemming process resulted in a word different
  473      * from the input.  You can retrieve the result with
  474      * getResultLength()/getResultBuffer() or toString().
  475      */
  476     public boolean stem() {
  477       return stem(0);
  478     }
  479   
  480     public boolean stem(int i0) {
  481       k = i - 1;
  482       k0 = i0;
  483       if (k > k0+1) {
  484         step1(); step2(); step3(); step4(); step5(); step6();
  485       }
  486       // Also, a word is considered dirty if we lopped off letters
  487       // Thanks to Ifigenia Vairelles for pointing this out.
  488       if (i != k+1)
  489         dirty = true;
  490       i = k+1;
  491       return dirty;
  492     }
  493   
  494     /** Test program for demonstrating the Stemmer.  It reads a file and
  495      * stems each word, writing the result to standard out.
  496      * Usage: Stemmer file-name
  497      */
  498     public static void main(String[] args) {
  499       PorterStemmer s = new PorterStemmer();
  500   
  501       for (int i = 0; i < args.length; i++) {
  502         try {
  503           InputStream in = new FileInputStream(args[i]);
  504           byte[] buffer = new byte[1024];
  505           int bufferLen, offset, ch;
  506   
  507           bufferLen = in.read(buffer);
  508           offset = 0;
  509           s.reset();
  510   
  511           while(true) {
  512             if (offset < bufferLen)
  513               ch = buffer[offset++];
  514             else {
  515               bufferLen = in.read(buffer);
  516               offset = 0;
  517               if (bufferLen < 0)
  518                 ch = -1;
  519               else
  520                 ch = buffer[offset++];
  521             }
  522   
  523             if (Character.isLetter((char) ch)) {
  524               s.add(Character.toLowerCase((char) ch));
  525             }
  526             else {
  527                s.stem();
  528                System.out.print(s.toString());
  529                s.reset();
  530                if (ch < 0)
  531                  break;
  532                else {
  533                  System.out.print((char) ch);
  534                }
  535              }
  536           }
  537   
  538           in.close();
  539         }
  540         catch (IOException e) {
  541           System.out.println("error reading " + args[i]);
  542         }
  543       }
  544     }
  545   }
  546   

Save This Page
Home » lucene-3.0.1-src » org.apache » lucene » analysis » [javadoc | source]