Sardinas-Patterson算法
Sardinas-Patterson算法
提问于 2020-04-30 07:35:41
Introduction
基本思想
算法确定(在多项式时间内)，代码是否唯一可解码。
示例
代码1不是唯一可解码的，因为"100“可能是"baa”或"bc“。
现在，让我们将该算法应用于代码2：
- 它将被检查，一个码字是否是另一个码字的前缀。如果是这样，则将后缀添加到S(如果S中还不存在后缀)。因此，由于‘01’是‘011’的前缀，在这个步骤之后，‘1’被添加到S中，所以字符串‘1’、‘11’和‘111’现在在S中。
- 在这个步骤中，将检查S中的元素是否是代码字的前缀(反之亦然)。如果是这种情况，则将后缀添加到S，然后步骤2再次启动(递归调用)。它也将被检查，一个完整的代码字是否在S中，如果是这样的话，该方法将返回代码不是唯一可解码的。在代码2的情况下，在此步骤中S将不添加其他后缀。
- 如果步骤2成功终止，则代码是唯一可解码的。
算法
的
终止
算法总是终止的，因为C是一组有限的码字，因此只有有限数量的后缀将添加到S.1中。
这是很重要的一点:你必须注意，只有S才会添加后缀，如果这些后缀还不在S里的话。否则，将无法保证该算法将终止。
我的实现
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;
}
}测试
在运行了一些单元测试之后，我认为该算法是完全正确的：
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);
}
}问题
如何改进这些代码？这个实现的主要问题之一是它的时间复杂度很差。这又如何改善呢？
如有任何建议，我将不胜感激。
1维基百科撰稿人。(2018年3月6日)撒丁岛-帕特森算法。在维基百科，免费百科全书。从https://en.wikipedia.org/w/index.php?title=Sardinas%E2%80%93Patterson_algorithm&oldid=829124957检索到的2020年4月30日
回答 1
Code Review用户
回答已采纳
发布于 2020-05-01 13:31:48
您已经说过，维基百科中描述的Sardinas算法是基于使用集合作为代码字的，并且对每个集合操作都有一个解释。因此，我将对所涉及的每个操作使用java Set类。我从第一个定义的操作符开始：
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的函数来实现：
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;
}在您必须定义元素S继承之后，以这种方式定义S1：
这可以用下面描述的一个称为firstSet的函数来表示：
private static Set<String> firstSet(Set<String> c) {
Set<String> set = inverseNMulD(c, c);
set.remove(""); <-- I'm removing the empty string
return set;
}在您需要定义如何从ith元素开始计算继承的i+1th元素之后：
这可以用下面描述的一个称为successiveSet的函数来表示：
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();
}现在解释布尔方法sardinasPatterson来检查给定的可变长度代码是否唯一可解码。该算法以i的递增顺序计算集合Si，一旦其中一个Si包含C中的一个字或一个空字，该算法就会终止，并回答给定代码不可唯一解码的问题。否则，一旦集合Si等于以前遇到的具有j< i的集合Sj，则该算法原则上将进入一个无穷无尽的循环。它没有无休止地继续，而是回答给定的代码是唯一可解码的。
这可以通过下面描述的sardinasPatterson函数来实现：
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.
}在这个类的代码下面：
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;
}
}正如您在第一个视图中所看到的，代码似乎比您的代码更复杂，但是使用Set，有关字符串的所有控件及其唯一性都会自动得到解决，并且它更严格地与算法的文档联系在一起。
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/241477
复制相关文章
相似问题
腾讯云开发者
