i18npool/source/search/levdis.hxx

   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 #ifndef INCLUDED_I18NPOOL_LEVDIS_HXX
  21 #define INCLUDED_I18NPOOL_LEVDIS_HXX
  22
  23 #include <rtl/ustring.hxx>
  24
  25 /*
  26  maximal X Ersetzungen  (User: gefundenes darf X Zeichen anders sein)
  27  maximal Y Einfuegungen (User: gefundenes darf Y Zeichen kuerzer sein)
  28  maximal Z Loeschungen  (User: gefundenes darf Z Zeichen laenger sein)
  29  mathematische WLD oder SplitCount  (User: strikt oder relaxed)
  30
  31  Joker ('?' und '*') fallen natuerlich nicht unter diese Bedingungen.
  32  Bei einem '?' wird eine Ersetzung nicht gezahlt, bei einem '*' darf
  33  der gefundene String an dieser Stelle beliebig viele Zeichen laenger sein.
  34
  35  Strikt: entweder maximal X anders oder Y kuerzer oder Z laenger
  36  Relaxed: maximal X anders und/oder Y kuerzer und/oder Z laenger
  37
  38  Wertebereich fuer X,Y,Z ist 0..33 um mit Limit sicher unter
  39  16-bit-signed-int-max zu bleiben, 31*32*33 gibt das Maximum
  40  KGV(31,32,33) == 32736
  41  */
  42
  43 #define LEVDISDEFAULT_XOTHER    2
  44 #define LEVDISDEFAULT_YSHORTER  1
  45 #define LEVDISDEFAULT_ZLONGER   3
  46 #define LEVDISDEFAULT_RELAXED   TRUE
  47
  48 #define LEVDISDEFAULTLIMIT  6       // default nLimit, passt zu x=2, y=1, z=3,
  49                                     // p=3, q=6, r=2
  50 #define LEVDISDEFAULT_P0    3       // default nRepP0, Gewichtung Ersetzen
  51 #define LEVDISDEFAULT_Q0    6       // default nInsQ0, Gewichtung Einfuegen
  52 #define LEVDISDEFAULT_R0    2       // default nDelR0, Gewichtung Loeschen
  53 /*
  54  Berechnung von angegebenen Userwerten max Ersetzen, Kuerzer, Laenger mittels
  55  CalcLPQR(). Unschoen: wenn in WLD z.B. nLimit durch nDelR0 erreicht ist
  56  (String ist nZ laenger als Pattern), kann kein Zeichen mehr ersetzt werden.
  57  Dies kann durch Erhoehung von nX oder/und nZ vermieden werden, natuerlich
  58  mit den entsprechenden Seiteneffekten.. oder aber mit SplitCount (s.u.), was
  59  der Default bei CalcLPQR() ist.
  60
  61  Achtung: Kuerzer = WLD.Insert, Laenger = WLD.Delete
  62
  63  Gezaehlt wird von String nach Pattern (eine Loeschung bedeutet, dass aus
  64  String etwas geloescht werden muss, um auf Pattern zu kommen)
  65
  66  Loeschungen zaehlen in diesem Beispiel am wenigsten, da meistens weniger
  67  bekannt ist, als gesucht wird. Ersetzungen erhalten mittlere Gewichtung
  68  wegen z.B. falscher Schreibweisen. Einfuegungen werden teuer.
  69
  70  Oder z.B.: P0 = 1, Q0 = 4, R0 = 4, Limit = 3
  71  Erlaubt sind maximal 4 Ersetzungen, keine Einfuegung, keine Loeschung
  72  Entspricht den Userangaben X = 3, Y = 0, Z = 0
  73
  74  bSplitCount: wenn TRUE, werden Rep/Ins/Del anders gezaehlt.  Der
  75  Rueckgabewert von WLD ist dann nicht mehr unbedingt die Levenshtein-Distanz,
  76  sondern kann negativ (-WLD) sein, wenn die WLD groesser als nLimit ist, aber
  77  die Einzelwerte jeweils innerhalb der Grenzen liegen.
  78  Bei den Default-Werten hiesse das z.B.: auch wenn der gefundene String 2
  79  Zeichen laenger ist (nLongerZ), koennen noch 3 Ersetzungen (nOtherX)
  80  erfolgen.  Zusatz-Gimmick:  Buchstabendreher zaehlen als eine Ersetzung.
  81  Mathematisch voellig unkorrekt, aber gut fuer den User ;-)
  82
  83  Zur Erlaeuterung: bei der echten WLD schoepfen alle Aktionen aus einem
  84  gemeinsamen 100%-Pool, wenn einer alles hat, ist fuer die anderen nichts
  85  mehr da. Mit bSplitCount hat Replace sein eigenes Wildwasser..
  86  */
  87
  88 class WLevDisPatternMem     // "sichere" Speicheranforderung im cTor
  89 {
  90     sal_Unicode     *cp;
  91     bool            *bp;
  92 public:
  93     WLevDisPatternMem( sal_Int32 s )    { cp = new sal_Unicode[ s ];
  94                                           bp = new bool[ s ];
  95                                         }
  96     ~WLevDisPatternMem()                { if (cp) delete [] cp;
  97                                           if (bp) delete [] bp;
  98                                         }
  99     sal_Unicode* GetcPtr() const        { return cp; }
 100     bool* GetbPtr() const               { return bp; }
 101 };
 102
 103 class WLevDisDistanceMem
 104 {
 105     int*    p;
 106 public:
 107     WLevDisDistanceMem( size_t s )  { p = 0; NewMem(s); }
 108     ~WLevDisDistanceMem()           { if (p) delete [] p; }
 109     int* GetPtr() const             { return p; }
 110     int* NewMem( size_t s )         {   if (p) delete [] p;
 111                                         return (p = new int[ s<3 ? 3 : s ]);
 112                                     }
 113 };
 114
 115 class WLevDistance
 116 {
 117     sal_Int32       nPatternLen;    // Laenge des Pattern
 118     WLevDisPatternMem   aPatMem;    // Verwaltung des Pattern Arrays
 119     sal_Unicode*    cpPattern;      // Pointer auf Pattern Array
 120     bool*           bpPatIsWild;    // Pointer auf bool Array, ob Pattern Wildcard ist
 121     sal_Int32       nArrayLen;      // Laenge des Distanz Arrays
 122     WLevDisDistanceMem  aDisMem;    // Verwaltung des Distanz Arrays
 123     int*            npDistance;     // Pointer auf Distanz Array
 124     int             nLimit;         // WLD Limit Ersetzungen/Einfuegungen/Loeschungen
 125     int             nRepP0;         // Ersetzen Gewichtung
 126     int             nInsQ0;         // Einfuegen Gewichtung
 127     int             nDelR0;         // Loeschen Gewichtung
 128     int             nStars;         // Anzahl '*' Joker im Pattern
 129     bool            bSplitCount;    // wenn TRUE, werden Rep/Ins/Del getrennt gezaehlt
 130
 131     void InitData( const sal_Unicode* cPattern );       // fuer die CToren
 132     inline int Min3( int x, int y, int z );     // inline wegen Schleife
 133     int Mid3( int x, int y, int z );
 134     int Max3( int x, int y, int z );
 135     int GGT( int a, int b );    // Groesster Gemeinsamer Teiler
 136     int KGV( int a, int b );    // Kleinstes Gemeinsames Vielfaches
 137
 138 public:
 139     // CToren mit Userangaben, danach mit GetLimit() Limit holen
 140     // interner Aufruf von CalcLPQR()
 141     // die mathematisch unkorrekte Berechnung wird als Default genommen!
 142     WLevDistance( const sal_Unicode* cPattern, int nOtherX, int nShorterY,
 143                     int nLongerZ, bool bRelaxed = true );
 144
 145     WLevDistance( const WLevDistance& rWLD );
 146     ~WLevDistance();
 147
 148     // Berechnung der Levenshtein-Distanz von String zu Pattern
 149     int WLD( const sal_Unicode* cString, sal_Int32 nStringLen );
 150
 151     // Berechnung der Gewichtung aus Userangaben, return nLimit
 152     int CalcLPQR( int nOtherX, int nShorterY, int nLongerZ,
 153                     bool bRelaxed = true );
 154
 155     inline int GetLimit() const     { return( nLimit ); }   // Limit holen
 156     inline int GetReplaceP0() const { return( nRepP0 ); }   // Gewichtungen holen
 157     inline int GetInsertQ0() const  { return( nInsQ0 ); }
 158     inline int GetDeleteR0() const  { return( nDelR0 ); }
 159     inline bool GetSplit() const    { return( bSplitCount ); }
 160     inline int SetLimit( int nNewLimit );       // Limit setzen,
 161     inline int SetReplaceP0( int nNewP0 );      // Gewichtungen setzen,
 162     inline int SetInsertQ0( int nNewQ0 );       // returnen bisherigen Wert
 163     inline int SetDeleteR0( int nNewR0 );
 164     inline bool SetSplit( bool bNewSplit );
 165         // SetSplit( TRUE ) macht nur mit Werten nach CalcLPQR() Sinn!
 166
 167     inline bool IsNormal( sal_Int32 nPos ) const { return( !bpPatIsWild[nPos] ); }
 168 };
 169
 170 inline int WLevDistance::SetLimit( int nNewLimit )
 171 {
 172     int nTmp = nLimit;
 173     nLimit = nNewLimit;
 174     return( nTmp );
 175 }
 176
 177 inline int WLevDistance::SetReplaceP0( int nNewP0 )
 178 {
 179     int nTmp = nRepP0;
 180     nRepP0 = nNewP0;
 181     return( nTmp );
 182 }
 183
 184 inline int WLevDistance::SetInsertQ0( int nNewQ0 )
 185 {
 186     int nTmp = nInsQ0;
 187     nInsQ0 = nNewQ0;
 188     return( nTmp );
 189 }
 190
 191 inline int WLevDistance::SetDeleteR0( int nNewR0 )
 192 {
 193     int nTmp = nDelR0;
 194     nDelR0 = nNewR0;
 195     return( nTmp );
 196 }
 197
 198 inline bool WLevDistance::SetSplit( bool bNewSplit )
 199 {
 200     bool bTmp = bSplitCount;
 201     bSplitCount = bNewSplit;
 202     return( bTmp );
 203 }
 204
 205 #endif      // _LEVDIS_HXX
 206
 207 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */