Bildebehandling

• Opplæringen

I denne artikkelen vi vil snakke om HEngine-algoritmen og implementering av en løsning på problemet med å beregne Hamming-avstanden på store datamengder.

Introduksjon

Hamming-avstanden er antall forskjellige posisjoner for strenger av samme lengde. For eksempel HD( 1 00 , 0 01 ) = 2.

Problemet med å beregne Hamming-avstanden ble først stilt av Minsky og Papert i 1969, hvor problemet var å finne alle rader fra en database som er innenfor en gitt Hamming-avstand til spørringen.

En oppgave som dette er utrolig enkel, men å finne den effektiv løsning er fortsatt på agendaen.

Hamming-avstanden er allerede ganske mye brukt til ulike oppgaver, for eksempel søk etter nære duplikater, mønstergjenkjenning, dokumentklassifisering, feilretting, virusdeteksjon osv.

For eksempel foreslo Manku og kolleger en løsning på problemet med duplikatgruppering i webdokumentindeksering basert på beregning av Hamming-avstanden.
Miller og venner foreslo også konseptet med å søke etter sanger basert på et gitt lydfragment.
Lignende løsninger har blitt brukt for problemet med bildehenting og netthinnegjenkjenning, etc.

Beskrivelse av problemet

Det er en database binære strenger T, størrelse n, hvor lengden på hver linje m. Forespurt streng en og den nødvendige Hamming-avstanden k.

Oppgaven går ut på å finne alle strenger som er innenfor avstanden k.

Det opprinnelige konseptet til algoritmen vurderer to varianter av problemet: statisk og dynamisk.

I et statisk problem er avstanden k forhåndsbestemt.
– I dynamisk er tvert imot nødvendig distanse ukjent på forhånd.

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

Beskrivelse av HEngine-algoritmen for en statisk oppgave

Denne implementeringen fokuserer på å finne strenger innenfor k <= 10.

Det er tre løsninger på et statisk problem: lineær skanning, spørringsutvidelse og tabellutvidelse.

I dette tilfellet under spørringsutvidelse Dette refererer til generering av alle mulige strengvarianter som passer innenfor en gitt avstand for den originale strengen.
Baseutvidelse data innebærer opprettelse av mange kopier av denne databasen, der enten alle mulige alternativer som oppfyller kravene til den nødvendige avstanden også genereres, eller dataene behandles på annen måte (mer om dette litt senere.).

HEngine bruker en kombinasjon av disse tre teknikkene for å effektivt balansere mellom minne og utførelsestid.

Litt teori

Algoritmen er basert på et lite teorem som sier følgende:

Hvis for to linjer en Og b avstand HD( en, b) <= k, så hvis vi deler linjene en Og b inn i understrenger ved hjelp av metoden rcut ved hjelp av segmenteringsfaktor
r >= ⌊k/2⌋ + 1
det vil definitivt være i det minste q= r − ⌊k/2⌋ understrenger, når deres avstand ikke overstiger én, HD( en Jeg, b Jeg)<= 1.

Trekker ut delstrenger fra basisstrengen ved å bruke metoden rcut utføres i henhold til følgende prinsipper:
Verdien som er navngitt segmenteringsfaktor, som tilfredsstiller betingelsen
r >= ⌊k/2⌋ + 1

Første lengde r − (m mod r) understreng vil ha lengde ⌊ m / r⌋, og de siste m mod r delstrenger ⌈ m/r⌉. Hvor m er lengden på strengen, ⌊ er avrundet til nærmeste bunn, og ⌉ er avrundet til nærmeste over.

Nå det samme, bare med et eksempel:

Gitt to binære strenger med lengde m= 8 biter: A = 11110000 og B = 11010001, avstand mellom dem k = 2.
Velge en segmenteringsfaktor r= 2 / 2 + 1 = 2, dvs. det vil være totalt 2 delstrenger i lengde m/r= 4 biter.

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

Hvis vi nå beregner avstanden mellom de tilsvarende delstrengene, så skal minst ( q= 2 - 2/2 = 1) én delstreng vil falle sammen eller avstanden deres vil ikke overstige én.

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

Basestrengens understrenger ble navngitt signaturer.
Signaturer eller understrenger a1 og b1 (a2 og b2, a3 og b3 ..., a r og b r) er kalt kompatibel med hverandre, og hvis antallet forskjellige biter ikke er mer enn én, kalles disse signaturene matchende.

Og hovedideen til HEngine-algoritmen er å forberede databasen på en slik måte å finne matchende signaturer og deretter velge de radene som er innenfor den nødvendige Hamming-avstanden.

Databaseforbehandling

Vi vet allerede at hvis vi deler en streng inn i delstrenger riktig, vil minst én delstreng matche den tilsvarende delstrengen eller antallet forskjellige biter vil ikke overstige én (signaturene vil samsvare).

Dette betyr at vi ikke trenger å foreta et fullstendig søk over alle rader fra databasen, men først må finne de signaturene som matcher, dvs. understrenger vil avvike med maksimalt én.

Men hvordan søke etter understrenger?

Den binære søkemetoden bør gjøre en god jobb med dette. Men det krever at listen over strenger er sortert. Men vi får flere delstrenger fra én linje. For å utføre et binært søk på en liste over understrenger, må hver slik liste sorteres på forhånd.
Derfor foreslår dette en metode for å utvide databasen, dvs. lage flere tabeller, hver for sin egen understreng eller signatur. (Denne tabellen kalles tabell over signaturer. Og samlingen av slike tabeller er sett med signaturer).

Den opprinnelige versjonen av algoritmen beskriver også omorganisering av delstrenger slik at de valgte delstrengene er på første plass. Dette gjøres mer for enkel implementering og for ytterligere optimalisering av algoritmen:

Det er en streng A, som er delt inn i 3 understrenger, a1, a2, a3, den komplette listen over permutasjoner vil være tilsvarende:
a1, a2, a3
a2, a1, a3
a3, a1, a2

Disse signaturtabellene blir deretter sortert.

Gjennomføring av søk

På dette stadiet, etter foreløpig behandling av databasen, har vi flere kopier av de sorterte tabellene, hver for sin egen underrad.

Selvfølgelig, hvis vi først vil finne understrenger, må vi hente signaturer fra den forespurte strengen på samme måte som ble brukt til å lage signaturtabellene.

Vi vet også at de nødvendige understrengene avviker med høyst ett element. Og for å finne dem må du bruke søkeutvidelsesmetoden.

Med andre ord, for den valgte delstrengen er det nødvendig å generere alle kombinasjoner, inkludert denne delstrengen selv, der forskjellen vil være høyst ett element. Antall slike kombinasjoner vil være lik lengden på delstrengen + 1.

Slike handlinger må utføres for alle underrader og for alle tabeller.

Og helt til slutt må du filtrere ut linjene som ikke passer innenfor den angitte Hamming-avstandsgrensen. De. utfør et lineært søk gjennom de funnet strengene og la bare de strengene som oppfyller betingelsen HD( en, b) <= k.

Bloom filter

Forfatterne foreslår å bruke et Bloom-filter for å redusere antall binære søk.
Et Bloom-filter kan raskt avgjøre om en delstreng er i en tabell med en liten prosentandel av falske positive. Som er raskere enn tabellhash.

Hvis filteret, før et binært søk etter en understreng i en tabell, returnerer at understrengen ikke er i den tabellen, er det ingen vits i å utføre søket.

Følgelig må du opprette ett filter for hver signaturtabell.

Nå det samme, bare med et eksempel

Det er en database med binære strenger på 8 bit:
11111111
10000001
00111110

Oppgaven er å finne alle linjer der antall forskjellige biter ikke overstiger 2 til mållinjen 10111111.
Altså nødvendig avstand k = 2.

1. Velg en segmenteringsfaktor.
Basert på formelen velger vi segmenteringsfaktoren r= 2 og det betyr at det bare vil være to delstrenger fra en linje.

2. Lag et sett med signaturer.
Siden antallet understrenger er 2, trenger bare 2 tabeller å opprettes:
T1 og T2

3. Vi lagrer understrengene i de aktuelle tabellene mens vi opprettholder en kobling til den opprinnelige kilden.

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

4. Sorter tabellene. Hver for seg.
T1
0011 => 00111110
1000 => 10000001
1111 => 11111111

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

Dette fullfører forbehandlingen. Og la oss starte søket.

1. Vi innhenter signaturene til den forespurte strengen.
Den søkte strengen 10111110 er delt inn i signaturer. Det viser seg henholdsvis 1011 og 1100, det første for det første bordet, og det andre for det andre.

2. Generer alle kombinasjoner som avviker med én.
Antall alternativer vil være 5.

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

2.2 For den andre delstrengen 1100:
1100
0 100
10 00
111 0
1101

3. Binært søk.

3.1 For alle genererte varianter av den første delstrengen 1011, utfører vi et binært søk i den første tabellen for en fullstendig match.

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

To understrenger funnet.

3.2 Nå, for alle varianter av den andre delstrengen 1100, utfører vi et binært søk i den andre tabellen.

1100
0100
1000
1110 == 1110 => 00111110
1101

En understreng funnet.

4. Kombiner resultatene til én liste:
00111110
11111111

5. Sjekk lineært for samsvar og filtrer ut de som ikke samsvarer med betingelsen<= 2:

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

Begge strengene tilfredsstiller betingelsen om at ikke mer enn to elementer er forskjellige.

Selv om det utføres et lineært søk på dette stadiet, forventes det at listen over kandidatstrenger ikke vil være stor i det hele tatt.
Under forhold hvor antallet kandidater er stort, foreslås det å bruke den rekursive versjonen av HEngine.

Helt klart

Figur 1 viser et eksempel på hvordan søkealgoritmen fungerer.
For en linjelengde på 64 og en avstandsgrense på 4 er segmenteringsfaktoren 3, tilsvarende kun 3 delstrenger per linje.
Hvor T1, T2 og T3 er signaturtabeller som kun inneholder delstrenger B1, B2, B3, 21, 21 og 22 biter lange.

Den forespurte strengen er delt inn i understrenger. Deretter genereres en rekke signaturer for de tilsvarende understrengene. For den første og andre signaturen vil antallet kombinasjoner være 22. Og den siste signaturen gir 23 alternativer. Til slutt utføres et binært søk.

Fig 1. En forenklet versjon av behandling av spørringer til signaturtabeller.

resultater

Gjennomsnittlig kompleksitet for en slik algoritme O(P* (Logg n+ 1)), hvor n er det totale antallet rader i databasen, logg n+ 1 binært søk, og P- antall binære søk: i vårt tilfelle beregnes det som antall kombinasjoner per tabell multiplisert med antall tabeller: P = (64 / r + 1) * r

I ekstreme tilfeller kan kompleksiteten overstige lineær kompleksitet.

Det bemerkes at denne tilnærmingen bruker 4,65 mindre minne og er 16 % raskere enn det forrige arbeidet beskrevet i . Og er den raskeste måten for øyeblikket kjent for å finne alle rader innenfor en gitt grense.

Gjennomføring

Alt dette er absolutt fristende, men før du faktisk berører det, er det vanskelig å vurdere skalaen.
En Hengine-prototype ble laget og testet på tilgjengelige reelle data.

Tester$ ./matches 7 data/db/table.txt data/query/face2.txt Lesing av datasettet ........ ferdig. 752420 db-hasjer og 343 søke-hasher. Bygg med 7 hammingsavstand bundet ....... ferdig. Byggetid: 12.964 sekunder. Søkte HEngine-treff ....... fant totalt 100 treff. Hengine-søketid: 0,1 sekunder. Søkte lineære treff ...... fant totalt 100 treff. Lineær spørretid: 6,828 sekunder

Resultatene var oppmuntrende, fordi søk etter 343 hashes fra en database på 752420 tar ~0,1 sekunder, som er 60 ganger raskere enn et lineært søk.

Det ser ut til at vi kunne stoppe her. Men jeg ville virkelig prøve å bruke det på en eller annen måte i et ekte prosjekt.

Fra PHP bare ring:
$list = file_get_contents("http://fcgi.local/?" . $hashes);
Som returnerer resultatet på ~0,5 sekunder. Når et lineært søk tar 9 sekunder, og gjennom spørringer til MySQL minst 20 sekunder.

Takk til alle som fullførte den.

Linker

M. Minsky og S. Papert. Perceptrons. MIT Press, Cambridge, MA, 1969.
G.S. Manku, A. Jain og A.D. Sarma. Oppdager nestenduplikater for nettgjennomgang. I Proc. 16. WWW, mai 2007.
M.L. Miller, M.A. Rodriguez og I.J. Cox. Lydfingeravtrykk: Søk etter nærmeste nabo i høydimensjonalt binært rom. I MMSP, 2002.
M.L. Miller, M.A. Rodriguez og I.J. Cox. Lydfingeravtrykk: søk etter nærmeste nabo i høydimensjonale binære rom. Journal of VLSI Signal Processing, Springer, 41(3):285–291, 2005.
J. Landr ́e og F. Truchetet. Bildehenting med binær hammingsavstand. I Proc. 2. VISAPP, 2007.
H. Yang og Y. Wang. En LBP-basert ansiktsgjenkjenningsmetode med hammingsavstandsbegrensning. I Proc. Fjerde ICIG, 2007.
B. Bloom. Avveininger mellom rom og tid i hash-koding med tillatte feil. Communications of ACM, 13(7):422–426, 1970.
Alex X. Liu, Ke Shen, Eric Torng. Storskala Hamming Distance Query Processing. ICDE-konferansen, side 553 - 564, 2011.
github.com/valbok/HEngine Min implementering av HEngine i C++ Legg til tagger

Hamming avstand

Den amerikanske matematikeren Hamming studerte hva denne koden avhenger av, om den vil oppdage feil og når den kan rette dem. Intuitivt er det klart at dette avhenger av hvordan kodeordene er separert fra hverandre og hvor mange feil som kan forekomme i det overførte ordet. Vi vil nå formalisere følgende idé. Ved koding er det nødvendig å koordinere antall mulige feil i det overførte kodeordet slik at når det overførte kodeordet endres, forblir det nærmere det opprinnelige kodeordet enn noe annet kodeord.

Definisjon 13.1. Tenk på settet med alle binære ord i alfabetet I= (0,1) lengde T avstand d(x, på), som er lik antall ikke-matchende posisjoner for disse ordene. For eksempel For ord X = 011101, på= 101010 avstand er d(x, y) = 5. Denne avstanden kalles Hamming avstand .

Det kan vises at Hamming-avstanden tilfredsstiller aksiomene til metrisk rom:

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

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

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

Teorem 13.1(om deteksjonskode). Koden oppdager i tilfellet når det overførte ordet ikke inneholder mer enn k

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

Teorem 13.2(om korrigeringskoden.). Koden korrigerer alle feil i tilfellet når det overførte ordet ikke inneholder mer enn k feil, hvis og bare hvis den minste avstanden mellom kodeord

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

Bevis. Bevisene for disse teoremene er like. Derfor vil vi bare bevise det siste teoremet.

Tilstrekkelighet. La for alle kodeord vi har d(b 1, b 2) ≥ 2k+ 1. Hvis, når du sender et kodeord b 1 ikke mer skjedde k feil, så for det aksepterte ordet med vi har d(b 1, c) ≤ k. Men fra trekanten ulikhet for alle andre kodeord b 2 vi har d(b 1, Med) + d(c, b 2) ≥ d(b 1, b 2) ≥ 2 k+ 1. Derfor, fra det mottatte ordet til et hvilket som helst annet kodeord, er avstanden d(c, b 2) ≥ k + 1, dvs. mer enn før b 1. Derfor, ifølge det aksepterte ordet Med du kan definitivt finne det nærmeste kodeordet b 1 og deretter dekode den.

Nødvendighet. Fra det motsatte. Anta at minimumsavstanden mellom kodeord er mindre enn 2 k+ 1. Så er det to kodeord, avstanden mellom dem vil være d(b 1, b 2) ≤ 2 k. La når du overfører ordet b 1 akseptert ord Med er plassert mellom ordene b 1, b 2i har akkurat k feil. Deretter d(c, b 1) = k, d (c, b 2) = d(b 1, b 2) – d(c, b 1) ≤ k. Fra ordet c er det altså umulig å entydig rekonstruere kodeordet som ble overført, b 1eller b 2. Vi kom til en motsetning.

Eksempel 13.3 . Tenk på følgende fem-bits koder for ord med lengde 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.

Minimumsavstanden mellom forskjellige kodeord er d(bi, bj) = 3. I kraft av det første teoremet om deteksjonskoden, er denne koden i stand til å oppdage ikke mer enn to feil i et ord. I kraft av det andre teoremet er koden i stand til å korrigere maksimalt én feil i et ord.

Gruppekoder

La oss se nærmere på kodene til ord i alfabetet I= (0, 1). Hvis for ord av lengde T kodeord med lengde brukes n, så kaller vi slike koder ( T , P)-koder. Total lengde på ord m tilsvarer 2 m. Å sette ( T , P)-kode, kan du liste kodeord for alle mulige ord med lengde m, som i forrige eksempel. En mer økonomisk måte å spesifisere kodeord på er en matriseoppgave.

I dette tilfellet er genereringsmatrisen spesifisert G= ∣∣ gij∣∣ rekkefølge T × P fra 0 og 1. Kodeord bestemmes hver gang for ord EN = EN 1en 2... på ved å multiplisere dette ordet til venstre, som en vektor, med den genererende matrisen

Her er addisjon definert modulo 2. For at ulike ord skal korrespondere med ulike kodeord er det nok å ha i matrisen G enhetsbasis mindre av ordre T, for eksempel den helt til venstre.

Eksempel 13.4 . Tenk på genereringsmatrisen

Denne matrisen definerer (3, 4) koden. I dette tilfellet er de tre første tegnene i kodeordet informative, og det fjerde er en kontroll. Det er lik 0 hvis det er et partall av enere i kildeordet, og 1 hvis det er et oddetall av enere. For eksempel for ordet EN= 101 kode vil være b= aG= 1010. Minimum Hamming-avstand mellom kodeord er d(bi, bj) = 2. Derfor er dette kode som oppdager en engangsfeil.

Definisjon 13.2. Koden kalles gruppe , hvis settet med alle kodeord danner en gruppe. Antall enheter i ordet a kalles vekter ord og er betegnet If b- kodeord og ord mottatt i kommunikasjonskanalen Med = b + e, deretter ordet e kalt vektor av feil .

Teorem 13.3. La det være en gruppe ( T , P)-kode. Deretter den kommutative gruppen TIL av alle kodeord er en undergruppe av den kommutative gruppen MED alle ord av lengde P, som kan mottas i kommunikasjonskanalen. Den minste avstanden mellom kodeord er lik den minste vekten til et kodeord som ikke er null og

Tenk på faktorgruppen S/K. Cosets her vil bli bestemt av skiftet e + b, b∈ K.

Som representant for coset-klassen velger vi elementet med minst vekt. Vi vil kalle slike elementer tilstøtende klasseledere .

Hvis ledere tolkes som feilvektorer, er hver tilstøtende klasse et sett med forvrengte ord i en kommunikasjonskanal med en fast feilvektor, spesielt når e= 0 har vi en tilstøtende klasse med ord uten forvrengninger, dvs. settet av alle kodeord. Prosessen med ordkorreksjon og dekoding Med består i å søke etter den tilstøtende klassen som ordet tilhører Med = e + b. Feilvektor e bestemmer antall og plassering av feil, kodeord b bestemmer korrigeringen av det mottatte ordet.

For å lette søket etter et coset og dermed feilvektoren, foreslo Hamming å bruke gruppekoder med spesielle genererende matriser.

Hamming-koder

La oss vurdere konstruksjonen av Hamming ( T , P)-kode med minste kodeordvekt lik 3, dvs. en kode som retter en feil.

La oss sette P = 2 r– 1 og la hvert kodeord inneholde r kontrolltegn, og T tegn ( T = P – r= 2 r– 1– r) - informativ, r≥ 2, for eksempel (1, 3) kode, (4, 7) kode osv. Dessuten, i hvert kodeord b= b 1b 2... b s symboler med indekser lik en potens på 2 vil være kontrollsymboler, og resten vil være informasjonssymboler. 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 kontroll seg, og symbolene b 3b 5b 6b 7- informativ. For å spesifisere generatormatrisen G Hammings ( T , P)-kode, vurdere hjelpematrisen M rekkefølge r× P, Hvor P = 2 r– 1, slik at i hver j matrisekolonne M det vil være binære symboler j, for eksempel for (4, 7)-koden matrisen M vil være 3 × 7:

Vi definerer settet av alle kodeord som sett med løsninger til et homogent system av lineære algebraiske ligninger av formen

b MT= 0.

For eksempel, for en (4, 7) kode vil et slikt system være:

La oss velge en naturlig basis mindre av systemet b MT= 0, står i kolonner med tall lik potensen 2. Dermed deler vi variablene inn i grunnleggende (kode) og fri (informasjon). Nå, etter å ha definert gratis variabler, er det enkelt å skaffe grunnleggende. La oss finne det grunnleggende systemet m= P – r løsninger av dette homogene systemet. Da er enhver løsning på systemet en lineær kombinasjon av disse m beslutninger. Skriv derfor ut linje for linje m løsninger av det grunnleggende systemet i form av en matrise G størrelse m× P, får vi genereringsmatrisen til Hamming-gruppen ( T , P) kode, for eksempel for en (4, 7) kode, vil det grunnleggende løsningssystemet være 4 = 7 – 3 av følgende løsninger av et homogent system:

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

Enhver lineær kombinasjon av disse løsningene vil være en løsning, dvs. et kodeord. La oss komponere en genererende matrise fra disse grunnleggende løsningene

Nå ifølge ethvert ord EN lengde T= 4 enkle å beregne kodeord b lengde P= 7 ved å bruke generatormatrisen b= aG. Samtidig symbolene b 3, b 5, b 6, b 7 vil være informativ. De sammenfaller med EN 1, EN 1, EN 3, EN 4. Symboler b 1, b 2, b 4 vil være kontroll.

Konklusjon. Hamming-koder er praktiske fordi cosets lett kan bestemmes under dekoding. La ordet mottatt over kommunikasjonskanalen være Med = e + b, Hvor e- feil, b- et kodeord. Multipliser det deretter med hjelpematrisen cMT= (e + b)MT= eM T. Hvis eM T= 0, deretter ordet Med- kode og vi vurderer: det er ingen feil. Hvis eM T≠ 0, deretter ordet e definerer en feil.

Husk at de konstruerte Hammings ( T , P)-kode identifiserer én feil. Derfor feilvektoren e inneholder en enhet i Jeg stillinger. Dessuten nummeret Jeg posisjon oppnås i binær representasjon som resultat eM T, sammenfallende med Jeg matrisekolonne M. Det gjenstår å endre symbolet Jeg i ordet c mottatt over kanalen, kryss ut kontrolltegnene og skriv ned det dekodede ordet.

La for eksempel det aksepterte ordet være Med= 1100011 for (4, 7) Hamming-koden. La oss multiplisere dette ordet med matrisen M T. Vi får

(1100011)M T=(010).

Derfor er det en feil i det andre tegnet. Derfor blir kodeordet b= 1000011. Kryss av kontrolltegnene b 1, b 2, b 4.Det dekodede ordet vil være EN = 0011.

Selvfølgelig, hvis feilen ble gjort i mer enn ett tegn, vil ikke denne koden rette den.

I Stefan Zweigs bok "Humanity's Finest Hours" er det en fantastisk historie "The Genius of One Night" om den franske hæroffiseren Rouget de Lisle, som skrev den berømte "La Marseillaise" i løpet av en natt i varmen av inspirasjon som grep ham. Dette var i 1792 i det revolusjonære Marseille. Sangen spredte seg over hele Frankrike i løpet av få dager, fikk raskt enorm popularitet over hele verden og ble deretter nasjonalsangen til den franske republikken. Historien har bevart navnet Rouget i ettertidens minne takket være denne enkeltsangen.

I analogi kan Richard Hamming kalles et "geni av én idé." Han formulerte det i 1950 i sin eneste vitenskapelige artikkel viet feilrettingskoder. Artikkelen inneholdt konstruksjonen av en blokkkode som korrigerer enkeltfeil som oppstår under meldingsoverføring.

Richard Hamming var konstant engasjert i aktiv vitenskapelig forskning, men hans eneste arbeid innen informasjonsteori, som når det gjelder volum utgjør en ubetydelig prosentandel av hans vitenskapelige arbeid, ble berømt. Denne artikkelen fikk raskt verdensomspennende berømmelse og brakte ham velfortjent berømmelse.

Akkurat som oppdagelsene til Faraday og Maxwell ble fulgt av en rekke oppfinnelser innen telekommunikasjon som forandret livene våre, så åpnet det seg nye muligheter etter dannelsen av informasjonsteori av Claude Shannon og Vladimir Kotelnikov, teorien om potensiell støyimmunitet. utvikling av telekommunikasjon. En av de viktigste delene av informasjonsteori er kodingsteorien, som ble lagt av Hamming.

Shannon fastslo at informasjon kan overføres feilfritt over en kommunikasjonskanal hvis overføringshastigheten ikke overskrider kapasiteten. Shannons bevis var imidlertid ikke konstruktivt. Senere studier av ham og en annen amerikansk vitenskapsmann S. O. Rice viste at nesten enhver tilfeldig valgt kode lar en oppnå den teoretiske grensen for støyimmunitet for meldingsmottak. Imidlertid hadde en slik kode en høy dekodingskompleksitet: antall operasjoner som kreves for å dekode den mottatte kodekombinasjonen økte eksponentielt med lengden.

Hamming var den første som foreslo en konstruktiv metode for å konstruere koder med redundans og enkel dekoding. Hans arbeid forutbestemte retningen for det meste av arbeidet i dette området som fulgte senere.

Til hans ære etablerte Institute of Electrical and Electronics Engineers en medalje for å anerkjenne forskere som har gitt betydelige bidrag til informasjonsteori.

Koder som er i stand til å korrigere feil (i kommunikasjonskanaler i digitale datamaskiner, etc.) under signalbehandling ble foreslått av Hamming allerede før 1948, da Shannons berømte artikkel “Mathematical Theory of Communication” ble publisert, som la et solid grunnlag for teorien i denne felt.områder.

I denne artikkelen beskrev Shannon, som siterer forskning utført i 1947 av hans Bell Labs-kollega Richard Hamming, som et eksempel en enkel kode med lengde 7 som korrigerte alle enkeltfeil. Publisering av Hammings originale materiale ble forsinket til april 1950 av patenthensyn. Det skal bemerkes at eksemplet på feilkorrigerende kode gitt i den nevnte artikkelen av Shannon satte i gang forskningen til en annen amerikansk vitenskapsmann, M. E. Golay. Golay, uavhengig av Hamming, oppdaget koder som korrigerer enkeltfeil. I 1949 (dvs. før Hamming) publiserte han et kort notat (bare en halv side) om resultatene hans i Proceedings of IEEE. I dette notatet vurderte han ikke bare binære koder, men også generelle koder, kombinasjoner som tilhører et begrenset felt (et matematisk sett med elementer med visse operasjoner med addisjon, subtraksjon, divisjon og multiplikasjon) med pn-elementer (p er et primtall) , og n er et heltall).

Det bør bemerkes at en rekke grunnleggende ideer innen kommunikasjonsteori var kjent som private matematiske resultater selv før de begynte å bli brukt av forskere som løste problemer med å overføre meldinger over kommunikasjonskanaler. I sin bok "Algebraic Coding Theory" kom en fremtredende amerikansk ekspert innen kodingsteori, E. Berlekamp, ​​med en veldig interessant bemerkning. Han bemerket at utformingen av Hamming-koder ble beskrevet i en annen kontekst tilbake i 1942 av den berømte amerikanske matematikeren R. A. Fisher, i et arbeid viet teorien om faktoranalyse (en av grenene til matematisk statistikk) og dens forbindelse med den matematiske. teori om grupper. Forresten, V. A. Kotelnikovs teorem, som indikerer muligheten for å representere analoge signaler i digital form, ble også oppdaget som et av de delvise matematiske resultatene av teorien om funksjonsinterpolasjon tilbake på begynnelsen av det tjuende århundre av engelske matematikere E. T. og J. M. Whitker. Det skal understrekes at verken Fisher eller de nevnte engelske forskerne koblet sine resultater med de viktigste problemene for den moderne verden med å overføre informasjon gjennom kommunikasjonskanaler.

Wolfgang Goethe sa: «Det er ikke nok å bare få kunnskap; Jeg må finne en app for ham. Det er ikke nok å bare ønske; trenger å gjøre". For teori og teknologi... kommunikasjon er Kotelnikovs teorem og Hamming-koder av eksepsjonell betydning, siden det var takket være dem at det åpnet seg en klar utsikt til å lage digitale systemer for ingeniører, som på slutten av det tjuende århundre revolusjonerte telekommunikasjon og derfor de er rettmessig kalt etter navnene til disse forskerne.

Etter å ha blitt en katalysator som akselererte utviklingen av kodingsteori, vakte Hammings artikkel oppmerksomheten til det vitenskapelige samfunnet. I alle lærebøker kalles denne klassen av koder Hamming-koder, og presentasjonen av kodingsteori begynner med en beskrivelse av deres konstruksjon. Tilsynelatende ville det fortsatt være mer rettferdig å kalle disse kodene Hamming–Golay-koder, gitt at Golay kom til de samme ideene som Hamming uavhengig og publiserte dem tidligere. At artikkelen hans ikke fikk den oppmerksomheten den fortjener, skyldes mest sannsynlig tilfeldigheter.

Sammenlignet med Shannons teori, var kodene introdusert av Hamming skuffende svake. Hammings vanlige metoder for å konstruere feilkorrigerende koder var imidlertid av grunnleggende betydning. De demonstrerte for ingeniører den praktiske muligheten for å nå grensene angitt av informasjonsteoriens lover. Disse kodene har funnet praktisk anvendelse i etableringen av datasystemer. Hammings papir førte også til en løsning på problemet med tettere pakking for endelige felt. Han introduserte i vitenskapelig bruk de viktigste konseptene innen kodingsteori - Hamming-avstanden mellom kodekombinasjoner i et vektorrom, definert for binære koder som antall posisjoner av disse kombinasjonene med forskjellige symboler, og Hamming-grensene for blokkens korrigeringsevne. korrigere koder. Hamming-grensen for binære koder beregnes ved å bruke følgende formel:

I dette uttrykket kan antall feil e korrigeres med en korrigerende blokkkode med lengde N, som har M kodekombinasjoner (CjN er den binomiale koeffisienten).

Hammings arbeid spilte en nøkkelrolle i den etterfølgende utviklingen av kodingsteori og stimulerte omfattende forskning utført i de påfølgende årene. I 1956 var David Slepyan den første som presenterte teorien om paritetskontrollerende koder på et seriøst matematisk grunnlag. Et stort skifte i feltet kodingsteori skjedde da den franske forskeren A. Hoquenghem (1959) og amerikanerne R. K. Bose og D. K. Roy-Chowdhury (1960) fant en stor klasse med koder (BCH-koder) som korrigerer multiple feil. Amerikanske forskere I. S. Reed og G. Solomon (1960) fant en klasse med koder for ikke-binære kanaler relatert til BCH-koder.

I 1980 skrev Hamming en strålende lærebok, "Coding Theory and Information Theory", som ble oversatt til russisk i 1983. Denne boken, i likhet med hans andre arbeider, utmerker seg ved originaliteten til formuleringen av spørsmål, populariteten til presentasjonen, en dyp forståelse av praktiske problemer, riktigheten og rimelig grad av strenghet i den matematiske tolkningen av problemene som reises. Presentasjonen av stoffet er strukturert på en slik måte at leseren intuitivt forstår hvorfor dette eller det teoremet er sant

På et sett med binære ord med lengde m avstand d(a,b) mellom ordene a og b er antall ikke-matchende posisjoner til disse ordene, for eksempel: avstanden mellom ordene a = 01101 og b = 00111 er 2.

Konseptet definert på denne måten kalles Hamming-avstanden.

Den tilfredsstiller følgende avstandsaksiomer:

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

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

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

Vekten w(a) til et ord a er antallet enere blant dets koordinater. Da er avstanden mellom ordene a og b vekten av summen deres a b: d(a,b)=w(a b) , hvor symbolet  angir operasjonen av koordinatvis addisjonsmodulo 2. Intuitivt er koden bedre egnet for feildeteksjon og korrigering, jo mer forskjellige kodeordene er. Konseptet Hamming-avstand lar oss klargjøre dette.

Teorem For at en kode skal oppdage feil i k (eller færre) posisjoner, er det nødvendig og tilstrekkelig at den minste avstanden mellom kodeord er  k + 1.

Beviset for denne teoremet ligner beviset for følgende utsagn.

Teorem. For at koden skal rette opp alle feil i k (eller færre) posisjoner, er det nødvendig og tilstrekkelig at den minste avstanden mellom kodeord er  2k + 1.

32. Teorem om koders korrigeringsevne.

Koder som automatisk kan rette feil kalles selvkorrigerende. For å bygge en selvkorrigerende kode designet for å korrigere enkeltfeil, er ikke ett kontrollsiffer nok. Som det fremgår av det følgende, må antall kontrollbiter k velges slik at ulikheten 2k≥k+m+1eller k≥log2(k+m+1) er tilfredsstilt, der m er antall grunnleggende binære biter. av kodeordet. For tiden er binære blokkkorreksjonskoder av størst interesse. Ved bruk av slike koder overføres informasjon i form av blokker av samme lengde og hver blokk kodes og dekodes uavhengig av hverandre. I nesten alle blokkkoder kan tegn deles inn i informasjon og verifisering.

Hovedkarakteristikkene til selvkorrigerende koder er:

1. Antall tillatte og forbudte kombinasjoner. Hvis n er antall symboler i blokken, r er antall kontrollsymboler i blokken, k er antall informasjonssymboler, så er 2n antall mulige kodekombinasjoner, 2k er antall tillatte kodekombinasjoner, 2n −2k er antall forbudte kombinasjoner.

2. Koderedundans. Verdien rn kalles redundansen til korreksjonskoden.

3. Minimum kodeavstand. Minste kodeavstand d er det minste antallet forvrengte symboler som kreves for å gå fra en tillatt kombinasjon til en annen.

4. Antall feil oppdaget og rettet. Hvis g er antall feil som koden kan rette, er det nødvendig og tilstrekkelig at d≥2g+1

5. Korrigerende muligheter for koder.

33. Matrisekoding. Gruppekoder.

Når du eksplisitt spesifiserer kodingsskjemaet i ( m, n)-kode bør spesifisere 2 m kodeord, noe som er svært ineffektivt.

En økonomisk måte å beskrive et kodeskjema på er matrisekodingsteknikken.

Tidligere ble hvert kodeskjema beskrevet av tabeller som spesifiserte et kodeord med lengde n for hvert kildeord av lengde m. For lange blokker krever denne metoden en stor mengde minne og er derfor upraktisk. For eksempel for ( 16, 33 ) kode vil kreve 33 * 2 16 = 2 162 688 biter.

Krever mye mindre minne matrisekoding. La E dimensjonsmatrise m×n, bestående av elementer e ij , hvor Jeg er linjenummeret, og j - kolonnenummer. Hvert av matriseelementene e ij kan være enten 0 eller 1. Koding implementeres av operasjonen b = aE eller hvor kodeord betraktes som vektorer, dvs. som radmatriser med størrelse 1×n.

Koding bør ikke tilordne det samme kodeordet til forskjellige kildemeldinger. En enkel måte å oppnå dette på er å m matrisekolonner dannet en enhetsmatrise. Når en hvilken som helst vektor multipliseres med identitetsmatrisen, oppnås den samme vektoren; derfor vil forskjellige meldingsvektorer tilsvare forskjellige vektorer av den systematiske koden.

Matrisekoder kalles også lineære koder. For lineær (n − r, n)-koder med minimum Hamming-avstand d finnes Plotkin nedre grense (Plotkin) for minimum antall sjekkbiter r på n³ 2d − 1,

binær ( En m, n) kode kalles en gruppekode hvis kodeordene danner en gruppe.

Legg merke til at settet med alle binære ord med lengde m danner en kommutativ gruppe med operasjonen av koordinatvis addisjon modulo 2, der relasjonen a a gjelder. Følgelig er settet med meldingsord a med lengde m en kommutativ gruppe.

Blokkkode kalles gruppe, hvis kodeordene danner en gruppe.

Hvis koden er en gruppekode, er den minste avstanden mellom to kodeord lik den minste vekten av ordet som ikke er null.

Dette følger av forholdet d(b Jeg , b j ) = w(b Jeg + b j ).

Når du bruker en jokerkode, blir de og bare de feilene som tilsvarer feilstrenger nøyaktig lik kodeordene uoppdaget.

Slike feillinjer oversetter ett kodeord til et annet.

Derfor er sannsynligheten for at en feil forblir uoppdaget lik summen av sannsynlighetene for alle feilstrenger lik kodeord.

Sett med alle binære ord a = a 1 ... a m lengde m danner en abelsk (kommutativ) gruppe med hensyn til bitvis addisjon.

La E - koding m×n-en matrise som har m × m- en submatrise med en determinant som ikke er null, for eksempel identitet. Så kartleggingen a → a E oversetter en gruppe av alle binære ord med lengde m til en gruppe kodeord av lengde n.

La oss anta at Da får vi

dvs. Derfor en en-til-en-kartlegging av en gruppe binære ord med lengde m ved hjelp av en gitt matrise E bevarer egenskapene til en gruppeoperasjon, som betyr at kodeordene danner en gruppe.

Gruppekodeegenskap: minste kodeavstand mellom kodevektorer er lik minimumsvekten til vektorer som ikke er null. Vekten til kodevektoren er lik antallet enere i kodekombinasjonen.

Det er praktisk å spesifisere gruppekoder ved hjelp av matriser, hvis dimensjon bestemmes av parametrene k og n. Antall rader er k og antall kolonner er n = k+m.

Kodene som genereres av disse matrisene kalles (n, k)-koder, og de tilsvarende matrisene kalles generatorer (generatorer).

Denne artikkelen vil diskutere HEngine-algoritmen og implementeringen av en løsning på problemet med å beregne Hamming-avstanden på store datamengder.

Introduksjon

Hamming-avstanden er antall forskjellige posisjoner for strenger av samme lengde. For eksempel, HD(100; 001) = 2.

Problemet med å beregne Hamming-avstanden ble først stilt av Minsky og Papert i 1969, hvor problemet var å finne alle rader fra en database som er innenfor en gitt Hamming-avstand til spørringen.

En slik oppgave er uvanlig enkel, men jakten på dens effektive løsning er fortsatt på agendaen.

Hamming-avstand er allerede ganske mye brukt til ulike oppgaver, som å finne nære duplikater, mønstergjenkjenning, dokumentklassifisering, feilretting, virusdeteksjon, etc.

For eksempel foreslo Manku og kolleger en løsning på problemet med duplikatgruppering i webdokumentindeksering basert på beregning av Hamming-avstanden.
Miller og venner foreslo også konseptet med å søke etter sanger basert på et gitt lydfragment.
Lignende løsninger har blitt brukt for problemet med bildehenting og netthinnegjenkjenning, etc.

Beskrivelse av problemet

Det er en database med binære strenger T, størrelse n, hvor lengden på hver linje m. Forespurt streng en og den nødvendige Hamming-avstanden k.

Oppgaven går ut på å finne alle strenger som er innenfor avstanden k.

Det opprinnelige konseptet til algoritmen vurderer to varianter av problemet: statisk og dynamisk.

I et statisk problem er avstanden k forhåndsbestemt.
– I dynamisk er tvert imot nødvendig distanse ukjent på forhånd.

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

Beskrivelse av HEngine-algoritmen for en statisk oppgave

Denne implementeringen fokuserer på å finne strenger innenfor k <= 10.

Det er tre løsninger på et statisk problem: lineær skanning, spørringsutvidelse og tabellutvidelse.

I dette tilfellet under spørringsutvidelse Dette refererer til generering av alle mulige strengvarianter som passer innenfor en gitt avstand for den originale strengen.
Baseutvidelse data innebærer opprettelse av mange kopier av denne databasen, der enten alle mulige alternativer som oppfyller kravene til den nødvendige avstanden også genereres, eller dataene behandles på annen måte (mer om dette litt senere.).

HEngine bruker en kombinasjon av disse tre teknikkene for å effektivt balansere mellom minne og utførelsestid.

Litt teori

Algoritmen er basert på et lite teorem som sier følgende:

Hvis for to linjer en Og b avstand HD( en, b) <= k, så hvis vi deler linjene en Og b inn i understrenger ved hjelp av metoden rcut ved hjelp av segmenteringsfaktor
r >= ⌊k/2⌋ + 1
det vil definitivt være i det minste q= r − ⌊k/2⌋ understrenger, når deres avstand ikke overstiger én, HD( en Jeg, b Jeg)<= 1.

Trekker ut delstrenger fra basisstrengen ved å bruke metoden rcut utføres i henhold til følgende prinsipper:
Verdien som er navngitt segmenteringsfaktor, som tilfredsstiller betingelsen
r >= ⌊k/2⌋ + 1

Første lengde r − (m mod r) understreng vil ha lengde ⌊ m / r⌋, og de siste m mod r delstrenger ⌈ m/r⌉. Hvor m er lengden på strengen, ⌊ er avrundet til nærmeste bunn, og ⌉ er avrundet til nærmeste over.

Nå det samme, bare med et eksempel:

Gitt to binære strenger med lengde m= 8 biter: A = 11110000 og B = 11010001, avstand mellom dem k = 2.
Velge en segmenteringsfaktor r= 2 / 2 + 1 = 2, dvs. det vil være totalt 2 delstrenger i lengde m/r= 4 biter.

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

Hvis vi nå beregner avstanden mellom de tilsvarende delstrengene, så i det minste q= 2 - 2/2 = 1, én delstreng vil matche eller avstanden deres vil ikke overstige én.

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

Basestrengens understrenger ble navngitt signaturer.
Signaturer eller understrenger a1 og b1 (a2 og b2, a3 og b3 ..., a r og b r) er kalt kompatibel med hverandre, og hvis antallet forskjellige biter ikke er mer enn én, kalles disse signaturene matchende.

Og hovedideen til HEngine-algoritmen er å forberede databasen på en slik måte å finne matchende signaturer og deretter velge de radene som er innenfor den nødvendige Hamming-avstanden.

Databaseforbehandling

Vi vet allerede at hvis vi deler en streng inn i delstrenger riktig, vil minst én delstreng matche den tilsvarende delstrengen eller antallet forskjellige biter vil ikke overstige én (signaturene vil samsvare).

Dette betyr at vi ikke trenger å foreta et fullstendig søk over alle rader fra databasen, men først må finne de signaturene som matcher, dvs. understrenger vil avvike med maksimalt én.

Men hvordan søke etter understrenger?

Den binære søkemetoden bør gjøre en god jobb med dette. Men det krever at listen over strenger er sortert. Men vi får flere delstrenger fra én linje. For å utføre et binært søk på en liste over understrenger, må hver slik liste sorteres på forhånd.
Derfor foreslår dette en metode for å utvide databasen, dvs. lage flere tabeller, hver for sin egen understreng eller signatur. (Denne tabellen kalles tabell over signaturer. Og samlingen av slike tabeller er sett med signaturer).

Den opprinnelige versjonen av algoritmen beskriver også omorganisering av delstrenger slik at de valgte delstrengene er på første plass. Dette gjøres mer for enkel implementering og for ytterligere optimalisering av algoritmen:

Det er en streng A, som er delt inn i 3 understrenger, a1, a2, a3, den komplette listen over permutasjoner vil være tilsvarende:
a1, a2, a3
a2, a1, a3
a3, a1, a2

Disse signaturtabellene blir deretter sortert.

Gjennomføring av søk

På dette stadiet, etter foreløpig behandling av databasen, har vi flere kopier av de sorterte tabellene, hver for sin egen underrad.

Selvfølgelig, hvis vi først vil finne understrenger, må vi hente signaturer fra den forespurte strengen på samme måte som ble brukt til å lage signaturtabellene.

Vi vet også at de nødvendige understrengene avviker med høyst ett element. Og for å finne dem må du bruke søkeutvidelsesmetoden.

Med andre ord, for den valgte delstrengen er det nødvendig å generere alle kombinasjoner, inkludert denne delstrengen selv, der forskjellen vil være høyst ett element. Antall slike kombinasjoner vil være lik lengden på delstrengen + 1.

Slike handlinger må utføres for alle underrader og for alle tabeller.

Og helt til slutt må du filtrere ut linjene som ikke passer innenfor den angitte Hamming-avstandsgrensen. De. utfør et lineært søk gjennom de funnet strengene og la bare de strengene som oppfyller betingelsen HD( en, b) <= k.

Bloom filter

Hvis filteret, før et binært søk etter en understreng i en tabell, returnerer at understrengen ikke er i den tabellen, er det ingen vits i å utføre søket.

Følgelig må du opprette ett filter for hver signaturtabell.

Forfatterne bemerker også at bruk av Bloom-filteret på denne måten reduserer spørringsbehandlingstiden med gjennomsnittlig 57,8 %. På mine testprøver har et slikt filter praktisk talt ingen effekt på den resulterende driftstiden. Merkbar bare på en tilfeldig generert database.

Nå det samme, bare med et eksempel

Det er en database med binære strenger på 8 bit:
11111111
10000001
00111110

Oppgaven er å finne alle linjer der antall forskjellige biter ikke overstiger 2 til mållinjen 10111111.

Altså nødvendig avstand k = 2.

1. Velg en segmenteringsfaktor.

Basert på formelen velger vi segmenteringsfaktoren r= 2 og det betyr at det bare vil være to delstrenger fra en linje.

2. Lag et sett med signaturer.

Siden antallet understrenger er 2, trenger bare 2 tabeller å opprettes:

3. Vi lagrer understrengene i de aktuelle tabellene mens vi opprettholder en kobling til den opprinnelige kilden.

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

4. Sorter tabellene. Hver for seg.

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

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

Dette fullfører forbehandlingen. Og la oss starte søket.

5. Vi mottar signaturene til den forespurte strengen.

Den søkte strengen 10111110 er delt inn i signaturer. Det viser seg henholdsvis 1011 og 1100, det første for det første bordet, og det andre for det andre.

6. Generer alle kombinasjoner som avviker med én.
Antall alternativer vil være 5.

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

6.2 For den andre delstrengen 1100:
1100
0 100
10 00
111 0
1101

7. Binært søk.

7.1 For alle genererte varianter av den første delstrengen 1011, utfører vi et binært søk i den første tabellen for en fullstendig match.

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

To understrenger funnet.

7.2 Nå, for alle varianter av den andre delstrengen 1100, utfører vi et binært søk i den andre tabellen.

1100
0100
1000
1110 == 1110 => 00111110
1101

En understreng funnet.

8. Kombiner resultatene til én liste:
00111110
11111111

9. Sjekk lineært for samsvar og filtrer ut de som ikke samsvarer med betingelsen<= 2:

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

Begge strengene tilfredsstiller betingelsen om at ikke mer enn to elementer er forskjellige.

Selv om det utføres et lineært søk på dette stadiet, forventes det at listen over kandidatstrenger ikke vil være stor i det hele tatt.
Under forhold hvor antallet kandidater er stort, foreslås det å bruke den rekursive versjonen av HEngine.

Helt klart

Figur 1 viser et eksempel på hvordan søkealgoritmen fungerer.
For en linjelengde på 64 og en avstandsgrense på 4 er segmenteringsfaktoren 3, tilsvarende kun 3 delstrenger per linje.
Hvor T1, T2 og T3 er signaturtabeller som kun inneholder understrenger B1, B2, B3.

Den forespurte strengen er delt inn i understrenger. Deretter genereres en rekke signaturer for de tilsvarende understrengene. Til slutt utføres et binært søk.

Fig 1. En forenklet versjon av behandling av spørringer til signaturtabeller.

resultater

Gjennomsnittlig kompleksitet for en slik algoritme O(m(Logg n+ 1)), hvor n er det totale antallet rader i databasen, m er antall binære søk, og logg n+ 1 binært søk.
I ekstreme tilfeller kan det overskride lineært. For eksempel gitt q= 1 og når alle rader fra alle signaturtabeller, bortsett fra den siste, samsvarer med den forespurte, så viser det seg O((r - 1)mn(Logg n + 1)).

Det bemerkes at denne tilnærmingen bruker 4,65 mindre minne og er 16 % raskere enn det forrige arbeidet beskrevet i .

Gjennomføring

Alt dette er absolutt fristende, men før du faktisk berører det, er det vanskelig å vurdere skalaen.
En Hengine-prototype ble laget og testet på tilgjengelige reelle data.

Tester$ ./matches 7 data/db/table.txt data/query/face2.txt Lesing av datasettet ........ ferdig. 752420 db-hasjer og 343 søke-hasher. Bygg med 7 hammingsavstand bundet ....... ferdig. Byggetid: 12.964 sekunder. Søkte HEngine-treff ....... fant totalt 100 treff. Hengine-søketid: 0.228 sekunder. Søkte lineære treff ....... fant 100 treff totalt. Lineær spørretid: 6,828 sekunder

Resultatene var oppmuntrende, fordi søk etter 343 hashes fra en database på 752420 tar ~0,2 sekunder, som er 30 ganger raskere enn et lineært søk.

Det ser ut til at vi kunne stoppe her. Men jeg ville virkelig prøve å bruke det på en eller annen måte i et ekte prosjekt.

Ett klikk før ekte applikasjon

Det er en database med bildehasher og en backend i PHP.
Oppgaven var å på en eller annen måte koble sammen funksjonaliteten til HEngine og PHP.
Det ble bestemt å bruke FastCGI, innleggene habrahabr.ru/post/154187/ og habrahabr.ru/post/61532/ hjalp meg mye med dette.

Fra PHP bare ring:

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

Som på ca 0,5 sekunder gir resultatet. Når et lineært søk krever 9 sekunder, og gjennom spørringer til MySQL minst 20 sekunder.

Takk til alle som fullførte den.