Нужна помощь с алгоритмом упаковки слов

Ответ 1

Хорошо, вы сказали, что вас интересуют субоптимальные решения, поэтому я дам вам один. Он зависит от размера алфавита. Например, для 26 размер массива будет чуть больше 100 (независимо от количества слов для кодирования).

Хорошо известно, что если у вас есть два разных простых числа a и b и неотрицательные целые числа k и l (k < a, l < b), вы можете найти номер n, что n % a == k и n % b == l.
Например, с (a = 7, a = 13, k = 6, l = 3) вы можете взять n = 7 * 13 + 7 * 3 + 13 * 6. n % 7 == 6 и n % 13 == 3

И то же самое верно для любого числа простых целых чисел.

Вы можете инициализировать такие массивы, как это.

['a', 'b', 'c', ... 'z', 'z', 'z', 'z', ...]   # array size = 29
['a', 'b', 'c', ... 'z', 'z', 'z', 'z', ...]   # array size = 31
['a', 'b', 'c', ... 'z', 'z', 'z', 'z', ...]   # array size = 37
['a', 'b', 'c', ... 'z', 'z', 'z', 'z', ...]   # array size = 41
...

Теперь предположим, что ваше слово "geek". Для этого вам нужно число X, такое, что X % 29 == 6, X % 31 == 4, X % 37 == 4, X % 41 == 10. И вы всегда можете найти такой X, как показано выше.

Итак, если у вас есть алфавит из 26 букв, вы можете создать матрицу шириной 149 (см. список простых чисел) и закодировать любое слово с ней.

Ответ 2

Мы можем улучшить ответ Никиты Рыбека, фактически не делая списки простой длины, а просто сопоставляя простое со списком. Это позволяет нам не делать суб-списки дольше, чем необходимо, следовательно, сохраняя простые числа, что подразумевает меньшее пространство ключей и более эффективную упаковку. Используя этот метод и приведенный ниже код, я упаковал список 58,110 (строчных) слов на 464 символа. Интересно отметить, что только буквы "алекс" кажутся 21-й буквой в слове. Ключевое пространство было выше 33 цифр, но также не обязательно использовать простые числа, связанные номера просто должны быть взаимно простыми. Вероятно, это может быть уменьшено.

import itertools
import operator
import math

# lifted from Alex Martelli post at http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python
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


# taken from http://en.literateprograms.org/Extended_Euclidean_algorithm_(Python)
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 = [[]] # the list of primedlists
        self.words = {} # keys are words, values are number that retrieves word
        self.moduli = [] # coprime moduli that are used to assign unique keys to words

    def add(self, new_words):
        added_letter = False # flag that we need to rebuild the keys
        for word in new_words:
            word = word.rstrip() # a trailing blank space could hide the need for a key rebuild
            word_length, lists_length = len(word), len(self.lists)
            # make sure we have enough lists
            if word_length > lists_length:
                self.lists.extend([' '] for i in xrange(word_length - lists_length))
            # make sure that each letter is in the appropriate list
            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
        # now we recalculate all of the keys if necessary
        if not added_letter:
            return self.words
        else:
            self._calculate_keys()

    def _calculate_keys(self):
        # were going to be solving a lot of systems of congruences
        # these are all of the form x % self.lists[i].modulus == self.lists[i].index(word[i]) with word padded out to 
        # len(self.lists). We will be using the Chinese Remainder Theorem to do this. We can do a lot of the calculations
        # once before we enter the loop because the numbers that we need are related to self.lists[i].modulus and not
        # the indexes of the necessary letters
        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)
        #now we begin the actual recalculation 
        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  # this solves the system of congruences
             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))

Ответ 3

Я не думаю, что полностью понимаю вашу проблему, но некоторое время назад я наткнулся на презип. Prezip - это способ сжатия отсортированного набора слов, используя тот факт, что многие слова имеют общий префикс.

Поскольку вы не ссылаетесь на какое-либо ограничение сортировки, я бы предложил создать отсортированный набор слов, которые вы хотите. Затем сделайте что-то похожее на то, что делает презип. Результат - сжатый и отсортированный набор слов, к которым вы можете обратиться по индексу.

Ответ 4

Я думаю, что вы ищете это http://en.wikipedia.org/wiki/Trie или это http://en.wikipedia.org/wiki/Radix_tree

Надеюсь, что это поможет.