diff options
Diffstat (limited to 'i18npool/source/search/levdis.hxx')
| -rw-r--r-- | i18npool/source/search/levdis.hxx | 218 |
1 files changed, 218 insertions, 0 deletions
diff --git a/i18npool/source/search/levdis.hxx b/i18npool/source/search/levdis.hxx new file mode 100644 index 000000000..c789b7da8 --- /dev/null +++ b/i18npool/source/search/levdis.hxx @@ -0,0 +1,218 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * 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 . + */ + +#ifndef INCLUDED_I18NPOOL_SOURCE_SEARCH_LEVDIS_HXX +#define INCLUDED_I18NPOOL_SOURCE_SEARCH_LEVDIS_HXX + +#include <sal/types.h> +#include <memory> + +// 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 +{ + std::unique_ptr<sal_Unicode[]> cp; + std::unique_ptr<bool[]> bp; +public: + explicit WLevDisPatternMem( sal_Int32 s ) + : cp(new sal_Unicode[s]) + , bp(new bool[s]) + { + } + + sal_Unicode* GetcPtr() const { return cp.get(); } + bool* GetbPtr() const { return bp.get(); } +}; + +class WLevDisDistanceMem +{ + std::unique_ptr<int[]> p; +public: + explicit WLevDisDistanceMem( size_t s ) + { + NewMem(s); + } + int* GetPtr() const { return p.get(); } + int* NewMem( size_t s ) + { + p.reset(new int[ s<3 ? 3 : s ]); + return p.get(); + } +}; + +/** Weighted Levenshtein Distance (WLD) + + For a more detailed explanation see documentation in + i18npool/source/search/levdis.hxx + */ +class WLevDistance +{ + 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 ); + static inline int Min3( int x, int y, int z ); ///< minimum value of 3 values + static int Mid3( int x, int y, int z ); ///< middle value of 3 values + static int Max3( int x, int y, int z ); ///< maximum value of 3 values + static int GCD( int a, int b ); ///< Greatest Common Divisor + static int LCM( int a, int b ); ///< Least Common Multiple + +public: + + /** 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 ); + + WLevDistance( const WLevDistance& rWLD ); + ~WLevDistance(); + + /** Calculate the Weighted Levenshtein Distance from string to pattern. */ + int WLD( const sal_Unicode* cString, sal_Int32 nStringLen ); + + /** Calculate the internal weighs corresponding to the user input values. + @returns nLimit for later comparison with WLD() + */ + void CalcLPQR( int nOtherX, int nShorterY, int nLongerZ, + bool bRelaxed ); + + int GetLimit() const { return nLimit; } + + // Calculate current balance, keep this inline for performance reasons! + // c == cpPattern[jj] == cString[ii] + // 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; + + if ( jj != ii ) + { + sal_Int32 k; + if ( jj > 0 ) + for ( k=0; k < jj; k++ ) + if ( cpPattern[k] == c ) + nBalance++; + if ( ii > 0 ) + for ( k=0; k < ii; k++ ) + if ( cString[k] == c ) + nBalance--; + if ( !nBalance ) + { + for ( k=jj+1; k < nPatternLen; k++ ) + if ( cpPattern[k] == c ) + nBalance++; + for ( k=ii+1; k < nStringLen; k++ ) + if ( cString[k] == c ) + nBalance--; + } + } + + return nBalance; + } +}; + + +#endif + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ |