LCOV - code coverage report
Current view: top level - api - editdistance.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core eba1a2e3082b Lines: 79 80 98.8 %
Date: 2019-06-13 13:35:36 Functions: 9 9 100.0 %
Branches: 61 72 84.7 %

           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,2019 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 <climits>
      38                 :            : #include <cstdlib>
      39                 :            : #include <cstring>
      40                 :            : 
      41                 :            : using namespace std;
      42                 :            : 
      43                 :            : template<class CHR>
      44                 :            : struct edist_seq {
      45                 :       1696 :     edist_seq(const CHR * ptr_, int len_) : ptr(ptr_), len(len_) { }
      46                 :            :     const CHR * ptr;
      47                 :            :     int len;
      48                 :            : };
      49                 :            : 
      50                 :            : template<class CHR>
      51                 :            : class edist_state {
      52                 :            :     /// Don't allow assignment.
      53                 :            :     edist_state& operator=(const edist_state&) = delete;
      54                 :            : 
      55                 :            :     /// Don't allow copying.
      56                 :            :     edist_state(const edist_state&) = delete;
      57                 :            : 
      58                 :            :     edist_seq<CHR> seq1;
      59                 :            :     edist_seq<CHR> seq2;
      60                 :            : 
      61                 :            :     /* Array of f(k,p) values, where f(k,p) = the largest index i such that
      62                 :            :      * d(i,j) = p and d(i,j) is on diagonal k.
      63                 :            :      * ie: f(k,p) = largest i s.t. d(i,k+i) = p
      64                 :            :      * Where: d(i,j) = edit distance between substrings of length i and j.
      65                 :            :      */
      66                 :            :     int * fkp;
      67                 :            :     int fkp_cols;
      68                 :            : 
      69                 :            :     /* Maximum possible edit distance (this is referred to as ZERO_K in
      70                 :            :      * the algorithm description by Berghel and Roach). */
      71                 :            :     int maxdist;
      72                 :            : 
      73                 :      61880 :     int calc_index(int k, int p) const {
      74                 :      61880 :         return (k + maxdist) * fkp_cols + p + 1;
      75                 :            :     }
      76                 :            : 
      77                 :            :   public:
      78                 :        848 :     edist_state(const CHR* ptr1, int len1, const CHR* ptr2, int len2,
      79                 :            :                 int* fkp_)
      80                 :        848 :         : seq1(ptr1, len1), seq2(ptr2, len2), fkp(fkp_), maxdist(len2) {
      81                 :            :         Assert(len2 >= len1);
      82                 :            :         // fkp is stored as a rectangular array, row by row.  Each entry
      83                 :            :         // represents a value of p, from -1 to maxdist or the special value
      84                 :            :         // INT_MIN.
      85                 :        848 :         fkp_cols = maxdist + 2;
      86                 :        848 :         set_f_kp(0, -1, -1);
      87         [ +  + ]:       5791 :         for (int k = 1; k <= maxdist; ++k) {
      88         [ +  + ]:      45112 :             for (int p = -1; p <= maxdist; ++p) {
      89         [ +  + ]:      40169 :                 if (p == k - 1) {
      90                 :       4943 :                     set_f_kp(k, p, -1);
      91                 :       4943 :                     set_f_kp(-k, p, k - 1);
      92         [ +  + ]:      35226 :                 } else if (p < k) {
      93                 :      17613 :                     set_f_kp(k, p, INT_MIN);
      94                 :      17613 :                     set_f_kp(-k, p, INT_MIN);
      95                 :            :                 }
      96                 :            :             }
      97                 :            :         }
      98                 :        848 :     }
      99                 :            : 
     100                 :      12377 :     int get_f_kp(int k, int p) const {
     101                 :      12377 :         return fkp[calc_index(k, p)];
     102                 :            :     }
     103                 :            : 
     104                 :      49503 :     void set_f_kp(int k, int p, int val) {
     105                 :      49503 :         fkp[calc_index(k, p)] = val;
     106                 :      49503 :     }
     107                 :            : 
     108                 :       3543 :     bool is_transposed(int pos1, int pos2) const {
     109 [ +  + ][ +  + ]:       3543 :         if (pos1 <= 0 || pos2 <= 0 || pos1 >= seq1.len || pos2 >= seq2.len) return false;
         [ +  + ][ -  + ]
     110                 :       2110 :         return (seq1.ptr[pos1 - 1] == seq2.ptr[pos2] &&
     111 [ +  + ][ +  + ]:       1055 :                 seq1.ptr[pos1] == seq2.ptr[pos2 - 1]);
     112                 :            :     }
     113                 :            : 
     114                 :            :     void edist_calc_f_kp(int k, int p);
     115                 :            : };
     116                 :            : 
     117                 :            : template<class CHR>
     118                 :       3543 : void edist_state<CHR>::edist_calc_f_kp(int k, int p)
     119                 :            : {
     120                 :       3543 :     int maxlen = get_f_kp(k, p - 1) + 1; /* dist if do substitute */
     121                 :       3543 :     int maxlen2 = get_f_kp(k - 1, p - 1); /* dist if do insert */
     122                 :       3543 :     int maxlen3 = get_f_kp(k + 1, p - 1) + 1; /* dist if delete */
     123                 :            : 
     124         [ +  + ]:       3543 :     if (is_transposed(maxlen, maxlen + k)) {
     125                 :            :         // Transposition.
     126                 :         70 :         ++maxlen;
     127                 :            :     }
     128                 :            : 
     129         [ +  + ]:       3543 :     if (maxlen >= maxlen2) {
     130         [ +  + ]:       2799 :         if (maxlen >= maxlen3) {
     131                 :            :             // Transposition or Substitution.
     132                 :            :         } else {
     133                 :            :             // Deletion.
     134                 :       2799 :             maxlen = maxlen3;
     135                 :            :         }
     136                 :            :     } else {
     137         [ +  - ]:        744 :         if (maxlen2 >= maxlen3) {
     138                 :            :             // Insertion.
     139                 :        744 :             maxlen = maxlen2;
     140                 :            :         } else {
     141                 :            :             // Deletion.
     142                 :          0 :             maxlen = maxlen3;
     143                 :            :         }
     144                 :            :     }
     145                 :            : 
     146                 :            :     /* Check for exact matches, and increase the length until we don't have
     147                 :            :      * one. */
     148 [ +  + ][ +  + ]:       6352 :     while (maxlen < seq1.len &&
                 [ +  + ]
     149                 :            :            maxlen + k < seq2.len &&
     150                 :      11092 :            seq1.ptr[maxlen] == seq2.ptr[maxlen + k]) {
     151                 :       2809 :         ++maxlen;
     152                 :            :     }
     153                 :       3543 :     set_f_kp(k, p, maxlen);
     154                 :       3543 : }
     155                 :            : 
     156                 :            : template<class CHR>
     157                 :            : static int
     158                 :        848 : seqcmp_editdist(const CHR* ptr1, int len1, const CHR* ptr2, int len2,
     159                 :            :                 int* fkp_, int max_distance)
     160                 :            : {
     161                 :        848 :     int lendiff = len2 - len1;
     162                 :            :     /* Make sure second sequence is longer (or same length). */
     163         [ +  + ]:        848 :     if (lendiff < 0) {
     164                 :        144 :         lendiff = -lendiff;
     165                 :        144 :         swap(ptr1, ptr2);
     166                 :        144 :         swap(len1, len2);
     167                 :            :     }
     168                 :            : 
     169                 :            :     /* Special case for if one or both sequences are empty. */
     170         [ -  + ]:        848 :     if (len1 == 0) return len2;
     171                 :            : 
     172         [ +  - ]:        848 :     edist_state<CHR> state(ptr1, len1, ptr2, len2, fkp_);
     173                 :            : 
     174                 :        848 :     int p = lendiff; /* This is the minimum possible edit distance. */
     175         [ +  + ]:       2019 :     while (p <= max_distance) {
     176         [ +  + ]:       4168 :         for (int temp_p = 0; temp_p != p; ++temp_p) {
     177                 :       2420 :             int inc = p - temp_p;
     178         [ +  + ]:       2420 :             if (abs(lendiff - inc) <= temp_p) {
     179         [ +  - ]:       1490 :                 state.edist_calc_f_kp(lendiff - inc, temp_p);
     180                 :            :             }
     181         [ +  + ]:       2420 :             if (abs(lendiff + inc) <= temp_p) {
     182         [ +  - ]:        305 :                 state.edist_calc_f_kp(lendiff + inc, temp_p);
     183                 :            :             }
     184                 :            :         }
     185         [ +  - ]:       1748 :         state.edist_calc_f_kp(lendiff, p);
     186                 :            : 
     187 [ +  - ][ +  + ]:       1748 :         if (state.get_f_kp(lendiff, p) == len1) break;
     188                 :       1171 :         ++p;
     189                 :            :     }
     190                 :            : 
     191                 :        848 :     return p;
     192                 :            : }
     193                 :            : 
     194                 :            : int
     195                 :       2752 : EditDistanceCalculator::calc(const unsigned* ptr, int len,
     196                 :            :                              int max_distance) const
     197                 :            : {
     198                 :            :     // Calculate a cheap lower bound on the edit distance by considering
     199                 :            :     // frequency histograms.
     200                 :            :     int freqs[VEC_SIZE];
     201                 :       2752 :     memcpy(freqs, target_freqs, sizeof(freqs));
     202         [ +  + ]:      15883 :     for (int i = 0; i != len; ++i) {
     203                 :      13131 :         unsigned ch = ptr[i];
     204                 :      13131 :         --freqs[ch % VEC_SIZE];
     205                 :            :     }
     206                 :       2752 :     unsigned int total = 0;
     207         [ +  + ]:     178880 :     for (int count : freqs) {
     208                 :     176128 :         total += abs(count);
     209                 :            :     }
     210                 :            :     // Each insertion or deletion adds at most 1 to total.  Each transposition
     211                 :            :     // doesn't change it at all.  But each substitution can change it by 2 so
     212                 :            :     // we need to divide it by 2.  Rounding up is OK, since the odd change must
     213                 :            :     // be due to an actual edit.
     214                 :       2752 :     int ed_lower_bound = (total + 1) / 2;
     215         [ +  + ]:       2752 :     if (ed_lower_bound > max_distance) {
     216                 :            :         // It's OK to return any distance > max_distance if the true answer is
     217                 :            :         // > max_distance.
     218                 :       1904 :         return ed_lower_bound;
     219                 :            :     }
     220                 :            : 
     221         [ +  + ]:        848 :     if (!array) {
     222                 :            :         // Allocate space for the largest case we need to consider, which is
     223                 :            :         // when the second sequence is len + max_distance long.  Any second
     224                 :            :         // sequence which is longer must be more than max_distance edits
     225                 :            :         // away.
     226                 :        222 :         int maxdist = target.size() + max_distance;
     227                 :        222 :         int max_cols = maxdist * 2;
     228                 :        222 :         int max_rows = maxdist * 2 + 1;
     229 [ +  - ][ +  - ]:        222 :         array = new int[max_rows * max_cols];
     230                 :            :     }
     231                 :            : 
     232                 :        848 :     return seqcmp_editdist<unsigned>(ptr, len, &target[0], target.size(),
     233         [ +  - ]:       2752 :                                      array, max_distance);
     234                 :            : }

Generated by: LCOV version 1.11