wink

string-hamming-normalized.js

  1. //     wink-distance
  2. //     Distance functions for Bag of Words, Strings,
  3. //     Vectors and more.
  4. //
  5. //     Copyright (C) GRAYPE Systems Private Limited
  6. //
  7. //     This file is part of “wink-distance”.
  8. //
  9. //     Permission is hereby granted, free of charge, to any person obtaining a
  10. //     copy of this software and associated documentation files (the "Software"),
  11. //     to deal in the Software without restriction, including without limitation
  12. //     the rights to use, copy, modify, merge, publish, distribute, sublicense,
  13. //     and/or sell copies of the Software, and to permit persons to whom the
  14. //     Software is furnished to do so, subject to the following conditions:
  15. //
  16. //     The above copyright notice and this permission notice shall be included
  17. //     in all copies or substantial portions of the Software.
  18. //
  19. //     THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  20. //     OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  21. //     FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  22. //     THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  23. //     LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  24. //     FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  25. //     DEALINGS IN THE SOFTWARE.
  27. // ## string
  29. // ### hammingNormalized
  30. /**
  31.  *
  32.  * Computes the normalized hamming distance between two strings. These strings
  33.  * may be of different lengths. Normalized distance is always between 0 and 1.
  34.  *
  35.  * @method string.hammingNormalized
  36.  * @param {string} str1 first string.
  37.  * @param {string} str2 second string.
  38.  * @return {number} normalized hamming distance between `str1` and `str2`.
  39.  * @example
  40.  * hammingNormalized( 'john', 'johny' );
  41.  * // ->  0.2
  42.  * hammingNormalized( 'sam', 'sam' );
  43.  * // -> 0
  44.  * hammingNormalized( 'sam', 'samuel' );
  45.  * // -> 0.5
  46.  * hammingNormalized( 'saturn', 'urn' );
  47.  * // -> 1
  48.  */
  49. var hammingNormalized = function ( str1, str2 ) {
  50.   // As we may need to swap values!
  51.   var s1 = str1,
  52.       s2 = str2;
  53.   // String lengths.
  54.   var s1Length = s1.length,
  55.       s2Length = s2.length;
  56.   // Absolute distance between `s1` & `s2`.
  57.   var distance;
  58.   // Helper variables.
  59.   var i, imax;
  60.   var dividend;
  61.   // Initialize stuff and may have to swap `s1`/`s2`.
  62.   if ( s1Length < s2Length ) {
  63.     // Swap `s1` and `s2` values.
  64.     s1 = [ s2, s2 = s1 ][ 0 ];
  65.     // Initialize distance as the difference in lengths of `s1` & `s2`.
  66.     distance = s2Length - s1Length;
  67.     imax = s1Length;
  68.     // Initialize dividend by the larger string length.
  69.     dividend = s2Length;
  70.   } else {
  71.     // No need to swap, but do initialize stuff.
  72.     distance = s1Length - s2Length;
  73.     imax = s2Length;
  74.     dividend = s1Length;
  75.   }
  76.   // Compute distance.
  77.   for ( i = 0; i < imax; i += 1 ) {
  78.     if ( s1[ i ] !== s2[ i ] ) distance += 1;
  79.   }
  80.   // Normalize the distance & return.
  81.   return ( dividend ) ? ( distance / dividend ) : 0;
  82. }; // hammingNormalized()
  84. module.exports = hammingNormalized;