Geeignete Baum-Struktur

Tobi_L

Hallo!

Ich möchte folgendes realisieren:
Ich möchte in C++ eine komplette Webseite analysieren. Dabei möchte ich speziell von der Startseite rekursiv alle internen Links folgen und so eine Übersicht an HTML-Seiten produzieren. Dabei soll aufgezeigt werden, welche Tiefe jede HTML-Seite hat. Wenn die Seite also mit drei Links von der Startseite erreichbar ist, hat die Seite im Graphen ... oder welcher Struktur auch immer ... die Tiefe 3.
Bei jedem Aufruf einer HTML-Seite müssen dementsprechend die schon registrierten Links mit den neuen Links abgeglichen werden.

Wichtig hierbei ist, dass die zu analysierende Seite extrem groß ist und durchaus mehrere 10.000 HTML-Seiten beinhaltet.

Das Frage dabei ist nun: welche Struktur zum temporären Speichern dieser Informationen soll gewählt werden?
Es ist ja wichtig, dass eine Seite möglichst schnell in dem Konstrukt gefunden wird. Darum habe ich spontan an einen Baum gedacht. Problem dabei ist allerdings, wie überhaupt die jeweilige Seite gefunden werden soll. Hashing?

Was wären eure Ansätze?

Viele Grüße,
Tobias

finix

Kommt drauf an was du genau willst. Wenn es dir rein um die "Linktiefe" geht sollte sich das eigentlich nicht allzu schwer realisieren lassen.

struct PageInfo
{
  size_t     linkDepth;
  date_time  lastChange;
};

[hash_]map<string,PageInfo> pages;

Der Key muss hierbei natürlich der komplette Pfad sein, nicht nur Dateiname.

Tobi_L schrieb:

Es ist ja wichtig, dass eine Seite möglichst schnell in dem Konstrukt gefunden wird. Darum habe ich spontan an einen Baum gedacht. Problem dabei ist allerdings, wie überhaupt die jeweilige Seite gefunden werden soll. Hashing?

Was genau meinst du?

Tobi_L

Hallo!

Vielen Dank!
An eine Hashmap habe ich auch gedacht. Nur die Frage, die ich mir dabei stelle, ist, ob es nicht noch eine effektiviere (performantere) Möglichkeit gibt. Da dachte ich dann auch an so etwas wie einen B+Baum.
Es bleibt mir aber wohl nicht anderes übrig, als es einfach mal durchzutesten.

Ich habe mit so etwas auch noch nie in C/C++ gearbeitet.

Viele Grüße,
Tobias

ZuK

Tobi_L schrieb:

Nur die Frage, die ich mir dabei stelle, ist, ob es nicht noch eine effektiviere (performantere) Möglichkeit gibt.

Du hast uns noch nicht gesagt wozu du performance brauchst. Willst du bei gegebener URL herausfinden von wo überall diese seite referenziert ist. Oder willst du....
Die optimale Struktur ergibt sich auf jeden fall daraus auf welche Auswertung du am meisten Wert legst.
Jedenfalls gibt der Vorschlag von finix einen schönen Baum;
Kurt

Tobi_L

Hallo!

Ich möchte letztlich eine Art internen Spider bauen, der alle Seiten im Portfolio analysiert. Die Tiefenstruktur ist dabei nur temporär. Es soll damit festgestellt werden, ob eine Seite schon analysiert wurde und welche Tiefe eine Seite besitzt, um ggf. auch abzubrechen.

Performance brauche ich, weil das ganze nur ein Bereich im Programm darstellen soll und das gesamte Programm auf einen unserer Webserver laufen soll und sich somit ggf. wertvolle Ressourcen mit Apache/DB teilt.

Und da stellt sich für mich die - vielleicht naive - Frage, ob eine Hashmap von vielleicht 10 MB Größe wirklich optimal ist, um darauf zu arbeiten.

Viele Grüße,
Tobias

ZuK

Hmm. Bei diesen Datenmengen würde ich auf jedenfall den Einsatz einer Datenbank überlegen.
Kurt

finix

Tobi_L schrieb:

Hallo!

Ich möchte letztlich eine Art internen Spider bauen, der alle Seiten im Portfolio analysiert. Die Tiefenstruktur ist dabei nur temporär. Es soll damit festgestellt werden, ob eine Seite schon analysiert wurde und welche Tiefe eine Seite besitzt, um ggf. auch abzubrechen.

Performance brauche ich, weil das ganze nur ein Bereich im Programm darstellen soll und das gesamte Programm auf einen unserer Webserver laufen soll und sich somit ggf. wertvolle Ressourcen mit Apache/DB teilt.

Und da stellt sich für mich die - vielleicht naive - Frage, ob eine Hashmap von vielleicht 10 MB Größe wirklich optimal ist, um darauf zu arbeiten.

Viele Grüße,
Tobias

Vielleicht solltest du einfach noch mal genauer erklären was du überhaupt willst bzw. was deine Anforderungen sind. Ansonsten wird's wohl eher schwer dir konkret zu helfen.