How could I detect if a character close to another character on a QWERTY keyboard?

2

I'm developing a spam detection system and have been alerted to find that it can't detect strings like this - "asdfsdf".

My solution to this involves detecting if the previous keys were near the other keys on the keyboard. I am not getting the input (to detect spam from) from the keyboard, I'm getting it in the form of a string.

All I want to know is whether a character is one key, two keys or more than two keys away from another character.

For example, on a modern QWERTY keyboard, the characters 'q' and 'w' would be 1 key away. Same would the chars 'q' and 's'. Humans can figure this out logically, how could I do this in code?

liamzebedee

Posted 2011-10-01T15:11:52.947

Reputation: 5 331

What language are you developing in? – garnertb – 2011-10-01T15:18:08.117

Sorry, I didn't tag it, its PHP. Just tagging now... – liamzebedee – 2011-10-01T15:20:59.290

What's the target user group? Not all keyboards are QWERTY, for instance the common layout in Germany has QWERTZ. http://en.wikipedia.org/wiki/QWERTZ.

– ivarni – 2011-10-01T15:24:53.437

Its mainly for my own purposes, a small project, I only started 1 hour ago, its growing quite fast however. So I'm not going to support other layouts until I'm ready – liamzebedee – 2011-10-01T15:27:26.997

Then I wouldn't worry about making assumptions about the client keyboard right now, but do keep in mind that not all keyboards have the same layout so if you do run into problems because of that down the road you'll probably need to figure out the locale of the user and apply a different mapping of keys based on that. – ivarni – 2011-10-01T15:29:13.017

Answers

2

You could simply create a two-dimensional map for the standard qwerty keyboard. Basically it could look something like this:

map[0][0] = 'q';
map[0][1] = 'a';
map[1][0] = 'w';
map[1][1] = 's';

and so on.

When you get two characters, you simply need to find their x, and y in the array 'map' above, and can simply calculate the distance using pythagoras. It would not fill the requirement you had as 'q' and 's' being 1 distance away. But rather it would be sqrt(1^2 + 1^2) approx 1.4

The formula would be:

  • Characters are c1 and c2
  • Find coordinates for c1 and c2: (x1,y1) and (x2,y2)
  • Calculate the distance using pythagoras: dist = sqrt((x2-x1)^2 + (y2-y1)^2).
  • If necessary, ceil or floor the result.

For example:

Say you get the characters c1='q', and c2='w'. Examine the map and find that 'q' has coordinates (x1,y1) = (0, 0) and 'w' has coordinates (x2,y2) = (1, 0). The distance is

sqrt((1-0)^2 + (0-0)^2) = sqrt(1) = 1

Alexander Olsson

Posted 2011-10-01T15:11:52.947

Reputation: 1 478

Brilliant! This is the exact solution, with the equation and everything, I would've never thought of this. – liamzebedee – 2011-10-01T15:26:29.773

1Glad to help. Dont forget to accept the answer if it fully responded to your question. – Alexander Olsson – 2011-10-01T15:27:35.583

3

Well, let's see. That's a tough one. I always take the brute-force method and I stay away from advanced concepts like that guy Pythagoras tried to foist on us, so how about a two-dimensional table? Something like this. maybe:

+---+---+---+---+---+---+---
|   | a | b | c | d | f | s ...
+---+---+---+---+---+---+---
| a | 0 | 5 | 4 | 2 | 4 | 1 ...
| b | 5 | 0 | 3 | 3 | 2 | 4 ...
| c | 4 | 3 | 0 | 1 | 2 | 2 ...
| d | 2 | 3 | 1 | 0 | 1 | 1 ...
| f | 3 | 2 | 2 | 1 | 0 | 2 ...
| s | 1 | 4 | 2 | 1 | 2 | 0 ...
+---+---+---+---+---+---+---

Could that work for ya'? You could even have negative numbers to show that one key is to the left of the other. PLUS you could put a 2-integer struct in each cell where the second int is positive or negative to show that the second letter is up or down from the first. Get my patent attorney on the phone, quick!

Pete Wilson

Posted 2011-10-01T15:11:52.947

Reputation: 6 865

Interesting solution, not quite what I wanted, but another approach..I like it – liamzebedee – 2011-10-01T15:31:06.870

2

Build a map from keys to positions on an idealized keyboard. Something like:

'q' => {0,0},
'w' => {0,1},
'a' => {1,0},
's' => {1,1}, ...

Then you can take the "distance" as the mathematical distance between the two points.

Mat

Posted 2011-10-01T15:11:52.947

Reputation: 163 114

1You will need a different map for every common different keyboard layout. French spam will come from an AZERTY keyboard for instance. – rossum – 2011-10-01T15:25:18.643

1

The basic idea is to create a map of characters and their positions on the keyboard. You can then use a simple distance formula to determine how close they are together.

For example, consider the left side of the keyboard:

  1 2 3 4 5 6
  q w e r t
  a s d f g
  z x c v b

Character a has the position [2, 0] and character b has the position [3, 4]. The formula for their distance apart is:

sqrt((x2-x1)^2 + (y2-y1)^2);

So the distance between a and b is sqrt((4 - 0)^2 + (3 - 2)^2)

It'll take you a little bit of effort to map the keys into a rectangular grid (my example isn't perfect, but it gives you the idea). But after that you can build a map (or dictionary), and lookup is simple and fast.

Jim Mischel

Posted 2011-10-01T15:11:52.947

Reputation: 105 215