xref: /aoo42x/main/i18npool/source/search/levdis.hxx (revision f7bd9df4)
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