Is there a good algorithm for finding a permutation which, applied to all the strings in a set, maximises the weight of those with a common fixed length prefix.

Given a set $S=\{(s,w)\}$ of pairs of fixed length bit strings and weights and an integer k find a permutation p of {1..k} and bit string v of length k to maximise

$$ \Sigma \{ w_i | (s_i,w_i)\in S\land s_i[p(1)]=v[1] \land s_i[p(2)]=v[2]\land...s_i[p(k)]=v[k] \} $$

I can think of an obvious greedy algorithm where we

  1. pick the index i and value v which maximises the weights of the strings with $s[i]=v$
  2. delete position i from all strings.
  3. Repeat until we've chosen k bits.

Is it possible to do better?

The problem I'm trying to solve is a compression one where the bits in the data can be reordered and each compressed item can be either the original or the suffix from the original which is concatenated with a common prefix when decompressed.

I need to find a reordering and prefix which maximises the number of items which can use the second form. If p is the permutation and v the prefix

Compression for s:

sp = permute(p, s).
If sp[1..k]=v then      # Does the permuted s have the prefix v
    return sp[k+1..n]   # Compressed case, uses only n-k bits
    return sp           # Uncompressed case, uses all n bits

Decompression for s:

if len(s)=k then 
    su = concat(v,s) # Compressed case, add the prefix.
    su = s  # Uncompressed case
return inverse_permutation(p, su)
  • 1
    $\begingroup$ What does this line mean: "s = len(s)=k ? concat(v,s) : s"? $\endgroup$
    – lox
    Jun 13, 2019 at 19:51
  • $\begingroup$ I mean if the length of s is k then set s to the concatenate of v and s otherwise don't modify it. $\endgroup$ Jun 13, 2019 at 21:10
  • 1
    $\begingroup$ I think you should edit the question so it's clear $\endgroup$
    – lox
    Jun 13, 2019 at 21:12
  • $\begingroup$ Thanks - I've done so. Is that any clearer? $\endgroup$ Jun 13, 2019 at 21:17


Your Answer

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

Browse other questions tagged or ask your own question.