top of page

Levenshtein Distance

I am very much into optimising my workflow. Each tedious task is an opportunity to test and improve my methods. So here I am "refurbishing" a pretty great spaceship model with my shaders and scripts. Everything is beautifully named, all the great parts, which animate separately. There are 28 parts, which will take up 28 lines of code in my script to assign - which is not a problem at all. But, we can do better. I want an enum and a Dictionary. Some parts will always be animated together, so they can share an enum.

That was quite straightforward. Now, to actually set up the prefab, I need to manually assign each component to its respective Enum group. Which is 28 components. Which would have taken around 4 minutes of work. But it is much better to spend 20 minutes writing an inspector to do this automatically and another 20 to write an article about it. Thanks for reading by the way.

So, how did I do it? Levenshtein Distance - helps find the closest match from text A to text B.

I don't remember where I found the original code for it. The snippet is below. This helped me automate a lot of work over the years.

       private static int LevenshteinDistance(this string s, string t)
        {

            if (s == null || t == null)
            {
                Debug.Log("Compared string is null: " + (s == null) + " " + (t == null));
                return 999;
            }

            if (s.Equals(t))
                return 0;

            var n = s.Length;
            var m = t.Length;
            var d = new int[n + 1, m + 1];

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

            if (m == 0)
                return n;

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

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

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

                    d[i, j] = Math.Min(
                        Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                        d[i - 1, j - 1] + cost);
                }

            return d[n, m];
        }

That is it basically. Helping yourself look through a bunch of stuff to find the match is a very rewarding time investment.


Comments


bottom of page