LCOV - code coverage report
Current view: top level - api - editdistance.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core 7028d852e609 Lines: 78 79 98.7 %
Date: 2019-02-17 14:59:59 Functions: 11 11 100.0 %
Branches: 59 70 84.3 %

           Branch data     Line data    Source code
       1                 :            : /** @file editdistance.cc
       2                 :            :  * @brief Edit distance calculation algorithm.
       3                 :            :  *
       4                 :            :  *  Based on that described in:
       5                 :            :  *
       6                 :            :  *  "An extension of Ukkonen's enhanced dynamic programming ASM algorithm"
       7                 :            :  *  by Hal Berghel, University of Arkansas
       8                 :            :  *  and David Roach, Acxiom Corporation
       9                 :            :  *
      10                 :            :  *  http://berghel.net/publications/asm/asm.php
      11                 :            :  */
      12                 :            : /* Copyright (C) 2003 Richard Boulton
      13                 :            :  * Copyright (C) 2007,2008,2009,2017 Olly Betts
      14                 :            :  *
      15                 :            :  * This program is free software; you can redistribute it and/or modify
      16                 :            :  * it under the terms of the GNU General Public License as published by
      17                 :            :  * the Free Software Foundation; either version 2 of the License, or
      18                 :            :  * (at your option) any later version.
      19                 :            :  *
      20                 :            :  * This program is distributed in the hope that it will be useful,
      21                 :            :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      22                 :            :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      23                 :            :  * GNU General Public License for more details.
      24                 :            :  *
      25                 :            :  * You should have received a copy of the GNU General Public License
      26                 :            :  * along with this program; if not, write to the Free Software
      27                 :            :  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
      28                 :            :  */
      29                 :            : 
      30                 :            : #include <config.h>
      31                 :            : 
      32                 :            : #include "editdistance.h"
      33                 :            : 
      34                 :            : #include "omassert.h"
      35                 :            : 
      36                 :            : #include <algorithm>
      37                 :            : #include <cstdlib>
      38                 :            : #include <cstring>
      39                 :            : 
      40                 :            : using namespace std;
      41                 :            : 
      42                 :            : template<class CHR>
      43                 :            : struct edist_seq {
      44                 :        312 :     edist_seq(const CHR * ptr_, int len_) : ptr(ptr_), len(len_) { }
      45                 :            :     const CHR * ptr;
      46                 :            :     int len;
      47                 :            : };
      48                 :            : 
      49                 :            : template<class CHR>
      50                 :            : class edist_state {
      51                 :            :     /// Don't allow assignment.
      52                 :            :     void operator=(const edist_state &);
      53                 :            : 
      54                 :            :     /// Don't allow copying.
      55                 :            :     edist_state(const edist_state &);
      56                 :            : 
      57                 :            :     edist_seq<CHR> seq1;
      58                 :            :     edist_seq<CHR> seq2;
      59                 :            : 
      60                 :            :     /* Array of f(k,p) values, where f(k,p) = the largest index i such that
      61                 :            :      * d(i,j) = p and d(i,j) is on diagonal k.
      62                 :            :      * ie: f(k,p) = largest i s.t. d(i,k+i) = p
      63                 :            :      * Where: d(i,j) = edit distance between substrings of length i and j.
      64                 :            :      */
      65                 :            :     int * fkp;
      66                 :            :     int fkp_cols;
      67                 :            : 
      68                 :            :     /* Maximum possible edit distance (this is referred to as ZERO_K in
      69                 :            :      * the algorithm description by Berghel and Roach). */
      70                 :            :     int maxdist;
      71                 :            : 
      72                 :      10557 :     int calc_index(int k, int p) const {
      73                 :      10557 :         return (k + maxdist) * fkp_cols + p + 1;
      74                 :            :     }
      75                 :            : 
      76                 :            :   public:
      77                 :            : 
      78                 :            :     edist_state(const CHR * ptr1, int len1, const CHR * ptr2, int len2);
      79                 :            : 
      80                 :            :     ~edist_state();
      81                 :            : 
      82                 :       1467 :     int get_f_kp(int k, int p) const {
      83                 :       1467 :         return fkp[calc_index(k, p)];
      84                 :            :     }
      85                 :            : 
      86                 :       9090 :     void set_f_kp(int k, int p, int val) {
      87                 :       9090 :         fkp[calc_index(k, p)] = val;
      88                 :       9090 :     }
      89                 :            : 
      90                 :        408 :     bool is_transposed(int pos1, int pos2) const {
      91 [ +  + ][ +  + ]:        408 :         if (pos1 <= 0 || pos2 <= 0 || pos1 >= seq1.len || pos2 >= seq2.len) return false;
         [ +  + ][ -  + ]
      92                 :        230 :         return (seq1.ptr[pos1 - 1] == seq2.ptr[pos2] &&
      93 [ +  + ][ +  + ]:        115 :                 seq1.ptr[pos1] == seq2.ptr[pos2 - 1]);
      94                 :            :     }
      95                 :            : 
      96                 :            :     void edist_calc_f_kp(int k, int p);
      97                 :            : };
      98                 :            : 
      99                 :            : template<class CHR>
     100                 :        408 : void edist_state<CHR>::edist_calc_f_kp(int k, int p)
     101                 :            : {
     102                 :        408 :     int maxlen = get_f_kp(k, p - 1) + 1; /* dist if do substitute */
     103                 :        408 :     int maxlen2 = get_f_kp(k - 1, p - 1); /* dist if do insert */
     104                 :        408 :     int maxlen3 = get_f_kp(k + 1, p - 1) + 1; /* dist if delete */
     105                 :            : 
     106         [ +  + ]:        408 :     if (is_transposed(maxlen, maxlen + k)) {
     107                 :            :         // Transposition.
     108                 :         33 :         ++maxlen;
     109                 :            :     }
     110                 :            : 
     111         [ +  + ]:        408 :     if (maxlen >= maxlen2) {
     112         [ +  + ]:        303 :         if (maxlen >= maxlen3) {
     113                 :            :             // Transposition or Substitution.
     114                 :            :         } else {
     115                 :            :             // Deletion.
     116                 :        303 :             maxlen = maxlen3;
     117                 :            :         }
     118                 :            :     } else {
     119         [ +  - ]:        105 :         if (maxlen2 >= maxlen3) {
     120                 :            :             // Insertion.
     121                 :        105 :             maxlen = maxlen2;
     122                 :            :         } else {
     123                 :            :             // Deletion.
     124                 :          0 :             maxlen = maxlen3;
     125                 :            :         }
     126                 :            :     }
     127                 :            : 
     128                 :            :     /* Check for exact matches, and increase the length until we don't have
     129                 :            :      * one. */
     130 [ +  + ][ +  - ]:       1076 :     while (maxlen < seq1.len &&
                 [ +  + ]
     131                 :            :            maxlen + k < seq2.len &&
     132                 :       1732 :            seq1.ptr[maxlen] == seq2.ptr[maxlen + k]) {
     133                 :        668 :         ++maxlen;
     134                 :            :     }
     135                 :        408 :     set_f_kp(k, p, maxlen);
     136                 :        408 : }
     137                 :            : 
     138                 :            : #define INF 1000000
     139                 :            : template<class CHR>
     140                 :        156 : edist_state<CHR>::edist_state(const CHR * ptr1, int len1,
     141                 :            :                               const CHR * ptr2, int len2)
     142                 :        156 :     : seq1(ptr1, len1), seq2(ptr2, len2), maxdist(len2)
     143                 :            : {
     144                 :            :     Assert(len2 >= len1);
     145                 :            :     /* Each row represents a value of k, from -maxdist to maxdist. */
     146                 :        156 :     int fkp_rows = maxdist * 2 + 1;
     147                 :            :     /* Each column represents a value of p, from -1 to maxdist. */
     148                 :        156 :     fkp_cols = maxdist + 2;
     149                 :            :     /* fkp is stored as a rectangular array, row by row. */
     150         [ +  - ]:        156 :     fkp = new int[fkp_rows * fkp_cols];
     151                 :            : 
     152         [ +  + ]:       2126 :     for (int k = -maxdist; k <= maxdist; ++k) {
     153         [ +  + ]:      18427 :         for (int p = -1; p <= maxdist; ++p) {
     154         [ +  + ]:      16457 :             if (p == abs(k) - 1) {
     155         [ +  + ]:       1970 :                 if (k < 0) {
     156                 :        907 :                     set_f_kp(k, p, abs(k) - 1);
     157                 :            :                 } else {
     158                 :       1970 :                     set_f_kp(k, p, -1);
     159                 :            :                 }
     160         [ +  + ]:      14487 :             } else if (p < abs(k)) {
     161                 :       6712 :                 set_f_kp(k, p, -INF);
     162                 :            :             }
     163                 :            :         }
     164                 :            :     }
     165                 :        156 : }
     166                 :            : 
     167                 :            : template<class CHR>
     168                 :        156 : edist_state<CHR>::~edist_state() {
     169         [ +  - ]:        156 :     delete [] fkp;
     170                 :        156 : }
     171                 :            : 
     172                 :            : template<class CHR>
     173                 :            : static int
     174                 :        156 : seqcmp_editdist(const CHR * ptr1, int len1, const CHR * ptr2, int len2,
     175                 :            :                 int max_distance)
     176                 :            : {
     177                 :        156 :     int lendiff = len2 - len1;
     178                 :            :     /* Make sure second sequence is longer (or same length). */
     179         [ +  + ]:        156 :     if (lendiff < 0) {
     180                 :         47 :         lendiff = -lendiff;
     181                 :         47 :         swap(ptr1, ptr2);
     182                 :         47 :         swap(len1, len2);
     183                 :            :     }
     184                 :            : 
     185                 :            :     /* Special case for if one or both sequences are empty. */
     186         [ -  + ]:        156 :     if (len1 == 0) return len2;
     187                 :            : 
     188         [ +  - ]:        156 :     edist_state<CHR> state(ptr1, len1, ptr2, len2);
     189                 :            : 
     190                 :        156 :     int p = lendiff; /* This is the minimum possible edit distance. */
     191         [ +  + ]:        248 :     while (p <= max_distance) {
     192         [ +  + ]:        488 :         for (int temp_p = 0; temp_p != p; ++temp_p) {
     193                 :        245 :             int inc = p - temp_p;
     194         [ +  + ]:        245 :             if (abs(lendiff - inc) <= temp_p) {
     195         [ +  - ]:        158 :                 state.edist_calc_f_kp(lendiff - inc, temp_p);
     196                 :            :             }
     197         [ +  + ]:        245 :             if (abs(lendiff + inc) <= temp_p) {
     198         [ +  - ]:          7 :                 state.edist_calc_f_kp(lendiff + inc, temp_p);
     199                 :            :             }
     200                 :            :         }
     201         [ +  - ]:        243 :         state.edist_calc_f_kp(lendiff, p);
     202                 :            : 
     203 [ +  - ][ +  + ]:        243 :         if (state.get_f_kp(lendiff, p) == len1) break;
     204                 :         92 :         ++p;
     205                 :            :     }
     206                 :            : 
     207                 :        156 :     return p;
     208                 :            : }
     209                 :            : 
     210                 :            : int
     211                 :        156 : edit_distance_unsigned(const unsigned * ptr1, int len1,
     212                 :            :                        const unsigned * ptr2, int len2,
     213                 :            :                        int max_distance)
     214                 :            : {
     215                 :        156 :     return seqcmp_editdist<unsigned>(ptr1, len1, ptr2, len2, max_distance);
     216                 :            : }
     217                 :            : 
     218                 :            : // We sum the character frequency histogram absolute differences to compute a
     219                 :            : // lower bound on the edit distance.  Rather than counting each Unicode code
     220                 :            : // point uniquely, we use an array with VEC_SIZE elements and tally code points
     221                 :            : // modulo VEC_SIZE which can only reduce the bound we calculate.
     222                 :            : //
     223                 :            : // There will be a trade-off between how good the bound is and how large and
     224                 :            : // array is used (a larger array takes more time to clear and sum over).  The
     225                 :            : // value 64 is somewhat arbitrary - it works as well as 128 for the testsuite
     226                 :            : // but that may not reflect real world performance.  FIXME: profile and tune.
     227                 :            : 
     228                 :            : #define VEC_SIZE 64
     229                 :            : 
     230                 :            : int
     231                 :        161 : freq_edit_lower_bound(const vector<unsigned> & a, const vector<unsigned> & b)
     232                 :            : {
     233                 :            :     int vec[VEC_SIZE];
     234                 :        161 :     memset(vec, 0, sizeof(vec));
     235                 :        161 :     vector<unsigned>::const_iterator i;
     236         [ +  + ]:       1030 :     for (i = a.begin(); i != a.end(); ++i) {
     237                 :        869 :         ++vec[(*i) % VEC_SIZE];
     238                 :            :     }
     239         [ +  + ]:       1050 :     for (i = b.begin(); i != b.end(); ++i) {
     240                 :        889 :         --vec[(*i) % VEC_SIZE];
     241                 :            :     }
     242                 :        161 :     unsigned int total = 0;
     243         [ +  + ]:      10465 :     for (size_t j = 0; j < VEC_SIZE; ++j) {
     244                 :      10304 :         total += abs(vec[j]);
     245                 :            :     }
     246                 :            :     // Each insertion or deletion adds at most 1 to total.  Each transposition
     247                 :            :     // doesn't change it at all.  But each substitution can change it by 2 so
     248                 :            :     // we need to divide it by 2.  Rounding up is OK, since the odd change must
     249                 :            :     // be due to an actual edit.
     250                 :        161 :     return (total + 1) / 2;
     251                 :            : }

Generated by: LCOV version 1.11