Structuur van computer programma's II Opgave project indexer

Dirk Vermeir
Departement Informatica
Faculteit Wetenschappen
Vrije Universiteit Brussel

Date: 2001/11/08 14:42:56

Contents

1  Inleiding: indexer

Indexer is een server programma dat kan gebruikt worden om:

1. een index file op te bouwen voor een aantal tekst bestanden,
2. snel een bestand terug te vinden waarvan de inhoud voldoet aan een aantal criteria, uitgedrukt als een ``query''

Een en ander is georganiseerd als een client-server systeem bestaande uit 2 programma's:

• Het server programma indexer.
• Een client programma ffiles dat een query naar de server stuurt en het ontvangen antwoord laat zien.

2  Achtergrond: client-server

De programma's maken gebruik van de normale internet protocollen en standaarden: tcp/ip,dns. Zeer summier:

• Een machine op het net heeft een numeriek adres, meestal voorgesteld als een rij van 4 bytes. Bvb. is het internet adres van tinf2 134.184.65.2.
• D.m.v. de DNS service kunnen een of meerdere namen geassocieerd worden met een internet adres. Bvb. is de officiële naam van de machine met adres 134.184.65.2 tinf2.vub.ac.be. Zulke namen zijn hierarchisch gestructureerd (de machine ``tinf2'' behoort tot het domein ``vub.ac.be'' dat zelf weer een deeldomein is van ``ac.be'', hetwelk een deel is van het ``top'' domein ``be''. Men kan bvb. d.m.v. het ``nslookup'' programma nagaan wat het adres is dat hoort bij een naam (of omgekeerd).
• Een machine op het net heeft een aantal poorten waarlangs een verbinding kan gemaakt worden met een poort van een andere machine. Sommige poorten worden, bij conventie, gebruikt voor bepaalde diensten. Bvb. wordt de poort nummer 80 veelal gebruikt door web servers. Wanneer bvb. konqueror (of netscape) vanop de machine 134.184.65.2 (tinf2) een verbinding wenst te maken naar de webserver op elvas.vub.ac.be (adres 134.18.65.31) met de web server van tinf2, dan wordt er een verbinding geopend tussen een poort, bvb 8026, op 134.184.65.2 en poort 80 op 134.18.65.31. D.m.v. het tcp protocol kunnen dan data uitgewisseld worden tussen de toepassingen aan beide kanten van de verbinding.

Voor het netwerk aspect kan gebruik gemaakt worden van het dvnet pakket dat o.a. een klasse Socket (voor clients) en SocketServer (voor servers definieert). Omdat Socket afgeleid is van iostream is het sturen en ontvangen van gegevens via een netwerkverbinding heel makkelijk.

De directorydemo bevat een volledig uitgewerkt voorbeeld van een ``echo server'', dit is een server die elke lijn gestuurd door een client terugstuurt, na de tekst te hebben omgezet naar hoofdletters.

3  Opgave: indexer en ffiles

1. Maak een server programma ``indexer'' en een client programma ``ffiles'' die voldoen aan de onderstaande functionele¹ en niet-functionele² eisen (``requirements'').

2. Beschrijf kort uw ontwerp in een apart document; waarvan u een afdruk bezorgt aan het secretariaat van de vakgroep vóór de uiterste indiendatum.

4  Functionele eisen indexer

4.1  Aanroepen, configuratie

Het programma kan op de volgende manier opgeroepen worden

indexer naam-van-configuratie-file

Het configuratie bestand bevat een aantal lijnen van de vorm naam=waarde waarbij naam en waarde één van de betekenissen uit tabel 4.1 kan hebben

4.2  Het index bestand

• De index file bevat een tekst representatie van de de associatie tussen woorden en de bestanden waar ze voorkomen. Een mogelijkheid is dat elke lijn bestaat uit een woord, gevolgd door een spatie, gevolgd door een absoluut pad van een tekst file die dat woord bevat, zoals geillustreerd in Figuur 4.2.

  aap /a/b/c/d.txt

  aap /a/b/xyz/e.txt

  cpp /a/b/xyz/d.txt

  ...

  Figure 1: Voorbeeld index file

• Een woord in een tekstbestand is gedefinieerd als een maximale rij van alfabetische tekens. Wanneer het indexer programma een file indexeert dan zal hij slechts de eerste woordlengte tekens gebruiken. Als woordlengte bvb 6 is, dan zal het bestand /a/b/c.txt met inhoud zoals in Figuur 4.2

  Dit is werkelijk een heel eenvoudig

  programma.

  Figure 2: Voorbeeld input tekstbestand

  leiden tot de volgende bijdrage aan de index van Figuur 4.2.

  dit /a/b/c.txt

  is /a/b/c.txt

  werkel /a/b/c.txt

  een /a/b/c.txt

  eenvou /a/b/c.txt

  ...

  Figure 3: Voorbeeld bijdrage aan indexbestand

• Het ignore bestand bevat woorden, 1 per lijn, die bij het indexeren niet in aanmerking worden genomen. Bvb. zal, voor een indexer die nederlandstalige teksten, indexeert, het woord ``en'' vermoedelijk in dat bestand voorkomen.

• Het logfile bestand wordt gebruikt om informatie over het gebruik van de indexer op te schrijven, bvb. fouten boodschappen etc.

4.3  Indexer protocol

De server accepteert bevelen (via het netwerk) met een syntax zoals getoond in tabel 4.3.

• Bij een add bevel zal de server het genoemde bestand indexeren, d.w.z. zijn index structuren aanvullen met gegevens uit het bestand, als dit bestand tenminste normale tekst bevat (zoek zelf uit hoe dit kan nagegaan worden). Als antwoord komt er 1 lijn met ofwel het woord OK ofwel het woord ERROR gevolgd door een spatie en de beschrijving van de fout (alles op dezelfde lijn). De foutenboodschap wordt ook op de logfile geschreven.
• Bij een query bevel zal de server snel alle bestanden zoeken die aan de query voldoen. Het volgende (niet-geoptimizeerde) algoritme kan hiervoor gebruikt worden.

  1. Voor elk woord w in de query (zo'n woord kan apart voorkomen of als deel van een zin): zoek de verzameling van padnamen F(w) van bestanden die w bevatten. Hiervoor wordt uiteraard gebruik gemaakt van de ingeladen index structuren.
  2. Bepaal de doorsnede G van alle F(w).
  3. Als er geen ``zinnen'' in de query voorkomen dan is G het resultaat.
  4. Als er zinnen voorkomen dan worden de bestanden in G één voor één geopend en er wordt nagekeken of de lijst van woorden in elke zin inderdaad in die volgorde voorkomt in het bestand (hierbij moet geen rekening gehouden worden met leestekens of cijfers, m.a.w. een bestand kan gezien worden als een lijst van woorden). De bestanden die een zin uit de query niet bevatten worden uit G verwijderd.
  5. Schrijf het resultaat G naar de client: 1 lijn per padnaam. Na de laatste padnaam wordt nog een lege lijn naar de client geschreven (zodat die weet dat het antwoord volledig is).

• Bij een save bevel wordt de index structuur weer weggeschreven naar indexfile. Indien er sinds het vorige save bevel (of het opstarten van de server) geen add bevel is uitgevoerd, hoeft de server niks te doen. Het antwoord dat naar de client wordt gestuurd is zoals voor het add bevel.
• Bij een stop bevel stopt de server. Het antwoord is zoals voor het add bevel.
• Als een bevel niet herkend wordt zal de server antwoorden met één lijn met SYNTAX ERROR gevolgd door een spatie en het foutieve bevel.

5  Functionele eisen ffiles

Het programma kan op de volgende manier opgeroepen worden

ffiles host poort bevel

waarbij bevel de vorm beschreven in tabel 4.3 heeft. Merk op dat bij een ``query'' bevel, de hele query het best tussen single quotes kan geplaatst worden, om interpretatie door de shell te vermijden.

ffiles localhost 2002 query 'student structuur2 "niet goed" '

In principe stuurt ffiles het bevel gewoon door naar de server op de gegeven poort en host machine. Het antwoord wordt gecopieerd naar standaard output (behalve de lege lijn op het einde, bij het antwoord op een query bevel). De exit status van ffiles komt overeen met het succes van de bevelen die naar de server werden gestuurd.

De interpretatie van het add bevel is echter verschillend: als het argument van add een directorynaam is dan zullen alle tekstbestanden in de directory geindexeerd worden (het is de taak van ffiles om een aantal add bevelen naar de server te sturen). Hierbij kan bvb. gebruik gemaakt worden van de Directory klasse zoals gedefinieerd in de dvutil library.

6  Niet-functionele eisen

1. Het programma moet volledig en uitsluitend in C++ geschreven worden.
2. Het programma moet gebaseerd zijn op een object-georienteerd ontwerp. Functies die langer zijn dan 30 lijnen zullen met argwaan worden bekeken.

3. Het ontwerp moet zodanig zijn dat delen zonder moeite herbruikbaar zijn. Een voor de hand liggende herbruikbare klasse is een filter stream (zie de website van het boek) die enkel woorden leest.

4. Het programma moet correct werken op wilma.
5. Enkel de C++ (of C) standaard library en de dvnet en dvutil libraries mogen gebruikt worden.
6. Eigen implementaties van containers zijn niet toegestaan, enkel standaard library containers zoals map, set, vector, mogen gebruikt worden.
7. De source (C++) bestanden dienen de suffix ``.cc'', ``.C'' of ``.cpp'' te gebruiken. De ``header files'' met declaraties dienen de suffix ``.h'' te gebruiken.
8. Alle source bestanden, samen met een ``Makefile'', dienen zich in een directory ``structuur2/project2001'' te bevinden. De volgende reeks van bevelen zal resulteren in correct uitvoerbare programma's ``indexer'' en ``ffiles'' in dit directory:

   	make clean
   	rm -f indexer ffiles *.o
   	make all
   	

9. Het programma moet robuust zijn. Dit wil zeggen dat het ook een redelijke actie moet ondernemen indien de input extreem of foutief is.

7  Vragen

• Zoals steeds kan je vragen en opmerkingen sturen naar o4556@elvas.vub.ac.be.
• Indien je zeker wil zijn van een goede aanpak, dan kan je het ontwerp (welke klassen die welke functies ondersteunen) naar stru2@tinf.vub.ac.be sturen voor commentaar.

8  Indienen

Footnotes:

¹ Functionele eisen leggen vast wat het programma moet doen.

² Niet-functionele eisen leggen vast aan welke andere voorwaarden het programma moet voldoen, bvb. onder welk operating system het moet werken, welke programmeertalen of bibliotheken mogen gebruikt worden, etc.