---

Lad os sige, at vi har en streng af tal:
"0129386501946312827125634585784747387362835..." Lad os sige, at
strengen er ret lang, f.eks. nogle tusinde cifre.

Nu skal der foretages nogle ændringer i strengen. Og vi skal holde
styr på, hvilke ændringer, der er foretaget hvor og hvornår.

Som jeg ser det, bliver vi *nødt* til at referere til positioner i
strengen. Jeg kan ikke se, hvordan det kunne gøres anderledes. F.eks.
"på position 51 skal 5 ændres til 3, på position 217 skal 9 ændres til
1", osv.

Så længe vi kun ændrer et tal ad gangen, går det fint. Men lige så
snart vi får en opgave af typen "på position 916 skal 3 ændres til
454" eller "på position 1045 skal 6-tallet fjernes", så har vi
balladen, for så skrider alle vores andre referencer.

Hvordan hulen griber man det an?

---

steen@silicium.dk wrote:
> Lad os sige, at vi har en streng af tal:
> "0129386501946312827125634585784747387362835..." Lad os sige, at
> strengen er ret lang, f.eks. nogle tusinde cifre.
>
> Nu skal der foretages nogle ændringer i strengen. Og vi skal holde
> styr på, hvilke ændringer, der er foretaget hvor og hvornår.
>
> Som jeg ser det, bliver vi *nødt* til at referere til positioner i
> strengen. Jeg kan ikke se, hvordan det kunne gøres anderledes. F.eks.
> "på position 51 skal 5 ændres til 3, på position 217 skal 9 ændres til
> 1", osv.
>
> Så længe vi kun ændrer et tal ad gangen, går det fint. Men lige så
> snart vi får en opgave af typen "på position 916 skal 3 ændres til
> 454" eller "på position 1045 skal 6-tallet fjernes", så har vi
> balladen, for så skrider alle vores andre referencer.
>
> Hvordan hulen griber man det an?

Jeg ved ikke om der er en "rigtig" måde at gøre det på, men en løsning
kunne vel være at bruge pointere til strenge af forskellige længder. Til
at starte med kunne man nøjes med en pointer til den samlede streng.
Hvis noget bliver ændret på "position" x kunne man så dele strengen så
den første pointer nu kun havde en streng fra position 0 til x-1 og den
anden pointer så havde resten af strengen. Ved indsættelser gør man som
ved ændringer men indsætter samtidigt en pointer til en ny streng der
skal læses om om den er mellem de den forrige og den efterfølgende. Ved
siden af vedligeholder man så en ordnet liste over pointerne.

My 2 cents.

---

>Hvordan hulen griber man det an?

Prøv at søg på difrential kompresion. Det er grundlæggende det princip man
bruger... at holde styr på ændringer.

Det er velbeskrveet online, men jeg læste en gang en udmærket beskrivelse på
dansk. Den handler dog primært om blokkodning med en server der er på den
anden side af et langsomt netværk.
http://www.greenleaf.dk/tag/projects.html
Lidt nede står der differential compression

Ved ikke om det kan bruges, men det er som sagt velbeskrevet.

---

steen@silicium.dk wrote:
> Lad os sige, at vi har en streng af tal:
> "0129386501946312827125634585784747387362835..." Lad os sige, at
> strengen er ret lang, f.eks. nogle tusinde cifre.
>
> Nu skal der foretages nogle ændringer i strengen. Og vi skal holde
> styr på, hvilke ændringer, der er foretaget hvor og hvornår.
>
> Som jeg ser det, bliver vi *nødt* til at referere til positioner i
> strengen. Jeg kan ikke se, hvordan det kunne gøres anderledes. F.eks.
> "på position 51 skal 5 ændres til 3, på position 217 skal 9 ændres til
> 1", osv.
>
> Så længe vi kun ændrer et tal ad gangen, går det fint. Men lige så
> snart vi får en opgave af typen "på position 916 skal 3 ændres til
> 454" eller "på position 1045 skal 6-tallet fjernes", så har vi
> balladen, for så skrider alle vores andre referencer.
>
> Hvordan hulen griber man det an?

Hej!

Prøv:

http://da.wikipedia.org/wiki/Git

http://en.wikipedia.org/wiki/Category:Version_control_systems

/Glenn

---

steen@silicium.dk wrote:
> Lad os sige, at vi har en streng af tal:
> "0129386501946312827125634585784747387362835..." Lad os sige, at
> strengen er ret lang, f.eks. nogle tusinde cifre.
>
> Nu skal der foretages nogle ændringer i strengen. Og vi skal holde
> styr på, hvilke ændringer, der er foretaget hvor og hvornår.
>
> Som jeg ser det, bliver vi *nødt* til at referere til positioner i
> strengen. Jeg kan ikke se, hvordan det kunne gøres anderledes. F.eks.
> "på position 51 skal 5 ændres til 3, på position 217 skal 9 ændres til
> 1", osv.
>
> Så længe vi kun ændrer et tal ad gangen, går det fint. Men lige så
> snart vi får en opgave af typen "på position 916 skal 3 ændres til
> 454" eller "på position 1045 skal 6-tallet fjernes", så har vi
> balladen, for så skrider alle vores andre referencer.
>
> Hvordan hulen griber man det an?
En posittion skal have tilstræklig bytes, til at bære informatinen og
herunder ."ikke-definition".
Er det mere kompliceret end som så?
mvh
jhp

---

Jeg ved ikke om det er en videnskabelig løsning, men du kan jo gemme en
XOR af strengen ved hver eneste ændring. Når der blot ændres værdier,
vil du få nogle 1'er hvor de ændres, resten vil være 0

De enkelte XOR "snaphots" kan du så komprimere med en eller anden
algoritme, evt. er RLE nok, men vil sikkert ikke være optimal når der
indsættes eller fjernes tal, hvorfor en mere snedig algoritme kunne være
relevant...

---

Esben von Buchwald skrev:

> Jeg ved ikke om det er en videnskabelig løsning, men du kan jo gemme en
> XOR af strengen ved hver eneste ændring.

Så kan man jo lige så godt gemme den rå streng hver gang.

--
Bertel
http://bertel.lundhansen.dk/         FIDUSO: http://fiduso.dk/

---

> Så kan man jo lige så godt gemme den rå streng hver gang.

Nah, nu skriver han dog
"De enkelte XOR "snaphots" kan du så komprimere med en eller anden
algoritme, evt. er RLE nok"
og det er jo korrekt at det generelt vil kunne pakkes ret voldsomt.
Princippet bruges i ligende form i andre algoritmer.

---

Peter Madsen skrev:

> og det er jo korrekt at det generelt vil kunne pakkes ret voldsomt.

Så pakker man bare den rå streng. Jeg kan ikke se nogen fordel
ved først at xore den.

--
Bertel
http://bertel.lundhansen.dk/         FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen wrote:
> Peter Madsen skrev:
>
>> og det er jo korrekt at det generelt vil kunne pakkes ret voldsomt.
>
> Så pakker man bare den rå streng. Jeg kan ikke se nogen fordel
> ved først at xore den.
>
fordi xor'en i tilfælde af substitution vil bestå af en hulens masse
sekventielle nuller og så enkelte 1-taller. Det kan komprimeres langt
bedre end en arbitrær streng af samme længde.

---

> fordi xor'en i tilfælde af substitution vil bestå af en hulens masse
> sekventielle nuller og så enkelte 1-taller. Det kan komprimeres langt
> bedre end en arbitrær streng af samme længde.

Ja, man kunne antage at første streng havde maksimal entropi og at anden
streng var identisk bortset fra een værdi der ændredes.
Denne anden streng xor første er 0 og eet 1-tal.

---

> Denne anden streng xor første er 0 og eet 1-tal.
.... som er minimal entropi.
Ja, det var det der var min pointe som skulle prøve at gøre det til andet
end en gentagelse af Martins indlæg

---

Har du styr på alogoritmisk informations teori og Kolmogorov
kompleksitit.
Hvis ikke bør du læse op på det, da det vil give dig en forståelse for
den teoretisk basis for dit spørgsmål.

Hvis du har problemer med at se relevansen i forhold til dit konkrete
spørgsmål, så spørg gerne igen.

J.O.