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 230