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

Question

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

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

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

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

Answer 1

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

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

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

Answer 2

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 3

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

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

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

Answer 4

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

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

Answer 5

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