Forem: Jeff Gould

Reimplementing grep in JavaScript using rolling hashes

Jeff Gould — Fri, 03 Jan 2020 14:22:45 +0000

Some time ago I watched an interview on interviewing.io where the task that the interviewer posed to the interviewee was to create a function called grep() that should accept two strings, haystack and needle, and return an array of indexes where needle exists in haystack.

The naive approach

The naive approach is pretty simple in javascript, just loop through each letter in the haystack, grab a slice starting at the current letter that is the length of the needle, and check to see if that slice is equal to the needle.

Here's what that might look like:

// Naive approach
function grepNaive(haystack, needle) {
  const matches = [];
  for(let i = 0; i < haystack.length - (needle.length-1); i++){
    const substr = haystack.slice(i, i + needle.length);
    if( substr === needle ) matches.push(i);
  } 
  return matches; 
}

This works great but it's not super efficient. The loop only runs once for each possible match, but the string comparison is arguably a heavy operation that further requires that each letter in the slice be compared to each letter in the needle. JavaScript hides this bit of complexity from us by allowing us to check string equality, but under the hood each individual letter still needs to be evaluated and since we're making this comparison once for each letter in the haystack, most letters actually get compared multiple times.

A more efficient solution: rolling-hash search

If you were to get asked this question in an interview, this is the point where the interviewer would say something a long the lines of "this is great, but is there a more efficient solution?" Any maybe you've memorized Rabin-Karp because you're a 10x-rockstar-ninja-guru. Awesome. If you're like me and you have no idea what fish have to do with pattern matching algorithms - then you've come to the right place!

First thing's first: What even is a rolling hash? Well, basically it's the idea that you can find hash of a substring within a string and then shift the first letter out of that hash and push another letter onto the end of the hash to find the hash of the substring next to the original without recalculating the entire hash. To do that we need to come up with a way to hash strings that will allow us to do this shift and push operation while still producing hashes that don't produce too many collisions (eg hash('ba') ≠ hash('ab')).

To do that, let's start simple and hash just a single character with a hash1() function. We can do this by finding the character code of a character and just multiplying that by a large number - multiplying by a large number will help us to avoid hash collisions when we're finding hashes of whole strings.

function hash1(str) {
  return str.charCodeAt(0) * 256;
}

We could use this function to create hashes of stings by adding the hashes together, but right now this will still be very prone to collision because hash1('a') + hash1('b') === hash1('b') + hash1('a') - we need to add a way to create hashes that respect the order of the characters in a string, and we can do that by first adding a vector argument to our hash1() function.

function hash1(char, vector = 0) {
  return char.charCodeAt(0) * 256 ** vector;
}

All that's changed here is that we're accepting that vector argument and using it as an exponent on our hash - so now, since vector defaults to 0, hash1('d') will actually return the same value as 'd'.charCodeAt(0) which is 100 but we can specify a vector to signify different positions of the letter, so the hash1 of the letter d within the string mad would be hash1('d', 2) which would be 6553600.

Now we just need to create a string hashing function that will use our hash1() function to create hashes of whole strings. We can do that by just passing each letter to hash1(), using its position in the string as the vector and adding all of those values up. I'll do that by splitting the string up into an array of characters and then utilize JavaScript's Array.map and Array.reduce methods to find the hash value and then get the sum of all hash values in the string:

function hash(str) {
  return str
    .split('') // transform the string into an array of characters
    .map(hash1) // hash each character, using its index in the array as vector
    .reduce(add, 0) // add all of the values up (assume add function defined as `(a,b) => a+b`)
}

What's nice about this hash method is that while there is a low chance of hash collisions, the math is pretty straightforward which allows us to modify the hash without having to jump through too many hoops. For example, if you find the hash for a string like foo (7303014) and want to find the hash for just oo, all you have to do is subtract the hash for f which is just its character code 7303014 - 102 = 7302912 and then shift the exponents on the rest of the hashed characters down by one which can be done by dividing the the remaining hash number by 256 7302912/256 = 28527.

Why divide by 256? Because (a*256^n)/256 is equal to (a*256^(n-1)). So assuming the character code for "f" is 102 and "o" is 111, we can find the original hash using the following equation hash(foo) = (102*256^0) + (111*256^1) + (111*256^2) so when we subtract 102 that equation looks like hash(_oo) = (111*256^1) + (111*256^2) and then dividing by 256 gets us hash(oo) = (111*256^0)+(111*256^1). Let's create a function to express that:

function shiftHash(originalHash, firstChar) {
  return (originalHash - hash1(firstChar)) / 256;
}

Next, we can create a function to pop a character on to the end of the existing hash. To add a character onto an existing hash, we just need to add the hash1() of the character that we'd like to add, with the vector appropriate for the position that we'll add it. So if we have the hash for oo (28527) and we'd like to find the hash for oof, we just need to find hash1('f', 2) //6684672 and add that to the existing hash 28527 + 6684672 = 6713199. Here's how that would work as a function

function pushHash(originalHash, strLen, nextChar) {
  return originalHash + hash1(nextChar, strLen-1); // Subtract 1 from strLen because indexes start at 0
}

And from that we can compose a rollHash function that will remove the first character from an existing hash and add a new character onto the end:

function rollHash(originalHash, firstChar, nextChar, strLen) {
  const shiftedHash = shiftHash(originalHash, firstChar);
  return pushHash(shiftedHash, strLen, nextChar);
}

Now we can find the hash of a string hash('foo') //7303014 and then easily find the hash of oof by using rollHash(7303014, 'f', 'f', 3); //6713199.

To put it all together, we can now build our grep function by looping through our haystack to find occurrences of our needle

// Rolling Hash Approach
function grepHash(haystack, needle) {
  const matches = []; // This will store all indexes where a match occurs
  const needleHash = hash(needle);
  const needleLength = needle.length;
  let currentHash = hash(haystack.substr(0, needleLength)); 
  for (let i = 0; i < haystack.length - (needleLength - 1); i++) {
    if (needleHash === currentHash) matches.push(i); // If hashes match, push the current index into matches
    currentHash = rollHash(
      currentHash,
      haystack[i], // first character in current search
      haystack.substr(i + needleLength, 1), // next letter in haystack
      needleLength
    );
  }

  return matches;
}

The code here is definitely more complicated, but this is often the case with optimized solutions - we're doing more work up front to prevent the computer from having to do it at runtime. Here it is in a CodeSandbox for you to play around with.

Conclusion

To be completely honest, modern hardware and languages would probably still support the naive solution just fine, even at scale. So this may only be something that you use in the context of interviewing or if you enjoy trying to level up on platforms like HackerRank. As a self-taught developer, I've come to enjoy learning about algorithms because even if I don't end up using them in my day to day, it helps me to expand the way that I think about code and problem solving.

5 Great Git CLI Shortcuts

Jeff Gould — Thu, 26 Sep 2019 18:55:53 +0000

I think we're all onboard with git these days - it's the best way to collaborate on code with a team or to just keep things organized, synchronized, and tidy when you're working alone. But there's still a great divide amongst git users - those who are Git CLI purists, and those of us who are happy to fire up the likes of Tower, SourceTree, Github Desktop, or one of the (probably) hundreds of other options.

CLI users will argue that it's faster and easier to use Git on the CLI but GUI users like myself are usually thinking, "I don't have that much room in my brain, I like buttons..." And, honestly, I think both are right. I've recently been working on my Git CLI skills and a great way to get better at using Git on the CLI is to create aliases for things you do often, especially when they require complex git commands - so here are a few of my favorite git aliases, straight from my .zshrc:

`gro`

alias gro="git reset --hard @{u}"

In my mind, gro is short for "git reset origin" but I think the whole #{u} thing means upstream tracking branch or something like that. I'll use this when I just want to make sure that I'm working with exactly the same version of this branch that's on github. Now, you can use git pull which will merge remote changes into your local branch or just fast-forward the branch if it can - but I like gro because it will just blow away any edits or even commits that I've made in my current working tree which is often useful if I've been doing some experimenting but now I'm ready to get down to business.

`gpub`

alias gpub="git push --set-upstream origin $(git_current_branch)"

Whenever I'm working on a new branch and am ready to push it up to github I'll just run gpub (shorthand for "git publish") which handles the minutia of telling my origin repo what I want the branch to be called (obviously, I just want it to be the same) and setting up the tracking so that I can just git push my changes in the future. If you try to git push when you don't have a tracking branch, git will give you an error that guides you in the right direction, but gpub is just so much easier.

`gst`

alias gst="git status -sb"
alias gsb="gst"
alias gss="gst"

This is an easy one, gst is just a better git status because it throws on the -s option which generates less verbose output (easier to read) and the -b option which shows the current branch and tracking branch at the top (eg ## dev...origin/dev). I also have a few aliases for the original alias because sometimes I forget.

"Why not use gs as the alias for that, it's so much easier!" Is what you're probably asking yourself. Well, that's because...

`gs`

alias gs="git stash"

Another super simple one but I do a fair amount of stashing and stash popping. Bonus tip is that you can still add arguments and subcommands to the end of an alias so you'll often catch me running gs push -m "WIP: converting React to Angular" or just gs pop, gs list, etc.

Honestly, I could probably swap the aliases for gs and gst since I'm sure I use git status more than I use git stash but the hard part would be getting my fingers to update their keymaps.

`gcr`

gcr(){ git checkout -t origin/"${@}" }

Okay, not an alias, but a function that basically works like an alias. Short for "git checkout remote", this will let you check out a remote branch locally and set the tracking up for you as well. I often use this after I've copied the branch name from a PR on github so I can run gcr branch-to-review.

I'm particularly lazy, so there's also a bonus alias here for mac users:

alias gcrc="gcr $(pbpaste)"

This is the same as gcr but it will just use the contents of your clipboard for the branch name.

Git Commit

I've got quite a few more git aliases, but those are pretty standard fare and half of the time I forget to use aliases like gp instead of git pull when the git commands are more obvious to me. I think the great part of having aliases set up for the more complex or esoteric git commands that you use is that you don't have to memorize the command right away in order to be able to use it, just remember the alias and you can also use which to remind yourself what it actually does.

$ which gro
>gro: aliased to git reset --hard @{u}

That's super helpful. Another trick I use is to actually group all of my git aliases in a .gitaliases file and import them into my .zshrc file - then I can also set up an alias to list out all of my git aliases, kind of like a cheat sheet!

# somewhere in .zshrc
if [ -f $HOME/.gitaliases ]; then 
  . $HOME/.gitaliases
  alias gcheat="\cat $HOME/.gitaliases"
fi

Git Merge

Do you have any git aliases or even non-git cli aliases, or functions that you couldn't live with out? Let me know!

Use the Web Crypto API to Generate a Public / Private Key Pair for End to End, Asymmetric Cryptography on the Web

Jeff Gould — Thu, 26 Sep 2019 04:01:36 +0000

I'll preface this by saying that I'm not cryptography expert - just a dev who has found himself interested in the topic of cryptography in general and in asymmetric cryptography more specifically. These concepts are incredibly deep and I will barely scratch the surface but let's dip our toes in, shall we?

Public Key What Now?

Public key cryptography (or asymmetric cryptography if you nasty), is a concept in cryptography that piqued my interest about a year ago because at first glance it doesn't make any sense but seems incredibly useful. It's the idea that you can create a set of cryptographic keys that are designed to work in tandem where one key can encrypt data that can then only be decrypted by the other key.

This may sound confusing but it's the crux of quite a bit of the encryption that we use on a daily basis (ssh, ssl, other acronyms starting with s) and for good reason: We need to be able to share secrets in an untrusted environment.

I want to get to the code, so if you need more explanation on public key cryptography, I'd recommend watching this great video from Computerphile

Enter `window.crypto.subtle`

Now that we've got the what out of the way, let's get to the how which involves using the Web Crypto API.

Generating the keypair is actually super simple using crypto.subtle.generateKey - the hard part is knowing what settings to use. I'd like to use RSA-OAEP with the recommended modulusLength of 4096 and recommended publicExponent of 65437 (which needs to be expressed as a UInt8Array) and we'll use the SHA-256 algorithm hashing algorithm.

Now that we've got those variables figured out, we just need to plug them in to the generateKey method:

    const keyPair = await crypto.subtle.generateKey(
      {
        name: "RSA-OAEP",
        modulusLength: 4096,
        publicExponent: new Uint8Array([1, 0, 1]),
        hash: "SHA-256"
      },
      true,
      ["encrypt", "decrypt"]
    );

The above code will return a promise that will resolve with a CryptoKeyPair object that looks like {publicKey: CryptoKey, privateKey: CryptoKey. Easy peasy.

What now?

That's really it, but also it's kind of useless. First of all, the CryptoKeys contained within the CryptoKeyPair object will kind of only work on the current page that you're on. So, if you ask me, they're basically only good for demonstration purposes in their current state.

The next thing that we need is to be able to export them so that they're re-usable and for my money, the most convenient way to do that is to export them as JSON Web Keys since the Web Crypto API supports that out of the box:

  const publicKey = await crypto.subtle.exportKey("jwk", keyPair.publicKey);
  const privateKey = await crypto.subtle.exportKey("jwk", keyPair.privateKey);

Now that we have exported our keypair as JWKs, we can keep our private key somewhere safe and–for example–publish our public key to allow encrypted messages that only we can decrypt to be sent to us via untrusted means. But we'll save that for another day.