Forem: Aniruddha Bhattacharjee

Algorithmic Deep-dive: Dynamic String Matching

Aniruddha Bhattacharjee — Sun, 08 Nov 2020 12:19:31 +0000

Setup

Consider a minimalistic and austere typing game wherein a player is required to type a bunch of words appearing on the screen before the timer expires.

Something like this:

The entire implementation of the game is here

Okay! Lets get to it then.

Problem

Lets consider the problem of actually matching the player string to the list of words. The typical implementation of it would work something like this:

Record the player input, we will refer to its present state as player_string
When the player hits enter, match the current player string with the list of words like

if player_string in word_list:
    # do something

The time complexity of this is O(len(player_string)*len(word_list)), which is fine if we are only processing such matching when the player hits enter. But say we don't want that, what we want is whenever the player presses any key, the player_string is matched with words in the word_list. Now the earlier time complexity seems a bit extraneous and we will try to come with a more elegant and efficient approach to solve this.

Requirements

Before going into the nitty-gritty of the different approaches used, let us take a pause and list down our exact requirements.

The string matching needs to be done with each keystroke, not just when player hits enter.
We should support the following user actions:
- The player can insert an alphanumeric character.
- The player can delete the character left of the cursor position, if any, by pressing backspace.
- The player can move the cursor position using the left-right direction keys.

Trie Approach

If you are not familiar with the Trie data structure, refer here1,
here2. Very briefly, Trie or prefix tree is a data structure that stores a list of strings in a tree structure and helps maintain the time complexity of many operations like insertion, deletion and search to order of O(len(word)). Note Trie can be used in various contexts other than just strings, refer here3 to understand how tries can be used to solve bit manipulation questions.

Now that we have got the introductions out of the way, lets see how Tries are relevant to our problem. Tries are pertinent to us in two ways:

Store the list of words:

Something like
The time required to store all the words in the list will be of order O(n*m), where n = len(words) and m = max(len(word))

Check if the player_string matches with any word:

Now, if you're following along, this part is rather trivial. We start at the root of the tree and for every character entered we traverse the tree accordingly and if we ever arrive at a node with last == True, VOILA! there is a match and we can strike that word out from the list, easy peasy.

But what happens if the player presses backspace, our data structure still doesn't have the capability to process this user action. A typical Trie implementation doesn't support going back along a path but this can be easily added by either appending an extra attribute parent to each trie node that way we can move back one node whenever the user presses backspace or the way I did it, by augmenting a list to keep track of all the nodes we have visited while traversing some input and then popping nodes from this list with each backspace. This does increase the space complexity to O(len(word)) but keeps the time complexity to O(1) for insertion and backspace user actions.

The implementation for this Trie based approach can be found here

Rolling hash + Deque Approach

The problem with Trie based approach is that, at least to the best of my knowledge, there's no way to incorporate the cursor moving actions. Come to think of it this does make sense, Trie or prefix tree, is a data structure which is designed to process, no surprises here, prefixes and as soon a player starts moving his/her cursor and start typing from arbitrary positions in the string that prerequisite is broken. So what do we do?

Rolling hash comes to the rescue. Rolling hash is a hashing technique which processes one character at a time for computing the hash value and depending how one implements it, can efficiently recompute hash values if some character(s) are to inserted/deleted. Rolling hash is used in the Rabin Karp algorithm for pattern matching here1 and also palindrome based queries here2.

Rolling hash intuitively fits the bill as it allows us to efficiently compute hash values for insertion and deletion operations. But what about the cursor moving actions? Well, for that we have to employ deques to dynamically maintain characters to the right and left of the cursor position. This approach works this way:

Store the list of words:

We compute the hash value for all the words in the list and store them in a dictionary.

Check if the player_string matches with any word:

We dynamically compute the hash value of the player_string with each user action and check if the hash value is present in the dictionary of stored hashes, if yes then we ensure that the strings actually match by brute-force string-matching of the player_string with the potential match.

This approach maintains a time complexity of O(log(mod)) per user action, where mod is the modulo used in calculating the hash values of the strings. Note that this approach does depend on the uniqueness of the hashing algorithm and key space used. For this instance I used a modulo closer to ~10^10.

The implementation of this Rolling hash + Deque approach can be found here

So that's it, the rolling hash + deque approach maintains a minimal time complexity for our problem while supporting all the intended user actions.

I've tried to explain the approaches and their essential points succinctly and so they may not be a 100% comprehensive but do look at the code, I believe that will clear a lot of confusion. Plus do comment if you believe anything is wrong or you think there is a more elegant or efficient way of solving this, I would love to learn about it.

Python's Import System

Aniruddha Bhattacharjee — Sat, 15 Aug 2020 10:49:14 +0000

In this blog, I want to shed some light on a somewhat overlooked and taken-for-granted feature of Python, and many programming languages for that matter, the Import System, specifically how Python goes about importing various modules and the subtle nuances involved in the process.

Before delving into the topic at hand, I want to briefly outline the difference between a Python module and a Python script, this will come in handy when we discuss relative imports.

Python Module & Python Script

In essence, both a python module and a python script are executable python code but serve different purposes, a script is a python file that is executed on its own like python xyz.py whereas a module is a python file that is imported by other python files and typically not executed on its own. Another subtle implementation difference shows up in the value of their global attribute __name__. The __name__ value for a python script is __main__ while that of a module is its path. To try it out, write an innocuous python file X.py and add the solitary line print("the __name__ attribute for X is", __name__). Now run X.py directly with python X.py and observe the output. Now, write another python file Y.py in the same directory and just add import X inside it. Run Y.py and Voila! see the difference in the value in the __name__ attribute for X.

When you first started learning to code in Python, you might have come across a statement at the end of the python program that read something like

if __name__ == "__main__":
# do something

Now you know the reason why! Python's __main__

Python Import System

For the sake of brevity, I'll confine this blog to the "basic" and "pertinent" (obviously basic and pertinent are used in relative terms, so don't take them absolutely) steps on what happens when Python executes an import XYZ statement without going into the more esoteric details, for that, you can refer Python's Import System.

From Python's official documentation, importing a module involves two stages:

Searching the named module.
Binding the result of the search to some name in the local namespace.

Now, the question is where does Python search the module in?
So, Python searches the required module in the following places in order:

sys.modules (the module cache)
the directories listed in sys.path (in order)

Open up a new python file and type in:

import sys
print(sys.path)

When you run this, it lists the directories Python searches to see if the requested module exists.

Another small experiment to test the precedence of imports, try this:

Create a file random.py and type in whatever you feel like it. Fire up the python shell in the same directory and import random. Which random module do you think is imported? The answer actually depends on whether you have already import random some earlier time, if yes then the in-built random module would have been cached in sys.modules and will be imported. If not then your recently created random module will be imported because the current working directory(in the interpreter it will be termed as '', an empty string) comes first in sys.path.

So, if you're stuck with an infuriating ModuleNotFoundError, try printing sys.path and append the intended module's directory in sys.path, sys.path.append('path_to_the_module_directory'). Be wary of name clashes though!

Relative Imports

This is one of the conundrums that has vexed a lot of people and mostly because the official Python documentation isn't very clear on this topic (I think). To be fair, Python's documentation does refer to the section as
Package Relative Imports and not Relative Imports and this is where we return to the distinction between modules and scripts, because again a Package is not supposed to be run on its own and anytime you call a Package you are essentially importing the __init__.py file defined in the top directory of the package.

So, here's the gist you cannot do relative imports on a file whose __name__ is __main__ because python uses this very attribute to construct paths for importing relative modules. So, if the __name__ of some file is /xyz/subpackage1/path2 then this is the base path used for any relative imports, import .moduleX basically implies to import a python module located in /xyz/subpackage1/path2 and import ..moduleY means to import moduleY from /xyz/subpackage1 (if it exists that is!)

If you're familiar with Django, its standard to see code like

from . import views

in urls.py but again we never really run urls.py on its own, we call manage.py and it implicitly calls urls.py in the background to do perform some tasks.

So there you have it, a small and hopefully definitive guide to imports in Python.

Thanks :)