Быстрый поиск строки с использованием побитовых операторов

Question

Какой самый быстрый (параллельный?) Способ найти подстроку в очень длинной строке с помощью побитовых операторов?

Например, найти все позиции последовательности "GCAGCTGAAAACA" в геноме человека http://hgdownload.cse.ucsc.edu/goldenPath/hg18/bigZips/hg18.2bit(770 МБ)

* алфавит состоит из 4 символов («G», «C», T, «A»), представленных с использованием 2 битов: «G»: 00, «A»: 01, «T»': 10,' C ': 11

* можно предположить, что строка запроса (более короткая) имеет фиксированную длину, например, 127 символов

* по быстрому, я имею в виду, не включая предварительно-обработка / индексирование времени

* файл будет загружен в память после предварительной обработки, в основном будут миллиарды коротких строк, которые нужно искать в большей строке, все в памяти.

* по битам, потому что я ищу самый простой и быстрый способ поиска битовой комбинации в большом битовом массиве и как можно ближе к кремнию.

* KMP не будет работатьну а алфавит маленький

* C-код, машинный код x86 был бы интересен.

InpuОписание формата t (.2 бита): http://jcomeau.freeshell.org/www/genome/2bitformat.html

Связано:

Самый быстрый способ поиска битовой комбинации в потоке битов

Алгоритм помощи!Быстрый алгоритм поиска строки с партнером

http://www.arstdesign.com/articles/fastsearch.html

http://en.wikipedia.org/wiki/Bitap_algorithm

Answer 1

Если вы просто просматриваете файл, вы в значительной степени гарантированно будете привязаны к io. Использование большого буфера (~ 16 КБ) и strstr() должно быть всем, что вам нужно. Если файл закодирован в ascii, ищите только "gcagctgaaaaca". Если это действительно закодировано в битах; просто переставьте возможные принятые строки (должно быть ~ 8; обрежьте первый байт) и используйте memmem() плюс небольшую проверку перекрывающихся битов.

Здесь я отмечу, что glibc strstr и memmem уже используют Кнут-Моррис-Пратт для поиска по линейному времени, поэтому протестируйте эту производительность. Это может вас удивить.

Answer 2

Если вы сначала кодируете / сжимаете строку ДНК методом кодирования без потерь (например, Хаффман, экспоненциальный Голумб и т. Д.), То вы получаете ранговую таблицу вероятностей («дерево кодирования») для токенов ДНК с различными комбинациями нуклеотидов (например,, A, AA, CA и т. Д.).

Это означает, что когда вы сжимаете свою ДНК:

1. Вы, вероятно, будете использовать меньше битов для хранения GCAGCTGAAAACA и других подпоследовательностей, чем "незакодированный" подходвсегда использовать два бита на базу.
2. Вы можете пройтись по дереву кодирования или таблице, чтобы построить закодированную строку поиска, которая обычно будет короче, чем строка без кодирования.
3. Вы можете применитьто же семейство точных алгоритмов поиска (например, Бойера-Мура), чтобы найти эту более короткую закодированную строку поиска.

Что касается параллельного подхода, разделите закодированную целевую строку на N кусков и запустите поискалгоритм на каждом фрагменте, используя сокращенную, закодированную строку поиска.Отслеживая смещения битов каждого блока, вы сможете генерировать совпадающие позиции.

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

Answer 3

Boyer-More - это метод, используемый для поиска подстрок в простых строках. Основная идея заключается в том, что если ваша подстрока имеет длину, скажем, 10 символов, вы можете искать символ в позиции 9 в строке для поиска. Если этот символ не является частью вашей строки поиска, вы можете просто начать поиск после этого символа. (Если этот символ действительно находится в вашей строке, алгоритм Бойера-Мора использует справочную таблицу, чтобы пропустить оптимальное количество символов вперед.)

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

Answer 4

Хорошо, учитывая ваши параметры, проблема не так сложна, просто не та, к которой вы подходите, как традиционная проблема поиска строк.Это больше напоминает проблему объединения таблиц базы данных, когда таблицы намного больше, чем RAM.

• выберите хорошую скользящую хеш-функцию, известную как бужаш.Если у вас есть миллиарды строк, вы ищете хеш с 64-битными значениями.

• создайте хеш-таблицу на основе каждой 127-элементной строки поиска.Таблицу в памяти нужно хранить только (хэш, идентификатор строки), а не целые строки.

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

• перечитайте целевую строку и поток пары, загрузив строки поиска какнеобходимо сравнивать их с целью при каждом смещении.

Я предполагаю, что загрузка всех строк паттернов в память одновременно является запретительной.Существуют способы сегментирования хеш-таблицы в нечто большее, чем ОЗУ, но не традиционный хэш-файл с произвольным доступом;если вам интересно, ищите «гибридный хеш» и «льготный хеш», которые более распространены в мире баз данных.

Я не знаю, стоит ли это вашего времени, но ваш поток пар дает вамидеальный прогнозирующий ввод для управления кэшем строк шаблонов - классический алгоритм замены страниц виртуальной машины Belady.

Answer 5

Вы можете создать конечный автомат.В этом разделе, Быстрый алгоритм извлечения тысяч простых шаблонов из больших объемов текста , я использовал [f] lex, чтобы создать для меня конечный автомат.Для использования 4-буквенного (: = двухбитного) алфавита потребуется некоторая хакерская атака, но это можно сделать с помощью тех же таблиц, что и сгенерированные [f] lex.(Вы могли бы даже создать свою собственную функцию, подобную fgetc (), которая извлекает по два бита за раз из входного потока и сохраняет остальные шесть битов для последовательных вызовов. Откат будет немного сложнее, но не отменен).

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

Answer 6

Преимущество кодирования алфавита в битовые поля заключается в компактности: один байт содержит эквивалент четырех символов. Это похоже на некоторые оптимизации, которые Google выполняет при поиске слов.

Это предполагает четыре параллельных выполнения, каждое с (преобразованной) строкой поиска, смещенной на один символ (два бита). Быстрый и грязный подход может заключаться в том, чтобы просто искать первый или второй байт строки поиска, а затем проверять дополнительные байты до и после сопоставления с остальной строкой, маскируя при необходимости концы концов. Первый поиск выполняется по инструкции x86 scasb. Последующие байтовые совпадения могут основываться на значениях регистра с cmpb.