---

Hej.

Er der nogen her der har kodeforslag/tips/links til at sortere en
islandsk ordlistefil efter det islandske alfabet, som er nogenlunde
sådan:
aábcdðeéfghiíjklmnoópqrstuúvwxyýzþæö
altså meget forskelligt fra det danske både mht bogstaver og
rækkefølge.
Jeg bruger Turbo Pascal 7 og har selve sorteringen klar, men det
kniber med den rigtige rækkefølge.

--
Mvh Ebbe Poulsen

---

Jeg er i tvivl om, hvorvidt du spørger efter algoritmen eller efter
rækkefølgen af bogstaverne i det islandske alfabet.

Men eftersom du angiver, hvilken version af Delphi/Pascal du anvender, så
antager jeg, at det er algoritmen, du leder efter.

En sorteringsalgoritme er den samme for alle sprog, bortset fra
sammenligningsfunktionen. Her skal du omregne tegnene til tal-værdier, der
så sammenlignes, hvor talværdierne er i korrekt sorteringsrækkefølge. Den
konkrete kodning afhænger lidt af, om du bruger 8-bit tegnsæt eller utf-8
(unicode fandtes ikke i TP7), men du bruger jo nok 8-bit tegnsæt? Her er
det simpelt:

var tabel:array[char] of integer;

initialisering:
tabel['a']:=1;
tabel['á']:=2;
tabel['b']:=3;
tabel['c']:=4;
tabel['d']:=5;
tabel['ð']:=6;
tabel['e']:=7;
tabel['é']:=8;
tabel['f']:=9;
tabel['g']:=10;

osv.

og sammenligningen laves om fra:

if c1<c2

til:

if tabel[c1]<tabel[c2]

Det var det.

Jeg går ud fra, at du ikke bruger utf-8 - hvis du gør det, så sig til, så
giver jeg dig gerne algoritmen for denne.

Lars Dybdahl.


Ebbe Poulsen wrote:
> Er der nogen her der har kodeforslag/tips/links til at sortere en
> islandsk ordlistefil efter det islandske alfabet, som er nogenlunde
> sådan:
> aábcdðeéfghiíjklmnoópqrstuúvwxyýzþæö
> altså meget forskelligt fra det danske både mht bogstaver og
> rækkefølge.
> Jeg bruger Turbo Pascal 7 og har selve sorteringen klar, men det
> kniber med den rigtige rækkefølge.

--

Dybdahl Engineering: http://dybdahl.dk/
Delphi brugergruppen DAPUG: http://dapug.dk/

---

On Sat, 21 Dec 2002 22:13:20 +0100, "Lars B. Dybdahl"
<Lars@dybdahl.dk> wrote:

>Jeg er i tvivl om, hvorvidt du spørger efter algoritmen eller efter
>rækkefølgen af bogstaverne i det islandske alfabet.
>

Tak for svaret; jeg er ked af at spørgsmålet ikke var tydeligt.
Her er en uddybning. Måske er det faktisk begge områder der skal
klargøres eller forbedres.

1. ´codepage´ - afdeling eller ´det islandske alfabet´
> var tabel:array[char] of integer;
eller som jeg forsøgte:
IceAlphabet := 'aábcdeéfg ....ýzþæö'; hvor der så måles på index
2. algoritme-afdeling
Den jeg bruger virker langsom, så vejledning til en hurtigere
vil være velkommen; se nedenfor.

ad 1.
Min forståelse af den afgørende sammenhæng mellem codepage, unicode,
utf-8, Charset Windows-1252, iso-8859-1 ... osv er ikke stor, så jeg
vidste/ved ikke om man så at sige skal emulere en codepage
861(Iceland) og bruge den som en look-up table á la din ´var tabel:
..´

Ved de første kørsler fik jeg nogle gange rigtige resultater, andre
gange forkerte, som jeg ikke kunne gennemskue om de kom fra dårlig
kode eller fordi min streng IceAlphabet jo ikke dækker alle mulige
andre tegn der kan forekomme i en ordfil.

Filen er ganske lang: godt 40300 linjer (ca 600 Kb) med islandske ord
efter fgl opbygning eller format:
I=Icelandic E=English G=German C=Comment
(Min tillempning af htm-filer fundet lexis.hi.is/sofn.html)
Jeg udfylder så E= osv. - pt fra en lille islandsk-engelsk ordbog)

ad 2. algoritmen
Som skabelon for rutiner der skal sortere har jeg med held brugt hvad
jeg tidligere har fundet via comp.lang.pascal.borland
From: Andreas Killer (andreas.killer@t-online.de)
Subject: Re: linked list and pointer problems
Newsgroups: comp.lang.pascal.borland Date: 2000-11-26 14:10:59 PST
(Eks. på mine tidligere anvendelser på Opera browserens hotlist fil:
http://users.cybercity.dk/~bkb1945/opera/
)

Her er den kodestump der skal laves om til tal, så man selv
sammenligner to indextal i stedet for at lade TP7 sammenligne to
strenge.
{ beg: kodestump i Andreas Killers notation }
while Work <> nil do begin
if Work^.Title > A^.Title then {<<--------HER}
Exit;
{ end: kodestump }

{ beg: kodestump erstatning }
Line01 := Work^.Title; Line02 := A^.Title;
i := 0;
repeat { Find stedet hvor forskellen er }
iHold := i;
Inc(i);
until ( Line01[i] <> Line02[i] );

PosLine01 := Pos(Line01[iHold+1], IceAlphabet);
PosLine02 := Pos(Line02[iHold+1], IceAlphabet);

if PosLine01 > PosLine02 then
Exit;
{ end: kodestump erstatning }

Det ser ud til at virke, men er ikke afprøvet med alle mulige
underlige tegn udenfor IceAlphabet, og forekomsten af sådanne tegn
måske ødelægge sorteringen. Man skal måske være dækket ind helt ud i
hjørnerne for at der ikke på et eller andet tidspunkt sker noget
utilsigtet.
Det tager ca 4 gange så lang til at sortere de 40300 linjer med
erstatnings-kodestumpen indskudt (ca 100 min med 166 MHz), så det er
nok en helt anden algoritme-type der skal bruges ?
Er det en slags QSORT.PAS tilpasset til brug på store filer med
almindelig tekst og ikke blot tal i et array som i eksemplet i
QSORT.PAS ?
Her vil lidt vejledning være vel anbragt og blive påskønnet.

PS. Det jeg forsøger at lave kan vel kaldes ´Islandsk ordfil med
tilknyttede små utilities´ for nybegyndere i islandske ord. Og hvis
andre end jeg selv skulle ende med at få lidt gavn af det, så var det
rart at få sorteringstiden bragt ned.

--
Mvh Ebbe Poulsen

---

Sorteringsalgoritmer:

Der findes et utal af sorteringsalgoritmer, der hver for sig har deres
fordele. Quicksort er godt til ting, der stort set er sorteret i forvejen,
men til at sortere helt usorterede ting, er Quicksort faktisk ret elendig
til. Min personlige favorit hedder Mergesort, som ved gode implementationer
har god performance i stort set alle sammenhæng - bortset fra at den bruger
noget memory til at holde styr på alle de tekster, der skal sorteres.

De fleste, der skal sortere noget, bruger den sorteringsfunktion, som ens
værktøj tilbyder, og her er TStringList.CustomSort en mulighed.


Tegnsæt:

Alt i en computer gemmes som bytes, som hver indeholder en værdi på 0-255.
Når man vil gemme tekst i en computer, bruges et tegnsæt, og et tegnsæt er
simpelthen en måde at oversætte bogstaver til bytes. De mest kendte er:

ASCII: Kun værdierne 32-127 bruges, og æøåÆØÅ har ingen talrepresentation.
Bogstavet A svarer til talværdien 65, og det lille a har talværdien 97.

ANSI: Svarer nogenlunde til ISO8859-1 og er standardtegnsættet i en dansk
WIndows

ISO8859-1: Bruges i Danmark og USA til internet formål. Alle tegn gemmes som
et byte, og et Æ har værdien 198.

Unicode: (også kaldet UCS-2) bruger to bytes ad gangen, som sammensættes til
en talværdi 0-65535. Værdierne 0-255 svarer til ISO8859-1, men som man nok
kan regne ud, indeholder Unicode en masse tegn, som simpelthen ikke findes
i ISO8859-1, bl.a. græske, russiske, japanske tegn osv.

UCS: Bruger talværdier fra 0 til 2 milliarder, og indeholder derfor endnu
flere tegn end Unicode. Værdierne 0-65535 svarer til Unicode tegnsættet.
Man kalder det "UCS-4", når man bruger 4 bytes for hvert tegn, og "UCS-2",
når man bruger 2 bytes til hvert tegn. På den måde svarer UCS-2 til
Unicode.

UTF-8: En anden måde at skrive UCS tegn på. Ideen er, at bruge et variabelt
antal bytes per tegn. ASCII tegn skrives på almindelig måde med 1 byte per
tegn, og talværdier på 0-127. UCS tegn med værdier over 127 skrives med 2
eller flere bytes, og således fylder et Æ to bytes, der har værdierne 195
og 134.

De fleste tegnsæt, der ikke er nævnt her, opfører sig enten som UTF-8, ved
at de bruger et variabelt antal bytes per tegn, eller også benytter de 1
byte per tegn ligesom ISO8859-1, bortset fra at talværdierne 128-255
referer til andre tegn.

Eftersom du bruger Delphi, vil jeg anbefale dig at lave
sammenligningsfunktionen med variable af typen widestring. Disse kan
indeholde unicode tegn (UCS-2). Hvis du f.eks. har:

var s:widestring;

så har ord(s[3]) en værdi på mellem 0 og 65535.

Her vil tabellen fra mit forrige indlæg være defineret således:

var tabel:array[widechar] of integer;

Du skal derfor konvertere fra dine forskellige andre tegnsæt til
unicode/widechar, og her skal du så vide, hvilke tegnsæt dine data ligger
i, og hvordan disse kan konverteres. Delphi konverterer automatisk fra
maskinens default 8-bit tegnsæt til unicode ved hjælp af Windows's
funktioner, når du tildeler en string til en widestring, men det er jo ikke
sikkert, at det er det, du ønsker. Generelt skal du være forsigtig med at
overlade konvertering til Windows, da mange af Windows's konverteringer er
afhængig af maskinens indstillinger og derfor ikke altid vil opføre sig
ens, når du installerer programmerne ude hos slutbrugerne.

Såvidt jeg forstår, vil du sortere noget, der både indholder islandsk tekst
og engelsk tekst, så du bliver derfor nødt til at afgøre med dig selv,
hvordan engelske tekster og islandske tekster skal flettes ind i hinanden
ved sorteringen, og så tildele talværdier derefter.

Windows har selv indbyggede faciliteter til tekst-sammenligning, men jeg er
ikke sikker på, hvordan det fungerer, når du har flere sprog blandet
sammen, og mine personlige erfaringer siger mig, at slutbrugeren også kunne
have specielle ønsker. Men her findes der ganske kompetente folk på news
serveren forums.borland.com i sektionen
borland.public.delphi.internationalization, hvor jeg synes du bør spørge.

Jeg håber jeg har hjulpet dig lidt på vej, men en komplet besvarelse kræver
nok et bedre kendskab til, hvad du forsøger at gøre.

Hilsen,

Lars Dybdahl.

--

Dybdahl Engineering: http://dybdahl.dk/
Delphi brugergruppen DAPUG: http://dapug.dk/

---

On Fri, 27 Dec 2002 18:15:31 +0100, "Lars B. Dybdahl"
<Lars@dybdahl.dk> wrote:

Tak for det uddybende svar. Jeg vil gå igang med at sætte mig ind i de
forskellige begreber.
(Jeg tror du glemte at jeg bruger TP7 og ikke Delphi.)

Jeg forsøger her at fortolke hvad du skriver - over i min situation
med TP7:

1. Tegnsæt.

Ordfilen er vel hvad der kaldes en ´flatfile database´, hvortil jeg
har lavet små utilities som var tiltænkt brug for nybegyndere - som
jeg selv er - (simpelt opslag ved strengstump + hukommelsestræning)


Her er en stump af den simple ordfil
I=Icelandic E=English G=German C=Comment
I=baðherbergi n E=bathroom
I=banvænn adj E=deadly, mortal
I=batna v E=recover, get better, improve C=T has ´vi´ (verb intrans.)
I=báðumegin adv & præp (w gen) E=on both sides (of) C=T
I=bál n E=flame
....
I=Lönd, þjóðaheiti, tungumál G=Länder C=abcdä
I=Lönd, þjóðaheiti, tungumál G=Länder C=abcdß

^her
Ovenfor er to linjer der er ens næsten indtil slut, hvor de så
indeholder to tegn der ikke indgik i min IceAlphbet := ´aáb....´. Hvis
jeg forstår det du skriver ret, skulle jeg så tilføje alle de tegn jeg
kunne forestille mig der kunne forekomme, til denne alfabetstreng,
eller - fordi der kun er plads til 255 i TP7 - slå over i dit forslag
med
>var tabel:array[widechar] of integer;
eller i TP7:
var tabel:array[char] of integer; med initialisering:
tabel['a']:=1;
tabel['á']:=2; osv.

>hvordan engelske tekster og islandske tekster skal flettes ind i hinanden
Jeg tror ikke man kan sige at forskellige tekster skal flettes sammen.
Derimod måske at den tabel, der skal sorteres efter, kan skifte hen
gennem en linje. Man kunne så have flere tabeller som den du foreslår,
og når E= dukker op, skiftes til engelsk sorteringsrækkefølge; osv med
G= for tysk.

Nu skal det jo ikke dække alle jordens tegnsæt, men hvis princippet er
rigtigt forstået, kan jeg jo begynde at bygge forskellige afprøvninger
op herudfra.


2. Sortering - Jeg har fundet to indlæg med MergeSort:

From: T.Drawneek@massey.ac.nz (T.Drawneek@massey.ac.nz)
Subject: Re: Sorting linked lists
Newsgroups: comp.lang.pascal.borland - Date: 1999/01/10
og:
From: Osmo Ronkanen (ronkanen@cc.helsinki.fi)
Subject: Re: Sorting linked lists
Newsgroups: comp.lang.pascal.borland Date: 1999/01/08

Det ser ud til at jeg kan få dem til at virke almindeligt - dvs som
TP7 fortolker ´større end´ og ´mindre end´ - og det er helt andre
sorteringstider der her er tale om; sekunder hvor den gamle havde
mange, mange minutter. Jeg håber nu at kunne indpasse den alternative
sorteringsrækkeføge.


Da du nu nævner Delphi, kunne jeg spørge om det ville være let at få
en ´incremental search´ til at virke på en sådan ordfil. Som i Windows
Help og som jeg har set i en lille fin online newsreader ´xnews´.
Hvis det er tilfældet, ville det jo være en god grund til at forsøge
at overføre disse ting til Delphi.

--
Mvh Ebbe Poulsen.

---

Ebbe Poulsen wrote:
> (Jeg tror du glemte at jeg bruger TP7 og ikke Delphi.)

Ja

> 1. Tegnsæt.

Såvidt jeg læser din beskrivelse, klarer du så alt inden for et 8-bit
tegnsæt.

> var tabel:array[char] of integer; med initialisering:
> tabel['a']:=1;
> tabel['á']:=2; osv.

Ja. Helt korrekt.

> 2. Sortering - Jeg har fundet to indlæg med MergeSort:

Der er forskellige måder at evaluere sorteringsalgoritmer på:

- Værste situation
- Sortering af tilfældige data.
- Sorterede data med x nye, tilfældige records.
- Gennemsnitstid
- Bedste situation

Quicksort er kendt for at håndtere sortering af næsten sorterede data
utroligt godt på en simpel måde. Princippet er, at den hopper hurtigt hen
over alle sorterede data, til gengæld bruger den en masse tid på at sortere
det, der skal sorteres. Man angiver normalt hastighederne som o(noget),
hvor Quicksort har o(n^2), hvilket betyder at tidsforbruget er
proportionalt med datamængen (n) i anden potens. Fordobler man datamængden,
øges tidsforbruget med en faktor 4. For quicksort gælder dette både for den
værste situation og for gennemsnitstid, hvorimod bedste situation er o(n) -
hvilket svarer til et enkelt gennemløb af alle data.

Den teoretisk mest optimale sorteringsalgoritme har:

- Værst: o(n*log(n))
- Tilfældige data: o(n*log(n))
- Gennemsnitstid: o(n*log(n))
- Sorterede data med x nye records: o(n+x*log(x))
- Bedste situation: o(n)

Mergesort har som udgangspunkt o(n*log(n)) på alle situationer, men ved at
tilføje mere intelligens som minder om Quicksort kan man komme ned på de
optimale tider, jeg har angivet foroven. Desværre har ikke alle
implementationer disse forbedringer, hvorved deres performance på allerede
sorterede datasæt forringes til o(n*log(n)).

Ud over selve sorteringsprocedurens tidsforbrug er der også memory
parameteren. Quicksort bruger stort set ingen extra memory - den bytter
bare rundt på alle elementerne. Mergesort skal derimod holde styr på lister
over elementer, hvilket betyder at den har et hukommelsesforbrug, der er
proportionalt med datamængden, hvilket nutildags dog ikke er det store
problem.

Ud over deciderede sorteringsalgoritmer findes der i øvrigt også en anden
måde at opnå sorterede data: Hold dem sorteret hele tiden. Når du så
tilføjer data, skal du sørge for at indsætte data det rigtige sted, til
gengæld har du dem altid i sorteret rækkefølge...

Incremental read kan man altid lave, når ens data er sorteret. Det kan du
lave både i TP7 og Delphi. Et skift til Delphi bør dog ikke afgøres heraf -
et sådan skift betyder temmeligt meget for din udvikling. Det største skift
består i at du skal lære at ignorere alt de lækre ting, du ikke umiddelbart
har behov for eller tid til at sætte dig ind i

Lars.

--

Dybdahl Engineering: http://dybdahl.dk/
Delphi brugergruppen DAPUG: http://dapug.dk/