src/site/apt/experts.apt

   1  ----\r
   2  Expert mode\r
   3  ----\r
   4  Haruaki Tamada\r
   5  ----\r
   6  2007-06-29\r
   7  ----\r
   8 \r
   9 Comparison Methods\r
  10 \r
  11  Let <p> and <q> be a target class files, and <f> be a birthmark\r
  12 extraction method.  Then, <f(p)> and <f(q)> be a extracted birthmarks\r
  13 which elements are <(e^p_1, e^p_2, ..., e^p_n)> and <(e^q_1, e^q_2,\r
  14 ..., e^q_m)>.\r
  15 \r
  16 *Plain\r
  17 \r
  18  Let <L> be a number of matched elements of two birthmarks and same\r
  19 index.  Then, the similarity of this method is calculated by\r
  20 \r
  21  <L> / <(n + m)>\r
  22 \r
  23 *Logical AND\r
  24 \r
  25  |<f(p) cap f(q)>| / |<f(p)>| |<f(q)>|\r
  26 \r
  27 *DP matching\r
  28 \r
  29  DP matching method\r
  30 \r
  31 *Edit distance\r
  32 \r
  33  Edit distance.\r
  34 \r
  35 *Cosine similarity\r
  36 \r
  37  Using this comparison method, birthmarks must have name and its\r
  38 frequency.  Therefore, elements of <f(p)> be a set of <(\{name_1,\r
  39 freq_1\}, \{name_2, freq_2\}, ..., \{name_n, freq_n\})>.\r
  40 \r
  41  Next, if <f(p)> have name <FOO> and <f(q)> do not have <FOO>, we add\r
  42 element <\{FOO, 0\}> to f(q).  Both birthmarks makes to appearing all\r
  43 names.\r
  44 \r
  45  Then, the similarity of <f(p)> and <f(q)>is denoted by\r
  46 \r
  47  <norm1 = sqrt(freq^p_1 * freq^p_1 + freq^p_2 * freq^p_2 + ... + freq^p_n * freq^p_n)>\r
  48 \r
  49  <norm2 = sqrt(freq^q_1 * freq^q_1 + freq^q_2 * freq^q_2 + ... + freq^q_n * freq^q_n)>\r
  50 \r
  51  <product = freq^p_1 * freq^q_1 + freq^p_2 * freq^q_2 + ... + freq^p_n * freq^q_n>\r
  52 \r
  53  <similarity = product / (norm1 * norm2)>