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

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

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

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

Теперь для каждой входящей иглы 1K вычислите ее 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 должно выполняться очень несколько раз, пока не вернется так или иначе. Так что каждый поиск иглы должен быть очень быстрым.

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

Вы хотите тратить много времени на предварительную обработку строки?

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

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

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

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

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

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

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

edit:

Основная идея здесь - сопоставить префиксы. Это может сильно сбить с толку, если информация очень похожа, но если у нее есть достаточное количество расхождений между 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, пока не будет найдена вся строка поиска.

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

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

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

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

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

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

Если шаблоны довольно случайны, вы можете предварительно вычислить расположение 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

Someone hinted at a possible way to index this thing if you have abundant RAM (or possibly even disk/swap) available.

Imagine if you performed a simple 32-bit CRC on a 1K block extending from each character in the original Gig string. This would result in 4bytes of checksum data for each byte offset from the beginning of the data.

By itself this might give a modest improvement in search speed. The checksum of each 1K search target could be checked against each CRC ... which each collision tested for a true match. That should still be a couple orders of magnitude faster than a normal linear search.

That, obviously, costs us 4GB of RAM for he CRC array (plus the original Gig for the original data and a little more overhead for the environment and our program).

If we have ~16GB we could sort the checksums and store a list of offsets where each is found. That becomes an indexed search (average of about 16 probes per target search ... worst case around 32 or 33 (might be a fence post there).

It's possible that a 16BG file index would still give better performance than a linear checksum search and it would almost certainly be better than a linear raw search (unless you have extremely slow filesystems/storage).

(Adding): I should clarify that this strategy is only beneficial given that you've described a need to do many searches on the same one gigabyte data blob.

You might use a threaded approach to building the index (while reading it as well as having multiple threads performing the checksumming). You might also offload the indexing into separate processes or a cluster of nodes (particularly if you use a file-based index --- the ~16GB option described above). With a simple 32-bit CRC you might be able to perform the checksums/indexing as fast as your reader thread can get the data (but we are talking about 1024 checksums for each 1K of data so perhaps not).

You might further improve performance by coding a Python module in C for actually performing the search ... and/or possibly for performing the checksumming/indexing.

The development and testing of such C extensions entail other trade-offs, obviously enough. It sounds like this would have near zero re-usability.

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

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

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

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

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