How to recognise a particular user in a long multi-user internet chat log?

Here is an online programming contest we are planning to have.

What could be possible approaches to solving the same?

From a random IRC (Internet Relay Chat) log, a small percentage of the user nicknames will be randomly deleted. The participant’s code must be able to fill in the missing user nicks. In other words, this event requires you to come up with an intelligent program that can figure out “who could have said what”.

It may be assumed that all communication will be in modern English, with or without punctuation.

For example -

Original Chat: ... <user1>: Hey! <user2>: Hello! Where are you from, user1? <user3>: Can anybody help me out with Gnome installation? <user1>: India. user3, do you have the X Windows System installed? <user2>: Cool. What is Gnome, user3? <user3>: I don’t know. How do I check? <user3>: Its a desktop environment, user2. <user2>: Oh yeah! Just googled. <user1>: Type “startx” on the command line. Login as root and type “apt-get install gnome”. <user3>: Thanks! <user5>: I’m root, obey me! <user2>: Huh?! <user3>: user2, you better start using Linux! ...

The following only will be given to the participant.

Chat log with some nicks deleted:

..

: Hey! : Hello! Where are you from, user1? : Can anybody help me out with Gnome installation? : India. user3, do you have t开发者_JAVA百科he X Windows System installed? : Cool. What is Gnome, user3? <%%%>: I don’t know. How do I check? <%%%>: Its a desktop environment, user2. : Oh yeah! Just googled. : Type “startx” on the command line. Login as root and type “apt-get install gnome”. : Thanks! <%%%>: I’m root, obey me! <%%%>: Huh?! : user2, you better start using Linux! ...

The participant’s code will have the task of replacing "<%%%>s" with the appropriate user nicks. In ambiguous cases, like the random comment by in the above example (which could have been said by any other user too!), the code should indicate the same.

Two things spring to my mind: authorship attribution and chat disentaglement. Neither are exactly what you describe, but they both come pretty close.

Authorship attribution is the problem of trying to find which of a known set of authors wrote a particular document. Classic authorship attribution is typically used on large sections of text (e.g. plays, novels, speeches) but people have been trying to do the same on shorter samples of text from internet sources. A good reference is probably anything written by Moshe Koppel with 'authorship' in the title, for example the recent paper Authorship Attribution in the Wild. The usual approach to this task involves using typical document classification approaches, that is using bag of words features and a machine learning classifier, on a set of what are usually thought of as stop words (e.g. as, of, the, etc.). The problem here is that all of this work is on documents and does not take into account the conversational nature of IRC data.

Chat disentanglement is the problem of identifying a number of coherent 'conversations' from chat data. This is quite a hard problem as you often need to use the context of conversation in order to know who is replying to who. I imagine this kind of approach would be important to this task as well. For example, if the anonymised message is part of a conversation then that limits the set of authors to the people in the conversation. I really only know about this from the paper Disentangling Chat by Elsner and Charniak. Their 'related work' section is a good overview of the field.

One possible solution would be to take the Naive Bayes Classifier 'spam filter' idea and see which words different nicks tend to use. Classify messages according to which user uses words 'most like' the ones sent from an unknown user. The downfall of this would be that if they were using new words you hadn't seen before (which is very likely), then you'd need to understand higher-level context information.