diff options
author | Eike Rathke <erack@redhat.com> | 2015-02-11 18:03:08 +0100 |
---|---|---|
committer | Eike Rathke <erack@redhat.com> | 2015-02-11 18:06:19 +0100 |
commit | 8fdf5e4944f44081d759f4993790821a2308b279 (patch) | |
tree | fd1cdb7099decd88674b9402bef51d80ebb422cd /i18npool | |
parent | 22f79e2bc8005b9f5e311c68ce5347913aaf68b0 (diff) |
translate documentation of Weighted Levenshtein Distance
... before the next horrible attempt arrives, use my own horrible
translation ;-)
Change-Id: I1dd72772977717da6a2da048adbfd27861e8c191
Diffstat (limited to 'i18npool')
-rw-r--r-- | i18npool/source/search/levdis.hxx | 218 |
1 files changed, 119 insertions, 99 deletions
diff --git a/i18npool/source/search/levdis.hxx b/i18npool/source/search/levdis.hxx index 94200af67f19..e25883ba91c8 100644 --- a/i18npool/source/search/levdis.hxx +++ b/i18npool/source/search/levdis.hxx @@ -22,70 +22,78 @@ #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 - LCM(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 +// Sensible default values for a user interface could be: +// LEVDISDEFAULT_XOTHER 2 +// Maximum X replacements to match query, found data may be different by X +// characters from query. +// LEVDISDEFAULT_YSHORTER 1 +// Maximum Y insertions to match query, found data may be Y characters +// shorter than query. +// LEVDISDEFAULT_ZLONGER 3 +// Maximum Z deletions to match query, found data may be Z characters +// longer than query. +// LEVDISDEFAULT_RELAXED TRUE +// Use relaxed SplitCount instead of mathematical WLD. +// +// Joker/wildcards ('?' and '*') of course do not count as +// replacement/insertion/deletion. At a '?' a replacement is not counted, for a +// '*' the found data may be any number of characters longer than the query. +// +// Strict mathematical WLD: EITHER maximum X replacements OR Y characters +// shorter OR Z characters longer. +// Relaxed SplitCount: maximum X replacements AND/OR Y character shorter AND/OR +// Z characters longer. Any combination of actions is valid. +// +// The value range for X,Y,Z is 0..33 to keep the limit within a 16 bit signed +// integer, 31*32*33 is the maximum limit, LCM(31,32,33) == 32736. +// +// The corresponding internal default weigh values for these user interface +// values would be: +// LEVDISDEFAULTLIMIT 6 +// Default nLimit, matches x=2, y=1, z=3, p=3, q=6, r=2 +// LEVDISDEFAULT_P0 3 +// Default nRepP0, weight of replacements. +// LEVDISDEFAULT_Q0 6 +// Default nInsQ0, weight of insertions. +// LEVDISDEFAULT_R0 2 +// Default nDelR0, weight of deletions. + +// The transformation of user input values to weighs is done using CalcLPQR(). +// One caveat, if the WLD reaches nLimit due to nDelR0 (i.e. data string is nZ +// characters longer than pattern) then no character can be replaced any more. +// This can be circumvented by increasing nX or/and nZ, but of course with the +// side effect of being less strict then.. or the other solution is to use +// relaxed SplitCount (see below), which is the default when using CalcLPQR(). +// +// Attention: shorter = WLD.Insert, longer = WLD.Delete +// +// View and counting is always from data string to pattern, a deletion means +// that something is deleted from data to match pattern. +// +// Deletions weigh less in this example because usually less is known than is +// searched for. Replacements get middle weight, for example because of +// misspellings. Insertions are expensive. +// +// Another example: P0 = 1, Q0 = 4, R0 = 4, Limit = 3 +// Allowed are maximum 4 replacements, no insertion, no deletion. +// Matches the user interface values X = 3, Y = 0, Z = 0 +// +// bSplitCount: if TRUE, Rep/Ins/Del are counted differently. The return value +// of WLD() then isn't necessarily the Levenshtein-Distance, but can be +// negative (-WLD) if the WLD is greater than nLimit but single values are +// within the limits. +// For the above default values that could mean: even if the found string is +// already 2 characters longer (nLongerZ), 3 replacements (nOtherX) can be made +// to reach pattern. Additionally, character swaps count as one replacement. +// Mathematically completely incorrect, but meets user expectations ;-) +// +// Explanation: in the real WLD all actions are withdrawn from a common 100% +// pool, if one gets all there's nothing left for others. With bSplitCount +// replacements have their own pool. + + +/** "Safe" memory allocation in ctor */ +class WLevDisPatternMem { sal_Unicode *cp; bool *bp; @@ -112,64 +120,76 @@ public: } }; +/** Weighted Levenshtein Distance (WLD) + + For a more detailed explanation see documentation in + i18npool/source/search/levdis.hxx + */ 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 GCD( int a, int b ); // Groesster Gemeinsamer Teiler - int LCM( int a, int b ); // Kleinstes Gemeinsames Vielfaches + sal_Int32 nPatternLen; ///< length of pattern + WLevDisPatternMem aPatMem; ///< manage allocation of pattern array + sal_Unicode* cpPattern; ///< pointer to pattern array + bool* bpPatIsWild; ///< pointer to bool array whether pattern is wildcard + sal_Int32 nArrayLen; ///< length of distance array + WLevDisDistanceMem aDisMem; ///< manage allocation of distance array + int* npDistance; ///< pointer to distance array + int nLimit; ///< WLD limit replacements/insertions/deletions + int nRepP0; ///< replacement weigh + int nInsQ0; ///< insertion weigh + int nDelR0; ///< deletion weigh + int nStars; ///< count of '*' wildcards in pattern + bool bSplitCount; ///< if TRUE, Rep/Ins/Del are counted separately + + void InitData( const sal_Unicode* cPattern ); + inline int Min3( int x, int y, int z ); ///< minimum value of 3 values + int Mid3( int x, int y, int z ); ///< middle value of 3 values + int Max3( int x, int y, int z ); ///< maximum value of 3 values + int GCD( int a, int b ); ///< Greatest Common Divisor + int LCM( int a, int b ); ///< Least Common Multiple public: - // CToren mit Userangaben, danach mit GetLimit() Limit holen - // interner Aufruf von CalcLPQR() - // die mathematisch unkorrekte Berechnung wird als Default genommen! + + /** CTor with user input. Internally calls CalcLPQR(). + + After this, obtain the resulting limit using GetLimit(). + + @param bRelaxed the mathematically incorrect method is default (TRUE) + */ 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 + /** Calculate the Weighted Levenshtein Distance from string to pattern. */ int WLD( const sal_Unicode* cString, sal_Int32 nStringLen ); - // Berechnung der Gewichtung aus Userangaben, return nLimit + /** Calculate the internal weighs corresponding to the user input values. + @returns nLimit for later comparison with WLD() + */ 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 GetLimit() const { return( nLimit ); } + inline int GetReplaceP0() const { return( nRepP0 ); } 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 SetLimit( int nNewLimit ); + inline int SetReplaceP0( int nNewP0 ); + inline int SetInsertQ0( int nNewQ0 ); inline int SetDeleteR0( int nNewR0 ); + /** SetSplit(true) makes only sense after having called CalcLPQR() for the + internal weighs! */ inline bool SetSplit( bool bNewSplit ); - // SetSplit( TRUE ) macht nur mit Werten nach CalcLPQR() Sinn! inline bool IsNormal( sal_Int32 nPos ) const { return( !bpPatIsWild[nPos] ); } - // Balance, aus Geschwindigkeitsgruenden ist dieses keine Funktion + // Calculate current balance, keep this inline for performance reasons! // c == cpPattern[jj] == cString[ii] - // erst wird bis Fundstelle gesucht, wenn dort die Balance gleich ist, wird - // auch nach der Fundstelle verglichen + // First seek up to found place, if the balance is still equal there then + // also compare after the found place. int levdisbalance(sal_Int32 jj, sal_Int32 ii, sal_Unicode c, const sal_Unicode* cString, sal_Int32 nStringLen) { int nBalance = 0; @@ -235,6 +255,6 @@ inline bool WLevDistance::SetSplit( bool bNewSplit ) return( bTmp ); } -#endif // _LEVDIS_HXX +#endif /* vim:set shiftwidth=4 softtabstop=4 expandtab: */ |