Redigerer Hjelp:Forfattere av sider (avsnitt)

==Algoritme==
Artikkelens historikk danner et spor i et flerdimensjonalt rom, hvor hver av forfatterne har bidratt til å flytte artikkelen et lite stykke langs dette sporet. Noen har bidratt med mange små veistykker, noen har skrevet den frem i større bolker. De enkeltes totaler sier hvor mye de har flyttet artikkelen i dette flerdimmensjonale rommet. Hvis det er mange små endringer, typisk for korrektur, så vil bidragene telle en del mer enn sammenhengende tekststykker.

Metoden baserer seg på bruk av [[:en:Locality sensitive hashing|locality sensitive hashing]], hvor vårt valg av hashfunksjoner og disses representasjon er slik at de kan brukes som avstandsmål. Dette gjør vi for å forenkle beregning av medgått arbeid isteden for å bruke en [[redigeringsavstand]] slik som [[:en:Damerau–Levenshtein distance|Damerau–Levenshtein distance]].

For hver revisjon beregnes det en ordinær digest og en vektor av trigrammer &ndash; et fingeravtrykk for revisjonen. Fordi beregningene utføres i nettleseren er det viktig at løsningen krever lite av maskinvaren. For å analysere artikkelen må hele historikken med komplett tekst for hver revisjon lastes ned fra serverne. En moderat artikkel på ~40KB med 500 revisjoner vil typisk medføre nedlasting og prosessering av ~20MB tekst. Dette setter en betydelig last på serverne og krever en nokså rask linje om det ikke skal bli mye venting. Den nedlastede teksten prosesseres videre i nettleseren noe som stiller store krav til Javascript-interpreteren.

For å kunne påvise tilbakestillinger bruker vi en digest, en [[:en:Fowler–Noll–Vo hash function|Fowler–Noll–Vo hash]]. Denne er rask å kalkulere og stiller moderate krav til maskinvaren. Vi kan bruke en vilkårlig [[digest]], for eksempel [[:en:MD5|MD5]], men kravene til utfallsrom er såvidt begrensede at det er bedre å bruke en hash som er lett å beregne. En Fowler–Noll–Vo hash ble ansett for å være tilstrekkelig for formålet og den økte kompleksiteten til en MD5 kunne ikke forsvares.

Det beregnes også en vektor som beregnes ved hjelp av av trigrammer som identifiserer et punkt lang veien til artikkelen. Fordi alle trigrammer danner et veldig stort rom, typisk med rank 29³ for norsk eller 24389, så foldes disse inn i et mindre subrom på rank 256 i vår implementasjon. Metoden for folding av trigrammer bruker en [[:en:Pearson hashing|Pearson hash]] og akkumulerer i en vektor med 256 elementer, som er et punkt i vårt subrom. Denne vektoren peker på et punkt i subrommet, og en serie av revisjoner vil beskrive en vei artikkelen har fulgt fra første til nåværende versjon. To slike vektorer har en differansvektor og denne beskriver arbeidet med å flytte artikkelen fra en form og over til en annen form. Hvis vi antar at subrommet er rettvinklet så har har differansvektoren en lengde som kan beregnes som en ordinær hypotenus i et euclidsk rom.

Første scan gjennom revisjonene er for å fjerne tilbakestillinger. For hver revisjon har vi en digest og et fingerprint, samtidig har systemet en ''parentid'' som det oppfatter som foregående revisjon. Når vi scanner fra eldste til nyeste revisjon så beholder vi en peker til hver unik digest. I noen tilfeller har systemet påvist riktig ''parentid'', da beholder vi denne. I andre tilfeller oppdager vi at samme digest dukker opp på nytt, da kan vi sette en ''previousid'' slik at vi vet at vi skal hoppe over mellomliggende revisjoner. Vi bruker previousid om den peker til en eldre revisjon enn parentid slik at alle tilbakestillinger og revisjonskriger fjernes.

I tillegg til denne måten å beregne hovedsporet til artikkelen trengs en måte å påvise store og ofte planløse endringer. Uten en mulighet til å avskjære disse vil klipp og lim av store blokker detekteres som uforholdsmessig store bidrag til artikkelen. Dette påviser vi ved å bruke fingerprintet. Blir endringene mellom versjoner for stort så gjøres det et kort scan tilbake i tid for å se om en versjon er tettere på den aktuelle revisjonen. Hvis så er tilfelle så settes ''previousid'' til å peke forbi seksjonene med klipp og lim og til den tidligere versjonen som var likest. Visuelt vil dette fremstå som at vi retter ut slynger på veien artikkelen følger.

Det er også problemer med å skille ut brukere som er aktive med vandalismepatruljering på enkeltartikler. Disse vokser fort frem som hovedforfattere hvis vandaliseringen er omfattende og det ikke reverteres til en forutgående versjon. Spesielt komplisert vandalisme og påfølgende opprydding som tas i flere omganger kan gi feil resultat. Det ser ikke ut som om det er noen enkel løsning på problemet, selv om det kan virke som omfattende vandalisme kan detekteres ved at fordelingen av trigrammer vil avvike kraftig fra den endelige.

For alle disse revisjonene beregnes det en tilvekst som tilordnes de enkelte bidragsyterne. For hver bruker akkumuleres en sum som representerer veilengden de har flyttet artikkelen i det flerdimensjonale rommet. Det beregnes med andre ord en cosineavstand mellom vektorer skapt av trigrammer for revisjonen og den som identifiseres med ''previousid''.

; Eksempel : Trigrammer for «[[:en:The quick brown fox jumps over the lazy dog|The quick brown fox jumps over the lazy dog]]» er «The», «he », «e q», « qu», «qui», «uic» og så videre.

Totalt er det 35 bokstaver og 8 mellomrom i eksempelet, noe som skaper 41 trigrammer om disse tar med mellomrommene. Legges en slik setning til i en tekst så vil den representere et maksimalt tillegg på 47. Hvis setningen flyttes i teksten så representerer dette en endring på 4 der den ble tatt ut, pluss to for den nye teksten på stedet, og 4 der den ble satt inn, totalt 10 i endring. Blir teksten fjernet vil det potensielt kunne gi like stort absolutt bidrag som å legge teksten til.

Beregning av arbeidet som er nedlagt i revisjonen vil få en «feil» som følge av at to eller flere trigrammer hashes til samme bin. Hvis endringene teller i forskjellig retning så blir differansen liten og akkumulert arbeid blir mindre enn det burde bli. Denne feilen er gitt som en sannsynlighet for hash-kollisjon justert for sannsynligheten for å observere de enkelte trigrammer. Fordi hver endring av et tegn medfører endring i tre trigrammer så vil observert feil som følge av hash-kollisjoner bli mindre enn 1, typisk blir den av størrelsesorden ⅓. Sannsynligheten for at feilen oppstår vil minskes ved å bruke en lengre vektor (subrom med flere dimmensjoner) men da går lagringsbehovet opp.

Merk at trigrammer kan erstattes med n-grammer. Det er ikke kjent hvordan dette vil påvirkes av tegnfordelingen i Norsk, men typisk størrelse på feil ved enkeltstående hash-kollisjon vil gå ned til ⅕ hvis fordelingen til hash-funksjonen er uforandret. Samtidig vil påvirkning fra mindre rettinger øke, endring i ett tegn vil påvirke fem bins mot tre tidligere. Bruk av lengre n-grammer vil også gi en økning i lasten under hashing av strengene.