Индекс подстроки на диске
У меня есть файл (точнее, файл fasta), который я хотел бы проиндексировать, чтобы я мог быстро найти любую подстроку в файле, а затем найти местоположение в исходном файле fasta.
Во многих случаях это было бы легко сделать, используя массив Trie или подстрок, к сожалению, строки, которые мне нужно проиндексировать, составляют 800+ МБ, что означает, что выполнение их в памяти недопустимо, поэтому я ищу разумный способ создать это индекс на диске с минимальным использованием памяти.
(редактировать для пояснения)
Меня интересуют только заголовки белков, поэтому для самой большой интересующей меня базы данных это около 800 МБ текста.
Я хотел бы найти точную подстроку за время O (N) на основе входной строки. Это должно быть использовано на 32-битных машинах, так как оно будет отправлено случайным людям, у которых не ожидается 64-битных машин.
Я хочу иметь возможность индексировать по любому разрыву слова в строке до конца строки (хотя строки могут быть длиной в несколько МБ).
Надеюсь, это проясняет, что необходимо, и почему текущие решения не проясняют.
Я также должен добавить, что это нужно делать изнутри java, и это должно быть сделано на клиентских компьютерах в различных операционных системах, поэтому я не могу использовать какое-либо решение для ОС, и это должно быть программное решение.
Операционная система? Вам нужно использовать регулярное выражение в строке поиска или вы ищете совпадения целой строки?
Ответы 4
Я поговорил с несколькими коллегами, и они просто используют VIM / Grep для поиска, когда им нужно. Однако в большинстве случаев я не ожидал, что кто-то будет искать такую подстроку.
Но я не понимаю, почему поиск MS Desktop или Spotlight или аналог Google не могут вам здесь помочь.
Я рекомендую разбить файл на части - по генам или видам, надеюсь, входные последовательности не чередуются.
На некоторых языках программисты имеют доступ к "прямые байтовые массивы" или «карты памяти», которые предоставляются ОС. В java у нас есть java.nio.MappedByteBuffer. Это позволяет работать с данными, как если бы это был массив байтов в памяти, когда на самом деле они находятся на диске. Размер файла, с которым можно работать, ограничен только возможностями виртуальной памяти ОС и обычно составляет ~ <4 ГБ для 32-разрядных компьютеров. 64-битный? Теоретически 16 эксабайт (17,2 миллиарда ГБ), но я думаю, что современные процессоры ограничены 40-битным (1 ТБ) или 48-битным (128 ТБ) адресным пространством.
Это позволит вам легко работать с одним большим файлом.
Итак, проблема с этой идеей заключается в том, что с заголовочным файлом размером 7 МБ подстрока Trie составляет около 600 МБ.
Суть моего сообщения в том, что при работе с прямыми байтовыми буферами можно буквально забыть о разнице между тем, что находится на диске, и тем, что находится в памяти, и просто сосредоточиться на алгоритме.
за исключением того, что вы не можете, когда имеете дело с более чем 4 гигабайтами данных, что так и есть.
Ваш OP говорит 800 МБ, а не 4 ГБ. : S Возможен ли переход на 64-битную ОС?
Я обновил ответ, добавив информацию об адресуемой памяти современных 64-разрядных процессоров общего назначения.
Формат файла FASTA очень разрежен. Первое, что я сделал бы, это сгенерировать компактный двоичный формат и индекс который - он должен составлять, возможно, 20-30% от размера вашего текущего файла, а процесс кодирования / декодирования данных должен быть достаточно быстрым (даже с 4 ГБ) что это не будет проблемой.
На этом этапе ваш файл должен уместиться в памяти даже на 32-битной машине. Позвольте ОС подать его на страницу или создайте RAM-диск, если хотите быть уверенным, что все это в памяти.
Имейте в виду, что память стоит всего около 30 долларов за ГБ (и становится все дешевле), поэтому, если у вас 64-разрядная ОС, вы даже можете работать с полным файлом в памяти, не кодируя его в более компактный формат.
Удачи!
-Адам
Я не думаю, что у оригинального плаката все еще есть эта проблема, но всем, кому нужна индексация файлов FASTA и извлечение подпоследовательностей, следует проверить fastahack: http://github.com/ekg/fastahack
Он использует индексный файл для подсчета новых строк и смещений начала последовательности. После создания индекса вы можете быстро извлекать подпоследовательности; извлечение осуществляется с помощью fseek64.
Это будет работать очень и очень хорошо в том случае, если ваши последовательности будут такими же длинными, как и плакат. Однако, если у вас есть много тысяч или миллионов последовательностей в вашем файле FASTA (как в случае с выходными данными последовательности короткого чтения или некоторых сборок de novo), вы захотите использовать другое решение, например, ключ-значение на диске. хранить.
Возможно, вы захотите немного уточнить. Что быстро? Существуют ли какие-либо ограничения на (размер) подстроки, которую вы будете искать? Содержит ли файл одну большую строку или несколько меньших, которые нужно искать отдельно? Размер диска? "Минимальное" использование памяти?