Hjelp:Forfattere av sider
- Surgeons warning
Løsningen er ikke skrevet for mobilbrowsere, men den er verifisert å fungere i nettleseren Fennec. Den er også testet på artikler med 1000–2000 revisjoner, men disse analysene bør ikke gjøres på en ordinær mobil. En artikkel ala Stavkirke er på omtrent 40KB, med rundt 500 revisjoner gir det omtrent 20MB med tekst som med 200kb/s mobiltilknytting gir omtrent 15-20 minutter overføringstid. Det er mulig, men neppe hensiktsmessig å bruke en mobil for å gjøre slike analyser.
Artikkelforfattere er en tilleggsfunksjon for å påvise hvem som er hovedforfatter og viktige medforfattere i en kollektivt skrevet tekst. Tallene som fremkommer representerer ikke anslag eller «bokstaver», det er et mål for veien artikkelen har tilbakelagt. I noen tilfeller blir endringer gjort på et slikt vis at en serie mindre endringer lager en lengre vei enn en enkelt større endring. I disse tilfellene kan brukere bli kreditert for mer bearbeiding enn ved mer konservative analyser. Omvendt kan store endringer bli feiltolket som vandalisme og analysen vil da forsøke å søke opp en forutgående lignende revisjon, derved kan flere iterative endringer bli utelatt.
Formålet med koden er å komme frem til et fungerende måltall som er tilstrekkelig og som har mellomregninger som effektivt lar seg lagre i databasen. Dermed kan det lages effektive løsninger for identifisering av forfatterskap, diagrammer over artikler hvor brukere bidrar, diagrammer for bidrag på artikler og artiklers utviklingslinje. Kun den første av disse er vist i implementasjonen, men alle disse subsystemene trenger metoder for å påvise hvor mye artiklene endres og hvilken versjoner som beholdes og som det bygges videre på i senere versjoner.
Tilleggsfunksjonen er skrevet som et proof of concept, og den eksisterende implementasjonen i Javascript har mangler som gjør den lite egnet for fullskala bruk. Spesielt er det viktig å være klar over at denne funksjonen er svært ressurskrevende for nettleseren, den utløser mye nett-trafikk og tunge beregninger.
Det er gjort noen analyser for forfatterskap av anbefalte artikler, men det er foreløpig ikke gjort noen analyse som tallfester hvor godt algoritmens resultater stemmer overens med faktiske anslag.
Algoritme rediger
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 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 Damerau–Levenshtein distance.
For hver revisjon beregnes det en ordinær digest og en vektor av trigrammer – 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 Fowler–Noll–Vo hash. Denne er rask å kalkulere og stiller moderate krav til maskinvaren. Vi kan bruke en vilkårlig digest, for eksempel 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 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 «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.
Destruktive endringer rediger
Det er et kjent problem at konstruktive vs destruktive endringer ikke blir skilt med denne metoden. Metoden vil måle den enkelte bidragsyters andel av en total sti gjennom artikkelens historikk. En destruktiv endring bidrar ikke til det totale innholdet, men vil likefullt representere en del av denne stien.
For en generell skribent betyr ikke dette så mye, men det skaper en usikkerhet i hvilken bidragsytere som er reelle forfattere. Fordi slike destruktive bidrag er en del av artikkelens sti gjennom bidragsrommet så oppnår sistnevnte en ranking som en relativt viktig bidragsyter, og kan lett tas som medforfatter, selv om volumet på det produserte innholdet er nokså begrenset.
En mulig variant for å få et klarere bilde av hvem som bidrar positivt til den endelige versjonen er å normalisere bidragene langs en vektor gitt av siste versjon. Når en summerer de enkeltes bidrag langs denne vektoren vil en finne at store destruktive endringer gir et negativt sluttresultat, til forskjell fra en forfatter med konstruktive bidrag som får et akkumulert positivt sluttresultat.
Denne variasjonen av algoritmen vil redusere innflytelsen fra tilfeldige endringer og fokusere på det som bringer artikkelen frem til slutt-tilstanden, men merk at enkelte typer trolling kan ha uheldige resultater. Spesielt skaper det problemer om dumping av tekst i en artikkel blir feiloppfattet som et positivt bidrag og den påfølgende fjerningen oppfattes som et destruktivt bidrag. I dette tilfellet vil det destruktive bidraget kunne gi et stort negativt tillegg for den aktuelle brukeren. Dette vil kun skje der tilbakestillingen er delvis og hvor den nye varianten er nokså ulik alle foregående versjoner.