fork download
copy 
  1. # Demo by Theo Varvadoukas, s1265135
  2.  
  3. '''
  4. Description
  5. ------------
  6. Implementation of the Sardinas-Patterson algorithm. 
  7. This algorithm is used to determine in polynomial time whether 
  8. a given variable-length code is uniquely decodable.
  9.  
  10. http://e...content-available-to-author-only...a.org/wiki/Sardinas-Patterson_algorithm
  11.  
  12. Input
  13. -----
  14. The core function is `uniqdecod`. It accepts a set of 
  15. codewords and each codeword must be a string. 
  16. E.g. 
  17. ExampleUnique = set(['0', '10', '110', '111'])
  18. print uniqdecod(ExampleUnique)
  19.  
  20. Output
  21. -------
  22. True in case it is uniquely decodable or 
  23. False otherwise.
  24.  
  25. Further notes
  26. --------------
  27. For a complete example of use check the main() function. 
  28. '''
  29.  
  30. def removeprefix(prefix, S):
  31.     ''' Remove prefix from S.'''
  32.     return S[len(prefix):]
  33.  
  34. def findprefix(prefix, L):
  35.     ''' Return the dangling suffixes of each matching string.'''
  36.     dangling = []
  37.     for l in L:
  38.         if l.startswith(prefix):
  39.             dangling.append(removeprefix(prefix, l))
  40.     return set(dangling)
  41.  
  42. def crossprefix(L1, L2):
  43.     ''' Return the dangling suffixes between 2 lists. '''
  44.     L1L2 = set()
  45.     for l1 in L1:
  46.         L1L2 |= findprefix(l1, L2)
  47.  
  48.     L2L1 = set()
  49.     for l2 in L2:
  50.         L2L1 |= findprefix(l2, L1)
  51.     return L1L2 | L2L1
  52.  
  53. def uniqdecod(codewords):
  54.     # Only for the first iteration.
  55.     # Find the dangling suffixes between the first 
  56.     # set and the codeword.
  57.     C = {}
  58.     C[0] = set()
  59.     for c in codewords:
  60.         C[0] |= findprefix(c, codewords - set([c]))                
  61.  
  62.     i = 1
  63.     while True:
  64.         C[i] = crossprefix(C[i-1],codewords)
  65.         #print i, C[i] # print each set if you wish.
  66.         if '' in C[i]:
  67.             return False
  68.  
  69.         # Check if C[i] is equal with any other previous set.
  70.         # If yes, the code is uniquely decodable.
  71.         for j in range(0,i):
  72.             if C[j] == C[i]:
  73.                 return True
  74.         i = i + 1
  75.  
  76. def main():
  77.     # ----------------
  78.     # Examples of use
  79.     # ----------------    
  80.     ExampleNonUnique = set(['01', '01111', '111110'])
  81.     ExampleUnique = set(['0', '10', '110', '111'])
  82.  
  83.     mycode = ExampleNonUnique
  84.     decodable = uniqdecod(mycode)
  85.     if decodable:
  86.         print("Wow congratulations! The code IS decodable!")
  87.     else:
  88.         print("Damn.. the code is NOT decodable!")
  89.  
  90. if __name__ == '__main__':
  91.     main()# your code goes here
Success #stdin #stdout 0.01s 7196KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Wow congratulations! The code IS decodable!
https://ideone.com/uQpcMw
language:
Python (cpython 2.7.16)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!