lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From dna...@apache.org
Subject cvs commit: jakarta-lucene/src/java/org/apache/lucene/search FuzzyTermEnum.java
Date Sun, 07 Nov 2004 23:41:50 GMT
dnaber      2004/11/07 15:41:50

  Modified:    src/java/org/apache/lucene/search FuzzyTermEnum.java
  Log:
  indent the same everywhere, no functional change
  
  Revision  Changes    Path
  1.11      +181 -184  jakarta-lucene/src/java/org/apache/lucene/search/FuzzyTermEnum.java
  
  Index: FuzzyTermEnum.java
  ===================================================================
  RCS file: /home/cvs/jakarta-lucene/src/java/org/apache/lucene/search/FuzzyTermEnum.java,v
  retrieving revision 1.10
  retrieving revision 1.11
  diff -u -r1.10 -r1.11
  --- FuzzyTermEnum.java	7 Nov 2004 23:27:24 -0000	1.10
  +++ FuzzyTermEnum.java	7 Nov 2004 23:41:50 -0000	1.11
  @@ -29,127 +29,127 @@
    */
   public final class FuzzyTermEnum extends FilteredTermEnum {
   
  -    /* This should be somewhere around the average long word.
  -     * If it is longer, we waste time and space. If it is shorter, we waste a
  -     * little bit of time growing the array as we encounter longer words.
  -     */
  -    private static final int TYPICAL_LONGEST_WORD_IN_INDEX = 19;
  -
  -    /* Allows us save time required to create a new array
  -     * everytime similarity is called.
  -     */
  -    private int[][] d;
  -
  -    private float similarity;
  -    private boolean endEnum = false;
  -
  -    private Term searchTerm = null;
  -    private final String field;
  -    private final String text;
  -    private final String prefix;
  -
  -    private final float minimumSimilarity;
  -    private final float scale_factor;
  -    private final int[] maxDistances = new int[TYPICAL_LONGEST_WORD_IN_INDEX];
  -
  -    /**
  -     * Creates a FuzzyTermEnum with an empty prefix and a minSimilarity of 0.5f.
  -     * 
  -     * @param reader
  -     * @param term
  -     * @throws IOException
  -     * @see #FuzzyTermEnum(IndexReader, Term, float, int)
  -     */
  -    public FuzzyTermEnum(IndexReader reader, Term term) throws IOException {
  -      this(reader, term, FuzzyQuery.defaultMinSimilarity, FuzzyQuery.defaultPrefixLength);
  -    }
  -    
  -    /**
  -     * Creates a FuzzyTermEnum with an empty prefix.
  -     * 
  -     * @param reader
  -     * @param term
  -     * @param minSimilarity
  -     * @throws IOException
  -     * @see #FuzzyTermEnum(IndexReader, Term, float, int)
  -     */
  -    public FuzzyTermEnum(IndexReader reader, Term term, float minSimilarity) throws IOException
{
  -      this(reader, term, minSimilarity, FuzzyQuery.defaultPrefixLength);
  -    }
  -    
  -    /**
  -     * Constructor for enumeration of all terms from specified <code>reader</code>
which share a prefix of
  -     * length <code>prefixLength</code> with <code>term</code>
and which have a fuzzy similarity &gt;
  -     * <code>minSimilarity</code>. 
  -     * 
  -     * @param reader Delivers terms.
  -     * @param term Pattern term.
  -     * @param minSimilarity Minimum required similarity for terms from the reader. Default
value is 0.5f.
  -     * @param prefixLength Length of required common prefix. Default value is 0.
  -     * @throws IOException
  -     */
  -    public FuzzyTermEnum(IndexReader reader, Term term, final float minSimilarity, final
int prefixLength) throws IOException {
  -        super();
  -        
  -        if (minSimilarity >= 1.0f)
  -          throw new IllegalArgumentException("minimumSimilarity cannot be greater than
or equal to 1");
  -        else if (minSimilarity < 0.0f)
  -          throw new IllegalArgumentException("minimumSimilarity cannot be less than 0");
  -        if(prefixLength < 0)
  -          throw new IllegalArgumentException("prefixLength cannot be less than 0");
  -
  -        this.minimumSimilarity = minSimilarity;
  -        this.scale_factor = 1.0f / (1.0f - minimumSimilarity);
  -        this.searchTerm = term;
  -        this.field = searchTerm.field();
  -
  -        //The prefix could be longer than the word.
  -        //It's kind of silly though.  It means we must match the entire word.
  -        final int fullSearchTermLength = searchTerm.text().length();
  -        final int realPrefixLength = prefixLength > fullSearchTermLength ? fullSearchTermLength
: prefixLength;
  +  /* This should be somewhere around the average long word.
  +   * If it is longer, we waste time and space. If it is shorter, we waste a
  +   * little bit of time growing the array as we encounter longer words.
  +   */
  +  private static final int TYPICAL_LONGEST_WORD_IN_INDEX = 19;
   
  -        this.text = searchTerm.text().substring(realPrefixLength);
  -        this.prefix = searchTerm.text().substring(0, realPrefixLength);
  +  /* Allows us save time required to create a new array
  +   * everytime similarity is called.
  +   */
  +  private int[][] d;
   
  -        initializeMaxDistances();
  -        this.d = initDistanceArray();
  +  private float similarity;
  +  private boolean endEnum = false;
   
  -        setEnum(reader.terms(new Term(searchTerm.field(), prefix)));
  -    }
  +  private Term searchTerm = null;
  +  private final String field;
  +  private final String text;
  +  private final String prefix;
  +
  +  private final float minimumSimilarity;
  +  private final float scale_factor;
  +  private final int[] maxDistances = new int[TYPICAL_LONGEST_WORD_IN_INDEX];
   
  -    /**
  -     * The termCompare method in FuzzyTermEnum uses Levenshtein distance to 
  -     * calculate the distance between the given term and the comparing term. 
  -     */
  -    protected final boolean termCompare(Term term) {
  -        if (field == term.field() && term.text().startsWith(prefix)) {
  -            final String target = term.text().substring(prefix.length());
  -            this.similarity = similarity(target);
  -            return (similarity > minimumSimilarity);
  -        }
  -        endEnum = true;
  -        return false;
  -    }
  -    
  -    public final float difference() {
  -        return (float)((similarity - minimumSimilarity) * scale_factor);
  -    }
  +  /**
  +   * Creates a FuzzyTermEnum with an empty prefix and a minSimilarity of 0.5f.
  +   * 
  +   * @param reader
  +   * @param term
  +   * @throws IOException
  +   * @see #FuzzyTermEnum(IndexReader, Term, float, int)
  +   */
  +  public FuzzyTermEnum(IndexReader reader, Term term) throws IOException {
  +    this(reader, term, FuzzyQuery.defaultMinSimilarity, FuzzyQuery.defaultPrefixLength);
  +  }
       
  -    public final boolean endEnum() {
  -        return endEnum;
  -    }
  +  /**
  +   * Creates a FuzzyTermEnum with an empty prefix.
  +   * 
  +   * @param reader
  +   * @param term
  +   * @param minSimilarity
  +   * @throws IOException
  +   * @see #FuzzyTermEnum(IndexReader, Term, float, int)
  +   */
  +  public FuzzyTermEnum(IndexReader reader, Term term, float minSimilarity) throws IOException
{
  +    this(reader, term, minSimilarity, FuzzyQuery.defaultPrefixLength);
  +  }
       
  -    /******************************
  -     * Compute Levenshtein distance
  -     ******************************/
  +  /**
  +   * Constructor for enumeration of all terms from specified <code>reader</code>
which share a prefix of
  +   * length <code>prefixLength</code> with <code>term</code> and
which have a fuzzy similarity &gt;
  +   * <code>minSimilarity</code>. 
  +   * 
  +   * @param reader Delivers terms.
  +   * @param term Pattern term.
  +   * @param minSimilarity Minimum required similarity for terms from the reader. Default
value is 0.5f.
  +   * @param prefixLength Length of required common prefix. Default value is 0.
  +   * @throws IOException
  +   */
  +  public FuzzyTermEnum(IndexReader reader, Term term, final float minSimilarity, final
int prefixLength) throws IOException {
  +    super();
       
  -    /**
  -     * Finds and returns the smallest of three integers 
  -     */
  -    private static final int min(int a, int b, int c) {
  -        final int t = (a < b) ? a : b;
  -        return (t < c) ? t : c;
  +    if (minSimilarity >= 1.0f)
  +      throw new IllegalArgumentException("minimumSimilarity cannot be greater than or equal
to 1");
  +    else if (minSimilarity < 0.0f)
  +      throw new IllegalArgumentException("minimumSimilarity cannot be less than 0");
  +    if(prefixLength < 0)
  +      throw new IllegalArgumentException("prefixLength cannot be less than 0");
  +
  +    this.minimumSimilarity = minSimilarity;
  +    this.scale_factor = 1.0f / (1.0f - minimumSimilarity);
  +    this.searchTerm = term;
  +    this.field = searchTerm.field();
  +
  +    //The prefix could be longer than the word.
  +    //It's kind of silly though.  It means we must match the entire word.
  +    final int fullSearchTermLength = searchTerm.text().length();
  +    final int realPrefixLength = prefixLength > fullSearchTermLength ? fullSearchTermLength
: prefixLength;
  +
  +    this.text = searchTerm.text().substring(realPrefixLength);
  +    this.prefix = searchTerm.text().substring(0, realPrefixLength);
  +
  +    initializeMaxDistances();
  +    this.d = initDistanceArray();
  +
  +    setEnum(reader.terms(new Term(searchTerm.field(), prefix)));
  +  }
  +
  +  /**
  +   * The termCompare method in FuzzyTermEnum uses Levenshtein distance to 
  +   * calculate the distance between the given term and the comparing term. 
  +   */
  +  protected final boolean termCompare(Term term) {
  +    if (field == term.field() && term.text().startsWith(prefix)) {
  +        final String target = term.text().substring(prefix.length());
  +        this.similarity = similarity(target);
  +        return (similarity > minimumSimilarity);
       }
  +    endEnum = true;
  +    return false;
  +  }
  +  
  +  public final float difference() {
  +    return (float)((similarity - minimumSimilarity) * scale_factor);
  +  }
  +  
  +  public final boolean endEnum() {
  +    return endEnum;
  +  }
  +  
  +  /******************************
  +   * Compute Levenshtein distance
  +   ******************************/
  +  
  +  /**
  +   * Finds and returns the smallest of three integers 
  +   */
  +  private static final int min(int a, int b, int c) {
  +    final int t = (a < b) ? a : b;
  +    return (t < c) ? t : c;
  +  }
   
     private final int[][] initDistanceArray(){
       return new int[this.text.length() + 1][TYPICAL_LONGEST_WORD_IN_INDEX];
  @@ -192,81 +192,79 @@
      * @return the similarity,  0.0 or less indicates that it matches less than the required
      * threshold and 1.0 indicates that the text and target are identical
      */
  -    private synchronized final float similarity(final String target) {
  -        final int m = target.length();
  -        final int n = text.length();
  -        if (n == 0)  {
  -          //we don't have antyhing to compare.  That means if we just add
  -          //the letters for m we get the new word
  -          return prefix.length() == 0 ? 0.0f : 1.0f - ((float) m / prefix.length());
  -        }
  -        if (m == 0) {
  -          return prefix.length() == 0 ? 0.0f : 1.0f - ((float) n / prefix.length());
  -        }
  -
  -        final int maxDistance = getMaxDistance(m);
  -
  -        if (maxDistance < Math.abs(m-n)) {
  -          //just adding the characters of m to n or vice-versa results in
  -          //too many edits
  -          //for example "pre" length is 3 and "prefixes" length is 8.  We can see that
  -          //given this optimal circumstance, the edit distance cannot be less than 5.
  -          //which is 8-3 or more precisesly Math.abs(3-8).
  -          //if our maximum edit distance is 4, than we can discard this word
  -          //without looking at it.
  -          return 0.0f;
  -        }
  -
  -        //let's make sure we have enough room in our array to do the distance calculations.
  -        if (d[0].length <= m) {
  -          growDistanceArray(m);
  -        }
  -
  -        // init matrix d
  -        for (int i = 0; i <= n; i++) d[i][0] = i;
  -        for (int j = 0; j <= m; j++) d[0][j] = j;
  -        
  -        // start computing edit distance
  -        for (int i = 1; i <= n; i++) {
  -            int bestPossibleEditDistance = m;
  -            final char s_i = text.charAt(i - 1);
  -            for (int j = 1; j <= m; j++) {
  -                if (s_i != target.charAt(j-1)) {
  -                    d[i][j] = min(d[i-1][j], d[i][j-1], d[i-1][j-1])+1;
  -                }
  -                else {
  -                  d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]);
  -                }
  -                bestPossibleEditDistance = Math.min(bestPossibleEditDistance, d[i][j]);
  -            }
  -
  -          //After calculating row i, the best possible edit distance
  -          //can be found by found by finding the smallest value in a given column.
  -          //If the bestPossibleEditDistance is greater than the max distance, abort.
  -
  -          if (i > maxDistance && bestPossibleEditDistance > maxDistance)
{  //equal is okay, but not greater
  -            //the closest the target can be to the text is just too far away.
  -            //this target is leaving the party early.
  -            return 0.0f;
  -          }
  -        }
  -
  -        // this will return less than 0.0 when the edit distance is
  -        // greater than the number of characters in the shorter word.
  -        // but this was the formula that was previously used in FuzzyTermEnum,
  -        // so it has not been changed (even though minimumSimilarity must be
  -        // greater than 0.0)
  -        return 1.0f - ((float)d[n][m] / (float) (prefix.length() + Math.min(n, m)));
  -
  -    }
  +  private synchronized final float similarity(final String target) {
  +    final int m = target.length();
  +    final int n = text.length();
  +    if (n == 0)  {
  +      //we don't have antyhing to compare.  That means if we just add
  +      //the letters for m we get the new word
  +      return prefix.length() == 0 ? 0.0f : 1.0f - ((float) m / prefix.length());
  +    }
  +    if (m == 0) {
  +      return prefix.length() == 0 ? 0.0f : 1.0f - ((float) n / prefix.length());
  +    }
  +
  +    final int maxDistance = getMaxDistance(m);
  +
  +    if (maxDistance < Math.abs(m-n)) {
  +      //just adding the characters of m to n or vice-versa results in
  +      //too many edits
  +      //for example "pre" length is 3 and "prefixes" length is 8.  We can see that
  +      //given this optimal circumstance, the edit distance cannot be less than 5.
  +      //which is 8-3 or more precisesly Math.abs(3-8).
  +      //if our maximum edit distance is 4, than we can discard this word
  +      //without looking at it.
  +      return 0.0f;
  +    }
  +
  +    //let's make sure we have enough room in our array to do the distance calculations.
  +    if (d[0].length <= m) {
  +      growDistanceArray(m);
  +    }
  +
  +    // init matrix d
  +    for (int i = 0; i <= n; i++) d[i][0] = i;
  +    for (int j = 0; j <= m; j++) d[0][j] = j;
  +    
  +    // start computing edit distance
  +    for (int i = 1; i <= n; i++) {
  +      int bestPossibleEditDistance = m;
  +      final char s_i = text.charAt(i - 1);
  +      for (int j = 1; j <= m; j++) {
  +        if (s_i != target.charAt(j-1)) {
  +            d[i][j] = min(d[i-1][j], d[i][j-1], d[i-1][j-1])+1;
  +        }
  +        else {
  +          d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]);
  +        }
  +        bestPossibleEditDistance = Math.min(bestPossibleEditDistance, d[i][j]);
  +      }
  +
  +      //After calculating row i, the best possible edit distance
  +      //can be found by found by finding the smallest value in a given column.
  +      //If the bestPossibleEditDistance is greater than the max distance, abort.
  +
  +      if (i > maxDistance && bestPossibleEditDistance > maxDistance) {  //equal
is okay, but not greater
  +        //the closest the target can be to the text is just too far away.
  +        //this target is leaving the party early.
  +        return 0.0f;
  +      }
  +    }
  +
  +    // this will return less than 0.0 when the edit distance is
  +    // greater than the number of characters in the shorter word.
  +    // but this was the formula that was previously used in FuzzyTermEnum,
  +    // so it has not been changed (even though minimumSimilarity must be
  +    // greater than 0.0)
  +    return 1.0f - ((float)d[n][m] / (float) (prefix.length() + Math.min(n, m)));
  +  }
   
     /**
      * Grow the second dimension of the array, so that we can calculate the
      * Levenshtein difference.
      */
     private void growDistanceArray(int m) {
  -    for (int i = 0; i < d.length; i++)
  -    {
  +    for (int i = 0; i < d.length; i++) {
         d[i] = new int[m+1];
       }
     }
  @@ -283,8 +281,7 @@
     }
   
     private void initializeMaxDistances() {
  -    for (int i = 0; i < maxDistances.length; i++)
  -    {
  +    for (int i = 0; i < maxDistances.length; i++) {
         maxDistances[i] = calculateMaxDistance(i);
       }
     }
  
  
  

---------------------------------------------------------------------
To unsubscribe, e-mail: lucene-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: lucene-dev-help@jakarta.apache.org


Mime
View raw message