# Inverse Document Frequency (IDF) implementation

I would like to share my class IDF. Any suggestions/modification?

public class IDFMeasure
{
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++)
{
}

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());
}
}


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++)
{
}
}


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.

• The ProcessDocument in GenerateTerms needs an object reference for the non-static method !! This the error I got. Could you review it again please ? – Falah SM Nov 29 '12 at 18:00
• I changed the _terms to an IList...I mentioned it there. I didn't think about the static and ProcessDocument. Just remove it :) – Jeff Vanzella Nov 29 '12 at 18:08
• The static from ProcessDocument – Jeff Vanzella Nov 29 '12 at 18:15
• I think a single more complicated Select() would be better than two simple ones: freq.Select(entry => GetTermIndex(entry.Key)). – svick Nov 29 '12 at 20:11
• You are right, I totally missed that. Change has been made – Jeff Vanzella Nov 29 '12 at 20:24

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;

{
List<int[]> documentWordIndexes = new List<int[]>();

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

GenerateDocumentFrequency(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>
{
foreach (var missingTerm in termStatistics.Keys.Where(term => !_wordIndex.ContainsKey(term)))
{
_wordIndex[missingTerm] = _terms.Count;
_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.

• I don't think having a public method that has to be called before the object can be used is a good idea. That's exactly what constructors are for. – svick Nov 29 '12 at 20:13
• @svick I would agree with you if the only thing done there is initialization. It's like XmlSchema class, you can initialize it, and then call Compile to prepare it (in our case - to calculate document stats). If there will be millions of 1-2MB documents submitted, the time for required for parsing would be significant. You can't make constructor async, but it's quite easy to rewrite method to run async – almaz Nov 30 '12 at 9:47
• @Qaesar the class you provided doesn't have public properties or methods, so I don't know what do you expect as result. If the only thing that you're interested in is _inverseDocFreq then you can actually return that value in Load method (and rename it correspondingly). The code corresponding to your's is following: var tf = new IDFMeasure(); tf.Load(allDocs); – almaz Nov 30 '12 at 9:52
• @Qaesar I don't like premature optimizations but if you touched this topic... Are you sure about same performance? I optimized solution to parse documents only once (extract terms and group them), and in both yours and Jeff's variants the same document is parsed 3 times. So my solution should be roughly 2 times faster then yours or Jeff's. And yours/Jeff's solutions should perform about the same since Jeff suggested cosmetic changes that should not affect performance much. – almaz Nov 30 '12 at 16:43