Is there an efficient way to fontify matches of thousands of different strings in a buffer?

Question

I have a list of thousands of different strings made up of different numbers of words (e.g. names of specific people) that I would like to fontify in a buffer. Some applications I could use for something like this are highlighting names from a contact list, highlighting chemical names in a notebook, etc.

I know that technically one fontifies a pattern, but in this case the pattern is a literal string (from the long list) to match, so I call this fontifying a string.

For small lists of strings, I can do something like this:

(font-lock-add-keywords nil
 `((,(string-join (cl-loop for name in list-of-names
              collect
              (format "\\(%s\\)" name))
         "\\|") . font-lock-keyword-face)))

And this works fine. But this doesn't scale well for much larger lists of patterns. I get an error of Invalid regexp: "Regular expression too big" if I try to put several thousand patterns joined by OR's.

Is there another strategy to do something like this with fontification?

A partial solution that seems to work reasonably well for strings with two words separated by a space in them is that I use a search function in the font-lock rule. In the function I break the region from point to limit into bigrams, and then I check if each bigram (joined by a space) is in a hashtable of the strings to match, and if it is, I set some match data. This works for strings made of two words separated by a space, but doesn't work if there is more than one space (I could probably live with standardizing this though). The same approach works for single words, I just use a separate function for that. I could probably extend it to 3-grams for matches with 3 words. I am interested in other solutions if anyone can think of them.

Answer 1

I get an error of Invalid regexp: "Regular expression too big" if I try to put several thousand patterns joined by OR's.

regexp-opt exists for creating efficient regexps from a set of strings.

I've no idea whether that's actually going to cope with your input, mind; but if it manages to do so then you'll get a far more efficient pattern out of it.

---

The ways in which first and last names will be mixed and matched is still going to bloat things though (and probably a lot), so other food for thought on that...

You could divide the matching into first-name and remainder. Have a pattern for only the possible first names, and for each first name have a pattern for the possible full names beginning with that specific first name. When you get a match for a word which is someone's first name, pull up the other associated regexp and check whether you're looking at one of those.

Each of those regexps would be relatively concise, I think -- although you'll have plenty of duplication between each of the secondary regexps.

You could also have just two regexps, and search for "all possible first names" followed by "all possible remainders", and if you get a match for that you can check to see whether the matched text is actually one of your known names.