Python의 순서 불변 해시

Question

파이썬에서는 파일의 내용을 "고유하게"식별하는 방법으로 파일 행의 순서 불변 해시를 빠르게 계산하고 싶습니다. 이러한 파일은 예를 들어 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() 

1메가바이트, 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 

?

in this answer에서 언급했듯이 Scala에는 Murmurhash를 기반으로하는 순서 불변 해시가 있지만 32 비트 버전의 mmh3 (내 용도로는 충돌 가능성이 높음)이라고 가정하고 일부 표준 라이브러리 C 또는 Cython에서 무언가를 구현하는 것이 아니라 Python으로 사용할 수 있습니다. Murmurhash3은 128 비트 버전이지만 x64와 x86의 출력은 다릅니다. 나는 기계 독립적 결과를 원합니다.

그래서, 요약, 내가 좋아하는 것 : 좋은 분산과

• 기계 구조
• 낮은 충돌 속도에 걸쳐 일관성있는 결과, 즉 적어도 128 비트 (하지만 난 할 해시가 필요하지 않습니다 암호화)
• 합리적으로 빠르며, 1MB, 50K 라인 파일의 경우 최소 5ms 미만입니다.
• 가능하면 PyPi 또는 Conda의 라이브러리로 쉽게 사용할 수 있습니다.
• 반복되는 파일을 사용하는 파일에 적합합니다. 따라서 모든 행마다 동일한 XOR을 수행하면 비동기입니다.

---

편집 및 메모 : 여러 의견에 덕분에, 위의 코드는 메모리에 라인을 정렬 업데이트됩니다. 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 줄에 n * log (n) 비용이 추가됩니다.

줄을 읽을 때 인코딩이 (UTF-8로) 변환되고 'r' 또는 'rb' 인 경우에는 바이트가 아닌 문자열을 가져와야합니다. 필자는 파일에 ASCII 데이터 만 포함한다고 가정하고 싶지 않습니다. 'rb'에서 읽으면 제대로 분할되지 않은 줄이 생길 수 있습니다. order_invariant이 False 일 때 동일한 문제가 발생하지 않습니다. 그 이유는 파일을 분할 할 필요가 없기 때문이며, 따라서 가장 빠른 방법은 해시를 업데이트하기 위해 이진 데이터 청크를 버리는 것입니다.

Answer 1

나는 (select ... from table order by ...) 전에 파일을 정렬하거나 실제 문제에 대한 다른 해결책을 찾아야한다고 생각합니다.

어쨌든, 사용 파이썬에서 가능한 접근 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 

나는 그것이 당신의 성능이 제약 일치 의심한다. 나는 frozenset()의 시간 복잡성 (Big O)을 모른다. 또한 선이 고유하다고 가정합니다. 다시 한 번, 근본적인 문제를 다르게 다루는 것이 좋습니다.

Answer 2

흥미로운 의견과 답변을 보내 주셔서 감사합니다.

대용량 파일 (> 350K 회선)에 대한 최상의 대답은 (a)입니다. Murmurhash3을 기반으로 각 행의 mmh3.hash128()을 추가합니다. 작은 파일의 경우, 아래의 (b)입니다. 변이가 ​​the frozenset approach proposed by Rolf인데, 128 비트 해시를 생성하기에 적합합니다 (128 비트의 품질을 보증하지는 않지만). 내 설정에서

각 라인에 대한 가) 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) 내에서 설정

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) 

두 frozenset 해시 : 백만 당 0.2 초 내지 0.6 라인.

노트

1. 고려 후, 나는 그들이 잠재적으로 UTF-8 텍스트를 포함하는 경우에도 바이너리 모드로 파일의 라인을 읽기 좋아라고 판단했습니다. 그 이유는 일부 유니 코드 문자에 '\n'이 포함되어 있으면 해당 위치에서 실수로 줄이 분리되기 때문입니다. 그런 다음 파일은 다른 부분과 동일한 다이제스트를 얻습니다.이 부분은 해당 부분의 두 부분이 다르게 배열되었지만 (또는 분할되어 파일을 통해 다른 위치에 배치 될 수도 있지만),이 확률은 매우 느리며 함께 살 수 있습니다 그것.

2. (a)의 모든 128 비트 해시를 추가하는 것은 파이썬의 임의 정밀도 int를 사용하여 수행됩니다. 처음에는 합계를 128 비트로 유지하려고 시도했습니다 (반복하여 반복하고 0xfff...fff 상수로). 그러나 파이썬이 임의의 정밀도를 사용하고 끝에 마스킹을 한 번 수행하는 것보다 느리다는 것이 밝혀졌습니다.

3. 나는 frozenset의 정규 해시에서 두 개의 해시를 가져 와서 128 비트를 얻으려고합니다. frozenset의 파일과 frozenset의 파일은 어떤 파일에도 나타나지 않습니다. 해시에 대해 다른 시드를 사용하는 것과 같음).

전체 결과

전체 노트북을 사용할 수 here입니다. 임의의 크기의 의사 랜덤 파일을 생성하고 각각의 시간을 측정하면서 몇 가지 다이제스트 방식을 시도합니다. 이것은 EC2 인스턴스 (r3.4xlarge, 의사 랜덤 파일의 저장을위한 EBS 볼륨 사용)와 Jupyter iPython 노트북 및 Python 3.6에서 실행됩니다.

46,341 라인, 우리는

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은 (a)에서 주어진 함수의 cython 화 된 버전이지만 약간의 차이가 있습니다.

get_digest_xxh64_order_sensitive은 매우 빠르지 만 주문에 따라 다릅니다. 주문 불변 버전을 파생시키려는 나의 시도 (여기에 열거되지 않음)는 모두 꽤 느린 결과를주었습니다. 그 이유는 해시를 초기화하고 마무리하는 데 드는 높은 비용 때문입니다.

큰 파일의 경우 get_digest_mmh3_128_add_cy이 이깁니다. 여기에, (주문 불변이 아닌 다른 사람)

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 

는 두 개의 주요 경쟁자에 초점을 그들이 크기의 함수 (행 수)를 가지고 얼마나 많은 시간이다 : 여기 11.8M 라인입니다. y 축은 마이크로 초/라인이고 x 축은 파일의 라인 수입니다. get_digest_mmh3_128_add_cy이 한 줄에 일정한 시간 (0.4 us)을 소비하는 방법에 유의하십시오.

다음은 장황한 답변 죄송합니다

단계를 반복합니다. 이것은 잠정적 인 대답 일뿐입니다. Murmurhash3를 직접 구현 한 numba 또는 Cython (또는 C++)에 대한 차후의 실험을 시도해 볼 수 있습니다.

Answer 3

머클 스타일 솔루션이 효과가없는 이유가 있습니까?

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))