我们可以通过不将列表长度设为质数，而是将质数与列表关联来改进 Nikita Rybek 的答案。这使我们不必使子列表比必要的更长，从而保持质数较小，这意味着更小的键空间和更有效的打包。使用此方法和下面的代码，我将一个由
58,110（小写）单词组成的列表压缩为 464 个字符。有趣的是，只有字母 'alex' 出现在单词的第 21 个字母中。键空间高达 33 位数，但并不严格需要使用质数，相关数字只需互质即可。这可能可以减少。
import itertools
import operator
import math
def erat2( ):
D = { }
yield 2
for q in itertools.islice(itertools.count(3), 0, None, 2):
p = D.pop(q, None)
if p is None:
D[q*q] = q
yield q
else:
x = p + q
while x in D or not (x&1):
x += p
D[x] = p
def eea(u, v):
u1 = 1; u2 = 0; u3 = u
v1 = 0; v2 = 1; v3 = v
while v3 != 0:
q = u3 / v3
t1 = u1 - q * v1
t2 = u2 - q * v2
t3 = u3 - q * v3
u1 = v1; u2 = v2; u3 = v3
v1 = t1; v2 = t2; v3 = t3
return u1, u2, u3
def assign_moduli(lists):
used_primes = set([])
unused_primes = set([])
moduli = [0]*len(lists)
list_lens = [len(lst) for lst in lists]
for i, length in enumerate(list_lens):
for p in erat2():
if length <= p and p not in used_primes:
used_primes.add(p)
moduli[i] = p
break
elif p not in used_primes:
unused_primes.add(p)
return moduli
class WordEncoder(object):
def __init__(self):
self.lists = [[]]
self.words = {}
self.moduli = []
def add(self, new_words):
added_letter = False
for word in new_words:
word = word.rstrip()
word_length, lists_length = len(word), len(self.lists)
if word_length > lists_length:
self.lists.extend([' '] for i in xrange(word_length - lists_length))
for i, c in enumerate(word):
if c in self.lists[i]: continue
self.lists[i].append(c)
added_letter = True
self.words[word] = None
if not added_letter:
return self.words
else:
self._calculate_keys()
def _calculate_keys(self):
self.moduli = assign_moduli(self.lists)
N = reduce(operator.mul, self.moduli)
e_lst = []
for n in self.moduli:
r, s, dummy = eea(n, N/n)
e_lst.append(s * N / n)
lists_len = len(self.lists)
for word in self.words:
word += ' ' * (lists_len - len(word))
coords = [self.lists[i].index(c) for i,c in enumerate(word)]
key = sum(a*e for a,e in zip(coords, e_lst)) % N
self.words[word.rstrip()] = key
class WordDecoder(object):
def __init__(self, lists):
self.lists = lists
self.moduli = assign_moduli(lists)
def decode(self, key):
coords = [key % modulus for modulus in self.moduli]
return ''.join(pl[i] for pl, i in zip(self.lists, coords))
with open('/home/aaron/code/scratch/corncob_lowercase.txt') as f:
wordlist = f.read().split()
encoder = WordEncoder()
encoder.add(wordlist)
decoder = WordDecoder(encoder.lists)
for word, key in encoder.words.iteritems():
decoded = decoder.decode(key).rstrip()
if word != decoded:
print word, decoded, key
print "max key size: {0}. moduli: {1}".format(reduce(operator.mul, encoder.moduli), encoder.moduli)
break
else:
print "it works"
print "max key size: {0}".format(reduce(operator.mul, encoder.moduli))
print "moduli: {0}".format(encoder.moduli)
for i, l in enumerate(encoder.lists):
print "list {0} length: {1}, {2} - \"{3}\"".format(i, len(l), encoder.moduli[i] - len(l), ''.join(sorted(l)))
print "{0} words stored in {1} charachters".format(len(encoder.words), sum(len(l) for l in encoder.lists))
