Поиск большого списка слов в другом большом списке

Question

У меня есть отсортированный список из 1000 000 строк с максимальной длиной 256 с именами белков. Каждая строка имеет связанный идентификатор. У меня есть еще один несортированный список из 4 000 000 000 строк с максимальной длиной 256 слов из слов, а каждое слово имеет идентификатор.

Я хочу найти все совпадения между списком имен белков и списком слов из статей. Какой алгоритм я должен использовать? Должен ли я использовать некоторый API предварительной сборки?

Было бы хорошо, если бы алгоритм работал на обычном ПК без специального оборудования.

Оценки времени, требуемые алгоритмом, были бы хороши, но не обязательно.

Answer 1

4 миллиарда строк - это много строк для поиска.

Возможно, вы сможете разместить всю структуру данных в хэш-памяти памяти для быстрого поиска, но, скорее всего, вы захотите сохранить весь список на более просторном (но медленном) диске, и в этом случае отсортированный список будет предоставлять сам по себе относительно эффективный алгоритм бинарного поиска.

Если бинарный поиск или такая функция была вызвана find_string_in_articles(), а затем псевдокод:

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

Answer 2

Похоже, что вы, вероятно, должны использовать двоичное дерево.

Answer 3

Вы можете отсортировать их, а затем сделать «», который слиянием не будет на самом деле сливаться, но найти вы дублирует/перекрывается. Википедия имеет хорошие ссылки на это.

Сортировка этого объема данных, вероятно, требует большего объема памяти, чем у вас есть. Я не знаю, справится ли это с Unix-сортировкой (доступной на Windows/Mac тоже), но любая достойная база данных SQL может это сделать.

Другая возможность заключается в использовании дерева оснований на ваших именах белков (те, которые начинаются с A, идут в корзину A, B в bin B и т. Д.). Затем просто зациклируйте на 4 gazillion слов и найдите перекрытия (вы, вероятно, должны внедрить более одного глубокого радиального биннинга, чтобы отбросить больше белков за раз).

Answer 4

Я бы сделал это одним из 2 способов.

1. Вставьте его в SQL базу данных и вытащить нужные вам данные (медленнее, но проще)
2. Сортировка списка, а затем делать двоичный поиск, чтобы найти то, что вам нужно (быстро, но сложно)

Answer 5

Это по существу реляционное соединение. Предполагая, что вы не уже отсортированы статью слова, ваш основной алгоритм должен быть:

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

proteins.find() является трудным, и вам придется поэкспериментировать, чтобы получить максимальную производительность, такого рода проблем где эффекты кеша начинают вступать в игру. Сначала я попытался бы с помощью сортировки radix, это довольно просто и, скорее всего, достаточно быстро, но бинарный поиск и хеширование также являются альтернативами.