/ Forside / Karriere / Uddannelse / Højere uddannelser / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
Højere uddannelser
#NavnPoint
Nordsted1 1588
erling_l 1224
ans 1150
dova 895
gert_h 800
molokyle 661
berpox 610
creamygirl 610
3773 570
10  jomfruane 570
forskelle på strenge
Fra : Jakob Nielsen


Dato : 26-12-04 22:17

HVis vi har to strenge
A="dette er en test"
B="det var testen"

så kan b udtrykkes som funktion af a og man kan eventuelt tegne et diagram
over dem begge som i nedenstående fastbredde ascii-grafik
te_er_en_
/ \
det test
\ / \
_var_---- en

Den nedre tekst er midterste linie og forgreninger ned og angiver B. B kan
så beskrives som A plus information om de øvre og nedre linier, hvor den
øvre er det der er fjernet fra A og de nedre er det der er tilføjet ekstra
til B. Givet den beskrivelse og A kan man gendanne B.

Det kan løses manuelt, selvom der findes situationer hvor flere løsninger
findes. Når de forekommer kan man vælge den udgave der fylder mindst.
Spørgsmålet er bare hvad en algoritme til løsning af opgaven mon kan hedde?
Jeg har ikke haft meget held med at find brugbar information om det. Måske
nogen her ved det, eller kan give et bud på en programmeringsmæsig løsning?




 
 
John Smith (26-12-2004)
Kommentar
Fra : John Smith


Dato : 26-12-04 22:47

Jakob Nielsen wrote:
> HVis vi har to strenge
> A="dette er en test"
> B="det var testen"
>
> så kan b udtrykkes som funktion af a og man kan eventuelt tegne et diagram
> over dem begge som i nedenstående fastbredde ascii-grafik
> te_er_en_
> / \
> det test
> \ / \
> _var_---- en
>
> Den nedre tekst er midterste linie og forgreninger ned og angiver B. B kan
> så beskrives som A plus information om de øvre og nedre linier, hvor den
> øvre er det der er fjernet fra A og de nedre er det der er tilføjet ekstra
> til B. Givet den beskrivelse og A kan man gendanne B.
>
> Det kan løses manuelt, selvom der findes situationer hvor flere løsninger
> findes. Når de forekommer kan man vælge den udgave der fylder mindst.
> Spørgsmålet er bare hvad en algoritme til løsning af opgaven mon kan hedde?
> Jeg har ikke haft meget held med at find brugbar information om det. Måske
> nogen her ved det, eller kan give et bud på en programmeringsmæsig løsning?
>
Jeg er ikke helt sikker på hvad det er du fisker efter, men det lyder
for mig lidt som en gramatik til et sprog - forstået i datalogisk forstand?

Men det giver ikke lige mening. Hvis sproget har sætningerne "det-te er
en test" og "det var test-en" så har du kun een stavelse der er fælles:
nemlig "det".
Alle udfald af sproget kan skrives som (uden den rette nørd jargon):
"det" eferfulgt af "te-er-en" eller "var" efterfulgt af "test" og "en".

Men hov - så passer vores gramatik jo ikke længere med vores sprog...
Kan du se problemet? Der er et "en" for meget i et af udfaldene...

Et sprog kunne bestå af ordene {"Lise", "har", "en", "rød", "blå",
"bold"}. Grammatikken kunne være: "Lise" efterfulgt af "har" efterfulgt
af "en" efterfulgt af ("rød" eller "blå") efterfulgt af "bold".

Man kan altså udtrykke at Lise har enten en rød eller blå bold.

Der er helt formaliserede måder at udtrykke et sprog og en gramatik på,
der er væsentligt nemmere at læse når man kender nomenklaturen.

Jeg vil foreslå at du kikker nærmere på emnerne syntaks og sematik og
sprog. Tingene bruges udbredt inden for programmering af compilere og
fortolkere til computere og er et af de mest underbyggede områder. Der
er nok at sætte tænderne i

Mvh
John Smith

Jakob Nielsen (26-12-2004)
Kommentar
Fra : Jakob Nielsen


Dato : 26-12-04 23:05

> Jeg er ikke helt sikker på hvad det er du fisker efter, men det lyder for
> mig lidt som en gramatik til et sprog - forstået i datalogisk forstand?

Nej ikke et sprog. Handler udelukkende om repræsentation af en tekst baseret
på en anden.
Frem for at lagre hele A og hele B så ønsker jeg at lagre hele A og en
forskelsbeskrivelse der lader mig danne B ud fra A og forskellen.



Jakob Nielsen (26-12-2004)
Kommentar
Fra : Jakob Nielsen


Dato : 26-12-04 22:58

Jeg kan sikkert ikke nå at slette indlæget før det bliver set her og der, så
lad mig bare beklage at jeg igen fandt det jeg søgte næsten lige efter jeg
postede.
vdiff med anvendelse af største fælles subsekvens er tilsyneladende det jeg
ledte efter.

Nu er jeg så der henne at det ikke virker optimalt på mig. Opgaven er jo
grundlæggende set at danne B fra A+dif. Kan man ikke lave en art kompression
hvor man bruger A som referencedata, så B beskrives som blokke af pointere
over i A og for ufundne blokke blokke med nyindsat data?

Eksemplet fra før, igen bedst med fastbreddefont
0123456789ABCDEF
A:dette_er_en_test
B:det_var_testen

blokke består af (startindex,længde) og er adskildt med :
blokke uden parantes er rå data som bare indsættes

B beskrevet ud fra A er da
(0,3):_va:(7,2):(c,4):(9,2)

Blokkene skal pakkes som man gør i gængs kompression med sliding window, og
så er den vel fin?
Med et andet eksempel virker fælles sekvens dårlig til at repræsentere
kompakt, mens ""min"" metode er god?:

0123456789ABCDEF
A:deterdeterdeterd
B:detedetedetedetedetedetedete
(0,4):(0,4):(0,4):(0,4):(0,4):(0,4):(0,4)

Kommentarer er velkomne. Formålet med routinen er at lagre mange versioner
af datafiler på en kompakt måde.




Jakob Nielsen (26-12-2004)
Kommentar
Fra : Jakob Nielsen


Dato : 26-12-04 23:11

> 0123456789ABCDEF
> A:deterdeterdeterd
> B:detedetedetedetedetedetedete
> (0,4):(0,4):(0,4):(0,4):(0,4):(0,4):(0,4)

Måske et dumt eksempel da subsekvensen faktisk er stor.

prøver istedet
A:det er lige sådan man skal gøre sådan noget
B:det er det er det er det er det er det er
her er subsekvensen kun "det er ", men blokken gentages igen og igen og kan
hver gang genfindes i A, så B kan beskrives med 5 blokke der peger ind i A,
men med subsekvens er længden kun 6 tegn og resten af tegnene skal beskrives
eksplicit.



Martin Larsen (26-12-2004)
Kommentar
Fra : Martin Larsen


Dato : 26-12-04 23:43

"Jakob Nielsen" <a@b.c> skrev i en meddelelse news:41cf36f5$0$172$edfadb0f@dtext01.news.tele.dk...
> > 0123456789ABCDEF
> > A:deterdeterdeterd
> > B:detedetedetedetedetedetedete
> > (0,4):(0,4):(0,4):(0,4):(0,4):(0,4):(0,4)
>
> Måske et dumt eksempel da subsekvensen faktisk er stor.
>
Du har vist ikke fundet på noget afgørende nyt i forhold til
de kompressionsteknikker som allerede findes. (Og som
er velbeskrevne)

Mvh
Martin



Jakob Nielsen (26-12-2004)
Kommentar
Fra : Jakob Nielsen


Dato : 26-12-04 23:54

> Du har vist ikke fundet på noget afgørende nyt i forhold til
> de kompressionsteknikker som allerede findes. (Og som
> er velbeskrevne)

Det har jeg forhåbentlig heller ikke antydet at jeg har?
Problemet er dog et andet end ved kompression af en enkelt datastrøm med
eksempelvis et sliding window, da ens vindue her skal placeres i den ældste
fil og matches skal findes fra den nye. Disse skal synkroniseres på en måde,
så problemet adskilder sig og jeg har derfor ikke kunnet find noget
velbeskrevet andet end største fælles subsekvens.



Niels L. Ellegaard (26-12-2004)
Kommentar
Fra : Niels L. Ellegaard


Dato : 26-12-04 23:51

"Jakob Nielsen" <a@b.c> writes:

>> 0123456789ABCDEF
>> A:deterdeterdeterd
>> B:detedetedetedetedetedetedete
>> (0,4):(0,4):(0,4):(0,4):(0,4):(0,4):(0,4)
>
> Måske et dumt eksempel da subsekvensen faktisk er stor.
>
> prøver istedet A:det er lige sådan man skal gøre sådan noget B:det
> er det er det er det er det er det er her er subsekvensen kun "det
> er ", men blokken gentages igen og igen og kan hver gang genfindes i
> A, så B kan beskrives med 5 blokke der peger ind i A, men med
> subsekvens er længden kun 6 tegn og resten af tegnene skal beskrives
> eksplicit.

Måske kan du få nogle gode ideer ved at kigge på diffutils til
Linux. Dette program har meget til fælles med din ide, men det kan kun
håndtere subsekvenser der består af hele linier.

http://www.gnu.org/software/diffutils/manual/html_mono/diff.html





Jakob Nielsen (26-12-2004)
Kommentar
Fra : Jakob Nielsen


Dato : 26-12-04 23:57

> Måske kan du få nogle gode ideer ved at kigge på diffutils til
> Linux. Dette program har meget til fælles med din ide, men det kan kun
> håndtere subsekvenser der består af hele linier.

Ja, det er den retning jeg finder info lige nu. Den bruger også største
fælles subsekvens.
Spørgsmålet er vel nu om jeg ser mig blind på problemer som er urealistiske.
Hele pointen med det her er jo at beskrive B som A+diff og det giver sig
selv at hvis A og B er meget ens, så er diff lille og hvis de er meget uens,
så er diff stor. De eksempler jeg stillede op til sidst er jo strengt taget
eksempler på meget forskellige A og B og det er vel rimeligt nok at diff
bliver stor. Man kan konstruere eksempler hvor diff bliver stor men block
matchning giver lille repræsentation. Måske de konstruerede eksempler er
dybt urealistiske?




Niels L. Ellegaard (27-12-2004)
Kommentar
Fra : Niels L. Ellegaard


Dato : 27-12-04 20:45

"Jakob Nielsen" <a@b.c> writes:

> Ja, det er den retning jeg finder info lige nu. Den bruger også
> største fælles subsekvens. Spørgsmålet er vel nu om jeg ser mig
> blind på problemer som er urealistiske. Hele pointen med det her er
> jo at beskrive B som A+diff og det giver sig selv at hvis A og B er
> meget ens, så er diff lille og hvis de er meget uens, så er diff
> stor. De eksempler jeg stillede op til sidst er jo strengt taget
> eksempler på meget forskellige A og B og det er vel rimeligt nok at
> diff bliver stor. Man kan konstruere eksempler hvor diff bliver stor
> men block matchning giver lille repræsentation. Måske de
> konstruerede eksempler er dybt urealistiske?

Det er lidt svært at snakke med, hvis du ikke giver en mere præcis
beskrivelse af den opgave du forsøger at løse. Du beskriver et meget
generelt problem, men hvis jeg har forstået dig rigtigt, så er du i
virkeligheden interesseret i at løse et meget specifikt problem.

Jakob Nielsen (27-12-2004)
Kommentar
Fra : Jakob Nielsen


Dato : 27-12-04 21:29

> Det er lidt svært at snakke med, hvis du ikke giver en mere præcis
> beskrivelse af den opgave du forsøger at løse. Du beskriver et meget
> generelt problem, men hvis jeg har forstået dig rigtigt, så er du i
> virkeligheden interesseret i at løse et meget specifikt problem.

Jeg tåger nok lidt rundt i den her tråd. Har dog tidligere skrevet
"Formålet med routinen er at lagre mange versioner af datafiler på en
kompakt måde."

Det jeg vil er at lagre mange versioner af samme binære datafil ved at lagre
den første udgave i fuld længde og lagre version 2..n som forskellen mellem
dem selv og den foregående version. Hvis ændringerne er få og små, så er
ændringerne meget kompakte.

Jeg overvejer så nu at bruge største fælles sekvens (longest common
subsequence) og en metode alla vdiff fra unix og jeg overvejer at bruge en
anden metode som er en art variation over mange gængse
kompressionsalgoritmer hvor man har et sliding window hvori man søger at
finde største match for de data man er ved at kode nu. Tanken er at version
2 vil kunne beskrives rimelig kompakt ud fra referencer ind i version 1. Jeg
overvejer så hvilken metode der egentlig er mest velegnet til løsning af
problemet. Dels virker det meget bekosteligt at beregne største fælles
sekvens med den array på datalængde1*datalængde2 man skal bruge. For store
filer kan det blive voldsomt.

Tåger måske stadig lidt, men nu er problemstillingen vel i det mindste klar?




Bjarke Dahl Ebert (29-12-2004)
Kommentar
Fra : Bjarke Dahl Ebert


Dato : 29-12-04 09:56

Jakob Nielsen wrote:

> Jeg tåger nok lidt rundt i den her tråd. Har dog tidligere skrevet
> "Formålet med routinen er at lagre mange versioner af datafiler på en
> kompakt måde."

Jeg synes du beskriver problemet klart nok - det er vist svarene der
tåger rundt... ;)

Prøv at kigge på xdelta - http://sourceforge.net/projects/xdelta/

Det er et library til effektiv lagring af mange versioner af "samme" fil.

Et mere komplet system (applikation snarere end library) er Subversion -
http://subversion.tigris.org/


Mvh. Bjarke

Jakob Nielsen (29-12-2004)
Kommentar
Fra : Jakob Nielsen


Dato : 29-12-04 13:54

> Jeg synes du beskriver problemet klart nok - det er vist svarene der tåger
> rundt... ;)

Takker. Den tolkning lyder da egentlig også bedre, så den hopper jeg med på


> Prøv at kigge på xdelta - http://sourceforge.net/projects/xdelta/

Tak igen. Der er endda kildekode med, så det skal jeg nok kunne blive klog
på.
Tror jeg vil opgive mine forsøg med at opfinde en effektiv algoritme selv.
Det viser sig hver gang efter flere dages hovedbrud at det jeg har opfundet
har været velkendt årevis..



Martin Larsen (29-12-2004)
Kommentar
Fra : Martin Larsen


Dato : 29-12-04 15:23

"Jakob Nielsen" <a@b.c> skrev i en meddelelse news:41d2a905$0$166$edfadb0f@dtext01.news.tele.dk...
> > Jeg synes du beskriver problemet klart nok - det er vist svarene der tåger
> > rundt... ;)
>
> Takker. Den tolkning lyder da egentlig også bedre, så den hopper jeg med på
>
>
Hvor yndigt som I kan finde sammen i tågen

Mvh
Martin



Jakob Nielsen (29-12-2004)
Kommentar
Fra : Jakob Nielsen


Dato : 29-12-04 16:48

> Hvor yndigt som I kan finde sammen i tågen

Jamen der er da plads til flere, så det var hyggeligt at du kunne komme
forbi



Søg
Reklame
Statistik
Spørgsmål : 177552
Tips : 31968
Nyheder : 719565
Indlæg : 6408847
Brugere : 218887

Månedens bedste
Årets bedste
Sidste års bedste