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