Datastrukturer og algoritmer
Henning Christiansen
22/9-2002
F¿lgende er ikke en eksakt besvarelse af opgaven, idet den benytter hashtabeller og ikke den banale array-repr¾sentation, som er foreslŒet i opgaven (hashtabeller f¿rst omtalt pŒ kurset efter opgaven blev stillet). Opgaveformuleringen foruds¾ttes kendt og forstŒet. Kildetekst til besvarelse: Word.java, Segment.java, SegmentCount.java
Word-klassen har kun et ikke-statisk medlem som er en heltalsvariabel kaldet wordNo. Konstruktoren kaldes med en tekststreng som parameter, og klassen opretholder en en-til-en relation mellem streng og wordNo for de strenge som er forekommet (dvs. sendt med konstruktoren). En hashtabel som er f¾lles for alle objekter i klassen afbilder strenge over i wordNo, sŒ den kan bruges af konstruktoren. F¿rste forekommende streng tildeles nr. 0, n¾ste nr. 1, og sŒ fremdeles. For at kunne implementere en toString metode pŒ effektiv mŒde opretholdes afbildningen fra nummer til faktisk string i et array, sŒ Word objekt med nr. n har sin streng i dette arrays position n. Endelig indeholder klassen en equals-metode som sammenligner pŒ wordNo.
Kildeteksten Word.java minus faciliteter til de efterf¿lgende sp¿rgsmŒl kan skitseres som f¿lger:
public
class Word {
public
Word(String s)
{Object foundWordNo;
if( (foundWordNo =
table.get(s)) != null )
wordNo =
((Integer)foundWordNo).intValue();
else { wordNo =
wordCount++;
table.put(s, new Integer(wordNo));
stringTable[wordNo]=s;};};
public
String toString() {return stringTable[wordNo];};
// the
following very inefficient way to compare two ints... sic, Java :(
public
boolean equals(Object rhs){
if(rhs==null || getClass() !=
rhs.getClass()) return false;
return wordNo == ((Word)rhs).wordNo;};
private
int wordNo;
public
int wordNo() {return wordNo;};
private
static int wordCount = 0;
private
static HashMap table = new HashMap(10000);
private
static String [] stringTable = new String [10000];
}
Sekvenser af l¾ngde mellem 1 og 4 ord repr¾senteres ved en klasse Segment, som uden grundl¾ggende ser sŒledes ud:
public
class Segment {
public static final int
maxSegmentLength = 4; // hardwired in code :(
Word [] words;
public Segment(Word w1)
{ words = new Word [1];
words[0]=w1;};
public Segment(Word w1,Word w2)
{ words = new Word
[2];words[0]=w1;words[1]=w2;};
public Segment(Word w1,Word w2,Word w3)
{ words = new
Word[3];words[0]=w1;words[1]=w2;words[2]=w3;};
public Segment(Word w1,Word w2,Word
w3,Word w4)
{ words = new
Word[4];words[0]=w1;words[1]=w2;words[2]=w3;
words[3]=w4;};
public
String toString()
{String s
="";
for(int i=0;
i<words.length; i++) s= s + " " + words[i];
return s;}
public boolean equals(Object rhs){
if(rhs==null || getClass()
!= rhs.getClass()) return false;
if(words.length !=
((Segment)rhs).words.length) return false;
for(int i=0;
i<words.length; i++)
if(!words[i].equals(
((Segment)rhs).words[i])) return false;
return true;};
}
Vi har valgt at repr¾sentere sekvensen ved et array af Word objekter, hvor l¾ngden af arrayet svarer til antallet af ord. Der er fire forskellige konstrukt¿rer svarende til de forskellige l¾ngder. Dette er ikke helt hensigtsm¾ssigt, da der skal skrives nye konstrukt¿rer sŒfremt nogen kunne finde pŒ at s¾tte den mulige maksimale sekvensl¾ngde op. Det havde v¾ret mere hensigtsm¾ssigt i det lys med kun en konstruktor (der sŒ skulle tage et array eller lignende af Word objekter som argument).
Opt¾lling af strenge sker ved en separat klasse SegmentCount der indeholder en hashtabel fra segment til antal gange det er forekommet, og sŒ en main-metode som indl¾ser ord fra en fil.
Opgaveformuleringen beskriver, at inputfilen skal slutte med ordet ÒendoffileÓ sŒ vi kan bruge det til at teste om vi er f¾rdige. For at fŒ det til at virke, tilf¿jer vi f¿lgende til Word klassen:
private
static int endoffileWordCount;
public
boolean isEndoffileWord() {return wordNo == endoffileWordCount;};
public static Word readWord(FileReader f) { ... se kildetekst ... };
Konstanten endoffile defineres i en statisk initialiseringdel i Word ved at skrive
new
Word("endoffile"); endoffileWordCount=wordCount-1;
public boolean isEndoffileWord(){return wordNo==endoffileWordCount;};
Klassen SegmentCount kan skitseres som f¿lger; det bliver noget forgr¾mmet pŒ grund af indl¾sning fra fil:
public
class SegmentCount {
public
static void main(String [] args) throws IOException{
FileReader dataFile = new FileReader("duckling");
Word w1 = Word.readWord(dataFile);
Word w2 = Word.readWord(dataFile);
Word w3 = Word.readWord(dataFile);
Word w4 = Word.readWord(dataFile);
while(!w4.isEndoffileWord())
{count(new
Segment(w1));
count(new Segment(w1,w2));
count(new Segment(w1,w2,w3));
count(new Segment(w1,w2,w3,w4));};
w1=w2;w2=w3;w3=w4;w4=Word.readWord(dataFile);
};
//the end
count(new Segment(w1));
count(new Segment(w1,w2));
count(new Segment(w1,w2,w3));
count(new Segment(w2));
count(new Segment(w2,w3));
count(new Segment(w3));
//print
out those occurring 3 or more times
slettet her, da det bliver meget klodset pga. designb¿ffer i Java; se
kildetekst
};
private static HashMap segmentCounts =
new HashMap(10000) ;
private static class IntegerVar //to be
use in segmentCounts only
{public int
value;
public
IntegerVar(int i){value=i;};
public
void inc(){value++;};
public
String toString(){return ""+value;};};
public static void count(Segment s)
{Object foundSegCount;
if( (foundSegCount =
segmentCounts.get(s)) != null )
((IntegerVar)foundSegCount).inc();
else
segmentCounts.put(s, new IntegerVar(1));
};
Strukturen omkring hashtabellen skyldes at vi ikke kan opbare heltal i en hashtabel, men det skal v¾re noget som er underklasse af Object. Vi kunne i princippet benytte objekter af java.langÕs Integer klasse, men de har den egenskab, at deres v¾rdi ikke kan t¾lles op (de er ÒimmutableÓ). Det ville betyde, at for at t¾lle Žn op for en sekvens, sŒ skulle vi slette en indgang i hashtabellen (med det gamle Integer objekt), oprette en ny Integer objekt med en h¿jere v¾rdi og endelig l¾gge det eksplicit ind i tabelle.
For at undgŒ alt det, har vi indf¿rt en lokal klasse IntegerVar som kan t¾lles op med med en metode ÒincÓ.
Bem¾rk at koden som foretager opt¾llingen er afh¾ngig af at den valgte max-l¾ngde for sekvenser. Det ville v¾re bedre at formulere denne del af koden i form af en l¿kkekonstruktion, som afl¾ste konstanten maxSegmentLength i klassen Segment.
Der beskrives en l¿sning, som tager hensyn til de sŒkaldte stopwords med det samme. Desuden tages der et s¾rligt hensyn til ordet ÒtheÓ som ikke fremgŒr af opgaven; forklares nedenfor.
Vi har indf¿rt en metode i klassen Segment som afg¿r om det givne segment er interessant:
public boolean isInteresting() {....};
For at kunne implementere den mŒ vi kunne klassificere de enkelt Word objekter i underarter. En mulighed kunne v¾re at lave forskellige underklasser af Word, men det ville medf¿re at Java-Compileren mŒ tilf¿je ekstra dynamisk typeinformation til den faktiske objektrepr¾sentation. I stedet har vi valgt at koble boolÕske metoder pŒ Word klassen, som sp¿rger til arten af Word objektet. Stopord skal indl¾ses fra en fil nŒr klassen startes, sŒ derfor har Word en statisk initialiseringsdel, som g¿r det. Implementationen er sŒ visseligt indrettet, at den tildeler ordnr. 0 til Òend-of-fileÓ. Derefter indl¾ses all stopordene og ÒoprettesÓ med new... dvs. de fŒr de efterf¿lgende numre, og vi kan registrere ordt¾llerens aktuelle v¾rdi i en skjult variabel maxStopwordCount; dvs. ord med lavere nummer er stopord, med h¿jere, ikke et stopord. Som et eksperiment er artiklen ÒtheÓ ikke i dette program opfattet som storord, men som et s¾rligt ord (det kommer vi til senere).
Den statiske initialiseringsdel i word bliver nu sŒdan her (bem¾rk, at stopordsfilen ogsŒ forventes at slutte med ÒendoffileÓ):
new
Word("endoffile"); endoffileWordCount = wordCount-1;
FileReader
stopWordFile = new FileReader("stopwords");
Word w =
readWord(stopWordFile);
while(!w.isEndoffileWord())
w=readWord(stopWordFile);
maxStopwordCount
= wordCount-1;
new
Word("the"); theWordCount = wordCount-1;
Metoderne i klasse Word til klassifikation bliver nu sŒledes:
public
boolean isStopword() {return wordNo <= maxStopwordCount;};
public
boolean isTheWord() {return wordNo == theWordCount;};
public
boolean isEndoffileWord() {return wordNo == endoffileWordCount;};
public
boolean isContentWord() {return !isStopword() && !isTheWord();};
Som det fremgŒr indf¿rer vi en ny kategori ÒContentWordÓ som er alt som ikke er stopord eller ÒtheÓ; bem¾rk at Òend-of-fileÓ pŒ denne mŒde ogsŒ kategoriseres som stopord, men det skulle helst v¾re lige meget, da den ikke er t¾nkt at skulle proppes ind i segmenter.
Vi kan nu udfylde metoden i Segment som afg¿r hvorvidt en sekvens er interessant (dvs. om vi gider at t¾lle den med):
public boolean isInteresting()
{ if(words[0].isStopword())
return false;
if(!words[words.length-1].isContentWord()) return false;
return true;};
Det er lige for at modificere main metoden i SegmentCount sŒ den kun t¾ller de interessante med. Vi har i udskriften af analysen af den grimme ¾lling pŒ engelsk begr¾nset os til at vise sekvenser pŒ l¾ngde 3 og derover som forekommer mindst 4 gange:
among the rushes: 3
the tom cat: 4
said the hen: 3
the poor duckling: 3
the poor little: 4
said the duckling: 3
said the old duck: 3
said the duck: 3
said the old: 4
said the mother: 4
the old duck: 3