Home  Sitemap  Kontakt 





 


TZI

---------------
 
 
Home
Thema:Klonerkennung mit Suffix-Arrays
Diplomand/in: Daniel Hofmann

Zusammenfassung:

Ein großes Problem für viele globale Code-Analysen ist die Größe der Projekte, auf die sie in der Praxis angewendet werden. Die auf der Grundlage von idealisierten Rechnern (Turingmaschine) entworfenen Algorithmen und Datenstrukturen stoßen bei der Analyse von Projekten mit Millionen von Zeilen an Quellcode schnell an die Grenzen der Rechenkapazität und des zur Verfügung stehenden schnellen Speichers (Arbeitsspeicher). Für die Klonerkennung in Bauhaus wird eine Datenstruktur namens Suffix-Baum eingesetzt, die extrem viel Laufzeit auf Kosten von erhöhtem Speicherverbrauch einspart. In dieser Diplomarbeit soll die dem Klonerkenner von Bauhaus zugrundeliegende Datenstruktur Suffix-Baum durch die ebenso mächtige Datenstruktur Suffix-Array ersetzt werden, die laut Literatur dieselben positiven Eigenschaften mit sich bringt, aber weniger Speicher benötigt.

Im einzelnen sollen hierfür bestehende Varianten der Suffix-Arrays verglichen und auf deren Eignung für die Klonerkennung hin überprüft werden. Anschließend soll die Datenstruktur für den gewählten Algorithmus möglichst speichersparend für Bauhaus entworfen und mit Routinen für den Aufbau der Datenstruktur und das Auslesen und die Übergabe der Informationen an den Klonerkenner implementiert werden. Eine Schwierigkeit der Aufgabe liegt dabei darin, dass der Aufbau der Datenstruktur in Linearzeit erfolgen soll, wie es auch schon beim bestehenden Algorithmus der Fall ist. Anschließend soll die Implementierung anhand großer Eingabeprogramme mit den bestehenden verglichen werden, um die Richtigkeit der Arbeit zu prüfen, sowie die Unterschiede in Laufzeit- und vor allem Speicherverbrauch zu sehen.



zurück  






Arbeitsgruppe

Forschung

Lehre

Publikationen

Service

Kontakt

 

---------
BEDIENUNG
---------


SEITENINHALT DRUCKEN

LESEZEICHEN SETZEN

ENGLISH VERSION  






  SEITENANFANG
Hier geht es zur Homepage des Fachbereiches 03 der Universität Bremen Hier geht es zur Homepage der Informatik des Fachbereiches 03 der Universität Bremen Hier geht es zur Homepage der Universität Bremen