5
\$\begingroup\$

Introduction

Basic Idea

The Sardinas-Patterson algorithm determines (in polynomial time), whether a code is uniquely decodeable or not.

Example

enter image description here

Code 1 is not uniquely decodeable, because "100" could be "baa" or "bc".

Now let's apply the algorithm to code 2:

  1. It will be checked, whether a codeword is another codeword's prefix. If so, the suffix is added to S (if the suffix does not yet exist in S). So since ’01’ is a prefix of ’011’, ’1’ is added to S. After this step, the strings ’1’, ’11’ and ’111’ are now in S.
  2. In this step it will be checked, whether an element in S is a prefix of a codeword (or vice versa). If this is the case, the suffix is added to S and step 2 starts again (recursive call). It will also be checked, whether a full codeword is in S. If this is the case, the method will return that the code is not uniquely decodeable. In case of Code 2, there will no other suffixes be added to S in this step.
  3. If step 2 terminates successfully, the code is uniquely decodeable.

Termination of the algorithm

The algorithm will always terminate, because C is a finite set of codewords, and therefore there only exits a finite number of suffixes that will be added to S.[1]

That's an important point: You have to take care that suffixes will be only added to S, if they aren't in S yet. Otherwise, it would be not guaranteed that the algorithm will terminate.


My implementation

import java.util.Arrays;

public class SardinasPatterson {

    //C = List of codewords

    public boolean sardinasPatterson(String[] C) {

        //Creating empty array S with length 1+2+...+n

        int sLength = ((C.length)*(C.length + 1)) / 2;
        String[] S = new String[sLength];
        return sardinasPatterson(C, S);
    }

    private boolean sardinasPatterson(String[] C, String[] S) {

        //saves first empty place in S

        int pivot = 0;          
        int length = C.length;

        //if codeword ist prefix of another codeword, 
        //the suffix is saved in S

        for(int i = 0; i < length; i++) {
            for(int j = 0; j < length; j++) {
                if(i != j && C[i].startsWith(C[j])) {
                    String cache = getDanglingSuffix(C[j], C[i]);
                    if(!Arrays.stream(S).anyMatch(cache::equals)) {
                        S[pivot] = getDanglingSuffix(C[j], C[i]);
                        pivot++;
                    }   
                }
            }
        }
        boolean unique = uniquelyDecodeable(C, S, pivot);
        return unique;
    }

    private boolean uniquelyDecodeable(String[] C, String[] S, int pivot) {
        int cLength = C.length;

        for(int i = 0; i < pivot; i++) {
            for(int j = 0; j < cLength; j++) {

                //If Codeword is in S -> Code not uniquely decodeable

                if(S[i].equals(C[j])) {
                    return false;
                }

                //If an element in S is prefix of a codeword,
                //the suffix is saved in S

                else if(C[j].startsWith(S[i])) {
                    String cache = getDanglingSuffix(S[i], C[j]);
                    if(!Arrays.stream(S).anyMatch(cache::equals)) {
                        S[pivot] = cache;
                        pivot++;
                    }
                }

                //If codeword is prefix of an element in S, the
                //suffix is saved in S

                else if(S[i].startsWith(C[j])) {
                    String cache = getDanglingSuffix(C[j], S[i]);
                    if(!Arrays.stream(S).anyMatch(cache::equals)) {
                        S[pivot] = cache;
                        pivot++;
                    }

                }
            }
        }
        return true;
    }

    //getting suffix

    private String getDanglingSuffix(String prefix, String str) {
        String suffix = "";
        for(int i = prefix.length(); i < str.length(); i++) {
            suffix += str.charAt(i);
        }
        return suffix;
    }
}

Tests

After running some unit-tests, I think the algorithm is working completely correctly:

import org.junit.Test;
import org.junit.Assert;

public class Tests {

    @Test
    public void firstTest() {
        String[] C = {"011", "111", "0", "01"};
        SardinasPatterson sp = new SardinasPatterson();
        boolean test = sp.sardinasPatterson(C);
        Assert.assertEquals(test, true);
    }

    @Test
    public void secondTest() {
        String[] C = {"0", "01", "11"};
        SardinasPatterson sp = new SardinasPatterson();
        boolean test = sp.sardinasPatterson(C);
        Assert.assertEquals(test, true);    
    }

    @Test
    public void thirdTest() {
        String[] C = {"0", "01", "10"};
        SardinasPatterson sp = new SardinasPatterson();
        boolean test = sp.sardinasPatterson(C);
        Assert.assertEquals(test, false);
    }

    @Test
    public void fourthTest() {
        String[] C = {"1", "011", "01110", "1110", "10011"};
        SardinasPatterson sp = new SardinasPatterson();
        boolean test = sp.sardinasPatterson(C);
        Assert.assertEquals(test, false);
    }

    @Test
    public void fifthTest() {
        String[] C = {"0", "1", "000000"};
        SardinasPatterson sp = new SardinasPatterson();
        boolean test = sp.sardinasPatterson(C);
        Assert.assertEquals(test, false);
    }

    @Test
    public void sixthTest() {
        String[] C = {"00", "11", "0101", "111", "1010", "100100", "0110"} ;
        SardinasPatterson sp = new SardinasPatterson();
        boolean test = sp.sardinasPatterson(C);
        Assert.assertEquals(test, false);
    }

    @Test
    public void seventhTest() {
        String[] C = {"0", "01", "0111", "01111", "11110"} ;
        SardinasPatterson sp = new SardinasPatterson();
        boolean test = sp.sardinasPatterson(C);
        Assert.assertEquals(test, false);
    }

    @Test
    public void eigthTest() {
        String[] C = {"0", "01", "011", "0111"} ;
        SardinasPatterson sp = new SardinasPatterson();
        boolean test = sp.sardinasPatterson(C);
        Assert.assertEquals(test, true);
    }

    @Test
    public void ninthTest() {
        String[] C = {"00", "00", "11"} ;
        SardinasPatterson sp = new SardinasPatterson();
        boolean test = sp.sardinasPatterson(C);
        Assert.assertEquals(test, false);
    }

    @Test
    public void tenthTest() {
        String[] C = {"0", "10", "11"} ;
        SardinasPatterson sp = new SardinasPatterson();
        boolean test = sp.sardinasPatterson(C);
        Assert.assertEquals(test, true);
    }

    @Test
    public void eleventhTest() {
        String[] C = {"0", "1", "00", "11"} ;
        SardinasPatterson sp = new SardinasPatterson();
        boolean test = sp.sardinasPatterson(C);
        Assert.assertEquals(test, false);
    }

    @Test
    public void twelfhTest() {
        String[] C = {"0", "01", "011", "0111"} ;
        SardinasPatterson sp = new SardinasPatterson();
        boolean test = sp.sardinasPatterson(C);
        Assert.assertEquals(test, true);
    }

    @Test
    public void thirteenthTest() {
        String[] C = {"00", "11", "010", "0100"} ;
        SardinasPatterson sp = new SardinasPatterson();
        boolean test = sp.sardinasPatterson(C);
        Assert.assertEquals(test, true);
    }

}

Question

How can this code be improved? One of the main problems with this implementation is that it has a pretty bad time-complexity. How can this be improved?

I would appreciate any suggestions.


[1] Wikipedia contributors. (2018, March 6). Sardinas–Patterson algorithm. In Wikipedia, The Free Encyclopedia. Retrieved April 30, 2020, from https://en.wikipedia.org/w/index.php?title=Sardinas%E2%80%93Patterson_algorithm&oldid=829124957

\$\endgroup\$
2
\$\begingroup\$

The Sardinas-Patterson algorithm described in wikipedia as you already said is based on the use of sets for codewords and there is an explanation for every set operation. Consequently I will use the java Set class for every operation involved. I start from the first defined operator:

In general, for two sets of strings D and N, the (left) quotient is defined as the residual words obtained from D by removing some prefix in N.

inverseNMulD

This can be implemented with a function I called inverseNMulD below described:

private static Set<String> inverseNMulD(Set<String> n, Set<String> d) {
    Set<String> set = new HashSet<>();
    for (String s1 : d) {
        for (String prefix : n) {
            if (s1.startsWith(prefix)) {
                set.add(s1.substring(prefix.length()));
            }
        }
    }
    return set; 
}

After you will have to define a element S succession where S1 is defined in this way:

Initial set

This can be expressed with a function I called firstSet below described:

private static Set<String> firstSet(Set<String> c) {
    Set<String> set = inverseNMulD(c, c);
    set.remove(""); <-- I'm removing the empty string
    return set;
}

After you have will to define how to calculate the i+1th element of your succession starting from the ith element:

Union

This can be expressed with a function I called successiveSet below described:

private static Set<String> successiveSet(Set<String> c, Set<String> s) {
    Set<String> set = inverseNMulD(c, s);
    set.addAll(inverseNMulD(s, c));
    return set;
}

After I defined a helper function to check if the intersection of two sets is empty:

private boolean isEmptyIntersection(Set<String> set, Set<String> codewordsSet) {
    Set<String> intersection = new HashSet<>(set);
    intersection.retainAll(codewordsSet);
    return intersection.isEmpty();
}

Now the explanation of the boolean method sardinasPatterson to check whether a given variable-length code is uniquely decodable. The algorithm computes the sets Si in increasing order of i. As soon as one of the Si contains a word from C or the empty word, then the algorithm terminates and answers that the given code is not uniquely decodable. Otherwise, once a set Si equals a previously encountered set Sj with j < i, then the algorithm would enter in principle an endless loop. Instead of continuing endlessly, it answers that the given code is uniquely decodable.

This can be implemented with the sardinasPatterson function below described:

public boolean sardinasPatterson(String[] codewords) {
    Set<String> codewordsSet = Arrays.stream(codewords).collect(Collectors.toSet());
    if (codewordsSet.size() != codewords.length) { return false; }
    Set<String> currentSet = firstSet(codewordsSet);
    List<Set<String>> list = new ArrayList<Set<String>>();
    list.add(currentSet);
    while (!currentSet.contains("") && isEmptyIntersection(currentSet, codewordsSet)) {
        currentSet = successiveSet(codewordsSet, currentSet);
        //one set previously found is equal to current set : success!
        if (list.contains(currentSet)) { return true; } 
        list.add(currentSet);
    }
    return false; //<-- failure: the code is not uniquely decodable. 
}

Below the code of the class:

public class SardinasPatterson {

    private static Set<String> inverseNMulD(Set<String> n, Set<String> d) {
        Set<String> set = new HashSet<>();
        for (String s1 : d) {
            for (String prefix : n) {
                if (s1.startsWith(prefix)) {
                    set.add(s1.substring(prefix.length()));
                }
            }
        }
        return set; 
    }
    
    private static Set<String> firstSet(Set<String> c) {
        Set<String> set = inverseNMulD(c, c);
        set.remove("");
        return set;
    }
    
    private static Set<String> successiveSet(Set<String> c, Set<String> s) {
        Set<String> set = inverseNMulD(c, s);
        set.addAll(inverseNMulD(s, c));
        return set;
    }
    
    private boolean isEmptyIntersection(Set<String> set, Set<String> codewordsSet) {
        Set<String> intersection = new HashSet<>(set);
        intersection.retainAll(codewordsSet);
        return intersection.isEmpty();
    }
    
    public boolean sardinasPatterson(String[] codewords) {
        Set<String> codewordsSet = Arrays.stream(codewords).collect(Collectors.toSet());
        if (codewordsSet.size() != codewords.length) { return false; }
        Set<String> currentSet = firstSet(codewordsSet);
        List<Set<String>> list = new ArrayList<Set<String>>();
        list.add(currentSet);
        while (!currentSet.contains("") && isEmptyIntersection(currentSet, codewordsSet)) {
            currentSet = successiveSet(codewordsSet, currentSet);
            if (list.contains(currentSet)) { return true; }
            list.add(currentSet);
        }
        return false;
    }
}

As you can see at a first view code seems more complicated than your's but with use of Set all the controls about strings and their unicity are automatically solved and it is more strictly tied to the documentation of the algorithm.

\$\endgroup\$
2
  • \$\begingroup\$ First of all, thank you for your answer! Your implementation is really amazing. Could you tell me, if you found any mistakes in my implementation? \$\endgroup\$ – Philipp Wilhelm May 1 '20 at 14:17
  • 1
    \$\begingroup\$ @chrysaetos99 You are welcome, I haven't found mistakes in your implementation of the algorithm, the only problem is that without use of Set class you had been obliged to handle the Set work by yourself. Just one thing, your function getDanglingSuffix can return str.substring(prefix.length(), str.length()). \$\endgroup\$ – dariosicily May 1 '20 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.