# Permutation to maximise strings' common prefix

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
else
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.
else
su = s  # Uncompressed case
return inverse_permutation(p, su)

• What does this line mean: "s = len(s)=k ? concat(v,s) : s"? – lox Jun 13 at 19:51
• I mean if the length of s is k then set s to the concatenate of v and s otherwise don't modify it. – David Welch Jun 13 at 21:10
• I think you should edit the question so it's clear – lox Jun 13 at 21:12
• Thanks - I've done so. Is that any clearer? – David Welch Jun 13 at 21:17