Algorithm for detecting keyboard slips

Question

I decided to make a script that will evaluate a user input and attempt to figure out what keyword they meant to type, by checking what characters are next to the ones they entered.

ie. On a QWERTY keyboard, d is surrounded by e,r,s,f,x and c, so if you wrote selete, this script would be able to check if you actually meant delete.

It starts by breaking the list of keywords into a 2D array of characters at each position. So the first list contains letters that occur at the start of keywords, then the next list contains letters that occur second in keywords etc.

I worked it this way to reduce the amount of work the script does when checking potentially intended inputs against keywords. And if I wanted to rewrite it as a class, I could have the indexed keywords calculated once and stored. That would mean that it only needs to evaluate the user inputs against the stored information on keyword characters.

I also defined a subclass of list in order to have it treat negative indices as errors that I could catch and pass as well as to not allow those lists to have empty variables appended as both of those behaved better for my purposes.

class StrictList(list):
    """List subclass, rejects appending falsey items and negative indexing.

    Extends __getitem__ to raise IndexErrors with negative indices.
    Extends __append__ to ignore append arguments that are falsey.
    """

    def __getitem__(self, n):
        if n < 0:
            raise IndexError("Strict lists don't accept negative indexing.")
        return list.__getitem__(self, n)

    def append(self, n):
        if not n:
            return
        return list.append(self, n)


def check(c):
    """Return only valid characters."""
    return c if c in validChars else ''

def neighbour_keys(k):   
    """Return a list of keys physically near character 'k' on the keyboard."""
    k = k.lower()
    keys = StrictList()
    keys.append(check(k))
    index = []

    for i,row in enumerate(keyboard):
        if k in row:
            index.append(i)
            # Detect whether to go one column forward or back,
            # based on which row of the keyboard this button is in.
            offset = 1 if i % 2 == 0 else -1
            index.append(row.index(k))
            break
    else:
        print ("Invalid Key: {}".format(k))
        return []

    # Iterate over the key's row, the row above and the one below,
    # pass an IndexError if the referenced index is non existent.
    for val in ([0,-1], [0, 1],         
                [-1, 0], [-1, offset],   
                [+1, 0], [ 1, offset],):
        try:
            neighbourKey = keyboard[index[0] + val[0]][index[1] + val[1]]
            keys.append(check(neighbourKey))
        except IndexError:
            pass
    return keys


def check_keys(word, keywords):
    """Return 'word' if it's in the keyword list."""
    for key in keywords:
        if word.lower() == key.lower():
            return key
    return None

def get_key(word):
    """Return 'word' with only charcters from validChars."""
    word = ''.join(c for c in word.lower() if check(c))
    return word

def index_keywords(keywords):
    """Return a 2D array of all the characters in the keywords list."""
    chars = []
    for word in keywords:
        for i,c in enumerate(word):
            c = check(c)
            try:
                if c not in chars[i]:
                    chars[i].append(c)
            except IndexError:
                chars.append(StrictList())
                chars[i].append(c)
    for index in chars:
        index.sort()
    return chars                


def check_word(word, keywords):
    """Return a list of keywords that the user may have intended to type.

    Takes a string 'word' of user input
    and a list of keywords that may have been the user's command.
    Will return either an empty list if there are no suitable results,
    or a list containing any matching keywords, even if there's just one.
    """

    originalword = get_key(word)
    firstCheck = check_keys(originalword,keywords)
    if firstCheck:
        return [firstCheck]

    possibleButtons = [neighbour_keys(c) for c in originalword]
    possibleChars = []
    keyChars = index_keywords(keywords)
    for i,buttonSet in enumerate(possibleButtons):
        possibleChars.append([])
        for button in buttonSet:
            if button in keyChars[i]:
                possibleChars[-1].append(button)

        if not possibleChars[-1]:
            # If there's no possible characters at any point,
            # no word will match so return an empty list.
            return []

    length = len(possibleChars)
    keywords = [word for word in keywords if len(word) == length]
    for i,chars in enumerate(possibleChars):
        matching = []
        for word in keywords:
            try:
                if word[i] in chars:
                    matching.append(word)
            except IndexError:
                pass
        if not matching:
            return []
        keywords = matching
    return keywords


def parse_results(word, keywords):
    """Pretty print the results of check_word."""
    if not keywords:
        return "'{}' keyword not found.".format(word)
    if len(keywords) == 1:
        return "'{}' will be interpreted as {}.".format(word, keywords[0])
    else:
        return ("'{}' can be interpreted as:\n- ".format(word) +
                "\n- ".join(word for word in keywords))

This is sample data that I used for testing, but it should be versatile enough to swap out these variables to perform different tests.

Note: I include punctuation in the keyboard but not validChars, as this allows the script to detect a punctuation mark as a typo where the user might have intended to write a letter, but it supposes that no keyword will contain punctuation.

validChars = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o',
              'p','q','r','s','t','u','v','w','x','y','z'}
keyboard = StrictList([
                   StrictList(['q','w','e','r','t','y','u','i','o','p']),
                   StrictList([None,'a','s','d','f','g','h','j','k','l',';',]),
                   StrictList(['\\','z','x','c','v','b','n','m',',','.',]),
                   ])
keywords = ['test','text','rest','yest','check', 'evaluation']

while True:
    word = raw_input("Perform a/an...")
    keys = checkWord(word,keywords)
    print parseResults(word, keys)
    # Do something with keys

I tried to keep it relatively optimised and light, but I'd like feedback on ways I could have done it better or problematic choices I've made along the way.

Answer 1

I disapprove of strictList. Writing a special subclass of list seems complex and error-prone. Why override append but not __setitem__? Why does __getitem__ not handle slices? The implementation seems to be tailored so closely to the use case that it does not seem likely that this class could have any other uses.

You say that you wrote it because it "behaved better for my purposes" but this doesn't actually explain anything. As far as I can tell, you use the features of this class in two places:

1. In neighbourKeys you want to make a list of neighbouring keys, and you want to get an IndexError if any of the neighbours go out of bounds. But in fact this doesn't make the code any shorter. Here's the original code:

   try:
       neighbourKey = keyboard[index[0] + val[0]][index[1] + val[1]]
       keys.append(check(neighbourKey))
   except IndexError:
       pass
   

   and here's the same code with explicit bounds checks:

   row, col = index[0] + val[0], index[1] + val[1]
   if 0 <= row < len(keyboard) and 0 <= col < len(keyboard[row]):
       neighbourKey = keyboard[row][col]
       keys.append(check(neighbourKey))
   

   which is one line shorter.

2. In neighbourKeys you want to make sure you only add valid keys to the list, and so you always call keys.append(check(k)), and you know that check(k) returns an empty string if k is invalid, and you know that keys.append will ignore an empty string. But this is very complex: there are a lot of things that you have to understand in order to figure out how this code works, and these things are spread out in different functions.

   Instead of:

   keys.append(check(neighbourKey))
   

   why not write:

   if neighbourKey in validChars:
       keys.append(neighbourKey)
   

   and get rid of check and strictList altogether? At the same time, instead of the special case for k:

   keys.append(check(k))
   

   add (0, 0) to the list of offsets so that this case is no longer special.