source/search/levdis.cxx

/* -*- 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 .
 */

/*

    Weighted Levenshtein Distance
    including wildcards
    '*' for any number (0 or more) of arbitrary characters
    '?' for exactly one arbitrary character
    escapable with  backslash, "\*" or "\?"

    Return:
        WLD if WLD <= nLimit, else nLimit+1

    or, if bSplitCount:
        WLD if WLD <= nLimit
        -WLD if Replace and Insert and Delete <= nLimit
        else nLimit+1

    Recursive definition of WLD:

    WLD( X(i), Y(j) ) = min( WLD( X(i-1), Y(j-1) ) + p(i,j) ,
                             WLD( X(i)  , Y(j-1) ) + q      ,
                             WLD( X(i-1), Y(j)   ) + r      )

    X(i)   := the first i characters of the word X
    Y(j)   := the first j characters of the word Y
    p(i,j) := 0 if i-th character of X == j-th character of Y,
              p else

    Boundary conditions:
    WLD( X(0), Y(j) ) := j*q  (Y created by j inserts)
    WLD( X(i), Y(0) ) := i*r  (Y created by i deletes)
    WLD( X(0), Y(0) ) := 0

    Instead of recursions a dynamic algorithm is used.

    See also: German computer magazine
    c't 07/89 pages 192-208 and c't 03/94 pages 230-239
*/

#include <algorithm>
#include <numeric>

#include "levdis.hxx"

#define LEVDISBIG   (nLimit + 1)    // Return value if distance > nLimit
#define LEVDISDOUBLEBUF 2048        // no doubling atop this border

static sal_Int32 Impl_WLD_StringLen( const sal_Unicode* pStr )
{
    const sal_Unicode* pTempStr = pStr;
    while( *pTempStr )
        pTempStr++;
    return static_cast<sal_Int32>(pTempStr-pStr);
}

// Distance from string to pattern
int WLevDistance::WLD( const sal_Unicode* cString, sal_Int32 nStringLen )
{
    int nSPMin = 0;     // penalty point Minimum
    int nRepS = 0;      // for SplitCount

    // length difference between pattern and string
    int nLenDiff = nPatternLen - nStars - nStringLen;
    // more insertions or deletions necessary as the limit? Then leave
    if ( (nLenDiff * nInsQ0 > nLimit)
            || ((nStars == 0) && (nLenDiff * nDelR0 < -nLimit)) )
        return LEVDISBIG;

     // comparative String greater than  instantaneous array
    // -> adapt array size
    if ( nStringLen >= nArrayLen )
    {
        // increase size much more to avoid reallocation
        if ( nStringLen < LEVDISDOUBLEBUF )
            nArrayLen = 2 * nStringLen;
        else
            nArrayLen = nStringLen + 1;
        npDistance = aDisMem.NewMem( nArrayLen );
    }

    // Calculate start values of the second column (first pattern value).
    // First column (0-Len pattern) is always zero .. nStringLen * nInsQ0,
    // therefore the minimum is 0
    if ( nPatternLen == 0 )
    {
        // Count of deletions to reach pattern
        for ( sal_Int32 i=0; i <= nStringLen; i++ )
            npDistance[i] = i * nDelR0;
    }
    else if ( cpPattern[0] == '*' && bpPatIsWild[0] )
    {
        // instead of a '*' you can fit in anything
        for ( sal_Int32 i=0; i <= nStringLen; i++ )
            npDistance[i] = 0;
    }
    else
    {
        sal_Unicode c;
        int nP;
        c = cpPattern[0];
        if ( c == '?' && bpPatIsWild[0] )
            nP = 0;     // a '?' could be any character.
        else
            // Minimum of replacement and deletion+insertion weighting
            nP = std::min({ nRepP0, nRepP0, nDelR0 + nInsQ0 });
        npDistance[0] = nInsQ0;     // start with simple insert
        npDistance[1] = nInsQ0;
        npDistance[2] = nInsQ0;
        int nReplacePos = -1;       // tristate flag
        int nDelCnt = 0;
        for ( sal_Int32 i=1; i <= nStringLen; i++, nDelCnt += nDelR0 )
        {
            if ( cString[i-1] == c )
                nP = 0;     // Replace from this position is 0
            // Deletions to match pattern + Replace
            npDistance[i] = nDelCnt + nP;
            if ( bSplitCount )
            {
                if ( nReplacePos < 0 && nP )
                {   // this position will be replaced
                    nRepS++;
                    nReplacePos = i;
                }
                else if ( nReplacePos > 0 && !nP )
                {
                    // same count of c
                    int nBalance = levdisbalance( 0, i-1, c, cString, nStringLen );
                    if ( !nBalance )
                    {   // one was replaced that was an insertion instead
                        nRepS--;
                        nReplacePos = 0;
                    }
                }
            }
        }
        nSPMin = std::min({ npDistance[0], npDistance[1], npDistance[2] });
    }

    // calculate distance matrix
    sal_Int32 j = 0;        // for all columns of the pattern, till limit is not reached
    while ( (j < nPatternLen-1)
            && nSPMin <= (bSplitCount ? 2 * nLimit : nLimit) )
    {
        sal_Unicode c;
        int nP, nQ, nR, nPij, d2;

        j++;
        c = cpPattern[j];
        if ( bpPatIsWild[j] )   // '*' or '?' not escaped
            nP = 0;     // could be replaced without penalty
        else
            nP = nRepP0;
        if ( c == '*' && bpPatIsWild[j] )
        {
            nQ = 0;     // insertion and deletion without penalty
            nR = 0;
        }
        else
        {
            nQ = nInsQ0;    // usual weighting
            nR = nDelR0;
        }
        d2 = npDistance[0];
        // increase insert count to get from null string to pattern
        npDistance[0] = npDistance[0] + nQ;
        nSPMin = npDistance[0];
        int nReplacePos = -1;       // tristate flag
        // for each pattern column run through the string
        for ( sal_Int32 i=1; i <= nStringLen; i++ )
        {
            int d1 = d2;            // WLD( X(i-1), Y(j-1) )
            d2 = npDistance[i];     // WLD( X(i)  , Y(j-1) )
            if ( cString[i-1] == c )
            {
                nPij = 0;           // p(i,j)
                if ( nReplacePos < 0 )
                {
                    // same count of c
                    int nBalance = levdisbalance( j, i-1, c, cString, nStringLen );
                    if ( !nBalance )
                        nReplacePos = 0;    // no replacement
                }
            }
            else
                nPij = nP;
            // WLD( X(i), Y(j) ) = min( WLD( X(i-1), Y(j-1) ) + p(i,j) ,
            //                          WLD( X(i)  , Y(j-1) ) + q      ,
            //                          WLD( X(i-1), Y(j)   ) + r      )
            npDistance[i] = std::min({ d1 + nPij, d2 + nQ, npDistance[i-1] + nR });
            if ( npDistance[i] < nSPMin )
                nSPMin = npDistance[i];
            if ( bSplitCount )
            {
                if ( nReplacePos < 0 && nPij && npDistance[i] == d1 + nPij )
                {   // this position will be replaced
                    nRepS++;
                    nReplacePos = i;
                }
                else if ( nReplacePos > 0 && !nPij )
                {
                    // character is equal in string and pattern
                    //
                    // If from this point:
                    // * pattern and string have the same count of this
                    //   character
                    // * and character count is the same before this position
                    // then the replace was none.
                    //
                    // Scrambled letters are recognized here and the nRepS
                    // replacement is withdrawn, whereby the double limit kicks
                    // in.

                    // Same count of c
                    int nBalance = levdisbalance( j, i-1, c, cString, nStringLen );
                    if ( !nBalance )
                    {   // one was replaced that was an insertion instead
                        nRepS--;
                        nReplacePos = 0;
                    }
                }
            }
        }
    }
    if ( (nSPMin <= nLimit) && (npDistance[nStringLen] <= nLimit) )
        return npDistance[nStringLen];
    else
    {
        if ( bSplitCount )
        {
            if ( nRepS && nLenDiff > 0 )
                nRepS -= nLenDiff;      // Inserts were counted
            if ( (nSPMin <= 2 * nLimit)
                    && (npDistance[nStringLen] <= 2 * nLimit)
                    && (nRepS * nRepP0 <= nLimit) )
                return -npDistance[nStringLen];
            return LEVDISBIG;
        }
        return LEVDISBIG;
    }
}

// Calculating      nLimit,   nReplP0,    nInsQ0,     nDelR0,     bSplitCount
// from user values           nOtherX,    nShorterY,  nLongerZ,   bRelaxed
void WLevDistance::CalcLPQR( int nX, int nY, int nZ, bool bRelaxed )
{
    if ( nX < 0 ) nX = 0;       // only positive values
    if ( nY < 0 ) nY = 0;
    if ( nZ < 0 ) nZ = 0;
    if (0 == std::min({ nX, nY, nZ })) // at least one 0
    {
        int nMid, nMax;
        nMax = std::max({ nX, nY, nZ }); // either 0 for three 0s or Max
        if ( 0 == (nMid = Mid3( nX, nY, nZ )) ) // even two 0
            nLimit = nMax;                      // either 0 or the only one >0
        else                                    // one is 0
            nLimit = std::lcm( nMid, nMax );
    }
    else                                        // all three of them are not 0
        nLimit = std::lcm(std::lcm(nX, nY), nZ);
    nRepP0 = ( nX ? nLimit / nX : nLimit + 1 );
    nInsQ0 = ( nY ? nLimit / nY : nLimit + 1 );
    nDelR0 = ( nZ ? nLimit / nZ : nLimit + 1 );
    bSplitCount = bRelaxed;
}

// The value in the middle
int WLevDistance::Mid3( int x, int y, int z )
{
    int min = std::min({ x, y, z });
    if ( x == min )
        return std::min(y, z);
    else if ( y == min )
        return std::min(x, z);
    else        // z == min
        return std::min(x, y);
}

// initialize data from CTOR
void WLevDistance::InitData( const sal_Unicode* cPattern )
{
    cpPattern = aPatMem.GetcPtr();
    bpPatIsWild = aPatMem.GetbPtr();
    npDistance = aDisMem.GetPtr();
    nStars = 0;
    const sal_Unicode* cp1 = cPattern;
    sal_Unicode* cp2 = cpPattern;
    bool* bp = bpPatIsWild;
    // copy pattern, count asterisks, escaped Jokers
    while ( *cp1 )
    {
        if ( *cp1 == '\\' )     // maybe escaped
        {
            if ( *(cp1+1) == '*' || *(cp1+1) == '?' )   // next Joker?
            {
                cp1++;          // skip '\\'
                nPatternLen--;
            }
            *bp++ = false;
        }
        else if ( *cp1 == '*' || *cp1 == '?' )      // Joker
        {
            if ( *cp1 == '*' )
                nStars++;
            *bp++ = true;
        }
        else
            *bp++ = false;
        *cp2++ = *cp1++;
    }
    *cp2 = '\0';
}

WLevDistance::WLevDistance( const sal_Unicode* cPattern,
                            int nOtherX, int nShorterY, int nLongerZ,
                            bool bRelaxed ) :
    nPatternLen( Impl_WLD_StringLen(cPattern) ),
    aPatMem( nPatternLen + 1 ),
    nArrayLen( nPatternLen + 1 ),
    aDisMem( nArrayLen )
{
    InitData( cPattern );
    CalcLPQR( nOtherX, nShorterY, nLongerZ, bRelaxed );
}

// CopyCTor
WLevDistance::WLevDistance( const WLevDistance& rWLD ) :
    nPatternLen( rWLD.nPatternLen ),
    aPatMem( nPatternLen + 1 ),
    nArrayLen( nPatternLen + 1 ),
    aDisMem( nArrayLen ),
    nLimit( rWLD.nLimit ),
    nRepP0( rWLD.nRepP0 ),
    nInsQ0( rWLD.nInsQ0 ),
    nDelR0( rWLD.nDelR0 ),
    nStars( rWLD.nStars ),
    bSplitCount( rWLD.bSplitCount )
{
    cpPattern = aPatMem.GetcPtr();
    bpPatIsWild = aPatMem.GetbPtr();
    npDistance = aDisMem.GetPtr();
    sal_Int32 i;
    for ( i=0; i<nPatternLen; i++ )
    {
        cpPattern[i] = rWLD.cpPattern[i];
        bpPatIsWild[i] = rWLD.bpPatIsWild[i];
    }
    cpPattern[i] = '\0';
}

// DTor
WLevDistance::~WLevDistance()
{
}

/* vim:set shiftwidth=4 softtabstop=4 expandtab: */