Самый быстрый способ поиска 1 ГБ + строка данных для первого появления шаблона в Python

Question

Есть строка произвольных данных размером 1 ГБ, которую можно предположить эквивалентной чему-то вроде:

1_gb_string=os.urandom(1*gigabyte)

Мы будем искать в этой строке 1_gb_string бесконечное число фиксированной ширины, 1 килобайт, 1_kb_pattern. Каждый раз, когда мы ищем, картина будет отличаться. Так что возможности кеширования не очевидны. Одна и та же строка в 1 гигабайт будет искать снова и снова. Вот простой генератор для описания того, что происходит:

def findit(1_gb_string):
    1_kb_pattern=get_next_pattern()
    yield 1_gb_string.find(1_kb_pattern)

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

Что я могу использовать быстрее, чем bultin, найденный python для сопоставления шаблонов размером 1 КБ с строками данных размером 1 ГБ или более?

(Я уже знаю, как разбить строку и искать ее параллельно, так что вы можете игнорировать эту базовую оптимизацию.)

Обновление: пожалуйста, ограничьте требования к памяти объемом 16 ГБ.

Answer 1

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

Определите функцию «скользящего хэша», то есть такую, что, когда вы знаете хэш для haystack[x:x+N], вычисление хеша для haystack[x+1:x+N+1] равно O (1). (Обычные функции хеширования, такие как встроенные в Python hash, не имеют этого свойства, поэтому вы должны написать свое собственное, в противном случае предварительная обработка становится длинной изнурительно , а не просто long-ish ;-) , Полиномиальный подход является плодотворным, и вы можете использовать, скажем, 30-битные результаты хеширования (маскируя при необходимости, то есть вы можете выполнять вычисления с большей точностью и просто сохранять маскированные 30 битов выбора). Давайте назовем эту скользящую хеш-функцию RH для ясности.

Итак, вычислите 1G результатов RH, когда вы катитесь вдоль строки 1 ГБ стога сена; если вы только что сохранили эти данные, вы получите массив H из 1G 30-битных значений (4 ГБ), отображающий значение index-in-haystack-> RH. Но вы хотите обратное отображение, поэтому используйте вместо этого массив A из 2 ** 30 записей (1G записей), который для каждого значения относительной влажности дает вам все интересующие вас значения в стоге сена (индексы, при которых возникает это значение относительной влажности); для каждой записи вы сохраняете индекс первого, возможно, интересного индекса стога сена в другой массив B индексов 1G в стоге сена, который приказывает хранить все индексы в стоге сена с идентичными значениями RH («коллизии» в терминах хеширования). H, A и B имеют записи 1G по 4 байта каждая, итого 12 ГБ.

Теперь для каждой входящей иглы 1К, вычислите ее RH, назовите ее k и используйте ее в качестве индекса для A; A [k] дает вам первый индекс b в B, с которым стоит сравнить. Итак, сделайте:

ib = A[k]
b = B[ib]
while b < len(haystack) - 1024:
  if H[b] != k: return "not found"
  if needle == haystack[b:b+1024]: return "found at", b
  ib += 1
  b = B[ib]

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

Answer 2

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

Answer 3

Насколько я знаю, стандартный алгоритм поиска - это наивный алгоритм со сложностью около n * m сравнений, потому что это проверяет образцы против каждого возможного смещения. Есть несколько более эффективных алгоритмов, требующих сравнения n + m. Если ваша строка не является строкой на естественном языке, вы можете попробовать Алгоритм Кнута-Морриса-Пратта . Алгоритм поиска Бойера – Мура также достаточно быстр и прост.

Answer 4

Готовы ли вы потратить значительное время на предварительную обработку строки?

Если да, то вы можете создать список n-грамм со смещениями.

Предположим, ваш алфавит - это шестнадцатеричные байты, а вы используете 1 грамм.

Затем для 00-ff вы можете создать словарь, который выглядит следующим образом (perlese, извините)

$offset_list{00} = @array_of_offsets
$offset_list{01} = #...etc

где вы идете вниз по строке и строите @array_of_offsets из всех точек, где происходят байты. Вы можете сделать это для произвольных n-грамм.

Это обеспечивает «начальную точку для поиска», которую вы можете использовать для ходьбы.

Конечно, недостатком является то, что вам нужно предварительно обработать строку, так что это ваш компромисс.

редактирование:

---

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

Давайте оценим расхождение, так как вы не обсуждали, какую информацию вы анализируете. Для целей этого алгоритма мы можем характеризовать расхождение как функцию расстояния: вам нужно прилично высоко расстояние Хэмминга . Если расстояние Хэмминга между n-граммами, скажем, 1, приведенная выше идея не сработает. Но если это n-1, приведенный выше алгоритм будет намного проще.

Чтобы улучшить мой алгоритм, давайте создадим алгоритм, который последовательно устраняет некоторые возможности:

Мы можем вызвать Энтропию Шеннона , чтобы определить информацию данного n-грамма. Возьмите строку поиска и последовательно создайте префикс, основанный на первых m символах. Когда энтропия m-префикса «достаточно высока», используйте ее позже.

1. Определите p как m-префикс строки поиска
2. Поиск в строке размером 1 ГБ и создание массива смещений, соответствующих p.
3. Расширить m-префикс до некоторого k-префикса, k> m, энтропия k-префикса выше, чем у m-префикса.
4. Сохраните массив смещений элементов, определенный выше, так, чтобы они соответствовали строке k-префикса. Откажитесь от несоответствующих элементов.
5. Переходите к 4, пока не будет встречена вся строка поиска.

В некотором смысле это похоже на изменение кодировки Хаффмана.

Answer 5

Одним из эффективных, но сложных способов является полнотекстовое индексирование с помощью преобразования Берроуза-Уилера . Это включает выполнение BWT для вашего исходного текста, а затем использование небольшого индекса для быстрого поиска любой подстроки в тексте, которая соответствует вашему шаблону ввода.

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

Answer 6

Кто-то намекнул на возможный способ индексирования этой вещи, если у вас достаточно ОЗУ (или, возможно, даже диск / своп).

Представьте, что вы выполнили простую 32-битную CRC для блока размером 1 КБ, начиная с каждого символа в исходной строке Gig. Это приведет к получению 4 байтов данных контрольной суммы для каждого байтового смещения от начала данных.

Само по себе это может дать незначительное улучшение скорости поиска. Контрольная сумма каждой цели поиска 1K может быть проверена по каждому CRC ... который каждое столкновение проверялось на истинное совпадение. Это все равно должно быть на пару порядков быстрее, чем при обычном линейном поиске.

Это, очевидно, стоит нам 4 ГБ ОЗУ для массива CRC (плюс исходный гигабайт для исходных данных и немного больше накладных расходов для среды и нашей программы).

Если у нас есть ~ 16 ГБ, мы могли бы отсортировать контрольные суммы и сохранить список смещений, где они найдены. Это становится индексированным поиском (в среднем около 16 проверок на целевой поиск ... в худшем случае около 32 или 33 (возможно, там есть ограждение).

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

(Добавление): Я должен уточнить, что эта стратегия выгодна только с учетом того, что вы описали необходимость выполнять много операций поиска на одном и том же гигабайте данных.

Вы можете использовать многопоточный подход к созданию индекса (при его чтении, а также при наличии нескольких потоков, выполняющих контрольную сумму). Вы также можете перенести индексирование в отдельные процессы или кластер узлов (особенно если вы используете индекс на основе файлов - параметр ~ 16GB, описанный выше). С помощью простого 32-разрядного CRC вы можете выполнять контрольные суммы / индексирование так быстро, как ваш читательский поток может получить данные (но мы говорим о 1024 контрольных суммах для каждого 1 КБ данных, поэтому, возможно, нет).

Вы можете еще больше повысить производительность, кодируя модуль Python в C для фактического выполнения поиска ... и / или, возможно, для выполнения контрольной суммы / индексации.

Разработка и тестирование таких расширений C влекут за собой другие компромиссы, очевидно, достаточно. Похоже, это будет иметь практически нулевое повторное использование.

Answer 7

Если шаблоны довольно случайные, вы можете предварительно вычислить расположение n-префиксов строк.

Вместо того чтобы просматривать все опции для n-префиксов, просто используйте фактические в строке 1 ГБ - их будет менее 1 ГБ. Используйте такой большой префикс, который умещается в вашей памяти, у меня нет 16 ГБ ОЗУ для проверки, но префикс 4 может сработать (по крайней мере, в структурах данных с эффективным использованием памяти), если не попробовать 3 или даже 2.

Для случайной строки размером 1 ГБ и случайных шаблонов размером 1 КБ вы должны получить несколько десятков местоположений для каждого префикса, если вы используете 3-байтовые префиксы, но 4-байтовые префиксы должны давать вам в среднем 0 или 1, поэтому поиск должен быть быстро.

Предварительно вычисленные местоположения

def find_all(pattern, string):
  cur_loc = 0
  while True:
     next_loc = string.find(pattern, cur_loc)
     if next_loc < 0: return
     yield next_loc
     cur_loc = next_loc+1

big_string = ...
CHUNK_SIZE = 1024
PREFIX_SIZE = 4
precomputed_indices = {}
for i in xrange(len(big_string)-CHUNK_SIZE):
  prefix = big_string[i:i+PREFIX_SIZE]
  if prefix not in precomputed_indices:
    precomputed_indices[prefix] = tuple(find_all(prefix, big_string))

Поиск шаблона

def find_pattern(pattern):
  prefix = pattern[:PREFIX_SIZE]
  # optimization - big prefixes will result in many misses
  if prefix not in precomputed_indices:
    return -1
  for loc in precomputed_indices[prefix]:
    if big_string[loc:loc+CHUNK_SIZE] == pattern:
        return loc
  return -1

Answer 8

http://www.youtube.com/watch?v=V5hZoJ6uK-s Будет наиболее ценным для вас. Это лекция MIT по динамическому программированию

Answer 9

Я не знаю точно, является ли метод find() для строк быстрее, чем метод search(), предоставляемый модулем re (регулярные выражения) Python, но есть только один способ выяснить.

Если вы просто ищете строку, вам нужно:

import re
def findit(1_gb_string):
    yield re.search(1_kb_pattern, 1_gb_string)

Однако, если вы действительно хотите только первое совпадение, вам может быть лучше использовать finditer(), который возвращает итератор, и с такими большими операциями на самом деле может быть лучше.

Answer 10

С бесконечной памятью вы можете хешировать каждую строку 1 КБ вместе с ее положением в файле 1 ГБ.

Имея менее бесконечной памяти, вы будете ограничены тем, сколько страниц памяти вы касаетесь при поиске.