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