src/Lucene.Net/Search/FuzzyTermsEnum.cs - lucenenet - Git at Google

 using J2N;
 using Lucene.Net.Index;
 using Lucene.Net.Support;
 using Lucene.Net.Util;
 using System;
 using System.Collections.Generic;
 using System.Diagnostics;
 using System.Linq;
 using JCG = J2N.Collections.Generic;

 namespace Lucene.Net.Search
 {
     /*
      * Licensed to the Apache Software Foundation (ASF) under one or more
      * contributor license agreements.  See the NOTICE file distributed with
      * this work for additional information regarding copyright ownership.
      * The ASF licenses this file to You under the Apache License, Version 2.0
      * (the "License"); you may not use this file except in compliance with
      * the License.  You may obtain a copy of the License at
      *
      *     http://www.apache.org/licenses/LICENSE-2.0
      *
      * Unless required by applicable law or agreed to in writing, software
      * distributed under the License is distributed on an "AS IS" BASIS,
      * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      * See the License for the specific language governing permissions and
      * limitations under the License.
      */

     using Attribute = Lucene.Net.Util.Attribute;
     using AttributeSource = Lucene.Net.Util.AttributeSource;
     using Automaton = Lucene.Net.Util.Automaton.Automaton;
     using BasicAutomata = Lucene.Net.Util.Automaton.BasicAutomata;
     using BasicOperations = Lucene.Net.Util.Automaton.BasicOperations;
     using IBits = Lucene.Net.Util.IBits;
     using ByteRunAutomaton = Lucene.Net.Util.Automaton.ByteRunAutomaton;
     using BytesRef = Lucene.Net.Util.BytesRef;
     using CompiledAutomaton = Lucene.Net.Util.Automaton.CompiledAutomaton;
     using DocsAndPositionsEnum = Lucene.Net.Index.DocsAndPositionsEnum;
     using DocsEnum = Lucene.Net.Index.DocsEnum;
     using FilteredTermsEnum = Lucene.Net.Index.FilteredTermsEnum;
     using LevenshteinAutomata = Lucene.Net.Util.Automaton.LevenshteinAutomata;
     using Term = Lucene.Net.Index.Term;
     using Terms = Lucene.Net.Index.Terms;
     using TermsEnum = Lucene.Net.Index.TermsEnum;
     using TermState = Lucene.Net.Index.TermState;
     using UnicodeUtil = Lucene.Net.Util.UnicodeUtil;

     /// <summary>
     /// Subclass of <see cref="TermsEnum"/> for enumerating all terms that are similar
     /// to the specified filter term.
     ///
     /// <para>Term enumerations are always ordered by
     /// <see cref="Comparer"/>.  Each term in the enumeration is
     /// greater than all that precede it.</para>
     /// </summary>
     public class FuzzyTermsEnum : TermsEnum
     {
         private void InitializeInstanceFields()
         {
             boostAtt = Attributes.AddAttribute<IBoostAttribute>();
         }

         private TermsEnum actualEnum;
         private IBoostAttribute actualBoostAtt;

         private IBoostAttribute boostAtt;

         private readonly IMaxNonCompetitiveBoostAttribute maxBoostAtt;
         private readonly ILevenshteinAutomataAttribute dfaAtt;

         private float bottom;
         private BytesRef bottomTerm;

         // TODO: chicken-and-egg
         private readonly IComparer<BytesRef> termComparer = BytesRef.UTF8SortedAsUnicodeComparer;

         protected readonly float m_minSimilarity;
         protected readonly float m_scaleFactor;

         protected readonly int m_termLength;

         protected int m_maxEdits;
         protected readonly bool m_raw;

         protected readonly Terms m_terms;
         private readonly Term term;
         protected readonly int[] m_termText;
         protected readonly int m_realPrefixLength;

         private readonly bool transpositions;

         /// <summary>
         /// Constructor for enumeration of all terms from specified <c>reader</c> which share a prefix of
         /// length <paramref name="prefixLength"/> with <paramref name="term"/> and which have a fuzzy similarity &gt;
         /// <paramref name="minSimilarity"/>.
         /// <para/>
         /// After calling the constructor the enumeration is already pointing to the first
         /// valid term if such a term exists.
         /// </summary>
         /// <param name="terms"> Delivers terms. </param>
         /// <param name="atts"> <see cref="AttributeSource"/> created by the rewrite method of <see cref="MultiTermQuery"/>
         /// thats contains information about competitive boosts during rewrite. It is also used
         /// to cache DFAs between segment transitions. </param>
         /// <param name="term"> Pattern term. </param>
         /// <param name="minSimilarity"> Minimum required similarity for terms from the reader. Pass an integer value
         ///        representing edit distance. Passing a fraction is deprecated. </param>
         /// <param name="prefixLength"> Length of required common prefix. Default value is 0. </param>
         /// <param name="transpositions"> Transpositions </param>
         /// <exception cref="System.IO.IOException"> if there is a low-level IO error </exception>
         public FuzzyTermsEnum(Terms terms, AttributeSource atts, Term term, float minSimilarity, int prefixLength, bool transpositions)
         {
             InitializeInstanceFields();
             if (minSimilarity >= 1.0f && minSimilarity != (int)minSimilarity)
             {
                 throw new ArgumentException("fractional edit distances are not allowed");
             }
             if (minSimilarity < 0.0f)
             {
                 throw new ArgumentException("minimumSimilarity cannot be less than 0");
             }
             if (prefixLength < 0)
             {
                 throw new ArgumentException("prefixLength cannot be less than 0");
             }
             this.m_terms = terms;
             this.term = term;

             // convert the string into a utf32 int[] representation for fast comparisons
             string utf16 = term.Text();
             this.m_termText = new int[utf16.CodePointCount(0, utf16.Length)];
             for (int cp, i = 0, j = 0; i < utf16.Length; i += Character.CharCount(cp))
             {
                 m_termText[j++] = cp = utf16.CodePointAt(i);
             }
             this.m_termLength = m_termText.Length;
             this.dfaAtt = atts.AddAttribute<ILevenshteinAutomataAttribute>();

             //The prefix could be longer than the word.
             //It's kind of silly though.  It means we must match the entire word.
             this.m_realPrefixLength = prefixLength > m_termLength ? m_termLength : prefixLength;
             // if minSimilarity >= 1, we treat it as number of edits
             if (minSimilarity >= 1f)
             {
                 this.m_minSimilarity = 0; // just driven by number of edits
                 m_maxEdits = (int)minSimilarity;
                 m_raw = true;
             }
             else
             {
                 this.m_minSimilarity = minSimilarity;
                 // calculate the maximum k edits for this similarity
                 m_maxEdits = InitialMaxDistance(this.m_minSimilarity, m_termLength);
                 m_raw = false;
             }
             if (transpositions && m_maxEdits > LevenshteinAutomata.MAXIMUM_SUPPORTED_DISTANCE)
             {
                 throw new System.NotSupportedException("with transpositions enabled, distances > " + LevenshteinAutomata.MAXIMUM_SUPPORTED_DISTANCE + " are not supported ");
             }
             this.transpositions = transpositions;
             this.m_scaleFactor = 1.0f / (1.0f - this.m_minSimilarity);

             this.maxBoostAtt = atts.AddAttribute<IMaxNonCompetitiveBoostAttribute>();
             bottom = maxBoostAtt.MaxNonCompetitiveBoost;
             bottomTerm = maxBoostAtt.CompetitiveTerm;
             BottomChanged(null, true);
         }

         /// <summary>
         /// Return an automata-based enum for matching up to <paramref name="editDistance"/> from
         /// <paramref name="lastTerm"/>, if possible
         /// </summary>
         protected virtual TermsEnum GetAutomatonEnum(int editDistance, BytesRef lastTerm)
         {
             IList<CompiledAutomaton> runAutomata = InitAutomata(editDistance);
             if (editDistance < runAutomata.Count)
             {
                 //if (BlockTreeTermsWriter.DEBUG) System.out.println("FuzzyTE.getAEnum: ed=" + editDistance + " lastTerm=" + (lastTerm==null ? "null" : lastTerm.utf8ToString()));
                 CompiledAutomaton compiled = runAutomata[editDistance];
                 return new AutomatonFuzzyTermsEnum(this, m_terms.Intersect(compiled, lastTerm == null ? null : compiled.Floor(lastTerm, new BytesRef())), runAutomata.SubList(0, editDistance + 1).ToArray(/*new CompiledAutomaton[editDistance + 1]*/));
             }
             else
             {
                 return null;
             }
         }

         /// <summary>
         /// Initialize levenshtein DFAs up to maxDistance, if possible </summary>
         private IList<CompiledAutomaton> InitAutomata(int maxDistance)
         {
             IList<CompiledAutomaton> runAutomata = dfaAtt.Automata;
             //System.out.println("cached automata size: " + runAutomata.size());
             if (runAutomata.Count <= maxDistance && maxDistance <= LevenshteinAutomata.MAXIMUM_SUPPORTED_DISTANCE)
             {
                 LevenshteinAutomata builder = new LevenshteinAutomata(UnicodeUtil.NewString(m_termText, m_realPrefixLength, m_termText.Length - m_realPrefixLength), transpositions);

                 for (int i = runAutomata.Count; i <= maxDistance; i++)
                 {
                     Automaton a = builder.ToAutomaton(i);
                     //System.out.println("compute automaton n=" + i);
                     // constant prefix
                     if (m_realPrefixLength > 0)
                     {
                         Automaton prefix = BasicAutomata.MakeString(UnicodeUtil.NewString(m_termText, 0, m_realPrefixLength));
                         a = BasicOperations.Concatenate(prefix, a);
                     }
                     runAutomata.Add(new CompiledAutomaton(a, true, false));
                 }
             }
             return runAutomata;
         }

         /// <summary>
         /// Swap in a new actual enum to proxy to </summary>
         protected virtual void SetEnum(TermsEnum actualEnum)
         {
             this.actualEnum = actualEnum;
             this.actualBoostAtt = actualEnum.Attributes.AddAttribute<IBoostAttribute>();
         }

         /// <summary>
         /// Fired when the max non-competitive boost has changed. This is the hook to
         /// swap in a smarter actualEnum
         /// </summary>
         private void BottomChanged(BytesRef lastTerm, bool init)
         {
             int oldMaxEdits = m_maxEdits;

             // true if the last term encountered is lexicographically equal or after the bottom term in the PQ
             bool termAfter = bottomTerm == null || (lastTerm != null && termComparer.Compare(lastTerm, bottomTerm) >= 0);

             // as long as the max non-competitive boost is >= the max boost
             // for some edit distance, keep dropping the max edit distance.
             while (m_maxEdits > 0 && (termAfter ? bottom >= CalculateMaxBoost(m_maxEdits) : bottom > CalculateMaxBoost(m_maxEdits)))
             {
                 m_maxEdits--;
             }

             if (oldMaxEdits != m_maxEdits || init) // the maximum n has changed
             {
                 MaxEditDistanceChanged(lastTerm, m_maxEdits, init);
             }
         }

         protected virtual void MaxEditDistanceChanged(BytesRef lastTerm, int maxEdits, bool init)
         {
             TermsEnum newEnum = GetAutomatonEnum(maxEdits, lastTerm);
             // instead of assert, we do a hard check in case someone uses our enum directly
             // assert newEnum != null;
             if (newEnum == null)
             {
                 Debug.Assert(maxEdits > LevenshteinAutomata.MAXIMUM_SUPPORTED_DISTANCE);
                 throw new System.ArgumentException("maxEdits cannot be > LevenshteinAutomata.MAXIMUM_SUPPORTED_DISTANCE");
             }
             SetEnum(newEnum);
         }

         // for some raw min similarity and input term length, the maximum # of edits
         private int InitialMaxDistance(float minimumSimilarity, int termLen)
         {
             return (int)((1D - minimumSimilarity) * termLen);
         }

         // for some number of edits, the maximum possible scaled boost
         private float CalculateMaxBoost(int nEdits)
         {
             float similarity = 1.0f - ((float)nEdits / (float)(m_termLength));
             return (similarity - m_minSimilarity) * m_scaleFactor;
         }

         private BytesRef queuedBottom = null;

         public override BytesRef Next()
         {
             if (queuedBottom != null)
             {
                 BottomChanged(queuedBottom, false);
                 queuedBottom = null;
             }

             BytesRef term = actualEnum.Next();
             boostAtt.Boost = actualBoostAtt.Boost;

             float bottom = maxBoostAtt.MaxNonCompetitiveBoost;
             BytesRef bottomTerm = maxBoostAtt.CompetitiveTerm;
             if (term != null && (bottom != this.bottom || bottomTerm != this.bottomTerm))
             {
                 this.bottom = bottom;
                 this.bottomTerm = bottomTerm;
                 // clone the term before potentially doing something with it
                 // this is a rare but wonderful occurrence anyway
                 queuedBottom = BytesRef.DeepCopyOf(term);
             }

             return term;
         }

         // proxy all other enum calls to the actual enum
         public override int DocFreq
         {
             get { return actualEnum.DocFreq; }
         }

         public override long TotalTermFreq
         {
             get { return actualEnum.TotalTermFreq; }
         }

         public override DocsEnum Docs(IBits liveDocs, DocsEnum reuse, DocsFlags flags)
         {
             return actualEnum.Docs(liveDocs, reuse, flags);
         }

         public override DocsAndPositionsEnum DocsAndPositions(IBits liveDocs, DocsAndPositionsEnum reuse, DocsAndPositionsFlags flags)
         {
             return actualEnum.DocsAndPositions(liveDocs, reuse, flags);
         }

         public override void SeekExact(BytesRef term, TermState state)
         {
             actualEnum.SeekExact(term, state);
         }

         public override TermState GetTermState()
         {
             return actualEnum.GetTermState();
         }

         public override IComparer<BytesRef> Comparer => actualEnum.Comparer;

         public override long Ord => actualEnum.Ord;

         public override bool SeekExact(BytesRef text)
         {
             return actualEnum.SeekExact(text);
         }

         public override SeekStatus SeekCeil(BytesRef text)
         {
             return actualEnum.SeekCeil(text);
         }

         public override void SeekExact(long ord)
         {
             actualEnum.SeekExact(ord);
         }

         public override BytesRef Term => actualEnum.Term;

         /// <summary>
         /// Implement fuzzy enumeration with <see cref="Terms.Intersect(CompiledAutomaton, BytesRef)"/>.
         /// <para/>
         /// This is the fastest method as opposed to LinearFuzzyTermsEnum:
         /// as enumeration is logarithmic to the number of terms (instead of linear)
         /// and comparison is linear to length of the term (rather than quadratic)
         /// </summary>
         private class AutomatonFuzzyTermsEnum : FilteredTermsEnum
         {
             internal virtual void InitializeInstanceFields()
             {
                 boostAtt = Attributes.AddAttribute<IBoostAttribute>();
             }

             private readonly FuzzyTermsEnum outerInstance;

             private readonly ByteRunAutomaton[] matchers;

             private readonly BytesRef termRef;

             private IBoostAttribute boostAtt;

             public AutomatonFuzzyTermsEnum(FuzzyTermsEnum outerInstance, TermsEnum tenum, CompiledAutomaton[] compiled)
                 : base(tenum, false)
             {
                 this.outerInstance = outerInstance;

                 InitializeInstanceFields();
                 this.matchers = new ByteRunAutomaton[compiled.Length];
                 for (int i = 0; i < compiled.Length; i++)
                 {
                     this.matchers[i] = compiled[i].RunAutomaton;
                 }
                 termRef = new BytesRef(outerInstance.term.Text());
             }

             /// <summary>
             /// Finds the smallest Lev(n) DFA that accepts the term. </summary>
             protected override AcceptStatus Accept(BytesRef term)
             {
                 //System.out.println("AFTE.accept term=" + term);
                 int ed = matchers.Length - 1;

                 // we are wrapping either an intersect() TermsEnum or an AutomatonTermsENum,
                 // so we know the outer DFA always matches.
                 // now compute exact edit distance
                 while (ed > 0)
                 {
                     if (Matches(term, ed - 1))
                     {
                         ed--;
                     }
                     else
                     {
                         break;
                     }
                 }
                 //System.out.println("CHECK term=" + term.utf8ToString() + " ed=" + ed);

                 // scale to a boost and return (if similarity > minSimilarity)
                 if (ed == 0) // exact match
                 {
                     boostAtt.Boost = 1.0F;
                     //System.out.println("  yes");
                     return AcceptStatus.YES;
                 }
                 else
                 {
                     int codePointCount = UnicodeUtil.CodePointCount(term);
                     float similarity = 1.0f - ((float)ed / (float)(Math.Min(codePointCount, outerInstance.m_termLength)));
                     if (similarity > outerInstance.m_minSimilarity)
                     {
                         boostAtt.Boost = (similarity - outerInstance.m_minSimilarity) * outerInstance.m_scaleFactor;
                         //System.out.println("  yes");
                         return AcceptStatus.YES;
                     }
                     else
                     {
                         return AcceptStatus.NO;
                     }
                 }
             }

             /// <summary>
             /// Returns <c>true</c> if <paramref name="term"/> is within <paramref name="k"/> edits of the query term </summary>
             internal bool Matches(BytesRef term, int k)
             {
                 return k == 0 ? term.Equals(termRef) : matchers[k].Run(term.Bytes, term.Offset, term.Length);
             }
         }

         /// <summary>
         /// @lucene.internal </summary>
         public virtual float MinSimilarity => m_minSimilarity;

         /// <summary>
         /// @lucene.internal </summary>
         public virtual float ScaleFactor => m_scaleFactor;

         /// <summary>
         /// Reuses compiled automata across different segments,
         /// because they are independent of the index
         /// <para/>
         /// @lucene.internal
         /// </summary>
         public interface ILevenshteinAutomataAttribute : IAttribute
         {
             IList<CompiledAutomaton> Automata { get; }
         }

         /// <summary>
         /// Stores compiled automata as a list (indexed by edit distance)
         /// <para/>
         /// @lucene.internal
         /// </summary>
         public sealed class LevenshteinAutomataAttribute : Attribute, ILevenshteinAutomataAttribute
         {
             // LUCENENET NOTE: Must use JCG.List for Equals and GetHashCode()
             private readonly IList<CompiledAutomaton> automata = new JCG.List<CompiledAutomaton>();

             public IList<CompiledAutomaton> Automata
             {
                 get { return automata; }
             }

             public override void Clear()
             {
                 automata.Clear();
             }

             public override int GetHashCode()
             {
                 return automata.GetHashCode();
             }

             public override bool Equals(object other)
             {
                 if (this == other)
                 {
                     return true;
                 }
                 if (!(other is LevenshteinAutomataAttribute))
                 {
                     return false;
                 }
                 return automata.Equals(((LevenshteinAutomataAttribute)other).automata);
             }

             public override void CopyTo(IAttribute target)
             {
                 IList<CompiledAutomaton> targetAutomata = ((LevenshteinAutomataAttribute)target).Automata;
                 targetAutomata.Clear();
                 targetAutomata.AddRange(automata);
             }
         }
     }
 }
	using J2N;
	using Lucene.Net.Index;
	using Lucene.Net.Support;
	using Lucene.Net.Util;
	using System;
	using System.Collections.Generic;
	using System.Diagnostics;
	using System.Linq;
	using JCG = J2N.Collections.Generic;

	namespace Lucene.Net.Search
	{
	/*
	* Licensed to the Apache Software Foundation (ASF) under one or more
	* contributor license agreements. See the NOTICE file distributed with
	* this work for additional information regarding copyright ownership.
	* The ASF licenses this file to You under the Apache License, Version 2.0
	* (the "License"); you may not use this file except in compliance with
	* the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	using Attribute = Lucene.Net.Util.Attribute;
	using AttributeSource = Lucene.Net.Util.AttributeSource;
	using Automaton = Lucene.Net.Util.Automaton.Automaton;
	using BasicAutomata = Lucene.Net.Util.Automaton.BasicAutomata;
	using BasicOperations = Lucene.Net.Util.Automaton.BasicOperations;
	using IBits = Lucene.Net.Util.IBits;
	using ByteRunAutomaton = Lucene.Net.Util.Automaton.ByteRunAutomaton;
	using BytesRef = Lucene.Net.Util.BytesRef;
	using CompiledAutomaton = Lucene.Net.Util.Automaton.CompiledAutomaton;
	using DocsAndPositionsEnum = Lucene.Net.Index.DocsAndPositionsEnum;
	using DocsEnum = Lucene.Net.Index.DocsEnum;
	using FilteredTermsEnum = Lucene.Net.Index.FilteredTermsEnum;
	using LevenshteinAutomata = Lucene.Net.Util.Automaton.LevenshteinAutomata;
	using Term = Lucene.Net.Index.Term;
	using Terms = Lucene.Net.Index.Terms;
	using TermsEnum = Lucene.Net.Index.TermsEnum;
	using TermState = Lucene.Net.Index.TermState;
	using UnicodeUtil = Lucene.Net.Util.UnicodeUtil;

	/// <summary>
	/// Subclass of <see cref="TermsEnum"/> for enumerating all terms that are similar
	/// to the specified filter term.
	///
	/// <para>Term enumerations are always ordered by
	/// <see cref="Comparer"/>. Each term in the enumeration is
	/// greater than all that precede it.</para>
	/// </summary>
	public class FuzzyTermsEnum : TermsEnum
	{
	private void InitializeInstanceFields()
	{
	boostAtt = Attributes.AddAttribute<IBoostAttribute>();
	}

	private TermsEnum actualEnum;
	private IBoostAttribute actualBoostAtt;

	private IBoostAttribute boostAtt;

	private readonly IMaxNonCompetitiveBoostAttribute maxBoostAtt;
	private readonly ILevenshteinAutomataAttribute dfaAtt;

	private float bottom;
	private BytesRef bottomTerm;

	// TODO: chicken-and-egg
	private readonly IComparer<BytesRef> termComparer = BytesRef.UTF8SortedAsUnicodeComparer;

	protected readonly float m_minSimilarity;
	protected readonly float m_scaleFactor;

	protected readonly int m_termLength;

	protected int m_maxEdits;
	protected readonly bool m_raw;

	protected readonly Terms m_terms;
	private readonly Term term;
	protected readonly int[] m_termText;
	protected readonly int m_realPrefixLength;

	private readonly bool transpositions;

	/// <summary>
	/// Constructor for enumeration of all terms from specified <c>reader</c> which share a prefix of
	/// length <paramref name="prefixLength"/> with <paramref name="term"/> and which have a fuzzy similarity >
	/// <paramref name="minSimilarity"/>.
	/// <para/>
	/// After calling the constructor the enumeration is already pointing to the first
	/// valid term if such a term exists.
	/// </summary>
	/// <param name="terms"> Delivers terms. </param>
	/// <param name="atts"> <see cref="AttributeSource"/> created by the rewrite method of <see cref="MultiTermQuery"/>
	/// thats contains information about competitive boosts during rewrite. It is also used
	/// to cache DFAs between segment transitions. </param>
	/// <param name="term"> Pattern term. </param>
	/// <param name="minSimilarity"> Minimum required similarity for terms from the reader. Pass an integer value
	/// representing edit distance. Passing a fraction is deprecated. </param>
	/// <param name="prefixLength"> Length of required common prefix. Default value is 0. </param>
	/// <param name="transpositions"> Transpositions </param>
	/// <exception cref="System.IO.IOException"> if there is a low-level IO error </exception>
	public FuzzyTermsEnum(Terms terms, AttributeSource atts, Term term, float minSimilarity, int prefixLength, bool transpositions)
	{
	InitializeInstanceFields();
	if (minSimilarity >= 1.0f && minSimilarity != (int)minSimilarity)
	{
	throw new ArgumentException("fractional edit distances are not allowed");
	}
	if (minSimilarity < 0.0f)
	{
	throw new ArgumentException("minimumSimilarity cannot be less than 0");
	}
	if (prefixLength < 0)
	{
	throw new ArgumentException("prefixLength cannot be less than 0");
	}
	this.m_terms = terms;
	this.term = term;

	// convert the string into a utf32 int[] representation for fast comparisons
	string utf16 = term.Text();
	this.m_termText = new int[utf16.CodePointCount(0, utf16.Length)];
	for (int cp, i = 0, j = 0; i < utf16.Length; i += Character.CharCount(cp))
	{
	m_termText[j++] = cp = utf16.CodePointAt(i);
	}
	this.m_termLength = m_termText.Length;
	this.dfaAtt = atts.AddAttribute<ILevenshteinAutomataAttribute>();

	//The prefix could be longer than the word.
	//It's kind of silly though. It means we must match the entire word.
	this.m_realPrefixLength = prefixLength > m_termLength ? m_termLength : prefixLength;
	// if minSimilarity >= 1, we treat it as number of edits
	if (minSimilarity >= 1f)
	{
	this.m_minSimilarity = 0; // just driven by number of edits
	m_maxEdits = (int)minSimilarity;
	m_raw = true;
	}
	else
	{
	this.m_minSimilarity = minSimilarity;
	// calculate the maximum k edits for this similarity
	m_maxEdits = InitialMaxDistance(this.m_minSimilarity, m_termLength);
	m_raw = false;
	}
	if (transpositions && m_maxEdits > LevenshteinAutomata.MAXIMUM_SUPPORTED_DISTANCE)
	{
	throw new System.NotSupportedException("with transpositions enabled, distances > " + LevenshteinAutomata.MAXIMUM_SUPPORTED_DISTANCE + " are not supported ");
	}
	this.transpositions = transpositions;
	this.m_scaleFactor = 1.0f / (1.0f - this.m_minSimilarity);

	this.maxBoostAtt = atts.AddAttribute<IMaxNonCompetitiveBoostAttribute>();
	bottom = maxBoostAtt.MaxNonCompetitiveBoost;
	bottomTerm = maxBoostAtt.CompetitiveTerm;
	BottomChanged(null, true);
	}

	/// <summary>
	/// Return an automata-based enum for matching up to <paramref name="editDistance"/> from
	/// <paramref name="lastTerm"/>, if possible
	/// </summary>
	protected virtual TermsEnum GetAutomatonEnum(int editDistance, BytesRef lastTerm)
	{
	IList<CompiledAutomaton> runAutomata = InitAutomata(editDistance);
	if (editDistance < runAutomata.Count)
	{
	//if (BlockTreeTermsWriter.DEBUG) System.out.println("FuzzyTE.getAEnum: ed=" + editDistance + " lastTerm=" + (lastTerm==null ? "null" : lastTerm.utf8ToString()));
	CompiledAutomaton compiled = runAutomata[editDistance];
	return new AutomatonFuzzyTermsEnum(this, m_terms.Intersect(compiled, lastTerm == null ? null : compiled.Floor(lastTerm, new BytesRef())), runAutomata.SubList(0, editDistance + 1).ToArray(/new CompiledAutomaton[editDistance + 1]/));
	}
	else
	{
	return null;
	}
	}

	/// <summary>
	/// Initialize levenshtein DFAs up to maxDistance, if possible </summary>
	private IList<CompiledAutomaton> InitAutomata(int maxDistance)
	{
	IList<CompiledAutomaton> runAutomata = dfaAtt.Automata;
	//System.out.println("cached automata size: " + runAutomata.size());
	if (runAutomata.Count <= maxDistance && maxDistance <= LevenshteinAutomata.MAXIMUM_SUPPORTED_DISTANCE)
	{
	LevenshteinAutomata builder = new LevenshteinAutomata(UnicodeUtil.NewString(m_termText, m_realPrefixLength, m_termText.Length - m_realPrefixLength), transpositions);

	for (int i = runAutomata.Count; i <= maxDistance; i++)
	{
	Automaton a = builder.ToAutomaton(i);
	//System.out.println("compute automaton n=" + i);
	// constant prefix
	if (m_realPrefixLength > 0)
	{
	Automaton prefix = BasicAutomata.MakeString(UnicodeUtil.NewString(m_termText, 0, m_realPrefixLength));
	a = BasicOperations.Concatenate(prefix, a);
	}
	runAutomata.Add(new CompiledAutomaton(a, true, false));
	}
	}
	return runAutomata;
	}

	/// <summary>
	/// Swap in a new actual enum to proxy to </summary>
	protected virtual void SetEnum(TermsEnum actualEnum)
	{
	this.actualEnum = actualEnum;
	this.actualBoostAtt = actualEnum.Attributes.AddAttribute<IBoostAttribute>();
	}

	/// <summary>
	/// Fired when the max non-competitive boost has changed. This is the hook to
	/// swap in a smarter actualEnum
	/// </summary>
	private void BottomChanged(BytesRef lastTerm, bool init)
	{
	int oldMaxEdits = m_maxEdits;

	// true if the last term encountered is lexicographically equal or after the bottom term in the PQ
	bool termAfter = bottomTerm == null \|\| (lastTerm != null && termComparer.Compare(lastTerm, bottomTerm) >= 0);

	// as long as the max non-competitive boost is >= the max boost
	// for some edit distance, keep dropping the max edit distance.
	while (m_maxEdits > 0 && (termAfter ? bottom >= CalculateMaxBoost(m_maxEdits) : bottom > CalculateMaxBoost(m_maxEdits)))
	{
	m_maxEdits--;
	}

	if (oldMaxEdits != m_maxEdits \|\| init) // the maximum n has changed
	{
	MaxEditDistanceChanged(lastTerm, m_maxEdits, init);
	}
	}

	protected virtual void MaxEditDistanceChanged(BytesRef lastTerm, int maxEdits, bool init)
	{
	TermsEnum newEnum = GetAutomatonEnum(maxEdits, lastTerm);
	// instead of assert, we do a hard check in case someone uses our enum directly
	// assert newEnum != null;
	if (newEnum == null)
	{
	Debug.Assert(maxEdits > LevenshteinAutomata.MAXIMUM_SUPPORTED_DISTANCE);
	throw new System.ArgumentException("maxEdits cannot be > LevenshteinAutomata.MAXIMUM_SUPPORTED_DISTANCE");
	}
	SetEnum(newEnum);
	}

	// for some raw min similarity and input term length, the maximum # of edits
	private int InitialMaxDistance(float minimumSimilarity, int termLen)
	{
	return (int)((1D - minimumSimilarity) * termLen);
	}

	// for some number of edits, the maximum possible scaled boost
	private float CalculateMaxBoost(int nEdits)
	{
	float similarity = 1.0f - ((float)nEdits / (float)(m_termLength));
	return (similarity - m_minSimilarity) * m_scaleFactor;
	}

	private BytesRef queuedBottom = null;

	public override BytesRef Next()
	{
	if (queuedBottom != null)
	{
	BottomChanged(queuedBottom, false);
	queuedBottom = null;
	}

	BytesRef term = actualEnum.Next();
	boostAtt.Boost = actualBoostAtt.Boost;

	float bottom = maxBoostAtt.MaxNonCompetitiveBoost;
	BytesRef bottomTerm = maxBoostAtt.CompetitiveTerm;
	if (term != null && (bottom != this.bottom \|\| bottomTerm != this.bottomTerm))
	{
	this.bottom = bottom;
	this.bottomTerm = bottomTerm;
	// clone the term before potentially doing something with it
	// this is a rare but wonderful occurrence anyway
	queuedBottom = BytesRef.DeepCopyOf(term);
	}

	return term;
	}

	// proxy all other enum calls to the actual enum
	public override int DocFreq
	{
	get { return actualEnum.DocFreq; }
	}

	public override long TotalTermFreq
	{
	get { return actualEnum.TotalTermFreq; }
	}

	public override DocsEnum Docs(IBits liveDocs, DocsEnum reuse, DocsFlags flags)
	{
	return actualEnum.Docs(liveDocs, reuse, flags);
	}

	public override DocsAndPositionsEnum DocsAndPositions(IBits liveDocs, DocsAndPositionsEnum reuse, DocsAndPositionsFlags flags)
	{
	return actualEnum.DocsAndPositions(liveDocs, reuse, flags);
	}

	public override void SeekExact(BytesRef term, TermState state)
	{
	actualEnum.SeekExact(term, state);
	}

	public override TermState GetTermState()
	{
	return actualEnum.GetTermState();
	}

	public override IComparer<BytesRef> Comparer => actualEnum.Comparer;

	public override long Ord => actualEnum.Ord;

	public override bool SeekExact(BytesRef text)
	{
	return actualEnum.SeekExact(text);
	}

	public override SeekStatus SeekCeil(BytesRef text)
	{
	return actualEnum.SeekCeil(text);
	}

	public override void SeekExact(long ord)
	{
	actualEnum.SeekExact(ord);
	}

	public override BytesRef Term => actualEnum.Term;

	/// <summary>
	/// Implement fuzzy enumeration with <see cref="Terms.Intersect(CompiledAutomaton, BytesRef)"/>.
	/// <para/>
	/// This is the fastest method as opposed to LinearFuzzyTermsEnum:
	/// as enumeration is logarithmic to the number of terms (instead of linear)
	/// and comparison is linear to length of the term (rather than quadratic)
	/// </summary>
	private class AutomatonFuzzyTermsEnum : FilteredTermsEnum
	{
	internal virtual void InitializeInstanceFields()
	{
	boostAtt = Attributes.AddAttribute<IBoostAttribute>();
	}

	private readonly FuzzyTermsEnum outerInstance;

	private readonly ByteRunAutomaton[] matchers;

	private readonly BytesRef termRef;

	private IBoostAttribute boostAtt;

	public AutomatonFuzzyTermsEnum(FuzzyTermsEnum outerInstance, TermsEnum tenum, CompiledAutomaton[] compiled)
	: base(tenum, false)
	{
	this.outerInstance = outerInstance;

	InitializeInstanceFields();
	this.matchers = new ByteRunAutomaton[compiled.Length];
	for (int i = 0; i < compiled.Length; i++)
	{
	this.matchers[i] = compiled[i].RunAutomaton;
	}
	termRef = new BytesRef(outerInstance.term.Text());
	}

	/// <summary>
	/// Finds the smallest Lev(n) DFA that accepts the term. </summary>
	protected override AcceptStatus Accept(BytesRef term)
	{
	//System.out.println("AFTE.accept term=" + term);
	int ed = matchers.Length - 1;

	// we are wrapping either an intersect() TermsEnum or an AutomatonTermsENum,
	// so we know the outer DFA always matches.
	// now compute exact edit distance
	while (ed > 0)
	{
	if (Matches(term, ed - 1))
	{
	ed--;
	}
	else
	{
	break;
	}
	}
	//System.out.println("CHECK term=" + term.utf8ToString() + " ed=" + ed);

	// scale to a boost and return (if similarity > minSimilarity)
	if (ed == 0) // exact match
	{
	boostAtt.Boost = 1.0F;
	//System.out.println(" yes");
	return AcceptStatus.YES;
	}
	else
	{
	int codePointCount = UnicodeUtil.CodePointCount(term);
	float similarity = 1.0f - ((float)ed / (float)(Math.Min(codePointCount, outerInstance.m_termLength)));
	if (similarity > outerInstance.m_minSimilarity)
	{
	boostAtt.Boost = (similarity - outerInstance.m_minSimilarity) * outerInstance.m_scaleFactor;
	//System.out.println(" yes");
	return AcceptStatus.YES;
	}
	else
	{
	return AcceptStatus.NO;
	}
	}
	}

	/// <summary>
	/// Returns <c>true</c> if <paramref name="term"/> is within <paramref name="k"/> edits of the query term </summary>
	internal bool Matches(BytesRef term, int k)
	{
	return k == 0 ? term.Equals(termRef) : matchers[k].Run(term.Bytes, term.Offset, term.Length);
	}
	}

	/// <summary>
	/// @lucene.internal </summary>
	public virtual float MinSimilarity => m_minSimilarity;

	/// <summary>
	/// @lucene.internal </summary>
	public virtual float ScaleFactor => m_scaleFactor;

	/// <summary>
	/// Reuses compiled automata across different segments,
	/// because they are independent of the index
	/// <para/>
	/// @lucene.internal
	/// </summary>
	public interface ILevenshteinAutomataAttribute : IAttribute
	{
	IList<CompiledAutomaton> Automata { get; }
	}

	/// <summary>
	/// Stores compiled automata as a list (indexed by edit distance)
	/// <para/>
	/// @lucene.internal
	/// </summary>
	public sealed class LevenshteinAutomataAttribute : Attribute, ILevenshteinAutomataAttribute
	{
	// LUCENENET NOTE: Must use JCG.List for Equals and GetHashCode()
	private readonly IList<CompiledAutomaton> automata = new JCG.List<CompiledAutomaton>();

	public IList<CompiledAutomaton> Automata
	{
	get { return automata; }
	}

	public override void Clear()
	{
	automata.Clear();
	}

	public override int GetHashCode()
	{
	return automata.GetHashCode();
	}

	public override bool Equals(object other)
	{
	if (this == other)
	{
	return true;
	}
	if (!(other is LevenshteinAutomataAttribute))
	{
	return false;
	}
	return automata.Equals(((LevenshteinAutomataAttribute)other).automata);
	}

	public override void CopyTo(IAttribute target)
	{
	IList<CompiledAutomaton> targetAutomata = ((LevenshteinAutomataAttribute)target).Automata;
	targetAutomata.Clear();
	targetAutomata.AddRange(automata);
	}
	}
	}
	}