4 ms·
Normalized Compression Distance (Wikipedia)
- tylermauthe 11y agoThis clever technique has all sorts of applications. Say you have 3 strings, NCD allows you to determine which two of the three are most closely related. I have used this professionally for: - Detecting plagiarism in submitted works - Detecting languages of strings to catch translation issues
- bediger4000 11y agoThe NCD that Wikipedia has you calculate is not the only one. "Common Pitfalls Using the Normalized Compression Distance: What to Watch Out For In A Compressor", by Manuel Cebrian, Manuel Alfonsecsa and Alfonso Ortega (http://www.ims.cuhk.edu.hk/~cis/2005.4/01.pdf http://www.ims.cuhk.edu.hk/~cis/2005.4/01.pdf) has another way to calculate it: NCD(x, y) = max(C(xy) - C(x), C(yx) - C(y))/max(C(x), C(y)) Where x and y are strings, xy is x concatenated with y, and C(x) is the compressed length of string x. This version of NCD is 0.0 for NCD(x,x) for any x, while the Wikipedia version isn't necessarily so. Also this NCD(x,y) = NCD(y,x) which is really handy. For an interesting use, see: http://clair.si.umich.edu/si767/papers/Week12/msa/Bennett.pdf http://clair.si.umich.edu/si767/papers/Week12/msa/Bennett.pd..., "Chain Letters and Evolutionary Histories". Pretty darn good.