I try to get the most matching color name depending on an given hex-value. For example if we have the hex-color #f00 we've to get the colorname red.

'#ff0000' => 'red'
'#000000' => 'black'
'#ffff00' => 'yellow'

I use currently the levenshtein-distance algorithm to get the closest color name, works well so far, but sometimes not as expected.

For example:

'#0769ad' => 'chocolate'
'#00aaee' => 'mediumspringgreen'

So any ideas how to get the result closer?

Here's what I made to get the closest color:

Array.closest = (function () {

    // 
    function levDist(s, t) {
        if (!s.length) return t.length;
        if (!t.length) return s.length;

        return Math.min(
            levDist(s.substring(1), t) + 1,
            levDist(t.substring(1), s) + 1,
            levDist(s.substring(1), t.substring(1)) + (s[0] !== t[0] ? 1 : 0)
        );
    }

    return function (arr, str) {
        // 
        return arr.sort(function (a, b) {
            return levDist(a, str) - levDist(b, str);
        });
    };

}());

/

Another thing is the performance! It seems that it there's somewehere a really big issue that makes this really slow (is it the algorithm?).

I try to get the most matching color name depending on an given hex-value. For example if we have the hex-color #f00 we've to get the colorname red.

'#ff0000' => 'red'
'#000000' => 'black'
'#ffff00' => 'yellow'

I use currently the levenshtein-distance algorithm to get the closest color name, works well so far, but sometimes not as expected.

For example:

'#0769ad' => 'chocolate'
'#00aaee' => 'mediumspringgreen'

So any ideas how to get the result closer?

Here's what I made to get the closest color:

Array.closest = (function () {

    // http://en.wikibooks/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#JavaScript
    function levDist(s, t) {
        if (!s.length) return t.length;
        if (!t.length) return s.length;

        return Math.min(
            levDist(s.substring(1), t) + 1,
            levDist(t.substring(1), s) + 1,
            levDist(s.substring(1), t.substring(1)) + (s[0] !== t[0] ? 1 : 0)
        );
    }

    return function (arr, str) {
        // http://stackoverflow./q/11919065/1250044#ment16113902_11919065
        return arr.sort(function (a, b) {
            return levDist(a, str) - levDist(b, str);
        });
    };

}());

http://jsfiddle/ARTsinn/JUZVd/2/

Another thing is the performance! It seems that it there's somewehere a really big issue that makes this really slow (is it the algorithm?).

• javascript
• performance
• colors
• levenshtein-distance

• 1 For more similar colors it would be better to use HSL colors instead. – Sirko Commented Jun 18, 2013 at 17:58
• 1 You could make the sort step a lot faster if you'd precalculate the distances before sorting. – Pointy Commented Jun 18, 2013 at 18:00
• Also I'm not sure why you wouldn't use a simple cartesian distance putation. (Actually I guess I'd convert to an angular coordinate space and do the distance in HSL or HSV terns.) – Pointy Commented Jun 18, 2013 at 18:00
• 1 i would calc the diff of two colors by averaging the difference between each of the two color's on each R, G, and B channel. ex (3,4,5) and (10,14,18) have an avg diff of 10. – dandavis Commented Jun 18, 2013 at 18:01
• I'll bet you find you have some problem colors that you can leave out of the list. I don't know your problem domain but, perhaps, less is more. If I put up a shade of green and you call it mint or light green or spring green, it might not matter. – Lee Meador Commented Jun 18, 2013 at 18:03

1 Answer 1

Levenshtein distance isn't really appropriate here, because it will pare character by character for equality. You need to check each color separately, and you would want 79 to be much closer to 80 than 00.

The following seems to be a lot closer to what you want, with only minimal changes to your code:

Array.closest = (function () {
    function dist(s, t) {
        if (!s.length || !t.length) return 0;
        return dist(s.slice(2), t.slice(2)) +
            Math.abs(parseInt(s.slice(0, 2), 16) - parseInt(t.slice(0, 2), 16));
    }

    return function (arr, str) {
        return arr.sort(function (a, b) {
            return dist(a, str) - dist(b, str);
        });
    };
}());

Note that this will only give reasonable results when both s and t are 6-character color hex codes.

Your code is inefficient because you don't need to sort the entire array to get the closest color. You should instead just loop through the array and keep track of the shortest distance.

For example:

Array.closest = (function () {
    function dist(s, t) {
        if (!s.length || !t.length) return 0;
        return dist(s.slice(2), t.slice(2)) +
            Math.abs(parseInt(s.slice(0, 2), 16) - parseInt(t.slice(0, 2), 16));
    }

    return function (arr, str) {
        var min = 0xffffff;
        var best, current, i;
        for (i = 0; i < arr.length; i++) {
            current = dist(arr[i], str)
            if (current < min) {
                min = current
                best = arr[i];
            }
        }
        return best;
    };
}());

Note that after this change Array.closest() will return a single value rather than an array, so you will need to remove the [0] further down in your code.