levdis.hxx

Go to the documentation of this file.

/* -*- 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.
 
 
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();
    }
};
 
class WLevDistance
{
    sal_Int32       nPatternLen;    
    WLevDisPatternMem   aPatMem;    
    sal_Unicode*    cpPattern;      
    bool*           bpPatIsWild;    
    sal_Int32       nArrayLen;      
    WLevDisDistanceMem  aDisMem;    
    int*            npDistance;     
    int             nLimit;         
    int             nRepP0;         
    int             nInsQ0;         
    int             nDelR0;         
    int             nStars;         
    bool            bSplitCount;    
 
    void InitData( const sal_Unicode* cPattern );
    static int Mid3( int x, int y, int z );        
 
public:
 
    WLevDistance( const sal_Unicode* cPattern, int nOtherX, int nShorterY,
                    int nLongerZ, bool bRelaxed );
 
    WLevDistance( const WLevDistance& rWLD );
    ~WLevDistance();
 
    int WLD( const sal_Unicode* cString, sal_Int32 nStringLen );
 
    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) const
    {
        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: */