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

Ответ 1

Как вы уточните, что длинная препроцессия приемлема, я бы предложил вариант Rabin-Karp: "алгоритм выбора для множественный поиск по шаблону", как это делает wikipedia.

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

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

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

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

Ответ 2

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

Ответ 3

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

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

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

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

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

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

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

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

изменить:

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

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

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

Мы можем вызвать Shannon Entropy для определения информации данного n-грамма. Возьмите строку поиска и последовательно создайте префикс, основанный на первых символах m. Когда энтропия m-префикса "достаточно высока", используйте ее позже.

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

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

Ответ 4

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

Ответ 5

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

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

Ответ 6

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

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

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

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

Ответ 7

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

Ответ 8

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

Вместо того, чтобы перебирать все опции для n-префиксов, просто используйте фактические строки в 1GB - их будет меньше 1Gig. Используйте как большой префикс, как подходит для вашей памяти, у меня нет 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

Ответ 9

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

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

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

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

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

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

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

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

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

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

Ответ 10

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

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