folks/potential-match.vala

   1 /*
   2  * Copyright (C) 2011 Collabora Ltd.
   3  *
   4  * This library is free software: you can redistribute it and/or modify
   5  * it under the terms of the GNU Lesser General Public License as published by
   6  * the Free Software Foundation, either version 2.1 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public License
  15  * along with this library.  If not, see <http://www.gnu.org/licenses/>.
  16  *
  17  * Authors:
  18  *       Raul Gutierrez Segales <raul.gutierrez.segales@collabora.co.uk>
  19  */
  20
  21 using Gee;
  22
  23 /**
  24  * Likely-ness of a potential match.
  25  *
  26  * Note that the order should be maintained.
  27  *
  28  * @since 0.5.0
  29  */
  30 public enum Folks.MatchResult
  31 {
  32   /**
  33    * Very low likelihood of a match.
  34    */
  35   VERY_LOW,
  36
  37   /**
  38    * Low likelihood of a match.
  39    */
  40   LOW,
  41
  42   /**
  43    * Medium likelihood of a match.
  44    */
  45   MEDIUM,
  46
  47   /**
  48    * High likelihood of a match.
  49    */
  50   HIGH,
  51
  52   /**
  53    * Very high likelihood of a match.
  54    */
  55   VERY_HIGH,
  56
  57   /**
  58    * Minimum likelihood of a match.
  59    */
  60   MIN = VERY_LOW,
  61
  62   /**
  63    * Maximum likelihood of a match.
  64    */
  65   MAX = VERY_HIGH
  66 }
  67
  68 /**
  69  * This class provides functionality to explore a potential match between
  70  * two individuals.
  71  *
  72  * @since 0.5.0
  73  */
  74 public class Folks.PotentialMatch : Object
  75 {
  76   MatchResult _result;
  77   private Folks.Individual _individual_a;
  78   private Folks.Individual _individual_b;
  79
  80   /**
  81    * A set of e-mail addresses known to be aliases of each other, such as
  82    * various forms of administrator address.
  83    *
  84    * @since 0.5.1
  85    */
  86   public static Set<string> known_email_aliases =
  87       new Gee.HashSet<string> (str_hash, str_equal);
  88
  89   private static double _DIST_THRESHOLD = 0.70;
  90   private const string _SEPARATORS = "._-+";
  91
  92   static construct
  93     {
  94       PotentialMatch.known_email_aliases.add ("admin");
  95       PotentialMatch.known_email_aliases.add ("abuse");
  96       PotentialMatch.known_email_aliases.add ("webmaster");
  97     }
  98
  99   /**
 100    * Whether two individuals are likely to be the same person.
 101    *
 102    * @param a an individual to compare
 103    * @param b another individual to compare
 104    *
 105    * @since 0.5.0
 106    */
 107   public MatchResult potential_match (Individual a, Individual b)
 108     {
 109       this._individual_a = a;
 110       this._individual_b = b;
 111       this._result = MatchResult.MIN;
 112
 113       if (this._individual_a.gender != Gender.UNSPECIFIED &&
 114           this._individual_b.gender != Gender.UNSPECIFIED &&
 115           this._individual_a.gender != this._individual_b.gender)
 116         {
 117           return this._result;
 118         }
 119
 120       /* If individuals share common im-addresses */
 121       this._inspect_im_addresses ();
 122       if (this._result == MatchResult.MAX)
 123         return this._result;
 124
 125       /* If individuals share common e-mails */
 126       this._inspect_emails ();
 127       if (this._result == MatchResult.MAX)
 128         return this._result;
 129
 130       /* If individuals share common phone numbers */
 131       this._inspect_phone_numbers ();
 132       if (this._result == MatchResult.MAX)
 133         return this._result;
 134
 135       /* they have the same (normalised) name? */
 136       this._name_similarity ();
 137       if (this._result == MatchResult.MAX)
 138         return this._result;
 139
 140       return this._result;
 141     }
 142
 143   private void _inspect_phone_numbers ()
 144     {
 145       var set_a = this._individual_a.phone_numbers;
 146       var set_b = this._individual_b.phone_numbers;
 147
 148       foreach (var phone_fd_a in set_a)
 149         {
 150           foreach (var phone_fd_b in set_b)
 151             {
 152               if (phone_fd_a.values_equal (phone_fd_b))
 153                 {
 154                   this._result = MatchResult.HIGH;
 155                   return;
 156                 }
 157             }
 158         }
 159     }
 160
 161   /* Approach:
 162    * - taking in account family, given, prefix, suffix and additional names
 163    *   we give some points for each non-empty match
 164    *
 165    * @since 0.5.0
 166    */
 167   private void _name_similarity ()
 168     {
 169       double similarity = 0.0;
 170       bool exact_match = false;
 171
 172       if (this._look_alike (this._individual_a.nickname,
 173               this._individual_b.nickname))
 174         {
 175           similarity += 0.20;
 176         }
 177
 178       if (this._look_alike_or_identical (this._individual_a.full_name,
 179               this._individual_b.full_name,
 180               out exact_match) ||
 181           this._look_alike_or_identical (this._individual_a.alias,
 182               this._individual_b.full_name,
 183               out exact_match) ||
 184           this._look_alike_or_identical (this._individual_a.full_name,
 185               this._individual_b.alias,
 186               out exact_match) ||
 187           this._look_alike_or_identical (this._individual_a.alias,
 188               this._individual_b.alias,
 189               out exact_match))
 190         {
 191           similarity += 0.70;
 192         }
 193
 194       var _a = this._individual_a.structured_name;
 195       var _b = this._individual_b.structured_name;
 196
 197       if (_a != null && _b != null)
 198         {
 199           var a = (!) _a;
 200           var b = (!) _b;
 201
 202           if (a.is_empty () == false && a.equal (b))
 203             {
 204               this._result = MatchResult.HIGH;
 205               return;
 206             }
 207
 208           if (Folks.Utils._str_equal_safe (a.given_name, b.given_name))
 209             similarity += 0.20;
 210
 211           if (this._look_alike (a.family_name, b.family_name) &&
 212               this._look_alike (a.given_name, b.given_name))
 213             {
 214               similarity += 0.40;
 215             }
 216
 217           if (Folks.Utils._str_equal_safe (a.additional_names,
 218                   b.additional_names))
 219             similarity += 0.5;
 220
 221           if (Folks.Utils._str_equal_safe (a.prefixes, b.prefixes))
 222             similarity += 0.5;
 223
 224           if (Folks.Utils._str_equal_safe (a.suffixes, b.suffixes))
 225             similarity += 0.5;
 226         }
 227
 228       debug ("[name_similarity] Got %f\n", similarity);
 229
 230       if (similarity >= this._DIST_THRESHOLD)
 231         {
 232           int inc = 2;
 233           /* We need exact matches to go to at least HIGH, or otherwise its
 234              not possible to get a HIGH match for e.g. a facebook telepathy
 235              persona, where alias is the only piece of information
 236              available */
 237           if (exact_match)
 238             inc += 1;
 239           this._result = this._inc_match_level (this._result, inc);
 240         }
 241     }
 242
 243   /**
 244    * Number of equal IM addresses between two individuals.
 245    *
 246    * This compares the addresses without comparing their associated protocols.
 247    *
 248    * @since 0.5.0
 249    */
 250   public void _inspect_im_addresses ()
 251     {
 252       var addrs = new HashSet<string> ();
 253
 254       foreach (var im_a in this._individual_a.im_addresses.get_values ())
 255         {
 256           addrs.add (im_a.value);
 257         }
 258
 259       foreach (var im_b in this._individual_b.im_addresses.get_values ())
 260         {
 261           if (addrs.contains (im_b.value) == true)
 262             {
 263               this._result = MatchResult.HIGH;
 264               return;
 265             }
 266         }
 267     }
 268
 269   /**
 270    * Inspect email addresses.
 271    *
 272    * @since 0.5.0
 273    */
 274   private void _inspect_emails ()
 275     {
 276       var set_a = this._individual_a.email_addresses;
 277       var set_b = this._individual_b.email_addresses;
 278
 279       foreach (var fd_a in set_a)
 280         {
 281           string[] email_split_a = fd_a.value.split ("@");
 282
 283           /* Sanity check for valid e-mail addresses. */
 284           if (email_split_a.length < 2)
 285             {
 286               warning ("Invalid e-mail address when looking for potential " +
 287                   "match: %s", fd_a.value);
 288               continue;
 289             }
 290
 291           string[] tokens_a =
 292             email_split_a[0].split_set (this._SEPARATORS);
 293
 294           foreach (var fd_b in set_b)
 295             {
 296               string[] email_split_b = fd_b.value.split ("@");
 297
 298               /* Sanity check for valid e-mail addresses. */
 299               if (email_split_b.length < 2)
 300                 {
 301                   warning ("Invalid e-mail address when looking for " +
 302                       "potential match: %s", fd_b.value);
 303                   continue;
 304                 }
 305
 306               if (fd_a.value == fd_b.value)
 307                 {
 308                   if (PotentialMatch.known_email_aliases.contains
 309                       (email_split_a[0]) == true)
 310                     {
 311                       if (this._result < MatchResult.HIGH)
 312                         {
 313                           this._result = MatchResult.LOW;
 314                         }
 315                     }
 316                   else
 317                     {
 318                       this._result = MatchResult.HIGH;
 319                       return;
 320                     }
 321                 }
 322               else
 323                 {
 324                   string[] tokens_b =
 325                     email_split_b[0].split_set (this._SEPARATORS);
 326
 327                   /* Do we have: first.middle.last@ ~= fml@ ? */
 328                   if (this._check_initials_expansion (tokens_a, tokens_b))
 329                     {
 330                       this._result = MatchResult.MEDIUM;
 331                     }
 332                   /* So we have splitted the user part of the e-mail
 333                    * address into tokens. Lets see if there is some
 334                    * matches between tokens.
 335                    * As in: first.middle.last@ ~= [first,middle,..]@  */
 336                   else if (this._match_tokens (tokens_a, tokens_b))
 337                     {
 338                       this._result = MatchResult.MEDIUM;
 339                     }
 340                }
 341             }
 342         }
 343     }
 344
 345   /* We are after:
 346    * you.are.someone@ =~ yas@
 347    */
 348   private bool _check_initials_expansion (string[] tokens_a, string[] tokens_b)
 349     {
 350       if (tokens_a.length > tokens_b.length &&
 351           tokens_b.length == 1)
 352         {
 353           return this._do_check_initials_expansion (tokens_a, tokens_b[0]);
 354         }
 355       else if (tokens_b.length > tokens_a.length &&
 356           tokens_a.length == 1)
 357         {
 358           return this._do_check_initials_expansion (tokens_b, tokens_a[0]);
 359         }
 360       return false;
 361     }
 362
 363   private bool _do_check_initials_expansion (string[] expanded_name,
 364       string initials)
 365     {
 366       if (expanded_name.length != initials.length)
 367         return false;
 368
 369       for (int i=0; i<expanded_name.length; i++)
 370         {
 371           if (expanded_name[i][0] != initials[i])
 372             return false;
 373         }
 374
 375       return true;
 376     }
 377
 378   /*
 379    * We should probably count how many tokens matched?
 380    */
 381   private bool _match_tokens (string[] tokens_a, string[] tokens_b)
 382     {
 383       /* To find matching items from 2 sets its more efficient
 384        * to make the outer loop go with the smaller set. */
 385       if (tokens_a.length > tokens_b.length)
 386         return this._do_match_tokens (tokens_a, tokens_b);
 387       else
 388         return this._do_match_tokens (tokens_b, tokens_a);
 389     }
 390
 391   private bool _do_match_tokens (string[] bigger_set, string[] smaller_set)
 392     {
 393       for (var i=0; i < smaller_set.length; i++)
 394         {
 395           for (var j=0; j < bigger_set.length; j++)
 396             {
 397               if (smaller_set[i] == bigger_set[j])
 398                 return true;
 399             }
 400         }
 401
 402       return false;
 403     }
 404
 405   private MatchResult _inc_match_level (
 406       MatchResult current_level, int times = 1)
 407     {
 408       MatchResult ret = current_level + times;
 409       if (ret > MatchResult.MAX)
 410         ret = MatchResult.MAX;
 411
 412       return ret;
 413     }
 414
 415   private bool _look_alike_or_identical (string? a, string? b, out bool exact)
 416     {
 417       exact = false;
 418       if (a == null || a == "" || b == null || b == "")
 419         {
 420           return false;
 421         }
 422
 423       if (a == b)
 424         {
 425           exact = true;
 426           return true;
 427         }
 428
 429       // a and b look alike if their Jaro distance is over the threshold.
 430       return (this.jaro_dist ((!) a, (!) b) >= this._DIST_THRESHOLD);
 431     }
 432
 433   private bool _look_alike (string? a, string? b)
 434     {
 435       if (a == null || a == "" || b == null || b == "")
 436         {
 437           return false;
 438         }
 439
 440       // a and b look alike if their Jaro distance is over the threshold.
 441       return (this.jaro_dist ((!) a, (!) b) >= this._DIST_THRESHOLD);
 442     }
 443
 444   /* Based on:
 445    *  http://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance
 446    *
 447    * d = 1/3 * ( m/|s1| + m/|s2| + (m - t)/m )
 448    *
 449    *   where
 450    *
 451    * m = matching characters
 452    * t = number of transpositions
 453    */
 454   private double jaro_dist (string s1, string s2)
 455     {
 456       double distance;
 457       int max = s1.length > s2.length ? s1.length : s2.length;
 458       int max_dist = (max / 2) - 1;
 459       double t;
 460       double m = (double) this._matches (s1, s2, max_dist, out t);
 461       double len_s1 = (double) s1.length;
 462       double len_s2 = (double) s2.length;
 463       double a = m / len_s1;
 464       double b = m / len_s2;
 465       double c = 0;
 466
 467       if ((int) m > 0)
 468         c = (m - t) / m;
 469
 470       distance = (1.0/3.0) * (a + b + c);
 471
 472       debug ("[jaro_dist] Distance for %s and %s: %f\n", s1, s2, distance);
 473
 474       return distance;
 475     }
 476
 477   /* Calculate matches and transpositions as defined by the Jaro distance.
 478    */
 479   private int _matches (string s1, string s2, int max_dist, out double t)
 480     {
 481       int matches = 0;
 482       t = 0.0;
 483
 484       for (int i=0; i < s1.length; i++)
 485         {
 486           var look_for = s1.slice (i, i + 1);
 487           int contains = this._contains (s2, look_for, i, max_dist);
 488           if (contains >= 0)
 489             {
 490               matches++;
 491               if (contains > 0)
 492                 t += 1.0;
 493             }
 494         }
 495
 496       debug ("%s and %s have %d matches and %f / 2 transpositions\n",
 497           s1, s2, matches, t);
 498
 499       t = t / 2.0;
 500       return matches;
 501     }
 502
 503   /* If haystack contains c in pos return 0, if it contains
 504    * it withing the bounds of max_dist return abs(pos-pos_found).
 505    * If its not found, return -1. */
 506   private int _contains (string haystack, string c, int pos, int max_dist)
 507     {
 508       if (pos < haystack.length && haystack.slice (pos, pos + 1) == c)
 509         return 0;
 510
 511       for (int i=pos-max_dist; i <= pos + max_dist; i++)
 512         {
 513           if (i < 0 || i >= haystack.length)
 514             continue;
 515
 516           var str = haystack.slice (i, i + 1);
 517           if (str == c)
 518             return (pos - i).abs ();
 519         }
 520
 521       return -1;
 522     }
 523 }