StrDiff()

Evaluate the “Edit (Levensthein) Distance” of two strings

Syntax

      StrDiff( <cString1>, <cString2>, [<nReplacementPenalty>], 
               [<nDeletionPenalty>], [<nInsertionPenalty>] ) 
               -> <nDistance>

Arguments

<cString1> string at the “starting point” of the transformation process, default is “”

<cString2> string at the “end point” of the transformation process, default is “”

<nReplacementPenalty> penalty points for a replacement of one character, default is 3

<nDeletionPenalty> penalty points for a deletion of one character, default is 6

<nInsertionPenalty> penalty points for an insertion of one character, default is 1

Returns

<nDistance> penalty point sum of all operations needed to transform <cString1> to <cString2>

Description

The StrDiff() functions calculates the so called “Edit” or “Levensthein” distance of two strings. This distance is a measure for the number of single character replace/insert/delete operations (so called “point mutations”) required to transform <cString1> into <cString2> and its value will be the smallest sum of the penalty points of the required operations.

Be aware that this function is both quite time – O(len(cString1)*len(cString2)) – and memory consuming – O((len(cString1)+1)*(len(cString2)+1)*sizeof(int)) – so keep the strings as short as possible. E.g., on common 32 bit systems (sizeof(int) == 4), calling StrDiff() with two strings of 1024 bytes in length will consume 4 MB of memory. To not impose unneeded restrictions, the function will only check if (len(cString1)+1)*(len(cString2)+1)*sizeof(int) <= UINT_MAX, although allocing UINT_MAX bytes will not work on most systems. If this simple check fails, -1 is returned.

Also, be aware that there can be an overflow when the penalty points are summed up: Assuming that the number of transformation operations is in the order of max(len(cString1), len(cString2)), the penalty point sum, that is internally stored in an “int” variable, is in the order of (max(len(cString1), len(cString2))*max(nReplacementPenalty, nDeletionPenalty, nInsertionPentaly). The StrDiff() does not do an overflow check due to time performance reasons. Future versions of StrDiff() could use a type different to “int” to store the penalty point sum to save memory or to avoid overflows.

The function is aware of the settings done by SETATLIKE(), that means that the wildchar character is considered equal to ALL characters.

Examples

      ? StrDiff( "ABC", "ADC" ) // 3, one character replaced
      ? StrDiff( "ABC", "AEC" ) // 3, dito
      ? StrDiff( "CBA", "ABC" ) // 6, two characters replaced
      ? StrDiff( "ABC", "AXBC" ) // 1, one character inserted
      ? StrDiff( "AXBC", "ABC" ) // 6, one character removed
      ? StrDiff( "AXBC", "ADC" ) // 9, one character removed and one replaced

Tests

      StrDiff( "ABC", "ADC" ) == 3
      StrDiff( "ABC", "AEC" ) == 3
      StrDiff( "CBA", "ABC" ) == 6
      StrDiff( "ABC", "AXBC" ) == 1
      StrDiff( "AXBC", "ABC" ) == 6
      StrDiff( "AXBC", "ADC" ) == 9

Compliance

StrDiff() is compatible with CT3’s StrDiff().

Platforms

All

Files

Source is strdiff.c, library is libct.

Seealso

SETATLIKE()

 SETATLIKE()
 Provides an additional search mode for all AT functions
------------------------------------------------------------------------------
 Syntax

     SETATLIKE([<nNewMode>,[<cCharacter>]]) --> nOldMode

 Arguments

     <nNewMode>  Designates which mode the AT functions and STRDIFF()
     should use during searches.  At this time, the 0 and 1 modes are
     permitted.  The default value is 0.

     <cCharacter>  Designates optional wildcard characters only.  The
     default value is "?".

     ()  When called without parameters, the function returns the current
     mode.

 Returns

     When a parameter is passed, the function returns the previous mode.  If
     no parameter is passed, the function returns the current mode.

 Description

     Generally speaking, all AT functions like ATNUM(), AFTERATNUM(), and the
     function STRDIFF(), operate to find an exact match during the execution
     of the search sequence.  When you use SETATLIKE(1), an additional mode
     can be selected which permits the use of wildcard characters.  For every
     position containing a wildcard character within the search expression,
     any character can occur in the character string that is searched.  The
     first character of the search expression cannot be a wildcard, and the
     entire expression cannot consist of wildcards.  These restrictions
     simultaneously avoid unwanted recursions with ATREPL().

     The customary "?" has been used as the default wildcard character.
     However, it can be replaced by using the optional <cCharacter>
     parameter.  Any character you choose can be set as a wildcard character,
     increasing the flexibility of this group of functions.

 Notes

     .  The DOS supported "*" wildcard character is not available for
        this function.

     .  The <nNewMode> parameter was selected to be a numeric value to
        allow future implementation of additional modes.

 Examples

     .  Set the SETATLIKE(1) wildcard mode to on:

        SETATLIKE(1)

     .  Determine the beginning position at the start of the last
        search expression:

        cTextsequence  := "ABCDEABC123AXCK"
        ? ATNUM("ABC", cTextsequence)                 // 6
        ? ATNUM("A?C", cTextsequence)                 // 12

     .  Determine if the search expression occurs with the text
        sequence:

        cTextsequence  := "ABCDEABC123AXCK"
        ? NUMAT("ABC", cTextsequence)                 // 2
        ? NUMAT("A?C", cTextsequence)                 // 3

     .  Determine the portion of the text sequence behind the last
        occurrence in the search expression:

        cTextsequence  := "ABCDEABC123AXCK"
        ? AFTERATNUM("ABC", cTextsequence)            // 123AXCK
        ? AFTERATNUM("A?C", cTextsequence)            // K

     .  Determine the portion of the text sequence before the last
        occurrence in the search expression:

        cTextsequence  := "ABCDEABC123AXCK"
        ? BEFOREATNUM("ABC", cTextsequence)           // ABCDE
        ? BEFOREATNUM("A?C", cTextsequence)           // ABCDEABC123

     .  Determine the portion of the text sequence from the last
        occurrence aligned at position 15:

        cTextsequence  := "ABCDEABC123AXCK"
        ? ATADJUST("ABC", cTextsequence, 15)          // ABCDE   ABC123AXCK
        ? ATADJUST("A?C", cTextsequence, 15)          // ABCDEABC123   AXCK

     .  ATREPL() poses an unusual situation.  If a search expression
        containing wildcard characters (like the one in the following
        example) is exchanged for a sequence where you only find other
        characters at the wildcard positions, a recursion occurs internally
        if CSETATMUPA() is on:

        CSETATMUPA(.T.)
        cTextsequence  := "ABCDEABC123AXCK"
        ? ATREPL("D?", cTextsequence, "DX")           // ABCDXXXXXXXXXXXX

     .  Wildcard characters reduce the valence with the STRDIFF()
        function:

        ? STRDIFF("ABC", "AXC")                       // Valence 3
        ? STRDIFF("A?C", "AXC")                       // Valence 0

See Also: ATADJUST() ATNUM() AFTERATNUM() BEFORATNUM()