Inverse Document Frequency (IDF) implementation

Question

I would like to share my class IDF with experts. Sorry for the poor data structure, but we are humans and still learning. Any Suggestion/ Modification please ?? many Thanks.

public class IDFMeasure
{
    private readonly string[] _docs;
    private readonly int _numDocs;
    private int _numTerms;
    private List<string> _terms;
    private float[][] _InverseDocFreq;
    private int[] _docFreq;

    private readonly Dictionary<string, int> _wordsIndex = new Dictionary<string, int>();

    public IDFMeasure(string[] documents)
    {
        _docs = documents;
        _numDocs = documents.Length;
        MyInit();
    }

    private List<string> GenerateTerms(string[] docs)
    {
        return docs.SelectMany(doc => ProcessDocument(doc)).Distinct().ToList();
    }

    private IEnumerable<string> ProcessDocument(string doc)
    {
        return doc.Split(' ')
            .GroupBy(word => word)
            .OrderByDescending(g => g.Count())
            .Select(g => g.Key)
    }

    private int GetTermIndex(string term)
    {
        return _wordsIndex[term];
    }

    private void MyInit()
    {
        _terms = GenerateTerms(_docs);
        _numTerms = _terms.Count;

        _docFreq = new int[_numTerms];

        for (var i = 0; i < _terms.Count; i++)
        {
            _wordsIndex.Add(_terms[i], i);
        }

        GenerateDocumentFrequency();
        GenerateInverseDocfrequency();
    }

    private float Log(float num)
    {
        return (float) Math.Log(num); //log2
    }

    private void GenerateDocumentFrequency()
    {
        _InverseDocFreq = new float[_numDocs][];

        for (var i = 0; i < _numDocs; i++)
        {
            _InverseDocFreq[i] = new float[_numTerms];


            var curDoc = _docs[i];
            var freq = GetWordFrequency(curDoc);


            foreach (var entry in freq)
            {
                var word = entry.Key;

                var termIndex = GetTermIndex(word);

                _docFreq[termIndex]++;
            }
        }
    }

    private void GenerateInverseDocfrequency()
    {
        for (var i = 0; i < _numDocs; i++)
        {
            var curDoc = _docs[i];
            var freq = GetWordFrequency(curDoc);


            foreach (var entry in freq)
            {
                var word = entry.Key;

                var termIndex = GetTermIndex(word);

                _InverseDocFreq[i][termIndex] = Log((_numDocs)/
                                                    (float) _docFreq[termIndex]);
            }
        }
    }

    private Dictionary<string, int> GetWordFrequency(string input)
    {
        return input.Split(' ').GroupBy(x => x)
            .OrderByDescending(g => g.Count())
            .ToDictionary(g => g.Key, g => g.Count());
    }
}

Answer 1

The layout and naming conventions look good. Thank you for that.

_InverseDocFreq should be renamed _inverseDocFreq to keep with conventions and also stay consistent in your code.

I also think _terms should be an IList. This just eliminates a bunch of the unneeded operations.

you are missing a ; after this statement in ProcessDocument

return doc.Split(' ')
            .GroupBy(word => word)
            .OrderByDescending(g => g.Count())
            .Select(g => g.Key)

I'm not sure why you are using MyInit, the constructor is the only place that is called. I would move the code into the constructor, then you can make _numTerms, _terms, and _docFreq readonly.

I would rename _wordsIndex to _wordIndex because it is really only and index for each word. I would also move the new into the constructor.

The for loop where you are filling the terms into the _wordIndex dictionary could be moved to its own method, I called it FillWordIndexWithTerms(), and it looks like

private void FillWordIndexWithTerms()
{
    for (var termIndex = 0; termIndex < _terms.Count; termIndex++)
    {
        _wordIndex.Add(_terms[termIndex], termIndex);
    }
}

I renamed i to termIndex to give it a bit better meaning in your code, and make it easier to read.

The constructor now looks like

public IDFMeasure(string[] documents)
{
    _docs = documents;
    _numDocs = documents.Length;

    _terms = GenerateTerms(_docs);
    _numTerms = _terms.Count;

    _docFreq = new int[_numTerms];
    _wordIndex = new Dictionary<string, int>();

    FillWordIndexWithTerms();
    GenerateDocumentFrequency();
    GenerateInverseDocfrequency();
}

In the GenerateTerms method, I would change the input parameter to an IEnumerable. You could also use a method group in the linq statement, you don't need the lamba. The function can also be made static.

private static IList<string> GenerateTerms(IEnumerable<string> docs)
{
    return docs.SelectMany(ProcessDocument).Distinct().ToList();
}

ProcessDocument looks good.

GetTermIndex looks good.

Log could be made static. Other than that it looks good.

I would move the inner ForEach in GenerateDocumentFrequency to its own method. This will reduce nesting.

private void GenerateDocumentFrequency()
{
    _inverseDocFreq = new float[_numDocs][];

    for (var i = 0; i < _numDocs; i++)
    {
        _inverseDocFreq[i] = new float[_numTerms];

        var curDoc = _docs[i];
        var freq = GetWordFrequency(curDoc);

        CalculateTermFrequency(freq);
    }
}

The ForEach can also be simplified using Linq.

private void CalculateTermFrequency(Dictionary<string, int> freq)
{
    foreach (var termIndex in freq.Select(entry => GetTermIndex(entry.Key)))
    {
        _docFreq[termIndex]++;
    }
}

In GenerateInverseDocfrequency I would rename i to currentDocument. The nested ForEach should be moved to its own method, CalculateInverseDocumentFrequency.

private void GenerateInverseDocfrequency()
{
    for (var currentDocument = 0; currentDocument < _numDocs; currentDocument++)
    {
        var curDoc = _docs[currentDocument];
        var freq = GetWordFrequency(curDoc);

        CalculateInverseDocumentFrequency(currentDocument, freq);
    }
}

private void CalculateInverseDocumentFrequency(int currentDocument, Dictionary<string, int> freq)
{
    foreach (var termIndex in freq.Select(entry => entry.Key).Select(GetTermIndex))
    {
        _inverseDocFreq[currentDocument][termIndex] = Log((_numDocs)/
                                                            (float) _docFreq[termIndex]);
    }
}

GetWordFrequency could be made static. Other than that it looks good.

Overall, nice code to read, the suggestions are just minor clean-up. I really liked the way you used methods to separate different operations.

Answer 2

In addition to Jeff's changes (I completely agree with all of them) here are my 2 cents:

I assume this class may process large number of documents, so it's better to switch it to using streaming techniques where you are not required to keep all the data in memory.

So, let's start with constructor... it's usually better to move time-consuming logic out of constructor, e.g. you may later want to introduce asynchronous implementation. So we get rid of constructor and move all the logic into Load method.

By following "streaming" technique it should receive IEnumerable instead of pre-loaded array of documents. We will calculate all the stats for each document and then forget about it, so all the arrays that expected a known number of terms and documents should become lists (except _inverseDocFreq as it have to be calculated later, when the total number of docs is known). Here is the resulting code for your class:

public class IDFMeasure
{
    private readonly List<string> _terms = new List<string>();

    /// <summary> contains the number of documents containing certain word. Index corresponds to word index. </summary>
    private readonly List<int> _docFreq = new List<int>();
    private readonly Dictionary<string, int> _wordIndex = new Dictionary<string, int>();

    private float[][] _inverseDocFreq;

    public void Load(IEnumerable<string> documents)
    {
        List<int[]> documentWordIndexes = new List<int[]>();

        foreach (var document in documents)
        {
            var termStatistics = GenerateTermStatistics(document);

            AddMissingTermsToIndex(termStatistics);
            GenerateDocumentFrequency(termStatistics);
            documentWordIndexes.Add(GetDocumentWordIndexes(termStatistics));
        }

        _inverseDocFreq = GenerateInverseDocfrequency(documentWordIndexes);
    }

    ///<summary> Extracts all unique terms from document along with the number of occurrences. </summary>
    private static Dictionary<string, int> GenerateTermStatistics(string document)
    {
        return document.Split(' ')
            .GroupBy(x => x)
            .ToDictionary(g => g.Key, g => g.Count());
    }

    ///<summary>Adds missing terms to terms index. </summary>
    private void AddMissingTermsToIndex(Dictionary<string, int> termStatistics)
    {
        foreach (var missingTerm in termStatistics.Keys.Where(term => !_wordIndex.ContainsKey(term)))
        {
            _wordIndex[missingTerm] = _terms.Count;
            _terms.Add(missingTerm);
            _docFreq.Add(0); //to make sure that list is of the same size as _terms
        }
    }

    private void GenerateDocumentFrequency(Dictionary<string, int> termStatistics)
    {
        foreach (var term in termStatistics.Keys)
            _docFreq[_wordIndex[term]]++;
    }

    private int[] GetDocumentWordIndexes(Dictionary<string, int> termStatistics)
    {
        return termStatistics.Keys.Select(term => _wordIndex[term]).ToArray();
    }

    private float[][] GenerateInverseDocfrequency(ICollection<int[]> documentWordIndexes)
    {
        return documentWordIndexes
            .Select(ints => BuildInverseIndexForDocument(documentWordIndexes.Count, ints))
            .ToArray();
    }

    private float[] BuildInverseIndexForDocument(int docCount, IEnumerable<int> documentWordIndex)
    {
        var result = new float[_terms.Count];

        foreach (var termIndex in documentWordIndex)
            result[termIndex] = (float)Math.Log((docCount / (float)_docFreq[termIndex]));

        return result;
    }
}

I preserved counting the number of term occurrences within document even though it is never used in your code, because most likely you would want to use it at some point later.

I removed Log method (it's used only in one place, and it basically does the same as Math.Log, so there is no need in separate method.

Note how _wordIndex dictionary and _terms are dynamically populated in AddMissingTermsToIndex as we find new terms in documents.