| dbo:abstract
|
- A rolling hash (also known as recursive hashing or rolling checksum) is a hash function where the input is hashed in a window that moves through the input. A few hash functions allow a rolling hash to be computed very quickly—the new hash value is rapidly calculated given only the old hash value, the old value removed from the window, and the new value added to the window—similar to the way a moving average function can be computed much more quickly than other low-pass filters. One of the main applications is the Rabin–Karp string search algorithm, which uses the rolling hash described below. Another popular application is the rsync program, which uses a checksum based on Mark Adler's adler-32 as its rolling hash. Low Bandwidth Network Filesystem (LBFS) uses a Rabin fingerprint as its rolling hash. FastCDC (Fast Content-Defined Chunking) uses a compute-efficient Gear fingerprint as its rolling hash. At best, rolling hash values are pairwise independent or strongly universal. They cannot be 3-wise independent, for example. (en)
- Un rolling hash (chiamato anche hash ricorsivo o rolling checksum) è una funzione di hash che processa l'input tramite una finestra scorrevole sull'input stesso. Alcune funzioni hash permettono il calcolo molto rapido, aggiornando il risultato in base al valore dell'hash nella finestra precedente e in base ai valori aggiunto e rimosso dalla finestra all'iterazione corrente, in maniera analoga al calcolo di una media mobile. Tutte le funzioni di rolling hash hanno complessità computazionale lineare nel numero di elementi, ma la complessità rispetto alla lunghezza k della finestra può variare a seconda dell'algoritmo. Ad esempio la funzione rolling hash di Rabin-Karp richiede la moltiplicazione di due interi di bit, con complessità , mentre l'hash di n-gram con polinomi ciclici può essere calcolato in tempo lineare. Un rolling hash può essere al più una funzione due-a-due indipendente o una funzione , ma non può essere k-a-k indipendente. (it)
- 旋转哈希（也称为滚动哈希、递归哈希、滚动校验和或滑动哈希）是一种哈希函数，输入的内容在一个窗口中进行移动哈希。 少数哈希函数允许快速计算滚动哈希值 — 只给出旧的哈希值，新的哈希值被快速计算出来，旧的值从窗口中移除，新的值添加到窗口中 — 类似于移動平均函数的计算方式，比其他低通滤波器更快。 主要应用之一是Rabin–Karp字符串搜索算法，该算法使用下面描述的滚动哈希。另一个流行的应用是rsync程序，它使用基于Mark Adler的adler-32的校验和作为滚动哈希。低带宽网络文件系统（LBFS）使用Rabin指纹作为其滚动哈希。 滚动哈希值最多只能是的或的。例如，它们不能是的。 (zh)
- Скользящий хеш (англ. rolling hash, также кольцевой хеш) — хеш-функция, обрабатывающая вход в рамках некоторого окна. Получение значения хеш-функции для сдвинутого окна в таких функциях является дешевой операцией. Для пересчета значения требуется знать лишь предыдущее значение хеша, значение входных данных, которые остались за пределами окна, и значение данных, которые попали в окно. Другими словами, если представляет собой хеш последовательности , то хеш для «сдвинутой» последовательности может быть получен с помощью легко вычислимой функции . Возможность быстрого «сдвига» хеша накладывает некоторые ограничения на теоретические гарантии. В частности, показано, что семейства кольцевых хешей не могут быть ; максимум — универсальными или . Впрочем, для большинства приложений достаточно универсальности (даже приблизительной). Кольцевой хеш применяется для поиска подстроки в алгоритме Рабина — Карпа, для вычисления хешей N-грамм в тексте, а также в программе rsync для сравнения двоичных файлов (используется кольцевая версия adler-32). (ru)
- Коткий геш (англ. rolling hash) (також відомий як рекурсивне гешування або котка контрольна сума) — це геш-функція, яка гешує дані у вікні, що рухається уздовж входових даних. Декілька геш-функцій дозволяють швидке обчислення коткого гешу маючи лише попередній геш і видалене з і до додане до вікна значення. Це подібно до функції рухомого середнього, яку можна обчислити швидше ніж інші низькочастотні фільтри. Одне з найпомініших застосувань це алгоритм Рабіна — Карпа пошуку підрядка, який використовує геш описаний нижче. Інше поширене застосування це застосунок rsync, який в якості коткого гешу використовує контрольну суму породжену з . Вузькосмугова мережева файлова система (LBFS) використовує «відбиткі пальців» Рабіна як коткий геш. Щонайбільше, значення коткого гешу або сильно . Наприклад, вони не можуть бути . (uk)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 13645 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dct:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- 旋转哈希（也称为滚动哈希、递归哈希、滚动校验和或滑动哈希）是一种哈希函数，输入的内容在一个窗口中进行移动哈希。 少数哈希函数允许快速计算滚动哈希值 — 只给出旧的哈希值，新的哈希值被快速计算出来，旧的值从窗口中移除，新的值添加到窗口中 — 类似于移動平均函数的计算方式，比其他低通滤波器更快。 主要应用之一是Rabin–Karp字符串搜索算法，该算法使用下面描述的滚动哈希。另一个流行的应用是rsync程序，它使用基于Mark Adler的adler-32的校验和作为滚动哈希。低带宽网络文件系统（LBFS）使用Rabin指纹作为其滚动哈希。 滚动哈希值最多只能是的或的。例如，它们不能是的。 (zh)
- A rolling hash (also known as recursive hashing or rolling checksum) is a hash function where the input is hashed in a window that moves through the input. A few hash functions allow a rolling hash to be computed very quickly—the new hash value is rapidly calculated given only the old hash value, the old value removed from the window, and the new value added to the window—similar to the way a moving average function can be computed much more quickly than other low-pass filters. (en)
- Un rolling hash (chiamato anche hash ricorsivo o rolling checksum) è una funzione di hash che processa l'input tramite una finestra scorrevole sull'input stesso. Alcune funzioni hash permettono il calcolo molto rapido, aggiornando il risultato in base al valore dell'hash nella finestra precedente e in base ai valori aggiunto e rimosso dalla finestra all'iterazione corrente, in maniera analoga al calcolo di una media mobile. Un rolling hash può essere al più una funzione due-a-due indipendente o una funzione , ma non può essere k-a-k indipendente. (it)
- Скользящий хеш (англ. rolling hash, также кольцевой хеш) — хеш-функция, обрабатывающая вход в рамках некоторого окна. Получение значения хеш-функции для сдвинутого окна в таких функциях является дешевой операцией. Для пересчета значения требуется знать лишь предыдущее значение хеша, значение входных данных, которые остались за пределами окна, и значение данных, которые попали в окно. Другими словами, если представляет собой хеш последовательности , то хеш для «сдвинутой» последовательности может быть получен с помощью легко вычислимой функции . (ru)
- Коткий геш (англ. rolling hash) (також відомий як рекурсивне гешування або котка контрольна сума) — це геш-функція, яка гешує дані у вікні, що рухається уздовж входових даних. Декілька геш-функцій дозволяють швидке обчислення коткого гешу маючи лише попередній геш і видалене з і до додане до вікна значення. Це подібно до функції рухомого середнього, яку можна обчислити швидше ніж інші низькочастотні фільтри. Щонайбільше, значення коткого гешу або сильно . Наприклад, вони не можуть бути . (uk)
|
| rdfs:label
|
- Rolling hash (it)
- Rolling hash (en)
- Скользящий хеш (ru)
- 旋转哈希 (zh)
- Коткий геш (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
