# Text Similarity using K-Shingling, Minhashing and LSH(Locality Sensitive Hashing)

Last Updated on October 29, 2021 by Editorial Team

**Author(s): Supriya Ghosh**

#### Natural Language Processing

### Text Similarity using K-Shingling, Minhashing, and LSH(Locality Sensitive Hashing)

Text similarity plays an important role in Natural Language Processing (NLP) and there are several areas where this has been utilized extensively. Some of the applications include Information retrieval, text categorization, topic detection, machine translation, text summarization, document clustering, plagiarism detection, news recommendation, etc. encompassing almost allย domains.

But sometimes, it becomes difficult to understand the concept behind the Text Similarity Algorithms. This write-up will show an implementation of Text Similarity along with an explanation of the required concepts.

But before I start, let me tell you that there might be several ways and several algorithms to perform the same task. I will use one of the ways for depiction using K-Shingling, Minhashing, and LSH(Locality Sensitive Hashing).

Dataset considered is Text Extract from 3 documents for the problem atย hand.

We can use nโโโnumber of documents with each document being of significant length. But to make it simpler and avoid heavy computations, I am considering a small chunk from each document.

Letโs perform the implementation inย Steps.

**Step 1ย :**

Set your working directory to the folder where the files are placed so that R can read it. Then read all the input files from the working directory using the belowย code.

# Libraries used

library(dplyr)

library(proxy)

library(stringr)

library(data.table)

# Set the working directory

setwd(".\")

# Read the original text file

files <- list.files(path=".", pattern='*.txt', all.files=FALSE,

full.names=FALSE)

( doc <- lapply( files, readLines ) )

R Studio Inputย Display

**Step 2ย :**

Preprocess the text to remove punctuation, convert it into lower cases, and split text into word byย word.

# Preprocess text

documents <- lapply(doc, function(x) {

text <- gsub("[[:punct:]]", "", x) %>% tolower()

text <- gsub("\\s+", " ", text) %>% str_trim()

word <- strsplit(text, " ") %>% unlist()

return(word)

})

# Print the texts in files

documents[[1]]

documents[[2]]

documents[[3]]

R Studioย Display

**Step 3ย :**

Introduce **K-Shingling** which is a technique of representing documents assets. We will understand further the importance of **K-Shingling** but as of now, we can just try getting familiar with theย Steps.

K-shingle of a document at hand is said to be all the possible consecutive sub-string of length k found inย it.

Letโs illustrate with an example with k =ย 3.

Shingling <- function(document, k) {

shingles <- character( length = length(document) - k + 1 )

for( i in 1:( length(document) - k + 1 ) ) {

shingles[i] <- paste( document[ i:(i + k - 1) ], collapse = " " )

}

return( unique(shingles) )

}

# "shingle" the example document, with k = 3

documents <- lapply(documents, function(x) {

Shingling(x, k = 3)

})

list( Original = doc[[1]], Shingled = documents[[1]] )

R Studioย Display

Hence with k = 3, the k-shingles of the first document which got printed out, consist of sub-strings of lengthย 3.

The first K-Shingle is: **โthe nightย isโ**

The second Shingle is: **โnight is darkโ** and soย on.

One important point to note is that a documentโs k-shingle set should be unique. For example, if the first document above contains more than one **โthe night isโ **then it will only appear once as the set of k-shingle for that document.

**Step 4:**

Construct a** โCharacteristicโ matrix** that visualizes the relationships between the three documents. The โcharacteristicโ matrix will be a Boolean matrix, withย :

rows = the elements of every unique possible combination of shingles set across all documents.

columns = one column per document.

Thus, the matrix will be filled with 1 in row i and column j if and only if document j contains the shingle iย , otherwise it will be filled withย 0.

Let us try to understand this with the below depiction.

# Unique shingles sets across all documents

doc_dict <- unlist(documents) %>% unique()

# "Characteristic" matrix

Char_Mat <- lapply(documents, function(set, dict) {

as.integer(dict %in% set)

}, dict = doc_dict) %>% data.frame()

# set the names for both rows and columns

setnames( Char_Mat, paste( "doc", 1:length(documents), sep = "_" ) )

rownames(Char_Mat) <- doc_dict

Char_Mat

R Studioย Display

The first row of the above matrix has all three columns as 1. This is because all three documents contain the 3-shingle โthe nightย isโ.

For the second column, the value is [1, 0, 1] which means that document 2 does not have the 3-shingle โnight is dark, while document 1 and 3ย has.

One important point noted here is that most of the time these โcharacteristic matricesโ are almost sparse. Therefore, we usually try to represent these matrices only by the positions in which 1 appears, so as to be more space-efficient.

**Step 5ย :**

After creating shingle sets and characteristic matrix, we now need to measure the similarity between documents.

We will make use of **Jaccard Similarity** for thisย purpose.

For example, with two shingle sets as set1 and set2, the Jaccard Similarity will beย :

With this we will calculate the pairwise Jaccard similarities for all three documents. โdistโ function in โRโ quickly computes and returns the distance/similarity matrix.

# how similar is two given document, Jaccard similarity

JaccardSimilarity <- function(x, y) {

non_zero <- which(x | y)

set_intersect <- sum( x[non_zero] & y[non_zero] )

set_union <- length(non_zero)

return(set_intersect / set_union)

}

# create a new entry in the registry

pr_DB$set_entry( FUN = JaccardSimilarity, names = c("JaccardSimilarity") )

# Jaccard similarity distance matrix

d1 <- dist( t(Char_Mat), method = "JaccardSimilarity" )

# delete the new entry

pr_DB$delete_entry("JaccardSimilarity")

d1

doc

R Studioย Display

The similarity matrix d1 tells us that document 1 and 3 is the most similar among the three documents.

For small datasets, the above method works perfectly fine, but imagine if we have a large number of documents to compare instead of just three that too with significantly larger lengths, then the above method might not scale well, and we might have heavy computation with performance issue building up as the sparse matrices with a set of unique shingles across all documents will be fairly large, making computation of the Jaccard similarity between the documents aย burden.

Under such situations, we employ a different technique that help us save computations and can compare document similarities on a large scale efficiently. The technique is called **Minhashing.**

**Step 6ย :**

**Minhashing** involves compressing the large sets of unique shingles into a much smaller representation called โsignaturesโ.

We then use these signatures to measure the similarity between documents.

Although it is impossible for these signatures to give the exact similarity measure, the estimates are prettyย close.

The larger the number of signatures chosen, the more accurate the estimateย is.

For illustration let us consider anย example.

Suppose we take up the above example to minhash characteristic matrix of 16 rows into 4 signatures. Then the first step is to generate 4 columns of randomly permutated rows that are independent of each other. We can see for ourselves that this simple hash function does in fact generate random permutated rows. To generate this, we use theย formula:

Whereย :

x is the row numbers of your original characteristic matrix.

a and b are any random numbers smaller or equivalent to the maximum number of x, and they both must be unique in each signature.

For e.g. For signature 1, if 5 is generated to serve as a- coefficient, it must be ensured that this value does not serve as a- coefficient multiple times within signature 1, though it can still be usedย as

b- coefficient in signature 1. And this restriction refreshes for the next signature as well, that is, 5 can be used to serve as a or b coefficient for signature 2, but again no multiple 5 for signature 2โs a or b coefficient and soย on.

c is a prime number slightly larger than the total number of shingleย sets.

For the above example set, since the total row count is 16, thus prime number 17 will doย fine.

Now letโs generate this through the โRโย code.

# number of hash functions (signature number)

signature_num <- 4

# prime number

prime <- 17

# generate the unique coefficients

set.seed(12345)

coeff_a <- sample( nrow(Char_Mat), signature_num )

coeff_b <- sample( nrow(Char_Mat), signature_num )

# see if the hash function does generate permutations

permute <- lapply(1:signature_num, function(s) {

hash <- numeric( length = length(nrow(Char_Mat)) )

for( i in 1:nrow(Char_Mat) ) {

hash[i] <- ( coeff_a[s] * i + coeff_b[s] ) %% prime

}

return(hash)

})

# # convert to data frame

permute_df <- structure( permute, names = paste0( "hash_", 1:length(permute) ) ) %>%

data.frame()

permute_df

R Studioย Display

From the above output, we see that the 4 columns of randomly permutated rows got generated. There are 0s also, but it will not affect our computation and we will see thisย later.

**Step 7ย :**

Using the randomly permutated rows, now signatures will be calculated further. The signature value of any column (document) is obtained by using the permutated order generated by each hash function, the number of the first row in which the column has aย 1.

What we will do further is combine randomly permutated rows (generated by hash functions) with the original characteristic matrix and change the row names of the matrix to its row number to illustrate the calculation.

# use the first two signature as an example

# bind with the original characteristic matrix

Char_Mat1 <- cbind( Char_Mat, permute_df[1:2] )

rownames(Char_Mat1) <- 1:nrow(Char_Mat1)

Char_Mat1

R Studioย Display

Now considering the matrix generated above, we will start with the first hash function (hash_1).

According to our first hash functionโs permutated row order, the first row is row 14 ( why row 14ย ? because 0 is the smallest value for our randomly generated permutation, and it has a 0 in row 14, making it the first row ). Then weโll look at row 14โs entry for all three documents and try to find โwhich documentโs entry at row 14 is a 1ย ?โ. document 3โs (doc_3) row 14 is a 1, thus the signature value for document 3 generated by our first hash function is 0. But documents 2 and 3โs entries at row 14 are both 0, thus weโll have to continueย looking.

According to our first hash functionโs permutated row order, the second row is row 8 ( 1 is the second smallest value for our randomly generated permutation, and it has a value of 1 at row 8 ). We apply the same concept as above and find that document 2โs (doc_2) entry for row 8 is a 1, thus the signature value for document 2 generated by our first hash function is 1. Note that weโre already done with document 3, we do not need to check if it contains a 1 anymore. But weโre still not done, document 1โs entry at row 8 is still a 0. Hence, weโll have to lookย further.

Again, checking the permutated row order for our first hash function, the third row is row 2. document 1โs entry for row 2 is 1. Therefore, weโre done with calculating the signature values for all three columns using our first hash function!! Which are [2, 1,ย 0].

We can then apply the same notion to calculate the signature value for each column (document) using the second hash function, and so on for the third, fourth, etc. A quick look at the signature second hash function shows that the first row according to its permutated row order is row 8 and doc_2 has a 1 in row 3. Similarly, the second row is row 14 with doc_3 as 1 and the third row is row3 with doc_1 as 1. Hence, the signature values generated by our second hash function for all three documents are [2, 0,ย 1].

As for these calculated signature values, we will store them into a signature matrix along the way, which will later replace the original characteristic matrix. The following section will calculate the signature values for all 3 columns using all 4 hash functions and print out the signature matrix.

# obtain the non zero rows' index for all columns

non_zero_rows <- lapply(1:ncol(Char_Mat), function(j) {

return( which( Char_Mat[, j] != 0 ) )

})

# initialize signature matrix

SM <- matrix( data = NA, nrow = signature_num, ncol = ncol(Char_Mat) )

# for each column (document)

for( i in 1:ncol(Char_Mat) ) {

# for each hash function (signature)'s value

for( s in 1:signature_num ) {

SM[ s, i ] <- min( permute_df[, s][ non_zero_rows[[i]] ] )

}

}

# set names for clarity

colnames(SM) <- paste( "doc", 1:length(doc), sep = "_" )

rownames(SM) <- paste( "minhash", 1:signature_num, sep = "_" )

SM

R Studioย Display

Our signature matrix has the same number of columns as the original characteristic matrix, but it only has n rows, where n is the number of hash functions we wish to generate (in this caseย 4).

Let me elaborate on how do we interpret the aboveย result?

For e.g., for documents 1 and 3 (columns 1 and 3), its similarity would be 0.25 because they only agree in 1 row out of a total of 4 (both columnsโ row 4 isย 1).

Letโs calculate the same explanation throughย code.

# signature similarity

SigSimilarity <- function(x, y) mean( x == y )

# same trick to calculate the pairwise similarity

pr_DB$set_entry( FUN = SigSimilarity, names = c("SigSimilarity") )

d2 <- dist( t(SM), method = "SigSimilarity" )

pr_DB$delete_entry("SigSimilarity")

list(SigSimilarity = d2, JaccardSimilarity = d1)

R Studioย Display

From the difference of the result between the original Jaccard similarity and the new similarity obtained using the signature similarity, we might doubt if this is an accurate estimate? But as mentioned earlier, Minhash's purpose is to provide a fast โapproximationโ to the true Jaccard similarity and the estimate can be closer but not 100% accurate hence the difference. Also, the example considered here is way too small to depict closer accuracy using the law of large numbers. More accurate and close results are expected with large datasets.

In cases where the primary requirement is to compute the similarity of every possible pair, probably for text clustering or so, then LSH (Locality Sensitive Hashing) does not serve the purpose but if the requirement is to find the pairs that are most likely to be similar, then a technique called Locality Sensitive Hashing can be employed further which I am discussing below.

#### Locality Sensitive Hashing

While the information necessary to compute the similarity between documents has been compressed from the original *sparse* characteristic matrix into a much smaller signature matrix, but the underlying problem or need to perform pairwise comparisons on all the documents stillย exists.

The concept for locality-sensitive hashing (LSH) is that given the signature matrix of size n (row count), we will partition it into b bands, resulting in each band with r rows. This is equivalent to the simple math formulaโโโn = br, thus when we are doing the partition, we have to be sure that the b we choose is divisible by n. Using the signature matrix above and choosing the band size to be 2 the above example will becomeย :

# number of bands and rows

bands <- 2

rows <- nrow(SM) / bands

data.frame(SM) %>%

mutate( band = rep( 1:bands, each = rows ) ) %>%

select( band, everything() )

R Studioย Display

What locality-sensitive hashing tells us is: If the signature values of two documents agree in all the rows of at least one band, then these two documents are likely to be similar and should be compared (list it as the candidate pair). Using this small set of documents might be a bad example since it can happen that none of them will get chosen as our candidate pair. For instance, if the signature value of document 2 for band 1 becomes [ 0, 1 ] instead of the current [ 1, 0 ], then document 2 and document 3 will become a candidate pair as both of their rows in band1 takes the same value of [ 0, 1ย ].

NoteโโโMy computations and your computations, while executing the above set of R Codes might vary as the signatures are randomly generated.

Final Thoughts

The above technique using Jaccard Similarity, Minhashing, and LSH is one of the utilized techniques to compute document similarity although many more exists. Text similarity is an active research field, and techniques are continuously evolving. Hence which method to use is very much dependent on the Use Case and the requirements of what we want toย achieve.

Thanks for readingย !!!

You can follow me on medium as wellย as

LinkedIn: Supriyaย Ghosh

Twitter: @isupriyaghosh

Text Similarity using K-Shingling, Minhashing and LSH(Locality Sensitive Hashing) was originally published in Towards AI on Medium, where people are continuing the conversation by highlighting and responding to this story.

Published via Towards AI