Negaidīta surogātpasta noteikšanas algoritmu izplatība

Ja vēlaties noskaidrot, vai divi surogātpasta e-pasta ziņojumi ir identiski, nesalīdzinot katru tajos esošo baitu (kas aizņemtu pārmērīgi daudz laika), jūs sagremot failu īsā virknē, ko sauc par kriptogrāfijas jaucējvērtība . Kriptogrāfiskās jaukšanas funkcijas būtība ir tāda, ka pat vismazākās izmaiņas failā radīs ļoti atšķirīgu jaucējvērtību, tāpēc ir viegli noteikt, vai divi faili ir identiski.

No Wikipedia: kriptogrāfijas jaucējfunkcija darbā. Ņemiet vērā, ka pat nelielas izmaiņas avota ievadē krasi maina iegūto izvadi.

Tas var izklausīties triviāli, taču tā nav: ja jums jau ir nevēlama faila piemērs — piemēram, surogātpasta e-pasta gabals — un vēlaties to salīdzināt ar miljoniem citu e-pasta ziņojumu, kas tiek straumēti caur jūsu serveriem, jums ir jāspēj ātri to identificēt. 40 ciparu virkņu salīdzināšana ir ievērojami vienkāršāka nekā miljoniem dzimumlocekļa tablešu e-pasta ziņojumu nolasīšana līdz galam.

Problēma ar kriptogrāfijas jaucējfunkcijām ir tāda, ka pat vismazākās izmaiņas avota failā rada jaucējvērtību, kas ir pilnīgi atšķirīga. Citiem vārdiem sakot, tie ir bezjēdzīgi, lai salīdzinātu failus, kas var būt funkcionāli identiski, bet tikai nedaudz atšķirīgi.

Viens no šīs problēmas risinājumiem ir tas, ko sauc par izplūdušo jaukšanu vai mainīgo jaucējkodu: tā vietā, lai jauktu tikai visu failu, algoritms nodrošina nepārtrauktu jaucējvērtību plūsmu ritošajam logam virs binārā [oriģinālā faila. ],saka Deivids Frenčs, vecākais pētnieks Kārnegija Melona Programmatūras inženierijas institūtā.

Salīdzinot jaucēju kopumu no diviem failiem, varat noteikt procentuālo atšķirību starp tiem.

Pieeja, kas vispārina... Viss?

Šeit izplūdušā jaukšana kļūst patiešām noderīga: pēkšņi jums ir vispārējas nozīmes metode ātrai salīdzināšanai. jebkura informācijas plūsma.

Tātad jūs redzat neskaidras jaucējzīmes, kas parādās visur. Lūk iepriekšminētā doktora Franča pūles lai izmantotu neskaidrus jaucējus, lai ātri noteiktu, vai fails lietotāja datorā ir vīruss vai cita ļaunprātīga programmatūra. Un šeit ir mēģinājums izmantot neskaidras jaucējzīmes, lai salīdzinātu uzmetuma gēnu secību viena mikroorganisma uz zināmu secību no radniecīgas būtnes. Tas ir milzīgi ģenētiķiem, kuriem ātrākais veids, kā savākt pietiekami precīzu genomu no iepriekš nesekvenētas būtnes, ir salīdzināt tās gēnu sekvencētos fragmentus ar zināmu secību.

Un vai esat kādreiz aizdomājies, kā Google atklāj satura dublikātu, lai tas varētu sniegt jums tikai visatbilstošākos rezultātus, nevis simtiem ziņu raksta vai uzziņu darba kopiju, kas neizbēgami nonāk internetā izplatītos slogos? Atkal neskaidra jaukšana ! Tas var pat atklāt identiskus dokumentus, kas tiek glabāti pilnīgi atšķirīgos formātos:

*Biežs gadījums ir viens un tas pats dokuments, bet dažādos formātos; šajos gadījumos mums būs pilnīgi atšķirīgi dokumenti binārā līmenī. Acīmredzams risinājums ir salīdzināt visu šo formātu vienkāršā teksta pārveidojumus, taču šie reklāmguvumi nekad nav identiski, jo dažādu formatēšanas elementu pārveidotāji (teksta rakstzīmes, diakritiskās zīmes, atstarpes, rindkopas utt.) tiek apstrādāti atšķirīgi. Šajā darbā mēs iepazīstinām ar iespēju izmantot tā saukto izplūdušo jaukšanu. Ideja ir izveidot failu (vai dokumentu utt.) pirkstu nospiedumus. Tādā veidā divu pirkstu nospiedumu salīdzinājums varētu sniegt mums aptuvenu vai attālumu starp diviem failiem, dokumentiem utt.

Pie velna, jūs varat pateikt, cik svarīga ir neskaidra jaukšana, jo Maikls Gregorijs Hoglunds no Montesereno, Kalifornijā tikko saņēma visaptverošs procesa patents , ko viņš sauc par digitālas DNS sekvences ģenerēšanu datu objektam. Pirms pamanāt, patentu trollis būs nopircis šo no Hoglundas, un tad var sākties īstā jautrība.

Izplūdušie jaucējfaili ir viens no neredzamajiem santehnikas elementiem, piemēram, Google izgudrotais MapReduce algoritms, kas ir pamatā gandrīz katram milzīgam tīmekļa pakalpojumam, kuru jūs varat iedomāties, un kas ir ļoti svarīgs mūsu atkarīgā globālā prāta darbībai.

Ikreiz, kad datoram ir jājautā, kura no šīm lietām nav līdzīga citai? Atbilde ir: jautājiet neskaidrai jaucējfunkcijai!

Sekojiet Mimsam Twitter vai sazinieties ar viņu pa e-pastu .

paslēpties