<commit_before>\documentclass[a4paper,titlepage,12pt]{scrartcl}

% utf-8
\usepackage{polyglossia}
\setdefaultlanguage[babelshorthands]{ngerman}
\usepackage{fontspec}

% german names
\usepackage{ngerman}

% colored links
\usepackage{color}
\usepackage[colorlinks]{hyperref}
% custom colors
\definecolor{grey}{rgb}{0.2,0.2,0.2}
\definecolor{orange}{rgb}{1,0.3,0}
\definecolor{turqoise}{rgb}{0,0.7,0.5}

% code listings
\usepackage{listings}
\lstset{%
	basicstyle={\ttfamily \small},
	breaklines=true,
	commentstyle=\color{grey},
	keywordstyle=\color{orange},
	language=C,
	numbers=left,
	showspaces=false,
	stringstyle=\color{turqoise},
	xleftmargin=20pt
}

% graphics
\usepackage{graphicx}
\graphicspath{i/}

% fancy headers and footers
\usepackage{fancyhdr}
\pagestyle{fancy}
% clear style
\fancyhead{}
\fancyfoot{}
% new style
\renewcommand{\headrulewidth}{0.5pt}
\renewcommand{\footrulewidth}{0.5pt}
\fancyhead[LE,RO]{\rightmark}
\fancyhead[LO,RE]{\leftmark}
\fancyfoot[LE,RO]{\thepage}
\fancyfoot[LO,RE]{Qualtitätssicherung WS 2012/2013}
\fancypagestyle{plain}{%
	\fancyhf{}
	\renewcommand{\headrulewidth}{0pt}
	\renewcommand{\footrulewidth}{0.5pt}
	\fancyfoot[LE,RO]{\thepage}
	\fancyfoot[LO,RE]{Qualitätssicherung WS 2012/2013}
}

% no indented paragraphs
\usepackage{parskip}

% TODO: what's this?
\setkomafont{disposition}{\normalfont\bfseries}

\usepackage{natbib}

\usepackage{amsfonts}

\usepackage{verbatim}

\begin{document}

\titlehead{%
	\includegraphics[width=0.9\linewidth]{i/hska_logo.png}
}

\title{Ausarbeitung Qualitätssicherung}
\author{<NAME> \\ Mat.-Nr.: 30470}
\date{Wintersemester 2012/2013}
\publishers{%
    \textbf{Betreuer:} Prof.\,Dr. <NAME>
}
\maketitle

\tableofcontents

\clearpage

\section{Einleitung}
\label{sec:intro}
Im Rahmen der Blockveranstaltung \emph{Qualtitätssicherung} war die Aufgabenstellung,
ein Werkzeug zum Verschmelzen zweier Textdateien auf der Basis einer gemeinsamen Version zu erstellen.
Dabei sollte ein Algorithmus zur Bestimmung der Längsten gemeinsamen Teilfolge verwendet werden,
welcher nicht rekursiv arbeitet und eine maximale Komplexität von $O(n^2)$ hat.
Dieses Werkzeug war im Anschluss unter Verwendung von Zeilenüberdeckung zu testen.
Die Implementierungssprache war freigestellt,
sofern Werkzeuge zur Zeilenüberdeckungsanalyse zur Verfügung stehen.

Diese Ausarbeitung bezieht sich auf das Programm \texttt{qsmerge},
welches die Lösung des Autors für die obige Aufgabenstellung darstellt.
Es wurde in C implementiert,
weshalb das Werkzeug \texttt{gcov} zu, Test der Zeilenüberdeckung verwendet wurde.
\\
Der gesamte Quellcode für das Programm sowie diese Ausarbeitung is im Internet unter der Adresse \url{https://github.com/flimberger/qsmerge} als Git-Repository zu finden.

\section{Design}
\label{sec:design}
Die Benutzerschnittstelle des \texttt{qsmerge}-Programms wurde \texttt{diff3} nachempfunden,
welches üblicherweise in unixoiden Systemumgebungen zur Verfügung steht.
Daher handelt es sich um ein Kommandozeilenprogramm,
welches mit folgender Signatur aufgerufen wird:
\lstset{language=sh, numbers=none, xleftmargin=0pt}
\begin{lstlisting}
qsmerge dave.txt orig.txt mike.txt
\end{lstlisting}
Dabei handelt es sich bei \texttt{dave.txt} und \texttt{mike.txt} um die beiden neuen Dateiversionen handelt,
welche miteinander verschmolzen werden sollen,
während \texttt{orig.txt} die gemeinsame Ausgangsversion ist.
Bei einer vollständig automatisch durchgeführten Verschmelzung ist der Rückgabewert 0,
falls Konflikte auftraten 1.
In diesem Falle werden die Konflikte ebenfalls in die Ausgabe geschrieben,
wobei sich die Syntax an der Ausgabe von \texttt{diff3 -m} orientiert:
\begin{verbatim}
<<<<<<< dave.txt:1
/* Dave */
=======
/* Mike */
>>>>>>> mike.txt:1
\end{verbatim}
Die Ausgabe wird in den Standardausgang geschrieben,
wodurch man sie einfach in Dateien oder andere Programme umleiten kann.
Falls während dem Programmablauf Fehler auftreten,
wird es mit einem Status von 2 beendet.
Durch diese Architektur kann \texttt{qsmerge} einfach in Skripten verwendet werden.

Im Gegensatz zum Vorbild werden keine Bereiche unterstützt,
da \texttt{qsmerge} lediglich auf Zeilenebene arbeitet.
Auch wird bei einem Konflikt nicht der Inhalt der Ursprungsdatei angezeigt,
da die Ausgabe dadurch sehr unübersichtlich werden würde.
Dafür wird die Zeile zusätzlich zur Ursprungsdatei angegeben.
Weitere Unterschiede zwischen \texttt{qsmerge} und \texttt{diff3} bestehen darin,
dass \texttt{qsmerge} keinerlei Optionen unterstützt und keine \texttt{ed}-Skripte ausgeben kann.
\\
Optionen zum automatischen Lösen von Konflikten durch Bevorzugung einer Version wären jedoch einfach hinzuzufügen.

\section{Algorithmus}
\label{sec:algorithm}
Der Verschmelzungsalgorithmus basiert auf der längsten gemeinsamen Teilfolge von Zeilen aller drei Dateiversionen und der darauffolgenden Auflösung der Konflikte.
Für die weitere Beschreibung gelten folgende Konventionen:
\begin{itemize}
\item $\mathbb{L}$ sei die Menge aller geordneten Listen von Textzeilen.
\item Großgeschriebene Variablen stehen für Elemente von $\mathbb{L}$,
wobei $A, B, O \in \mathbb{L}$ die beiden Eingabedateien und die Originaldatei repräsentieren.
\item $|L| \in \mathbb{N}_0$ mit $L \in \mathbb{L}$ beschreibt die Kardinalität von $L$,
also die Anzahl der Textzeilen in $L$.
\item $L(i)$ mit $i \in \mathbb{N}_0, L \in \mathbb{L}$ beschreibt die $i$-te Zeile aus $L$.
\item $\mbox{LCS}: \mathbb{L} \times \mathbb{L} \rightarrow \mathbb{L}$ beschreibt eine Funktion,
welche die längte gemeinsame Teilfolge der Zeilen der beiden Eingabeparameter zurückgibt.
\end{itemize}

Um die LGT aller drei Dateien zu erhalten,
werden zunächst die längsten gemeinsamen Teilfolgen mit $L_{A,O} = \mbox{LCS}(A, O)$ und $L_{B,O} = \mbox{LCS}(B, O)$ berechnet,
mit $L_{A,B,O} = \mbox{LCS}(L_{A,O}, L_{B,O})$ wird anschließend die LGT aller drei Eingabedateien berechnet.

Zur Ermittelung der längsten gemeinsamen Teilfolge wurde der in \citet{web:eppstein} beschriebene LGT-Algorithmus verwendet,
jedoch musste er an die Eigenheiten des Programms angepasst werden.
Der Algorithmus nutzt aufsteigende dynamische Programmierung,
um Rekursion zu vermeiden.
Dabei werden alle Zeilen der Eingabeparameter miteinander verglichen,
indem über eine Matrix iteriert wird,
in welcher die Vergleichsresultate der einzelnen Zeilen gespeichert sind.
Die Iteration beginnt rechts unten in der ausgenullten Matrix und wird nach links oben fortgesetzt.
Mit jeder Übereinstimmung zweier Zeilen erhält das aktuelle Feld den Wert des diagonal darunterliegenden Feldes um 1 erhöht.
Alle nachfolgenden Felder erhalten den Wert der Felder rechts daneben oder darunter,
außer es kommt zu einer weiteren Übereinstimmung.
Dadurch erhält man die Anzahl der gleichen Zeilen im ersten Feld der Mastrix.
Daraufhin kann von vorne durch die Matrix iteriert werden,
wobei die diagonalen Übergänge zwischen den Feldwerten gesucht werden,
da an diesen Stellen die Zeilen übereinstimmen.

Mit den auf diese Weise ermittelten LGT wird die Ausgabe zusammengestellt,
wofür über alle Zeilen der beiden neuen Dateiversionen iteriert wird.
Solange sowohl $A(i)$ als auch $B(j)$ gültige Zeilen beschreiben,
also wenn $i < |A| \wedge j < |B|$ gilt,
wird die Ausgabe von folgende Regeln bestimmt:
\begin{itemize}
\item Wenn $A(i) = B(j)$ gilt,
dann wird eine der beiden Zeilen (welche identisch sind) ausgegeben.
\item Wenn $A(i) = L_{A,B,O}(m)$ gilt,
dann wird die Zeile $B(j)$ ausgegeben,
da diese in B neu eingefügt wurde.
\item Wenn $B(j) = L_{A,B,O}(m)$ gilt,
dann wird $A(i)$ augegeben.
\item Wenn $A(i) = L_{A,O}(k)$ gilt,
dann wird die Zeile $B(j)$ ausgegeben,
da diese in A beibehalten wurde.
Die Zeile $A(i)$ wird verworfen.
\item Wenn $B(j) = L_{B,O}$ gilt,
dann wird $A(i)$ ausgegeben und $B(j)$ verworfen.
\item Im letzten Fall liegt ein Verschmelzungskonflikt vor,
da sowohl $A(i)$ als auch $B(j)$ neu eingefügt worden.
Daher werden beide Zeilen mit der in Abschnitt~\ref{sec:design} beschriebenen Notation ausgegeben.
\end{itemize}<commit_msg>Break up long and ununderstandable sentence<commit_after>\documentclass[a4paper,titlepage,12pt]{scrartcl}

% utf-8
\usepackage{polyglossia}
\setdefaultlanguage[babelshorthands]{ngerman}
\usepackage{fontspec}

% german names
\usepackage{ngerman}

% colored links
\usepackage{color}
\usepackage[colorlinks]{hyperref}
% custom colors
\definecolor{grey}{rgb}{0.2,0.2,0.2}
\definecolor{orange}{rgb}{1,0.3,0}
\definecolor{turqoise}{rgb}{0,0.7,0.5}

% code listings
\usepackage{listings}
\lstset{%
	basicstyle={\ttfamily \small},
	breaklines=true,
	commentstyle=\color{grey},
	keywordstyle=\color{orange},
	language=C,
	numbers=left,
	showspaces=false,
	stringstyle=\color{turqoise},
	xleftmargin=20pt
}

% graphics
\usepackage{graphicx}
\graphicspath{i/}

% fancy headers and footers
\usepackage{fancyhdr}
\pagestyle{fancy}
% clear style
\fancyhead{}
\fancyfoot{}
% new style
\renewcommand{\headrulewidth}{0.5pt}
\renewcommand{\footrulewidth}{0.5pt}
\fancyhead[LE,RO]{\rightmark}
\fancyhead[LO,RE]{\leftmark}
\fancyfoot[LE,RO]{\thepage}
\fancyfoot[LO,RE]{Qualtitätssicherung WS 2012/2013}
\fancypagestyle{plain}{%
	\fancyhf{}
	\renewcommand{\headrulewidth}{0pt}
	\renewcommand{\footrulewidth}{0.5pt}
	\fancyfoot[LE,RO]{\thepage}
	\fancyfoot[LO,RE]{Qualitätssicherung WS 2012/2013}
}

% no indented paragraphs
\usepackage{parskip}

% TODO: what's this?
\setkomafont{disposition}{\normalfont\bfseries}

\usepackage{natbib}

\usepackage{amsfonts}

\usepackage{verbatim}

\begin{document}

\titlehead{%
	\includegraphics[width=0.9\linewidth]{i/hska_logo.png}
}

\title{Ausarbeitung Qualitätssicherung}
\author{<NAME> \\ Mat.-Nr.: 30470}
\date{Wintersemester 2012/2013}
\publishers{%
    \textbf{Betreuer:} Prof.\,Dr. Dirk <NAME>
}
\maketitle

\tableofcontents

\clearpage

\section{Einleitung}
\label{sec:intro}
Im Rahmen der Blockveranstaltung \emph{Qualtitätssicherung} war die Aufgabenstellung,
ein Werkzeug zum Verschmelzen zweier Textdateien auf der Basis einer gemeinsamen Version zu erstellen.
Dabei sollte ein Algorithmus zur Bestimmung der Längsten gemeinsamen Teilfolge verwendet werden,
welcher nicht rekursiv arbeitet und eine maximale Komplexität von $O(n^2)$ hat.
Dieses Werkzeug war im Anschluss unter Verwendung von Zeilenüberdeckung zu testen.
Die Implementierungssprache war freigestellt,
sofern Werkzeuge zur Zeilenüberdeckungsanalyse zur Verfügung stehen.

Diese Ausarbeitung bezieht sich auf das Programm \texttt{qsmerge},
welches die Lösung des Autors für die obige Aufgabenstellung darstellt.
Es wurde in C implementiert,
weshalb das Werkzeug \texttt{gcov} zu, Test der Zeilenüberdeckung verwendet wurde.
\\
Der gesamte Quellcode für das Programm sowie diese Ausarbeitung is im Internet unter der Adresse \url{https://github.com/flimberger/qsmerge} als Git-Repository zu finden.

\section{Design}
\label{sec:design}
Die Benutzerschnittstelle des \texttt{qsmerge}-Programms wurde \texttt{diff3} nachempfunden,
welches üblicherweise in unixoiden Systemumgebungen zur Verfügung steht.
Daher handelt es sich um ein Kommandozeilenprogramm,
welches mit folgender Signatur aufgerufen wird:
\lstset{language=sh, numbers=none, xleftmargin=0pt}
\begin{lstlisting}
qsmerge dave.txt orig.txt mike.txt
\end{lstlisting}
Dabei handelt es sich bei \texttt{dave.txt} und \texttt{mike.txt} um die beiden neuen Dateiversionen handelt,
welche miteinander verschmolzen werden sollen,
während \texttt{orig.txt} die gemeinsame Ausgangsversion ist.
Bei einer vollständig automatisch durchgeführten Verschmelzung ist der Rückgabewert 0,
falls Konflikte auftraten 1.
In diesem Falle werden die Konflikte ebenfalls in die Ausgabe geschrieben,
wobei sich die Syntax an der Ausgabe von \texttt{diff3 -m} orientiert:
\begin{verbatim}
<<<<<<< dave.txt:1
/* Dave */
=======
/* Mike */
>>>>>>> mike.txt:1
\end{verbatim}
Die Ausgabe wird in den Standardausgang geschrieben,
wodurch man sie einfach in Dateien oder andere Programme umleiten kann.
Falls während dem Programmablauf Fehler auftreten,
wird es mit einem Status von 2 beendet.
Durch diese Architektur kann \texttt{qsmerge} einfach in Skripten verwendet werden.

Im Gegensatz zum Vorbild werden keine Bereiche unterstützt,
da \texttt{qsmerge} lediglich auf Zeilenebene arbeitet.
Auch wird bei einem Konflikt nicht der Inhalt der Ursprungsdatei angezeigt,
da die Ausgabe dadurch sehr unübersichtlich werden würde.
Dafür wird die Zeile zusätzlich zur Ursprungsdatei angegeben.
Weitere Unterschiede zwischen \texttt{qsmerge} und \texttt{diff3} bestehen darin,
dass \texttt{qsmerge} keinerlei Optionen unterstützt und keine \texttt{ed}-Skripte ausgeben kann.
\\
Optionen zum automatischen Lösen von Konflikten durch Bevorzugung einer Version wären jedoch einfach hinzuzufügen.

\section{Algorithmus}
\label{sec:algorithm}
Der Verschmelzungsalgorithmus basiert auf der längsten gemeinsamen Teilfolge von Zeilen aller drei Dateiversionen und der darauffolgenden Auflösung der Konflikte.
Für die weitere Beschreibung gelten folgende Konventionen:
\begin{itemize}
\item $\mathbb{L}$ sei die Menge aller geordneten Listen von Textzeilen.
\item Großgeschriebene Variablen stehen für Elemente von $\mathbb{L}$,
wobei $A, B, O \in \mathbb{L}$ die beiden Eingabedateien und die Originaldatei repräsentieren.
\item $|L| \in \mathbb{N}_0$ mit $L \in \mathbb{L}$ beschreibt die Kardinalität von $L$,
also die Anzahl der Textzeilen in $L$.
\item $L(i)$ mit $i \in \mathbb{N}_0, L \in \mathbb{L}$ beschreibt die $i$-te Zeile aus $L$.
\item $\mbox{LCS}: \mathbb{L} \times \mathbb{L} \rightarrow \mathbb{L}$ beschreibt eine Funktion,
welche die längte gemeinsame Teilfolge der Zeilen der beiden Eingabeparameter zurückgibt.
\end{itemize}

Um die LGT aller drei Dateien zu erhalten,
werden zunächst die längsten gemeinsamen Teilfolgen mit $L_{A,O} = \mbox{LCS}(A, O)$ und $L_{B,O} = \mbox{LCS}(B, O)$ berechnet,
mit $L_{A,B,O} = \mbox{LCS}(L_{A,O}, L_{B,O})$ wird anschließend die LGT aller drei Eingabedateien berechnet.

Zur Ermittelung der längsten gemeinsamen Teilfolge wurde der in \citet{web:eppstein} beschriebene LGT-Algorithmus verwendet,
jedoch musste er an die Eigenheiten des Programms angepasst werden.
Der Algorithmus nutzt aufsteigende dynamische Programmierung,
um Rekursion zu vermeiden.
Dabei werden alle Zeilen der Eingabeparameter miteinander verglichen,
indem über eine Matrix iteriert wird,
in welcher die Vergleichsresultate der einzelnen Zeilen gespeichert sind.
Die Iteration beginnt rechts unten in der ausgenullten Matrix und wird nach links oben fortgesetzt.
Jedes Mal, wenn eine Übereinstimmung vorliegt,
erhält das aktuelle Feld den um Eins inkrementierten Wert des Felds rechts darunter.
Alle nachfolgenden Felder erhalten den Wert der Felder rechts daneben oder darunter,
außer es kommt zu einer weiteren Übereinstimmung.
Dadurch erhält man die Anzahl der gleichen Zeilen im ersten Feld der Matrix.
Daraufhin kann von vorne durch die Matrix iteriert werden,
wobei die diagonalen Übergänge zwischen den Feldwerten gesucht werden,
da an diesen Stellen die Zeilen übereinstimmen.

Mit den auf diese Weise ermittelten LGT wird die Ausgabe zusammengestellt,
wofür über alle Zeilen der beiden neuen Dateiversionen iteriert wird.
Solange sowohl $A(i)$ als auch $B(j)$ gültige Zeilen beschreiben,
also wenn $i < |A| \wedge j < |B|$ gilt,
wird die Ausgabe von folgende Regeln bestimmt:
\begin{itemize}
\item Wenn $A(i) = B(j)$ gilt,
dann wird eine der beiden Zeilen (welche identisch sind) ausgegeben.
\item Wenn $A(i) = L_{A,B,O}(m)$ gilt,
dann wird die Zeile $B(j)$ ausgegeben,
da diese in B neu eingefügt wurde.
\item Wenn $B(j) = L_{A,B,O}(m)$ gilt,
dann wird $A(i)$ augegeben.
\item Wenn $A(i) = L_{A,O}(k)$ gilt,
dann wird die Zeile $B(j)$ ausgegeben,
da diese in A beibehalten wurde.
Die Zeile $A(i)$ wird verworfen.
\item Wenn $B(j) = L_{B,O}$ gilt,
dann wird $A(i)$ ausgegeben und $B(j)$ verworfen.
\item Im letzten Fall liegt ein Verschmelzungskonflikt vor,
da sowohl $A(i)$ als auch $B(j)$ neu eingefügt worden.
Daher werden beide Zeilen mit der in Abschnitt~\ref{sec:design} beschriebenen Notation ausgegeben.
\end{itemize}
{'fraction_non_alphanumeric': 0.09510211682910175, 'fraction_numerical': 0.008877025265379602, 'mean_word_length': 5.7974683544303796, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 21, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '895237', 'n_tokens_mistral': 5809, 'n_tokens_neox': 5977, 'n_words': 1770}