C# Levenshtein Distance (Difference Between 2 Strings)

If you want to match approximate strings with fuzzy logic, use the Levenshtein distance algorithm. Many projects need this logic, including programs such as spell-checkers, suggestion searches and plagiarism detectors.

In information theory and computer science, the Levenshtein distance is a metric for measuring the amount of difference between two sequences (i.e., the so called edit distance). The Levenshtein distance between two strings is given by the minimum number of operations needed to transform one string into the other, where an operation is an insertion, deletion, or substitution of a single character. A generalization of the Levenshtein distance (Damerau–Levenshtein distance) allows the transposition of two characters as an operation.

I needed to simply to measure the difference between two independant strings.  This was my saving grace, and the C# implementation I found:

using System;

/// 
/// Contains approximate string matching
/// 
static class LevenshteinDistance
{
    /// 
    /// Compute the distance between two strings.
    /// 
    ///The first of the two strings.
    ///The second of the two strings.
    /// The Levenshtein cost.
    public static int Compute(string s, string t)
    {
        int n = s.Length;
        int m = t.Length;
        int[,] d = new int[n + 1, m + 1];

        // Step 1
        if (n == 0)
        {
            return m;
        }

        if (m == 0)
        {
            return n;
        }

        // Step 2
        for (int i = 0; i <= n; d[i, 0] = i++)
        {
        }

        for (int j = 0; j <= m; d[0, j] = j++)
        {
        }

        // Step 3
        for (int i = 1; i <= n; i++)
        {
            //Step 4
            for (int j = 1; j <= m; j++)
            {
                // Step 5
                int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;

                // Step 6
                d[i, j] = Math.Min(
                    Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                    d[i - 1, j - 1] + cost);
            }
        }
        // Step 7
        return d[n, m];
    }
}

What’s the best Way for 2 Processes to Communicate in .Net?

While trawling the internet the other day, I came across this question, and thought it might be something that others might like to know.  The question was:

What’s the best (or maybe not the best — just good) way for two processes in the same machine to communicate, using .NET?

Actually the two processes in the app I’m working on aren’t even two different programs; they’re just two instances of the same EXE. I wanted to do something like a singleton app, but have it per user (meaning a Terminal Server or Citrix or App-V server with multiple users should be able to launch their own single copy of the app). If another instance is run by the same user, it should just delegate the task to the already running instance, then exit. Only one instance per user of the program should be running. So far I’ve done (thanks to StackOverflow) the part that detects whether an instance of the app is already running, using Mutex. But I need the second app instance to be able to send data to the first app instance.

I’m leaning towards using named pipes and WCF’s NetNamedPipeBinding for this, but if you have better ideas I’ll really appreciate it. Thanks 🙂

IPC is what I’ve used in the past for this. And it is supprisingly easy. .Net remoting is a good option but unfortunately it is a restricted option becasue you can’t for example use it on the CF.

Below is a copy of the class I use to perform Inter-process Communication, you can use it in conjuction with a MutEx if you wish, but it isnt necessary. As long as the “pMappedMemoryName” and “pNamedEventName” are the same in both processes, it should work just fine. I tried to make it as event driven as possible.

The class looks a little like this:

  public class IpcService {
    private IServiceContext mContext;
    const int maxLength = 1024;
    private Thread listenerThread;
    private readonly string mMappedMemoryName;
    private readonly string mNamedEventName;
    public event EventHandler IpcEvent;
    private readonly bool mPersistantListener;

    public IpcService(bool pPersistantListener)
      : this(pPersistantListener, "IpcData", "IpcSystemEvent") {
      ;
    }

    public IpcService(bool pPersistantListener, string pMappedMemoryName, string pNamedEventName) {
      mPersistantListener = pPersistantListener;
      mMappedMemoryName = pMappedMemoryName;
      mNamedEventName = pNamedEventName;
    }

    public void Init(IServiceContext pContext) {
      mContext = pContext;
      listenerThread = new Thread(new ThreadStart(listenUsingNamedEventsAndMemoryMappedFiles));
      listenerThread.IsBackground = !mPersistantListener;
      listenerThread.Start();
    }

    private void listenUsingNamedEventsAndMemoryMappedFiles() {
      IntPtr hWnd = EventsManagement.CreateEvent(true, false, mNamedEventName);
      while (listenerThread != null) {
        if (Event.WAITOBJECT == EventsManagement.WaitForSingleObject(hWnd, 1000)) {
          string data = Peek();
          EventsManagement.ResetEvent(hWnd);
          EventHandler handler = IpcEvent;
          if (handler != null) handler(this, new TextualEventArgs(data));
        }
      }
      EventsManagement.SetEvent(hWnd);
      Thread.Sleep(500);
      HandleManagement.CloseHandle(hWnd);
    }

    public void Poke(string format, params object[] args) {
      Poke(string.Format(format, args));
    }

    public void Poke(string somedata) {
      using (MemoryMappedFileStream fs = new MemoryMappedFileStream(mMappedMemoryName, maxLength, MemoryProtection.PageReadWrite)) {
        fs.MapViewToProcessMemory(0, maxLength);
        fs.Write(Encoding.ASCII.GetBytes(somedata + "\0"), 0, somedata.Length + 1);
      }
      IntPtr hWnd = EventsManagement.CreateEvent(true, false, mNamedEventName);
      EventsManagement.SetEvent(hWnd);
      Thread.Sleep(500);
      HandleManagement.CloseHandle(hWnd);
    }

    public string Peek() {
      byte[] buffer;
      using (MemoryMappedFileStream fs = new MemoryMappedFileStream(mMappedMemoryName, maxLength, MemoryProtection.PageReadWrite)) {
        fs.MapViewToProcessMemory(0, maxLength);
        buffer = new byte[maxLength];
        fs.Read(buffer, 0, buffer.Length);
      }
      string readdata = Encoding.ASCII.GetString(buffer, 0, buffer.Length);
      return readdata.Substring(0, readdata.IndexOf('\0'));
    }

    private bool mDisposed = false;

    public void Dispose() {
      if (!mDisposed) {
        mDisposed = true;
        if (listenerThread != null) {
          listenerThread.Abort();
          listenerThread = null;
        }
      }
    }

    ~IpcService() {
      Dispose();
    }

  }

Simply use the Poke method to write data, and the Peek method to read it, although I designed it to automatically fire an event when new data is available. In this way you can simply subscribe to the IpcEvent event and not have to worry about expensive and constant polls.  Enjoy.

Simple Solution to Illegal Cross-thread Calls in C#

If the thread call is “illegal” (i.e. the call affects controls that were not created in the thread it is being called from) then you need to create a delegate so that even if the decision / preparation for the change is not done in the control-creating thread, any resultant modification of them will be. Basically, this is a long winded way of saying you can’t (and shouldn’t) access controls on a form from a thread that didn’t create the control in the first place.

.Net version older than 2.0 (1.0 and 1.1) would actually allow this to happen, but cross-threaded operations should always be dealt with cautiously and properly. The technical solution to the problem is to create a delegate function, and pass the delegate function to the Invoke() method on the control, which allows code to execute as if it was being executed from the control’s parent thread, but if you need to do this a lot, all the extra functions and delegates can make the code unreadable, if a lot of it is going on. Fortunately there are 2 “cheats” to the problem. The first is to use the ThreadStart delegate (System.Threading namespace), since its already setup as a simple delegate with one parameter. The second, is to use anonymous delegates, which is something I have covered in the past.

if (label1.InvokeRequired) {
  label1.Invoke(
    new ThreadStart(delegate {
      label1.Text = "some text changed from some thread";
    }));
} else {
  label1.Text = "some text changed from the form's thread";
}

Now, the more curious and perceptive of you are asking, why not just use control.Invoke() everytime you change a value? Well, the truth is you could. But calling control.Invoke() has a great deal more overhead than not calling it. However, when you avoid calling control.Invoke() and access UI objects directly from the UI thread, you’re writing incorrect code that could cause stability problems in your application.

The problem is that a “window” object in the underlying Windowing API in Win32, as represented by the HWND handle, has thread-affinity. It must be directly accessed only from the thread that created it. If it’s not, the results are unpredictable and can cause subtle, intermittent bugs.

By all means skip control.Invoke() if you’ve only got one thread. However, if you need to affect a UI object from a worker thread, you absolutely must use control.Invoke() to transition back to the UI thread before making that call or you’re in for a world of pain.

Moving the Default PostgreSQL Data Directory (Windows)

PostgreSQL for Windows installs the PGDATA directory by default into “C:\<Program Files>\PostgreSQL\some version\data”.  While is usually ok for development and even some production environments, it can be somewhat limited given the typically large amount of disk activity on (what is normally) the system volume.

This step-by-step post aims to explain the fastest way to change the default PGDATA directory to another location.

Step 1:

Close all application that are currently connected to your database, then go to Windows Services Management and stop the PostgreSQL service.  Naturally, the fastest way to get to Windows Services Management is by right clicking on my computer -> manage, and then click on the services node in the computer management tree:

Once the Postgres service is stopped, leave computer the Computer Management Console open (we’ll need it again in a second).

Step 2:

Copy the “C:\<Program Files>\PostgreSQL\some version\data” directory to the new location.  In my own attempts, moves do not seem to work, but the redundant disk usage should be pretty minimal and at least you will have an old backup in the default location if something goes wrong.

Step 3 (Very Important):

Rick click on the new “data” directory, and click properties, and select the security tab.  Give the local Postgres user (or for advanced users the user account Postgres uses) and give full permission on that direct and all child objects (sometimes you need to reset the child permission inheritance).  Click ok on the properties window.

Step 4:

Open regedit.exe by clicking on the start button and typing “rededit” in either the search box, or start->run box (depending on whether your using Vista or XP) and navigate to the “HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\pgsql-some version” branch. Double click on “ImagePath” and change the directory after the “–D” option to your new location. If the path to your new location contains spaces, you should then enclose it with quotes.

Step 5:

Close regedit and go back to Computer Management and restart the Postgres service. Close Computer management.

After  completeing these steps, and assuming something hasn’t gone wrong, you should now have Postgres running from the new location.

(Reference: http://wiki.postgresql.org/wiki/Change_the_default_PGDATA_directory_on_Windows)

Using NSIS to Install an ASP.NET Web Application to IIS

One of the main projects I have been working on recently has been a .Net 3.5 web project.  While I have always liked the agile development and IDE which .Net and Visual Studio provide, The Setup Project template (which creates MSI installation files) has always been hard to use, difficult to customise and very restrictive.

In the past, I’ve used the NSIS (Nullsoft Scriptable Install System), which:

… is a professional open source system to create Windows installers. It is designed to be as small and flexible as possible and is therefore very suitable for internet distribution.(http://nsis.sourceforge.net).

However, despite the great number of resources and example scripts to do anything you can pretty-well imagine, a simple straight up installer script to modify IIS using NSIS to install the web application seems to be quite a challenge.

I did, however, stumble across a blog faced with a similar issue, wanting an installer system to perform the following tasks:

  • Show ‘Hello’ page
  • Ask to select virtual directory name and installation folder
  • Ask about database connection string (user name, password etc)
  • Copy working files to destination folder
  • Create Virtual Directory
  • Create Database
  • Show ‘Installation complete’ page
  • Open installed application in web browser

They provided an example script which I repost here should the direct link ever go down.  They do mention on their blog a number of future enhancements missing from the installer script:

There are many things should be improved in installer. First is improvement of virtual folder creation. User should have possibility to choose between different virtual servers. Also correct default installation directory should be suggested (now it hardcoded as “C:\Inetpub\wwwroot\TargetProcess2”). Installer should detect if .Net 2.0 is installed and help to download and install it. Installer should upgrade old version of TargetProcess to new.

Given that I have quite a bit of experience with NSIS, I think those points should be mostly trivial and I will be sure to post the updated example script to this blog once it’s complete.


UPDATE
This url http://weblogs.asp.net/krobertson/archive/2004/04/01/106002.aspx looks promising, not exactly what I want to do but a useful reference never-the-less.

Autosizing Textarea (using Prototype)

Recently, I have been doing a lot of Model-View-Controller work in ASP.NET which has caused me to have to use some more “old school” style HTML controls, instead of the .Net Server-side Controls I am so used to.  I came along an interesting problem where I needed a text area which automatically changed it’s height to fit all the text in without a horizontal scroll bar, much like Facebook does with it’s wall.

I also wanted the Javascript to use the Javascript library for the event listening so I didn’t need to worry about the event handler quirks of the various browsers (and becasue that’s what I know).  I post the solution that worked for me in the interest of creative commons.




  
  


  

  

If you have a textarea, with the wrap=”off” attribute set, then its even easier. Just replace the script tage above with this one:

WorkingSet vrs WorkingSet64

Recently I’ve been doing a lot of work with the Process.GetCurrentProcess() method and since the application I am building is being developed on the 2.0 64bit framework, I was worried that if I used Process.GetCurrentProcess().WorkingSet64, that the application wouldnt work with 32bit OS’s, since WorkingSet was deprecated, but not enforced.

After some thought though, I realised that the WorkingSet returns the amount of memory being used by the process as an integer (32 bit signed integer). OK, so the maximum value of an integer is 2,147,483,647 — which is remarkably close to the total amount of memory that a process can have in its working set.  Except, there is actually a switch in Windows that will allow a process to use 3 gig of memory instead of 2 gig.  So what would happen when you poll the WorkingSet you will get a negative number, a really big small negative number. Usually, in the realm of -2,147,482,342.  As the more perceptive of you have guessed the problem already.  The overflow bit.

So you ask, why didn’t Microsoft just change the API so WorkingSet returned an Int64 instead of an Int32.  Well they could, except that they would break applications built against version 1.0 and 1.1 frameworks, as this post explains.

But after all this pondering, it turns out that WorkingSet64 des exactly what WorkingSet does, except returns an Int64 instead – and as such is less prone to breaks.  Works with both 32bit and 64bit Windows and Frameworks and all is good with the world.

Install A .Net Service Via Command Line

I’ve been working with .Net services for the last few years or so and it is often convenient for debugging to be able to install your debug version. Since it is a major pain to build an installer every time we want to test, we used the command line utility InstallUtil.exe that comes with the .Net Framework to install and uninstall our services in batch files.

If you’ve installed .Net in the default location InstallUtil.exe lives in C:\Windows\Microsoft.Net\Framework\v2.0.50727\InstallUtil.exe
in the respective framework version directory.

Below is an example batch file.

C:\Windows\Microsoft.Net\Framework\v2.0.50727\InstallUtil.exe [your-service.exe]

and to uninstall, use the /u flag

C:\Windows\Microsoft.Net\Framework\v2.0.50727\InstallUtil.exe /u [your-service.exe]

Using these batch files we just create short cuts to them and can double click the short cut to install or uninstall. Of course you can install/uninstall more than one service in the batch file.

Be sure to also check out the other flags available for InstallUtil.

“Project type is not supported by this installation” error in Visual Studio 2005

In the office recently, some of our Visual Studio machines have been having trouble opening up some web applications created by other staff.  They get greeted with the rather unpleasant (and not very useful) “Project type is not supported by this installation” message.

After som googling on the issue, I stumbled across a blog on Ira Miller‘s blog, talking about the new version of the web applications add on for visual studio 2005, which, apparently is not backwards compatible with the old.

Leaving the arguments about legacy support and upgrade paths aside, I found that an easy solution to the problem is to simply download the Microsoft Visual Studio 2005 – Update to Support Web Application Projects and install it on the machine in question.  We’ve found that in 2 instances, this solved our troubles.

More information about the Visual Studio 2005 Web Application Projects, can be found here.