NovelEssay.com Programming Blog

Exploration of Big Data, Machine Learning, Natural Language Processing, and other fun problems.

Extracting important snip-its with C# and Log Likelyhood


How does text summary software pick out the most important ideas to present?

One solution is to use Log Likelyhood to generate a summary of the sentences that contain the important terms and cover the most different topics.


What Log Likelyhood is and why it works can be read here: https://en.wikipedia.org/wiki/Likelihood_function


This article will focus on implementing it in C#. Here's the code I wrote as a translation from the Mahout version. I tried to make it as readable as possible rather than optimizing for performance.

// Log Likelyhood code roughly translated from here:
// http://grepcode.com/file/repo1.maven.org/maven2/org.apache.mahout/mahout-math/0.3/org/apache/mahout/math/stats/LogLikelihood.java#LogLikelihood.logLikelihoodRatio%28int%2Cint%2Cint%2Cint%29
static private double ShannonEntropy(List<Int64> elements)
{
    double sum = 0;
    foreach (Int64 element in elements)
    {
        sum += element;
    }
    double result = 0.0;
    foreach (Int64 element in elements)
    {
        if(element < 0)
        {
            throw new Exception("Should not have negative count for entropy computation (" + element + ")");
        }
        int zeroFlag = (element == 0 ? 1 : 0);
        result += element * Math.Log((element + zeroFlag) / sum);
    }
    return result;
}
/*
    Calculate the Raw Log-likelihood ratio for two events, call them A and B. Then we have:
 	    Event A	Everything but A
        Event B	A and B together (k_11)	B, but not A (k_12)
        Everything but B	A without B (k_21)	Neither A nor B (k_22)
    Parameters:
    k11 The number of times the two events occurred together
    k12 The number of times the second event occurred WITHOUT the first event
    k21 The number of times the first event occurred WITHOUT the second event
    k22 The number of times something else occurred (i.e. was neither of these events
*/
static public double LogLikelihoodRatio(Int64 k11, Int64 k12, Int64 k21, Int64 k22)
{
    double rowEntropy = ShannonEntropy(new List<Int64>() { k11, k12 }) + ShannonEntropy(new List<Int64>() { k21, k22 });
    double columnEntropy = ShannonEntropy(new List<Int64>() { k11, k21 }) + ShannonEntropy(new List<Int64>() { k12, k22 });
    double matrixEntropy = ShannonEntropy(new List<Int64>() { k11, k12, k21, k22 });
    return 2 * (matrixEntropy - rowEntropy - columnEntropy);
}

Now, we have a simple LogLikelihoodRatio function we can call with 4 parameters and get the score result.


Let's say we want to pick out the most important sentences from a particular Wikipedia article in order to summarize it. (See this article for loading Wikipedia in to ElasticSearch: http://blog.novelessay.com/post/loading-wikipedia-in-to-elasticsearch)

Follow these steps:

  1. Pick a Wikipedia article.
  2. Get a Term Frequency dictionary for the whole article.
  3. Parse the article in to sentences.
  4. For each token in each sentence, calculate the Log Likelyhood score with the above LogLikelihoodRatio function.
  5. If the result of LogLikelihoodRatio is less than -10, give that sentence +1 to a weight value.
  6. At the end of each sentence, you have a +X weight value. That can be normalized by the number of words in the sentence.
  7. After you've obtained the weight score from #6 for all of the sentences in an article, you can sort them and pick the most important ones.
For extra credit, you'll want to avoid redundant important sentences. In order to do that, you'll need to score the candidate sentences against the summary's output as you build it.


Here's some code with comments about populating the input values passed to the LogLikelihoodRatio function. Be sure to check the result score is less than -10 before adding a +1 weight.

// http://www.cs.columbia.edu/~gmw/candidacy/LinHovy00.pdf - Section 4.1
Int64 k11 = // frequency of current term in this article
Int64 k12 = // frequency of current term in all of Wikipedia - k11
Int64 k21 = // total count of all terms in this article - k11
Int64 k22 = // total count of all terms in Wikipedia - k12
double termWeight = LogLikelihoodRatio(k11, k12, k21, k22);

if(termWeight < -10)
{
    weightSum++;
}

Obviously, in the above you don't want to be calculating Term Frequency across Wikipedia on-the-fly. K11 and K21 will get calculated as you process an article, but K12 and K22 should be calculated in advance and cached in a lookup dictionary. 


I use LevelDb as my Term Frequency look up dictionary. You can read about using that here: http://blog.novelessay.com/post/fast-persistent-key-value-pairs-in-c-with-leveldb


In order to build your Term Frequency look up dictionary chace, you could process each documents and create your own term frequency output, or use the ElasticSearch plugin for _termList here: https://github.com/jprante/elasticsearch-index-termlist



Text Extraction using C# .Net and Apache Tika


You want to using C# to extract text from documents and web pages. You want it to have high quality and be free. Try the .Net wrapper to the Apache Tika library!


Let's build a sample app and show the use case. First step, start a C# console application with Visual Studio. Use the Nuget package manager and install the TikaOnDotNet.TextExtractor packages.



Then, try this sample code. It shows an example of text extraction examples for a file, Url, and byte array sources.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using TikaOnDotNet.TextExtraction;

namespace TikaTest
{
    class Program
    {
        static void Main(string[] args)
        {

            TextExtractor textExtractor = new TextExtractor();

            // Fun Utf8 strings found here: http://www.columbia.edu/~fdc/utf8/
            string utf8InputString = @"It's a small village in eastern Lower Saxony. The ""oe"" in this case turns out to be the Lower Saxon ""lengthening e""(Dehnungs-e), which makes the previous vowel long (used in a number of Lower Saxon place names such as Soest and Itzehoe), not the ""e"" that indicates umlaut of the preceding vowel. Many thanks to the Óechtringen-Namenschreibungsuntersuchungskomitee (Alex Bochannek, Manfred Erren, Asmus Freytag, Christoph Päper, plus Werner Lemberg who serves as Óechtringen-Namenschreibungsuntersuchungskomiteerechtschreibungsprüfer) for their relentless pursuit of the facts in this case. Conclusion: the accent almost certainly does not belong on this (or any other native German) word, but neither can it be dismissed as dirt on the page. To add to the mystery, it has been reported that other copies of the same edition of the PLZB do not show the accent! UPDATE (March 2006): David Krings was intrigued enough by this report to contact the mayor of Ebstorf, of which Oechtringen is a borough, who responded:";
            // Convert string to byte array
            byte[] byteArrayInput = Encoding.UTF8.GetBytes(utf8InputString);
            // Text Extraction Example for Byte Array
            TextExtractionResult result = textExtractor.Extract(byteArrayInput);
            Console.WriteLine(result.Text);

            // Text Extraction Example for Uri:
            result = textExtractor.Extract(new Uri("http://blog.novelessay.com"));
            Console.WriteLine(result.Text);

            // Text Extraction Example for File
            result = textExtractor.Extract(@"c:\myPdf.pdf");
            Console.WriteLine(result.Text);

            // Note that result also has metadata collection and content type attributes
            //result.Metadata
            //result.ContentType
        }
    }
}

Notice that the TextExtractionResult has a Metadata collection and also a content type attribute. Here's an example of the metadata provided along with the extracted text. It contains many things including author, dates, keywords, title, and description.


      

I've been very pleased with Tika's quality and ability to handle many different file types. I hope you try it out and enjoy it too.


Fast Persistent Key Value Pairs in C# with LevelDb



Let's say we want to crawl the internet, but we don't want to request any given URL more than once. We need to have a collection of URL keys that we can look up. It would be nice if we could have key-value pairs, so that we can give URL keys a value in case we change our minds and want to allow URL request updates every X days. We want it to handle billions of records and be really fast (and free). This article will show how to accomplish that using LevelDb and its C# wrapper.


First, start a Visual Studio C# project and download the LevelDb.Net nuget package. There are a few different one, but this is my favorite. 


You can also find this LevelDb.Net at this Github location:

https://github.com/AntShares/leveldb


First, I'm going to show how to use LevelDb via C#. Later in this article, code shows how to insert and select a large number of records for speed testing.


Let's create a LevelDb:

            Options levelDbOptions = new Options();
            levelDbOptions.CreateIfMissing = true;
            LevelDB.DB levelDb = LevelDB.DB.Open("myLevelDb.dat", levelDbOptions);

Next, we'll insert some keys:

            levelDb.Put(LevelDB.WriteOptions.Default, "Key1", "Value1");
            levelDb.Put(LevelDB.WriteOptions.Default, "Key1", "Value2");
            levelDb.Put(LevelDB.WriteOptions.Default, "Key1", "Value3");
            levelDb.Put(LevelDB.WriteOptions.Default, "Key2", "Value2");

Then, we'll select some keys:

            LevelDB.Slice outputValue;
            if (levelDb.TryGet(LevelDB.ReadOptions.Default, "Key2", out outputValue))
            {
                Console.WriteLine("Key2: Value = " + outputValue.ToString());// Expect: Value2
            }
            if (levelDb.TryGet(LevelDB.ReadOptions.Default, "Key1", out outputValue))
            {
                Console.WriteLine("Key1: Value = " + outputValue.ToString()); // Expect: Value3
            }
            if (!levelDb.TryGet(LevelDB.ReadOptions.Default, "KeyXYZ", out outputValue))
            {
                Console.WriteLine("KeyXYZ: NOT FOUND.");
            }

LevelDb supports many different types of keys and values (strings, int, float, byte[], etc...).

  1. Open instance handle.
  2. Insert = Put
  3. Select = TryGet

That's it! 

But, how fast is it?

Let's build a collection of MD5 hash keys and insert them:

            List<string> seedHashes = new List<string>();
            for (int idx = 0; idx < 500000; idx++)
            {
                byte[] encodedPassword = new UTF8Encoding().GetBytes(idx.ToString());
                byte[] hash = ((HashAlgorithm)CryptoConfig.CreateFromName("MD5")).ComputeHash(encodedPassword);
                string encoded = BitConverter.ToString(hash).Replace("-", string.Empty).ToLower();
                seedHashes.Add(encoded);
            }

            // Start Insert Speed Tests
            Stopwatch stopWatch = new Stopwatch();
            stopWatch.Start();
            foreach(var key in seedHashes)
            {
                levelDb.Put(LevelDB.WriteOptions.Default, key, "1");
            }
            stopWatch.Stop();
            Console.WriteLine("LevelDb Inserts took (ms) " + stopWatch.ElapsedMilliseconds);


Next, let's select each of the keys we just inserted several times:

            // Start Lookup Speed Tests
            stopWatch.Start();
            for (int loopIndex = 0; loopIndex < 10; loopIndex++)
            {
                for(int seedIndex = 0; seedIndex < seedHashes.Count; seedIndex++)
                {
                    if (!levelDb.TryGet(LevelDB.ReadOptions.Default, seedHashes[seedIndex], out outputValue))
                    {
                        Console.WriteLine("ERROR: Key Not Found: " + seedHashes[seedIndex]);
                    }
                }
            }
            stopWatch.Stop();
            Console.WriteLine("LevelDb Lookups took (ms) " + stopWatch.ElapsedMilliseconds);

On my junky 4 year old desktop, 500,000 inserts took just under 60 seconds and 5 Million selects took just over 2 minutes. Here's the program output:


The complete code sample is below:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using LevelDB;
using System.Security.Cryptography;
using System.Diagnostics;

namespace LevelDbExample
{
    class Program
    {
        static void Main(string[] args)
        {

            Options levelDbOptions = new Options();
            levelDbOptions.CreateIfMissing = true;
            LevelDB.DB levelDb = LevelDB.DB.Open("myLevelDb.dat", levelDbOptions);

            // Insert some records
            levelDb.Put(LevelDB.WriteOptions.Default, "Key1", "Value1");
            levelDb.Put(LevelDB.WriteOptions.Default, "Key1", "Value2");
            levelDb.Put(LevelDB.WriteOptions.Default, "Key1", "Value3");
            levelDb.Put(LevelDB.WriteOptions.Default, "Key2", "Value2");

            // Select some records
            LevelDB.Slice outputValue;
            if (levelDb.TryGet(LevelDB.ReadOptions.Default, "Key2", out outputValue))
            {
                Console.WriteLine("Key2: Value = " + outputValue.ToString());// Expect: Value2
            }
            if (levelDb.TryGet(LevelDB.ReadOptions.Default, "Key1", out outputValue))
            {
                Console.WriteLine("Key1: Value = " + outputValue.ToString()); // Expect: Value3
            }
            if (!levelDb.TryGet(LevelDB.ReadOptions.Default, "KeyXYZ", out outputValue))
            {
                Console.WriteLine("KeyXYZ: NOT FOUND.");
            }

            // Build a collection of hash keys
            List<string> seedHashes = new List<string>();
            for (int idx = 0; idx < 500000; idx++)
            {
                byte[] encodedPassword = new UTF8Encoding().GetBytes(idx.ToString());
                byte[] hash = ((HashAlgorithm)CryptoConfig.CreateFromName("MD5")).ComputeHash(encodedPassword);
                string encoded = BitConverter.ToString(hash).Replace("-", string.Empty).ToLower();
                seedHashes.Add(encoded);
            }

            // Start Insert Speed Tests
            Stopwatch stopWatch = new Stopwatch();
            stopWatch.Start();
            foreach(var key in seedHashes)
            {
                levelDb.Put(LevelDB.WriteOptions.Default, key, "1");
            }
            stopWatch.Stop();
            Console.WriteLine("LevelDb Inserts took (ms) " + stopWatch.ElapsedMilliseconds);

            // Start Lookup Speed Tests
            stopWatch.Start();
            for (int loopIndex = 0; loopIndex < 10; loopIndex++)
            {
                for(int seedIndex = 0; seedIndex < seedHashes.Count; seedIndex++)
                {
                    if (!levelDb.TryGet(LevelDB.ReadOptions.Default, seedHashes[seedIndex], out outputValue))
                    {
                        Console.WriteLine("ERROR: Key Not Found: " + seedHashes[seedIndex]);
                    }
                }
            }
            stopWatch.Stop();
            Console.WriteLine("LevelDb Lookups took (ms) " + stopWatch.ElapsedMilliseconds);

            return;
        }
    }
}