Lösungen Blatt 1

1.
a)
1. Anzahl der Webadressen / Dokumente
- wenn alle Adressen / Dokumente bekannt wären, dann wäre somit das gesamte Web erfasst
- es ist unmöglich alle zu erfassen
- die ermittelte Größe berücksichtigt keinerlei Inhalte von Seiten, sie macht eine Aussage über die Struktur und Komplexität des Webs

2. Größe der Gesamtdatenmenge
- gleiches Problem wie a) 1. , unmöglich zu ermitteln, jedoch wäre logischerweise das gesamte Web erfasste
- wieder erhielte man “nur“ ein sehr große Zahl, die zwar sicherlich sehr beeindruckend wäre, jedoch nicht weiter interessant

3. Anzahl der Teilnehmer
- unmöglich zu messen
- macht keinerlei Aussage über die Größe des Webs an sich
- auch hier, lediglich große Zahl

4. Anzahl der registrierten Domains
- gibt keine Aussage über wirkliche Anzahl der Dokumente und Unterseiten hinter der Domain
- im Vergleich zu den anderen Größen relativ einfach zu ermitteln → Domains müssen registriert sein.
- Seiten ohne Domainnamen werden jedoch ignoriert und registrierte Domains können unbenutzt sein

b)
1. Umsetzung durch Webcrawler. Je größer die Anzahl der Webseiten wird, desto mehr Speicher und CPU Zeit wird benötigt. Durch sich ständig ändernde Inhalte recht ineffizient.

2. Ähnlich wie b) 1. durch Webcrawler, der die Größe aller Dokumente / Dateien speichert.

3. unmöglich zu messen

4. registrierte Domains zählen

c) Probleme eines Webcrawlers:
- benötigt viel Speicherplatz und muss um effizienter zu arbeiten hochgradig parallel laufen
- muss Ringverweise erkennen, was bei der großen Datenmenge schwierig werden kann bzw. bei ungenügendem RAM sehr langsam
- passwortgeschützte Seiten können nicht durchsucht werden
- Links können kein Ergebnis liefern, da z.B. die Adresse nicht mehr existiert, der entsprechende Server gerade offline oder einfach nur sehr langsam ist.
- Seiten die nicht von anderen Seiten verlinkt sind werden nicht gefunden. Es kann passieren, dass nur eine sehr kleine, abgeschlossene Teilmenge von Seiten gefunden wird, z.B. es wird auf einer Seite begonnen, die keine externe Seite verlinkt.
- Neue Inhalte auf schon durchsuchten Seiten können neue Suche nötig machen
→ ständige Aktualisierung wäre nötig. Könnte behoben werden indem Suchmaschine von der Seite informiert wird, dass neue Inhalte hinzugekommen sind.

d)

/**
*
*/
package uebung1;

import java.io.BufferedReader;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.ObjectOutputStream;
import java.net.URL;
import java.net.URLConnection;
import java.util.HashMap;
import java.util.Map;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class WebCrawler {

// initial pages
private final static String[] PAGES = new String[] { "http://www.web.de" };

// mapping from URL to crawled or not
private Map pages = null;

private String currentPage = null;

private int errorCount = 0;

private long start = 0;
private long end = 0;

/*
* Probleme: -relative pfade zusammenbasteln...de/test/ kann auch ein Blatt
* sein, d.h. relativer Pfad existiert nicht
* (http://www.hpi.uni-potsdam.de/meinel/projects/lock-keeper/meinel/research.html)
* -keine BerŸcksichtigung von anderen Dateiformaten...pdf, .mpg usw.
* -verschlŸsselte Seiten -passwortgeschŸtze Seiten -mit captchas geschŸtzte
* Seiten -verschiedene URLs verweisen auf die gleichen Seiten
*
*/

/**
*
*/
public WebCrawler() {
pages = new HashMap();

for (String page : PAGES) {
pages.put(page, false);
}

start = System.currentTimeMillis();

while (pages.containsValue(false)) {
for (String key : pages.keySet()) {
if (!pages.get(key).booleanValue()) {
currentPage = key;
break;
}
}
getPage(currentPage);
pages.put(currentPage, true);
}
}

/**
* Builds up a connection to a page and reads it.
*
* @param page
*/
private void getPage(String page) {

try {
URL url = new URL(page);
URLConnection urlConn = url.openConnection();
BufferedReader in = new BufferedReader(new InputStreamReader(
urlConn.getInputStream()));

String inputLine;
while ((inputLine = in.readLine()) != null) {
getUrlsFromPageContent(inputLine);
}

in.close();
} catch (Exception ex) {
System.out.println("Fehler beim Lesen aufgetreten: " + ex);
pages.remove(page);
errorCount++;
}
}

/**
* Collects urls from a given html-string.
*
* @param html
*/
private void getUrlsFromPageContent(String html) {

// define regular expression
Pattern p = Pattern.compile("<a.*?href=\".*?\".*?</a>");
Matcher m = p.matcher(html);

while (m.find()) {
String htmlPart = html.substring(m.start(), m.end());
int indexOfFirstQuotation = htmlPart.indexOf("\"") + 1;
String url = htmlPart.substring(indexOfFirstQuotation, htmlPart
.indexOf("\"", indexOfFirstQuotation));

// handle relative paths
if (!url.startsWith("http") && !url.startsWith("ftp")) {
// do not handle the relative paths in case the current page is
// a "leaf"
if (currentPage.contains("htm") || currentPage.contains("php")) {
continue;
}
if (url.startsWith("/")) {
if (currentPage.endsWith("/")) {
url = url.substring(1);
}
} else {
if (!currentPage.endsWith("/")) {
url = "/" + url;
}
}
url = currentPage + url;
}

// add new URL
if (!pages.containsKey(url)) {
pages.put(url, false);

int size = pages.size();
if (size % 100000 == 0) {
end = System.currentTimeMillis();
System.out.println((end - start) / 1000
+ " seconds; found pages: " + size
+ "; error count: " + errorCount);
System.out.println(currentPage);

// serialize pages in order to determine size of data
// structure
// try {
// ObjectOutputStream out = new ObjectOutputStream(
// new FileOutputStream("data.out"));
// out.writeObject(pages);
// out.close();
// } catch (IOException ex) {
// System.out.println(ex);
// }
}
}
}
}

/**
* @param args
*/
public static void main(String[] args) {
new WebCrawler();
}

}


- 100.000 Seiten ausgehend von www.web.de erfasst, allerdings ist die Gültigkeit/Erreichbarkeit der Seiten noch nicht sicher
Dauer: 5 min
Größe der verwendeten Datenstruktur: 42,3 MB Speicherplatz für die auf der
Festplatte abgelegte serialisierte HashMap
- 10^12 Seiten
5 min * 10.000.000 = 95,13 Jahre
42,3 MB * 10.000.000 = 423 TB

2.
a)
– Um die goldene Toilette benutzen zu dürfen.
– http://wcar.alrc.net/mainfile2.php/For+the+negative/8/
– lam sai wing hongkong 1000 dollars
– 6
– 5 min

b)
– Da Berufstätigkeit bei Frauen strikt auf die Zeit vor der Ehe beschränkt war.
– http://de.wikipedia.org/wiki/Fräulein#Anrede_.E2.80.9EHerr.E2.80.9C_vs._.E2.80.9EFrau_oder_Fr.C3.A4ulein.E2.80.9C
– lehrerin fräulein wiki
– 1
– 0 min

c)
– Tadschikistan
– http://www.imf.org/external/np/sec/nb/2000/nb0097.htm
– currency reform 2000
– 3
– 5 min inkl. Check auf wikipedia mit 'Somoni'

d)
– Hawaii
– http://distancecalculator.globefeed.com/World_Distance_Calculator.asp
http://de.wikipedia.org/wiki/Bundesstaat_der_Vereinigten_Staaten
– botswana us state distance
– 3
– 10 min (testen von Washington, Kalifornien und Hawaii)

e)
– Tycho Brahe
– http://de.wikipedia.org/wiki/Tycho_Brahe?title=Spezial:Booksources&isbn=3518369903
– hamburg-wandsbek harnverhaltung
– 2
– 1 min

f) Schwierigkeit:
- sich in den Kopf von Leuten versetzen, die über das Thema schreiben, um gute Suchworte abzuleiten,
- Suchmaschine kann Zusammenhänge der Suchworte nicht erkennen und sucht stur nach Übereinstimmungen in Dokumenten, jedoch nicht deren Bedeutung

3.
a)
- Aktualität: Sind die Treffer (tages-)aktuell? Es sollten beispielsweise keine veralteten oder überholten Antworten kommen.
- Abdeckung: Wird wirklich jede mögliche Seite (das 'gesamte Internet') durchsucht? Die beste Suchmaschine nützt nichts, wenn sie nur zwei Seiten kennt und meine gesuchte Information auf einer dritten steht.

(Wichtiger als objektive Qualität ist aber eigentliche die subjektive Qualität. Habe ich gefunden, was ich gesucht hab?)

b)

Eine Möglichkeit die Mächtigkeit einer semantischen Suchmaschine zu zeigen ist die Verwendung von natürlicher Sprache zur Suche. Eine weitere Möglichkeit ist das finden von Informationen durch Eingabe von Synonymen der Informationen.