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

[kaliman79912]

The complexity of your algorithm may depend on how easy your logic will get a hit. But the only recomendation I am giving you right now is that try to put it in a way that when the Admin is typing the name it gets a list of all the hits and he needs only to select from a list instead of relying only on what he types.

[NickThissen]

The complexity of your algorithm may depend on how easy your logic will get a hit. But the only recomendation I am giving you right now is that try to put it in a way that when the Admin is typing the name it gets a list of all the hits and he needs only to select from a list instead of relying only on what he types.

That's not possible; the admin is typing this in the ingame chat, there is no way for me to display a list of any kind there.

[BrainWart]

I did this once before.. but in Lua.

-Lua

function GetPlayersWith(PartialName)
	local SelectedPlayers = {}
	for i, a in pairs(game.Players:GetChildren()) do
		if string.lower(string.sub(a.Name,1,string.len(PartialName))) == string.lower(PartialName) then
			SelectedPlayers[#SelectedPlayers + 1] = a.Name
		end
	end
	return SelectedPlayers
end

-VB

    Function FindFullNameWithPartialName(ByVal PartialName As String, ByVal Players() As String) As String
        Dim Name As String = ""
        For Each Player As String In Players
            If Player.Substring(0, PartialName.Length).ToLower = PartialName.ToLower Then
                If Name = "" Then
                    Name = Player
                Else
                    Return "Multiple names"
                End If
            End If
            If Player.ToLower = PartialName.ToLower Then
                Return Player
            End If
        Next
        Return Name
    End Function

[NickThissen]

Looks like you are just comparing the first part of the name, so you are basically doing

If Player.StartsWith(PartialName) Then ...

That's not really ideal since names often start with strange symbols and the main part of the name (easy to read and type) is often somewhere in the middle.
In that case I could use Contains instead, but even then I like to give the admin the opportunity to make a few small mistakes (not typing the "." in "Mr.Smith" for example), which would not work using any of the built in string comparison functions.

For now I have settled with wildcards so that the admin can use * to represent any character, but it would be much better if the * is 'implied', so to speak....

[BrainWart]

Well then use String.Contains()

Function FuzzySearch(ByVal PartialName As String, ByVal PlayerList() As String) As String
        Dim Name As String = ""
        For Each Player As String In PlayerList
            If Player.ToLower().Contains(PartialName.ToLower) Then
                If Name = "" Then
                    Name = Player
                Else
                    If Player.ToLower = PartialName.ToLower Then
                        Return Player
                    Else
                        Return "Multiple Matches"
                    End If
                End If
            End If
        Next
        Return Name
    End Function

[NickThissen]

In that case I could use Contains instead, but even then I like to give the admin the opportunity to make a few small mistakes (not typing the "." in "Mr.Smith" for example), which would not work using any of the built in string comparison functions.

[BrainWart]

Run a loop for all of the characters the and give it like 3 strikes to give up... Give me a while and I'll see If I can do something...

EDIT:

Hows this?

    Function FuzzySearch(ByVal PartialName As String, ByVal PlayerList() As String, Optional ByVal Mistakes As Integer = 3) As String
        Dim Name As String = ""
        For Each Player As String In PlayerList
            For ia As Integer = 0 To Player.Length - 1
                Mistakes = 3
                For ib As Integer = 0 To PartialName.Length - 1
                    If ia + ib > Player.Length - 1 Then
                        Mistakes = 0
                        Exit For
                    End If
                    If Not (Char.ToLower(Player.Chars(ia + ib)) = Char.ToLower(PartialName.Chars(ib))) Then
                        Mistakes -= 1
                    End If
                    If Mistakes = 0 Then
                        Exit For
                    End If
                Next
                If Mistakes > 0 Then
                    If Name = "" Then
                        Name = Player
                    Else
                        Return "Multiple Matches"
                    End If
                End If
            Next
        Next
        Return Name
    End Function

[NickThissen]

Don't have much time to check it now, but I am assuming it simply checks each character in the two strings at a time, and ticks off a mistake if they are not equal.

Take my example: the real player name is "Mr.Smith". Admin types "mrsmith". In your scenario (if I'm not mistaken), the first two characters would pass, but the third would fail. Ok, one mistake, no biggy. But then you continue with the rest and you will be comparing "S" with "m", "m" with "i", "i" with "t", etc. In other words, if the admin doesn't type one character (or types one too many) then the character checking is 'out of sync' and keeps checking the wrong characters, indicating like 6 mistakes when there was just one.

[JayJayson]

Hiya, here's an idea for you to consider.

This function will return the usernames that contain the letters typed into the textbox. It will search for the letters in the order they appear e.g.

If you type: "lan" it will return the name "Alan" but not "Nala".

It will search for the next letter based on the position of the last so it will be able to look past other chars e.g.

If you type: "JJ" it will return the name "John Johnson".

The search is case insensitive, although you can easily change that if you wish. Also there is no need to worry about the space in the names, the code will return the results regardless.

Do you have any control over the Textbox that the name will be typed into? If so rather than waiting for the search to narrow down to 1 result before showing it, you could cycle the results within the textbox by simply pressing the up and down arrows on the keyboard.

Anyway, heres the function (Just add a textbox to the form to test it):

Public Class Form1
 
    Dim Names() As String = {"Joe Bloggs", "Greg Gregson", "Bob Bobson", "John Johnson", "Hansolo123", "Gregory94", "Mr.Smith"}
 
    Private Sub TextBox1_TextChanged(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles TextBox1.TextChanged
        'If the texbox is blank, do nothing
        If TextBox1.Text = Nothing Then Exit Sub
 
        'Get the list of names that contain the lookup string
        Dim GetNames As List(Of String) = PartialMatch(TextBox1.Text.ToLower)
        'If the resutl has been narrowed down to 1 match then show it in the textbox
        If GetNames.Count = 1 Then TextBox1.Text = GetNames(0)
    End Sub
 
    Private Function PartialMatch(ByVal Lookup As String) As List(Of String)
        'The list of names that contain the lookup string
        Dim Results As New List(Of String)
 
        'Loop each username
        For Each Name As String In Names
            'Check the username for the occurence of the first letter in the lookup string. (If it's not in there we can skip this user)
            If Name.ToLower.Contains(Lookup.Chars(0)) Then
                'Let's search for each char from the position of the previous lookup char (start at 0)
                Dim inStrIndex As Integer = 0
                'We also want to be able to identify which usernames make it to the end of the next For, Loop.
                Dim isResult As Boolean = True
 
                'Now for the loop. We want to check that every char in the lookup string is found in the username.
                'We want to make sure that the letters occur in order as well so we don't end up with "smi" resulting in "sim" for example.
                'We can use IndexOf and the inStrIndex to control that for us
                For Each c As Char In Lookup
                    'Search for the first index of each char, starting at the position of the previously found char
                    Dim NextIndex As Integer = Name.ToLower.IndexOf(c, inStrIndex)
 
                    'If no char is found
                    If NextIndex = -1 Then
                        'Indicate that this is not a match and stop the loop
                        isResult = False
                        Exit For
                    End If
 
                    'If the last char we matched is at the end of the string, exit for the loop
                    If inStrIndex >= Name.Length Then Exit For
                    'Otherwise update the index we are going to search from on the next pass
                    inStrIndex = NextIndex + 1
                Next c
                'And here we can check whether or not we got a successful match. If so, add it to the Results
                If isResult = True Then Results.Add(Name)
            End If
        Next Name
 
        'Pass the results back to the calling sub
        Return Results
    End Function
 
End Class

Hope this helps

P.s. How did you get on with the Black Ops, Weapons/Attachments function?

[NickThissen]

Thanks, will check it out.

The weapons thing worked almost fine, had to make a few adjustments (my own fault, I was unaware of some edge cases) and since then I have tried it on a few hundred log file lines and it seems to work fine.

[nbrege]

Maybe you can use this:

http://www.vbforums.com/showthread.php?t=540094

[wild_bill]

Maybe you can use this:

http://www.vbforums.com/showthread.php?t=540094

I was just going to suggest that

You could also save the list of possible matches, and give the admin the option of chossing one.

[NickThissen]

I was just going to suggest that

You could also save the list of possible matches, and give the admin the option of chossing one.

Looks good, but the problem with approaches like that (I think) is that nearly all strings will turn out as a 'slight match'. Then I would have to define a cut-off value, for example 60%, such that any matches that match under 60% are discarded, and that there should then remain just one match above 60%. The problem is that this cut-off value would be hard to determine, there are so many game servers and so many different player names, there is no way testing any cut-off value on a few servers would work in all cases.

Also, while approaches like 'showing the list of matching names' are completely logical normally, they are impossible in this case. I am not modding the game in any way, I am merely parsing the log files (which show what a player says in the chat) and sending a message back to the server. So, the only way for me to show something to the admin is by sending him a (series of) message(s). The ingame chat however is not equipped for a lot of messages, if you send 5 messages at once only the last 4 will show for example, the rest is already gone by that point.


I think my best bet at this point is to implement wildcard searching and leave it at that. With wildcards there's a much smaller chance you get multiple matches, and if you do you probably didn't use the wildcard well. When I now get multiple matches I just tell the admin to please try again with a more specific name.