Searching a large list of words in another large list

Question

I have a sorted list of 1,000,000 strings with a maximum length of 256 with protein names. Every string has an associated ID. I have another unsorted list of 4,000,000,000 strings with a maximum length of 256 with words out of articles and every word has an ID.

I want to find all matches between the list of protein names and the list of words of the articles. Which algorithm should I use? Should I use some prebuild API?

It would be good if the algorithm runs on a normal PC without special hardware.

Estimates of time that the algorithm requires would be nice but not obligatory.

Answer 1

Sounds like something you should use a binary-tree for maybe.

Answer 2

4 billion strings is a lot of strings to search.

You may be able to fit the entire data structure into a memory hash for fast lookup, but more likely you'd want to store the entire list on more spacious (but slower) disk in which case a sorted list would lend itself to the relatively efficient binary search algorithm.

If your binary search or such function was called find_string_in_articles(), then psuedocode:

foreach $protein_name ( @protein_names ) {
    if ( $article_id = find_string_in_articles( $protein_name ) ) {
        print( "$protein_name matches $article_id\n" );
    }
}

Answer 3

You could sort them and then do "mergesort" which would not actually merge but find you duplicates/overlaps. Wikipedia has good references on that.

Sorting that amount of data probably requires more memory than you have accessible. I don't know if unix sort (available on Windows/Mac too) can handle that, but any decent SQL database can do that.

Another possibility is to use a radix tree on your protein names (those starting with A go to bin A, B to bin B etc.). Then just loop over the 4 gazillion of words and locate overlaps (you probably must implement more than one deep radix binning to discard more proteins at a time).

Answer 4

I would go about this in 1 of 2 ways.

1. Insert it into a sql database and pull out the data you need (slower, but easier)
2. Sort the list, then do binary searches to find what you need (fast, but tricky)

Answer 5

This is essentially a relational join. Assuming you don't have already sorted article words, your basic algorithm should be:

for word in article_words:
    if (proteins.find(word)):
        found_match(word)

proteins.find() is the difficult part, and you will have to experiment to get the best performance, this sort of problem is where cache effects start to come into play. I would first try with a radix sort, it's pretty simple and is likely fast enough, but binary searching and hashing are also alternatives.