Get the closest color name based on six-color

Question

I am trying to get the most suitable color name depending on the given hex value. For example, if we have the hexadecimal color #f00 , we should get colorname red .

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

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

For instance:

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

So, any ideas on how to get the result closer?

Here is what I did to get the closest color:

 Array.closest = (function () { // http://en.wikibooks.org/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.com/q/11919065/1250044#comment16113902_11919065 return arr.sort(function (a, b) { return levDist(a, str) - levDist(b, str); }); }; }()); 

http://jsfiddle.net/ARTsinn/JUZVd/2/

Another thing is performance! There seems to be a really big problem somewhere that makes this very slow (is this an algorithm?).

Answer 1

Levenshtein’s distance here is not entirely appropriate, because he will compare character by character for equality. You need to check each color separately, and you want 79 be much closer to 80 than 00 .

The following seems to be much closer to what you want, with 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 if both s and t are hexadecimal sixth hexadecimal characters.

Your code is inefficient because you do not need to sort the entire array to get the closest color. Instead, you should just iterate over the array and track the shortest distance.

For instance:

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

Please note that after this change Array.closest() will return a single value, not an array, so you will need to remove [0] further in your code.