LCOV - code coverage report
Current view: top level - i18npool/source/search - levdis.cxx (source / functions) Hit Total Coverage
Test: commit e02a6cb2c3e2b23b203b422e4e0680877f232636 Lines: 0 186 0.0 %
Date: 2014-04-14 Functions: 0 12 0.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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             : #include <string.h>
      59             : 
      60             : #if defined( _MSC_VER )
      61             : #pragma warning(once: 4068)
      62             : #endif
      63             : 
      64             : #include "levdis.hxx"
      65             : 
      66             : #ifdef SOLARIS
      67             : #undef min
      68             : #endif
      69             : 
      70             : #define LEVDISBIG   (nLimit + 1)    // Return value if distance > nLimit
      71             : #define LEVDISDOUBLEBUF 2048        // dadrueber wird nicht mehr gedoppelt
      72             : 
      73             : // Balance, aus Geschwindigkeitsgruenden ist dieses keine Funktion
      74             : // c == cpPattern[jj] == cString[ii]
      75             : // erst wird bis Fundstelle gesucht, wenn dort die Balance gleich ist, wird
      76             : // auch nach der Fundstelle verglichen
      77             : #define LEVDISBALANCE(jj,ii)                        \
      78             : {                                                   \
      79             :     if ( jj != ii )                                 \
      80             :     {                                               \
      81             :         sal_Int32 k;                                \
      82             :         if ( jj > 0 )                               \
      83             :             for ( k=0; k < jj; k++ )                \
      84             :                 if ( cpPattern[k] == c )            \
      85             :                     nBalance++;                     \
      86             :         if ( ii > 0 )                               \
      87             :             for ( k=0; k < ii; k++ )                \
      88             :                 if ( cString[k] == c )              \
      89             :                     nBalance--;                     \
      90             :         if ( !nBalance )                            \
      91             :         {                                           \
      92             :             for ( k=jj+1; k < nPatternLen; k++ )    \
      93             :                 if ( cpPattern[k] == c )            \
      94             :                     nBalance++;                     \
      95             :             for ( k=ii+1; k < nStringLen; k++ )     \
      96             :                 if ( cString[k] == c )              \
      97             :                     nBalance--;                     \
      98             :         }                                           \
      99             :     }                                               \
     100             : }
     101             : 
     102           0 : static sal_Int32 Impl_WLD_StringLen( const sal_Unicode* pStr )
     103             : {
     104           0 :     const sal_Unicode* pTempStr = pStr;
     105           0 :     while( *pTempStr )
     106           0 :         pTempStr++;
     107           0 :     return (sal_Int32)(pTempStr-pStr);
     108             : }
     109             : 
     110             : // Distance from string to pattern
     111           0 : int WLevDistance::WLD( const sal_Unicode* cString, sal_Int32 nStringLen )
     112             : {
     113           0 :     int nSPMin = 0;     // penalty point Minimum
     114           0 :     int nRepS = 0;      // for SplitCount
     115             : 
     116             :     // Laengendifferenz von Pattern und String
     117           0 :     int nLenDiff = nPatternLen - nStars - nStringLen;
     118             :     // mehr Einfuegungen oder Loeschungen noetig als Limit? => raus hier
     119           0 :     if ( (nLenDiff * nInsQ0 > nLimit)
     120           0 :             || ((nStars == 0) && (nLenDiff * nDelR0 < -nLimit)) )
     121           0 :         return(LEVDISBIG);
     122             : 
     123             :     // wenn der zu vergleichende String groesser ist als das bisherige Array
     124             :     // muss dieses angepasst werden
     125           0 :     if ( nStringLen >= nArrayLen )
     126             :     {
     127             :         // gib ihm moeglichst mehr, damit nicht gleich naechstesmal
     128             :         // wieder realloziert werden muss
     129           0 :         if ( nStringLen < LEVDISDOUBLEBUF )
     130           0 :             nArrayLen = 2 * nStringLen;
     131             :         else
     132           0 :             nArrayLen = nStringLen + 1;
     133           0 :         npDistance = aDisMem.NewMem( nArrayLen );
     134             :     }
     135             : 
     136             :     // Anfangswerte der zweiten Spalte (erstes Pattern-Zeichen) berechnen
     137             :     // die erste Spalte (0-Len Pattern) ist immer 0 .. nStringLen * nInsQ0,
     138             :     // deren Minimum also 0
     139           0 :     if ( nPatternLen == 0 )
     140             :     {
     141             :         // Anzahl der Loeschungen, um auf Pattern zu kommen
     142           0 :         for ( sal_Int32 i=0; i <= nStringLen; i++ )
     143           0 :             npDistance[i] = i * nDelR0;
     144             :     }
     145           0 :     else if ( cpPattern[0] == '*' && bpPatIsWild[0] )
     146             :     {
     147             :         // statt einem '*' ist alles einsetzbar
     148           0 :         for ( sal_Int32 i=0; i <= nStringLen; i++ )
     149           0 :             npDistance[i] = 0;
     150             :     }
     151             :     else
     152             :     {
     153             :         sal_Unicode c;
     154             :         int nP;
     155           0 :         c = cpPattern[0];
     156           0 :         if ( c == '?' && bpPatIsWild[0] )
     157           0 :             nP = 0;     // ein '?' kann jedes Zeichen sein
     158             :         else
     159             :             // Minimum von Ersetzen und Loeschen+Einfuegen Gewichtung
     160           0 :             nP = Min3( nRepP0, nRepP0, nDelR0 + nInsQ0 );
     161           0 :         npDistance[0] = nInsQ0;     // mit einfachem Einfuegen geht's los
     162           0 :         npDistance[1] = nInsQ0;
     163           0 :         npDistance[2] = nInsQ0;
     164           0 :         int nReplacePos = -1;       // tristate flag
     165           0 :         int nDelCnt = 0;
     166           0 :         for ( sal_Int32 i=1; i <= nStringLen; i++, nDelCnt += nDelR0 )
     167             :         {
     168           0 :             if ( cString[i-1] == c )
     169           0 :                 nP = 0;     // Replace ab dieser Stelle ist 0
     170             :             // Loeschungen um auf Pattern zu kommen + Replace
     171           0 :             npDistance[i] = nDelCnt + nP;
     172           0 :             if ( bSplitCount )
     173             :             {
     174           0 :                 if ( nReplacePos < 0 && nP )
     175             :                 {   // diese Stelle wird ersetzt
     176           0 :                     nRepS++;
     177           0 :                     nReplacePos = i;
     178             :                 }
     179           0 :                 else if ( nReplacePos > 0 && !nP )
     180             :                 {
     181           0 :                     int nBalance = 0;   // gleiche Anzahl c
     182           0 :                     LEVDISBALANCE( 0, i-1 );
     183           0 :                     if ( !nBalance )
     184             :                     {   // einer wurde ersetzt, der ein Insert war
     185           0 :                         nRepS--;
     186           0 :                         nReplacePos = 0;
     187             :                     }
     188             :                 }
     189             :             }
     190             :         }
     191           0 :         nSPMin = Min3( npDistance[0], npDistance[1], npDistance[2] );
     192             :     }
     193             : 
     194             :     // Distanzmatrix berechnen
     195           0 :     sal_Int32 j = 0;        // fuer alle Spalten des Pattern, solange nicht Limit
     196           0 :     while ( (j < nPatternLen-1)
     197           0 :             && nSPMin <= (bSplitCount ? 2 * nLimit : nLimit) )
     198             :     {
     199             :         sal_Unicode c;
     200             :         int nP, nQ, nR, nPij, d1, d2;
     201             : 
     202           0 :         j++;
     203           0 :         c = cpPattern[j];
     204           0 :         if ( bpPatIsWild[j] )   // '*' oder '?' nicht escaped
     205           0 :             nP = 0;     // kann ohne Strafpunkte ersetzt werden
     206             :         else
     207           0 :             nP = nRepP0;
     208           0 :         if ( c == '*' && bpPatIsWild[j] )
     209             :         {
     210           0 :             nQ = 0;     // Einfuegen und Loeschen ohne Strafpunkte
     211           0 :             nR = 0;
     212             :         }
     213             :         else
     214             :         {
     215           0 :             nQ = nInsQ0;    // normale Gewichtung
     216           0 :             nR = nDelR0;
     217             :         }
     218           0 :         d2 = npDistance[0];
     219             :         // Anzahl Einfuegungen um von Null-String auf Pattern zu kommen erhoehen
     220           0 :         npDistance[0] = npDistance[0] + nQ;
     221           0 :         nSPMin = npDistance[0];
     222           0 :         int nReplacePos = -1;       // tristate Flag
     223             :         // fuer jede Patternspalte den String durchgehen
     224           0 :         for ( sal_Int32 i=1; i <= nStringLen; i++ )
     225             :         {
     226           0 :             d1 = d2;                // WLD( X(i-1), Y(j-1) )
     227           0 :             d2 = npDistance[i];     // WLD( X(i)  , Y(j-1) )
     228           0 :             if ( cString[i-1] == c )
     229             :             {
     230           0 :                 nPij = 0;           // p(i,j)
     231           0 :                 if ( nReplacePos < 0 )
     232             :                 {
     233           0 :                     int nBalance = 0;   // same quantity c
     234           0 :                     LEVDISBALANCE( j, i-1 );
     235           0 :                     if ( !nBalance )
     236           0 :                         nReplacePos = 0;    // keine Ersetzung mehr
     237             :                 }
     238             :             }
     239             :             else
     240           0 :                 nPij = nP;
     241             :             // WLD( X(i), Y(j) ) = min( WLD( X(i-1), Y(j-1) ) + p(i,j) ,
     242             :             //                          WLD( X(i)  , Y(j-1) ) + q      ,
     243             :             //                          WLD( X(i-1), Y(j)   ) + r      )
     244           0 :             npDistance[i] = Min3( d1 + nPij, d2 + nQ, npDistance[i-1] + nR );
     245           0 :             if ( npDistance[i] < nSPMin )
     246           0 :                 nSPMin = npDistance[i];
     247           0 :             if ( bSplitCount )
     248             :             {
     249           0 :                 if ( nReplacePos < 0 && nPij && npDistance[i] == d1 + nPij )
     250             :                 {   // this poition will be replaced
     251           0 :                     nRepS++;
     252           0 :                     nReplacePos = i;
     253             :                 }
     254           0 :                 else if ( nReplacePos > 0 && !nPij )
     255             :                 {   // Zeichen in String und Pattern gleich.
     256             :                     // wenn ab hier die gleiche Anzahl dieses Zeichens
     257             :                     // sowohl in Pattern als auch in String ist, und vor
     258             :                     // dieser Stelle das Zeichen gleich oft vorkommt, war das
     259             :                     // Replace keins. Buchstabendreher werden hier erfasst
     260             :                     // und der ReplaceS zurueckgenommen, wodurch das doppelte
     261             :                     // Limit zum Tragen kommt.
     262           0 :                     int nBalance = 0;   // same quantity c
     263           0 :                     LEVDISBALANCE( j, i-1 );
     264           0 :                     if ( !nBalance )
     265             :                     {   // einer wurde ersetzt, der ein Insert war
     266           0 :                         nRepS--;
     267           0 :                         nReplacePos = 0;
     268             :                     }
     269             :                 }
     270             :             }
     271             :         }
     272             :     }
     273           0 :     if ( (nSPMin <= nLimit) && (npDistance[nStringLen] <= nLimit) )
     274           0 :         return(npDistance[nStringLen]);
     275             :     else
     276             :     {
     277           0 :         if ( bSplitCount )
     278             :         {
     279           0 :             if ( nRepS && nLenDiff > 0 )
     280           0 :                 nRepS -= nLenDiff;      // Inserts were counted
     281           0 :             if ( (nSPMin <= 2 * nLimit)
     282           0 :                     && (npDistance[nStringLen] <= 2 * nLimit)
     283           0 :                     && (nRepS * nRepP0 <= nLimit) )
     284           0 :                 return( -npDistance[nStringLen] );
     285           0 :             return(LEVDISBIG);
     286             :         }
     287           0 :         return(LEVDISBIG);
     288             :     }
     289             : }
     290             : 
     291             : // Calculating nLimit,   nReplP0,    nInsQ0,     nDelR0,     bSplitCount
     292             : // from user values           nOtherX,    nShorterY,  nLongerZ,   bRelaxed
     293           0 : int WLevDistance::CalcLPQR( int nX, int nY, int nZ, bool bRelaxed )
     294             : {
     295           0 :     if ( nX < 0 ) nX = 0;       // only positive values
     296           0 :     if ( nY < 0 ) nY = 0;
     297           0 :     if ( nZ < 0 ) nZ = 0;
     298           0 :     if (0 == Min3( nX, nY, nZ ))     // at least one 0
     299             :     {
     300             :         int nMid, nMax;
     301           0 :         nMax = Max3( nX, nY, nZ );      // either 0 for three 0s or Max
     302           0 :         if ( 0 == (nMid = Mid3( nX, nY, nZ )) )     // even two 0
     303           0 :             nLimit = nMax;  // either 0 or the only one >0
     304             :         else        // one is 0
     305           0 :             nLimit = KGV( nMid, nMax );
     306             :     }
     307             :     else        // all three of them are not 0
     308           0 :         nLimit = KGV( KGV( nX, nY ), nZ );
     309           0 :     nRepP0 = ( nX ? nLimit / nX : nLimit + 1 );
     310           0 :     nInsQ0 = ( nY ? nLimit / nY : nLimit + 1 );
     311           0 :     nDelR0 = ( nZ ? nLimit / nZ : nLimit + 1 );
     312           0 :     bSplitCount = bRelaxed;
     313           0 :     return( nLimit );
     314             : }
     315             : 
     316             : // Groesster Gemeinsamer Teiler nach Euklid (Kettendivision)
     317             : // Sonderfall: 0 und irgendwas geben 1
     318           0 : int WLevDistance::GGT( int a, int b )
     319             : {
     320           0 :     if ( !a || !b )
     321           0 :         return 1;
     322           0 :     if ( a < 0 ) a = -a;
     323           0 :     if ( b < 0 ) b = -b;
     324           0 :     do
     325             :     {
     326           0 :         if ( a > b )
     327           0 :             a -= int(a / b) * b;
     328             :         else
     329           0 :             b -= int(b / a) * a;
     330           0 :     } while ( a && b );
     331           0 :     return( a ? a : b);
     332             : }
     333             : 
     334             : // Kleinstes Gemeinsames Vielfaches: a * b / GGT(a,b)
     335           0 : int WLevDistance::KGV( int a, int b )
     336             : {
     337           0 :     if ( a > b )    // Ueberlauf unwahrscheinlicher machen
     338           0 :         return( (a / GGT(a,b)) * b );
     339             :     else
     340           0 :         return( (b / GGT(a,b)) * a );
     341             : }
     342             : 
     343             : // Minimum of three values
     344           0 : inline int WLevDistance::Min3( int x, int y, int z )
     345             : {
     346           0 :     if ( x < y )
     347           0 :         return( x < z ? x : z );
     348             :     else
     349           0 :         return( y < z ? y : z );
     350             : }
     351             : 
     352             : // The value in the middle
     353           0 : int WLevDistance::Mid3( int x, int y, int z )
     354             : {
     355           0 :     int min = Min3(x,y,z);
     356           0 :     if ( x == min )
     357           0 :         return( y < z ? y : z);
     358           0 :     else if ( y == min )
     359           0 :         return( x < z ? x : z);
     360             :     else        // z == min
     361           0 :         return( x < y ? x : y);
     362             : }
     363             : 
     364             : // Maximum of three values
     365           0 : int WLevDistance::Max3( int x, int y, int z )
     366             : {
     367           0 :     if ( x > y )
     368           0 :         return( x > z ? x : z );
     369             :     else
     370           0 :         return( y > z ? y : z );
     371             : }
     372             : 
     373             : // Daten aus CTor initialisieren
     374           0 : void WLevDistance::InitData( const sal_Unicode* cPattern )
     375             : {
     376           0 :     cpPattern = aPatMem.GetcPtr();
     377           0 :     bpPatIsWild = aPatMem.GetbPtr();
     378           0 :     npDistance = aDisMem.GetPtr();
     379           0 :     nStars = 0;
     380           0 :     const sal_Unicode* cp1 = cPattern;
     381           0 :     sal_Unicode* cp2 = cpPattern;
     382           0 :     bool* bp = bpPatIsWild;
     383             :     // copy pattern, count asterisks, escaped Jokers
     384           0 :     while ( *cp1 )
     385             :     {
     386           0 :         if ( *cp1 == '\\' )     // maybe escaped
     387             :         {
     388           0 :             if ( *(cp1+1) == '*' || *(cp1+1) == '?' )   // next Joker?
     389             :             {
     390           0 :                 cp1++;          // skip '\\'
     391           0 :                 nPatternLen--;
     392             :             }
     393           0 :             *bp++ = false;
     394             :         }
     395           0 :         else if ( *cp1 == '*' || *cp1 == '?' )      // Joker
     396             :         {
     397           0 :             if ( *cp1 == '*' )
     398           0 :                 nStars++;       // Sternchenzaehler erhoehen
     399           0 :             *bp++ = true;
     400             :         }
     401             :         else
     402           0 :             *bp++ = false;
     403           0 :         *cp2++ = *cp1++;
     404             :     }
     405           0 :     *cp2 = '\0';
     406           0 : }
     407             : 
     408           0 : WLevDistance::WLevDistance( const sal_Unicode* cPattern,
     409             :                             int nOtherX, int nShorterY, int nLongerZ,
     410             :                             bool bRelaxed ) :
     411           0 :     nPatternLen( Impl_WLD_StringLen(cPattern) ),
     412             :     aPatMem( nPatternLen + 1 ),
     413           0 :     nArrayLen( nPatternLen + 1 ),
     414           0 :     aDisMem( nArrayLen )
     415             : {
     416           0 :     InitData( cPattern );
     417           0 :     CalcLPQR( nOtherX, nShorterY, nLongerZ, bRelaxed );
     418           0 : }
     419             : 
     420             : // CopyCTor
     421           0 : WLevDistance::WLevDistance( const WLevDistance& rWLD ) :
     422             :     nPatternLen( rWLD.nPatternLen ),
     423             :     aPatMem( nPatternLen + 1 ),
     424           0 :     nArrayLen( nPatternLen + 1 ),
     425             :     aDisMem( nArrayLen ),
     426             :     nLimit( rWLD.nLimit ),
     427             :     nRepP0( rWLD.nRepP0 ),
     428             :     nInsQ0( rWLD.nInsQ0 ),
     429             :     nDelR0( rWLD.nDelR0 ),
     430             :     nStars( rWLD.nStars ),
     431           0 :     bSplitCount( rWLD.bSplitCount )
     432             : {
     433           0 :     cpPattern = aPatMem.GetcPtr();
     434           0 :     bpPatIsWild = aPatMem.GetbPtr();
     435           0 :     npDistance = aDisMem.GetPtr();
     436             :     sal_Int32 i;
     437           0 :     for ( i=0; i<nPatternLen; i++ )
     438             :     {
     439           0 :         cpPattern[i] = rWLD.cpPattern[i];
     440           0 :         bpPatIsWild[i] = rWLD.bpPatIsWild[i];
     441             :     }
     442           0 :     cpPattern[i] = '\0';
     443           0 : }
     444             : 
     445             : // DTor
     446           0 : WLevDistance::~WLevDistance()
     447             : {
     448           0 : }
     449             : 
     450             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.10