simhash-haskell

– Unfortunately, vanilla SimHash only compares text syntactically: it looks at whether two strings literally have words in common – but it doesn't tell you whether two texts are semantically similar.

Strings

{-# LANGUAGE OverloadedStrings #-}

Modules

Using qualified is really important, to make it easy to see what's an imported funciton and what's programmer-defined

module SimHash where

import qualified Data.Text as T
import Data.Word (Word64)
import Data.Bits (testBit, setBit, xor, popCount)
import Data.Hashable (hashPtr)
import System.IO.Unsafe (unsafePerformIO)
import Foreign.Storable (sizeOf)

Type-safety

newtype SyntacticID = SyntacticID Word64
  deriving (Show, Eq)

We set up a distinction between the type Word64 and the type SyntacticID

Bit Manipulation

Because we're working with the raw memory, we need to make sure that the compiler doesn't move our string around in RAM while we're hashing it

hash64 :: Text -> Word64
hash64 txt = unsafePerformIO $ 
  T.useAsPtr txt $ \ptr len ->
    fromIntegral <$> hashPtr ptr (fromIntegral $ len * sizeOf (undefined :: Char))

Main function

Our goal is to compute a hash function for the text, such that if two texts have similar hash functions, their content is syntactically similar.

We take our list of text tokens and

  1. vectorSums : compute the list of integers that it corresponds to
  2. give each of those integers an index, from 0 to 63
  3. buildBits : flatten the integers into a single hash value
computeSimHash :: [Text] -> SyntacticID
computeSimHash tokens = SyntacticID $ foldr buildBits 0 (zip [0..63] vectorSums)
  where

Issues

There are suboptimality issues though:

We use MV.modify

accumulateMutable :: Word64 -> MV.IOVector Int -> IO ()
accumulateMutable tokenH acc = go 0
  where
    go :: Int -> IO ()
    go 64 = return ()
    go i  = do
      let delta = if testBit tokenH i then 1 else -1
      MV.modify acc (+ delta) i
      go (i + 1)

Functions here

Hash

The starting hash we use is arbitrary

-- 1. Hash all of the tokens in the list
tokenHashes :: [Word64]
tokenHashes = map hash64 tokens

Accumulate

We take each of the hashes we got and assign it an index from 0 to 63. For each hash-index pair, accumulate will (weightDelta) add +1 if the bit value at the specified index is 1, and add -1 if the bit value is 0.

We end up with a list of 64 integers (vectorSums)

vectorSums :: [Int]
vectorSums = foldr accumulate (replicate 64 0) tokenHashes

accumulate :: Word64 -> [Int] -> [Int]
accumulate tokenH acc = zipWith (\bitIdx weight -> weight + weightDelta tokenH bitIdx) [0..63] acc

weightDelta :: Word64 -> Int -> Int
weightDelta tokenH idx = if testBit tokenH idx then 1 else -1

Rebuild a single hash

Finally, take each of those 64 integers, along with their indices, and create a 64 bit word whose 1's correspond to the indices with integers > 0, and 0's correspond to those integers < 0

buildBits :: (Int, Int) -> Word64 -> Word64
buildBits (bitIdx, score) currentWord =
  if score > 0 then setBit currentWord bitIdx else currentWord

Syntactic Distance


-- | Compute the structural distance between two semantic vectors.
-- Returns an integer between 0 (identical) and 64 (complete inversion).
syntacticDistance :: SyntacticID -> SyntacticID -> Int
syntacticDistance (SyntacticID h1) (SyntacticID h2) = popCount (h1 `xor` h2)

-- | Hard boundary rail evaluating structural duplication
isNearDuplicate :: SyntacticID -> SyntacticID -> Bool
isNearDuplicate id1 id2 = semanticDistance id1 id2 <= 3