2

I have two data sets. The first data set has approx. 50.000 movie and song titles and the second one have 20.000 blacklist strings. I am looking for the best algorithm to detect movie/song title which contains blacklisted word(s).

Example: Dataset #1

The Lord Of The Rings
E.T.
Star Wars
...
(50k items)

Blacklist Data set

Lord
Home Alone
Matrix
ar
...
(20k items)

Items in these data sets may be a character or a few words. String search algorithms like Boyer-Moore is not helping me with this since I have more than 1 needle to search in the haystack. I (probably) need to find an algorithm to find all combinations efficiently and later make a string search (regex maybe?) for each combination.

  • Well, after seeing many algorithm questions/discussions on softwareengineering.stackexchange.com , I thought it's in the scope of this website and decided to ask this question here. But got a downvote after a few seconds of my question submission :-) – Eray Feb 19 at 19:36
  • Is the blacklist composed of words (in your example it's always full words) ? Or can it be partial strings like ord or me Al? And is it case sensitive or not ? – Christophe Feb 19 at 19:40
  • Yes, it can be. @Christophe thanks for your comment, I will update the question. – Eray Feb 19 at 19:41
  • 1
    There are several such algorithms, e.g. en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm, the main gimmick is that you spend a lot of time preprocessing the dataset. Which for you is great because your dataset is fixed so you can just reuse the preprocessing, updating it every once in a while. – Countingstuff Feb 19 at 22:46
  • 1
    Do you have any evidence that simply cramming those pattern into a disjunctive pattern (or several) and using the standard regex engine of your environment is not efficient enough? – Kilian Foth Feb 20 at 7:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.