i18npool/source/search/levdis.hxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2008 by Sun Microsystems, Inc.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * $RCSfile: levdis.hxx,v $
  10  * $Revision: 1.4.24.1 $
  11  *
  12  * This file is part of OpenOffice.org.
  13  *
  14  * OpenOffice.org is free software: you can redistribute it and/or modify
  15  * it under the terms of the GNU Lesser General Public License version 3
  16  * only, as published by the Free Software Foundation.
  17  *
  18  * OpenOffice.org is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU Lesser General Public License version 3 for more details
  22  * (a copy is included in the LICENSE file that accompanied this code).
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * version 3 along with OpenOffice.org.  If not, see
  26  * <http://www.openoffice.org/license.html>
  27  * for a copy of the LGPLv3 License.
  28  *
  29  ************************************************************************/
  30
  31 #ifndef INCLUDED_I18NPOOL_LEVDIS_HXX
  32 #define INCLUDED_I18NPOOL_LEVDIS_HXX
  33
  34 #include <rtl/ustring.hxx>
  35
  36 /*
  37  maximal X Ersetzungen  (User: gefundenes darf X Zeichen anders sein)
  38  maximal Y Einfuegungen (User: gefundenes darf Y Zeichen kuerzer sein)
  39  maximal Z Loeschungen  (User: gefundenes darf Z Zeichen laenger sein)
  40  mathematische WLD oder SplitCount  (User: strikt oder relaxed)
  41
  42  Joker ('?' und '*') fallen natuerlich nicht unter diese Bedingungen.
  43  Bei einem '?' wird eine Ersetzung nicht gezahlt, bei einem '*' darf
  44  der gefundene String an dieser Stelle beliebig viele Zeichen laenger sein.
  45
  46  Strikt: entweder maximal X anders oder Y kuerzer oder Z laenger
  47  Relaxed: maximal X anders und/oder Y kuerzer und/oder Z laenger
  48
  49  Wertebereich fuer X,Y,Z ist 0..33 um mit Limit sicher unter
  50  16-bit-signed-int-max zu bleiben, 31*32*33 gibt das Maximum
  51  KGV(31,32,33) == 32736
  52  */
  53
  54 #define LEVDISDEFAULT_XOTHER    2
  55 #define LEVDISDEFAULT_YSHORTER  1
  56 #define LEVDISDEFAULT_ZLONGER   3
  57 #define LEVDISDEFAULT_RELAXED   TRUE
  58
  59 #define LEVDISDEFAULTLIMIT  6       // default nLimit, passt zu x=2, y=1, z=3,
  60                                     // p=3, q=6, r=2
  61 #define LEVDISDEFAULT_P0    3       // default nRepP0, Gewichtung Ersetzen
  62 #define LEVDISDEFAULT_Q0    6       // default nInsQ0, Gewichtung Einfuegen
  63 #define LEVDISDEFAULT_R0    2       // default nDelR0, Gewichtung Loeschen
  64 /*
  65  Berechnung von angegebenen Userwerten max Ersetzen, Kuerzer, Laenger mittels
  66  CalcLPQR(). Unschoen: wenn in WLD z.B. nLimit durch nDelR0 erreicht ist
  67  (String ist nZ laenger als Pattern), kann kein Zeichen mehr ersetzt werden.
  68  Dies kann durch Erhoehung von nX oder/und nZ vermieden werden, natuerlich
  69  mit den entsprechenden Seiteneffekten.. oder aber mit SplitCount (s.u.), was
  70  der Default bei CalcLPQR() ist.
  71
  72  Achtung: Kuerzer = WLD.Insert, Laenger = WLD.Delete
  73
  74  Gezaehlt wird von String nach Pattern (eine Loeschung bedeutet, dass aus
  75  String etwas geloescht werden muss, um auf Pattern zu kommen)
  76
  77  Loeschungen zaehlen in diesem Beispiel am wenigsten, da meistens weniger
  78  bekannt ist, als gesucht wird. Ersetzungen erhalten mittlere Gewichtung
  79  wegen z.B. falscher Schreibweisen. Einfuegungen werden teuer.
  80
  81  Oder z.B.: P0 = 1, Q0 = 4, R0 = 4, Limit = 3
  82  Erlaubt sind maximal 4 Ersetzungen, keine Einfuegung, keine Loeschung
  83  Entspricht den Userangaben X = 3, Y = 0, Z = 0
  84
  85  bSplitCount: wenn TRUE, werden Rep/Ins/Del anders gezaehlt.  Der
  86  Rueckgabewert von WLD ist dann nicht mehr unbedingt die Levenshtein-Distanz,
  87  sondern kann negativ (-WLD) sein, wenn die WLD groesser als nLimit ist, aber
  88  die Einzelwerte jeweils innerhalb der Grenzen liegen.
  89  Bei den Default-Werten hiesse das z.B.: auch wenn der gefundene String 2
  90  Zeichen laenger ist (nLongerZ), koennen noch 3 Ersetzungen (nOtherX)
  91  erfolgen.  Zusatz-Gimmick:  Buchstabendreher zaehlen als eine Ersetzung.
  92  Mathematisch voellig unkorrekt, aber gut fuer den User ;-)
  93
  94  Zur Erlaeuterung: bei der echten WLD schoepfen alle Aktionen aus einem
  95  gemeinsamen 100%-Pool, wenn einer alles hat, ist fuer die anderen nichts
  96  mehr da. Mit bSplitCount hat Replace sein eigenes Wildwasser..
  97  */
  98
  99 class WLevDisPatternMem     // "sichere" Speicheranforderung im cTor
 100 {
 101     sal_Unicode     *cp;
 102     bool            *bp;
 103 public:
 104     WLevDisPatternMem( sal_Int32 s )    { cp = new sal_Unicode[ s ];
 105                                           bp = new bool[ s ];
 106                                         }
 107     ~WLevDisPatternMem()                { if (cp) delete [] cp;
 108                                           if (bp) delete [] bp;
 109                                         }
 110     sal_Unicode* GetcPtr() const        { return cp; }
 111     bool* GetbPtr() const               { return bp; }
 112 };
 113
 114 class WLevDisDistanceMem
 115 {
 116     int*    p;
 117 public:
 118     WLevDisDistanceMem( size_t s )  { p = 0; NewMem(s); }
 119     ~WLevDisDistanceMem()           { if (p) delete [] p; }
 120     int* GetPtr() const             { return p; }
 121     int* NewMem( size_t s )         {   if (p) delete [] p;
 122                                         return (p = new int[ s<3 ? 3 : s ]);
 123                                     }
 124 };
 125
 126 class WLevDistance
 127 {
 128     sal_Int32       nPatternLen;    // Laenge des Pattern
 129     WLevDisPatternMem   aPatMem;    // Verwaltung des Pattern Arrays
 130     sal_Unicode*    cpPattern;      // Pointer auf Pattern Array
 131     bool*           bpPatIsWild;    // Pointer auf bool Array, ob Pattern Wildcard ist
 132     sal_Int32       nArrayLen;      // Laenge des Distanz Arrays
 133     WLevDisDistanceMem  aDisMem;    // Verwaltung des Distanz Arrays
 134     int*            npDistance;     // Pointer auf Distanz Array
 135     int             nLimit;         // WLD Limit Ersetzungen/Einfuegungen/Loeschungen
 136     int             nRepP0;         // Ersetzen Gewichtung
 137     int             nInsQ0;         // Einfuegen Gewichtung
 138     int             nDelR0;         // Loeschen Gewichtung
 139     int             nStars;         // Anzahl '*' Joker im Pattern
 140     bool            bSplitCount;    // wenn TRUE, werden Rep/Ins/Del getrennt gezaehlt
 141
 142     void InitData( const sal_Unicode* cPattern );       // fuer die CToren
 143     inline int Min3( int x, int y, int z );     // inline wegen Schleife
 144     int Mid3( int x, int y, int z );
 145     int Max3( int x, int y, int z );
 146     int GGT( int a, int b );    // Groesster Gemeinsamer Teiler
 147     int KGV( int a, int b );    // Kleinstes Gemeinsames Vielfaches
 148
 149 public:
 150
 151 #ifdef erTEST
 152     // CToren fuer direktes Setzen der Gewichtung mit Set...()
 153     // im CTor werden die Defaultwerte fuer Limit/Rep/Ins/Del gesetzt
 154     explicit WLevDistance( const ::rtl::OUString& rPattern );
 155 #endif
 156
 157     // CToren mit Userangaben, danach mit GetLimit() Limit holen
 158     // interner Aufruf von CalcLPQR()
 159     // die mathematisch unkorrekte Berechnung wird als Default genommen!
 160     WLevDistance( const sal_Unicode* cPattern, int nOtherX, int nShorterY,
 161                     int nLongerZ, bool bRelaxed = true );
 162
 163     WLevDistance( const WLevDistance& rWLD );
 164     ~WLevDistance();
 165
 166     // Berechnung der Levenshtein-Distanz von String zu Pattern
 167     int WLD( const sal_Unicode* cString, sal_Int32 nStringLen );
 168
 169     // Berechnung der Gewichtung aus Userangaben, return nLimit
 170     int CalcLPQR( int nOtherX, int nShorterY, int nLongerZ,
 171                     bool bRelaxed = true );
 172
 173     inline int GetLimit() const     { return( nLimit ); }   // Limit holen
 174     inline int GetReplaceP0() const { return( nRepP0 ); }   // Gewichtungen holen
 175     inline int GetInsertQ0() const  { return( nInsQ0 ); }
 176     inline int GetDeleteR0() const  { return( nDelR0 ); }
 177     inline bool GetSplit() const    { return( bSplitCount ); }
 178     inline int SetLimit( int nNewLimit );       // Limit setzen,
 179     inline int SetReplaceP0( int nNewP0 );      // Gewichtungen setzen,
 180     inline int SetInsertQ0( int nNewQ0 );       // returnen bisherigen Wert
 181     inline int SetDeleteR0( int nNewR0 );
 182     inline bool SetSplit( bool bNewSplit );
 183         // SetSplit( TRUE ) macht nur mit Werten nach CalcLPQR() Sinn!
 184
 185     inline bool IsNormal( sal_Int32 nPos ) const { return( !bpPatIsWild[nPos] ); }
 186
 187 #ifdef erTEST
 188     void    ShowTest();
 189 #ifdef erTESTMAT
 190     void    ShowMatrix( const sal_Unicode* cString );
 191 #endif
 192 #endif
 193
 194 };
 195
 196 inline int WLevDistance::SetLimit( int nNewLimit )
 197 {
 198     int nTmp = nLimit;
 199     nLimit = nNewLimit;
 200     return( nTmp );
 201 }
 202
 203 inline int WLevDistance::SetReplaceP0( int nNewP0 )
 204 {
 205     int nTmp = nRepP0;
 206     nRepP0 = nNewP0;
 207     return( nTmp );
 208 }
 209
 210 inline int WLevDistance::SetInsertQ0( int nNewQ0 )
 211 {
 212     int nTmp = nInsQ0;
 213     nInsQ0 = nNewQ0;
 214     return( nTmp );
 215 }
 216
 217 inline int WLevDistance::SetDeleteR0( int nNewR0 )
 218 {
 219     int nTmp = nDelR0;
 220     nDelR0 = nNewR0;
 221     return( nTmp );
 222 }
 223
 224 inline bool WLevDistance::SetSplit( bool bNewSplit )
 225 {
 226     bool bTmp = bSplitCount;
 227     bSplitCount = bNewSplit;
 228     return( bTmp );
 229 }
 230
 231 #endif      // _LEVDIS_HXX
 232