[CodeParrot] Near-deduplication with jaccard similarity
Author: liyongsea
Pull request: yes

# What does this PR do?

This PR address the code duplication issue describe in this thread
https://twitter.com/miltos1/status/1497126435261083649?s=20&t=v5-vwaEtXLrgZ_GuZHrPKQ

<!--
Congratulations! You've made it this far! You're not quite done yet though.

Once merged, your PR is going to appear in the release notes with the title you set, so make sure it's a great title that fully reflects the extent of your awesome contribution.

Then, please replace this with a description of the change and which issue is fixed (if applicable). Please also include relevant motivation and context. List any dependencies (if any) that are required for this change.

Once you're done, someone will review your PR shortly (see the section "Who can review?" below to tag some potential reviewers). They may suggest changes to make the code even better. If no one reviewed your PR after a week has passed, don't hesitate to post a new comment @-mentioning the same persons---sometimes notifications get lost.
-->

# run the code

```
from datasets import load_dataset
from minhash_deduplication import deduplicate_dataset
ds = load_dataset("lvwerra/codeparrot-clean", split="train")
ds_dedup, duplicate_clusters = deduplicate_dataset(ds)
``` 

The function runs in 2:30 (make_duplicate_clusters) + 1:30 (find_extremes) on a 8 cores VM
```
Orginal dataset size: 5361373
Duplicate cluster: 757944
Files in duplicate cluster: 2677040
Unique files in duplicate cluster: 911947
Filtered dataset size: 3596280
```

Comments:
_The documentation is not available anymore as the PR was closed or merged._

Hi @lvwerra I agree with you. I will do that. The overall code is running now, here are the next steps:

- [x] refactor the code to be used in preprocess.py and clean up
- [x] document statistics and performance data in the PR
- [x] use dataset.map to compute minhash

I will do the deduplication of the validation set in another PR probably.
~question, does dataset.map put the whole dataset in RAM? I imagine it is not a problem because preprocess.py is already doing so~

Hi @lvwerra there is one decision we need make, then the PR will be ready to review.
I mentioned before, we could use dataset.map to compute the minhash. However, there is two steps in the deduplication:
- compute minhash for each code file
- add into MinHashLSH (can not be parallelized)

In previous function, a queue is used while adding into minhash. It would be difficult to do the same using dataset.map. So the dataset.map [implementation](https://github.com/huggingface/transformers/pull/17054/files#diff-c6c3b9ed9e98c7b3b8603011208c2db7c0cf08facbf2a75ec8f56dfea0242040R119) will be almost twice slow (to be confirmed ...) 
~I might prefer the dataset.map solution, which makes the code easier to read~
Finally I choose the initial implementation, which reduce the computation time by half 

Here are some statistic and time performance data:

on the dataset lvwerra/codeparrot-clean
~Execution time 13h: Execution time: 2:30:00 for make_duplicate_clusters, 11:00:00 for find_cluster_extremes~

Orginal dataset size: 5361373                                                                        
Duplicate cluster: 757938          
Files in duplicate cluster: 2677039          
Unique files in duplicate cluster: 940857
Filtered dataset size: 3625191 

~I think the code is ready for review. If you need to generate a dataset, you can go ahead. I might still need more days to figure out how to do find_cluster_extremes better~

Please see the next message for update

multipro_find_extremes is done with multi processing ! This PR is ready for review
Execution time ~3h: Execution time: 2:30:00 for make_duplicate_clusters, 1:00:00 for multipro_find_extremes

Orginal dataset size: 5361373
Duplicate cluster: 757938
Files in duplicate cluster: 2677039
Unique files in duplicate cluster: 940857
Filtered dataset size: 3625191
@lvwerra when review, pay more attention to
- [Here](https://github.com/huggingface/transformers/pull/17054/files#diff-c6c3b9ed9e98c7b3b8603011208c2db7c0cf08facbf2a75ec8f56dfea0242040R140) I use a global parameter to be able to do multi pro in a efficient way


We are good to go, welcome your thought @lvwerra 
I will try to run some last test