SimHash

SimHash — Kompüter elmlərində, xüsusilə mətn üzərində olan əməliyyatların sıx olduğu, axtarış mühərriki kimi tətbiqlərdə faylların və ya veb saytlarının bir-birinə olan bənzərliyini tapmaq üçün istifadə edilən alqoritmdir.

Alqoritmə alternativ olaraq klassik hash funksiyaları istifadə edilə bilər. Məsələn iki veb səhifənin ayrı-ayrı hash qiymətləri alınıb bu dəyərləri müqayisə etmək mümkündür. Ancaq simhash alqoritmi, bu üsula görə daha çox sürət və performans təqdim edir.

SimHash alqoritmi, iki faylı bir vektor olaraq görür və bu vektorlar arasındakı kosinusu tapır.

Yuxarıdakı şəkildən də görsəndiyi kimi ayrı-ayrı iki sənədin xüsusi vektor olması vəziyyətində, aralarında cos (x) olaraq göstərilən bir bucaq ilə əlaqə qurulması mümkündür.

Alqoritm, əvvəlcə işlədiyi mətndəki sözlərin ağırlıqlarını (weight) çıxarır və buna görə də sözləri sıralayır.

Sıralanan hər sözə, b uzunluğunda, yeganə (unique) qiymət qaytaran funksiya istifadə olunur. Məsələn hər söz üçün fərqli bir hash qiyməti qaytaran funksiya istifadə edilə bilər.

b ölçüsündəki bir vektorun ağırlıq dəyəri hesablanarkən, hər sözdəki 1 qiyməti üçün +1 və 0 qiyməti üçün -1 dəyəri əlavə olunur.

Son olaraq çıxarılan ağırlıq vektorundakı + dəyərlər 1, 0 və - dəyərlər isə 0 olaraq çevrilir.

Məsələn bir nümünə üzrə izah edək.

“code org code yazmaq saytıdır”

Yuxarıdakı mətni alqoritm üzrə işləyək. İlk olaraq hər bir sözün ağırlıq dərəcəsini hesablayırıq.

Code 2, org 1, yazmaq 1, saytıdır 1

İndi hər bir söz üçün barmaq izi (fingeprint) yaradırıq. Barmaq izləri yalnız bir sözə məxsus olur. Bu qiymət Hash funksiyalarından yaradılır. Biz sadəlik olsun deyə təsadüfi qiymətlər verəcəyik, amma real tətbiqlərdə təsadüfi ədələrdən istifadə oluna bilməz.

Indi bu ədədləri toplayaq:

Alınan nəticəni ikilik koda çevirik və bu bizim simhash qiymətimiz olur.

1 0 0 1 0 0 1 0

Fərz edək ki, başqa bir mətn üzərində də eyni bir əməliyyatı aparmışıq və nəticə olaraq

1 1 0 1 1 1 0 1

qiyməti almışıq.

Sonda biz hər iki qiyməti bir-biri ilə müqayisə edirik.

Bu iki simhash qiyməti arasındakı bit fərqi 4-ə bərabərdir. Bu o deməkdir ikinci hash qiymətini çıxardığımız mətn birinci mətnə (“code org code yazmaq saytıdır”) 4 məsafəsində yaxındır.