Хеш-инвариант порядка в Python

В Python я хотел бы быстро вычислить хеш-инвариант порядка для строк файла как способ идентифицировать "уникально" его содержимое. Эти файлы представляют собой, например, вывод select ... from table и, следовательно, порядок строк является случайным.

Вот пример, который достигает того, что я хочу (используя один из хэшеров в hashlib), но за счет необходимости сортировки строк. Обратите внимание, что сортировка строк - это просто способ достижения цели, то есть получить хэш, который не зависит от упорядочения строк в файле. Но ясно, что я бы хотел избежать стоимости O (n * log (n)), особенно. когда файлы намного длиннее.

def get_hexdigest(filename, hasher, blocksize=65536, order_invariant=False):
    if not os.path.isfile(filename):
        return None
    if order_invariant:
        with open(filename, 'r') as f:
            for line in sorted(f):
                hasher.update(line.encode())
    else:
        with open(filename, 'rb') as f:
            while True:
                buf = f.read(blocksize)
                hasher.update(buf)
                if len(buf) < blocksize:
                    break
    return hasher.hexdigest()

Таким образом, например, 1MB, файл 50K строк:

%%time
get_hexdigest('some_file', hashlib.sha1())
# Wall time: 1.71 ms

Но:

%%time
get_hexdigest('some_file', hashlib.sha1(), order_invariant=True)
# Wall time: 77.4 ms

Что это лучший/быстрый способ сделать это?

Как отмечено в этом ответе, Scala имеет хеш-инвариант порядка на основе Murmurhash, но я предполагаю, что это 32-разрядная версия mmh3 (тоже склонный к конфликтам для моего использования), а также я предпочел бы использовать некоторую стандартную библиотеку, доступную в Python, а не реализовывать что-то на C или в Cython. Murmurhash3 имеет 128-битную версию, но ее выход отличается от x64 vs x86. Я хотел бы иметь независимые от машины результаты.

Итак, в общем, я бы хотел:

  • согласованные результаты в машинных архитектурах
  • низкая скорость столкновения, то есть не менее 128 бит с хорошей дисперсией (но мне не нужно, чтобы хэш был криптографическим).
  • достаточно быстро, то есть не менее 5 мс для файла с 1 МБ, 50 тыс. строк.
  • легкодоступно, если возможно, как библиотека на PyPi или Conda.
  • совместим с файлами с повторяющимися строками (так что хеширование XORing для строк не является стартером, так как любая пара одинаковых строк будет отменять друг друга).

Редактирование и примечания: Благодаря нескольким комментариям приведенный выше код обновляется для сортировки строк в памяти. Исходная версия для order_invariant is True была:

    with os.popen('sort {}'.format(filename)) as f:
        for line in f:
            hasher.update(line.encode(encoding='utf-8'))
    return hasher.hexdigest()

Связанное время стены (для файла, используемого выше) составляло 238 мс. Теперь это уменьшено до 77 мс, но все еще медленнее, чем не сортировка строк. Сортировка добавит стоимость n * log (n) для n строк.

Копирование (в UTF-8) и чтение в режиме 'r' и 'rb' необходимо при чтении строк, так как тогда мы получаем строки не байтов. Я не хочу полагаться на предположение, что файлы содержат только данные ASCII; чтение в 'rb' может привести к неправильному разделению строк. У меня нет той же заботы, когда order_invariant является False, потому что тогда мне не нужно разбить файл, и, таким образом, самым быстрым способом является сокращение фрагментов двоичных данных для обновления хэширования.

Ответы

Ответ 1

Я думаю, вам нужно отсортировать файл до (select ... from table order by ...) или придумать другое решение для вашей реальной проблемы.

В любом случае, возможный подход в Python с помощью frozenset:

#!/usr/bin/python

lines1 = ['line1', 'line2', 'line3', 'line4']
lines2 = ['line2', 'line1', 'line3', 'line4']  # same as lines1 but different order
lines3 = ['line1', 'line1', 'line3', 'line4', 'line5']


for lines in [lines1, lines2, lines3]:
    print(lines)
    print(hash(frozenset(lines)))
    print('')

Выход

['line1', 'line2', 'line3', 'line4']
8013284786872469720

['line2', 'line1', 'line3', 'line4']
8013284786872469720

['line1', 'line1', 'line3', 'line4', 'line5']
7430298023231386903

Я сомневаюсь, что это будет соответствовать вашим ограничениям производительности. Я не знаю временную сложность (Big O) frozenset(). Он также предполагает, что линии уникальны. Опять же, я настоятельно рекомендую по-разному решить основную проблему.

Ответ 2

Есть ли причина, по которой это решение в стиле merkle не будет работать?

import hashlib

def hasher(data):
    hasher = hashlib.sha1()
    hasher.update(data.encode('utf-8'))
    return hasher.hexdigest()


def get_digest_by_line(filename, line_invariant=False, hasher=hasher):
    with open(filename, 'r') as f:
        hashes = (hasher(line) for line in f)
        if line_invariant:
            hashes = sorted(hashes)
        return hasher(''.join(hashes))

Ответ 3

Спасибо всем за интересные комментарии и ответы.

В настоящее время лучший ответ для больших файлов ( > 350K строк) ниже (a). Он основан на Murmurhash3, добавляя mmh3.hash128() каждой строки. Для более мелких файлов это (b) ниже: вариант метода frozenset, предложенного Ролфом, который я адаптировал для создания 128-битного хэша (хотя я не стал бы ручаться за качество этих 128 бит).

a) mmh3.hash128() для каждой строки и добавьте

import mmh3
def get_digest_mmh3_128_add(filename):
    a = 0
    with open(filename, 'rb') as f:
        for line in f:
            a += mmh3.hash128(line)
    return '{:032x}'.format(a & 0xffffffffffffffffffffffffffffffff)

В моей настройке: постоянная 0,4 секунды на миллион строк.

b) два хэша frozenset

def get_digest_hash_frozenset128(filename):
    with open(filename, 'rb') as f:
        frz = frozenset(f.readlines())
    return '{:032x}'.format(((hash(frz) << 64) + hash(frz.union('not a line'))) & 0xffffffffffffffffffffffffffffffff)

В моей настройке: от 0,2 до 0,6 секунды на миллион строк.

Примечания

  • После рассмотрения я решил, что нормально читать строки файла в двоичном режиме, даже если они потенциально содержат текст UTF-8. Причина в том, что если некоторый символ Unicode содержит '\n', линия будет случайно разбита на эту точку. Затем файл будет иметь тот же дайджест, что и другой, где две части этой строки были расположены по-разному (или даже раздроблены и помещены в другое место через файл), но вероятность этого чрезвычайно медленная, и я могу жить с он.

  • Добавление всех 128-битовых хэшей в (a) выполняется с использованием произвольной точности int Python. Сначала я попытался сохранить сумму в 128 бит (повторяя и сохраняя константу 0xfff...fff). Но это оказывается медленнее, чем позволить Python использовать произвольную точность и делать маскировку один раз в конце.

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

Полные результаты

Полный ноутбук доступен здесь. Он создает псевдослучайные файлы произвольных размеров и пробует несколько подходов к дайджесту, измеряя время, затрачиваемое каждым из них. Это выполняется на экземпляре EC2 (r3.4xlarge, с использованием тома EBS для хранения псевдослучайного файла) и ноутбука Jupyter iPython и Python 3.6.

Для 46341 строк получим

fun                              lines millis
get_digest_xxh64_order_sensitive 46341    0.4 *
get_digest_sha1                  46341    1.7 *
get_digest_hash_frozenset64      46341    8.7
get_digest_hash_frozenset128     46341   10.8
get_digest_sha1_by_lines         46341   14.1 *
get_digest_mmh3_128_add_cy       46341   18.6
get_digest_mmh3_128_add          46341   19.7
get_digest_sha1_sort_binary      46341   44.3
get_digest_sha1_sort             46341   65.9

*: они зависят от порядка, просто для сравнения.

get_digest_hash_frozenset64 не подходит, поскольку он дает только 64 бита.

get_digest_mmh3_128_add_cy - это cythonized версия функции, приведенной выше в (a), но мало различий.

get_digest_xxh64_order_sensitive работает очень быстро, но зависит от порядка. Мои попытки (не перечисленные здесь) для получения версии, не зависящей от порядка, дали довольно медленные результаты. Причина, по-моему, - это, по-видимому, высокая стоимость инициализации и завершения хеша.

Для больших файлов выигрывает get_digest_mmh3_128_add_cy. Вот для 11.8M строк:

fun                                 lines    millis
get_digest_xxh64_order_sensitive 11863283      97.8 *
get_digest_sha1                  11863283     429.3 *
get_digest_sha1_by_lines         11863283    3453.0 *
get_digest_mmh3_128_add_cy       11863283    4692.8
get_digest_mmh3_128_add          11863283    4956.6
get_digest_hash_frozenset64      11863283    6418.2
get_digest_hash_frozenset128     11863283    7663.6
get_digest_sha1_sort_binary      11863283   27851.3
get_digest_sha1_sort             11863283   34806.4

Сосредоточив внимание на двух ведущих претендентах (инвариант порядка, а не на других), вот сколько времени они берут в функции размера (количество строк). У-ось - микросекунды/линия, а ось x - это количество строк файла. Обратите внимание, как get_digest_mmh3_128_add_cy проводит постоянное время (0,4 us) в строке.

time of two order-invariant digests in function of size

Следующие шаги

Извините за длинный ответ. Это только промежуточный ответ, как я мог (если позволит время) позже попытаться продолжить эксперименты с numba или Cython (или С++) прямой реализации Murmurhash3.