Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
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.
That’s not the problem with a hash. - how can you know whether or not that's a problem for me?
Jun 29, 2022 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, 2022 at 13:03