# Algorithm for detecting keyboard slips

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:
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.

• You mean levenshtein distance weighted with the key distance? Jun 8 '15 at 11:48
• @ratchetfreak Mine's pretty dumb, it doesn't actually weight anything or care about levenshtein distance. You could type every key wrong but it would still detect the actual word, and there's currently nothing that checks how closely the input matches any of the keywords (except giving total preference to an input that 100% matches a keyword). Jun 8 '15 at 11:54
• Shouldn't a strictList also reject None (which is false-y) as input? What about e.g. list.insert and list.extend? And you should really comply with the style guide. Jun 8 '15 at 13:16
• @jonrsharpe I reformatted it after re-reading the style guide, but did I miss something/was there something you thought was particularly bad? strictList would reject append(None) but I only intended it to reject with append specifically. I originally did that as a fix to my original implementation when really I should have just formed my code better as Gareth Rees noted. Jun 8 '15 at 15:29
• @SuperBiasedMan: The Help Center says: "Do not change the code in the question after receiving an answer." I've left your changes alone because my answer still makes sense (apart from the capitalization of StrictList), but no more changes, please. Jun 8 '15 at 15:30

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.

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.