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