\chapter{Algorithmen}
 \label{ch:algorithmen}

\section{Extraktion von Wiki-Links}
\label{alg:makeLink}

Die Methode \javaid{WikiTextAnalyzer.extractLinks} extrahiert alle Wiki-Links aus dem gegebenen Text. Der Text sollte bereits mit \javaid{stripClutter} bereinigt worden sein. Dafür werden zunächst alle Links in dem Text gesucht; der reguläre Ausdruck, der dafür verwendet wird, ist \startregex \\[\\[([^\\r\\n]+?)(\\|([^\\r\\n]*?))?\\]\\]\endregex, gefolgt von dem Ausdruck, der in \javaid{WikiConfig.linkTrail} definiert ist. Der "`\lingo{Link-Trail}"' legt fest, welche Zeichen als zum Text eines Links gehörig betrachtet werden, wenn sie unmittelbar auf den Link folgen --- zum Beispiel wäre im Fall von \wikitext{[[Physik]]er} der Link-Text \txt{Physiker}, weil \txt{er} auf das Link-Trail Muster passt. Der Link-Trail ist normalerweise eine Folge solcher Zeichen, die im Inneren eines Wortes der betreffenden Sprache vorkommen können (also "`normale"' Buchstaben der Sprache). Per Default sind hier alle Zeichen der Unicode-Kategorien für "`Buchstaben"' erlaubt (genauer, Zeichen in den Kategorien \lingo{Lu}, \lingo{Ll}, \lingo{Lt}, \lingo{Lm} und \lingo{Lo} \qs{UNICODE}{139}), also folgender reguläre Ausdruck: \nospell{\startregex ([\\p{IsL}]*)\endregex}.

Für jede Fundstelle für diesen regulären Ausdruck wird nun mittels \javaid{WikiTextAnalyzer.makeLink} ein Link als Instanz der Klasse \javaid{WikiTextAnalyzer.WikiLink} erzeugt. Dabei werden drei der vier von dem Ausdruck erfassten Gruppen verwendet: Gruppe 1 als Link-Ziel, Gruppe 3 als Link-Text (falls angegeben) und Gruppe 4 als Link-Trail. 

%{back-ref: \rr{sec:analyzer:links}; magic constants, link-propties; ausserdem \rr{sec:wikitext:links}}

Das Vorgehen von \javaid{WikiTextAnalyzer.makeLink} ist dann folgendes:

\begin{center}
 \footnotesize
 \begin{algorithmic}[1]
  \Procedure{makeLink}{$context$, $target$, $text$, $tail$}
    
    \State{ $target \gets$ decodeLinkTarget($target$);}     \Comment Dekodiere HTML- und URL-kodierte Zeichen
    \If{$target$ starts with "`:"'}                           \Comment Entferne Doppelpunkte vom Anfang
      \State{ $esc \gets $true;}           \Comment ...und markiere Link als "`escaped"', als "`nicht-magisch"'
    \EndIf 
   
    \State{ $page \gets target$ without leading "`:"';}                   \Comment Seitennamen initialisieren
    \State{ $section \gets page$ portion after first "`\#"', if any;} \Comment  Trenne den Abschnittsnamen...
    \State{ $page \gets page$ portion before first "`\#"`, if any;}    \Comment  vom eigentlichen Seitennamen
    \If{$section$}                                               \Comment Normalisiere den Abschnittsnamen
      \State{ $section \gets$ decodeSectionName($section$)};
      \State{ $section \gets section$ with all spaces replaced by "`\_"'};
    \EndIf

%  \algstore{makeLink}
%  \end{algorithmic}
% \end{center}
% 
\later{bla bla bla}
% 
% \begin{center}
%  \begin{algorithmic}[1]
%  \algrestore{makeLink}
    \State{ $prefix \gets page$ portion before first "`:"', if any;}    \Comment Trenne den Präfix vom Seitennamen
    \If{$prefix$}
      \State{ $prefix \gets$ normalizeTitle($prefix$);}                             \Comment Normalisiere den Präfix
      \State{ $ns \gets$ getNamespaceId($prefix$);}                           \Comment Finde Namensraum-ID für Präfix
      
      \If{$ns \neq$ Namespace.NONE}                         \Comment Falls ein solcher Namensraum existiert...
        \State{ $page \gets page$ portion after first "`:"';}\Comment Entferne Präfix vom eigentlichen Seitennamen
        \State{ $namespace \gets ns$;}                   \Comment Speichere Namensraum-ID für Nutzung im Link-Objekt
        
        \If{$\neg esc$}                                         \Comment Falls der Link nicht "`escaped"' ist...
          \If{$ns = $ Namespace.IMAGE}                              \Comment Falls der Namensraum "`Image"' ist...
            \State{ $magic \gets $LinkMagic.IMAGE;}                                     \Comment setze \var{magic} auf IMAGE
          \ElsIf{$ns =$ Namespace.CATEGORY}                     \Comment Falls der N.r. "`Category"' ist...
            \State{ $magic \gets$ LinkMagic.CATEGORY;}                               \Comment setze \var{magic} auf CATEGORY
          \EndIf
        \EndIf
      \ElsIf{isInterwikiPrefix($prefix$)}                 \Comment Falls der Präfix ein Interwiki-Präfix ist...
        \State{ $page \gets page$ portion after first "`:"';}\Comment entferne Präfix vom eigentlichen Seitennamen
        \State \Comment Falls der Präfix ein Interlanguage-Präfix ist und der Link nicht "`escaped"'...
        \If{$isInterlanguagePrefix(prefix) \wedge \neg esc $} 
          \State{ $magic \gets$ LinkMagic.LANGUAGE;}                                \Comment setze \var{magic} auf LANGUAGE
        \EndIf
      \EndIf
    \EndIf

%  \algstore{makeLink}
%  \end{algorithmic}
% \end{center}
% 
\later{bla bla bla}
% 
% \begin{center}
%  \begin{algorithmic}[1]
%  \algrestore{makeLink}
    \If{$\neg text$}                                          \Comment Falls kein Link-Text angegeben wurde...
      \State{ $implied \gets$ true;}                       \Comment Merke, dass impliziter Link-Text verwendet wird

      \If{$magic =$ LinkMagic.Category}                \Comment Falls der Link Kategorisierungssemantik hat...
        \State \Comment setze den Link-Text (hier: Sortierschlüssel)\ldots
        \State \Comment auf den Namen der Seite, die den Link enthält
        \State{ $text \gets context$;} 
      \Else                     \Comment sonst...
        \State{ $text \gets target$;}          \Comment setze den Link-Text auf das ursprünglich angegebene Link-Ziel
      \EndIf
    \EndIf

    \State \Comment Falls der Link keine Kategorisierungssemantik hat...
    \If{$tail \wedge magic \neq$ LinkMagic.CATEGORY} 
      \State{ $text \gets$ concat($text$, $tail$);}                         \Comment hänge den Trail an den Link-Text an
    \EndIf

    \State{ $text \gets$ decodeEntities($text$);}                         \Comment Dekodiere HTML-Entities im Link-Text
    \State{ $page \gets$ normalizeTitle($page$);}                                   \Comment Normalisiere das Link-Ziel
    
    \State \Comment Gib neues Wiki-Link-Objekt zurück
    \State \Return {new WikiLink($interwiki$, $namespace$, $page$, $section$, $text$, $implied$, $magic$);} 
  \EndProcedure
 \end{algorithmic}
% \captionof{algorithm}{makeLink}
\end{center}

Dabei verwendet \javaid{makeLink} (\rr{alg:makeLink}) die folgenden Funktionen:

\begin{description}
 \item[\javaid{WikiTextAnalyzer.decodeLinkTarget}] entschlüsselt HTML Entity-Referenzen \q{W3C:HTML} und URL-kodierte Zeichen \q{RFC:3986}.
 \item[\javaid{WikiTextAnalyzer.decodeSectionName}] entschlüsselt Codes in Abschnittsnamen; MediaWiki verwendet einen speziellen Code, um Sonderzeichen in Abschnittsnamen zu kodieren, die anderweitig nicht  den Anforderungen an ein HTML \wikitext{id}-Attribut \q{W3C:HTML} genügen würden. Diese können auch beim Angeben eines Abschnittsnamens in einem Link verwendet werden. Der Code entspricht im Wesentlichen der URL-Kodierung, nur dass hier der Punkt ("`."') statt dem Prozentzeichen ("`\%"') für die Kodierung verwendet wird. 
 \item[\javaid{WikiTextAnalyzer.isInterwikiPrefix}] gibt \javaid{true} zurück, falls eine gegebene Zeichenkette ein Interwiki-Präfix ist. Dazu wird die Zeichenkette mit dem regulären Ausdruck \regex{\^{}[a-z]+(-[a-z]+)*\$} verglichen --- dieses Muster ist weit gefasst und kann dazu führen, dass einige Links fälschlich als Interwiki-Links klassifiziert werden. Allerdings sind Seitennamen, die einen Doppelpunkt nicht als Trennzeichen für den Namensraum, sondern im eigentlichen Namen haben, recht selten. \later{count them}
 \later{ggf check for space after "`:"'? but that's legal fpr interwiki...}
 \item[\javaid{WikiTextAnalyzer.isInterlanguagePrefix}] gibt \javaid{true} zurück, falls eine gegebene Zeichenkette ein Interlanguage-Präfix ist, das heißt also, ob es sich um einen bekannten Sprach-Code handelt. Die Sprach-Codes werden durch die Property-Datei \javaid{Languages.properties} im Package \javaid{de.brightbyte.wikiword} definiert. Die dort aufgeführten Codes und Namen sind der entsprechenden Datei in MediaWiki entnommen, nämlich \javaid{languages/Names.php}.
 \item[\javaid{WikiTextAnalyzer.getNamespaceId}] gibt die numerische ID für einen gegebenen Namensraum zurück (oder \javaid{Namespace.NONE}, wenn kein solcher Namensraum bekannt ist). Die kanonischen Namensräume sind in der Property-Datei \javaid{Namespaces.properties} im Package \javaid{de.brightbyte.wikiword} definiert. Die für ein konkretes Wiki-Projekt gültigen Namensräume und Namensraumnamen werden dem Abschnitt \wikitext{<namespaces>} des XML-Dumps entnommen \q{MW:XML}.
 \item[\javaid{WikiTextAnalyzer.normalizeTitle}] normalisiert einen Seitentitel: der erste Buchstabe wird in einen Großbuchstaben umgewandelt, und alle Leerzeichen durch Unterstriche (\wikitext{\_}) ersetzt.
\end{description}

\label{p:badlink}
Die \javaid{page}-Eigenschaft des resultierenden \javaid{WikiLink}-Objekts wird dann mittels \javaid{WikiTextAnalyzer.isBadLinkTarget} geprüft --- diese Methode benutzt das in \javaid{WikiConfiguration.badLinkPattern} festgelegte Muster, um fehlerhafte Links zu erkennen. Per Default werden vor allem solche Links ausgefiltert, deren Ziel (\javaid{WikiTextAnalyzer.WikiLink.getPage()}) "`schlechte"' Zeichen enthält, wie \zB "`\wikitext{\{}"' oder "`\wikitext{\}}"', "`\wikitext{[}"' oder "`\wikitext{]}"', "`\wikitext{|}"', usw. Auch Link-Ziele, die vor dem ersten Leerzeichen einen Doppelpunkt enthalten, der nicht von einem Leerzeichen gefolgt wird, werden als "`schlecht"' betrachtet. Diese Regel fängt Links ab, die einen unbekannten Interwiki-Präfix oder einen Pseudo-Namensraum verwenden. Insbesondere werden so die sogenannten Shortcut-Redirects auf Projektseiten ausgefiltert, wie sie in vielen Wikipedias verwendet werden: \wikipage{WP:LK} als Abkürzung für \wikipage{Wikipedia:Löschkandidaten}, usw.

Falls \javaid{isBadLinkTarget} also \javaid{true} liefert, wird der Link verworfen, ansonsten wird er der Liste hinzugefügt, die am Ende von \javaid{extractLinks} zurückgegeben wird.

\section{Extraktion von Glossen}
\label{alg:extractFirstSentence}

Per Konvention ist der erste Satz in einem Wikipedia-Artikel eine Definition des Konzeptes, das der Artikel beschreibt. Um also eine Glosse für dieses Konzept zu erhalten, kann einfach dieser erste Satz extrahiert werden.

Um das zu erreichen, wird zunächst mit Hilfe von \javaid{WikiTextAnalyzer.extractFirstParagraph} der erste Absatz der Seite bestimmt. Dieser Absatz wird dann über das Muster \javaid{LanguageConfiguration.sentencePattern} in "`Schnipsel"' (\lingo{Chunks}) zerlegt. Einem Puffer wird dann immer ein Schnipsel hinzugefügt, solange das Ende des Puffers auf das Muster in \javaid{LanguageConfiguration.sentenceTailGluePattern} passt (oder der Puffer leer ist), oder der Anfang des nächsten Schnipsels zu \javaid{LanguageConfiguration.sentenceFollowGluePattern} passt. Der erste Satz gilt als gefunden, wenn keine der beiden Bedingungen mehr zutrifft, oder es keine weiteren Schnipsel gibt. In Pseudocode:

\begin{samepage}
\begin{center}
 \footnotesize
 \begin{algorithmic}[1]
 \Procedure{extractFirstSentence}{$text$}
   \State{ apply $sentenceManglers$ to $text$;} \Comment Entferne unerwünschten Text
   \State{ $s =$ "`"';} \Comment Starte mit leerem Satz
   \State{ $chunk =$ first chunk in $text$ matching $sentencePattern$;} \Comment Finde ersten Schnipsel
   \While{$chunk$} \Comment Solang noch Schnipsel übrig sind\ldots
     \State{ $s \gets$ append($s$, $chunk$);} \Comment hänge Schnipsel an den Satz an

     \If{next thing in $text$ is a linebreak} \Comment Ein Zeilenumbruch beendet den Satz
       \State{ break};
     \EndIf

     \State{ $chunk =$ next chunk if $text$ matching $sentencePattern$;} \Comment Finde nächsten Schnipsel

     \If{$s$ matches $sentenceTailGlue$}
       \State{ continue;} \Comment Satzende verlangt nach Verlängerung
     \EndIf

     \If{$chunk$ matches $sentenceFollowGlue$}
       \State{ continue;} \Comment Nächster Schnipsel verlangt nach Verlängerung
     \EndIf

     \State{ break;} \Comment Sonst ist der Satz fertig.
   \EndWhile

   \State \Return {return $s$;}
 \EndProcedure
 \end{algorithmic}
% \captionof{algorithm}{makeLink}
\end{center}
\end{samepage}

Der obige Pseudocode verwendet die folgenden Konfigurationsvariablen:
 
\begin{description}
\item[\javaid{LanguageConfiguration.sentenceManglers}] dienen der Vorverarbeitung des Textes vor der Satzerkennung. Sie entfernen unerwünschte Elemente, per Default vor allem Textstücke in Klammern, die die Erkennung von Satzenden verkomplizieren würden. Geklammerte Teile des ersten Satzes enthalten meist etymologische Erläuterungen oder die Lebensdaten von Personen, also Informationen, die für eine \emph{Definition} des Konzeptes nicht relevant sind. 
\item[\javaid{LanguageConfiguration.sentencePattern}] ist ein Muster zur vorläufigen Satzerkennung, also zur Zerlegung des Absatzes in "`Schnipsel"'. Es erkennt potentielle Satzenden, per Default Zeilenenden und Punkte dann, wenn auf sie ein Leerzeichen folgt. Andere Zeichen, die in freiem Text ein Satzende anzeigen können (also Ausrufungszeichen und Fragezeichen) kommen in der Wikipedia in dieser Funktion kaum vor und sollten vor allem niemals den einleitenden Definitionssatz abschließen --- daher werden sie hier nicht beachtet.
\item[\javaid{LanguageConfiguration.sentenceTailGlue}] definiert ein Muster, das "`unechte"' Satzenden erkennt: falls das Ende des bisher gefundene Textes auf dieses Muster passt, so ist der Satz vermutlich noch nicht vollständig und es sollte ein weiterer "`Schnipsel"' angehängt werden. Diese Muster enthält vor allem Abkürzungen, die mit einem Punkt enden, insbesondere solche, die auch häufig in Definitionssätzen vorkommen, wie \zB \wikitext{Dr.} (\txt{Doktor}) oder \wikitext{geb.} (\txt{geboren}).
\item[\javaid{LanguageConfiguration.sentenceFollowGlue}] definiert ein Muster, das Satzfortsetzungen findet: falls der Anfang des nächsten "`Chunks"' auf dieses Muster passt, so sollte er an den bereits gefundenen Text angehängt werden. Dieses Muster passt per Default auf alle Kleinbuchstaben, also Zeichen in der Unicode-Kategorie \lingo{Ll} \qs{UNICODE}{139}.
\end{description}

Auf diese Weise kann recht zuverlässig der erste Satz im Fließtext eines Wikipedia-Artikels gefunden werden (\rr{ch:eval-glossen}). In einigen Fällen werden aber Satzgrenzen nicht erkannt, es werden also die ersten beiden Sätze zurückgegeben: das ist insbesondere dann der Fall, wenn der erste Satz mit einer Abkürzung endet, zum Beispiel mit "`\wikitext{etc.}"', was aber auf Grund der Natur des Definitionssatzes selten ist. 

\section{Analyse von Begriffsklärungsseiten}
\label{alg:extractDisambigLinks}

Bei der Analyse von Begriffsklärungsseiten ist das Ziel, von allen Wiki-Links auf der Seite diejenigen zu finden, die auf Bedeutungen des zu klärenden Begriffes verweisen. Das vorgeschlagene Verfahren ist darauf ausgerichtet, in einfachen Fällen mit geringem Aufwand schnell ein Resultat zu liefern, in "`schwierigen"' Fällen aber dennoch präzise Ergebnisse zu erzielen. Sie arbeitet wie folgt:

\begin{center}
 \footnotesize
 \begin{algorithmic}[1]
 \Procedure{extractDisambigLinks}{$title$, $text$} \Comment Finde alle Links zu Bedeutungen
   \State{ $links \gets \emptyset$};
   \If {$disambigStripSectionPattern$} \Comment Falls ein bestimmter Abschnitt ignoriert werden soll\ldots
     \State{$text = $stripSections($text$, $disambigStripSection$);} \Comment \ldots{}entferne ihn.
   \EndIf
   \State{ $name \gets$ determineBaseName($title$);} \Comment Bestimme den zu klärenden Term
   \For{$line$ matching $disambigLinePattern$} \Comment Für alle relevanten Zeilen\ldots
     \State {$link = $determineDisambigTarget($name$, $line$); }\Comment \ldots{}finde den richtigen Link in der Zeile
     \If{$link$}                           \Comment Falls ein solcher Link gefunden wurde\ldots
       \State {add $link$ to $links$;}              \Comment \ldots{}füge ihn zu der Ergebnisliste hinzu
     \EndIf
   \EndFor
 \EndProcedure

 \Procedure{determineDisambigTarget}{$term$, $line$} \Comment Finde den Bedeutungslink in einer Zeile
   \For {$pattern$ in $disambigLinkPatterns$} \Comment Für alle speziellen Link-Muster\ldots
     \If {$line$ matches $pattern$}           \Comment \ldots{}prüfe ob das Muster passt
       \State \Return{ \instr{a link constructed from the match};} \Comment Falls ja, gib den entsprechenden Link zurück
     \EndIf
   \EndFor
   \State \Comment Weiter, falls mittels \var{disambigLinkPatterns} kein Link gefunden wurde.

   \State {$links \gets$ extractLinks($term$, $line$);} \Comment Extrahiere alle Links aus der Zeile

   \If {size($links$) = 0} \Comment Falls es keine Links in der Zeile gibt\ldots
       \State{ return null;} \Comment \ldots{}gib \javaid{null} zurück
   \ElsIf {size($links$) = 1} \Comment Falls es nur genau einen Link in der Zeile gibt\ldots
       \State{ return $links[0]$;} \Comment \ldots{}gib diesen zurück
   \EndIf

   \State \Comment Alle Links, die "`irgendwo"' den Term enthalten
   \State {$links2 \gets \{link \in links | SubStringLinkFilter.matches(name, link)\}$;} 

   \If {size($links2$) $> 0$} \Comment Falls es solche Links gibt\ldots
     \If {size($links2$) $= 1$} \Comment falls es genau einen solchen Link gibt\ldots
       \State{ return $links2[0]$;}  \Comment \ldots{}gib diesen zurück\ldots
     \EndIf
     $links \gets links2$; \Comment ansonsten betrachte im weiteren nur noch die gefilterte Liste
   \EndIf
   \State \Comment Falls es keine solchen Links gab, wird weiter die ungefilterte Liste von Links verwendet

   \For{$link \in links$} \Comment Für jeden Link\ldots
     \State \Comment \ldots{}berechne, wie gut er zu dem Term passt
     \State{ $match[link] \gets $ DefaultLinkSimilarityMeasure.measure($term$, $link$); } 
   \EndFor

   \State{ $best \gets link \in links | best match[link]$;} \Comment Link, der am besten zu dem Term passt
   
   \State \Comment Wenn selbst beste Ähnlichkeit zu gering\ldots
   \If{$match[best] < minDisambigLinkSimilarity$} 
     \State{ return null;} \Comment \ldots{}dann gib \javaid{null} zurück
   \EndIf
   
   \State \Return{ $best$;}
 \EndProcedure
 \end{algorithmic}
% \captionof{algorithm}{makeLink}
\end{center}

Der oben beschriebene Algorithmus verwendet die folgenden Funktionen und Konfigurationsparameter:

\begin{description}
\item[\javaid{WikiConfiguration.disambigStripSectionPattern}] ist ein Muster für die Namen von Abschnitten, die bei der Verarbeitung von Begriffsklärungsseiten ignoriert werden sollen. Insbesondere sind das Abschnitte für Querverweise, also \zB für die deutschsprachige Wikipedia \wikitext{Siehe auch} und für die englischsprachige \wikitext{See also}. Gegebenenfalls wird die Methode \javaid{WikiTextAnalyzer.stripSections} verwendet, um jeden Abschnitt zu entfernen, auf den dieses Muster passt.

\item[\javaid{WikiTextAnalyzer.determineBaseName}] gibt, wie bereits oben (in \rr{sec:analyzer:terme}) beschrieben, den Titel ohne Klammerzusatz zurück. Im Fall einer Begriffsklärungsseite ist das der zu klärende, mehrdeutige Term.

\item[\javaid{WikiConfiguration.disambigLinePattern}] ist ein Muster für solche Zeilen auf einer Begriffsklärungsseite, die typischerweise Links auf Bedeutungen des zu klärenden Terms haben. Per Konvention werden Bedeutungen in Listen aufgezählt, per Default werden also Zeilen betrachtet, die mit "`\wikitext{*}"' oder "`\wikitext{\#}"' beginnen --- allerdings sollten Zeilen ignoriert werden, die mit einem Doppelpunkt enden, da diese in der Regel keine Bedeutung auflisten, sondern einen Abschnitt in der Bedeutungsliste bezeichnen. Der reguläre Ausdruck für Disambiguierungszeilen ist per Default \regex{\^{}:*[*\#]+(.+[\^{}:\textbackslash{}s])\textbackslash{}s*\$}.

\item[\javaid{WikiConfiguration.disambigLinkPatterns}] ist ein Muster für Formulierungen, von denen bekannt ist, dass sie, falls sie in einer Begriffsklärungszeile vorkommen, den gesuchten Link auf den Bedeutungsartikel enthalten. Per Default ist kein solches Muster konfiguriert, es könnte aber verwendet werden, um zum Beispiel gängige Formulierungen wie \wikitext{siehe [[xyz]]} auszunutzen, um den richtigen Link in der Zeile zu finden.

\item[\javaid{PlainTextAnalyzer.SubStringLinkFilter}] ist ein Filter, der auf solche Links passt, die einen bestimmten Term als Substring in ihrem Link-Ziel, Abschnittstext oder Link-Text enthalten. Er benutzt vereinfachte Formen dieser Strings, genau wie \javaid{DefaultLinkSimilarityMeasure.measure} (Kleinschreibung, keine Klammerzusätze, etc).

\item[\javaid{PlainTextAnalyzer.DefaultLinkSimilarityMeasure}] ist ein Maß für die Ähnlichkeit von Links mit einem gegebenen Term --- die Berechnung der Ähnlichkeit ist wie oben beschrieben in der Methode \javaid{DefaultLinkSimilarityMeasure.measure} implementiert. In der tatsächlichen Implementation werden Instanzen dieser Klasse über \javaid{WikiConfiguration.linkSimilarityMeasureFactory} erzeugt, dort kann auch die konkrete Klasse konfiguriert werden.
\item[\javaid{WikiConfiguration.minDisambigLinkSimilarity}] gibt die minimale Ähnlichkeit an, die ein Link zu dem gesuchten Term aufweisen muss, um als Bedeutungslink in Betracht zu kommen. Hat kein Link in der Zeile einen Ähnlichkeitswert, der \javaid{minDisambigLinkSimilarity} übersteigt, so wird die Zeile übergangen.
\end{description}

Im Folgenden ist der Algorithmus beschrieben, der von \javaid{PlainTextAnalyzer.DefaultLinkSimilarityMeasure} verwendet wird, um die lexikographische Ähnlichkeit\index{lexikographische Ähnlichkeit} eines Links mit einem gegebenen Term zu bestimmen.

\begin{center}
 \label{alg:DefaultLinkSimilarityMeasure.measure}
 \footnotesize
 \begin{algorithmic}[1]
 
 \State \Comment misst zwischen einem Link und einem Term.
 \Procedure{DefaultLinkSimilarityMeasure.measure}{$term$, $link$} 
   \State{ $p \gets$ trimAndLower(determineBaseName($link.page$));} \Comment Vereinfache das Link-Ziel
   \State{ $s \gets$ trimAndLower(normalizeTitle($link.section$));} \Comment Vereinfache den Abschnittsnamen
   \State{ $t \gets$ trimAndLower(normalizeTitle($link.text$);}     \Comment Vereinfache den Link-Text

   \State{ $ps \gets$ measureTextMatch($term$, $p$);} \Comment Vergleiche Term mit Link-Ziel
   \State{ $ss \gets$ measureTextMatch($term$, $s$);} \Comment Vergleiche Term mit Abschnittsnamen
   \State{ $ts \gets$ measureTextMatch($term$, $t$);} \Comment Vergleiche Term mit Link-Text

   \State  \Return{ max($ps$, $ss$, $ts$);} \Comment Gib besten Ähnlichkeitswert zurück
 \EndProcedure

 \State \Comment Misst, wie gut ein Name zu einem Term passt (Wert zwischen 0 und 1).
 \Procedure{DefaultLinkSimilarityMeasure.measureTextMatch}{$term$, $name$} 
   \If {$term = name$} \Comment Falls Name und Term identisch sind\ldots
     \State \Return{ 1;} \Comment \ldots{}gib 1 zurück.
   \EndIf
   \State{ $subsim \gets$ calculateSubstringSimilarity($term$, $name$);}    \Comment Zeichenweise Abdeckung 
   \State{ $levsim \gets$ calculateLevenshteinSimilarity($term$, $name$);}  \Comment Levenshtein-Ähnlichkeit
   \State{ $wordsim \gets$ calculateWordOverlapSimilarity($term$, $name$);} \Comment Überlappung der Wortmengen
   \State{ $acrosim \gets$ calculateAcronymSimilarity($term$, $name$);}     \Comment Levenshtein auf Anfangsbuchstaben

   \State \Return{ max($subsim$, $levsim$, $wordsim$, $acrosim$)}; \Comment Gib besten Wert zurück
 \EndProcedure
 \end{algorithmic}
% \captionof{algorithm}{makeLink}
\end{center}

Dieser Algorithmus verwendet die folgenden Funktionen zur Berechnung von lexikographischer Ähnlichkeit zwischen Zeichenketten (der resultierende Ähnlichkeitswert liegt immer zwischen 0 und 1):

\begin{description}
  \item[\javaid{DefaultLinkSimilarityMeasure.calculateSubstringSimilarity}] berechnet die Ähnlichkeit eines Namens \var{n} zu dem gegebenen Term \var{t} wie folgt: falls \var{t} nicht in \var{n} vorkommt, ist die Ähnlichkeit 0. Sonst ist die Ähnlichkeit gegeben durch den Anteil, zu dem der Term den Namen abdeckt:
\nospell{$$sim_{sub} = \frac{|t|}{|n|}$$}
  
  \item[\javaid{DefaultLinkSimilarityMeasure.calculateLevenshteinSimilarity}] \label{p:levenshtein-similarity} berechnet die Ähnlichkeit eines Namens \var{n} zu dem gegebenen Term \var{t} auf Basis der Levenshtein-Distanz \q{levenshtein1966bcc} \var{lev(n, t)} als normierter Rest verbleibend auf die maximal mögliche Distanz: 
 \nospell{$$sim_{lev} = \frac{max(|n|, |t|) - lev(n, t)}{max(|n|, |t|)}$$}
  
  \item[\javaid{DefaultLinkSimilarityMeasure.calculateWordOverlapSimilarity}] berechnet die Ähnlichkeit eines Namens \var{n} zu dem gegebenen Term \var{t} als die normierte Überlappung der Wortmengen $w(n)$ und $w(t)$ gemäß der Formel
 \nospell{$$sim_{words} = \frac{|w(n) \cap w(t)|}{max(|w(n)|, |w(t)|)}$$}
  
  Zur Zerlegung der Zeichenketten in Wortmengen wird die Methode \javaid{PlainTextAnalyzer.extractWords} verwendet, die ihrerseits das in \javaid{LanguageConfiguration.wordPattern} festgelegte Muster benutzt. Per Default ist der verwendete reguläre Ausdruck \regex{\textbackslash{}p\{L\}+|\textbackslash{}p\{Nd\}+}, also jede Folge von entweder Buchstaben oder Ziffern, gemäß den Unicode-Kategorien für Buchstaben und Dezimalziffern, nämlich \lingo{Lu}, \lingo{Ll}, \lingo{Lt}, \lingo{Lm}, \lingo{Lo} und \lingo{Nd} \qs{UNICODE}{139}.
  
  \item[\javaid{DefaultLinkSimilarityMeasure.calculateAcronymSimilarity}] berechnet die Ähnlichkeit eines Namens \var{n} mit dem gegebenen Term \var{t} unter der Annahme, dass \var{t} ein Akronym für \var{n} ist: Sei \var{acro(n)} eine Funktion, die die Konkatenation der Anfangsbuchstaben der Wörter aus \var{n} liefert (wie durch \javaid{LanguageConfiguration.wordPattern} bestimmt), dann ist die Ähnlichkeit gegeben durch:
  \nospell{$$ sim_{acro} = sim_{lev}(t, acro(n))$$}
  
  Diese Ähnlichkeitsfunktion ist besonders deshalb wichtig, weil Begriffsklärungsseiten häufig verschiedene Bedeutungen von Akronymen aufzählen, der zu klärende Term also ein Akronym ist: \zB listet die Seite \wikipage{AA} in der deutschsprachigen Wikipedia unter anderem Links auf die Bedeutungen \wikipage{Alemannia Aachen}, \wikipage{American Airlines}, \wikipage{Anonyme Alkoholiker} und \wikipage{Arbeitsagentur}. Daher ist es wichtig, dass der Term \wwterm{AA} als lexikographisch ähnlich zu solchen Namen erkannt wird.
\end{description}

Dieses Verfahren wurde in \rr{ch:eval-bkl} evaluiert.

\section{Zusammenführen von sprachübergreifenden Konzepten}
 \label{alg:Merging}
 
Nachdem die Ähnlichkeiten von Konzepten wie in \rr{sec:Merging} beschrieben bestimmt wurden, werden nach folgendem Schema Konzepte aus unterschiedlichen Sprachen zu einem sprachübergreifenden Konzept zusammengefasst:

\pagebreak %XXX: nasty hardcoded pagebreak to fix orphan
\begin{center}
 \footnotesize
 \begin{algorithmic}[1]
 \Procedure{clusterGlobalConcepts}{$concepts$, $langref$} \Comment Vereinige passende Konzepte
    \State \Comment \var{langref} enthält Language-Link Referenzen zwischen Konzepten
    
    \State \Comment gegenseitige Referenzierung via Language-Link wird als "`Ähnlichkeit"' interpretiert
    \State{ $similar \gets \{(x, y) \quad|\quad (x, y) \in langref \wedge (y, x) \in langref\}$;} 
    
    \Repeat \Comment das Zusammenführen ist in "`Runden"' aufgeteilt
        \State{ $replace \gets$ findMergeCandidates($concepts$, $similar$)};
        \State \Comment Neue, vereinigte Konzepte wurden hinzugefügt, die alten wurden aber noch erhalten
        \State \Comment \var{replace} enthält nun Paare von Konzept-IDs, die als Abbildung von den IDs der alten 
        \State \Comment auf die IDs der neuen, vereinigten Konzepte dient. Die neuen, vereinigten Konzepte
        \State \Comment wurden in \var{concepts} aufgenommen.
        
        \State{ performMerge($replace$, $similar$);} \Comment Vereinigte Konzepte in allen Relationen ersetzen
    \Until{$replace = \emptyset$}
 \EndProcedure
 
 \Procedure{findMergeCandidates}{$concepts$, $similar$} \Comment Finde zu vereinigende Konzepte
    \State{ $stop \gets \emptyset$;}  \Comment Stoppliste von bereits verarbeiteten Konzepten
    \State{ $replace \gets \emptyset$;} \Comment Liste von ausstehenden Ersetzungen
    
    \For{$x \in concepts$}
      \If{$x \in stop$}    \Comment während dieser Runde bereits verarbeitet
        \State{ continue};
      \EndIf
      
      \State{ $stop$.add($x$);} \Comment als verarbeitet markieren
      \State{  $sim \gets \{y \in concepts \quad|\quad (x, y) \in similar\}$;} \Comment Ähnliche Konzepte
      
      \For{$y \in concepts$}
	      \If{$y \in stop$} \Comment während dieser Runde bereits verarbeitet
	        \State{ continue};
	      \EndIf
      
          \State{ $stop$.add($y$);} \Comment als verarbeitet markieren
          
	      \If{$(x.language\_bits \& y.language\_bits) > 0$)} \Comment Konflikt, Vereinigen nicht möglich;
	        \State{ $similar$.remove( $(x, y)$ )};
	        \State{ continue};
	      \EndIf
          
          \State{ $m \gets$ createMergedConcept($x$, $y$);}  \Comment vereinigtes Konzept erzeugen
          \State{ $concepts$.add($m$);}        \Comment vereinigtes Konzept hinzufügen
          \State{ $replace$.add( $(x, m)$ );}  \Comment zur Ersetzung vormerken
          \State{ $merge$.add( $(y, m)$ );}    \Comment zur Ersetzung vormerken
      \EndFor
    \EndFor
    \State \Return {$replace$;}
 \EndProcedure

 \Procedure{performMerge}{$replace$, $similar$} \Comment Ersetzt Referenzen von alten Konzepten
   \State \instr{Ersetze alle Vorkommen der alten einzelnen Konzepte in \var{replace} durch die neuen,}
   \State \instr{vereinigten, in allen Relationen inklusive \var{similar}. }
   \State \instr{Auch die Tabellen \var{origin} und \var{relation} werden entsprechend angepasst.}
                            
   \State \instr{Nach der Ersetzung, lösche die entstandenen Schleifen aus allen Relationen.}
   \State \instr{Lösche nun die alten Konzepte.}
   %\State{ $concepts$.remove($\{x \quad|\quad \exists y: (x, y) \in replace\}$);}  \Comment Lösche die alten Konzepte aus \var{concepts}
 \EndProcedure
 
 \Procedure{createMergedConcept}{$x$, $y$} \Comment Erzeuge kombiniertes Konzept
   \State $z \gets$ new Concept(); 					\Comment Erzeuge neues Konzeptobjekt
   \State $z.name \gets x.name + "`|"' + y.name$;   \Comment Konkatenation der beiden Namen
   \State $z.language\_bits \gets x.language\_bits | y.language\_bits$; \Comment Bit-OR der Language-Bits
   \If { $x.type = UNKNOWN \vee x.type = OTHER$ } \Comment Wenn \var{x} keinen spezifischen Typ hat\ldots
	   \State $z.type \gets y.type$;   \Comment \ldots{}dann verwendet den Typ von \var{y}
   \ElsIf { $y.type = UNKNOWN \vee y.type = OTHER$ } \Comment Wenn \var{y} keinen spezifischen Typ hat\ldots
	   \State $z.type \gets x.type$;   \Comment \ldots{}dann verwendet den Typ von \var{x}
   \Else { $y.ltype = UNKNOWN \vee y.type = OTHER$ } \Comment Wenn beide einen spezifischen Typ haben\ldots
   	\If { $x.type \neq y.type$ }
   	   \Comment Wenn zwei Konzepte vereinigt werden, die unterschiedliche, spezifische 
   	   \Comment Konzepttypen haben, ist das ein Hinweis auf einen Fehler. \later{give count from log}
       \State \instr{log type conflict.} 
    \EndIf
	   \State $z.type \gets x.type$;   \Comment \ldots{} Verwendet den Typ von \var{x}
   \EndIf
   \State \Return {$z$;}
 \EndProcedure
 
 \end{algorithmic}
\end{center}

Das Zusammenführen findet also in "`Runden"' statt: In jeder Runde werden zunächst alle Konzepte durchlaufen und für jedes nach einem "`Partner"' zum Zusammenführen gesucht. Dann werden alle solchen Paare von Partnern zu neuen Konzepten zusammengeführt und sämtliche Referenzen auf die alten Konzepte durch eine Referenz auf das neue, kombinierte Konzept ersetzt. Wird in einer Runde kein zu vereinigendes Paar mehr gefunden, terminiert der Algorithmus.

Dabei ist zu beachten, dass jedes der globalen Konzepte immer eine Menge von sprachspezifischen Konzepten ist, wobei die Größe dieser Menge durch die Anzahl der betrachteten Sprachen begrenzt ist, da ja aus jeder Sprache höchstens ein lokales Konzept zu einem globalen Konzept gehören kann. Andererseits wächst die Größe dieser Mengen bei jeder Runde an: in der ersten Zusammenführungsrunde entstehen Gruppen der Größe zwei, in der zweiten Zusammenführungsrunde entstehen Gruppen der Größe von mindestens drei bis höchstens vier, in der dritten Runde zwischen mindestens vier bis höchstens acht, und so weiter. Damit ist klar, dass die Anzahl der betrachteten Sprachen auch die Anzahl der maximal notwendigen Vereinigungsrunden begrenzt.

Auch die Anzahl der maximal zu betrachtenden Partner für jedes Konzept ist durch die Anzahl der Sprachen beschränkt, da die Partner ja durch gegenseitige Verknüpfung über Language-Links bestimmt werden, pro Sprache und Artikel aber nur ein Language-Link zulässig ist. Ist nun \var{k} die Anzahl der Sprachen und \var{n} die Anzahl der Konzepte, so ist die Laufzeit des Vereinigungsalgorithmus beschränkt durch \nospell{$\mathcal{O}(k \cdot n)$} --- beachtet man den Aufwand der Lookups für die verschiedenen Mengen, ergibt sich \nospell{$\mathcal{O}(k \cdot n \cdot log(n))$}.

\later{critique: too restrictive. missing links to small projects.}
