Хэш - Rolling hash

A жылжымалы хэш (рекурсивті хэштеу немесе бақылау сомасы деп те аталады) - бұл а хэш функциясы мұнда кіріс арқылы қозғалатын терезеде кірістер хэштеледі.

Бірнеше хэш функциясы жылжымалы хэшті тез есептеуге мүмкіндік береді - жаңа хэш мәні тек ескі хэш мәні, терезеден ескі мән алынып тасталса және терезеге қосылған жаңа мән берілген жағдайда жылдам есептеледі - а орташа жылжымалы функциясын басқа төмен жылдамдықты сүзгілерге қарағанда тезірек есептеуге болады.

Негізгі қосымшалардың бірі Рабин – Карп жолдарын іздеу алгоритмі, ол төменде сипатталған жылжымалы хэшті қолданады. Тағы бір танымал қосымша болып табылады rsync Марк Адлер негізінде бақылау сомасын қолданатын бағдарлама адлер-32 оның жылжымалы хэші ретінде. Төмен өткізу қабілеті бар желілік файлдық жүйе (LBFS) а Рабиннің саусақ ізі оның жылжымалы хэші ретінде. FastCDC (жылдам мазмұнмен анықталған қыстырма) есептеу үшін тиімді Gear саусақ ізін өзінің хэші ретінде пайдаланады.

Ең жақсы жағдайда, айналмалы хэш мәндері жұптық тәуелсіз[1] немесе қатты әмбебап. Олар болуы мүмкін емес 3 дана тәуелсіз, Мысалға.

Көпмүшелік жылжымалы хэш

The Рабин – Карп жолдарын іздеу алгоритмі көбейту мен толықтыруды ғана қолданатын жылжымалы хэш функциясын қолдану арқылы жиі түсіндіріледі:

қайда тұрақты болып табылады және кіріс таңбалары болып табылады (бірақ бұл функция а емес Рабиннің саусақ ізі, төменде қараңыз).

Айла-шарғы жасамас үшін барлық математика орындалды модуль . Таңдау және жақсы хэшті алу үшін өте маңызды; қараңыз сызықтық конгруденциялы генератор көбірек талқылау үшін.

Таңбаларды жою және қосу тек бірінші немесе соңғы мүшені қосуды немесе азайтуды қамтиды. Барлық таңбаларды бір позицияға солға ауыстыру барлық қосындыларды көбейтуді қажет етеді арқылы . Барлық таңбаларды бір позицияға оңға ауыстыру бүкіл соманы бөлуді қажет етеді арқылы . Арифметикалық модульде, болуы мүмкін деп таңдауға болады мультипликативті кері сол арқылы бөлудің нәтижесін алу үшін көбейтуге болады, бөлуді нақты жүзеге асырмай.

Рабиннің саусақ ізі

The Рабиннің саусақ ізі тағы бір хэш, ол кірісті көпмүшелік ретінде түсіндіреді, бірақ Галуа өрісі GF (2). Кірісті байттардың көпмүшесі ретінде қарастырудың орнына, биттердің көпмүшесі ретінде көрінеді және барлық арифметика GF (2) -де орындалады (ұқсас CRC32 ). Хэш - бұл көпмүшені GF (2) -ге төмендетілмейтін көпмүшелікке бөлудің нәтижесі. Рабиннің саусақ ізін тек кіру және шығу байтын пайдаланып жаңартуға болады, бұл оны айналмалы хэшке айналдырады.

Ол Rabin-Karp жол іздеу алгоритмімен бірдей автормен бөлісетіндіктен, оны басқа қарапайым, жай жылжымалы хэшпен түсіндіруге болады және бұл жай илектеу хэші де көпмүшелік болғандықтан, екі жылжымалы хэш те бір-бірімен қателеседі. Сақтық көшірме жасау бағдарламасы рестикалық Файлдарды бөлу үшін Rabin саусақ ізін пайдаланады, оның көлемі 512 байт пен 8MiB аралығында өзгереді.[2]

Циклдік полином

Циклдық көпмүшелік арқылы хэштеу[3]- кейде «Бужаш» деп те аталады - бұл қарапайым, бірақ көбейтуді болдырмайтын және пайдаланатын артықшылығы бар баррель ауысымдары орнына. Бұл формасы кестелік хэштеу: бұл кейбір хэш функциясы бар деп болжайды таңбалардан интервалдағы бүтін сандарға дейін . Бұл хэш-функция жай массив немесе а болуы мүмкін хэш-кесте таңбаларды кездейсоқ сандарға салыстыру. Функцияға рұқсат етіңіз циклдық екілік айналу (немесе дөңгелек ауысым ): ол биттерді солға қарай 1-ге айналдырып, ең соңғы битті бірінші позицияға итереді. Мысалы, . Келіңіздер биттік болыңыз эксклюзивті немесе. Хэш мәндері келесідей анықталады

мұндағы екілік дәрежеге көбейтуді екілік жылжу арқылы жүзеге асыруға болады. Нәтижесінде in шығады .

Хэш мәндерін жылжымалы түрде есептеу келесідей жүзеге асырылады. Келіңіздер алдыңғы хэш мәні. Айналдыру бір рет: . Егер жою керек таңба, оны айналдырыңыз рет: . Содан кейін жай орнатыңыз

қайда жаңа кейіпкер.

Циклдық көпмүшеліктермен хэштеу әмбебап немесе жұптық тәуелді емес: жай біріншісін сақтаңыз биттер. Яғни, нәтижені алыңыз және кез келгенін босату дәйекті биттер.[1] Іс жүзінде бұған бүтін санды бөлу арқылы қол жеткізуге болады .

Жылжымалы хэшті пайдалану арқылы мазмұнға негізделген кесу

Жылжымалы хэш функциясын пайдаланудың қызықты жағдайларының бірі - ол ағынның немесе файлдың мазмұнға негізделген динамикалық бөліктерін жасай алады. Бұл әсіресе үлкен файлдың тек өзгертілген бөліктерін желіге жіберу қажет болғанда және файлдың алдыңғы жағына қарапайым байт қосымшасы барлық бекітілген өлшемді терезелердің жаңартылуына әкеледі, ал шын мәнінде тек бірінші «кесек» өзгертілді.

Динамикалық кесектерді есептеудің қарапайым тәсілі - домаланған хэшті есептеу және егер ол үлгіге сәйкес келсе (төменгі сияқты) N биттердің барлығы нөлге тең). Бұл тәсіл файлдағы кез-келген өзгеріс тек оның ағымдағы және мүмкін келесі бөлігіне әсер ететіндігіне кепілдік береді, бірақ басқа ешнәрсе болмайды.

Шекаралары белгілі болған кезде, олардың қайсысы өзгертілгенін және желі арқылы тасымалдау қажеттілігін анықтау үшін бөліктерді олардың хэш мәндерімен салыстыру қажет.[4] Сақтық көшірме жасау бағдарламасы Шатыр файл ағындарын бөлу үшін теңшелетін кескін өлшемі бар Бужаш алгоритмін қолданады.[5]

Қозғалмалы қосынды пайдаланып мазмұнға негізделген кесу

Бірнеше бағдарлама, оның ішінде gzip (бірге - синхронды параметр) және rsyncrypto, осы нақты (өлшенбеген) қозғалмалы сомаға негізделген мазмұнға негізделген тілімдер жасаңыз:[6]

қайда

  • - байтпен аяқталатын 8196 байттың қосындысы (21 бит сақтауды қажет етеді),
  • байт файлдың,
  • төменгі 12 биттен тұратын «хэш мәні» болып табылады .

Терезені бір байтқа ауыстыру тек қосындыға жаңа таңбаны қосуды және қосындының ішіндегі ең көне таңбаны (енді терезеде емес) алып тастауды ғана қамтиды.

Әрқайсысы үшін қайда , бұл бағдарламалар файлды кесіп тастайды және . Бұл тәсіл файлдағы кез-келген өзгеріс тек оның ағымдағы және мүмкін келесі бөлігіне әсер ететіндігіне кепілдік береді, бірақ басқа бөлікке әсер етпейді.

Саусақ іздері мен жылдамдықты мазмұнға негізделген алгоритмнің жылдамдығы

Мазмұнды анықтау (CDC) алгоритмі мәліметтер ағынының байт-байт мәнін есептеп, хэш мәні алдын-ала анықталған мәнге сәйкес болған кезде мәліметтер ағынын бөліктерге бөлуі керек. Алайда, байт-байтты жолдармен салыстыру ауыр есептеуді енгізеді. FastCDC [7] мазмұнмен анықталған жаңа және тиімді тәсілді ұсынады. Ол жылдам айналмалы Gear алгоритмін қолданады [8], минималды ұзындықты өткізіп, бөлшектердің үлестірілуін қалыпқа келтіреді және CDC алгоритмін жылдамдату үшін әр уақытта екі байт айналдырады, бұл Рабинге негізделген CDC тәсілінен 10 есе жоғары өнімділікке қол жеткізе алады. [9]

Жалған кодтың негізгі нұсқасы келесідей:

алгоритм FastCDC
    енгізу: деректер буфері src,
           деректер ұзындығы n, 
    шығу: кесу нүктесі мен
    
    MinSize ← 2KB // бөлудің минималды мөлшері - 2 KB
    MaxSize ← 64KB // бөлудің максималды мөлшері 64 КБ
    фп0
    менMinSize
    Маска0x0000d93003530000LL
    
    // буфер өлшемі минималды бөлік өлшемінен аз
    егер nMinSize содан кейін
        қайту n
    егер nMaxSize содан кейін
        nMaxSize
     
    уақыт мен < n істеу
        фп ← (фп << 1 ) + Беріліс[src[мен]]
        егер !(фп & Маска) содан кейін
            қайту мен
   
    қайту мен

Мұндағы Gear массиві - алдын-ала есептелген хэштеу массиві. Мұнда FastCDC Gear хэштеу алгоритмін қолданады, ол жылжымалы хэштеу нәтижелерін тез есептей алады және хэштеу нәтижелерінің Rabin ретінде біркелкі үлестірілуін сақтайды. Дәстүрлі Rabin хэштеу алгоритмімен салыстырғанда ол әлдеқайда жылдам жылдамдыққа қол жеткізеді. Тәжірибелер көрсеткендей, ол біршама қысқа уақыт ішінде шамамен бірдей кесек мөлшерін бөле алады (рабинге негізделген кесектердің 1/10 бөлігі). [9]) мәліметтер ағынын сегментациялау кезінде.

Есептеудің күрделілігі

Барлық айналмалы хэш функциялары символдар саны бойынша сызықтық, бірақ олардың терезенің ұзындығына қатысты күрделілігі () өзгереді. Рабин-Карп прокаты екіге көбейтуді қажет етеді -бит сандары, бүтін көбейту ішінде .[10] Хэштеу нграмм циклдық көпмүшеліктерді сызықтық уақытта жасауға болады.[1]

Бағдарламалық жасақтама

Сондай-ақ қараңыз

Сыртқы сілтемелер

Сілтемелер

  1. ^ а б c Даниэль Лемир, Оуэн Касер: Рекурсивті n-грамманы хэштеу екіге бөлінбейді, ең жақсысы, Computer Speech & Language 24 (4), 698-710 беттер, 2010 ж. arXiv: 0705.4676.
  2. ^ «Пайдаланылған әдебиеттер - restic 0.9.0 құжаттамасы». restic.readthedocs.io. Алынған 2018-05-24.
  3. ^ Джонатан Д.Коэн, рекурсивті хэштеу функциялары n-Граммалар, ACM транс. Инф. Сист. 15 (3), 1997 ж.
  4. ^ Хорват, Адам (24.10.2012). «Rabin Karp жылжымалы хэші - алынған мазмұнға негізделген динамикалық өлшемдер».
  5. ^ «Деректер құрылымы және файл форматтары - Borg - Archiver 1.1.5 құжаттамасын көшіру». borgbackup.readthedocs.io. Алынған 2018-05-24.
  6. ^ «Рсинкрипто алгоритмі».
  7. ^ Ся, Вэнь; Чжоу, Юкун; Цзян, Хонг; Фэн, Дэн; Хуа, Ю; Ху, Ючонг; Лю, Цин; Чжан, Ючэн. «FastCDC: деректерді көшіруге арналған жылдам және тиімді мазмұнмен анықталған тәсіл». USENIX. Алынған 2020-07-24.
  8. ^ Ся, Вэнь; Цзян, Хонг; Фэн, Дэн; Тянь, Лей; Фу, Мин; Чжоу, Юкун (2014). «Ddelta: делупацияға негізделген жылдам дельтаны қысу тәсілі». Өнімділікті бағалау. 79: 258–272. дои:10.1016 / j.peva.2014.07.016. ISSN  0166-5316.
  9. ^ а б Ся, Вэнь; Цзоу, Сянюй; Цзян, Хонг; Чжоу, Юкун; Лю, Чуаньи; Фэн, Дэн; Хуа, Ю; Ху, Ючонг; Чжан, Ючэн (2020-06-16). «Деректерді көшіруге негізделген сақтау жүйелеріне арналған жылдам мазмұнды жобалау». Параллельді және үлестірілген жүйелердегі IEEE транзакциялары. 31 (9): 2017–2031. дои:10.1109 / TPDS.2020.2984632. S2CID  215817722. Алынған 2020-07-22.
  10. ^ М.Фюрер, жылдамырақ көбейту, STOC ’07, 2007 ж., 57–66 бб.