Søgemaskineprojekt for

Grundlæggende Programmering,
Objekt orienteret programmering,
Databasesystemer,
Parallelle systemer og
Introduktion til algoritmik og datastrukturer

December 2002

Søgemaskineprojektet er et standardprojekt,
se her for at finde andre standardprojekter

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

Vejlederansøgning skal afleveres senest 18 November. Da underviserne på projektet er bortrejst i perioden 15-18 November, opfordres studerende til at tilmelde sig projektet før 15 November. Hvis du efter den 15 November ønsker at lave søgemaskineprojekt og ikke har en vejlederansøgning, skal du kontakte Carsten Butz i lokale 1:17, tlf. 38 16 88 20. Casten vil have udfyldte vejlederansøgning til søgemaskineprojektet som du blot skal underskrive og aflevere i studieadministrationen.


Indhold

Denne side: Andet:

Overordnet

Velkommen til hjemmesiden for søgemaskineprojektet. Søgemaskineprojektet er for studerende med forskellige forudsætninger og projektmål. 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 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 i projektperioden 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 lave en projektaftale. Hver gruppe skal beskrive sit projektarbejde i en rapport, og denne rapport skal senere forsvares ved en projekteksamen.

Under projektperioden 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. Endvidere vil der være flere individuelle gruppemøder med vejleder. 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. Endelig vil der også være tilknyttet instruktorer til projektet som vil være behjælpelig med programmeringsproblemer.

På den første projektdag præsenteres projektet og der vil være mulighed for at danne endelig grupper, hvis dette ikke er allerede er sket. 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 projektet 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:

Disse filer findes også i kataloget:

  s:\sysadm\soegemaskine

og det anbefales at man bruger dem direkte herfra når man er på IT-C.

Hvis man arbejder under linux finder man filerne på /import/share/stud/sysadm/soegemaskine/

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 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 projekt 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.

På grundlæggende programmering er der udarbejdet en note om hvorledes en projektrapport kan se ud. Denne note anbefales det at man læser før rapportskrivning. I noten skønnes det at en projektrapport ca. fylder 25 side. For dette konkrete projekt 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.Vi har erfaring med at følgende struktur på rapporten er god :

Beskrivelsen af Searchmd ? kan gøres på følgende måde : Hvis man finder det relevant kan man evt. efter forordet have et kapitel som beskriver hægtet lister, generelle krav til input, osv. som er fælles for alle de søgemaskiner som beskrives.

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.

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. Alle de jar filer der er henvist til på hjemmesiden for søgemaskineprojektet findes også i kataloget:

  s:\sysadm

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:

  {"s:\\sysadm\\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 s:\sysadm\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

Vigtige datoer

Projektaftale

I dette afsnit beskrives kortfattet de administrative regler vedrørende 4-ugers projekter.

Det nemmeste er hvis du møder op til et af oplægene til søgemaskineprojektet, hvor vi så sammen udfylder relevante formularer. Se datoer for sådanne oplæg under Vigtige datoer. På Intranettet findes dels et dokument som hedder "projektaftale" og dels en guide til denne.
Projektaftaledokumentet skal afleveres til studieadministrationen 3 gange, første gang fungere dokumentet som en vejlederansøgning, dernæst som en projektaftale, og til sidst som en forside.

Datoer for hvornår vejlederansøgning, projektaftale, og forside skal afleveres finder du under Vigtige datoer. Teksten i dette afsnit følger terminologien fra studieadministrationen.

Det bemærkes at "Projektaftale" dækker over to ting, dels et "dokument" og dels en af tre delaflevering af dette dokument. Hver gruppe som ønsker at lave projekt sammen skal være fælles om hver delaflevering. De to første delafleveringer skal underskrives af lærerne tilknyttet projektet.

I nedestående finder du en vejledning til enkelte delafleveringer :

Vejlederansøgning En lang række felter skal udfyldes på vejlederansøgningen. I nedestående gennemgåes hvorledes visse af disse felter udfyldes for søgemaskineprojektet.

Projektaftale En lang række felter skal udfyldes på projektaftalen.Alle oplysninger som er givet under vejlederansøgningen, skal også fremgå af projektaftalen. I nedestående gennemgåes hvorledes visse af disse felter udfyldes for søgemaskineprojektet. Forside En del felter skal udfyldes på forsiden..Alle oplysninger som er givet under vejlederansøgningen og projektaftale, skal også fremgå af forsiden.Specielt gælder det for forsiden at gruppen skal skrive om man hæfter kollektivt eller individuelt. Hvis man hæfter kollektivt står hele gruppen til ansvar for hele rapporten. Kollektiv hæftelse er hvad der gælder for søgemaskineprojektet, med mindre andet er aftalt med vejleder. Hvis man hæfter individuelt skal det fremgå hvorledes dette gøres.

Projekteksamen

Tidspunktet for eksamen vil blive offentliggjort senere.

Der vil udarbejdet en eksamensplan snarest muligt efter at projekterne er afleveret.
Eksamensplan er ikke klar endnu

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

Projektdage

Under projektperioden vil der være dage hvor projektgrupperne har mulighed for at få hjælp til projektet m.m.

Datoerne for projektdagene er endnu ikke helt fastlagt, men der vil som i tidligere semester være en lang række projektdage om f.eks. servletter, lister, hashing, crawlere som er relevante for konstruktion af søgemaskiner.

Projektgrupper

Hvis du er interesseret i projektet i søgemaskiner skal du straks skrive til stephen, hvor du samtidig oplyser om hvilke tekniske kurser du har haft.
Nedenstående projektgrupper skal betragtes som foreløbige projektgrupper. Indtil videre er blot listet de studerende som på dette tidlige tidspunkt har ytret interesse for projektet.

Bemærk, der skal være mindst to deltagere i en gruppe, med mindre andet er aftalt med projektvejleder. Vi anbefaler dog mindst 3 personer i hver gruppe.
Hvis du er medlem af en gruppe med få medlemmer skal du forsøge at kontakte andre grupper via nedestående mail, for at flette grupperne sammen. Hvis der til den første projektdag stadig er grupper med kun et medlem, vil vi denne dag forsøge at flette disse grupper sammen.

Gruppe 1 (P) :Mikael Blomqvist(DBD, GP, DB), Lars C. Hansen (OOP, DBD), Bertel K. Brodersen (DBD, GP, ITPO)
Gruppe 2 (P) : Kristian Thy (OOP, IADS, WEB)
Gruppe 3 (P) : Xu Li,Jianjun Chen (IPBR, Mark, DSP), Shaolin Zhou, Nguyen Viet Thang (English report, IM, DSP, Introduction to Programming)
Gruppe 4 : Esben R. Hansen (OOP, IAD,DBD), Ayhan Binici (VOP,IAD,BA.Dat),
--------Peter Tiedemann (DB,OOP,BA. Mat/DAT), Rebekka Andersen (DiS,NOP,DS,Algoritmik,OOP,BA.Dat)
Gruppe 5 (P) : Peter Lysdal Jakobsen (OOP, DB)
Gruppe 6 (P) :Claudio Arias (GP, AMPI), Kim Hartung Jørgensen (GP)
Gruppe 7 :Lijie He (English Report,IPBR, IM,DSP)
Gruppe 8 (P) : Laust Juul Christensen (VOOP,DB,DBD, Algoritmik)
Gruppe 9 : Kaleem (English report, MS,SP,Basic programming)
Gruppe 10 (P) : Anne S. F. B-Christensen(GP,DBD,ITOP), Anders Musiat, Lene Marie Ramløse, Flemming Kristensen (DBD,ITPO,GP)
Gruppe 11 (P) :
Gruppe 12 (P) : Lena E. Fredeiksen (GP,DKM), Jens Ulrik Nielsen(GP,DBD,ITPO), Jakob Schrøder Andersen(GP,DBD,ITPO)
Gruppe 13 : Michael Kauffmann (GP, WEB)
Gruppe 14 (P) : Siri Hamre (GP, ITPO, DBD), Andreas Hansen (GP, DBD), Ragnar Lundø
Gruppe 15 (P) : Lars Bengtsson (DB,WEB, NP,IADS,OOP)
Gruppe 16 (P) : Morten Franck, Peter Gath Hansenk
Gruppe 17 (P) : Lene Christansen (DBD, GP, ITPO), Dorthe Skovshoved Rasmussen (GP, ITPO, DBD), Bente B. Petersen (GP, DBD)
Gruppe 18 (P) :Orri Palsson (GP, DBD, WEB)
Gruppe 19 (P) : Havard Semundseth (OOP,DBD,FP), Eirik Laberg (OOP,DBD,FP)
Gruppe 20 :

Alle lærere og studerende

Lærere

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

Instruktorvagtplan

Instruktorerne sidder i lokale 1.80 (eller går rundt i terminalrummet). Vagtplanen vil blive oplyst senere. Men det forventes at der vil være instruktorer hver dag.