python - medias - Necesita ayuda con un algoritmo de empaquetado de palabras

k medias python

Question

Tengo una lista de sub-listas de letras, donde el número de letras en cada sub-lista puede variar. La lista y las sub-listas están ordenadas. Esta estructura se puede usar para producir palabras eligiendo un número X, tomando una letra de la posición X en cada sub-lista y concatenándolas en orden. Si el número X es mayor que la longitud de la sub-lista, se ajustaría.

Dado un conjunto de palabras, necesito encontrar una manera de incluirlas en la estructura más pequeña posible de este tipo (es decir, con las sub-listas más cortas). Tendría que haber tantas sub-listas como el número de letras en la palabra más larga, por supuesto, y las palabras más cortas se rellenarán con espacios en blanco.

No soy un graduado de CS, por lo que me disculpo si la descripción del problema no está del todo clara. Para dar un ejemplo simple: supongamos que tengo las palabras [ ''a '', ''an'', ''if'', ''is'', ''in'', ''on'', ''of'', ''i ''] Necesito empacar, I Podría usar la siguiente estructura:

[  
    [ ''i'', ''o'', ''a'' ],  
    [ ''s'', ''n'', ''f'', '' '' ]  
]

Esto me permitiría producir las siguientes palabras:

0: is  
1: on  
2: af*  
3: i  
4: os*  
5: an  
6: if  
7: o *  
8: as*  
9: in  
10: of  
11: a

Si toma la posición 10, por ejemplo, la palabra ''de'' se genera al concatenar la letra en el índice 10% 3 (= 1) de la primera sub-lista, con la letra en el índice 10% 4 (= 2) de la segunda sub-lista.

Mi mejor intento hasta ahora es usar una matriz de distancias de Hamming para colocar primero las palabras más "conectadas" y luego a sus vecinos más cercanos, con el objetivo de minimizar el cambio con cada inserción. Este fue un intento completamente intuitivo y creo que tiene que haber una manera mejor / más inteligente de resolver esto.

Aclaración

Este es un problema práctico que estoy tratando de resolver y las restricciones son (aproximadamente) las siguientes:
1. El número de caracteres por sub-lista debe estar en el área de 100 o menos.
2. El espacio de teclas debe ser lo más pequeño posible (es decir, el número de palabras espurias debe ser mínimo). A grandes rasgos, un espacio de teclas en los millones de opciones está en el límite.

No sé si una buena solución es posible para esto. Con el algoritmo que tengo ahora, por ejemplo, puedo insertar aproximadamente 200 palabras (solo palabras en inglés aleatorias) en un espacio de teclas de 1.5 millones de opciones. Me gustaría hacerlo mejor que eso.

Answer 1

Bueno, dijiste que te interesaban las soluciones subóptimas, así que te daré una. Depende del tamaño del alfabeto. Por ejemplo, para 26 el tamaño de la matriz será poco más de 100 (independientemente de la cantidad de palabras para codificar).

Es bien sabido que si tiene dos números primos diferentes a y b y enteros no negativos k y l ( k < a , l < b ), puede encontrar el número n que n % a == k y n % b == l .
Por ejemplo, con ( a = 7, a = 13, k = 6, l = 3 ) puede tomar n = 7 * 13 + 7 * 3 + 13 * 6 . n % 7 == 6 y n % 13 == 3

Y lo mismo se aplica a cualquier número de enteros primos.

Puedes inicializar matrices como esta.

[''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
...

Ahora, supongamos que su palabra es ''geek''. Para ello necesita el número X, tal que X % 29 == 6 , X % 31 == 4 , X % 37 == 4 , X % 41 == 10 . Y siempre puedes encontrar dicha X, como se mostró arriba.

Por lo tanto, si tiene un alfabeto de 26 letras, puede crear una matriz de ancho 149 (ver la lista de números primos) y codificar cualquier palabra con ella.

Answer 2

Creo que estás buscando este http://en.wikipedia.org/wiki/Trie o este http://en.wikipedia.org/wiki/Radix_tree

Espero eso ayude.

Answer 3

No creo que entienda su problema por completo, pero me encontré con Prezip hace algún tiempo. Prezip es una forma de comprimir un conjunto ordenado de palabras aprovechando el hecho de que muchas palabras comparten un prefijo común.

Como no se está refiriendo a ninguna restricción de clasificación, sugeriría crear un conjunto ordenado de palabras que desee. Luego hacer algo similar a lo que prezip está haciendo. El resultado es un conjunto de palabras comprimidas y ordenadas, a las que puede hacer referencia por índice.

Answer 4

Podemos mejorar la respuesta de Nikita Rybek al no hacer que las listas sean una longitud primordial, sino simplemente asociar una prima a la lista. Esto nos permite no hacer las sub-listas más tiempo del necesario, por lo tanto, mantener los números primos más pequeños, lo que implica un espacio de teclas más pequeño y un empaquetado más eficiente. Usando este método y el código a continuación, empaqueté una lista de 58,110 palabras (minúsculas) en 464 caracteres. Es interesante observar que solo las letras "alex" aparecen como la letra 21 en una palabra. El espacio de teclas tenía más de 33 dígitos, sin embargo, tampoco es estrictamente necesario usar números primos, los números asociados solo necesitan ser coprime. Esto probablemente podría reducirse.

import itertools
import operator
import math

# lifted from Alex Martelli''s post at http://.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))