Kategorisierte Tags
Zefau hat mich am letzten Wochenende auf eine interessante Technik aufmerksam gemacht, die er bei Gmail-Labs verwendet hatte: Die Kategorisierung von Tags. Man kann seine Tags dabei baumartig strukturieren, wie man es bereits von den Kategorien, die auf vielen Blogs verwendet werden, kennt. Wählt man ein Tag, dann sind alle Tags, die darüber angeordnet sind, automatisch gewählt. Hierzu ein kleines Beispiel für einen Kategorienbaum:
|--+ Theoretische Informatik
|--+ Graphentheorie
|--+ Kategorientheorie
|--+ Lambda-Kalkül
|--+ Praktische Informatik
|--+ Softwaretechnik
|--+ Programmierung
|--+ Funktionale Programmierung
|--+ Haskell
|--+ Objektorientierte Programmierung
Wähle ich nun für einen Artikel die Tags "Graphentheorie" und "Haskell", so werden automatisch die Tags "Theoretische Informatik", "Praktische Informatik", "Programmierung" und "Funktionale Programmierung" zusätzlich ausgewählt. Der Vorteil daran ist zum einen dass Suchanfragen nach "Programmierung" auch Artikel mit dem Tag "Haskell" listet. Außerdem muss man nur die konkretesten Tags angeben, da die allgemeineren Tags automatisch gewählt werden. Insgesamt steigt also der Komfort. Bevor ich Haskell-Code angebe, der das Problem löst, möchte ich noch eine graphentheoretische Betrachtung des Problems angeben um das Problem vor dem Lösen zu analysieren.
Wir gehen davon aus, dass es sich beim Kategorisierungsbaum um einen Out-Tree handelt, bei dem die Knoten den Tags entsprechen und die Kanten die Struktur des Kategorisierungsbaums annehmen. Ein Out-Tree G = (V, E, r) hat folgende Eigenschaften:
- Die Kantenmenge E enthält ausschließlich gerichtete Kanten.
- Die Wurzel r ∈ V besitzt keine eingehenden Kanten, d.h. indeg(r) = 0.
- Für jeden Knoten v ∈ V gibt es genau einen Weg von r nach v.
Auf Graphen dieser Form werde ich nun die Probleme und deren Lösungen formal beschreiben.
Problem. Man gebe zur Menge T ⊆ V von Tags die Menge T* ⊆ V an, die alle Tags enthält, die allgemeiner oder genauso konkret wie die Tags in T sind und einen Zusammenhang im Kategorienbaum zueinander haben.
Konstruktion. Sei T ⊆ V eine Menge von Tags, dann ist T* = ∪{{a1, a2, ..., an} | t ∈ T ∧ ∃ Pfad: r = a1 → ... → an = t}.
Lemma. Gegeben sei eine Menge T und ein ai ∈ T. T* = (T\{ai})* gilt genau dann, wenn es ein Element t ∈ T gibt, sodass ein Weg r = a1 → a2 → ... → ai-1 → ai → ai+1 → ... → an = t mit i ≠ n existiert.
Beweis. Gilt T* = (T\{ai})*, so muss es lt. Definition von * einen Weg r = a1 → ... → ai-1 → ai → ai+1 → ... → an = t mit i ≠ n geben, da ai sonst nicht ohne Veränderung von T* hätte entfernt werden können. Existiert ein Weg r = a1 → ... → ai-1 → ai → ai+1 → ... → an = t und entfernt man ai aus T, so existiert der Weg weiterhin, womit T* = (T\{ai})* gilt. Da beide Implikationen gelten, gilt auch die zu zeigende Äquivalenz.
Folgerung. Sei A die Menge aller ai für die T* = (T\{ai})* gilt, dann ist T* = (T\A)*.
Beweis. Seien a1, ..., an Elemente für die T* = (T\{aj})* mit j ∈ {1, ..., n} gilt. Lt. Lemma gilt T* = (T\{a1})* = ((T\{a1})\{a2})* = ... = (((((T\{a1})\{a2})\{a3})\...)\{an})*. Somit gilt auch T* = (T\{a1, ..., an})*.
Problem. Man gebe zu einer Menge T den Generator, d.h. die kleinste Menge G(T) = S an, für die S* = T* gilt.
Konstruktion. Sei A die Menge aller ai für die T* = (T\{ai})* gilt, dann ist G(T) = T\A.
Beweis. Sei S = G(T) für eine beliebige Menge T. Lt. Folgerung gilt S* = T*. Es ist also zu zeigen, dass S die kleinste Menge ist, welche diese Eigenschaft hat. Dies zeigen wir indirekt: Angenommen, es gibt ein Element s ∈ S sodass S* = (S\{s})*, dann gibt es lt. Konstruktion von S genau einen Weg r = a1 → ... → an = s. Das bedeutet, dass s das Ende genau eines Weges ist und in keinen anderen Wegen vorkommt. Entfernt man dieses s also, kommt das s in keinem Pfad mehr vor, womit wiederum s ∉ (S\{s})* gilt, was einen Widerspruch zur Annahme, dass ein solches s existiert, darstellt.
Nachdem die schwierige Arbeit getan ist, geht die Implementierung schnell von der Hand:
type Tag = String
type Tags = [String]
data Tree a = T a [Tree a] deriving (Show, Eq)
tree = T
leaf = (`tree` [])
generate :: Tree Tag -> Tags -> Tags
generate (T tag ts) tags
| tag `elem` tags = tag:children
| (not . null) children = tag:children
| otherwise = []
where children = concatMap (`generate` tags) ts
generator :: Tree Tag -> Tags -> Tags
generator (T tag ts) tags
| (not . null) children = children
| tag `elem` tags = [tag]
| otherwise = []
where children = concatMap (`generator` tags) ts
blog = tree "Blog" [theory, pragmatic]
theory = tree "Theoretische Informatik" [leaf "Graphentheorie", leaf "Kategorientheorie", leaf "Lambda-Kalkül"]
pragmatic = tree "Praktische Informatik" [leaf "Softwaretechnik", programming]
programming = tree "Programmierung" [leaf "Objektorientierte Programmierung", functional]
functional = tree "Funktionale Programmierung" [leaf "Haskell"]
Die Funktionen generator und generate ähneln sich sehr stark - besteht zwischen den beiden Funktionen womöglich ein kategorientheoretischer Hintergrund? Möglicherweise. :-) Testen wir aber erstmal den Code:
*Main> generate blog ["Graphentheorie","Haskell"]
["Blog","Theoretische Informatik","Graphentheorie","Praktische Informatik","Programmierung","Funktionale Programmierung","Haskell"]
*Main> generator blog ["Kategorientheorie", "Blog", "Haskell", "Programmierung"]
["Kategorientheorie","Haskell"]
Scheint zu funktionieren. Eine Verifikation des Codes erspare ich mir an diesem Punkt, da es sich sehr leicht mit struktureller Induktion machen ließe.