nGram Dictionary

On a recent project, had to deal with searching of tens of thousands of product descriptions, with a need to find substring matches quickly.  The select: statement in Smalltalk works like a SQL table scan – okay for small collections, but becomes seconds+ response time with larger lists.

An effective solution to this is an nGram Dictionary.  Strings of words can be broken up into sets of tri-grams, quad-grams, quint-grams, and so on.

My approach to this is a Dictionary indexed by nGram length, each element containing dictionaries of nGram strings of collections of the string objects to be searched.  Thus, indexing results as such:

3 -> ana -> ('banana')
ban -> ('banana', 'band')
4 -> bana -> ('banana')
band -> ('band')
anan -> ('banana')
5 -> banan -> ('banana')

To instantiate, just NGramDictionary new on: someCollectionofStrings from: 4 to: 10, for example.  To search, just foo search: ‘someString’.  If someString can be larger than the NGramDictionary size; search: will handle longer string searches by doing a select: scan.

How large to make the nGram Dictionary is a matter of how large and non-unique the string collection may be.  I recommend starting at the low end at 3 or 4 – searches of 1 or 2 character strings will return way too many results with most string collections to be useful.

There’s a few other special cases I kept this in this example code, to meet my particular needs; for example, this is not a strict nGram splicing – spaces, numbers and punctuation marks are excluded and become “word” boundaries.  But, the results are super-fast, enabling, for example, type-ahead select lists on a web-based form.

Object subclass: #NGramDictionary
instanceVariableNames: 'mySmallest myLargest myCollectionofStrings myNGrams'
classVariableNames: ''
poolDictionaries: ''
category: ''

at: aString
"returns strictly those strings that have an indexed nGram.  If the string is larger than
te largest nGram specified in this dictionary, return an empty collection"
nGram := self nGrams at: aString size ifAbsent: [nil].
^nGram notNil
   ifTrue: [nGram at: aString ifAbsent: [OrderedCollection new]]
   ifFalse: [Bag new]

nGramed: aCollectionofStrings n: length
"private.  Return a dictionary of all nGrams or order length for the given collection of strings, excluding nGrams with punctuation or numbers"
|ngram e words |

ngram := Dictionary new.
do: [:each |
   e := each asLowercase.
   1 to: e size - length + 1 do: [:i |
        words := (e copyFrom: i to: i + length -1) subStrings: '., :;- ()[]!!''&%/#+0123456789'.
        (words size > 0 and: [words first size = length]) "split it, save if still the same length"
         [(ngram at: words first ifAbsentPut: [OrderedCollection new]) add: each]

"Private. lazily initialized"
    ^ myNGrams ifNil:
[myNGrams := Dictionary new.
mySmallest to: myLargest do: [ :i |
   myNGrams at: i put: (self nGramed: myCollectionofStrings n: i) ].
   myNGrams yourself ]

on: aCollectionofStrings from: start to: finish
"initialization method"
myCollectionofStrings := aCollectionofStrings.
mySmallest := start.
myLargest := finish

search: aString
"returns a collection of strings that contain aString.  If there's not an nGram available, do a select: , which is slower of course'"
|nGram searchstring|
searchstring := aString asLowercase.
searchstring size <= myLargest
     [nGram := self nGrams at: searchstring size.
     ^nGram at: searchstring ifAbsent: [OrderedCollection new]]
     [nGram := self nGrams at: myLargest.
     ^(nGram at: (searchstring copyFrom: 1 to: myLargest) ifAbsent: [OrderedCollection new])
select: [: each | each asLowercase includesSubString: searchstring]