Коткий геш (англ. rolling hash) (також відомий як рекурсивне гешування або котка контрольна сума) — це геш-функція, яка гешує дані у вікні, що рухається уздовж входових даних.
Декілька геш-функцій дозволяють швидке обчислення коткого гешу маючи лише попередній геш і видалене з і до додане до вікна значення. Це подібно до функції рухомого середнього, яку можна обчислити швидше ніж інші низькочастотні фільтри.
Одне з найпомініших застосувань це алгоритм Рабіна — Карпа пошуку підрядка, який використовує геш описаний нижче. Інше поширене застосування це застосунок rsync, який в якості коткого гешу використовує контрольну суму породжену з . Вузькосмугова мережева файлова система (LBFS) використовує «відбиткі пальців» Рабіна як коткий геш.
Щонайбільше, значення коткого гешу або сильно універсальні. Наприклад, вони не можуть бути [en].
Поліномний коткий геш
Алгоритм Рабіна — Карпа часто пояснюють за допомогою функції коткого гешу, яка використовує лише множення і додавання:
,
де це стала величина, а
це входові символи (але ця функція не є «відбитками пальців» Рабіна).
Щоб не довелось працювати з величезними значеннями , всю математику роблять за модулем
. Вибір
і
критичний для отримання хорошого гешування; дивись лінійний конгруентний метод.
Видаляння і додавання символів потребує просто додавання або віднімання першого або останнього доданку. Зсування всіх символів на одну позицію ліворуч вимагає домноження усієї суми на
. Зауважте, що в модульній арифметиці
можна обрати так, щоб вона мала множильне обернене
, на яке можна домножити
, щоб отримати ділення не роблячи його насправді.
Примітки
- Daniel Lemire, Owen Kaser: Recursive n-gram hashing is pairwise independent, at best, Computer Speech & Language 24 (4), pages 698–710, 2010. arXiv:0705.4676.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Kotkij gesh angl rolling hash takozh vidomij yak rekursivne geshuvannya abo kotka kontrolna suma ce gesh funkciya yaka geshuye dani u vikni sho ruhayetsya uzdovzh vhodovih danih Dekilka gesh funkcij dozvolyayut shvidke obchislennya kotkogo geshu mayuchi lishe poperednij gesh i vidalene z i do dodane do vikna znachennya Ce podibno do funkciyi ruhomogo serednogo yaku mozhna obchisliti shvidshe nizh inshi nizkochastotni filtri Odne z najpominishih zastosuvan ce algoritm Rabina Karpa poshuku pidryadka yakij vikoristovuye gesh opisanij nizhche Inshe poshirene zastosuvannya ce zastosunok rsync yakij v yakosti kotkogo geshu vikoristovuye kontrolnu sumu porodzhenu z Vuzkosmugova merezheva fajlova sistema LBFS vikoristovuye vidbitki palciv Rabina yak kotkij gesh Shonajbilshe znachennya kotkogo geshu abo silno universalni Napriklad voni ne mozhut buti en Polinomnij kotkij geshAlgoritm Rabina Karpa chasto poyasnyuyut za dopomogoyu funkciyi kotkogo geshu yaka vikoristovuye lishe mnozhennya i dodavannya H c 1 a k 1 c 2 a k 2 c 3 a k 3 c k a 0 displaystyle H c 1 a k 1 c 2 a k 2 c 3 a k 3 c k a 0 de a displaystyle a ce stala velichina a c 1 c k displaystyle c 1 c k ce vhodovi simvoli ale cya funkciya ne ye vidbitkami palciv Rabina Shob ne dovelos pracyuvati z velicheznimi znachennyami H displaystyle H vsyu matematiku roblyat za modulem n displaystyle n Vibir a displaystyle a i n displaystyle n kritichnij dlya otrimannya horoshogo geshuvannya divis linijnij kongruentnij metod Vidalyannya i dodavannya simvoliv potrebuye prosto dodavannya abo vidnimannya pershogo abo ostannogo dodanku Zsuvannya vsih simvoliv na odnu poziciyu livoruch vimagaye domnozhennya usiyeyi sumi H displaystyle H na a displaystyle a Zauvazhte sho v modulnij arifmetici a displaystyle a mozhna obrati tak shob vona mala mnozhilne obernene a 1 displaystyle a 1 na yake mozhna domnozhiti H displaystyle H shob otrimati dilennya ne roblyachi jogo naspravdi PrimitkiDaniel Lemire Owen Kaser Recursive n gram hashing is pairwise independent at best Computer Speech amp Language 24 4 pages 698 710 2010 arXiv 0705 4676