Finding a matching string from a partial search (fuzzy logic?)

[NickThissen]

Hi,

I have a list of names of players and their names in some game. Now an administrator of that game might want to contact one of the players by sending him a message. He does that by writing a command that basically has the format "tell <player> <message>", where <player> is the name of the player.

The problem is simple: player names might be quite complicated and long (it's their screen name not their real name), and it would take the admin quite some time to find out how to spell the name exactly and he will probably make a few mistakes. Basically, having the admin type out the exact name is not practical.


So I am trying to implement a 'fuzzy logic' search (is that even the correct term?) but with a twist, I guess.

The idea is that the admin can type just part of the name and is even allowed to make a couple mistakes. For example, suppose a player has a screen name of "Mr.Smith34", then the admin should be able to type, for example

smith, mrsmith, smith34

perhaps even shorter words (smi, sm?).


The problem now is that there can be absolutely no ambiguity in which player is meant. Instead of sending a message (which is quite harmless) the admin should also be able to 'kick' or ban someone from a game server, banning them from ever playing there again. Obviously, the admin should then not accidently ban a player named "Mrs.Smith" when he meant "Mr.Smith"!

My solution (unless someone else can come up with something better) is to just not allow the command if there are multiple matches. If the admin searches for 'smith' and there are multiple names that are similar to 'smith' (maybe even 'sith' or similar) then I disregard that search and tell the admin he needs to try again with a more specific name.
(If all else fails he can always look up the ID of the player and use that, which should be foolproof as long as the admin doesn't make a mistake and picks the wrong ID..., but that is even more work it does not have preference).

But this brings further problems. The example I just gave might be good: suppose there's a player "Mr.Smith" and a player "Sith". If the admin searches for 'Smith' then there should be no question who he meant (Mr.Smith), but I am sure any fuzzy logic implementation would count Sith as a very close match...

Another thing is that my solution of only allowing the search if there is just a single match probably wouldn't work. I have never used fuzzy logic searching before, but I can imagine some names being marked as 'slightly similar' even when they are completely different ('smi' might match 'smith', but also 'ims' perhaps, in which case it would possibly match a whole new range of names), even though 'for humans' it is clear which result is meant.

Can anyone provide any thoughts on this matter? I am really unsure how I should approach this... I am assuming any fuzzy search would return the matches and rate them according to how similar they are to the search term. Perhaps I can choose some kind of cut-off value, where any matches that are less than 30&#37; similar (I've no idea just guessing here) are assumed not equal whereas higher ranked matches are assumed a possible match.

Any idea's?


EDIT
Perhaps this makes it easier (perhaps harder, I dunno), but I forgot to mention that the search term cannot contain any spaces. Player screen names can contain spaces though. I am thinking to just strip out the spaces of each name before starting the search, but perhaps there are better solutions in combination with fuzzy searching...