Billedbehandling

• Tutorial

I denne artikel vi taler om HEngine-algoritmen og implementering af en løsning på problemet med beregning af Hamming-afstanden på store mængder data.

Introduktion

Hamming-afstanden er antallet af forskellige positioner for strenge af samme længde. For eksempel HD( 1 00 , 0 01 ) = 2.

Problemet med at beregne Hamming-afstanden blev først stillet af Minsky og Papert i 1969, hvor problemet var at finde alle rækker fra en database, der er inden for en given Hamming-afstand til forespørgslen.

En opgave som denne er utrolig enkel, men at finde den effektiv løsning er stadig på dagsordenen.

Hamming-distancen er allerede ret meget brugt til forskellige opgaver, såsom søgning efter tætte dubletter, mønstergenkendelse, dokumentklassificering, fejlrettelse, virusdetektion osv.

For eksempel foreslog Manku og kolleger en løsning på problemet med duplikatklynger i webdokumentindeksering baseret på beregning af Hamming-afstanden.
Miller og venner foreslog også konceptet med at søge efter sange baseret på et givet lydfragment.
Lignende løsninger er blevet brugt til problemet med billedsøgning og nethindegenkendelse mv.

Beskrivelse af problemet

Der er en database binære strenge T, størrelse n, hvor længden af ​​hver linje m. Anmodet streng -en og den nødvendige Hamming-afstand k.

Opgaven handler om at finde alle strenge, der er inden for afstanden k.

Det oprindelige koncept for algoritmen betragter to varianter af problemet: statisk og dynamisk.

I et statisk problem er afstanden k forudbestemt.
- I dynamik er den nødvendige distance tværtimod ukendt på forhånd.

Artiklen beskriver kun løsningen på et statisk problem.

Beskrivelse af HEngine-algoritmen til en statisk opgave

Denne implementering fokuserer på at finde strenge indeni k <= 10.

Der er tre løsninger på et statisk problem: lineær scanning, forespørgselsudvidelse og tabeludvidelse.

I dette tilfælde under forespørgselsudvidelse Dette refererer til genereringen af ​​alle mulige strengvarianter, der passer inden for en given afstand for den originale streng.
Baseudvidelse data indebærer oprettelse af mange kopier af denne database, hvor enten alle mulige muligheder, der opfylder kravene til den nødvendige afstand, også genereres, eller dataene behandles på anden måde (mere om dette lidt senere.).

Hengine bruger en kombination af disse tre teknikker til effektivt at balancere mellem hukommelse og eksekveringstid.

Lidt teori

Algoritmen er baseret på en lille sætning, der siger følgende:

Hvis for to linjer -en Og b afstand HD( -en, b) <= k, så hvis vi deler linjerne -en Og b ind i understrenge ved hjælp af metoden rcut ved brug af segmenteringsfaktor
r >= ⌊k/2⌋ + 1
der vil helt sikkert være i det mindste q= r − ⌊k/2⌋ understrenge, når deres afstand ikke overstiger én, HD( -en jeg, b jeg)<= 1.

Udtræk af understrenge fra basisstrengen ved hjælp af metoden rcut udføres efter følgende principper:
Den navngivne værdi segmenteringsfaktor, som opfylder betingelsen
r >= ⌊k/2⌋ + 1

Første længde r − (m mod r) understreng vil have længden ⌊ m / r⌋, og de sidste m mod r understrenge ⌈ m/r⌉. Hvor m er længden af ​​strengen, ⌊ er afrundet til nærmeste bund, og ⌉ er afrundet til nærmeste over.

Nu det samme, kun med et eksempel:

Givet to binære strenge af længde m= 8 bit: A = 11110000 og B = 11010001, afstand mellem dem k = 2.
Valg af segmenteringsfaktor r= 2 / 2 + 1 = 2, dvs. der vil være i alt 2 understrenge i længden m/r= 4 bit.

A1 = 1111, a2 = 0000
b1 = 1101, b2 = 0001

Hvis vi nu beregner afstanden mellem de tilsvarende understrenge, så skal der som minimum ( q= 2 - 2/2 = 1) en understreng vil falde sammen, eller deres afstand vil ikke overstige en.

Hvad vi ser:
HD(a1; b1) = HD(1111; 1101) = 1
Og
HD(a2; b2) = HD(0000; 0001) = 1

Basisstrengens understrenge blev navngivet underskrifter.
Signaturer eller understrenge a1 og b1 (a2 og b2, a3 og b3 ..., a r og b r) hedder kompatibel med hinanden, og hvis antallet af forskellige bits ikke er mere end én, kaldes disse signaturer matchende.

Og hovedideen med HEngine-algoritmen er at forberede databasen på en sådan måde, at den finder matchende signaturer og derefter vælge de rækker, der er inden for den nødvendige Hamming-afstand.

Database forbehandling

Vi ved allerede, at hvis vi opdeler en streng korrekt i understrenge, så vil mindst én understreng matche den tilsvarende understreng, eller antallet af forskellige bits vil ikke overstige én (signaturerne vil matche).

Det betyder, at vi ikke skal foretage en fuldstændig søgning over alle rækker fra databasen, men først skal finde de signaturer, der matcher, dvs. understrenge vil afvige med maksimalt én.

Men hvordan søger man efter understrenge?

Den binære søgemetode burde gøre et godt stykke arbejde med dette. Men det kræver, at listen over strenge er sorteret. Men vi får flere understrenge fra én linje. For at udføre en binær søgning på en liste over understrenge skal hver sådan liste sorteres på forhånd.
Derfor foreslår dette en metode til at udvide databasen, dvs. oprette flere tabeller, hver for sin egen understreng eller signatur. (Denne tabel kaldes tabel over underskrifter. Og samlingen af ​​sådanne borde er sæt underskrifter).

Den originale version af algoritmen beskriver også omarrangering af understrenge, så de valgte understrenge er på førstepladsen. Dette gøres mere for at lette implementeringen og for yderligere optimering af algoritmen:

Der er en streng A, som er opdelt i 3 understrenge, a1, a2, a3, den komplette liste over permutationer vil være i overensstemmelse hermed:
a1, a2, a3
a2, a1, a3
a3, a1, a2

Disse signaturtabeller sorteres derefter.

Gennemførelse af søgning

På dette stadium, efter foreløbig behandling af databasen, har vi flere kopier af de sorterede tabeller, hver for sin egen underrække.

Det er klart, at hvis vi først vil finde understrenge, skal vi hente signaturer fra den anmodede streng på samme måde, som blev brugt til at oprette signaturtabellerne.

Vi ved også, at de påkrævede understrenge afviger med højst ét ​​element. Og for at finde dem skal du bruge forespørgselsudvidelsesmetoden.

Med andre ord, for den valgte delstreng er det nødvendigt at generere alle kombinationer, inklusive denne delstreng selv, hvor forskellen højst vil være ét element. Antallet af sådanne kombinationer vil være lig med længden af ​​understrengen + 1.

Sådanne handlinger skal udføres for alle underrækker og for alle tabeller.

Og til allersidst bliver du nødt til at filtrere de linjer fra, der ikke passer inden for den angivne Hamming-afstandsgrænse. De der. udfør en lineær søgning gennem de fundne strenge og lad kun de strenge, der opfylder betingelsen HD( -en, b) <= k.

Bloom filter

Forfatterne foreslår at bruge et Bloom-filter for at reducere antallet af binære søgninger.
Et Bloom-filter kan hurtigt afgøre, om en understreng er i en tabel med en lille procentdel af falske positive. Hvilket er hurtigere end tabelhash.

Hvis filteret før en binær søgning efter en understreng i en tabel returnerer, at understrengen ikke er i den tabel, så nytter det ikke noget at udføre søgningen.

Derfor skal du oprette et filter for hver signaturtabel.

Nu det samme, kun med et eksempel

Der er en database med binære strenge 8 bit lange:
11111111
10000001
00111110

Opgaven er at finde alle linjer, hvor antallet af forskellige bits ikke overstiger 2 til mållinjen 10111111.
Altså den nødvendige afstand k = 2.

1. Vælg en segmenteringsfaktor.
Ud fra formlen vælger vi segmenteringsfaktoren r= 2 og det betyder, at der kun vil være to understrenge fra en linje.

2. Opret et sæt signaturer.
Da antallet af understrenge er 2, skal der kun oprettes 2 tabeller:
T1 og T2

3. Vi gemmer understrengene i de relevante tabeller, mens vi bevarer et link til den originale kilde.

T1 T2
1111 1111 => 11111111
1000 0001 => 10000001
0011 1110 => 00111110

4. Sorter tabellerne. Hver enkelt for sig.
T1
0011 => 00111110
1000 => 10000001
1111 => 11111111

T2
0001 => 10000001
1110 => 00111110
1111=> 11111111

Dette afslutter forbehandlingen. Og lad os starte søgningen.

1. Vi opnår signaturerne af den ønskede streng.
Den søgte streng 10111110 er opdelt i signaturer. Det viser sig henholdsvis 1011 og 1100, det første for det første bord og det andet for det andet.

2. Generer alle kombinationer, der adskiller sig med én.
Antallet af muligheder vil være 5.

2.1 For den første understreng 1011:
1011
0 011
11 11
100 1
1010

2.2 For den anden understreng 1100:
1100
0 100
10 00
111 0
1101

3. Binær søgning.

3.1 For alle genererede varianter af den første delstreng 1011 udfører vi en binær søgning i den første tabel for at finde et komplet match.

1011
0011 == 0011 => 00111110
1111 == 1111 => 11111111
1001
1010

To understrenge fundet.

3.2 Nu, for alle varianter af den anden understreng 1100, udfører vi en binær søgning i den anden tabel.

1100
0100
1000
1110 == 1110 => 00111110
1101

En understreng fundet.

4. Kombination af resultaterne til én liste:
00111110
11111111

5. Kontroller lineært for overensstemmelse og filtrer dem fra, der ikke matcher betingelsen<= 2:

HD(10111110; 00111110) = 1
HD(10111110; 11111111) = 2

Begge strenge opfylder betingelsen om, at ikke mere end to elementer er forskellige.

Selvom en lineær søgning udføres på dette stadium, forventes det, at listen over kandidatstrenge slet ikke vil være stor.
Under forhold, hvor antallet af kandidater er stort, foreslås det at anvende den rekursive version af HEngine.

Klart

Figur 1 viser et eksempel på, hvordan søgealgoritmen fungerer.
For en linjelængde på 64 og en afstandsgrænse på 4 er segmenteringsfaktoren 3, svarende til kun 3 delstrenge pr. linje.
Hvor T1, T2 og T3 er signaturtabeller, der kun indeholder understrenge B1, B2, B3, 21, 21 og 22 bit lange.

Den anmodede streng er opdelt i understrenge. Dernæst genereres en række signaturer for de tilsvarende understrenge. For den første og anden signatur vil antallet af kombinationer være 22. Og den sidste signatur giver 23 muligheder. Til sidst udføres en binær søgning.

Fig. 1. En forenklet version af behandling af forespørgsler til signaturtabeller.

resultater

Gennemsnitlig kompleksitet af en sådan algoritme O(P* (log n+ 1)), hvor n er det samlede antal rækker i databasen, log n+ 1 binær søgning, og P- antal binære søgninger: i vores tilfælde beregnes det som antallet af kombinationer pr. tabel ganget med antallet af tabeller: P = (64 / r + 1) * r

I ekstreme tilfælde kan kompleksiteten overstige lineær kompleksitet.

Det bemærkes, at denne tilgang bruger 4,65 mindre hukommelse og er 16 % hurtigere end det tidligere arbejde beskrevet i . Og er den hurtigste måde, man i øjeblikket kender til at finde alle rækker inden for en given grænse.

Implementering

Alt dette er bestemt fristende, men før du rent faktisk rører ved det, er det svært at vurdere skalaen.
En Hengine-prototype blev skabt og testet på tilgængelige reelle data.

Tests$ ./matches 7 data/db/table.txt data/query/face2.txt Læsning af datasættet ........ færdig. 752420 db hashes og 343 forespørgsels hashes. Bygning med 7 hammerafstand bundet ...... færdig. Byggetid: 12.964 sekunder. Søgning efter HEngine-matches ....... fandt 100 samlede resultater. Hengine-forespørgselstid: 0,1 sekunder. Lineær forespørgselstid: 6,828 sekunder

Resultaterne var opmuntrende, fordi søgning efter 343 hashes fra en database med 752420 tager ~0,1 sekunder, hvilket er 60 gange hurtigere end en lineær søgning.

Det ser ud til, at vi kunne stoppe her. Men jeg ville virkelig prøve at bruge det på en eller anden måde i et rigtigt projekt.

Fra PHP ring blot:
$list = file_get_contents("http://fcgi.local/?" . $hashes);
Hvilket returnerer resultatet på ~0,5 sekunder. Når en lineær søgning tager 9 sekunder, og gennem forespørgsler til MySQL mindst 20 sekunder.

Tak til alle, der fuldførte det.

Links

M. Minsky og S. Papert. Perceptroner. MIT Press, Cambridge, MA, 1969.
G.S. Manku, A. Jain og A.D. Sarma. Registrering af næstenduplikater til webcrawling. I Proc. 16. WWW, maj 2007.
M.L. Miller, M.A. Rodriguez og I.J. Cox. Lydfingeraftryk: Søgning efter nærmeste nabo i højdimensionelt binært rum. I MMSP, 2002.
M.L. Miller, M.A. Rodriguez og I.J. Cox. Lydfingeraftryk: søgning efter nærmeste nabo i højdimensionelle binære rum. Journal of VLSI Signal Processing, Springer, 41(3):285–291, 2005.
J. Landr ́e og F. Truchetet. Billedsøgning med binær hammerafstand. I Proc. 2. VISAPP, 2007.
H. Yang og Y. Wang. En LBP-baseret metode til ansigtsgenkendelse med begrænsning af hammingsafstand. I Proc. Fjerde ICIG, 2007.
B. Bloom. Mellemrum/tid afvejninger i hash-kodning med tilladte fejl. Communications of ACM, 13(7):422-426, 1970.
Alex X. Liu, Ke Shen, Eric Torng. Storskala Hamming Distance Query Processing. ICDE-konference, side 553 - 564, 2011.
github.com/valbok/HEngine Min implementering af HEngine i C++ Tilføj tags

Hammerafstand

Den amerikanske matematiker Hamming undersøgte, hvad denne kode afhænger af, om den vil opdage fejl, og hvornår den kan rette dem. Intuitivt er det klart, at dette afhænger af, hvordan kodeordene er adskilt fra hinanden, og hvor mange fejl der kan forekomme i det transmitterede ord. Vi vil nu formalisere følgende idé. Ved kodning er det nødvendigt at koordinere antallet af mulige fejl i det transmitterede kodeord, således at når det transmitterede kodeord ændres, forbliver det tættere på det originale kodeord end på noget andet kodeord.

Definition 13.1. Overvej mængden af ​​alle binære ord i alfabetet I= (0,1) længde T afstand d(x, på), hvilket er lig med antallet af ikke-matchende positioner for disse ord. For eksempel For ord x = 011101, på= 101010 afstand er d(x, y) = 5. Denne afstand kaldes Hammerafstand .

Det kan vises, at Hamming-afstanden opfylder aksiomer for metrisk rum:

1) d(x, på) ≥ 0, d(x, på) = 0 hvis og kun hvis x = y;

2) d(x, y) = d(y, x);

3) d(x, på) ≤ d(x, z) + d(z, på) - trekantulighed.

Sætning 13.1(om detektionskode). Koden detekterer i det tilfælde, hvor det transmitterede ord ikke indeholder mere end k

d(b 1, b 2) ≥ k+ 1.

Sætning 13.2(om rettelseskoden.). Koden retter alle fejl i det tilfælde, hvor det transmitterede ord ikke indeholder mere end k fejl, hvis og kun hvis den mindste afstand mellem kodeord

d(b 1, b 2) ≥ 2k+ 1.

Bevis. Beviserne for disse teoremer er ens. Derfor vil vi kun bevise den sidste sætning.

Tilstrækkelighed. Lad os for alle kodeord, vi har d(b 1, b 2) ≥ 2k+ 1. Hvis, når du sender et kodeord b 1 skete der ikke mere k fejl, så for det accepterede ord med vi har d(b 1, c) ≤ k. Men fra trekanten ulighed for ethvert andet kodeord b 2 vi har d(b 1, Med) + d(c, b 2) ≥ d(b 1, b 2) ≥ 2 k+ 1. Derfor er afstanden fra det modtagne ord til ethvert andet kodeord d(c, b 2) ≥ k+ 1, dvs. mere end tidligere b 1. Derfor ifølge det accepterede ord Med du kan helt sikkert finde det nærmeste kodeord b 1 og derefter afkode den.

Nødvendighed. Fra det modsatte. Antag, at minimumsafstanden mellem kodeord er mindre end 2 k+ 1. Så er der to kodeord, afstanden mellem dem vil være d(b 1, b 2) ≤ 2 k. Lad, når du overfører ordet b 1 accepteret ord Med er placeret mellem ordene b 1, b 2i har præcis k fejl. Derefter d(c, b 1) = k, d (c, b 2) = d(b 1, b 2) – d(c, b 1) ≤ k. Ud fra ordet c er det således umuligt entydigt at rekonstruere kodeordet, der blev transmitteret, b 1 eller b 2. Vi kom til en modsigelse.

Eksempel 13.3 . Overvej følgende fem-bit koder for ord med længde 2 i alfabetet I = {0,1}:

b 1= K(00) = 00000, b 2= K(01) = 01011,

b 3= K(10) = 10101, b 4= k(11) =11110.

Minimumsafstanden mellem forskellige kodeord er d(bi, bj) = 3. I kraft af den første sætning om detektionskoden er denne kode i stand til ikke at detektere mere end to fejl i et ord. I kraft af den anden sætning er koden i stand til at rette højst én fejl i et ord.

Gruppekoder

Lad os se nærmere på koderne for ord i alfabetet I= (0, 1). Hvis for ord af længde T kodeord af længde bruges n, så kalder vi sådanne koder ( T , P)-koder. Samlet ordlængde m er lig med 2 m. At indstille ( T , P)-kode, kan du liste kodeord for alle mulige ord af længde m, som i det foregående eksempel. En mere økonomisk måde at specificere kodeord på er en matrixopgave.

I dette tilfælde er den genererende matrix specificeret G= ∣∣ gij∣∣ rækkefølge T × P fra 0 og 1. Kodeord bestemmes hver gang for ord EN = EN 1-en 2... på ved at gange dette ord til venstre, som en vektor, med den genererende matrix

Her er addition defineret modulo 2. For at forskellige ord skal svare til forskellige kodeord, er det nok at have i matrixen G enhedsbasis mindre af ordre T, for eksempel den yderste venstre.

Eksempel 13.4 . Overvej den genererende matrix

Denne matrix definerer (3, 4) koden. I dette tilfælde er de første tre tegn i kodeordet informative, og det fjerde er et kontroltegn. Det er lig med 0, hvis der er et lige antal enere i kildeordet, og 1, hvis der er et ulige antal enere. For eksempel for ordet EN= 101 kode vil være b= aG= 1010. Den mindste Hamming-afstand mellem kodeord er d(bi, bj) = 2. Derfor er dette kode, der registrerer en engangsfejl.

Definition 13.2. Koden hedder gruppe , hvis sættet af alle kodeord danner en gruppe. Antallet af enheder i ordet a kaldes vægte ord og betegnes If b- kodeord og ord modtaget i kommunikationskanalen Med = b + e, så ordet e hedder vektor af fejl .

Sætning 13.3. Lad der være en gruppe ( T , P)-kode. Derefter den kommutative gruppe TIL af alle kodeord er en undergruppe af den kommutative gruppe MED alle ord af længde P, som kan modtages i kommunikationskanalen. Den mindste afstand mellem kodeord er lig med den mindste vægt af et kodeord, der ikke er nul og

Overvej faktorgruppen S/K. Cosets her vil blive bestemt af skiftet e + b, b∈ K.

Som repræsentant for coset-klassen vælger vi det element med mindst vægt. Vi vil kalde sådanne elementer tilstødende klasseledere .

Hvis ledere fortolkes som fejlvektorer, så er hver tilstødende klasse et sæt forvrængede ord i en kommunikationskanal med en fast fejlvektor, især når e= 0 har vi en tilstødende klasse af ord uden forvrængninger, dvs. mængden af ​​alle kodeord. Processen med ordkorrektion og afkodning Med består i at søge efter den tilstødende klasse, som ordet tilhører Med = e + b. Fejlvektor e bestemmer antallet og placeringen af ​​fejl, kodeord b bestemmer rettelsen af ​​det modtagne ord.

For at lette søgningen efter et coset og dermed fejlvektoren foreslog Hamming at bruge gruppekoder med specielle genereringsmatricer.

Hamming koder

Lad os overveje konstruktionen af ​​Hamming ( T , P)-kode med den mindste kodeordsvægt lig med 3, dvs. en kode, der retter en fejl.

Lad os sætte P = 2 r– 1 og lad hvert kodeord indeholde r kontroltegn, og T tegn ( T = P – r= 2 r– 1– r) - informativ, r≥ 2, for eksempel (1, 3) kode, (4, 7) kode osv. Desuden i hvert kodeord b= b 1b 2... b p symboler med indekser lig med en potens på 2 vil være kontrolsymboler, og resten vil være informationssymboler. For eksempel for en (4, 7) kode i kodeordet b= b 1b 2b 3b 4b 5b 6b 7 tegn b 1b 2b 4 vil være kontrol dem, og symbolerne b 3b 5b 6b 7- oplysende. For at specificere generatormatrixen G Hammings ( T , P)-kode, overvej hjælpematrixen M bestille r× P, Hvor P = 2 r– 1, sådan at der i hver j matrix kolonne M der vil være binære symboler j, for eksempel for (4, 7)-koden matrixen M vil være 3 × 7:

Vi definerer mængden af ​​alle kodeord som mængden af ​​løsninger til et homogent system af lineære algebraiske ligninger af formen

b MT= 0.

For eksempel, for en (4, 7) kode ville et sådant system være:

Lad os vælge en naturlig basis mindre af systemet b MT= 0, stående i kolonner med tal svarende til potensen 2. Således opdeler vi variablerne i basis (kode) og fri (information). Nu, efter at have defineret gratis variabler, er det nemt at få grundlæggende. Lad os finde det grundlæggende system m= P – r løsninger af dette homogene system. Så er enhver løsning til systemet en lineær kombination af disse m beslutninger. Skriv derfor linje for linje m løsninger af grundsystemet i form af en matrix G størrelse m× P, får vi den genererende matrix for Hamming-gruppen ( T , P) kode, for eksempel for en (4, 7) kode, vil det grundlæggende system af løsninger være 4 = 7 – 3 af følgende løsninger af et homogent system:

g 1= 1110000, g 2= 1001100, g 3= 0101010, g 4= 1101001.

Enhver lineær kombination af disse løsninger vil være en løsning, dvs. et kodeord. Lad os sammensætte en genererende matrix ud fra disse grundlæggende løsninger

Nu ifølge ethvert ord EN længde T= 4 let at beregne kodeord b længde P= 7 ved hjælp af generatormatricen b= aG. Samtidig er symbolerne b 3, b 5, b 6, b 7 vil være oplysende. De falder sammen med EN 1, EN 1, EN 3, EN 4.Symboler b 1, b 2, b 4 vil være kontrol.

Konklusion. Hamming-koder er praktiske, fordi cosets let bestemmes under afkodning. Lad ordet modtaget over kommunikationskanalen være Med = e + b, Hvor e- fejl, b- et kodeord. Derefter ganges det med hjælpematrixen cMT= (e + b)MT= eM T. Hvis eM T= 0, derefter ordet Med- kode og vi overvejer: der er ingen fejl. Hvis eM T≠ 0, derefter ordet e definerer en fejl.

Husk, at de konstruerede Hammings ( T , P)-kode identificerer én fejl. Derfor fejlvektoren e indeholder en enhed i jeg stillinger. Desuden antallet jeg position opnås i binær repræsentation som resultat eM T, sammenfaldende med jeg matrix kolonne M. Det er tilbage at ændre symbolet jeg i ordet c modtaget over kanalen, streg kontroltegnene ud og skriv det afkodede ord ned.

Lad for eksempel det accepterede ord være Med= 1100011 for (4, 7) Hamming-koden. Lad os gange dette ord med matrixen M T. Vi får

(1100011)M T=(010).

Derfor er der en fejl i det andet tegn. Derfor bliver kodeordet b= 1000011. Overstreg kontroltegnene b 1, b 2, b 4.Det afkodede ord vil være EN = 0011.

Selvfølgelig, hvis fejlen blev lavet i mere end ét tegn, så vil denne kode ikke rette den.

I Stefan Zweigs bog "Humanity's Finest Hours" er der en vidunderlig historie "The Genius of One Night" om den franske hærofficer Rouget de Lisle, som skrev den berømte "La Marseillaise" i løbet af en nat i den inspirationshede, der greb ham. Dette var i 1792 i det revolutionære Marseille. Sangen spredte sig over hele Frankrig i løbet af få dage, vandt hurtigt enorm popularitet over hele verden og blev efterfølgende nationalsangen for den franske republik. Historien har bevaret navnet Rouget i eftertidens hukommelse takket være denne enkeltsang.

I analogi kan Richard Hamming kaldes et "geni af én idé." Han formulerede det i 1950 i sin eneste videnskabelige artikel om fejlkorrektionskoder. Artiklen indeholdt konstruktionen af ​​en blokkode, der korrigerer enkelte fejl, der opstår under meddelelsestransmission.

Richard Hamming beskæftigede sig konstant med aktiv videnskabelig forskning, men hans eneste arbejde inden for informationsteorien, der målt i volumen udgør en ubetydelig procentdel af hans videnskabelige arbejde, blev berømt. Denne artikel fik hurtigt verdensomspændende berømmelse og bragte ham velfortjent berømmelse.

Ligesom Faradays og Maxwells opdagelser blev fulgt af adskillige opfindelser inden for telekommunikation, der ændrede vores liv, så åbnede der sig nye muligheder efter Claude Shannon og Vladimir Kotelnikovs skabelse af informationsteorien, teorien om potentiel støjimmunitet. udvikling af telekommunikation. En af de vigtigste dele af informationsteori er kodningsteori, hvis grundlag blev lagt af Hamming.

Shannon konstaterede, at information kan transmitteres fejlfrit over en kommunikationskanal, hvis transmissionshastigheden ikke overstiger dens kapacitet. Shannons bevis var dog ikke konstruktivt. Senere undersøgelser af ham og en anden amerikansk videnskabsmand S. O. Rice viste, at næsten enhver tilfældigt udvalgt kode gør det muligt at opnå den teoretiske grænse for støjimmunitet for modtagelse af beskeder. Imidlertid havde en sådan kode en høj afkodningskompleksitet: antallet af operationer, der kræves for at afkode den modtagne kodekombination, steg eksponentielt med dens længde.

Hamming var den første til at foreslå en konstruktiv metode til at konstruere koder med redundans og simpel afkodning. Hans arbejde forudbestemte retningen for det meste af arbejdet på dette område, der fulgte senere.

Til hans ære etablerede Institute of Electrical and Electronics Engineers en medalje for at anerkende videnskabsmænd, der har ydet betydelige bidrag til informationsteori.

Koder, der er i stand til at rette fejl (i kommunikationskanaler i digitale computere osv.) under signalbehandling, blev foreslået af Hamming allerede før 1948, hvor Shannons berømte artikel "Mathematical Theory of Communication" blev offentliggjort, som lagde et solidt grundlag for teorien i denne felt områder.

I dette papir beskrev Shannon, med henvisning til forskning udført i 1947 af hans Bell Labs-kollega Richard Hamming, som et eksempel en simpel kode med længde 7, der korrigerede alle enkeltfejl. Offentliggørelsen af ​​Hammings originale materiale blev forsinket til april 1950 af patentmæssige årsager. Det skal bemærkes, at eksemplet på fejlkorrigerende kode givet i den nævnte artikel af Shannon startede forskningen af ​​en anden amerikansk videnskabsmand, M. E. Golay. Golay, uafhængigt af Hamming, opdagede koder, der retter enkelte fejl. I 1949 (dvs. før Hamming) udgav han en kort note (kun en halv side) om sine resultater i Proceedings of IEEE. I denne note betragtede han ikke kun binære koder, men også generelle koder, hvis kombinationer hører til et endeligt felt (et matematisk sæt af elementer med visse operationer med addition, subtraktion, division og multiplikation) med pn-elementer (p er et primtal , og n er et heltal).

Det skal bemærkes, at en række grundlæggende ideer om kommunikationsteori var kendt som private matematiske resultater, selv før de begyndte at blive anvendt af videnskabsmænd, der løser problemer med at transmittere beskeder via kommunikationskanaler. I sin bog "Algebraic Coding Theory" kom en fremtrædende amerikansk ekspert inden for kodningsteori, E. Berlekamp, ​​med en meget interessant bemærkning. Han bemærkede, at designet af Hamming-koder blev beskrevet i en anden sammenhæng tilbage i 1942 af den berømte amerikanske matematiker R. A. Fisher, i et værk, der var helliget teorien om faktoranalyse (en af ​​grenene af matematisk statistik) og dens forbindelse med den matematiske statistik. teori om grupper. V. A. Kotelnikovs teorem, der indikerer muligheden for at repræsentere analoge signaler i digital form, blev i øvrigt også opdaget som et af de delvise matematiske resultater af teorien om funktionsinterpolation tilbage i det tidlige tyvende århundrede af engelske matematikere E. T. og J. M. Whitker. Det skal understreges, at hverken Fisher eller de nævnte engelske videnskabsmænd forbandt deres resultater med de vigtigste problemer for den moderne verden med at overføre information gennem kommunikationskanaler.

Wolfgang Goethe sagde: ”Det er ikke nok kun at få viden; Jeg skal finde en app til ham. Det er ikke nok bare at ønske; skal gøre". For teori og teknologi... kommunikation er Kotelnikovs teorem og Hamming-koder af enestående betydning, da det var takket være dem, at der åbnede sig en klar udsigt til at skabe digitale systemer for ingeniører, som i slutningen af ​​det tyvende århundrede revolutionerede telekommunikation og derfor de kaldes med rette efter disse videnskabsmænds navne.

Efter at være blevet en katalysator, der accelererede udviklingen af ​​kodningsteori, tiltrak Hammings artikel det videnskabelige samfunds opmærksomhed. I alle lærebøger kaldes denne klasse af koder for Hamming-koder, og præsentationen af ​​kodningsteori begynder med en beskrivelse af deres konstruktion. Tilsyneladende ville det stadig være mere retfærdigt at kalde disse koder Hamming-Golay-koder, i betragtning af at Golay kom til de samme ideer som Hamming uafhængigt og udgav dem tidligere. At hans artikel ikke tiltrak sig den opmærksomhed, den fortjener, skyldes højst sandsynligt tilfældigheder.

Sammenlignet med Shannons teori var de koder, Hamming introducerede, skuffende svage. Hammings almindelige metoder til at konstruere fejlkorrigerende koder var dog af fundamental betydning. De demonstrerede for ingeniører den praktiske mulighed for at nå de grænser, der er angivet af informationsteoriens love. Disse koder har fundet praktisk anvendelse i skabelsen af ​​computersystemer. Hammings papir førte også til en løsning på problemet med tættere pakning for begrænsede felter. Han indførte i videnskabelig brug de vigtigste begreber inden for kodningsteori - Hamming-afstanden mellem kodekombinationer i et vektorrum, defineret for binære koder som antallet af positioner af disse kombinationer med forskellige symboler, og Hamming-grænserne for blokkens korrektionsevne. rette koder. Hamming-grænsen for binære koder beregnes ved hjælp af følgende formel:

I dette udtryk kan antallet af fejl e korrigeres med en korrigerende blokkode af længden N, der har M kodekombinationer (CjN er den binomiale koefficient).

Hammings arbejde spillede en nøglerolle i den efterfølgende udvikling af kodningsteori og stimulerede omfattende forskning udført i de efterfølgende år. I 1956 var David Slepyan den første til at præsentere teorien om paritetskontrolkoder på et seriøst matematisk grundlag. Et stort skift inden for kodningsteorien skete, da den franske videnskabsmand A. Hoquenghem (1959) og amerikanerne R. K. Bose og D. K. Roy-Chowdhury (1960) fandt en stor klasse af koder (BCH-koder), der korrigerer multiple fejl. Amerikanske forskere I. S. Reed og G. Solomon (1960) fandt en klasse af koder for ikke-binære kanaler relateret til BCH-koder.

I 1980 skrev Hamming en genial lærebog, "Coding Theory and Information Theory", som blev oversat til russisk i 1983. Denne bog er, ligesom hans andre værker, kendetegnet ved originaliteten af ​​formuleringen af ​​spørgsmål, populariteten af ​​præsentationen, en dyb forståelse af praktiske problemer, rigtigheden og rimelig grad af stringens i den matematiske fortolkning af de rejste spørgsmål. Præsentationen af ​​materialet er struktureret på en sådan måde, at læseren intuitivt forstår, hvorfor denne eller hin sætning er sand

På et sæt binære ord af længde m afstand d(a,b) mellem ordene a og b er antallet af ikke-matchende positioner af disse ord, for eksempel: afstanden mellem ordene a = 01101 og b = 00111 er 2.

Begrebet defineret på denne måde kaldes Hamming-afstanden.

Den opfylder følgende afstandsaksiomer:

1) d(a,b)  0 og d(a,b)=0 hvis og kun hvis a = b;

2) d(a,b) = d(b,a);

3) d(a,b) + d(b,c)  d(a,c) (trekantulighed).

Vægten w(a) af et ord a er antallet af ener blandt dets koordinater. Så er afstanden mellem ordene a og b vægten af ​​deres sum a b: d(a,b)=w(a b) , hvor symbolet  angiver operationen af ​​koordinatmæssig addition modulo 2. Intuitivt er koden bedre egnet til fejldetektion og korrektion, jo mere forskellige kodeordene er. Begrebet Hamming-afstand giver os mulighed for at afklare dette.

Sætning For at en kode kan detektere fejl i k (eller færre) positioner, er det nødvendigt og tilstrækkeligt, at den mindste afstand mellem kodeord er  k + 1.

Beviset for denne sætning svarer til beviset for følgende udsagn.

Sætning. For at koden kan rette alle fejl i k (eller færre) positioner, er det nødvendigt og tilstrækkeligt, at den mindste afstand mellem kodeord er  2k + 1.

32. Sætning om koders korrigerende evne.

Koder, der automatisk kan rette fejl, kaldes selvkorrigerende. For at bygge en selvkorrigerende kode designet til at rette enkelte fejl, er et kontrolciffer ikke nok. Som det fremgår af det følgende, skal antallet af kontrolbit k vælges således, at uligheden 2k≥k+m+1eller k≥log2(k+m+1) er opfyldt, hvor m er antallet af grundlæggende binære bits. af kodeordet. I øjeblikket er binære blokkorrektionskoder af størst interesse. Ved brug af sådanne koder transmitteres information i form af blokke af samme længde, og hver blok kodes og afkodes uafhængigt af hinanden. I næsten alle blokkoder kan tegn opdeles i information og verifikation.

De vigtigste egenskaber ved selvkorrigerende koder er:

1. Antal tilladte og forbudte kombinationer. Hvis n er antallet af symboler i blokken, r er antallet af kontrolsymboler i blokken, k er antallet af informationssymboler, så er 2n antallet af mulige kodekombinationer, 2k er antallet af tilladte kodekombinationer, 2n −2k er antallet af forbudte kombinationer.

2. Kode redundans. Værdien rn kaldes redundansen af ​​korrektionskoden.

3. Minimum kodeafstand. Den mindste kodeafstand d er det mindste antal forvrængede symboler, der kræves for at skifte fra en tilladt kombination til en anden.

4. Antal fejl opdaget og rettet. Hvis g er antallet af fejl, som koden kan rette, så er det nødvendigt og tilstrækkeligt, at d≥2g+1

5. Korrigerende muligheder for koder.

33. Matrixkodning. Gruppekoder.

Når kodningsskemaet eksplicit specificeres i ( m, n)-kode skal angive 2 m kodeord, hvilket er meget ineffektivt.

En økonomisk måde at beskrive et kodningsskema på er matrixkodningsteknikken.

Tidligere blev hvert indkodningsskema beskrevet af tabeller, der specificerede et kodeord af længde n for hvert kildeord af længde m. For lange blokke kræver denne metode en stor mængde hukommelse og er derfor upraktisk. For eksempel for ( 16, 33 ) kode vil kræve 33 * 2 16 = 2.162.688 bit.

Kræver meget mindre hukommelse matrix kodning. Lade E dimensionsmatrix m×n, bestående af elementer e ij , hvor jeg er linjenummeret, og j - kolonnenummer. Hvert af matrixelementerne e ij kan være enten 0 eller 1. Kodning implementeres af operationen b = aE eller hvor kodeord betragtes som vektorer, dvs. som rækkematricer af størrelse 1×n.

Kodning bør ikke tildele det samme kodeord til forskellige kildemeddelelser. En enkel måde at opnå dette på er at m matrix søjler dannede en enhedsmatrix. Når en hvilken som helst vektor multipliceres med identitetsmatrixen, opnås den samme vektor; derfor vil forskellige meddelelsesvektorer svare til forskellige vektorer af den systematiske kode.

Matrixkoder kaldes også lineære koder. Til lineær (n − r, n)-koder med minimum Hamming-afstand d eksisterer Plotkin nedre bund (Plotkin) for det mindste antal kontrolbits r på n³ 2d − 1,

binær ( En m, n) kode kaldes en gruppekode, hvis dens kodeord danner en gruppe.

Bemærk, at mængden af ​​alle binære ord med længden m danner en kommutativ gruppe med operationen af ​​koordinatmæssig addition modulo 2, hvori relationen a a gælder. Følgelig er sættet af meddelelsesord a med længden m en kommutativ gruppe.

Blokkode kaldes gruppe, hvis dets kodeord danner en gruppe.

Hvis koden er en gruppekode, så er den mindste afstand mellem to kodeord lig med den mindste vægt af det ikke-nul ord.

Dette følger af forholdet d(b jeg , b j ) = w(b jeg + b j ).

Når du bruger en jokerkode, bliver de og kun de fejl, der svarer til fejlstrenge, der nøjagtigt svarer til kodeordene, uopdaget.

Sådanne fejllinjer oversætter et kodeord til et andet.

Derfor er sandsynligheden for, at en fejl forbliver uopdaget, lig med summen af ​​sandsynligheden for alle fejlstrenge, der er lig med kodeord.

Sæt af alle binære ord a = a 1 ... a m længde m danner en abelsk (kommutativ) gruppe med hensyn til bitvis addition.

Lade E - kodning m×n-en matrix, der har m × m- en submatrix med en ikke-nul determinant, for eksempel identitet. Derefter kortlægningen a → a E oversætter en gruppe af alle binære ord af længde m til en gruppe kodeord af længde n.

Lad os antage, at Så for vi får

dvs. Derfor en en-til-en kortlægning af en gruppe af binære ord af længde m ved hjælp af en given matrix E bevarer egenskaberne for en gruppeoperation, hvilket betyder, at kodeordene danner en gruppe.

Gruppekodeegenskab: den mindste kodeafstand mellem kodevektorer er lig med minimumsvægten af ​​vektorer, der ikke er nul. Vægten af ​​kodevektoren er lig med antallet af ener i kodekombinationen.

Det er praktisk at specificere gruppekoder ved hjælp af matricer, hvis dimension er bestemt af parametrene k og n. Antallet af rækker er k og antallet af kolonner er n = k+m.

Koderne genereret af disse matricer kaldes (n, k)-koder, og de tilsvarende matricer kaldes generatorer (generatorer).

Denne artikel vil diskutere HEngine-algoritmen og implementeringen af ​​en løsning på problemet med at beregne Hamming-afstanden på store mængder data.

Introduktion

Hamming-afstanden er antallet af forskellige positioner for strenge af samme længde. For eksempel HD(100, 001) = 2.

Problemet med at beregne Hamming-afstanden blev først stillet af Minsky og Papert i 1969, hvor problemet var at finde alle rækker fra en database, der er inden for en given Hamming-afstand til forespørgslen.

En sådan opgave er usædvanlig enkel, men søgen efter dens effektive løsning er stadig på dagsordenen.

Hamming distance er allerede ret meget brugt til forskellige opgaver, såsom at finde tætte dubletter, mønstergenkendelse, dokumentklassificering, fejlretning, virusdetektion mv.

For eksempel foreslog Manku og kolleger en løsning på problemet med duplikatklynger i webdokumentindeksering baseret på beregning af Hamming-afstanden.
Miller og venner foreslog også konceptet med at søge efter sange baseret på et givet lydfragment.
Lignende løsninger er blevet brugt til problemet med billedsøgning og nethindegenkendelse mv.

Beskrivelse af problemet

Der er en database med binære strenge T, størrelse n, hvor længden af ​​hver linje m. Anmodet streng -en og den nødvendige Hamming-afstand k.

Opgaven handler om at finde alle strenge, der er inden for afstanden k.

Det oprindelige koncept for algoritmen betragter to varianter af problemet: statisk og dynamisk.

I et statisk problem er afstanden k forudbestemt.
- I dynamik er den nødvendige distance tværtimod ukendt på forhånd.

Artiklen beskriver kun løsningen på et statisk problem.

Beskrivelse af HEngine-algoritmen til en statisk opgave

Denne implementering fokuserer på at finde strenge indeni k <= 10.

Der er tre løsninger på et statisk problem: lineær scanning, forespørgselsudvidelse og tabeludvidelse.

I dette tilfælde under forespørgselsudvidelse Dette refererer til genereringen af ​​alle mulige strengvarianter, der passer inden for en given afstand for den originale streng.
Baseudvidelse data indebærer oprettelse af mange kopier af denne database, hvor enten alle mulige muligheder, der opfylder kravene til den nødvendige afstand, også genereres, eller dataene behandles på anden måde (mere om dette lidt senere.).

Hengine bruger en kombination af disse tre teknikker til effektivt at balancere mellem hukommelse og eksekveringstid.

Lidt teori

Algoritmen er baseret på en lille sætning, der siger følgende:

Hvis for to linjer -en Og b afstand HD( -en, b) <= k, så hvis vi deler linjerne -en Og b ind i understrenge ved hjælp af metoden rcut ved brug af segmenteringsfaktor
r >= ⌊k/2⌋ + 1
der vil helt sikkert være i det mindste q= r − ⌊k/2⌋ understrenge, når deres afstand ikke overstiger én, HD( -en jeg, b jeg)<= 1.

Udtræk af understrenge fra basisstrengen ved hjælp af metoden rcut udføres efter følgende principper:
Den navngivne værdi segmenteringsfaktor, som opfylder betingelsen
r >= ⌊k/2⌋ + 1

Første længde r − (m mod r) understreng vil have længden ⌊ m / r⌋, og de sidste m mod r understrenge ⌈ m/r⌉. Hvor m er længden af ​​strengen, ⌊ er afrundet til nærmeste bund, og ⌉ er afrundet til nærmeste over.

Nu det samme, kun med et eksempel:

Givet to binære strenge af længde m= 8 bit: A = 11110000 og B = 11010001, afstand mellem dem k = 2.
Valg af segmenteringsfaktor r= 2 / 2 + 1 = 2, dvs. der vil være i alt 2 understrenge i længden m/r= 4 bit.

a1 = 1111, a2 = 0000
b1 = 1101, b2 = 0001

Hvis vi nu beregner afstanden mellem de tilsvarende delstrenge, så i hvert fald q= 2 - 2/2 = 1, vil én understreng matche, eller deres afstand vil ikke overstige én.

Hvad vi ser:
HD(a1; b1) = HD(1111; 1101) = 1
Og
HD(a2; b2) = HD(0000; 0001) = 1

Basisstrengens understrenge blev navngivet underskrifter.
Signaturer eller understrenge a1 og b1 (a2 og b2, a3 og b3 ..., a r og b r) hedder kompatibel med hinanden, og hvis antallet af forskellige bits ikke er mere end én, kaldes disse signaturer matchende.

Og hovedideen med HEngine-algoritmen er at forberede databasen på en sådan måde, at den finder matchende signaturer og derefter vælge de rækker, der er inden for den nødvendige Hamming-afstand.

Database forbehandling

Vi ved allerede, at hvis vi opdeler en streng korrekt i understrenge, så vil mindst én understreng matche den tilsvarende understreng, eller antallet af forskellige bits vil ikke overstige én (signaturerne vil matche).

Det betyder, at vi ikke skal foretage en fuldstændig søgning over alle rækker fra databasen, men først skal finde de signaturer, der matcher, dvs. understrenge vil afvige med maksimalt én.

Men hvordan søger man efter understrenge?

Den binære søgemetode burde gøre et godt stykke arbejde med dette. Men det kræver, at listen over strenge er sorteret. Men vi får flere understrenge fra én linje. For at udføre en binær søgning på en liste over understrenge skal hver sådan liste sorteres på forhånd.
Derfor foreslår dette en metode til at udvide databasen, dvs. oprette flere tabeller, hver for sin egen understreng eller signatur. (Denne tabel kaldes tabel over underskrifter. Og samlingen af ​​sådanne borde er sæt underskrifter).

Den originale version af algoritmen beskriver også omarrangering af understrenge, så de valgte understrenge er på førstepladsen. Dette gøres mere for at lette implementeringen og for yderligere optimering af algoritmen:

Der er en streng A, som er opdelt i 3 understrenge, a1, a2, a3, den komplette liste over permutationer vil være i overensstemmelse hermed:
a1, a2, a3
a2, a1, a3
a3, a1, a2

Disse signaturtabeller sorteres derefter.

Gennemførelse af søgning

På dette stadium, efter foreløbig behandling af databasen, har vi flere kopier af de sorterede tabeller, hver for sin egen underrække.

Det er klart, at hvis vi først vil finde understrenge, skal vi hente signaturer fra den anmodede streng på samme måde, som blev brugt til at oprette signaturtabellerne.

Vi ved også, at de påkrævede understrenge afviger med højst ét ​​element. Og for at finde dem skal du bruge forespørgselsudvidelsesmetoden.

Med andre ord, for den valgte delstreng er det nødvendigt at generere alle kombinationer, inklusive denne delstreng selv, hvor forskellen højst vil være ét element. Antallet af sådanne kombinationer vil være lig med længden af ​​understrengen + 1.

Sådanne handlinger skal udføres for alle underrækker og for alle tabeller.

Og til allersidst bliver du nødt til at filtrere de linjer fra, der ikke passer inden for den angivne Hamming-afstandsgrænse. De der. udfør en lineær søgning gennem de fundne strenge og lad kun de strenge, der opfylder betingelsen HD( -en, b) <= k.

Bloom filter

Hvis filteret før en binær søgning efter en understreng i en tabel returnerer, at understrengen ikke er i den tabel, så nytter det ikke noget at udføre søgningen.

Derfor skal du oprette et filter for hver signaturtabel.

Forfatterne bemærker også, at brug af Bloom-filteret på denne måde reducerer forespørgselsbehandlingstiden med et gennemsnit på 57,8 %. På mine testprøver har et sådant filter stort set ingen effekt på den resulterende driftstid. Kun mærkbar på en tilfældigt genereret database.

Nu det samme, kun med et eksempel

Der er en database med binære strenge 8 bit lange:
11111111
10000001
00111110

Opgaven er at finde alle linjer, hvor antallet af forskellige bits ikke overstiger 2 til mållinjen 10111111.

Altså den nødvendige afstand k = 2.

1. Vælg en segmenteringsfaktor.

Ud fra formlen vælger vi segmenteringsfaktoren r= 2 og det betyder, at der kun vil være to understrenge fra en linje.

2. Opret et sæt signaturer.

Da antallet af understrenge er 2, skal der kun oprettes 2 tabeller:

3. Vi gemmer understrengene i de relevante tabeller, mens vi bevarer et link til den originale kilde.

T1 T2
1111 1111 => 11111111
1000 0001 => 10000001
0011 1110 => 00111110

4. Sorter tabellerne. Hver enkelt for sig.

T1
0011 => 00111110
1000 => 10000001
1111 => 11111111

T2
0001 => 10000001
1110 => 00111110
1111=> 11111111

Dette afslutter forbehandlingen. Og lad os starte søgningen.

5. Vi modtager signaturerne af den anmodede streng.

Den søgte streng 10111110 er opdelt i signaturer. Det viser sig henholdsvis 1011 og 1100, det første for det første bord og det andet for det andet.

6. Generer alle kombinationer, der adskiller sig med én.
Antallet af muligheder vil være 5.

6.1 For den første understreng 1011:
1011
0 011
11 11
100 1
1010

6.2 For den anden understreng 1100:
1100
0 100
10 00
111 0
1101

7. Binær søgning.

7.1 For alle genererede varianter af den første understreng 1011 udfører vi en binær søgning i den første tabel for at finde et komplet match.

1011
0011 == 0011 => 00111110
1111 == 1111 => 11111111
1001
1010

To understrenge fundet.

7.2 Nu, for alle varianter af den anden understreng 1100, udfører vi en binær søgning i den anden tabel.

1100
0100
1000
1110 == 1110 => 00111110
1101

En understreng fundet.

8. Kombination af resultaterne til én liste:
00111110
11111111

9. Kontroller lineært for overensstemmelse og filtrer dem fra, der ikke matcher betingelsen<= 2:

HD(10111110; 00111110) = 1
HD(10111110; 11111111) = 2

Begge strenge opfylder betingelsen om, at ikke mere end to elementer er forskellige.

Selvom en lineær søgning udføres på dette stadium, forventes det, at listen over kandidatstrenge slet ikke vil være stor.
Under forhold, hvor antallet af kandidater er stort, foreslås det at anvende den rekursive version af HEngine.

Klart

Figur 1 viser et eksempel på, hvordan søgealgoritmen fungerer.
For en linjelængde på 64 og en afstandsgrænse på 4 er segmenteringsfaktoren 3, svarende til kun 3 delstrenge pr. linje.
Hvor T1, T2 og T3 er signaturtabeller, der kun indeholder understrenge B1, B2, B3.

Den anmodede streng er opdelt i understrenge. Dernæst genereres en række signaturer for de tilsvarende understrenge. Til sidst udføres en binær søgning.

Fig. 1. En forenklet version af behandling af forespørgsler til signaturtabeller.

resultater

Gennemsnitlig kompleksitet af en sådan algoritme O(m(log n+ 1)), hvor n er det samlede antal rækker i databasen, m er antallet af binære søgninger og log n+ 1 binær søgning.
I ekstreme tilfælde kan det overskride lineært. F.eks. forudsat q= 1 og når alle rækker fra alle signaturtabeller, undtagen den sidste, matcher den anmodede, så viser det sig O((r - 1)mn(log n + 1)).

Det bemærkes, at denne tilgang bruger 4,65 mindre hukommelse og er 16 % hurtigere end det tidligere arbejde beskrevet i .

Implementering

Alt dette er bestemt fristende, men før du rent faktisk rører ved det, er det svært at vurdere skalaen.
En Hengine-prototype blev skabt og testet på tilgængelige reelle data.

Tests$ ./matches 7 data/db/table.txt data/query/face2.txt Læsning af datasættet ........ færdig. 752420 db hashes og 343 forespørgsels hashes. Bygning med 7 hammerafstand bundet ...... færdig. Byggetid: 12.964 sekunder. Søgning efter HEngine-matches ....... fandt 100 samlede resultater. Hengine-forespørgselstid: 0,228 sekunder. Lineær forespørgselstid: 6,828 sekunder

Resultaterne var opmuntrende, fordi søgning efter 343 hashes fra en database på 752420 tager ~0,2 sekunder, hvilket er 30 gange hurtigere end en lineær søgning.

Det ser ud til, at vi kunne stoppe her. Men jeg ville virkelig prøve at bruge det på en eller anden måde i et rigtigt projekt.

Et klik før rigtig anvendelse

Der er en database med billedhash og en backend i PHP.
Opgaven var på en eller anden måde at forbinde funktionaliteten af ​​Hengine og PHP.
Det blev besluttet at bruge FastCGI, indlæggene habrahabr.ru/post/154187/ og habrahabr.ru/post/61532/ hjalp mig meget med dette.

Fra PHP ring blot:

$list = file_get_contents("http://fcgi.local/?" . $hashes);

Hvilket på cirka 0,5 sekunder returnerer resultatet. Når en lineær søgning kræver 9 sekunder, og gennem forespørgsler til MySQL mindst 20 sekunder.

Tak til alle, der fuldførte det.