Side 1

Hammeravstand mellom to sekvenser lik lengde tilsvarer antall stillinger okkupert av ikke-matchende elementer. Når det gjelder sekvenser av forskjellig lengde, er Hamming-avstanden definert som minimum antall posisjoner okkupert av ikke-sammenfallende elementer ved.

Hamming-avstanden d (u, v) mellom to ord u og v med samme lengde er lik antall ikke-matchende biter av disse ordene. Den brukes i teorien om blokkkoder (V.

Ved å bruke de metriske egenskapene til Hamming-avstanden, bekreftes det direkte at / l er en metrikk på Xt, men er ikke en metrikk på settet med blandede periodiske sekvenser.

Denne nærhetsfunksjonen tilsvarer Hamming-avstanden.

Metrikken p i KLOP-algoritmen er gitt av Hamming-avstanden.

Hvis søkeprosedyren kan finne en posisjon der Hamming-avstanden er null, vil problemet være løst.

Sammenligning av uklare delmengder B og B3, grader av uklarhet og Hamming-avstand viser at de betraktede uklare undergruppene er forskjellige. Imidlertid, hvis elementet m2 G Uz tas som den beregnede verdien, hvor medlemskapsgraden til den oppnådde fuzzy delmengden er maksimal, kan bruken av fuzzy ratio R beregnet på denne måten rettferdiggjøres. Sammen med det faktum at med denne tilnærmingen er det mulig å beskrive ikke-lineariteten i forholdet mellom maksimal temperatur i den andre sonen av reaktoren og polyetylen-smeltestrømningshastigheten, tar denne metoden ikke hensyn til ikke-stasjonariteten til LDPE-produksjonsprosessen, som er forbundet med en endring i egenskapene til den teknologiske prosessen.

Overføringsfunksjonen til denne koden indikerer at det bare er én bane med en Hamming-avstand d - fra en bane med alle nuller, som smelter sammen med en bane med alle nuller ved en gitt node. Fra tilstandsdiagrammet vist i fig. 6, eller espalierdiagrammet vist i fig. 5, kan du se at banen med d6 er acbe. Igjen fra tilstandskartet eller gitteret kan vi se at disse banene er acdbe og acbcbe. Det tredje leddet i (8.1.2) indikerer at det er fire baner med avstand d 0 og så videre. Og dermed, Overføringsfunksjon gir oss avstandsegenskapene til konvolusjonskoden.

Dette resultatet stemmer overens med observasjonen av at banen med helt null (/ 0) har en Hamming-avstand på d3 fra den mottatte sekvensen, mens c/1-banen har en Hamming-avstand på d5 fra den mottatte banen. Dermed er Hamming-avstand en ekvivalent beregning for hard beslutningsdekoding.

Dette resultatet stemmer overens med observasjonen av at banen med helt null (/ 0) har en Hamming-avstand på d3 fra den mottatte sekvensen, mens c/1-banen har en Hamming-avstand på d5 fra den mottatte banen. Dermed er Hamming-avstand en ekvivalent beregning for hard beslutningsdekoding.

I boken til Stefan Zweig "The Star Hours of Humanity" er det en fantastisk historie "The Genius of One Night" om den franske hæroffiseren Rouge de Lille, som skrev den berømte "Marseillaise" i varmen av sin inspirasjon i løpet av en natt . 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 Rouge i ettertidens minne takket være denne enkeltsangen.

I analogi med Richard Hamming kan det kalles "geniet til én idé". Han formulerte det i 1950 i sin eneste vitenskapelig artikkel dedikert til koder for feilretting. Artikkelen inneholdt konstruksjonen av en blokkkode som korrigerer enkeltfeil som oppstår under meldingsoverføring.

Richard Hamming ledet stadig aktivt Vitenskapelig forskning, men hans eneste arbeid innen informasjonsteori ble berømt, og utgjorde en ubetydelig prosentandel av hans vitenskapelige arbeid. 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 endret livene våre, så åpnet det seg nye muligheter etter dannelsen av teorien om informasjon av Claude Shannon og Vladimir Kotelnikov om teorien om potensiell støyimmunitet. for utvikling av telekommunikasjon. En av kritiske avsnitt informasjonsteori er en teori om koding, som ble lagt av Hamming.

Shannon fant ut at informasjon kan overføres gjennom en kommunikasjonskanal uten feil hvis overføringshastigheten ikke overskrider den båndbredde... Shannons bevis var imidlertid ikke-konstruktivt. Senere studier av ham og en annen amerikansk forsker S.O. Rice viste at nesten enhver tilfeldig valgt kode kan oppnå teoretisk grense støyimmunitet ved mottak av meldinger. Imidlertid hadde en slik kode en høy dekodingskompleksitet: antall operasjoner som kreves for å dekode det mottatte kodeordet vokste eksponentielt med lengden.

Hamming var den første som foreslo en konstruktiv metode for å konstruere redundanskoder og enkel dekoding. Arbeidet hans bestemte retningen for det meste av arbeidet på dette området som fulgte.

Til hans ære etablerte Institute of Electrical and Electronic Engineers en medalje, som deles ut til forskere som har gitt betydelige bidrag til informasjonsteori.

Koder som er i stand til å korrigere feil (i kommunikasjonskanaler i digital datamaskiner etc.) i signalbehandling ble foreslått av Hamming før 1948, da Shannons berømte artikkel "Mathematical Communication Theory" ble publisert, som la et solid grunnlag for teorien på dette området.

I denne artikkelen beskrev Shannon, med henvisning til forskning utført i 1947 av hans medarbeider Richard Hamming, som et eksempel en enkel kode med lengde 7 som korrigerer alle enkeltfeil. Publiserer det samme originalt materiale Hamming ble arrestert av patenthensyn frem til april 1950. Det skal bemerkes at eksemplet med feilkorrigerende kode gitt i den nevnte artikkelen av Shannon initierte forskningen til en annen amerikansk forsker, M. E. Golay. Golay, uavhengig av Hamming, oppdaget koder for å korrigere enkeltfeil. I 1949 (dvs. før Hamming) publiserte han et kort notat (bare en halv side) om resultatene sine i Proceedings IEEE. I dette notatet vurderte han ikke bare binære koder men også koder generelt syn, kombinasjoner som tilhører et begrenset felt (et matematisk sett av elementer med visse operasjoner for addisjon, subtraksjon, divisjon og multiplikasjon) med pn-elementer (p er primtall, og n er et heltall).

Det skal bemerkes at en rekke grunnleggende ideer innen kommunikasjonsteori var kjent som spesielle matematiske resultater selv før forskere begynte å bruke dem, løser problemer overføring av meldinger gjennom kommunikasjonskanaler. I sin bok "Algebraic Coding Theory" kom en fremtredende amerikansk ekspert innen kodeteori, E. Berlekamp, ​​med en meget interessant bemerkning. Han bemerket at konstruksjonen av Hamming-koder ble beskrevet i en annen kontekst tilbake i 1942 av den berømte amerikanske matematikeren R.A. Forresten, V.A.Kotelnikovs teorem som indikerer muligheten for å representere analoge signaler v digital form, ble også oppdaget som et av de spesielle matematiske resultatene av teorien om interpolering av en funksjon på begynnelsen av det tjuende århundre av de engelske matematikerne E. T. og J. M. Whitker. Det skal understrekes at verken Fischer eller de nevnte engelske forskerne koblet sine resultater med de viktigste for moderne verden problemer med informasjonsoverføring over kommunikasjonskanaler.

Wolfgang Goethe sa: «Det er ikke nok bare å få kunnskap; du må finne en søknad for ham. Det er ikke nok bare å ønske; trenger å gjøre". For teori og teknologi ... er forbindelsene mellom Kotelnikovs teorem og Hamming-koder av eksepsjonell betydning, siden det var takket være dem at en klar utsikt til å skape digitale systemer, som på slutten av det tjuende århundre gjorde en revolusjon innen telekommunikasjon og derfor kalles de med rette 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 er mest sannsynlig tilfeldig.

Sammenlignet med Shannons teori var Hammings koder skuffende svake. Imidlertid var Hammings foreslåtte vanlige metoder for å konstruere feilkorrigerende koder av grunnleggende betydning. De demonstrerte for ingeniørene praktisk mulighet nå disse grensene, som ble indikert av lovene for informasjonsteori. Disse kodene ble funnet praktisk bruk mens du lager datasystemer... Hammings papir førte også til en løsning på det tettere pakkingsproblemet for endelige felt. Han introduserte de viktigste konseptene for kodingsteori i vitenskapelig bruk - Hamming-avstanden mellom kodekombinasjoner i et vektorrom, definert for binære koder som antall posisjoner av disse kombinasjonene med ulike symboler, og Hamming grenser for korrigeringsevnen til blokkkorrigeringskoder. Hamming-grensen for binære koder beregnes ved å bruke følgende formel:

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

Hammings verk spilte nøkkelrolle i den påfølgende utviklingen av kodingsteori og stimulerte til omfattende forskning utført i årene etter. I 1956 var David Slepyan den første som forklarte teorien om paritetssjekkkoder på en seriøs matematisk grunnlag... Et stort skifte i feltet kodingsteori skjedde da den franske forskeren A. Hawkingham (1959) og amerikanerne R.K.Bowes og D.K.Roy-Chowdhury (1960) fant en stor klasse med koder (BCH-koder) som korrigerer flere feil. Amerikanske forskere I.S.Reed og G. Solomon (1960) fant en klasse med koder for ikke-binære kanaler assosiert med 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 å stille spørsmål, populariteten til presentasjonen, en dyp forståelse av praktiske problemer, korrekthet og en 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 hint teoremet er sant.

Bildebehandling

• Opplæringen

I denne artikkelen vil vi snakke om HEngine-algoritmen og implementeringen av løsningen på problemet med å beregne Hamming-avstanden på store volumer data.

Introduksjon

Hammeravstand er antall forskjellige posisjoner for rader med 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 oppgaven var å finne alle rader fra databasen som er innenfor en gitt Hamming-avstand til den forespurte.

Denne oppgaven er uvanlig enkel, men søket etter det effektiv løsning står fortsatt på agendaen.

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

For eksempel har Manku og kolleger foreslått en løsning på problemet med gruppering av duplikater ved indeksering av nettdokumenter basert på beregning av Hamming-avstanden.
Miller og venner foreslo også konseptet med å søke etter sanger etter et gitt lydfragment.
Lignende løsninger er brukt for oppgaven med bildesøk og netthinnegjenkjenning mv.

Beskrivelse av problemet

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

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

I det opprinnelige konseptet av algoritmen vurderes to varianter av problemet: statisk og dynamisk.

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

Denne artikkelen beskriver løsningen på bare et statisk problem.

Beskrivelse av HEngine-algoritmen for et statisk problem

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

Det er tre løsninger på det statiske problemet: lineær skanning, spørringsutvidelse og tabellutvidelse.

I dette tilfellet under ved å utvide forespørselen Jeg mener å generere alle mulige strengvarianter som passer innenfor den angitte avstanden for den originale strengen.
Utvide basen data innebærer opprettelse av mange kopier av denne databasen, der enten alle mulige varianter genereres som oppfyller de nødvendige avstandskravene, eller dataene behandles på annen måte (mer om dette litt senere.).

Hengine bruker en kombinasjon av disse tre teknikkene for å effektivt balansere minne og kjøretid.

Litt teori

Algoritmen er basert på et lite teorem som lyder som følger:

Hvis for to linjer en og b avstand HD ( en, b) <= k, så hvis du deler linjene en og b på delstrenger etter metode rcut ved hjelp av segmenteringsfaktor
r >= ⌊k/2⌋ + 1
sikkert blir det i det minste q= r − ⌊k/ 2⌋ delstrenger, når avstanden deres ikke overstiger én, HD ( en Jeg, b Jeg)<= 1.

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

Lengden på den første r − (m mod r) understrenger vil ha lengde ⌊ m / r⌋, og den siste m mod r delstrenger ⌈ m/r⌉. Hvor m er lengden på strengen, ⌊ er avrunding til nærmeste bunn, og ⌉ er avrunding til nærmeste topp.

Nå det samme, bare ved eksempel:

Gitt to binære strenger med lengde m= 8 biter: A = 11110000 og B = 11010001, avstanden mellom dem k = 2.
Velge en segmenteringsfaktor r= 2/2 + 1 = 2, dvs. totalt vil det være 2 delstrenger med 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 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

Understrengene til basisstrengen har fått navn 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 sammenfallende.

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

Databaseforbehandling

Vi vet allerede at hvis vi deler strengen 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 å utføre en full oppregning over alle rader fra databasen, men først må vi finne de signaturene som samsvarer, dvs. understrenger vil avvike med maksimalt én.

Men hvordan søker du etter understrenger?

Den binære søkemetoden burde gjøre en god jobb med dette. Men det krever at listen over strenger er sortert. Men vi får flere delstrenger fra en streng. For å utføre et binært søk på en liste over understrenger, må hver slik liste sorteres på forhånd.
Derfor foreslår metoden for å utvide databasen seg selv her, det vil si å lage flere tabeller, hver for sin egen understreng eller signatur. (En slik tabell kalles signaturtabell... Og et sett med slike bord - signatursett).

Den originale versjonen av algoritmen beskriver også permutasjonen av delstrenger på en slik måte at de valgte delstrengene er i utgangspunktet. Dette gjøres mer for enkel implementering og for ytterligere optimaliseringer av algoritmen:

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

Disse signaturtabellene blir deretter sortert.

Søkeimplementering

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

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, det kreves at den valgte delstrengen genererer alle kombinasjoner, inkludert denne delstrengen selv, der forskjellen maksimalt vil være ett element. Antall slike kombinasjoner vil være lik lengden på delstrengen + 1.

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

Og helt til slutt må du filtrere ut linjene som ikke passer inn i den spesifiserte grensen for Hamming-avstanden. De. utfør et lineært søk gjennom de funnet linjene og la bare de linjene som oppfyller HD ( en, b) <= k.

Bloom filter

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

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

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

Nå det samme, bare ved eksempel

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

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

1. Velg segmenteringsfaktor.
Basert på formelen velger vi segmenteringsfaktoren r= 2 og det vil derfor være to delstrenger fra en streng totalt.

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

3. Vi lagrer understrengene i de tilsvarende tabellene mens vi beholder koblingen til kilden.

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

4. Sorter tabeller. Hver enkelt individuelt.
T1
0011 => 00111110
1000 => 10000001
1111 => 11111111

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

På dette Foreløpig behandling ferdig. Og vi begynner å lete.

1. Få signaturene til den forespurte strengen.
Søkestrengen 10111110 er delt opp i signaturer. Det viser seg henholdsvis 1011 og 1100, det første for det første bordet, og det andre for det andre.

2. Vi genererer alle kombinasjoner som er forskjellige med én.
Antallet 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

Fant to understrenger.

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

Fant én understreng.

4. Kombiner resultatene til én liste:
00111110
11111111

5. Sjekk lineært for samsvar og filtrer ut uegnede etter tilstand<= 2:

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

Begge linjer tilfredsstiller betingelsen om forskjell på ikke mer enn to elementer.

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 når antallet kandidater vil være stort, foreslås det å bruke den rekursive varianten av HEngine.

Helt klart

Figur 1 viser et eksempel på søkealgoritmen.
For en strenglengde på 64 og en avstandsgrense på 4 er segmenteringsfaktoren 3, så det er bare 3 delstrenger per streng.
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 et signaturområde for de tilsvarende understrengene. For den første og andre signaturen vil antallet kombinasjoner være 22. Og den siste signaturen gir 23 alternativer. Og til slutt gjøres et binært søk.

Figur 1. En forenklet versjon av behandling av signaturtabellspørringer.

resultater

Kompleksiteten til en slik algoritme i gjennomsnittlig tilfelle 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: det anses i vårt tilfelle som antall kombinasjoner per tabell multiplisert med antall tabeller: P = (64 / r + 1) * r

I ekstreme tilfeller kan kompleksiteten overstige lineær.

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

Gjennomføring

Alt dette er selvsagt fristende, men før du faktisk rører ved det, er det vanskelig å vurdere skalaen.
En prototype av HEngine 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 100 treff totalt. 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, siden søket etter 343 hashes fra databasen i 752420 tar ~0,1 sekunder, som er 60 ganger raskere enn et lineært søk.

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

Fra PHP er det nok å ringe:
$ 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 gjorde det.

Lenker

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 begrensning for hammingsavstand. I Proc. Fjerde ICIG, 2007.
B. Bloom. Avveininger mellom plass 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 HEngine C ++ Implementering Legg til tagger

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

Introduksjon

Hammeravstand er antall forskjellige posisjoner for rader med samme lengde. For eksempel HD (100, 001) = 2.

For første gang ble problemet med å beregne Hamming-avstanden stilt av Minsky og Papert i 1969, hvor oppgaven var å finne alle rader fra databasen som er innenfor en gitt Hamming-avstand til den forespurte.

Denne oppgaven er uvanlig enkel, men jakten på en effektiv løsning er fortsatt på agendaen.

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

For eksempel har Manku og kolleger foreslått en løsning på problemet med gruppering av duplikater ved indeksering av nettdokumenter basert på beregning av Hamming-avstanden.
Miller og venner foreslo også konseptet med å søke etter sanger etter et gitt lydfragment.
Lignende løsninger er brukt for oppgaven med bildesøk og netthinnegjenkjenning mv.

Beskrivelse av problemet

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

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

I det opprinnelige konseptet av algoritmen vurderes to varianter av problemet: statisk og dynamisk.

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

Denne artikkelen beskriver løsningen på bare et statisk problem.

Beskrivelse av HEngine-algoritmen for et statisk problem

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

Det er tre løsninger på det statiske problemet: lineær skanning, spørringsutvidelse og tabellutvidelse.

I dette tilfellet under ved å utvide forespørselen Jeg mener å generere alle mulige strengvarianter som passer innenfor den angitte avstanden for den originale strengen.
Utvide basen data innebærer opprettelse av mange kopier av denne databasen, der enten alle mulige varianter genereres som oppfyller de nødvendige avstandskravene, eller dataene behandles på annen måte (mer om dette litt senere.).

Hengine bruker en kombinasjon av disse tre teknikkene for å effektivt balansere minne og kjøretid.

Litt teori

Algoritmen er basert på et lite teorem som lyder som følger:

Hvis for to linjer en og b avstand HD ( en, b) <= k, så hvis du deler linjene en og b på delstrenger etter metode rcut ved hjelp av segmenteringsfaktor
r >= ⌊k/2⌋ + 1
sikkert blir det i det minste q= r − ⌊k/ 2⌋ delstrenger, når avstanden deres ikke overstiger én, HD ( en Jeg, b Jeg)<= 1.

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

Lengden på den første r − (m mod r) understrenger vil ha lengde ⌊ m / r⌋, og den siste m mod r delstrenger ⌈ m/r⌉. Hvor m er lengden på strengen, ⌊ er avrunding til nærmeste bunn, og ⌉ er avrunding til nærmeste topp.

Nå det samme, bare ved eksempel:

Gitt to binære strenger med lengde m= 8 biter: A = 11110000 og B = 11010001, avstanden mellom dem k = 2.
Velge en segmenteringsfaktor r= 2/2 + 1 = 2, dvs. totalt vil det være 2 delstrenger med 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

Understrengene til basisstrengen har fått navn 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 sammenfallende.

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

Databaseforbehandling

Vi vet allerede at hvis vi deler strengen 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 å utføre en full oppregning over alle rader fra databasen, men først må vi finne de signaturene som samsvarer, dvs. understrenger vil avvike med maksimalt én.

Men hvordan søker du etter understrenger?

Den binære søkemetoden burde gjøre en god jobb med dette. Men det krever at listen over strenger er sortert. Men vi får flere delstrenger fra en streng. For å utføre et binært søk på en liste over understrenger, må hver slik liste sorteres på forhånd.
Derfor foreslår metoden for å utvide databasen seg selv her, det vil si å lage flere tabeller, hver for sin egen understreng eller signatur. (En slik tabell kalles signaturtabell... Og et sett med slike bord - signatursett).

Den originale versjonen av algoritmen beskriver også permutasjonen av delstrenger på en slik måte at de valgte delstrengene er i utgangspunktet. Dette gjøres mer for enkel implementering og for ytterligere optimaliseringer av algoritmen:

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

Disse signaturtabellene blir deretter sortert.

Søkeimplementering

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

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, det kreves at den valgte delstrengen genererer alle kombinasjoner, inkludert denne delstrengen selv, der forskjellen maksimalt vil være ett element. Antall slike kombinasjoner vil være lik lengden på delstrengen + 1.

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

Og helt til slutt må du filtrere ut linjene som ikke passer inn i den spesifiserte grensen for Hamming-avstanden. De. utfør et lineært søk gjennom de funnet linjene og la bare de linjene som oppfyller HD ( en, b) <= k.

Bloom filter

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

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. Vi vil bare føle det på en tilfeldig generert database.

Nå det samme, bare ved eksempel

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

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

Betyr nødvendig avstand k = 2.

1. Velg segmenteringsfaktor.

Basert på formelen velger vi segmenteringsfaktoren r= 2 og det vil derfor være to delstrenger fra en streng totalt.

2. Vi lager et sett med signaturer.

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

3. Vi lagrer understrengene i de tilsvarende tabellene mens vi beholder koblingen til kilden.

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

4. Sorter tabeller. Hver enkelt individuelt.

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

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

Dette fullfører forbehandlingen. Og vi begynner å lete.

5. Vi får signaturene til den forespurte strengen.

Søkestrengen 10111110 er delt opp 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.
Antallet 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 de genererte variantene 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

Fant to understrenger.

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

Fant én understreng.

8. Kombiner resultatene til én liste:
00111110
11111111

9. Sjekk lineært for samsvar og filtrer ut uegnede etter tilstand<= 2:

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

Begge linjer tilfredsstiller betingelsen om forskjell på ikke mer enn to elementer.

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 når antallet kandidater vil være stort, foreslås det å bruke den rekursive varianten av HEngine.

Helt klart

Figur 1 viser et eksempel på søkealgoritmen.
For en strenglengde på 64 og en avstandsgrense på 4 er segmenteringsfaktoren 3, så det er bare 3 delstrenger per streng.
Hvor T1, T2 og T3 er signaturtabeller som kun inneholder delstrenger B1, B2, B3.

Den forespurte strengen er delt inn i understrenger. Deretter genereres et signaturområde for de tilsvarende understrengene. Og til slutt gjøres et binært søk.

Figur 1. En forenklet versjon av behandling av signaturtabellspørringer.

resultater

Kompleksiteten til en slik algoritme i gjennomsnittlig tilfelle 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, faller sammen 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 selvsagt fristende, men før du faktisk rører ved det, er det vanskelig å vurdere skalaen.
En prototype av HEngine 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 100 treff totalt. Hengine-søketid: 0,228 sekunder. Søkte lineære treff ....... fant totalt 100 treff. Lineær spørretid: 6,828 sekunder

Resultatene var oppmuntrende, siden søket etter 343 hashes fra databasen i 752420 tar ~ 0,2 sekunder, som er 30 ganger raskere enn et lineært søk.

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

Ett klikk til ekte applikasjon

Det er en database med bildehasher og en PHP-backend.
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.

Fra PHP er det nok å ringe:

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

Som returnerer resultatet på omtrent 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 gjorde det.

Hamming avstand

Den amerikanske matematikeren Hemming undersøkte hva den gitte koden avhenger av, om den vil oppdage feil og når den kan fikse dem. Intuitivt er det klart at det avhenger av hvordan kodeordene er adskilt og hvor mange feil som kan oppstå i det overførte ordet. Vi formaliserer nå følgende idé. Ved koding er det nødvendig å matche antallet mulige feil i det overførte ordet 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 av alle binære ord i alfabetet V= (0,1) lengde T avstand d(x, på), som er lik antall posisjoner som ikke samsvarer med disse ordene. For eksempel For ord NS = 011101, på= 101010 avstand er d(x, y) = 5. Denne avstanden kalles Hamming avstand .

Det kan vises at Hamming-avstanden tilfredsstiller aksiomene til det metriske rommet:

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

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

3) d(x, på) ≤ d(x, z) + d(z, på) er trekanten ulikhet.

Teorem 13.1(om deteksjonskoden). Koden er detektiv når det overførte ordet inneholder høyst 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 eventuelle kodeord vi har d(b 1, b 2) ≥ 2k+ 1. Hvis under overføring av kodeord b 1 skjedde på det meste 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. Følgelig, fra det mottatte ordet til et hvilket som helst annet kodeord, avstanden d(c, b 2) ≥ k + 1, dvs. mer enn før b 1. Derfor, i henhold til det aksepterte ordet med du kan entydig finne det nærmeste kodeordet b 1 og deretter dekode den.

Trenge... Ved selvmotsigelse. Anta at minimumsavstanden mellom kodeord er mindre enn 2 k+ 1. Så er det to kodeord, avstanden mellom disse vil være d(b 1, b 2) ≤ 2 k... La når du overfører et ord b 1 akseptert ord med er mellom ordene b 1, b 2 og 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 således umulig å entydig gjenopprette kodeordet som ble overført, b 1eller b 2. Vi kom til en motsetning.

Eksempel 13.3 ... Tenk på følgende 5-biters ordkoder med lengde 2 i alfabetet V = {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 maksimalt to feil i et ord. I kraft av det andre teoremet er koden i stand til å korrigere maksimalt én ordfeil.

Gruppekoder

La oss vurdere mer detaljert kodene til ord i alfabetet. V= (0, 1). Hvis for ord lange T kodeord med lengde n, så kalles slike koder ( T , NS) -koder. Totalt lange ord m tilsvarer 2 m... Å spørre ( T , NS) -kode, kan du telle kodeord for alle mulige ord med lengde m som i forrige eksempel. En mer økonomisk måte å spesifisere kodeord på er matrisetilordning.

I dette tilfellet er genereringsmatrisen gitt G= ∣∣ gij∣∣ rekkefølge T × NS 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 bestemmes addisjon modulo 2. For at ulike ord skal korrespondere med ulike kodeord er det nok å ha i matrisen G enhet base ordre mindre T, for eksempel ytterst 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 0 hvis det er et partall av enere i det opprinnelige ordet, og 1 hvis det er et oddetall av enere. For eksempel for ordet en= 101 vil koden være b= aG= 1010. Minimum Hamming-avstand mellom kodeord er d(bi, bj) = 2. Derfor er dette en kode som oppdager en enkelt feil.

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

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

Tenk på faktorgruppen C / K... Tilstøtende klasser her vil bli bestemt av skiftet e + b, b∈ K.

Velg elementet med lavest vekt som representant for kosesettet. Vi vil kalle slike elementer allierte klasseledere .

Hvis ledere tolkes som feilvektorer, er hvert medsett et sett med forvrengte ord i en kommunikasjonskanal med en fast feilvektor, spesielt for e= 0 har vi en tilstøtende klasse med ord uten forvrengning, dvs. settet med alle kodeord. Ordkorreksjon og dekodingsprosess med er å finne cosettet som ordet tilhører med = e + b... Vektor av feil e bestemmer antall og plassering av feil, kodeord b bestemmer korrigeringen av det mottatte ordet.

For å lette søket etter coset og dermed feilvektoren foreslo Hamming bruk av gruppekoder med spesielle generatormatriser.

Hemming-koder

Vurder konstruksjonen av en Hamming ( T , NS) -kode med den minste kodeordvekten lik 3, dvs. en kode som retter en feil.

Vi putter NS = 2 r- 1 og la hvert kodeord inneholde r kontrolltegn, og T tegn ( T = NS – 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 kraften 2 vil være kontroll, og resten vil være informativ. For eksempel for (4, 7) -koden i kodeordet b= b 1b 2b 3b 4b 5b 6b 7 symboler b 1b 2b 4 vil være kontroll, og karakterer b 3b 5b 6b 7- informativ. For å definere en genererende matrise G hemming ( T , NS) -kode, vurder hjelpematrisen M rekkefølge r× NS, hvor NS = 2 r- 1, slik at i hver j matrisekolonne M det vil være symboler for binær dekomponering av tallet j, for eksempel, for en (4, 7) -kode, matrisen M vil være 3 × 7:

Settet med alle kodeord er definert som settet 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 grunnfag i systemet b MT= 0, står i kolonner med tall lik potensen 2. Dermed deler vi variablene inn i grunnleggende (kode) og frie (informasjonsmessige). Nå, etter å ha satt gratis variabler, er det enkelt å få grunnleggende. Finn det grunnleggende systemet m= NS – r løsninger på dette homogene systemet. Da er enhver løsning på systemet en lineær kombinasjon av disse m løsninger. Skriv derfor ut linje for linje m løsninger av det grunnleggende systemet i form av en matrise G størrelsen m× NS, får vi genereringsmatrisen til Hamming-gruppen ( T , NS) -kode, for eksempel for (4, 7) -koden, vil det grunnleggende løsningssystemet være 4 = 7 - 3 av følgende løsninger av det homogene systemet:

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 den genererende matrisen fra disse grunnleggende løsningene

Nå for et hvilket som helst ord en lengden T= 4 enkelt å beregne kodeordet b lengden NS= 7 ved å bruke generatormatrisen b= aG... Dessuten symbolene b 3, b 5, b 6, b 7 vil være informativ. De er de samme som en 1, en 1, en 3, en 4. Symboler b 1, b 2, b 4 vil være kontroll.

Produksjon... Hamming-koder er praktiske ved at cosets lett kan bestemmes under dekoding. La ordet mottatt gjennom kommunikasjonskanalen være med = e + b, hvor e- feil, b- kodeord. Så multipliserer vi det med hjelpematrisen SMT= (e + b)MT= eM T... Hvis eM T= 0, deretter ordet med- kode og vurdere: ingen feil. Hvis eM T≠ 0, deretter ordet e identifiserer feilen.

Husk at den konstruerte hemningen ( T , NS) -kode definerer én feil. Derfor er feilvektoren e inneholder en enhet i Jeg posisjon. Og nummeret Jeg posisjon oppnås i binært som resultat eM T sammenfallende med Jeg kolonne av matrise M... Det gjenstår å endre symbolet Jeg i ordet c mottatt over kanalen, slett kontrolltegnene og skriv ut 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 en feil ble gjort i mer enn ett tegn, vil ikke denne koden fikse det.