i18npool/source/search/levdis.hxx

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