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:
WLevDisPatternMem(sal_Int32 s)97 WLevDisPatternMem( sal_Int32 s ) { cp = new sal_Unicode[ s ];
98 bp = new bool[ s ];
99 }
~WLevDisPatternMem()100 ~WLevDisPatternMem() { if (cp) delete [] cp;
101 if (bp) delete [] bp;
102 }
GetcPtr() const103 sal_Unicode* GetcPtr() const { return cp; }
GetbPtr() const104 bool* GetbPtr() const { return bp; }
105 };
106
107 class WLevDisDistanceMem
108 {
109 int* p;
110 public:
WLevDisDistanceMem(size_t s)111 WLevDisDistanceMem( size_t s ) { p = 0; NewMem(s); }
~WLevDisDistanceMem()112 ~WLevDisDistanceMem() { if (p) delete [] p; }
GetPtr() const113 int* GetPtr() const { return p; }
NewMem(size_t s)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
GetLimit() const166 inline int GetLimit() const { return( nLimit ); } // Limit holen
GetReplaceP0() const167 inline int GetReplaceP0() const { return( nRepP0 ); } // Gewichtungen holen
GetInsertQ0() const168 inline int GetInsertQ0() const { return( nInsQ0 ); }
GetDeleteR0() const169 inline int GetDeleteR0() const { return( nDelR0 ); }
GetSplit() const170 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
IsNormal(sal_Int32 nPos) const178 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
SetLimit(int nNewLimit)189 inline int WLevDistance::SetLimit( int nNewLimit )
190 {
191 int nTmp = nLimit;
192 nLimit = nNewLimit;
193 return( nTmp );
194 }
195
SetReplaceP0(int nNewP0)196 inline int WLevDistance::SetReplaceP0( int nNewP0 )
197 {
198 int nTmp = nRepP0;
199 nRepP0 = nNewP0;
200 return( nTmp );
201 }
202
SetInsertQ0(int nNewQ0)203 inline int WLevDistance::SetInsertQ0( int nNewQ0 )
204 {
205 int nTmp = nInsQ0;
206 nInsQ0 = nNewQ0;
207 return( nTmp );
208 }
209
SetDeleteR0(int nNewR0)210 inline int WLevDistance::SetDeleteR0( int nNewR0 )
211 {
212 int nTmp = nDelR0;
213 nDelR0 = nNewR0;
214 return( nTmp );
215 }
216
SetSplit(bool bNewSplit)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