| /************************************************************** |
| * |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you under the Apache License, Version 2.0 (the |
| * "License"); you may not use this file except in compliance |
| * with the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, |
| * software distributed under the License is distributed on an |
| * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| * KIND, either express or implied. See the License for the |
| * specific language governing permissions and limitations |
| * under the License. |
| * |
| *************************************************************/ |
| |
| |
| |
| #ifndef INCLUDED_I18NPOOL_LEVDIS_HXX |
| #define INCLUDED_I18NPOOL_LEVDIS_HXX |
| |
| #include <rtl/ustring.hxx> |
| |
| /* |
| maximal X Ersetzungen (User: gefundenes darf X Zeichen anders sein) |
| maximal Y Einfuegungen (User: gefundenes darf Y Zeichen kuerzer sein) |
| maximal Z Loeschungen (User: gefundenes darf Z Zeichen laenger sein) |
| mathematische WLD oder SplitCount (User: strikt oder relaxed) |
| |
| Joker ('?' und '*') fallen natuerlich nicht unter diese Bedingungen. |
| Bei einem '?' wird eine Ersetzung nicht gezahlt, bei einem '*' darf |
| der gefundene String an dieser Stelle beliebig viele Zeichen laenger sein. |
| |
| Strikt: entweder maximal X anders oder Y kuerzer oder Z laenger |
| Relaxed: maximal X anders und/oder Y kuerzer und/oder Z laenger |
| |
| Wertebereich fuer X,Y,Z ist 0..33 um mit Limit sicher unter |
| 16-bit-signed-int-max zu bleiben, 31*32*33 gibt das Maximum |
| KGV(31,32,33) == 32736 |
| */ |
| |
| #define LEVDISDEFAULT_XOTHER 2 |
| #define LEVDISDEFAULT_YSHORTER 1 |
| #define LEVDISDEFAULT_ZLONGER 3 |
| #define LEVDISDEFAULT_RELAXED TRUE |
| |
| #define LEVDISDEFAULTLIMIT 6 // default nLimit, passt zu x=2, y=1, z=3, |
| // p=3, q=6, r=2 |
| #define LEVDISDEFAULT_P0 3 // default nRepP0, Gewichtung Ersetzen |
| #define LEVDISDEFAULT_Q0 6 // default nInsQ0, Gewichtung Einfuegen |
| #define LEVDISDEFAULT_R0 2 // default nDelR0, Gewichtung Loeschen |
| /* |
| Berechnung von angegebenen Userwerten max Ersetzen, Kuerzer, Laenger mittels |
| CalcLPQR(). Unschoen: wenn in WLD z.B. nLimit durch nDelR0 erreicht ist |
| (String ist nZ laenger als Pattern), kann kein Zeichen mehr ersetzt werden. |
| Dies kann durch Erhoehung von nX oder/und nZ vermieden werden, natuerlich |
| mit den entsprechenden Seiteneffekten.. oder aber mit SplitCount (s.u.), was |
| der Default bei CalcLPQR() ist. |
| |
| Achtung: Kuerzer = WLD.Insert, Laenger = WLD.Delete |
| |
| Gezaehlt wird von String nach Pattern (eine Loeschung bedeutet, dass aus |
| String etwas geloescht werden muss, um auf Pattern zu kommen) |
| |
| Loeschungen zaehlen in diesem Beispiel am wenigsten, da meistens weniger |
| bekannt ist, als gesucht wird. Ersetzungen erhalten mittlere Gewichtung |
| wegen z.B. falscher Schreibweisen. Einfuegungen werden teuer. |
| |
| Oder z.B.: P0 = 1, Q0 = 4, R0 = 4, Limit = 3 |
| Erlaubt sind maximal 4 Ersetzungen, keine Einfuegung, keine Loeschung |
| Entspricht den Userangaben X = 3, Y = 0, Z = 0 |
| |
| bSplitCount: wenn TRUE, werden Rep/Ins/Del anders gezaehlt. Der |
| Rueckgabewert von WLD ist dann nicht mehr unbedingt die Levenshtein-Distanz, |
| sondern kann negativ (-WLD) sein, wenn die WLD groesser als nLimit ist, aber |
| die Einzelwerte jeweils innerhalb der Grenzen liegen. |
| Bei den Default-Werten hiesse das z.B.: auch wenn der gefundene String 2 |
| Zeichen laenger ist (nLongerZ), koennen noch 3 Ersetzungen (nOtherX) |
| erfolgen. Zusatz-Gimmick: Buchstabendreher zaehlen als eine Ersetzung. |
| Mathematisch voellig unkorrekt, aber gut fuer den User ;-) |
| |
| Zur Erlaeuterung: bei der echten WLD schoepfen alle Aktionen aus einem |
| gemeinsamen 100%-Pool, wenn einer alles hat, ist fuer die anderen nichts |
| mehr da. Mit bSplitCount hat Replace sein eigenes Wildwasser.. |
| */ |
| |
| class WLevDisPatternMem // "sichere" Speicheranforderung im cTor |
| { |
| sal_Unicode *cp; |
| bool *bp; |
| public: |
| WLevDisPatternMem( sal_Int32 s ) { cp = new sal_Unicode[ s ]; |
| bp = new bool[ s ]; |
| } |
| ~WLevDisPatternMem() { if (cp) delete [] cp; |
| if (bp) delete [] bp; |
| } |
| sal_Unicode* GetcPtr() const { return cp; } |
| bool* GetbPtr() const { return bp; } |
| }; |
| |
| class WLevDisDistanceMem |
| { |
| int* p; |
| public: |
| WLevDisDistanceMem( size_t s ) { p = 0; NewMem(s); } |
| ~WLevDisDistanceMem() { if (p) delete [] p; } |
| int* GetPtr() const { return p; } |
| int* NewMem( size_t s ) { if (p) delete [] p; |
| return (p = new int[ s<3 ? 3 : s ]); |
| } |
| }; |
| |
| class WLevDistance |
| { |
| sal_Int32 nPatternLen; // Laenge des Pattern |
| WLevDisPatternMem aPatMem; // Verwaltung des Pattern Arrays |
| sal_Unicode* cpPattern; // Pointer auf Pattern Array |
| bool* bpPatIsWild; // Pointer auf bool Array, ob Pattern Wildcard ist |
| sal_Int32 nArrayLen; // Laenge des Distanz Arrays |
| WLevDisDistanceMem aDisMem; // Verwaltung des Distanz Arrays |
| int* npDistance; // Pointer auf Distanz Array |
| int nLimit; // WLD Limit Ersetzungen/Einfuegungen/Loeschungen |
| int nRepP0; // Ersetzen Gewichtung |
| int nInsQ0; // Einfuegen Gewichtung |
| int nDelR0; // Loeschen Gewichtung |
| int nStars; // Anzahl '*' Joker im Pattern |
| bool bSplitCount; // wenn TRUE, werden Rep/Ins/Del getrennt gezaehlt |
| |
| void InitData( const sal_Unicode* cPattern ); // fuer die CToren |
| inline int Min3( int x, int y, int z ); // inline wegen Schleife |
| int Mid3( int x, int y, int z ); |
| int Max3( int x, int y, int z ); |
| int GGT( int a, int b ); // Groesster Gemeinsamer Teiler |
| int KGV( int a, int b ); // Kleinstes Gemeinsames Vielfaches |
| |
| public: |
| |
| #ifdef erTEST |
| // CToren fuer direktes Setzen der Gewichtung mit Set...() |
| // im CTor werden die Defaultwerte fuer Limit/Rep/Ins/Del gesetzt |
| explicit WLevDistance( const ::rtl::OUString& rPattern ); |
| #endif |
| |
| // CToren mit Userangaben, danach mit GetLimit() Limit holen |
| // interner Aufruf von CalcLPQR() |
| // die mathematisch unkorrekte Berechnung wird als Default genommen! |
| WLevDistance( const sal_Unicode* cPattern, int nOtherX, int nShorterY, |
| int nLongerZ, bool bRelaxed = true ); |
| |
| WLevDistance( const WLevDistance& rWLD ); |
| ~WLevDistance(); |
| |
| // Berechnung der Levenshtein-Distanz von String zu Pattern |
| int WLD( const sal_Unicode* cString, sal_Int32 nStringLen ); |
| |
| // Berechnung der Gewichtung aus Userangaben, return nLimit |
| int CalcLPQR( int nOtherX, int nShorterY, int nLongerZ, |
| bool bRelaxed = true ); |
| |
| inline int GetLimit() const { return( nLimit ); } // Limit holen |
| inline int GetReplaceP0() const { return( nRepP0 ); } // Gewichtungen holen |
| inline int GetInsertQ0() const { return( nInsQ0 ); } |
| inline int GetDeleteR0() const { return( nDelR0 ); } |
| inline bool GetSplit() const { return( bSplitCount ); } |
| inline int SetLimit( int nNewLimit ); // Limit setzen, |
| inline int SetReplaceP0( int nNewP0 ); // Gewichtungen setzen, |
| inline int SetInsertQ0( int nNewQ0 ); // returnen bisherigen Wert |
| inline int SetDeleteR0( int nNewR0 ); |
| inline bool SetSplit( bool bNewSplit ); |
| // SetSplit( TRUE ) macht nur mit Werten nach CalcLPQR() Sinn! |
| |
| inline bool IsNormal( sal_Int32 nPos ) const { return( !bpPatIsWild[nPos] ); } |
| |
| #ifdef erTEST |
| void ShowTest(); |
| #ifdef erTESTMAT |
| void ShowMatrix( const sal_Unicode* cString ); |
| #endif |
| #endif |
| |
| }; |
| |
| inline int WLevDistance::SetLimit( int nNewLimit ) |
| { |
| int nTmp = nLimit; |
| nLimit = nNewLimit; |
| return( nTmp ); |
| } |
| |
| inline int WLevDistance::SetReplaceP0( int nNewP0 ) |
| { |
| int nTmp = nRepP0; |
| nRepP0 = nNewP0; |
| return( nTmp ); |
| } |
| |
| inline int WLevDistance::SetInsertQ0( int nNewQ0 ) |
| { |
| int nTmp = nInsQ0; |
| nInsQ0 = nNewQ0; |
| return( nTmp ); |
| } |
| |
| inline int WLevDistance::SetDeleteR0( int nNewR0 ) |
| { |
| int nTmp = nDelR0; |
| nDelR0 = nNewR0; |
| return( nTmp ); |
| } |
| |
| inline bool WLevDistance::SetSplit( bool bNewSplit ) |
| { |
| bool bTmp = bSplitCount; |
| bSplitCount = bNewSplit; |
| return( bTmp ); |
| } |
| |
| #endif // _LEVDIS_HXX |
| |