Søgemaskinekursus

Cand.it - Mastergradsstudium med spesialisering i softwareutvikling

HiNT

Efterår 2002

Denne hjemmeside :
http://www.it-c.dk/research/algorithms/Kurser/SoegeProjekt/HiNT/


Indhold

Denne side: Andet:

Overordnet

Velkommen til hjemmesiden for søgemaskinekurset. Søgemaskinekurset er tilrettelagt således at studerende med forskellige forudsætninger og mål kan følge kurset. De studerende vil blive opdelt i grupper. Alle grupper skal løse de opgaver der er beskrevet under fællesdelen nedenfor. Dog kan der træffes specielle aftaler for hver gruppe med en lærer. Når en gruppe har løst opgaverne under fællesdelen har gruppen sin første primitive udgave af en søgemaskine, der kan bruges til at søge efter information på for IT-C.

Efter fællesdelen kan gruppen arbejde videre i forskellige retninger. F.eks. kan gruppen arbejde videre med en eller flere af de foreslåede udvidelser. Hvad den enkelte gruppe vælger at arbejde videre med vil afhænge af interesser og forudsætninger. Såfremt gruppen ikke har andre forudsætninger end grundlæggende programmering forventes det ikke at gruppen når meget længere end at besvare fællesdelen. Grupper med flere forudsætninger forventes at nå mere end at besvare fællesdelen.

Hver gruppe skal beskrive sit projektarbejde i en rapport, og denne rapport skal senere forsvares ved en projekteksamen.

I kursusperioden afholdes der projektdage hvor der vil blive givet generel information om projektet og hvor der vil være mulighed for at stille spørgsmål. På disse projektdage vil hver gruppe ligeledes få individuel vejledning af en af kursets lærere, Hvis du eller din gruppe herudover har problemer under projektet, er I velkomne til at henvende jer til en af de lærere, der er tilknyttet projektet.

Lærerne som er tilknyttet kurset vil vejlede i hvilke ting man kan lave, hvordan man gør det, samt hvordan man dokumentere sit arbejde. Spørgsmål om Java og programmeringsproblemer kan rettes til personale på HiNT.

På den første projektdag præsenteres projektet og der vil være mulighed for at danne grupper. Desuden præsenteres de programmeringsteknikker som er nødvendige for at kunne løse fællesdelen. I nedenstående beskrivelse af opgaven vil der således sikkert være ord som du ikke kender før den første projektdag har været afholdt. Specielt vil dele af teksten nok i en eller anden udstrækning være uforståelig, hvis man ikke før har hørt om hægtede lister. Hægtede lister er en af de programmeringsteknikker som bliver præsenteret på den første projektdag.


Opgaven

Datafiler

Til brug for kurset stilles forskellige datafiler der indeholder hele eller dele af IT-Cs hjemmesidestruktur til rådighed. Datafilernes format kan illustreres ved følgende eksempel:

*PAGE:http://www.it-c.dk
Her
står
et
ord
og
et
ord
mere
*PAGE:http://www.it-c.dk/enandenside.html
Her
står
mere
og
endnu
mere

Ideen er altså, at en datafil indeholder informationer om en række hjemmesider. Informationerne for en given hjemmeside starter med en *PAGE linje der angiver hvilken adresse siden findes på. Sådan en adresse kaldes også en URL. Dernæst kommer en liste over de ord siden indeholder. Ordne er blot opremset med et ord pr linje i den rækkefølge de står i på siden. Det fremgår at det samme ord godt kan optræde flere gange under den samme side.

Man kan hente følgende datafiler hvor de første indeholder nogle af IT-Cs hjemmesider og den sidste indeholder allesammen:

Programmet SearchCmd

Som en del af denne opgave udleveres programmet SearchCmd.java som implementerer en lille søgemaskine. Programmet skal, når det udføres, gives navnet på den datafil som det skal bassere sin søgning på, som parameter. Se afsnittet om brug af Java nedenfor for informationer om hvordan man angiver parametre til Java programmer.

Den parameter man angiver til programmet bliver lagt i args[0] hvor args er parameteren til programmets main metode. Det første programmet gør er at konstruere en hægtet liste datastruktur med alle linjerne fra datafilen hvis navn står i args[0]. Objekterne i den hægtede liste indeholder felterne str og next. Feltet str indeholder en linje fra datafilen og next peger på det næste objekt i listen. Efter indlæsning startes en simpel brugergrænseflade hvor brugeren kan få svar på om et givet ord findes på en af hjemmesiderne i den indlæste datafil.

Fællesdelen

Fællesdelen består i at løse følgende 4 opgaver hvor opgave 3 er den mest omfattende. Disse opgaver bliver præsenteret på den første projektdag.
  1. Kør og forstå programmet SearchCmd.
  2. Modificer SearchCmd således at hvis der f.eks. søges på "Hans", så udskrives alle de URL'er, hvorpå "Hans" forekommer. Dette skal gøres ved at ændre på søgemetoden i SearchCmd. Man skal altså ikke ændre på opbygningen af datastrukturen.
  3. Modificer opbygningen af datastrukturen således at der dannes en hægtet liste af objekter som indeholder tre felter, nemlig str, next og urls. Felterne str og next skal være som i SearchCmd, blot skal der kun stå ord i listen og hvert ord skal kun forekomme en gang. Såfremt et objekt indeholder ordet "Hans" i feltet str skal objektets urls felt være en peger til en liste af de URL'er som indeholder ordet "Hans". En liste af URL'er skal bestå af objekter med to felter, nemlig next og url. Feltet next skal være en peger til det næste objekt i listen og feltet url skal være en peger til en URL. Efter konstruktionen af denne datastruktur skal der laves tilhørende søgerutiner. Datastrukturen opbygget her fylder mindre end strukturen fra SearchCmd og er hurtigere at søge i.
  4. Modificer løsningen fra opgave 3 således at man i stedet for at have en hægtet liste med de forskellige ord der forekommer har disse i en hashtabel datastruktur. I skal opbygge hashtabellen med chained hashing, d.v.s. hver indgang skal indeholde en objekt reference til en haegtet liste. Brug af sådan en struktur vil give en drastisk reducering af den tid det tager at opbygge og søge i datastrukturen.

I løsningen af ovenstående fællesopgaver er det ikke tilladt at bruge andre pakker end java.io og java.lang. Specielt er det altså ikke tilladt at bruge nogen af klasserne fra java.util pakken. Baggrunden for dette krav er, at et af formålene med dette kursus er at lære hvordan man programmerer forskellige datastrukturer og ikke blot at lære hvordan man bruger datastrukturer programmeret af andre.

Som det fremgår er det tilladt at bruge forskellige metoder på String objekter. Herunder er det tilladt at bruge metoden hashCode. Desuden er det tilladt at oprette tabeller (arrays). Hvis du er i tvivl om du må bruge en given Java funktionalitet så kontakt en af lærerne.

Til de opgaver der kommer efter fællesdelen er der ikke nogen begrænsninger på hvilke java faciliteter man må bruge.

Rapporten

Der stilles følgende helt generelle krav til rapporten:

Desuden er der følgende krav til rapporten som alle er relateret til de 3 søgemaskiner implementeret i fællesdelen:

Hvad rapporten skal indeholde i forbindelse med det der ligger udover fællesdelen vil afhænge af hvad gruppen har arbejdet med og hvor gruppen har valgt at lægge fokus i dette arbejde.

Hvordan skriver man rapport? Til hjælp med dette kan du finde en lille note her. I noten skønnes det at en projektrapport ca. fylder 25 side. For dette kursus skønner vi at en rapport kan fylde meget mindre, og rapporten må maksimalt fylde 20 sider med almindelig font. I de 20 sider skal ikke indregnes bilag og figur.

Ved beskrivelse af et program, skal man starte med at specificere input/output. Dvs. hvilke informationer får programmet fra tastetur, filer, osv. og hvad programmet udskriver til skærm, filer osv. Denne beskrivelse skal være så præcis som mulig. Den skal endvidere beskrives således at en uden programmeringskundskab skal kunne læse beskrivelsen, specielt må der ikke refereres i denne beskrivelse til hvorledes programmet er opbygget. Efter denne beskrivelse, kan der redegøres for hvilke datastrukturer programmet bruger. Dette skal være en beskrivelse af hvorledes strukturen ser ud, og beskrivelsen skal gøres uafhængig af hvorledes strukturen er opbygget. Dernæst kan det beskrives hvorledes strukturen er opbygget og hvorledes denne bruges. I denne sidste beskrivelse skal der fokuseres på kerneideer og beskrivelsen skal laves i videst mulig udstrækning uden brug af gengivelse af kode.

Datastrukturer

Til at løse opgaverne hørende til fællesdelen skal man bruge hægtede lister og hashing.

Hægtede lister bliver gennemgået på den første projektdag. Hvis man ikke kender til hægtede lister kan man læse om disse i "JAVA: software solutions" af John Lewis og William Loftus, anden udgave, kapitel 12.1. Alternativt kan man kigge på denne hjemmeside. Man kan også hente ListProgram.java som indeholder et lille eksempel på brug af hægtede lister. En rigitg god måde at blive fortrolig med hægtedede lister på er ved at eksperimentere med og ændre i dette program.

Som baggrundsliteratur om hashing anbefaler vi materialet man kan finde på denne hjemmeside.

Udvidelser

Her forslag til hvad man kan gå i gang med efter fællesdelen. Rækkefølgen af disse forslag er vilkårlig.

Om brug af Java

I dette afsnit kan man læse nogle udvalgte informationer om brug af Java. Man kan finde yderligere og mere grundlæggende informationer på hjemmesiden for grundlæggende programmering. Desuden er her et link til Java API specifikationen. På denne hjemmeside findes oplysninger om en bog som på en kompakt og præcis måde beskriver Java. Man kan endvidere gratis hente tidligere versioner af bogen.

I forbindelse med kørsel af SearchCmd har man brug for at angive parametre til main metoden. Desuden er det i forbindelse med flere af de foreslåede udvidelse nødvendigt at bruge såkaldte jar filer. I de følgende afsnit er det beskrevet hvordan man gør disse to ting i forskellige Java udviklingsmiljøer.

Generelt kan det nævnes at en jar fil indeholder funktionalitet udover den der findes i selve Java. En jar fil er nødvendig både når man oversætter og når man udfører et program der benytter sig af den ekstra funktionalitet. BlueJ

I BlueJ kører man et program ved at udføre main metoden. Der kommer så en dialogboks frem hvor man skal angive programparametrene. Her kan man eksempelvis angive:

  {"c:\\soegemaskine\\itcwww-small.txt"}

Bemærk de dobbbelte backslasher.

I BlueJ kan man anvende .jar filer ved at gå ind i Options og dernæst Preferences. Man skal så vælge fanen Libraries. Man skal så trykke Add og så finde den jar fil man skal bruge.

JCreator

Hvis man bruger JCreator til at oversætte og udføre Java programmer og hvis man har problemer med at få oversat og kørt de rette programmer, så kan det anbefales at gå ind i File menuen og vælge Close workspace hver gang JCreator startes op.

Man kan angive hvilke parametre man vil give til et programs main metode på følgende måde: Vælg Configure menuen. Vælg dernæst Options og så JDK Tools. Vælg så i feltet Select tools type værdien Run application og tryk på <default>. Tryk så Edit og vælg fanen Parameters. Parametrene kan så skrives i feltet Main (...).

Man kan benytte en jar fil ved i menuen at vælge Configure, dernæst vælge Options og så vælge JDK Profiles. Man skal så vælge JDK version 1.3 og vælge Edit. Man skal så trykke på Add og vælge Add package og man skal angive den jar fil man ønsker at bruge.

Kommandolinjeprogrammernre

Den helt klassiske måde at køre og oversætter java programmer på er via de såkaldte kommandolinje programmer. Man kan oversætte programmet i SearchCmd.java på følgende måde:

  javac SearchCmd.java

Man kan så køre dette program med den lille datafil på følgende måde:

  java SearchCmd c:\soegemaskine\itcwww-small.txt

Hvis man vil benytte en jar fil gør man det ved at tilføje den til den såkaldte CLASSPATH. Dette er allerede gjort for de jar filer der henvises til fra hjemmesiden for søgemaskine projektet.

Administrativt

Projekteksamen

Tidspunktet for eksamen vil blive offentliggjort senere.

Der vil udarbejdet en eksamensplan snarest muligt efter at projekterne er afleveret.

Hver gruppe skal forsvare sin rapport ved en mundtlig eksamen. På basis af rapporten og forsvaret gives der en individuel karakter for hver deltager i gruppen.

Projektdage

Under projektperioden vil der være 4 gange (ca. 1 dag per gang) hvor en af Lærerne vil være på HiNT. På disse dage, kaldet projektdage, vil der være fællesoplæg samt individuel gruppevejledning. Under den individuelle gruppevejledning vil det blive aftalt med hver gruppe hvilke dele af rapporten det forventes der er skrevet færdig inden næste gruppevejledningsmøde. Disse dele skal sendes til lærerne senest 2 hvedage inden vejledningsmødet. Nedestående projektdage kan blive ændret efter behov.

Projektgrupper

Gruppe 1 :Kamilla og Robert
Gruppe 2 :Ståle Andre Nygård og Svein Arne Haug
Gruppe 3: Trygve Pløhn, Silje Vangstad

Alle lærere og studerende

Studerende

Svein Arne Haug : Pascal, Matematik
Robert Landsem : VB, Java, Matematik, PHP, ASP, Perl, Javascript
Ståle Andre Nygård : Javva, og en masse andet
Kamilla Overholmen : Java, Algoritmik, OO, Matematik,
Frode Pedersen : Linux, DB, algoritmer, Java, C
Trygve Pløhn : Pascal, Perl, PHP, lidt Java, Matematik, Algoritmik, MySQL, Javascript, lidt ASP
Silje Vangstad : Pascal, Java, VB, Perl, Matematik, Algoritmik, Perl

Lærere

Stephen Alstrup (Lærer), email:stephen@it-c.dk
Theis Rauhe (Lærer), email:theis@it-c.dk

Hjælp med Java på HiNT

På HiNT vil der være en lære som kan hjælpe med Java og programmeringsproblemer . Denne lære er Ståle Andre Nygård.