i18npool/source/search/levdis.cxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  *
   9  * This file incorporates work covered by the following license notice:
  10  *
  11  *   Licensed to the Apache Software Foundation (ASF) under one or more
  12  *   contributor license agreements. See the NOTICE file distributed
  13  *   with this work for additional information regarding copyright
  14  *   ownership. The ASF licenses this file to you under the Apache
  15  *   License, Version 2.0 (the "License"); you may not use this file
  16  *   except in compliance with the License. You may obtain a copy of
  17  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
  18  */
  19
  20 /*************************************************************************
  21
  22     Weighted Levenshtein Distance
  23     including wildcards
  24     '*' for any number (0 or more) of arbitrary characters
  25     '?' for exactly one arbitrary character
  26     escapeable with  backslash, "\*" or "\?"
  27
  28     Return:
  29         WLD if WLD <= nLimit, else nLimit+1
  30
  31     or, if bSplitCount:
  32         WLD if WLD <= nLimit
  33         -WLD if Replace and Insert and Delete <= nLimit
  34         else nLimit+1
  35
  36     Recursive definition of WLD:
  37
  38     WLD( X(i), Y(j) ) = min( WLD( X(i-1), Y(j-1) ) + p(i,j) ,
  39                              WLD( X(i)  , Y(j-1) ) + q      ,
  40                              WLD( X(i-1), Y(j)   ) + r      )
  41
  42     X(i)   := the first i characters of the word X
  43     Y(j)   := the first j characters of the word Y
  44     p(i,j) := 0 if i-th character of X == j-th character of Y,
  45               p else
  46
  47     Boundary conditions:
  48     WLD( X(0), Y(j) ) := j*q  (Y created by j inserts)
  49     WLD( X(i), Y(0) ) := i*r  (Y created by i deletes)
  50     WLD( X(0), Y(0) ) := 0
  51
  52     Instead of recursions a dynamic algorithm is used.
  53
  54     See also: German computer magazine
  55     c't 07/89 pages 192-208 and c't 03/94 pages 230-239
  56
  57 *************************************************************************/
  58
  59
  60 #include <string.h>     // strlen()
  61
  62 #if defined( _MSC_VER )
  63 #pragma warning(once: 4068)
  64 #endif
  65
  66 #include "levdis.hxx"
  67
  68 #ifdef SOLARIS
  69 #undef min
  70 #endif
  71
  72 #define LEVDISBIG   (nLimit + 1)    // Returnwert wenn Distanz > nLimit
  73 #define LEVDISDOUBLEBUF 2048        // dadrueber wird nicht mehr gedoppelt
  74
  75 // Balance, aus Geschwindigkeitsgruenden ist dieses keine Funktion
  76 // c == cpPattern[jj] == cString[ii]
  77 // erst wird bis Fundstelle gesucht, wenn dort die Balance gleich ist, wird
  78 // auch nach der Fundstelle verglichen
  79 #define LEVDISBALANCE(jj,ii)                        \
  80 {                                                   \
  81     if ( jj != ii )                                 \
  82     {                                               \
  83         register sal_Int32 k;                       \
  84         if ( jj > 0 )                               \
  85             for ( k=0; k < jj; k++ )                \
  86                 if ( cpPattern[k] == c )            \
  87                     nBalance++;                     \
  88         if ( ii > 0 )                               \
  89             for ( k=0; k < ii; k++ )                \
  90                 if ( cString[k] == c )              \
  91                     nBalance--;                     \
  92         if ( !nBalance )                            \
  93         {                                           \
  94             for ( k=jj+1; k < nPatternLen; k++ )    \
  95                 if ( cpPattern[k] == c )            \
  96                     nBalance++;                     \
  97             for ( k=ii+1; k < nStringLen; k++ )     \
  98                 if ( cString[k] == c )              \
  99                     nBalance--;                     \
 100         }                                           \
 101     }                                               \
 102 }
 103
 104 static sal_Int32 Impl_WLD_StringLen( const sal_Unicode* pStr )
 105 {
 106     const sal_Unicode* pTempStr = pStr;
 107     while( *pTempStr )
 108         pTempStr++;
 109     return (sal_Int32)(pTempStr-pStr);
 110 }
 111
 112 // Distanz von String zu Pattern
 113 int WLevDistance::WLD( const sal_Unicode* cString, sal_Int32 nStringLen )
 114 {
 115     int nSPMin = 0;     // StrafPunkteMinimum
 116     int nRepS = 0;      // fuer SplitCount
 117
 118     // Laengendifferenz von Pattern und String
 119     int nLenDiff = nPatternLen - nStars - nStringLen;
 120     // mehr Einfuegungen oder Loeschungen noetig als Limit? => raus hier
 121     if ( (nLenDiff * nInsQ0 > nLimit)
 122             || ((nStars == 0) && (nLenDiff * nDelR0 < -nLimit)) )
 123         return(LEVDISBIG);
 124
 125     // wenn der zu vergleichende String groesser ist als das bisherige Array
 126     // muss dieses angepasst werden
 127     if ( nStringLen >= nArrayLen )
 128     {
 129         // gib ihm moeglichst mehr, damit nicht gleich naechstesmal
 130         // wieder realloziert werden muss
 131         if ( nStringLen < LEVDISDOUBLEBUF )
 132             nArrayLen = 2 * nStringLen;
 133         else
 134             nArrayLen = nStringLen + 1;
 135         npDistance = aDisMem.NewMem( nArrayLen );
 136     }
 137
 138     // Anfangswerte der zweiten Spalte (erstes Pattern-Zeichen) berechnen
 139     // die erste Spalte (0-Len Pattern) ist immer 0 .. nStringLen * nInsQ0,
 140     // deren Minimum also 0
 141     if ( nPatternLen == 0 )
 142     {
 143         // Anzahl der Loeschungen, um auf Pattern zu kommen
 144         for ( sal_Int32 i=0; i <= nStringLen; i++ )
 145             npDistance[i] = i * nDelR0;
 146     }
 147     else if ( cpPattern[0] == '*' && bpPatIsWild[0] )
 148     {
 149         // statt einem '*' ist alles einsetzbar
 150         for ( sal_Int32 i=0; i <= nStringLen; i++ )
 151             npDistance[i] = 0;
 152     }
 153     else
 154     {
 155         sal_Unicode c;
 156         int nP;
 157         c = cpPattern[0];
 158         if ( c == '?' && bpPatIsWild[0] )
 159             nP = 0;     // ein '?' kann jedes Zeichen sein
 160         else
 161             // Minimum von Ersetzen und Loeschen+Einfuegen Gewichtung
 162             nP = Min3( nRepP0, nRepP0, nDelR0 + nInsQ0 );
 163         npDistance[0] = nInsQ0;     // mit einfachem Einfuegen geht's los
 164         npDistance[1] = nInsQ0;
 165         npDistance[2] = nInsQ0;
 166         int nReplacePos = -1;       // tristate Flag
 167         int nDelCnt = 0;
 168         for ( sal_Int32 i=1; i <= nStringLen; i++, nDelCnt += nDelR0 )
 169         {
 170             if ( cString[i-1] == c )
 171                 nP = 0;     // Replace ab dieser Stelle ist 0
 172             // Loeschungen um auf Pattern zu kommen + Replace
 173             npDistance[i] = nDelCnt + nP;
 174             if ( bSplitCount )
 175             {
 176                 if ( nReplacePos < 0 && nP )
 177                 {   // diese Stelle wird ersetzt
 178                     nRepS++;
 179                     nReplacePos = i;
 180                 }
 181                 else if ( nReplacePos > 0 && !nP )
 182                 {
 183                     int nBalance = 0;   // gleiche Anzahl c
 184                     LEVDISBALANCE( 0, i-1 );
 185                     if ( !nBalance )
 186                     {   // einer wurde ersetzt, der ein Insert war
 187                         nRepS--;
 188                         nReplacePos = 0;
 189                     }
 190                 }
 191             }
 192         }
 193         nSPMin = Min3( npDistance[0], npDistance[1], npDistance[2] );
 194     }
 195
 196     // Distanzmatrix berechnen
 197     sal_Int32 j = 0;        // fuer alle Spalten des Pattern, solange nicht Limit
 198     while ( (j < nPatternLen-1)
 199             && nSPMin <= (bSplitCount ? 2 * nLimit : nLimit) )
 200     {
 201         sal_Unicode c;
 202         int nP, nQ, nR, nPij, d1, d2;
 203
 204         j++;
 205         c = cpPattern[j];
 206         if ( bpPatIsWild[j] )   // '*' oder '?' nicht escaped
 207             nP = 0;     // kann ohne Strafpunkte ersetzt werden
 208         else
 209             nP = nRepP0;
 210         if ( c == '*' && bpPatIsWild[j] )
 211         {
 212             nQ = 0;     // Einfuegen und Loeschen ohne Strafpunkte
 213             nR = 0;
 214         }
 215         else
 216         {
 217             nQ = nInsQ0;    // normale Gewichtung
 218             nR = nDelR0;
 219         }
 220         d2 = npDistance[0];
 221         // Anzahl Einfuegungen um von Null-String auf Pattern zu kommen erhoehen
 222         npDistance[0] = npDistance[0] + nQ;
 223         nSPMin = npDistance[0];
 224         int nReplacePos = -1;       // tristate Flag
 225         // fuer jede Patternspalte den String durchgehen
 226         for ( register sal_Int32 i=1; i <= nStringLen; i++ )
 227         {
 228             d1 = d2;                // WLD( X(i-1), Y(j-1) )
 229             d2 = npDistance[i];     // WLD( X(i)  , Y(j-1) )
 230             if ( cString[i-1] == c )
 231             {
 232                 nPij = 0;           // p(i,j)
 233                 if ( nReplacePos < 0 )
 234                 {
 235                     int nBalance = 0;   // gleiche Anzahl c
 236                     LEVDISBALANCE( j, i-1 );
 237                     if ( !nBalance )
 238                         nReplacePos = 0;    // keine Ersetzung mehr
 239                 }
 240             }
 241             else
 242                 nPij = nP;
 243             // WLD( X(i), Y(j) ) = min( WLD( X(i-1), Y(j-1) ) + p(i,j) ,
 244             //                          WLD( X(i)  , Y(j-1) ) + q      ,
 245             //                          WLD( X(i-1), Y(j)   ) + r      )
 246             npDistance[i] = Min3( d1 + nPij, d2 + nQ, npDistance[i-1] + nR );
 247             if ( npDistance[i] < nSPMin )
 248                 nSPMin = npDistance[i];
 249             if ( bSplitCount )
 250             {
 251                 if ( nReplacePos < 0 && nPij && npDistance[i] == d1 + nPij )
 252                 {   // diese Stelle wird ersetzt
 253                     nRepS++;
 254                     nReplacePos = i;
 255                 }
 256                 else if ( nReplacePos > 0 && !nPij )
 257                 {   // Zeichen in String und Pattern gleich.
 258                     // wenn ab hier die gleiche Anzahl dieses Zeichens
 259                     // sowohl in Pattern als auch in String ist, und vor
 260                     // dieser Stelle das Zeichen gleich oft vorkommt, war das
 261                     // Replace keins. Buchstabendreher werden hier erfasst
 262                     // und der ReplaceS zurueckgenommen, wodurch das doppelte
 263                     // Limit zum Tragen kommt.
 264                     int nBalance = 0;   // gleiche Anzahl c
 265                     LEVDISBALANCE( j, i-1 );
 266                     if ( !nBalance )
 267                     {   // einer wurde ersetzt, der ein Insert war
 268                         nRepS--;
 269                         nReplacePos = 0;
 270                     }
 271                 }
 272             }
 273         }
 274     }
 275     if ( (nSPMin <= nLimit) && (npDistance[nStringLen] <= nLimit) )
 276         return(npDistance[nStringLen]);
 277     else
 278     {
 279         if ( bSplitCount )
 280         {
 281             if ( nRepS && nLenDiff > 0 )
 282                 nRepS -= nLenDiff;      // Inserts wurden mitgezaehlt
 283             if ( (nSPMin <= 2 * nLimit)
 284                     && (npDistance[nStringLen] <= 2 * nLimit)
 285                     && (nRepS * nRepP0 <= nLimit) )
 286                 return( -npDistance[nStringLen] );
 287             return(LEVDISBIG);
 288         }
 289         return(LEVDISBIG);
 290     }
 291 }
 292
 293
 294
 295 // Berechnung von nLimit,   nReplP0,    nInsQ0,     nDelR0,     bSplitCount
 296 // aus Userwerten           nOtherX,    nShorterY,  nLongerZ,   bRelaxed
 297 int WLevDistance::CalcLPQR( int nX, int nY, int nZ, bool bRelaxed )
 298 {
 299     if ( nX < 0 ) nX = 0;       // nur positive Werte
 300     if ( nY < 0 ) nY = 0;
 301     if ( nZ < 0 ) nZ = 0;
 302     if (0 == Min3( nX, nY, nZ ))     // mindestens einer 0
 303     {
 304         int nMid, nMax;
 305         nMax = Max3( nX, nY, nZ );      // entweder 0 bei drei 0 oder Max
 306         if ( 0 == (nMid = Mid3( nX, nY, nZ )) )     // sogar zwei 0
 307             nLimit = nMax;  // entweder 0 oder einziger >0
 308         else        // einer 0
 309             nLimit = KGV( nMid, nMax );
 310     }
 311     else        // alle drei nicht 0
 312         nLimit = KGV( KGV( nX, nY ), nZ );
 313     nRepP0 = ( nX ? nLimit / nX : nLimit + 1 );
 314     nInsQ0 = ( nY ? nLimit / nY : nLimit + 1 );
 315     nDelR0 = ( nZ ? nLimit / nZ : nLimit + 1 );
 316     bSplitCount = bRelaxed;
 317     return( nLimit );
 318 }
 319
 320
 321
 322 // Groesster Gemeinsamer Teiler nach Euklid (Kettendivision)
 323 // Sonderfall: 0 und irgendwas geben 1
 324 int WLevDistance::GGT( int a, int b )
 325 {
 326     if ( !a || !b )
 327         return 1;
 328     if ( a < 0 ) a = -a;
 329     if ( b < 0 ) b = -b;
 330     do
 331     {
 332         if ( a > b )
 333             a -= int(a / b) * b;
 334         else
 335             b -= int(b / a) * a;
 336     } while ( a && b );
 337     return( a ? a : b);
 338 }
 339
 340
 341
 342 // Kleinstes Gemeinsames Vielfaches: a * b / GGT(a,b)
 343 int WLevDistance::KGV( int a, int b )
 344 {
 345     if ( a > b )    // Ueberlauf unwahrscheinlicher machen
 346         return( (a / GGT(a,b)) * b );
 347     else
 348         return( (b / GGT(a,b)) * a );
 349 }
 350
 351
 352 // Minimum von drei Werten
 353 inline int WLevDistance::Min3( int x, int y, int z )
 354 {
 355     if ( x < y )
 356         return( x < z ? x : z );
 357     else
 358         return( y < z ? y : z );
 359 }
 360
 361
 362
 363 // mittlerer von drei Werten
 364 int WLevDistance::Mid3( int x, int y, int z )
 365 {
 366     int min = Min3(x,y,z);
 367     if ( x == min )
 368         return( y < z ? y : z);
 369     else if ( y == min )
 370         return( x < z ? x : z);
 371     else        // z == min
 372         return( x < y ? x : y);
 373 }
 374
 375
 376
 377 // Maximum von drei Werten
 378 int WLevDistance::Max3( int x, int y, int z )
 379 {
 380     if ( x > y )
 381         return( x > z ? x : z );
 382     else
 383         return( y > z ? y : z );
 384 }
 385
 386
 387
 388 // Daten aus CTor initialisieren
 389 void WLevDistance::InitData( const sal_Unicode* cPattern )
 390 {
 391     cpPattern = aPatMem.GetcPtr();
 392     bpPatIsWild = aPatMem.GetbPtr();
 393     npDistance = aDisMem.GetPtr();
 394     nStars = 0;
 395     const sal_Unicode* cp1 = cPattern;
 396     sal_Unicode* cp2 = cpPattern;
 397     bool* bp = bpPatIsWild;
 398     // Pattern kopieren, Sternchen zaehlen, escaped Jokers
 399     while ( *cp1 )
 400     {
 401         if ( *cp1 == '\\' )     // maybe escaped
 402         {
 403             if ( *(cp1+1) == '*' || *(cp1+1) == '?' )   // naechstes Joker?
 404             {
 405                 cp1++;          // skip '\\'
 406                 nPatternLen--;
 407             }
 408             *bp++ = false;
 409         }
 410         else if ( *cp1 == '*' || *cp1 == '?' )      // Joker
 411         {
 412             if ( *cp1 == '*' )
 413                 nStars++;       // Sternchenzaehler erhoehen
 414             *bp++ = true;
 415         }
 416         else
 417             *bp++ = false;
 418         *cp2++ = *cp1++;
 419     }
 420     *cp2 = '\0';
 421 }
 422
 423
 424 WLevDistance::WLevDistance( const sal_Unicode* cPattern,
 425                             int nOtherX, int nShorterY, int nLongerZ,
 426                             bool bRelaxed ) :
 427     nPatternLen( Impl_WLD_StringLen(cPattern) ),
 428     aPatMem( nPatternLen + 1 ),
 429     nArrayLen( nPatternLen + 1 ),
 430     aDisMem( nArrayLen )
 431 {
 432     InitData( cPattern );
 433     CalcLPQR( nOtherX, nShorterY, nLongerZ, bRelaxed );
 434 }
 435
 436
 437 // CopyCTor
 438 WLevDistance::WLevDistance( const WLevDistance& rWLD ) :
 439     nPatternLen( rWLD.nPatternLen ),
 440     aPatMem( nPatternLen + 1 ),
 441     nArrayLen( nPatternLen + 1 ),
 442     aDisMem( nArrayLen ),
 443     nLimit( rWLD.nLimit ),
 444     nRepP0( rWLD.nRepP0 ),
 445     nInsQ0( rWLD.nInsQ0 ),
 446     nDelR0( rWLD.nDelR0 ),
 447     nStars( rWLD.nStars ),
 448     bSplitCount( rWLD.bSplitCount )
 449 {
 450     cpPattern = aPatMem.GetcPtr();
 451     bpPatIsWild = aPatMem.GetbPtr();
 452     npDistance = aDisMem.GetPtr();
 453     sal_Int32 i;
 454     for ( i=0; i<nPatternLen; i++ )
 455     {
 456         cpPattern[i] = rWLD.cpPattern[i];
 457         bpPatIsWild[i] = rWLD.bpPatIsWild[i];
 458     }
 459     cpPattern[i] = '\0';
 460 }
 461
 462
 463 // DTor
 464 WLevDistance::~WLevDistance()
 465 {
 466 }
 467
 468 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */