ShingleMatrixFilter.cs

Go to the documentation of this file.

/*
 * 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 System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Lucene.Net.Analysis.Miscellaneous;
using Lucene.Net.Analysis.Shingle.Codec;
using Lucene.Net.Analysis.Shingle.Matrix;
using Lucene.Net.Analysis.Tokenattributes;
using Lucene.Net.Support;

namespace Lucene.Net.Analysis.Shingle
{
    public sealed class ShingleMatrixFilter : TokenStream
    {
        public static Char DefaultSpacerCharacter = '_';
        public static TokenSettingsCodec DefaultSettingsCodec = new OneDimensionalNonWeightedTokenSettingsCodec();
        public static bool IgnoringSinglePrefixOrSuffixShingleByDefault;

        private readonly IFlagsAttribute _flagsAtt;
        private readonly IFlagsAttribute _inFlagsAtt;

        private readonly IOffsetAttribute _inOffsetAtt;
        private readonly IPayloadAttribute _inPayloadAtt;
        private readonly IPositionIncrementAttribute _inPosIncrAtt;
        private readonly ITermAttribute _inTermAtt;
        private readonly ITypeAttribute _inTypeAtt;
        private readonly TokenStream _input;
        private readonly IOffsetAttribute _offsetAtt;
        private readonly IPayloadAttribute _payloadAtt;
        private readonly IPositionIncrementAttribute _posIncrAtt;
        private readonly Token _requestNextToken = new Token();
        private readonly Token _reusableToken = new Token();
        private readonly TokenSettingsCodec _settingsCodec;

        private readonly HashSet<EquatableList<Token>> _shinglesSeen =
            new HashSet<EquatableList<Token>>(); 

        private readonly ITermAttribute _termAtt;
        private readonly ITypeAttribute _typeAtt;
        private List<Token> _currentPermuationTokens;

        // Index to what row a token in currentShingleTokens represents
        private List<Row> _currentPermutationRows;

        private int _currentPermutationTokensStartOffset;
        private int _currentShingleLength;
        private MatrixPermutationIterator _permutations;
        private Token _readColumnBuf;


        public ShingleMatrixFilter(Matrix.Matrix matrix, int minimumShingleSize, int maximumShingleSize, Char spacerCharacter, bool ignoringSinglePrefixOrSuffixShingle, TokenSettingsCodec settingsCodec)
        {
            Matrix = matrix;
            MinimumShingleSize = minimumShingleSize;
            MaximumShingleSize = maximumShingleSize;
            SpacerCharacter = spacerCharacter;
            IsIgnoringSinglePrefixOrSuffixShingle = ignoringSinglePrefixOrSuffixShingle;
            _settingsCodec = settingsCodec;

            // ReSharper disable DoNotCallOverridableMethodsInConstructor
            _termAtt = AddAttribute<ITermAttribute>();
            _posIncrAtt = AddAttribute<IPositionIncrementAttribute>();
            _payloadAtt = AddAttribute<IPayloadAttribute>();
            _offsetAtt = AddAttribute<IOffsetAttribute>();
            _typeAtt = AddAttribute<ITypeAttribute>();
            _flagsAtt = AddAttribute<IFlagsAttribute>();
            // ReSharper restore DoNotCallOverridableMethodsInConstructor

            // set the input to be an empty token stream, we already have the data.
            _input = new EmptyTokenStream();

            _inTermAtt = _input.AddAttribute<ITermAttribute>();
            _inPosIncrAtt = _input.AddAttribute<IPositionIncrementAttribute>();
            _inPayloadAtt = _input.AddAttribute<IPayloadAttribute>();
            _inOffsetAtt = _input.AddAttribute<IOffsetAttribute>();
            _inTypeAtt = _input.AddAttribute<ITypeAttribute>();
            _inFlagsAtt = _input.AddAttribute<IFlagsAttribute>();
        }

        public ShingleMatrixFilter(TokenStream input, int minimumShingleSize, int maximumShingleSize)
            : this(input, minimumShingleSize, maximumShingleSize, DefaultSpacerCharacter) { }

        public ShingleMatrixFilter(TokenStream input, int minimumShingleSize, int maximumShingleSize, Char? spacerCharacter)
            : this( input, minimumShingleSize, maximumShingleSize, spacerCharacter, IgnoringSinglePrefixOrSuffixShingleByDefault) { }

        public ShingleMatrixFilter(TokenStream input, int minimumShingleSize, int maximumShingleSize, Char? spacerCharacter, bool ignoringSinglePrefixOrSuffixShingle)
            : this(input, minimumShingleSize, maximumShingleSize, spacerCharacter, ignoringSinglePrefixOrSuffixShingle, DefaultSettingsCodec) { }

        public ShingleMatrixFilter(TokenStream input, int minimumShingleSize, int maximumShingleSize, Char? spacerCharacter, bool ignoringSinglePrefixOrSuffixShingle, TokenSettingsCodec settingsCodec)
        {
            _input = input;
            MinimumShingleSize = minimumShingleSize;
            MaximumShingleSize = maximumShingleSize;
            SpacerCharacter = spacerCharacter;
            IsIgnoringSinglePrefixOrSuffixShingle = ignoringSinglePrefixOrSuffixShingle;
            _settingsCodec = settingsCodec;

            // ReSharper disable DoNotCallOverridableMethodsInConstructor
            _termAtt = AddAttribute<ITermAttribute>();
            _posIncrAtt = AddAttribute<IPositionIncrementAttribute>();
            _payloadAtt = AddAttribute<IPayloadAttribute>();
            _offsetAtt = AddAttribute<IOffsetAttribute>();
            _typeAtt = AddAttribute<ITypeAttribute>();
            _flagsAtt = AddAttribute<IFlagsAttribute>();
            // ReSharper restore DoNotCallOverridableMethodsInConstructor

            _inTermAtt = input.AddAttribute<ITermAttribute>();
            _inPosIncrAtt = input.AddAttribute<IPositionIncrementAttribute>();
            _inPayloadAtt = input.AddAttribute<IPayloadAttribute>();
            _inOffsetAtt = input.AddAttribute<IOffsetAttribute>();
            _inTypeAtt = input.AddAttribute<ITypeAttribute>();
            _inFlagsAtt = input.AddAttribute<IFlagsAttribute>();
        }

        public int MinimumShingleSize { get; set; }

        public int MaximumShingleSize { get; set; }

        public Matrix.Matrix Matrix { get; set; }

        public Char? SpacerCharacter { get; set; }

        public bool IsIgnoringSinglePrefixOrSuffixShingle { get; set; }

        public override void Reset()
        {
            _permutations = null;
            _shinglesSeen.Clear();
            _input.Reset();
        }

        protected override void Dispose(bool disposing)
        {
            // Do nothing
        }

        public override sealed bool IncrementToken()
        {
            if (Matrix == null)
            {
                Matrix = new Matrix.Matrix();

                // fill matrix with maximumShingleSize columns
                while (Matrix.Columns.Count < MaximumShingleSize && ReadColumn())
                {
                    // this loop looks ugly
                }
            }

            // This loop exists in order to avoid recursive calls to the next method
            // as the complexity of a large matrix
            // then would require a multi gigabyte sized stack.
            Token token;
            do
            {
                token = ProduceNextToken(_reusableToken);
            } while (token == _requestNextToken);
            
            if (token == null) 
                return false;

            ClearAttributes();

            _termAtt.SetTermBuffer(token.TermBuffer(), 0, token.TermLength());
            _posIncrAtt.PositionIncrement = token.PositionIncrement;
            _flagsAtt.Flags = token.Flags;
            _offsetAtt.SetOffset(token.StartOffset, token.EndOffset);
            _typeAtt.Type = token.Type;
            _payloadAtt.Payload = token.Payload;

            return true;
        }

        private Token GetNextInputToken(Token token)
        {
            if (!_input.IncrementToken()) return null;

            token.SetTermBuffer(_inTermAtt.TermBuffer(), 0, _inTermAtt.TermLength());
            token.PositionIncrement = _inPosIncrAtt.PositionIncrement;
            token.Flags = _inFlagsAtt.Flags;
            token.SetOffset(_inOffsetAtt.StartOffset, _inOffsetAtt.EndOffset);
            token.Type = _inTypeAtt.Type;
            token.Payload = _inPayloadAtt.Payload;
            return token;
        }

        private Token GetNextToken(Token token)
        {
            if (!this.IncrementToken()) return null;
            token.SetTermBuffer(_termAtt.TermBuffer(), 0, _termAtt.TermLength());
            token.PositionIncrement = _posIncrAtt.PositionIncrement;
            token.Flags = _flagsAtt.Flags;
            token.SetOffset(_offsetAtt.StartOffset, _offsetAtt.EndOffset);
            token.Type = _typeAtt.Type;
            token.Payload = _payloadAtt.Payload;
            return token;
        }

        private Token ProduceNextToken(Token reusableToken)
        {
            if (_currentPermuationTokens != null)
            {
                _currentShingleLength++;

                if (_currentShingleLength + _currentPermutationTokensStartOffset <= _currentPermuationTokens.Count
                    && _currentShingleLength <= MaximumShingleSize)
                {
                    // it is possible to create at least one more shingle of the current matrix permutation

                    if (IsIgnoringSinglePrefixOrSuffixShingle && 
                        _currentShingleLength == 1 && 
                        (_currentPermutationRows[_currentPermutationTokensStartOffset].Column.IsFirst || _currentPermutationRows[_currentPermutationTokensStartOffset].Column.IsLast))
                    {
                        return GetNextToken(reusableToken);
                    }

                    var termLength = 0;

                    var shingle = new EquatableList<Token>();

                    for (int i = 0; i < _currentShingleLength; i++)
                    {
                        var shingleToken = _currentPermuationTokens[i + _currentPermutationTokensStartOffset];
                        termLength += shingleToken.TermLength();
                        shingle.Add(shingleToken);
                    }
                    if (SpacerCharacter != null)
                        termLength += _currentShingleLength - 1;

                    // only produce shingles that not already has been created
                    if (!_shinglesSeen.Add(shingle))
                        return _requestNextToken;

                    // shingle token factory
                    var sb = new StringBuilder(termLength + 10); // paranormal ability to foresee the future. ;)
                    foreach (var shingleToken in shingle)
                    {
                        if (SpacerCharacter != null &&  sb.Length > 0)
                            sb.Append(SpacerCharacter);

                        sb.Append(shingleToken.TermBuffer(), 0, shingleToken.TermLength());
                    }

                    reusableToken.SetTermBuffer(sb.ToString());
                    UpdateToken(reusableToken, shingle, _currentPermutationTokensStartOffset, _currentPermutationRows,
                                _currentPermuationTokens);

                    return reusableToken;
                }

                // it is NOT possible to create one more shingles of the current matrix permutation
                if (_currentPermutationTokensStartOffset < _currentPermuationTokens.Count - 1)
                {
                    // reset shingle size and move one step to the right in the current tokens permutation
                    _currentPermutationTokensStartOffset++;
                    _currentShingleLength = MinimumShingleSize - 1;
                    return _requestNextToken;
                }


                // todo does this ever occur?
                if (_permutations == null)
                    return null;

                if (!_permutations.HasNext())
                {
                    // load more data (if available) to the matrix

                    // don't really care, we just read it.
                    if (_input != null)
                        ReadColumn();

                    // get rid of resources

                    // delete the first column in the matrix
                    var deletedColumn = Matrix.Columns[0];
                    Matrix.Columns.RemoveAt(0);

                    // remove all shingles seen that include any of the tokens from the deleted column.
                    var deletedColumnTokens = deletedColumn.Rows.SelectMany(row => row.Tokens).ToList();
                    
                    // I'm a little concerned about this part of the code, because the unit tests currently 
                    // don't cover this scenario. (I put a break point here, and ran the unit tests in debug mode 
                    // and this code block was never hit... I also changed it significatly from the Java version
                    // to use RemoveWhere and LINQ. 
                    //
                    // TODO: Write a unit test to cover this and make sure this is a good port! -thoward

                    // linq version
                    _shinglesSeen.RemoveWhere(
                        shingle => (shingle.Find(deletedColumnTokens.Contains) != default(Token)));

                    //var shinglesSeenIterator = _shinglesSeen.ToList();
                    //foreach (var shingle in shinglesSeenIterator)
                    //{
                    //    foreach (var deletedColumnToken in deletedColumnTokens)
                    //    {
                    //        if (shingle.Contains(deletedColumnToken))
                    //        {
                    //            _shinglesSeen.Remove(shingle);
                    //            break;
                    //        }
                    //    }
                    //}

                    // exhausted
                    if (Matrix.Columns.Count < MinimumShingleSize)
                        return null;

                    // create permutations of the matrix it now looks
                    _permutations = Matrix.PermutationIterator();
                }

                NextTokensPermutation();
                return _requestNextToken;
            }

            if (_permutations == null)
                _permutations = Matrix.PermutationIterator();

            if (!_permutations.HasNext())
                return null;

            NextTokensPermutation();

            return _requestNextToken;
        }

        private void NextTokensPermutation()
        {
            var rowsPermutation = _permutations.Next();
            var currentPermutationRows = new List<Row>();
            var currentPermuationTokens = new List<Token>();

            foreach (var row in rowsPermutation)
            {
                foreach (var token in row.Tokens)
                {
                    currentPermuationTokens.Add(token);
                    currentPermutationRows.Add(row);
                }
            }
            _currentPermuationTokens = currentPermuationTokens;
            _currentPermutationRows = currentPermutationRows;

            _currentPermutationTokensStartOffset = 0;
            _currentShingleLength = MinimumShingleSize - 1;
        }

        public void UpdateToken(Token token, List<Token> shingle, int currentPermutationStartOffset, List<Row> currentPermutationRows, List<Token> currentPermuationTokens)
        {
            token.Type = typeof(ShingleMatrixFilter).Name;
            token.Flags = 0;
            token.PositionIncrement = 1;
            token.StartOffset = (shingle[0]).StartOffset;
            token.EndOffset = shingle[shingle.Count - 1].EndOffset;

            _settingsCodec.SetWeight(
                token, 
                CalculateShingleWeight(token, shingle, currentPermutationStartOffset, currentPermutationRows, currentPermuationTokens)
                );
        }

        public float CalculateShingleWeight(Token shingleToken, List<Token> shingle, int currentPermutationStartOffset, List<Row> currentPermutationRows, List<Token> currentPermuationTokens)
        {
            var weights = new double[shingle.Count];

            double total = 0f;
            double top = 0d;

            for (int i = 0; i < weights.Length; i++)
            {
                weights[i] = _settingsCodec.GetWeight(shingle[i]);

                double tmp = weights[i];

                if (tmp > top)
                    top = tmp;

                total += tmp;
            }

            double factor = 1d/Math.Sqrt(total);

            double weight = weights.Sum(partWeight => partWeight*factor);

            return (float) weight;
        }

        private bool ReadColumn()
        {
            Token token;

            if (_readColumnBuf != null)
            {
                token = _readColumnBuf;
                _readColumnBuf = null;
            }
            else
            {
                token = GetNextInputToken(new Token());
            }

            if (token == null)
                return false;

            var currentReaderColumn = new Column(Matrix);
            var currentReaderRow = new Row(currentReaderColumn);

            currentReaderRow.Tokens.AddLast(token);

            TokenPositioner tokenPositioner;
            while ((_readColumnBuf = GetNextInputToken(new Token())) != null &&
                   (tokenPositioner = _settingsCodec.GetTokenPositioner(_readColumnBuf)) != TokenPositioner.NewColumn)
            {
                if (tokenPositioner == TokenPositioner.SameRow)
                {
                    currentReaderRow.Tokens.AddLast(_readColumnBuf);
                }
                else
                {
                    currentReaderRow = new Row(currentReaderColumn);
                    currentReaderRow.Tokens.AddLast(_readColumnBuf);
                }
                _readColumnBuf = null;
            }

            if (_readColumnBuf == null)
            {
                _readColumnBuf = GetNextInputToken(new Token());

                if (_readColumnBuf == null)
                    currentReaderColumn.IsLast = true;
            }

            return true;
        }
    }
}