By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,214 Members | 1,971 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,214 IT Pros & Developers. It's quick & easy.

Simple Hash algorithm to detect duplicate content

P: n/a
Hello,

I need a simple hash algorithm that will detect duplicate content in
my application.

I want to hash not just the content, but a few other parameters also
like EmployeeID and DepartmentID.

So something like:

int hash = DoHash(string Message, int EmployeeID, int DepartmentID);
Now the hash has to be unique with unique inputs i.e. can't duplicate
the hash value if the inputs are the same.

Ideas?
Feb 27 '08 #1
Share this Question
Share on Google+
9 Replies


P: n/a
On Wed, 27 Feb 2008 13:33:26 -0800 (PST), DotNetNewbie
<sn***********@yahoo.comwrote:
>Hello,

I need a simple hash algorithm that will detect duplicate content in
my application.

I want to hash not just the content, but a few other parameters also
like EmployeeID and DepartmentID.

So something like:

int hash = DoHash(string Message, int EmployeeID, int DepartmentID);
Now the hash has to be unique with unique inputs i.e. can't duplicate
the hash value if the inputs are the same.
Probably not possible with a reasonable sized hash. If the size of
the hash is limited, and thare are more than that possible inputs then
there must be some collisions. How many possible values are there for
the Message string for example?

However it is possible to do something with a reasonably low
probability of a collision, something along the lines of:

int DoHash(string Message, int EmployeeID, int DepartmentID) {
const int multiplier = 29;
const int startValue = 37;
int hash = startValue;
hash = multiplier * hash + Message.GetHashCode();
hash = multiplier * hash + EmployeeID;
hash = multiplier * hash + DepartmentID;
return hash;
}

This relies on Messsage.GetHashCode() returning a suitable value.
Depending on your exact requirement you may need to put in your own
function there.

Remember that collisions are possible, though they should be rare. If
you get matching hash values then you must do a full check for
equality.

rossum
>
Ideas?
Feb 27 '08 #2

P: n/a
DotNetNewbie wrote:
I need a simple hash algorithm that will detect duplicate content in
my application.

I want to hash not just the content, but a few other parameters also
like EmployeeID and DepartmentID.

So something like:

int hash = DoHash(string Message, int EmployeeID, int DepartmentID);

Now the hash has to be unique with unique inputs i.e. can't duplicate
the hash value if the inputs are the same.
A hash that has to be unique for all input will need to have the same
size as the input meaning that it is useless.

It is really a trade off between risk of collisions with size and
computational effort.

int DoHash(string Message, int EmployeeID, int DepartmentID)
{
return (Message+EmployeeID+DepartmentID).GetHashCode();
}

only has 2^32 possible values.

string DoHash(string Message, int EmployeeID, int DepartmentID)
{
MD5 md5 = new MD5CryptoServiceProvider();
return
Convert.ToBase64String(md5.ComputeHash(Encoding.UT F8.GetBytes(Message+EmployeeID+DepartmentID)));
}

has 2^128 possible values.

Arne
Feb 27 '08 #3

P: n/a
I am not sure that using a hash computation is the best way to detect
"duplicate content". Are you storing your content in a database? You really
haven't specified much detail. Perhaps you should be looking into a more
robust computation such as CRC32.
-- Peter
Site: http://www.eggheadcafe.com
UnBlog: http://petesbloggerama.blogspot.com
Short Urls & more: http://ittyurl.net
"DotNetNewbie" wrote:
Hello,

I need a simple hash algorithm that will detect duplicate content in
my application.

I want to hash not just the content, but a few other parameters also
like EmployeeID and DepartmentID.

So something like:

int hash = DoHash(string Message, int EmployeeID, int DepartmentID);
Now the hash has to be unique with unique inputs i.e. can't duplicate
the hash value if the inputs are the same.

Ideas?
Feb 28 '08 #4

P: n/a
On Feb 27, 10:16 pm, Peter Bromberg [C# MVP]
<pbromb...@yahoo.NoSpamMaam.comwrote:
I am not sure that using a hash computation is the best way to detect
"duplicate content". Are you storing your content in a database? You really
haven't specified much detail. Perhaps you should be looking into a more
robust computation such as CRC32.
-- Peter
Site:http://www.eggheadcafe.com
UnBlog:http://petesbloggerama.blogspot.com
Short Urls & more:http://ittyurl.net

"DotNetNewbie" wrote:
Hello,
I need a simple hash algorithm that will detect duplicate content in
my application.
I want to hash not just the content, but a few other parameters also
like EmployeeID and DepartmentID.
So something like:
int hash = DoHash(string Message, int EmployeeID, int DepartmentID);
Now the hash has to be unique with unique inputs i.e. can't duplicate
the hash value if the inputs are the same.
Ideas?
Peter,

Yes the content is stored in the database, before anyone inserts new
content I need to check if the same user has posted the same content
before, if he has, then don't insert it again.

Same content means: same employee ID, same departmentID and same
Message.

Meaning that the user can insert the same message text, but it has to
be in a different departmentID.
Feb 28 '08 #5

P: n/a
On Feb 27, 6:03 pm, Arne Vajhøj <a...@vajhoej.dkwrote:
DotNetNewbie wrote:
I need a simple hash algorithm that will detect duplicate content in
my application.
I want to hash not just the content, but a few other parameters also
like EmployeeID and DepartmentID.
So something like:
int hash = DoHash(string Message, int EmployeeID, int DepartmentID);
Now the hash has to be unique with unique inputs i.e. can't duplicate
the hash value if the inputs are the same.

A hash that has to be unique for all input will need to have the same
size as the input meaning that it is useless.

It is really a trade off between risk of collisions with size and
computational effort.

int DoHash(string Message, int EmployeeID, int DepartmentID)
{
return (Message+EmployeeID+DepartmentID).GetHashCode();

}

only has 2^32 possible values.

string DoHash(string Message, int EmployeeID, int DepartmentID)
{
MD5 md5 = new MD5CryptoServiceProvider();
return
Convert.ToBase64String(md5.ComputeHash(Encoding.UT F8.GetBytes(Message+EmployeeID+DepartmentID)));

}

has 2^128 possible values.

Arne
Arne, that looks like it is good for me (the string version).
Is that always going to be 32 characters in length?
Feb 28 '08 #6

P: n/a
DotNetNewbie wrote:
>string DoHash(string Message, int EmployeeID, int DepartmentID)
{
MD5 md5 = new MD5CryptoServiceProvider();
return
Convert.ToBase64String(md5.ComputeHash(Encoding.U TF8.GetBytes(Message+EmployeeID+DepartmentID)));

}

has 2^128 possible values.

Arne, that looks like it is good for me (the string version).
Is that always going to be 32 characters in length?
Yes.

Arne
Feb 29 '08 #7

P: n/a
DotNetNewbie wrote:
On Feb 29, 2:38 am, Jon Skeet [C# MVP] <sk...@pobox.comwrote:
>Christopher Van Kirk <chris.vank...@fdcjapan.comwrote:
>>I'm not a fan of this approach. The message column could be quite
large, and may affect the performance of such an index. Seems like it
would be better to compute a hash of some kind of the message, store
the hashed value in the database, and index on that along with the
other two key fields.
But that's exactly what an indexed unique constraint would do, but in a
more transparent fashion.

I've only ever had to manually store a hash in a database once, and
that was to effectively hash an unknown-until-execution-time number of
Guids when populating a set of sets.

Databases know how to index text columns. I think it's best to let them
do their job.

My message column is NTEXT(MAX), and it is going to have articles in
it.
I'll look into this approach....
You mean NTEXT *or* NVARCHAR(MAX) ?

Well - neither can be indexed by SQLServer ...

Arne
Mar 3 '08 #8

P: n/a
Jon Skeet [C# MVP] wrote:
Christopher Van Kirk <ch***********@fdcjapan.comwrote:
>I'm not a fan of this approach. The message column could be quite
large, and may affect the performance of such an index. Seems like it
would be better to compute a hash of some kind of the message, store
the hashed value in the database, and index on that along with the
other two key fields.

But that's exactly what an indexed unique constraint would do, but in a
more transparent fashion.

I've only ever had to manually store a hash in a database once, and
that was to effectively hash an unknown-until-execution-time number of
Guids when populating a set of sets.

Databases know how to index text columns. I think it's best to let them
do their job.
SQLServer does not.

To quote from BOL:

#Columns that are of the large object (LOB) data types ntext, text,
#varchar(max), nvarchar(max), varbinary(max), xml, or image cannot be
#specified as key columns for an index.

Arne
Mar 3 '08 #9

P: n/a
On Mon, 3 Mar 2008 07:44:48 -0000, Jon Skeet [C# MVP]
<sk***@pobox.comwrote:
>Arne Vajhoj <ar**@vajhoej.dkwrote:
Databases know how to index text columns. I think it's best to let them
do their job.

SQLServer does not.

To quote from BOL:

#Columns that are of the large object (LOB) data types ntext, text,
#varchar(max), nvarchar(max), varbinary(max), xml, or image cannot be
#specified as key columns for an index.

That's a pity - and it makes life a bit awkward.

The OP could use a hash and then fetch all values which have the same
hash, then performing the comparison.
Indeed. If you "scroll up" you'll see that this is exactly what I
suggested.

--
Posted via a free Usenet account from http://www.teranews.com

Mar 7 '08 #10

This discussion thread is closed

Replies have been disabled for this discussion.