International Conference on Computer and Knowledge Engineering

Home / 13th International Conference on Computer and Knowledge Engineering

Lempel-Ziv-based Hyper-Heuristic Solution for Longest Common Subsequence Problem

Authors :

Mahdi Nasrollahi¹ Reza Shami Tanha² Mohsen Hooshmand³

1- Graduate student 2- Graduate student 3- Assistant Professor

Keywords :

Longest Common Subsequence،Lempel-Ziv Complexity،Hyepr-Heuristic

Abstract :

The longest common subsequence of a given set of strings is a string that its characters are common among all the strings with two properties of being ordered but not consecutive. The general form of LCS problem belongs to the NP-hard problems, therefore, finding the exact LCS cannot be done in a reasonable time. Thus, heuristic methods have been proposed to find the best possible LCS among a set of given strings. However, now it is clear that each heuristic can be useful for a specific type of set. Some algorithms are useful for highly correlated strings and others are useful for less-correlated sets. Therefore, there is no single algorithm for any type of the set. In this work we introduce a hyper-heuristic that computes the correlation among a given set and based on the similarity measure, it assigns the given set to the proper heuristic. To do a correlation measure, it uses the concepts of the Lempel-Ziv complexity and the longest common substring. The results show that the proposed hyper-heuristic outperforms the state-of-the-art heuristics and hyper-heuristics.