Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / WS 2009/10 / Oberseminar / Dongyuan Yu: Algorithmen und Heuristiken für das Longest-Common-Substring-Problem


Inhaltsbereich

Dongyuan Yu: Algorithmen und Heuristiken für das Longest-Common-Substring-Problem

09.10.2009 14:15
Wann 14:15 15:45 09.10.2009
von bis
Wo Z1.09
Termin übernehmen vCal
iCal
Diese Diplomarbeit beschreibt die Implementierungen von zwei Algorithmen zur LCS (Longest-Common-Substring)-Suche. Einer ist ein bereits vorhandener Algorithmus, um das LCS-Problem effizient zu lösen, und heißt Suffix-Baum-Algorithmus. Der andere ist ein neu vom Autor entdeckter Algorithmus namens N-Breiten-Tiefen-Suchen-Algorithmus. Der neue Algorithmus ist ein Kombinationsverfahren zwischen der traditionalen Tiefensuche und der Breitensuche. Er ermöglicht einen unterbrechbaren Suchprozess, wodurch man innerhalb kurzer Zeit einen langen gemeinsamen Substring finden kann. Im Rahmen dieser Arbeit werden die Tests zur Ermittlung der Eigenschaften von dem neuen entdeckten Algorithmus durchgeführt werden. Dabei ist zu beachten, dass die Auswirkungen der Einflussgrößen (Länge des Input-Strings, Menge des Input-Strings, Suchbreite N usw.) auf die Sucheffizienz getestet werden. Aufgezeigt wird auch der Vergleich von zwei Algorithmen. Anhand des Vergleichsergebnisses wird die individuelle Auswertung von zwei Algorithmen angefertigt.

Artikelaktionen


Funktionsleiste