Unit:
Τομέας Υπολογιστικών Συστημάτων και ΕφαρμογώνLibrary of the School of Science
Author:
Πανταζή Δέσποινα Αθανασία
Supervisors info:
Γιώργος Γιαννακόπουλος, Παναγιώτης Σταματόπουλος
Original Title:
N-gram graph decompression
Translated title:
Αποσυμπίεση γράφων ν-γραμμάτων
Summary:
The current thesis examines the information represented by an n-gram graph. To
achieve
this task, we searched for all the strings that can be compressed to the same
n-gram graph. In
order to find these strings, we defined the n-gram graph decompression problem.
In addition,
we defined the constraint satisfaction problem formulation of the decompression
problem, to
optimize the latter, and we applied a set of search methods to solve it. We
also designed two variable ordering heuristics to improve our time
measurements. Finally, we conducted a set of experiments on certain applied
search methods to retrieve the initial text from the n-gram graph. We compared
the findings from our experiments and we concluded that the best results for
short-length texts were achieved when Local Search was performed. For
longer-length strings, the weighted degree heuristic was the one that offered
the best results.
Keywords:
n-gram graph, decompression, local search, constraint satisfaction problem, heuristics
Number of index pages:
9, 10, 11
