NGram Approximate String Matching

[Rabbit]

INTRODUCTION
An ngram is the subsequence of n units from a given sequence. These units can be words, characters, etc. For example, the 2-gram, or bigram, of the phrase "Hello World" is "He", "el", "ll", "lo", "o ", " W", "Wo", "or", "rl", and "ld".

USES
NGram modeling is often used to model natural languages. It is also used to predict the next item in a sequence. I.E., given an NGram model with frequencies of occurrence, you can predict what the next item in the sequence is going to be.

It is also used for approximate string matching. It is based on the observation that any two similar strings are likely to share many of the same NGrams. Because of this, it is also used to detect plagiarism. One of the benefits of using an ngram technique is the ability to index an ngram because the ngram of a string can be precalculated. This is in contrast to edit distance algorithms such as Levenshtein in which the string to compare and the string it is being compared to is part of the input. The ability to index an ngram leads to much faster searches but results in very large indexes.

CODE
The code below is written for VBScript but should be directly portable to VBA.

The CreateNGram function takes a string and an integer as inputs. The integer defines the size of the n-gram you wish to use to create subsequences. It outputs a 2-dimensional array. The first item is the ngram and the second item is the frequency with which it occurs.

The CompareNGram function takes two ngram arrays and outputs a double representing the similarity of the two arrays. The number returned is Dice's Coefficient of the two arrays. The higher the coefficient, the more similar the two strings.

Function CreateNGram(strInput, intN)
    Dim arrNGram, intBound, i, j, strGram, didInc, arrTemp
 
    If Len(strInput) = 0 Then Exit Function
 
    ReDim arrNGram(Len(strInput) + 1, 1)
    strInput = Chr(0) & UCase(Trim(strInput)) & Chr(0)
    intBound = -1
 
    For i = 1 To Len(strInput)-intN+1
        strGram = Mid(strInput, i, intN)
        didInc = False
 
        For j = 0 To intBound
            If strGram = arrNGram(j, 0) Then
                arrNGram(j, 1) = arrNGram(j, 1) + 1
                didInc = True
                Exit For
            End If
        Next
 
        If Not didInc Then
            intBound = intBound + 1
            arrNGram(intBound, 0) = strGram
            arrNGram(intBound, 1) = 1
        End If
    Next
 
    ReDim arrTemp(intBound, 1)
    For i = 0 To intBound
        arrTemp(i, 0) = arrNGram(i, 0)
        arrTemp(i, 1) = arrNGram(i, 1)
    Next
 
    CreateNGram = arrTemp
End Function
 
Function CompareNGram(arr1, arr2)
    Dim i, j, intMatches, intCount1, intCount2
 
    intMatches = 0
    intCount1 = 0
 
    For i = 0 To UBound(arr1)
        intCount1 = intCount1 + arr1(i, 1)
        intCount2 = 0
 
        For j = 0 To UBound(arr2)
            intCount2 = intCount2 + arr2(j, 1)
 
            If arr1(i, 0) = arr2(j, 0) Then
                If arr1(i, 1) >= arr2(j, 1) Then
                    intMatches = intMatches + arr2(j, 1)
                Else
                    intMatches = intMatches + arr1(i, 1)
                End If
            End If
        Next
    Next
 
    CompareNGram = 2 * intMatches / (intCount1 + intCount2)
End Function

[GORKAL]

Can u give a example queary

[Rabbit]

You mean a sample call of the function? You call it the same way you would any other function.

CreateNGram("sample string", 2)

[soundsofthedeep]

Hi Rabbit,

Thanks for sharing this information! I'm trying to use your functions (in VBA) to compare some strings, and I'm getting a Type Mismatch error in the CreateNGram function. It seems like the arrNGram array and the arrTemp array are empty at all times during the run, resulting in an error during the function call. Any ideas?

[Rabbit]

The CreateNGram function returns a 2 dimensional array. It looks like that's an issue for the CompareNGram function because it's defaulting to a 1 dimensional empty array. I modified the function prototype above to fix the CompareNGram function so it just defaults to a Variant.

If you're calling just CreateNGram by itself, then you need to treat the returned results as a 2 dimensional array.