Все самые длинные общие подпоследовательности - PullRequest
Новая
       10

Все самые длинные общие подпоследовательности

1 голос
/ 10 сентября 2011

[ПРИМЕЧАНИЕ: я искал заранее и не мог найти совет по решению проблемы LCS для всех подпоследовательностей.]

У меня возникли проблемы при кодировании решения проблемы "самой длинной общей подпоследовательности", когда я возвращаю все самые длинные общие подпоследовательности для двух входных строк. Я посмотрел на страницу Википедии и попытался реализовать там псевдокод, но столкнулся с проблемой с моим методом «backtrackAll». Я полагаю, что я правильно вычисляю матрицу LCS ниже, но мой метод "backtrackAll" возвращает пустой набор. Любые советы о том, что я делаю не так? 

public static void main (String[] args) {
    String s1 = "AGCAT";
    String s2 = "GAC";
    int[][] matrix = computeMatrix(s1,s2);
    HashSet<String> set = backtrackAll(matrix,s1,s2,s1.length(),s2.length());
    //more stuff would go here...
}

private static int[][] computeMatrix(String s1, String s2) {
    int[][] C = new int[s1.length()+1][s2.length()+1];
    for (int i = 1; i < s1.length()+1; i++) {
        for (int j = 1; j < s2.length()+1; j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                C[i][j] = C[i-1][j-1] + 1;
            } else {
                C[i][j] = Math.max(C[i][j-1], C[i-1][j]);
            }
        }
    }
    return C;
}

private static HashSet<String> backtrackAll(int[][] C, String s1, String s2, int i, int j) {
    if (i == 0 || j == 0) {
        return new HashSet<String>();
    } else if (s1.charAt(i-1) == s2.charAt(j-1)) {
        HashSet<String> R = backtrackAll(C,s1,s2,i-1,j-1);
        HashSet<String> new_set = new HashSet<String>();
        for (String Z: R) {
            new_set.add(Z + s1.charAt(i-1));
        }
        return new_set;
    } else {
        HashSet<String> R = new HashSet<String>();
        if (C[i][j-1] >= C[i-1][j]) {
            R = backtrackAll(C, s1, s2, i, j-1);
        } 
        if (C[i-1][j] >= C[i][j-1]) {
            R.addAll(backtrackAll(C,s1,s2,i-1,j));
        }
        return R;
    }
}

Ответы [ 4 ]

2 голосов
/ 25 января 2012

Я немного его изменил.Теперь это работает.Также следует учитывать, когда возвращается ноль HashSet, и в этом случае необходимо добавить последний соответствующий символ. 

private static HashSet<String> backtrackAll(int[][] C, String s1, String s2, int i, int j) {
    // System.out.println(i+" " + j);
    if (i == 0 || j == 0) {
        // System.out.println("0t");
        return new HashSet<String>();
    } else if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
        // System.out.println("2t");
        HashSet<String> R = backtrackAll(C, s1, s2, i - 1, j - 1);
        HashSet<String> new_set = new HashSet<String>();

        for (String Z : R) {
            // System.out.println("1t");
            new_set.add(Z + s1.charAt(i - 1));
        }
        new_set.add("" + s1.charAt(i - 1));
        return new_set;
    } else {
        // System.out.println("3t");
        HashSet<String> R = new HashSet<String>();
        if (C[i][j - 1] >= C[i - 1][j]) {
            R = backtrackAll(C, s1, s2, i, j - 1);
        }
        if (C[i - 1][j] >= C[i][j - 1]) {
            R.addAll(backtrackAll(C, s1, s2, i - 1, j));
        }
        return R;
    }
}
1 голос
/ 09 апреля 2013

Второй ответ печатает все, но не только самое длинное, мое правильно. 

private static HashSet<String> backtrackAll(int[][] C, String s1, String s2, int i, int j) {
    if (i == 0 || j == 0) {
        HashSet<String> set = new HashSet<String>();
        set.add("");
        return set;

    } else if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
        HashSet<String> R = backtrackAll(C, s1, s2, i - 1, j - 1);
        HashSet<String> new_set = new HashSet<String>();

        for (String Z : R) {
            new_set.add(Z + s1.charAt(i - 1));
        }
        return new_set;
    } else {
        HashSet<String> R = new HashSet<String>();
        if (C[i][j - 1] >= C[i - 1][j]) {
            R = backtrackAll(C, s1, s2, i, j - 1);
        }
        if (C[i - 1][j] >= C[i][j - 1]) {
            R.addAll(backtrackAll(C, s1, s2, i - 1, j));
        }
        return R;
    }
}
1 голос
/ 10 сентября 2011

Поскольку это «домашнее задание», вот пара советов.

  1. Убедитесь, что вы понимаете алгоритм, который вы кодировали. Это, пожалуй, самый важный шаг в выяснении того, что не так с вашей реализацией.

  2. Попробуйте использовать отладчик, чтобы выяснить, что происходит. Сравните то, что, по вашему мнению, должно происходить с тем, что происходит на самом деле.

  3. Попробуйте добавить в код некоторые операторы assert, чтобы проверить предварительные условия, постусловия и инварианты, которые, как вы считаете, должны выполняться. (Запуск с java -ea ...)

  4. Придерживайтесь нормальных соглашений об именах Java. Имена переменных начинаются со строчной буквы. Без подчеркиваний в именах переменных.

0 голосов
/ 30 июля 2014

Вот две версии в C #, чтобы добраться до самых длинных общих подпоследовательностей (вы можете обратиться к: http://codingworkout.blogspot.com/2014/07/longest-common-subsequence.html)

  1. Возврат на основе кэшированной таблицы, которая содержит длину самых длинных общих подпоследовательностей

  2. Во время кэширования, вместо кэширования, сборы самого lcs.

Версия 1 (возврат на основе длины lcsпрефиксы): 

string[] GetLongestCommonSubsequences(string A, string B, int aIndex, int bIndex, 
        int[][] DP_LCS_AllPrefixes_Cache)
    {
        if(DP_LCS_AllPrefixes_Cache[aIndex][bIndex] == 0)
        {
            return null;
        }
        if(A[aIndex-1] == B[bIndex -1])
        {
            var r = this.GetLongestCommonSubsequences(A, B, aIndex - 1, bIndex - 1,
                DP_LCS_AllPrefixes_Cache);
            if(r == null)
            {
                return new string[] { A[aIndex - 1].ToString() };
            }
            return r.Select(s => s + A[aIndex - 1].ToString()).ToArray();
        }
        int lcs_up_direction = DP_LCS_AllPrefixes_Cache[aIndex - 1][bIndex];
        int lcs_left_direction = DP_LCS_AllPrefixes_Cache[aIndex][bIndex-1];
        if(lcs_up_direction == lcs_left_direction)
        {
            string[] lcs_up = this.GetLongestCommonSubsequences(A, B, aIndex - 1, bIndex,
                DP_LCS_AllPrefixes_Cache);
            string[] lcs_left = this.GetLongestCommonSubsequences(A, B, aIndex, bIndex-1,
                DP_LCS_AllPrefixes_Cache);
            return lcs_up.Union(lcs_left).ToArray();
        }
        if(lcs_up_direction > lcs_left_direction)
        {
            return this.GetLongestCommonSubsequences(A, B, aIndex - 1, bIndex, 
                DP_LCS_AllPrefixes_Cache);
        }
        return this.GetLongestCommonSubsequences(A, B, aIndex, bIndex - 1, DP_LCS_AllPrefixes_Cache);
    }

**, где вызывающая рекурсивная функция - ** 

string[] GetLongestCommonSubsequences(string A, string B, int[][] DP_LCS_AllPrefixes_Cache)
        {
            var r = this.GetLongestCommonSubsequences(A, B, A.Length, B.Length,
                DP_LCS_AllPrefixes_Cache);
            return r;
        }

версия 2 - где кеш захватывает lcs всехпрефиксы 

class LCS_Prefix
        {
            public int Length = 0;
            public string[] Subsequences = null;
        }
        LCS_Prefix[][] LCS_OfAllPrefixes_Subsequences(string A, string B)
        {
            A.ThrowIfNullOrWhiteSpace("a");
            B.ThrowIfNullOrWhiteSpace("b");
            LCS_Prefix[][] LCS_DP_OfAllPrefixes_Subsequences_Cache = new LCS_Prefix[A.Length + 1][];
            for (int i = 0; i < LCS_DP_OfAllPrefixes_Subsequences_Cache.Length; i++)
            {
                LCS_DP_OfAllPrefixes_Subsequences_Cache[i] = new LCS_Prefix[B.Length + 1];
                for(int j = 0; j< LCS_DP_OfAllPrefixes_Subsequences_Cache[i].Length; j++)
                {
                    LCS_DP_OfAllPrefixes_Subsequences_Cache[i][j] = new LCS_Prefix();
                }
            }
            for (int rowIndexOfCache = 1; rowIndexOfCache <= A.Length; rowIndexOfCache++)
            {
                for (int columnIndexOfCache = 1; columnIndexOfCache <= B.Length; columnIndexOfCache++)
                {
                    //LCS(Ai, Bj) = 0 if i <=0, or j <= 0
                    //              LCS(Ai, Bj) + 1 if Ai == Bj
                    //              Max(LCS(Ai-1, Bj), LCS(Ai, Bj-1))
                    LCS_Prefix lcsPrefix = LCS_DP_OfAllPrefixes_Subsequences_Cache[rowIndexOfCache][columnIndexOfCache];
                    if (A[rowIndexOfCache - 1] == B[columnIndexOfCache - 1])
                    {
                        var lcs_Prefix_Diagnoal = LCS_DP_OfAllPrefixes_Subsequences_Cache[rowIndexOfCache - 1]
                            [columnIndexOfCache - 1];
                        lcsPrefix.Length = lcs_Prefix_Diagnoal.Length + 1;
                        if (lcs_Prefix_Diagnoal.Subsequences == null)
                        {
                            lcsPrefix.Subsequences = new string[] { A[rowIndexOfCache - 1].ToString() };
                        }
                        else
                        {
                            lcsPrefix.Subsequences = lcs_Prefix_Diagnoal.Subsequences
                                .Select(s => s + A[rowIndexOfCache - 1]).ToArray();
                        }
                    }
                    else
                    {
                        LCS_Prefix prefix1_Upward = LCS_DP_OfAllPrefixes_Subsequences_Cache[rowIndexOfCache - 1][columnIndexOfCache];
                        var prefix2_Leftward = LCS_DP_OfAllPrefixes_Subsequences_Cache[rowIndexOfCache][columnIndexOfCache-1];
                        if(prefix1_Upward.Length == prefix2_Leftward.Length)
                        {
                            Assert.IsTrue(prefix1_Upward.Length == prefix2_Leftward.Length);
                            Assert.IsTrue((prefix1_Upward.Subsequences == null &&
                                            prefix2_Leftward.Subsequences == null)
                                        || (prefix1_Upward.Subsequences != null
                                            && prefix2_Leftward.Subsequences != null));
                            if (prefix1_Upward.Subsequences != null)
                            {
                                Assert.IsTrue(prefix1_Upward.Subsequences.All(s1 => prefix2_Leftward.Subsequences.Any(s2 => (s2.Length == s1.Length))));
                            }

                            lcsPrefix.Length = prefix1_Upward.Length;
                            if (prefix1_Upward.Subsequences != null)
                            {
                                lcsPrefix.Subsequences = prefix1_Upward.Subsequences
                                    .Union(prefix2_Leftward.Subsequences).ToArray();
                            }
                            else
                            {
                                Assert.IsNull(prefix2_Leftward.Subsequences);
                            }
                        }
                        else if(prefix1_Upward.Length > prefix2_Leftward.Length)
                        {
                            lcsPrefix.Length = prefix1_Upward.Length;
                            lcsPrefix.Subsequences = prefix1_Upward.Subsequences;
                        }
                        else
                        {
                            lcsPrefix.Length = prefix2_Leftward.Length;
                            lcsPrefix.Subsequences = prefix2_Leftward.Subsequences;
                        }
                    }
                }
            }
            return LCS_DP_OfAllPrefixes_Subsequences_Cache;
        }

Модульные тесты 

[TestMethod]
        public void LCS_Tests()
        {
            string A = "AGCAT", B = "GAC";
            var DP_LCS_AllPrefixes_Cache = this.LCS_OfAllPrefixes_Length(A, B);
            Assert.IsTrue(DP_LCS_AllPrefixes_Cache[A.Length][B.Length] == 2);
            var lcs_sequences = this.GetLongestCommonSubsequences(A, B, DP_LCS_AllPrefixes_Cache);
            Assert.IsNotNull(lcs_sequences);
            Assert.IsTrue(lcs_sequences.Any(s => "AC".Equals(s)));
            Assert.IsTrue(lcs_sequences.Any(s => "GC".Equals(s)));
            Assert.IsTrue(lcs_sequences.Any(s => "GA".Equals(s)));
            var DP_LCS_AllPrefixes_Subsequences_Cache = this.LCS_OfAllPrefixes_Subsequences(A, B);
            Assert.IsTrue(DP_LCS_AllPrefixes_Subsequences_Cache[A.Length][B.Length].Length == 2);
            Assert.IsTrue(DP_LCS_AllPrefixes_Subsequences_Cache[A.Length][B.Length].Subsequences
               .Any(s => "AC".Equals(s)));
            Assert.IsTrue(DP_LCS_AllPrefixes_Subsequences_Cache[A.Length][B.Length].Subsequences
                .Any(s => "GC".Equals(s)));
            Assert.IsTrue(DP_LCS_AllPrefixes_Subsequences_Cache[A.Length][B.Length].Subsequences
                .Any(s => "GA".Equals(s)));
            A = "ABCDGH"; B = "AEDFHR";
            DP_LCS_AllPrefixes_Cache = this.LCS_OfAllPrefixes_Length(A, B);
            Assert.IsTrue(DP_LCS_AllPrefixes_Cache[A.Length][B.Length] == 3);
            lcs_sequences = this.GetLongestCommonSubsequences(A, B, DP_LCS_AllPrefixes_Cache);
            Assert.IsNotNull(lcs_sequences);
            Assert.IsTrue(lcs_sequences.Any(s => "ADH".Equals(s)));
            DP_LCS_AllPrefixes_Subsequences_Cache = this.LCS_OfAllPrefixes_Subsequences(A, B);
            Assert.IsTrue(DP_LCS_AllPrefixes_Subsequences_Cache[A.Length][B.Length].Length == 3);
            Assert.IsTrue(DP_LCS_AllPrefixes_Subsequences_Cache[A.Length][B.Length].Subsequences
                .Any(s => "ADH".Equals(s)));
            A = "AGGTAB"; B = "GXTXAYB";
            DP_LCS_AllPrefixes_Cache = this.LCS_OfAllPrefixes_Length(A, B);
            Assert.IsTrue(DP_LCS_AllPrefixes_Cache[A.Length][B.Length] == 4);
            lcs_sequences = this.GetLongestCommonSubsequences(A, B, DP_LCS_AllPrefixes_Cache);
            Assert.IsNotNull(lcs_sequences);
            Assert.IsTrue(lcs_sequences.Any(s => "GTAB".Equals(s)));
            DP_LCS_AllPrefixes_Subsequences_Cache = this.LCS_OfAllPrefixes_Subsequences(A, B);
            Assert.IsTrue(DP_LCS_AllPrefixes_Subsequences_Cache[A.Length][B.Length].Length == 4);
            Assert.IsTrue(DP_LCS_AllPrefixes_Subsequences_Cache[A.Length][B.Length].Subsequences
                .Any(s => "GTAB".Equals(s)));
        }
...