How to check if a string exists in a very large list of strings

Questions / Help
,
1

Hello!
I have a list of 100 million strings, each string is up to 20 characters long.
I need to check if an arbitrary string (or a small list of strings) exists in this list.
How to do it quickly and efficiently?
Does it make sense to hash all strings and check hashes?

2

Either hash, but if the set of strings is known beforehand then you can use finite state transducers or tries. Alternatively you can try to find perfect hash function, but it can be hard and expensive. I think that in this case trie would be the easiest solution.

3 Likes
3

If you want to find a single string, then just using Enum.member?/2 or Kernel.in/2 with the large list might be totally sufficient.

Depending on your source of the list, though, there might be ways that are more efficient (eg. if from DB, ask the DB, if file from disk, stop loading of the file once the item is found, etc).

If though you have to query the list multiple times and have to load it into memory completely, it might make it faster to convert the heystack list to a MapSet first and query the mapset for membership of the needle.

4
  1. Partition the big list for speed. (for ex. by first 1 or 2 letters).
  2. Bloom filters (can have false positives): https://hex.pm/packages?search=bloom&sort=recent_downloads

Do you also need to find strings that are similar but not exactly equal?

2 Likes
5

Just wondering how you get a list of 100 million strings. What is the context?

1 Like
6

An addition to what I have said already.

If your list is known at compile time, you could create a multihead function from it using some metaprogramming.

This makes use of pattern matching, which again gets optimised into a prefix tree.

~w(a b c Foo Bar)
|> Enum.each(fn word ->
  def in_list?(unquote(word)), do: true
end)
def in_list?(_), do: false
7

If anyone wants a possibly outdated example of using fst in elixir, here I used BurntSushi/fst via rustler.

The API can be seen in the benchmark.

1 Like
8

I was writing something similar but with wider API.

1 Like
9

For a list this large, a suffix tree has a lot of advantages. I haven’t yet had time to implement it in Elixir, but it’s on my list, and I have been gathering info to work on it. Dan Gusfeld’s Algorithms on Strings, Trees, and Sequences describes the construction in detail, based on methods devised by Ukkonen. It’s a nontrivial thing to implement, but if this is going to be a recurring theme in your work it would be worth it. There are a number of implementations in other languages, but none yet in Elixir.

1 Like