001/** 002 * Copyright (c) 2011, The University of Southampton and the individual contributors. 003 * All rights reserved. 004 * 005 * Redistribution and use in source and binary forms, with or without modification, 006 * are permitted provided that the following conditions are met: 007 * 008 * * Redistributions of source code must retain the above copyright notice, 009 * this list of conditions and the following disclaimer. 010 * 011 * * Redistributions in binary form must reproduce the above copyright notice, 012 * this list of conditions and the following disclaimer in the documentation 013 * and/or other materials provided with the distribution. 014 * 015 * * Neither the name of the University of Southampton nor the names of its 016 * contributors may be used to endorse or promote products derived from this 017 * software without specific prior written permission. 018 * 019 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND 020 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 021 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 022 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR 023 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 024 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 025 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON 026 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 027 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 028 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 029 */ 030package org.openimaj.math.util.distance; 031 032/** 033 * Utilities for hamming distance calculations. All hamming distance 034 * calculations between native types are decomposed into the summation over all 035 * bytes in the native type. The hamming distance of byte types is computed 036 * through a lookup table. 037 * 038 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk) 039 * 040 */ 041public class HammingUtils { 042 private static int[] BYTE_BIT_COUNTS; 043 static { 044 BYTE_BIT_COUNTS = new int[256]; 045 046 for (int i = 0; i < 256; i++) { 047 BYTE_BIT_COUNTS[i] = (i & 1) + BYTE_BIT_COUNTS[i / 2]; 048 } 049 } 050 051 private final static int LONG_BYTES = Long.SIZE / Byte.SIZE; 052 private final static int INT_BYTES = Integer.SIZE / Byte.SIZE; 053 private final static int SHORT_BYTES = Short.SIZE / Byte.SIZE; 054 private final static int CHAR_BYTES = Character.SIZE / Byte.SIZE; 055 056 /** 057 * Bitwise (assuming packed bit strings) hamming distance 058 * 059 * @param i1 060 * first bit string 061 * @param i2 062 * second bit string 063 * @return the hamming distance 064 */ 065 public static int packedHamming(double i1, double i2) { 066 final long i1l = Double.doubleToRawLongBits(i1); 067 final long i2l = Double.doubleToRawLongBits(i2); 068 069 return packedHamming(i1l, i2l); 070 } 071 072 /** 073 * Bitwise (assuming packed bit strings) hamming distance 074 * 075 * @param i1 076 * first bit string 077 * @param i2 078 * second bit string 079 * @return the hamming distance 080 */ 081 public static int packedHamming(float i1, float i2) { 082 final int i1l = Float.floatToIntBits(i1); 083 final int i2l = Float.floatToIntBits(i2); 084 085 return packedHamming(i1l, i2l); 086 } 087 088 /** 089 * Bitwise (assuming packed bit strings) hamming distance 090 * 091 * @param i1 092 * first bit string 093 * @param i2 094 * second bit string 095 * @return the hamming distance 096 */ 097 public static int packedHamming(long i1, long i2) { 098 int h = 0; 099 for (int i = 0; i < LONG_BYTES; i++) { 100 final byte b1 = (byte) (i1 & 0xff); 101 i1 >>= 8; 102 103 final byte b2 = (byte) (i2 & 0xff); 104 i2 >>= 8; 105 106 h += packedHamming(b1, b2); 107 } 108 return h; 109 } 110 111 /** 112 * Bitwise (assuming packed bit strings) hamming distance 113 * 114 * @param i1 115 * first bit string 116 * @param i2 117 * second bit string 118 * @return the hamming distance 119 */ 120 public static int packedHamming(int i1, int i2) { 121 int h = 0; 122 for (int i = 0; i < INT_BYTES; i++) { 123 final byte b1 = (byte) (i1 & 0xff); 124 i1 >>= 8; 125 126 final byte b2 = (byte) (i2 & 0xff); 127 i2 >>= 8; 128 129 h += packedHamming(b1, b2); 130 } 131 return h; 132 } 133 134 /** 135 * Bitwise (assuming packed bit strings) hamming distance 136 * 137 * @param i1 138 * first bit string 139 * @param i2 140 * second bit string 141 * @return the hamming distance 142 */ 143 public static int packedHamming(byte i1, byte i2) { 144 return BYTE_BIT_COUNTS[(i1 ^ i2) & 0xFF]; 145 } 146 147 /** 148 * Bitwise (assuming packed bit strings) hamming distance 149 * 150 * @param i1 151 * first bit string 152 * @param i2 153 * second bit string 154 * @return the hamming distance 155 */ 156 public static int packedHamming(char i1, char i2) { 157 int h = 0; 158 for (int i = 0; i < CHAR_BYTES; i++) { 159 final byte b1 = (byte) (i1 & 0xff); 160 i1 >>= 8; 161 162 final byte b2 = (byte) (i2 & 0xff); 163 i2 >>= 8; 164 165 h += packedHamming(b1, b2); 166 } 167 return h; 168 } 169 170 /** 171 * Bitwise (assuming packed bit strings) hamming distance 172 * 173 * @param i1 174 * first bit string 175 * @param i2 176 * second bit string 177 * @return the hamming distance 178 */ 179 public static int packedHamming(short i1, short i2) { 180 int h = 0; 181 for (int i = 0; i < SHORT_BYTES; i++) { 182 final byte b1 = (byte) (i1 & 0xff); 183 i1 >>= 8; 184 185 final byte b2 = (byte) (i2 & 0xff); 186 i2 >>= 8; 187 188 h += packedHamming(b1, b2); 189 } 190 return h; 191 } 192 193 /** 194 * Unpack a binary string ("10011...") into a double 195 * 196 * @param bits 197 * @return a double value with the same bit pattern defined by bits 198 */ 199 public static double unpackDouble(String bits) { 200 return Double.longBitsToDouble(Long.parseLong(bits, 2)); 201 } 202 203 /** 204 * Unpack a binary string ("10011...") into a float 205 * 206 * @param bits 207 * @return a float value with the same bit pattern defined by bits 208 */ 209 public static float unpackFloat(String bits) { 210 return Float.intBitsToFloat(Integer.parseInt(bits, 2)); 211 } 212 213 /** 214 * Unpack a binary string ("10011...") into an int 215 * 216 * @param bits 217 * @return an int value with the same bit pattern defined by bits 218 */ 219 public static int unpackInt(String bits) { 220 return Integer.parseInt(bits, 2); 221 } 222 223 /** 224 * Unpack a binary string ("10011...") into a long 225 * 226 * @param bits 227 * @return a long value with the same bit pattern defined by bits 228 */ 229 public static long unpackLong(String bits) { 230 return Long.parseLong(bits, 2); 231 } 232 233 /** 234 * Unpack a binary string ("10011...") into a short 235 * 236 * @param bits 237 * @return a short value with the same bit pattern defined by bits 238 */ 239 public static short unpackShort(String bits) { 240 return Short.parseShort(bits, 2); 241 } 242 243 /** 244 * Unpack a binary string ("10011...") into a byte 245 * 246 * @param bits 247 * @return a byte value with the same bit pattern defined by bits 248 */ 249 public static byte unpackByte(String bits) { 250 return Byte.parseByte(bits, 2); 251 } 252}