2
$\begingroup$

I have a file with about 25000 rows. I want to find sentences that are near duplicates (sentences which have difference of just one or two words/symbols or ones which are just paraphrasing of another).

To accomplish this, I'm using a very naive solution by comparing every row to every other row using the model bert-base-cased-finetuned-mrpc. Now the thing is that this is obviously very inefficient as it comparing for $25000^2$ pairs, and the task won't complete on my device.

Is there a way I can first find sentences which are candidates for being near duplicate, and then put the pairs into the model, or is there another approach which is efficient? I'm new to this, so any suggestions are appreciated.

$\endgroup$
4
  • 1
    $\begingroup$ If you're solely looking for sentences that are a few words or symbols different, then en.wikipedia.org/wiki/Levenshtein_distance is a natural choice. Paraphrasing would require a more complex solution, though. $\endgroup$
    – Sycorax
    Commented Oct 1, 2021 at 15:32
  • $\begingroup$ paraphrasing isnt necessary for me right now so i can start with Levenshtein distance what do you think is the most efficient implementation because currently my method will take 25000^2 comparisons $\endgroup$ Commented Oct 1, 2021 at 18:06
  • $\begingroup$ also do you think that this question is more suited to the ai stackexchang or is it fine $\endgroup$ Commented Oct 1, 2021 at 18:28
  • 1
    $\begingroup$ It’s fine here. $\endgroup$
    – Sycorax
    Commented Oct 1, 2021 at 18:56

1 Answer 1

2
$\begingroup$

When I’ve faced the problem of comparing many strings in the past, I’ve simplified it by only comparing texts where the first $k$ characters match. Even if $k$ is 1 or 2, you can dramatically reduce the number of comparisons you need make. This might not be appropriate in every setting, but it worked for me.

Using Levenshtein distance is great for detecting a small number of different symbols between texts, but obviously fails at finding paraphrasing.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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