title: How do i find variable length Huffman codes in a string for a best fit?
body: <p>I have a string, i want to find the most variable length characters up to a length to make better huffman codes: </p>
  
  <p>For example, the string </p>
  
  <pre><code>"++----++--++--+-++++++-+-+-----++-+---+-+---+-++--" 
  </code></pre>
  
  <p>from which i manually created the following Huffman to symbol to frequency string:</p>
  
  <pre><code>In [1665]: symb2freq                                                                                                                                                                                       
  Out[1665]: {'++--': 4, '-+-+-': 2, '--': 1, '+-++++++': 1, '----++-+--': 1, '--+-': 1}
  </code></pre>
  
  <p>This allowed me to have the Huffman binary string of 110011111000011010110011 to represent:</p>
  
  <pre><code>'++----++--++--+-++++++-+-+-----++-+---+-+---+-++--'
  </code></pre>
  
  <p>which is half the size and which is better than fixed length symb2frequencies. My question is, it there a regex, or itertools, or method of programming to create symb2frequencies of multiple lengths, with a largest length. In my case the largest length is 11. The shortest length doesn't matter, but the goal is to get the best frequencies possible to reduce the size of the huffman code to represent the tree. If i group by a set size, i can 't get a short Huffman binary string to represent the best code set.</p>
  
  <p>So my question is how do i programmatically, using regex or itertools, or any other method to convert:</p>
  
  <pre><code>"++----++--++--+-++++++-+-+-----++-+---+-+---+-++--"
  </code></pre>
  
  <p>to:</p>
  
  <pre><code>In [1665]: symb2freq                                                                                                                                                                                       
  Out[1665]: {'++--': 4, '-+-+-': 2, '--': 1, '+-++++++': 1, '----++-+--': 1, '--+-': 1}
  </code></pre>
  
  <p>which i built manually.</p>
  
  <p>I think this is a hard problem, so thanks in advance for any advice on how to tackle this issue.</p>
  
  <p>I wrote this code to show that you can use variable length codes to decode a huffman code to the pattern shown, which i use to recreate the number 1009732533765201 in half the size. I created the sym2freq manually and need help on ideas on how to create it programmatically so i can achieve better compression than set grouping sizes. I have a program that creates a mathematical pattern to recreate a number, and i'm looking to create variable length codes to best represent those patterns which are in the format of + and - 's</p>
  
  <pre><code># Incorporated a better method of rebuilding the string from RoyM
  # Uncompresses the number: 1009732533765201
  # which has the binary:
  # 0b11100101100101100010101100111111100100010001010001
  # Our compressed binary is:
  # 110011111000011010110011
  # We compress a variable length pattern that is decoded 
  # to try to achieve nearly as good compression (maybe better in this case )and to more importantly 
  # to compare compression as this is a different approach
  # to that of binary compression of Huffman using XOR Patterns
  # S is a representation of XOR math that is required to rebuild the original number
  # so we don't compress the number itself, we compress the XOR math to rebuild the number
  # instead
  
  s={'11': '++--', '01': '-+-+-', '000': '+-++++++', '001': '--', '100': '--+-', '101': '----++-+--'}
  compressed_binary='110011111000011010110011'
  
  def decodepattern(pattern, j=1):
     x=2
     for c in range(len(pattern)):
       if pattern[c]=='+' or pattern[c]=='1':
         j^=x
       else:
         j^=-x
       x&lt;&lt;=1
     return abs(j)
  
  
  i = 0
  j = 0
  uncompressed_string = ''
  while(j&lt;len(compressed_binary)):
      if compressed_binary[i:j] in s:
          uncompressed_string += s[compressed_binary[i:j]]
          i = j
      else:
          j += 1
  uncompressed_string += s[compressed_binary[i:j]]
  answer = decodepattern(uncompressed_string)
  
  print("Bin length of 1009732533765201 is 50 which is the same as the pattern length")
  print("Original Bin of 1009732533765201 is: ")
  print(bin(1009732533765201)[2:])
  print("Original Pattern:")
  print(uncompressed_string)
  print("Compressed to: ", bin(13600435)[2:])
  print("110011111000011010110011 uncompressed to the original string pattern of : ")
  print(uncompressed_string)
  print("Which then i was able to recreate the original integer of: ")
  print(decodepattern(uncompressed_string))
  </code></pre>
  
  <p>Output of program is:</p>
  
  <pre><code>Bin length of 1009732533765201 is 50 which is the same as the pattern length
  Original Bin of 1009732533765201 is: 
  11100101100101100010101100111111100100010001010001
  Original Pattern:
  b'++----++--++--+-++++++-+-+-----++-+---+-+---+-++--'
  Compressed to:  110011111000011010110011
  110011111000011010110011 uncompressed to the original string pattern of : 
  b'++----++--++--+-++++++-+-+-----++-+---+-+---+-++--'
  Which then i was able to recreate the original integer of: 
  1009732533765201
  </code></pre>
  
  <p>So you can see i can use variable length codes to decompress a number, i just don't know how to create variable length codes (up to a certain length) without doing it manually.</p>
  
  <p>Expected result is some sort of regex, or itertools method or any other method to take the string:</p>
  
  <pre><code>"++----++--++--+-++++++-+-+-----++-+---+-+---+-++--"
  </code></pre>
  
  <p>and create a symb2freq like this ( which i did manually ):</p>
  
  <pre><code>In [1665]: symb2freq                                                                                                                                                                                       
  Out[1665]: {'++--': 4, '-+-+-': 2, '--': 1, '+-++++++': 1, '----++-+--': 1, '--+-': 1}
  </code></pre>