-4

Let's say I was to create a scraper. At some point I'll need to come up with algorithm of identifing whether or not a piece of a newly scraped text matches the one that's already in the DB. How would I check whether those 2 pieces are identical?

If I decided to use a hash to compare them, it wouldn't be reliable because a tiny difference, such as a whitespace or anything else would result in a different hash.

How else then?

12
  • 1
    You'll have to normalize the data--stripping away formatting code like HTML tags. Jun 29 at 2:26
  • 11
    I guess the real problem is that you are asking us what "almost identical" should be for a scraper. But that should be part of your requirements analysis, knowing what this scraper will be used for.
    – Doc Brown
    Jun 29 at 4:33
  • 1
    What you want is basically a plagiarism detector, and those things are hard to make.
    – Pieter B
    Jun 29 at 7:16
  • 2
    Do you have an algorithm that determines whether two texts are functionally identical? What differences are permissible? Whitespace changes? Typo correction? Change of wording for clarification? If you can't clearly say how to determine whether two strings are functionally identical how are you expecting an algorithm to do it for you? Jun 29 at 15:58
  • 1
    The edit did not clarify anything. What does "funtionally identical" for texts mean? No idea why such an unclear post was reopened.
    – Doc Brown
    Jun 29 at 16:06

3 Answers 3

2

The purpose of a hash would be to save resources. The chances of a collision using a hash with good distribution would be very small.

You would not be worried about someone having changed something insignificant. This is also unlikely and if it happened you just treat the page as new and you do some unnecessary work without knowing it and still be fine. For that reason I would not bother with cleaning too much. But you should be aware that dynamically created pages may include elements like counters or timestamps that make every page unique. This may well be your biggest problem.

You may also be worried about false positives: the hash is a match but the page has changed, you got a colliding hash. Again, using a good 64 bit hash would make this unlikely and you may want to ignore this. You would just miss one update in the worst case scenario. The chances of the site being unreachable at the time of the poll would be significantly higher. The web is not a perfect thing anyway.

1

It's unclear what you mean by "anything else" but whitespace is simple. Just use a regex e.g. \s+ and replace with something deterministic like a single space or some other character of your choosing. Then you can hash etc. "Anything else" might be a similar answer or completely different. No one can answer that until you clarify what you mean.

-1

How would I check whether those 2 pieces are identical?

Convert each character to a number. Subtract each number from the number of its corresponding character. If the result is ever not zero they ain’t equal. Works when the lengths are the same. Hint, if the length isn’t the same they ain’t equal. It’s called string comparison.

If I decided to use a hash to compare them, it wouldn't be reliable because a tiny difference, such as a whitespace or anything else would result in a different hash.

That’s not the problem with a hash. The problem with a hash is collisions that say they’re equal when they’re not. No matter how good the hash algorithm the pigeonhole principle says you can’t reduce the bits of an arbitrary length string to a fixed size integer without collisions. The best you can do is make them unlikely. If you can accept that risk then a hash is fine for this.

The advantage of a hash is that you won't have to store the old string in the DB. Just the hash.

But you have exactly the same "reliable" problem either way you do it. Both hash and string comparison require you to prep the string before hand. If that means trimming whitespace or making everything lower case or whatever "anything else" means, you have to do it before the hashing algorithm see's what you want to ignore.

5
  • That’s not the problem with a hash. - how can you know whether or not that's a problem for me? Jun 29 at 13:03
  • Convert each character to a number. Subtract each number from the number of its corresponding character. If the result is ever not zero they ain’t equal. - give me an examle please Jun 29 at 13:03
  • @NicholasE.Harding Because of how hashes work. Hashes keep you from having to store what you're comparing. They don't magically ignore "anything else". You have to transform the data so that "anything else" is gone before you hash. As for examples: in Java see String.compareTo(), in Python see unicode_compare_eq() Jun 29 at 14:00
  • I don't "have to". How do you know that that is what I want for this task? Jun 29 at 14:55
  • Because you told me. The way you get a hash (or a comparison) to ignore "whitespace or anything else" is by keeping the hashing algorithm from seeing it. First remove (or normalize) what you want the hash to ignore. Jun 29 at 17:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.