include/it/distance.h

Go to the documentation of this file.
00001 /*
00002    libit - Library for basic source and channel coding functions
00003    Copyright (C) 2005-2005 Vivien Chappelier, Herve Jegou
00004 
00005    This library is free software; you can redistribute it and/or
00006    modify it under the terms of the GNU Library General Public
00007    License as published by the Free Software Foundation; either
00008    version 2 of the License, or (at your option) any later version.
00009 
00010    This library is distributed in the hope that it will be useful,
00011    but WITHOUT ANY WARRANTY; without even the implied warranty of
00012    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013    Library General Public License for more details.
00014 
00015    You should have received a copy of the GNU Library General Public
00016    License along with this library; if not, write to the Free
00017    Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00018 */
00019 
00020 /*
00021   Base class for convolutional codes.
00022   Copyright (C) 2005 Vivien Chappelier, Herve Jegou
00023 */
00024 
00025 #ifndef __it_distance_h
00026 #define __it_distance_h
00027 
00028 #include <it/types.h>
00029 #include <it/vec.h>
00030 #include <it/mat.h>
00031 
00032 /*---------------------------------------------------------------------------*/
00033 /*! \defgroup dis Distances                                                  */
00034 /* @{                                                                        */
00035 /*---------------------------------------------------------------------------*/
00036 
00037 /* Return the Hamming distance between two vectors. 
00038    The Hamming distance is the number of elements that are not equal. If the vectors are 
00039    not of the same size, the distance is increased by the difference of lengths.          */
00040 int  vec_distance_hamming (vec v1, vec v2);
00041 int  ivec_distance_hamming (ivec v1, ivec v2);
00042 int  bvec_distance_hamming (bvec v1, bvec v2);
00043 
00044 /* Return the symbol error rate or bit error rate corresponding to the distance 
00045    between the input vector and the output vector. If v2 has a smaller size than 
00046    v1, then all the symbols which are not received are assumed to be in error. 
00047    If v2 has a greater size, the symbols are discarded (but not added to increase the ser.*/
00048 double vec_ser (vec v1, vec v2);
00049 double ivec_ser (ivec v1, ivec v2);
00050 double bvec_ber (bvec v1, bvec v2);
00051 
00052 /* Return the levenshtein distance between two vectors.
00053    The distance is computed with the algorithm of Wagner and Fischer.
00054    The cost of insertion, deletion and substitution operations are parameters. 
00055    Usually, they are all assigned 1.                                                      */
00056 int  ivec_distance_levenshtein (ivec v1, ivec v2, int cost_ins,
00057         int cost_del, int cost_sub);
00058 
00059 /* Return the distance derived from a norm between two vectors. 
00060    This distance is given by the norm of the difference between the two vectors.
00061    If the vectors are not of the same size, the distance is increased assuming 
00062    that missing elements are equal to 0.
00063    Note that norm is often assigned 2 (square error)
00064 */
00065 double vec_distance_norm (vec v1, vec v2, double norm);
00066 double mat_distance_norm (mat v1, mat v2, double norm);
00067 
00068 int ivec_distance_norm1 (ivec v1, ivec v2);
00069 
00070 
00071 /* Return the Mean Square Error (MSE) between vector v2 and vector v1.
00072    Missing elements are assumed to be equal to the parameter 'rec_value'. */
00073 double vec_distance_mse (vec v1, vec v2, double rec_value);
00074 double mat_distance_mse (mat v1, mat v2, double rec_value);
00075 
00076 double ivec_distance_mse (ivec v1, ivec v2, double rec_value);
00077 double imat_distance_mse (imat v1, imat v2, double rec_value);
00078 
00079 /* Return the energy of the vector of differences. Vectors should have the same size. */
00080 long ivec_distance_sqr (ivec v1, ivec v2);
00081 
00082 /* Return the Kullback-Leibler pseudo-distance between distribution pdf1 and pdf2.
00083    In other terms, the quantity \sum_{a in A} pdf1(a) log2(pdf1(a)/log(pdf1(a)/pdf2(a))) 
00084    is computed                                                                            */
00085 double vec_distance_kullback_leibler (vec pdf1, vec pdf2);
00086 
00087 
00088 /* compute the matrix of distance associated with a set of vectors
00089    Note that the vectors are assumed to be stored in rows          */
00090 mat compute_distance_matrix (mat v, double nr);
00091 
00092 
00093 /*----------------------------------------------------------------*/
00094 /*             Distances between sparse vectors                   */
00095 
00096 /* compute the distance between two sparse vectors */
00097 double spvec_distance_norm1 (ivec svi1, vec sv1, ivec svi2, vec sv2);
00098 int spivec_distance_norm1 (ivec svi1, ivec sv1, ivec svi2, ivec sv2);
00099 
00100 double spvec_distance_norm2 (ivec svi1, vec sv1, ivec svi2, vec sv2);
00101 
00102 /* compute the square of the euclidean distance */
00103 double spvec_distance_sqr (ivec svi1, vec sv1, ivec svi2, vec sv2);
00104 int spivec_distance_sqr (ivec svi1, ivec sv1, ivec svi2, ivec sv2);
00105 
00106 /* @} */
00107 
00108 #endif

Hosted by
Copyright (C) 2005-2006 Hervé Jégou
Vivien Chappelier
Francois Cayre
libit logo courtesy of Jonathan Delhumeau