Built-In Hashing

Python có xây dựng sẵn cho chúng ta một hàm hash, chúng ta cứ việc gọi ra và sử dụng.

1hash("pham duy tung")
2-7141560399917772220

Một lưu ý nhỏ là giá trị của hàm hash sẽ khác nhau giữa các phiên bản python. Ví dụ ở trên mình xài python 3.8, với bản 3.6 sẽ là

1hash("pham duy tung")
21568935795476364190

Checksums

Chúng ta có thể sử dụng checksums để hash dữ liệu. Checksum được sử dụng trong thuật toán nén file ZIP để đảm bảo toàn vẹn dữ liệu sau khi nén. Thư viện zlib của python hỗ trợ 2 hàm tính checksum là adler32 và crc32. Để đảm bảo tốc độ chương trình và chỉ cần lấy hash đơn giản, chúng ta có thể sử dụng hàm Adler32. Tuy nhiên, nếu bạn muốn chương trình có độ tin cậy cao hoặc đơn giản là checksums, hãy sử dụng crc32. Các bạn có thể đọc bài viết ở đây https://www.leviathansecurity.com/blog/analysis-of-adler32 để hiểu hơn.

1>>> import zlib
2>>> zlib.adler32(b"Pham Duy Tung")
3524616855
4>>> zlib.crc32(b"Pham Duy Tung")
53750031252

Secure Hashing

Mã hóa an toàn (Secure Hashing) và bảo mật dữ liệu đã được nghiên cứu và ứng dụng từ nhiều năm về trước. Tiền thân là thuật toán MD5 đến SHA1, SHA256, SHA512…. Mỗi thuật toán ra đời sau sẽ cải tiến độ bảo mật và giảm đụng độ của các thuật toán trước đó.

Một số hàm hash phổ biến:

MD5– 16 bytes/128 bit

Chuỗi đầu ra của MD5 có kích thước 16 bytes hay 16*8 = 128 bits. Ở thời điểm hiện tại MD5 không còn là thuật toán phổ biến và không được khuyến khích dùng bởi các tổ chức bảo mật.

1>>> import hashlib
2>>> hashlib.md5(b"Pham Duy Tung").hexdigest()
3'58067430b9caa44f5ac1220b171f45c8'
4>>> len(hashlib.md5(b"Pham Duy Tung").digest()) # Chiều dài của đầu ra là 16 bytes
516

Chú ý: Hàm hexdigest biểu diễn một byte thành một ký tự hex (2 ký tự đầu 58 của ví dụ trên là giá trị hex của số 88 trong hệ thập phân)

SHA1–20 bytes/160 bits

Đầu ra của SHA1 có chiều dài là 20 bytes tương ứng với 160 bit. Cũng giống như MD5, SHA1 cũng không được khuyến khích sử dụng ở trong các ứng dụng bảo mật.

1>>> import hashlib
2>>> hashlib.sha1(b"Pham Duy Tung").hexdigest()
3'b95b8716f15d89b6db67e2e788dea42d3fba5ee8'
4>>> len(hashlib.sha1(b"Pham Duy Tung").digest())
520

SHA256–32 bytes/256 bit và SHA512–64 bytes/512 bit

Đây là hai hàm hash được khuyên là nên dùng ở thời điểm hiện tại

1>>> hashlib.sha256(b"Pham Duy Tung").hexdigest()
2'611b322b6b8ee570831c6061408ac5aa77fcdb572206d5d443855f5d3c1383c6'
3>>> len(hashlib.sha256(b"Pham Duy Tung").digest())
432
5>>> hashlib.sha512(b"Pham Duy Tung").hexdigest()
6'ac1f6a2dd234bc15c1fa2be1db4e55ad4af8c476abb8e3d9ac3d4c74d3e151c23314e20925616e90a0bcb13a38b5531e064c586d65fed54504d713fdabee03f9'
7>>> len(hashlib.sha512(b"Pham Duy Tung").digest())
864

Near-Duplicate Detection

Các thuật toán được giới thiệu ở trên, khi chúng ta thay đổi giá trị đầu vào, dù chỉ một giá trị nhỏ thôi ở một vài vị trí nào đó, thì kết quả trả ra lại khác nhau khá lớn. Tuy nhiên, đôi khi chúng ta gặp những bài toán tìm nội dung tương tự nhau hoặc gần như tương tự nhau. Ví dụ giống như google crawler dữ liệu xác định những bài văn copy paste từ những trang web khác nhau, hoặc phát hiện đạo văn, phát hiện đạo nhạc …

Một thuật toán khá phổ biến nằm trong nhóm này là SimHash. Thuật toán được google sử dụng để tìm ra các trang gần trùng nhau (theo wiki https://en.wikipedia.org/wiki/SimHash). Tác giả của thuật toán là Moses Charikar.

Để dùng Simhash, chúng ta phải cài đặt package từ kho của python

1from simhash import Simhash
2
3>>> Simhash("Pham Duy Tung").value
417022061268703429674
5>>> Simhash("Pham Duy Tung1").value
617184261516160517290

Một trong những lưu ý quan trọng khi sử dụng SimHash ( tham khảo https://stackoverflow.com/questions/49820228/how-to-compare-the-similarity-of-documents-with-simhash-algorithm/49831194#49831194)

SimHash thật sự hữu ích trong bài toán phát hiện văn bản trùng lắp.
Để tìm văn bản trùng lắp chính xác, dúng ta có thể sử dụng các thuật toán đơn giản mà hiệu quả như md5, sha1sha1.
Thuật toán phù hợp các văn bản lớn, không phù hợp cho các câu văn nhỏ.

Đoạn code bên dưới là một ví dụ được dùng để tìm các văn bản có đạo nội dung.

 1 #assuming that you have a dictionary with document id as the key and the document as the value:
 2# documents = { doc_id: doc } you can do:
 3
 4from simhash import simhash
 5
 6def split_hash(str, num):
 7    return [ str[start:start+num] for start in range(0, len(str), num) ]
 8
 9hashes = {}
10for doc_id, doc in documents.items():
11    hash = simhash(doc)
12
13    # you can either use the whole hash for higher precision or split into chunks for higher recall
14    hash_chunks = split_hash(hash, 4)
15
16    for chunk in hash_chunks:
17        if chunk not in hashes:
18            hashes[chunk] = []
19        hashes[chunk].append(doc_id)
20
21# now you can print the duplicate documents:
22for hash, doc_list in hashes:
23    if doc_list > 1:
24        print("Duplicates documents: ", doc_list)

Ngoài SimHash, còn một thuật toán hash khá nổi tiếng nữa cũng được google sử dụng trong việc cá nhân hóa người dùng, đó là MinHash. Ở các bài viết tiếp theo mình sẽ viết về thuật toán này.

Perceptual Hashing

Loại hash cuối cùng chúng ta đề cập ở đây là perceptual hashing. Loại hash này được sử dụng để phát hiện sự khác nhau trong tập hình ảnh hoặc trong video.

Một ví dụ của các thuật toán thuộc nhóm là là được dùng để phát hiện các frame ảnh trùng lắp trong video. Thuật toán được dùng để loại bỏ những nội dung trùng lắp, giúp tiết kiệm lưu trữ. Hoặc dùng trong các thuật toán tóm tắt video.

Ảnh 1 Ảnh 1 Ảnh 2 Ảnh 2

1>>> import hashlib
2>>> from PIL import Image
3>>> image1 = Image.open("google_free_ds1.png")
4>>> image1 = Image.open("google_free_ds_1.png")
5>>> image2 = Image.open("google_free_ds_2.png")
6>>> hashlib.sha256(image1.tobytes()).hexdigest()
7'c57d0b5b1ca64077b45bdb65f817497834675232a2fc2ed76d6b8aa7955126b9'
8>>> hashlib.sha256(image2.tobytes()).hexdigest()
9'02ea5e51b19cf3748f91f9bbe26976e9e14dca4b47e0aaff88ab20030a695f44'

Giá trị hash khác xa nhau, có vẻ chúng ta không thể nào sử dụng SHA256 trong bài toán này được. Lúc này, chúng ta sẽ tìm tới các thư viện thuộc nhóm Perceptual Hashing, một trong số chúng là ImageHash.

1>>> import imagehash
2>>> hash1 = imagehash.average_hash(image1)
3>>> hash2 = imagehash.average_hash(image2)
4>>> hash1-hash2
524

Giá trị hash của hai ảnh trên là khác nhau, nhưng sự khác nhau là rất ít. Chứng tỏ hai ảnh trên có thể là bản sao của nhau.

Kết luận

Trong bài viết này, chúng ta đã đề cập qua các cách khác nhau để hash dữ liệu trong Python. Phụ thuộc vào bài toán, chúng ta sẽ sử dụng các thuật toán với các tham số phù hợp. Hi vọng bài viết này sẽ ít nhiều giúp ích được cho các bạn.

Chú thích:

Ảnh cover của bài viết là ảnh của chùm sao thất tinh bắc đẩu mình chụp từ trang https://stellarium-web.org/.
hash collision : Khi cho 2 input khác nhau vào hàm hash mà cùng ra một output -> collision.

Nguồn bài viết:

https://medium.com/better-programming/how-to-hash-in-python-8bf181806141

Các Hàm Hash Có Sẵn Trong Python