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