Simple Hash algorithm to detect duplicate content

**rossum** · Feb 27 '08, 10:15 PM

Re: Simple Hash algorithm to detect duplicate content

On Wed, 27 Feb 2008 13:33:26 -0800 (PST), DotNetNewbie
<snowman908070@ 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.GetHash Code();
hash = multiplier * hash + EmployeeID;
hash = multiplier * hash + DepartmentID;
return hash;
}

This relies on Messsage.GetHas hCode() 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?

**=?ISO-8859-1?Q?Arne_Vajh=F8j?=** · Feb 27 '08, 11:05 PM

Re: Simple Hash algorithm to detect duplicate content

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+Employ eeID+Department ID).GetHashCode ();
}

only has 2^32 possible values.

string DoHash(string Message, int EmployeeID, int DepartmentID)
{
MD5 md5 = new MD5CryptoServic eProvider();
return
Convert.ToBase6 4String(md5.Com puteHash(Encodi ng.UTF8.GetByte s(Message+Emplo yeeID+Departmen tID)));
}

has 2^128 possible values.

Arne

**=?Utf-8?B?UGV0ZXIgQnJvbWJlcmcgW0MjIE1WUF0=?=** · Feb 28 '08, 03:25 AM

RE: Simple Hash algorithm to detect duplicate content

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

"DotNetNewb ie" 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?
>

**DotNetNewbie** · Feb 28 '08, 06:45 PM

Re: Simple Hash algorithm to detect duplicate content

On Feb 27, 10:16 pm, Peter Bromberg [C# MVP]
<pbromb...@yaho o.NoSpamMaam.co mwrote:

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
>
"DotNetNewb ie" 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.

**DotNetNewbie** · Feb 28 '08, 07:15 PM

Re: Simple Hash algorithm to detect duplicate content

On Feb 27, 6:03 pm, Arne Vajhøj <a...@vajhoej.d kwrote:

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+Employ eeID+Department ID).GetHashCode ();
>
}
>
only has 2^32 possible values.
>
string DoHash(string Message, int EmployeeID, int DepartmentID)
{
MD5 md5 = new MD5CryptoServic eProvider();
return
Convert.ToBase6 4String(md5.Com puteHash(Encodi ng.UTF8.GetByte s(Message+Emplo yeeID+Departmen tID)));
>
}
>
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?

**=?ISO-8859-1?Q?Arne_Vajh=F8j?=** · Feb 29 '08, 12:05 AM

Re: Simple Hash algorithm to detect duplicate content

DotNetNewbie wrote:

>string DoHash(string Message, int EmployeeID, int DepartmentID)
>{
> MD5 md5 = new MD5CryptoServic eProvider();
> return
>Convert.ToBase 64String(md5.Co mputeHash(Encod ing.UTF8.GetByt es(Message+Empl oyeeID+Departme ntID)));
>>
>}
>>
>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

**=?ISO-8859-1?Q?Arne_Vajh=F8j?=** · Mar 3 '08, 04:15 AM

Re: Simple Hash algorithm to detect duplicate content

DotNetNewbie wrote:

On Feb 29, 2:38 am, Jon Skeet [C# MVP] <sk...@pobox.co mwrote:

>Christopher Van Kirk <chris.vank...@ fdcjapan.comwro te:

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

**=?ISO-8859-1?Q?Arne_Vajh=F8j?=** · Mar 3 '08, 04:15 AM

Re: Simple Hash algorithm to detect duplicate content

Jon Skeet [C# MVP] wrote:

Christopher Van Kirk <chris.vankirk@ fdcjapan.comwro te:

>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

**Christopher Van Kirk** · Mar 7 '08, 03:35 PM

Re: Simple Hash algorithm to detect duplicate content

On Mon, 3 Mar 2008 07:44:48 -0000, Jon Skeet [C# MVP]
<skeet@pobox.co mwrote:

>Arne Vajhoj <arne@vajhoej.d kwrote:

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

Simple Hash algorithm to detect duplicate content

Simple Hash algorithm to detect duplicate content

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment