Alternativas de memoria eficiente a los diccionarios de Python

Question

En uno de mis proyectos paralelos actuales, estoy escaneando un texto para ver la frecuencia de trillizos de palabras. En mi primer intento, utilicé el diccionario predeterminado tres niveles de profundidad. En otras palabras, topDict[word1][word2][word3] devuelve el número de veces que estas palabras aparecen en el texto, topDict[word1][word2] devuelve un diccionario con todas las palabras que aparecen después de las palabras 1 y 2, etc.

Esto funciona correctamente, pero requiere mucha memoria. En mis pruebas iniciales, utilizó algo así como 20 veces la memoria de simplemente almacenar los trillizos en un archivo de texto, lo que parece una gran cantidad de memoria sobrecarga.

Mi sospecha es que muchos de estos diccionarios se están creando con muchas más ranuras de las que realmente se utilizan, así que quiero reemplazar los diccionarios con otra cosa que sea más eficiente con la memoria cuando se utiliza de esta manera. Preferiría mucho una solución que permita búsquedas clave a lo largo de las líneas de los diccionarios.

Por lo que sé de las estructuras de datos, un árbol de búsqueda binaria equilibrado usando algo como rojo-negro o AVL probablemente sería ideal, pero realmente preferiría no implementarlo yo mismo. Si es posible, preferiría quedarme con las bibliotecas estándar de Python, pero definitivamente estoy abierto a otras alternativas si funcionan mejor.

Entonces, ¿alguien tiene alguna sugerencia para mí?

Editado para añadir:

Gracias por las respuestas hasta ahora. Algunas de las respuestas hasta ahora han sugerido el uso de tuplas, que realmente no me ayudó mucho cuando condensé las dos primeras palabras en una tupla. Dudo en utilizar los tres como clave, ya que quiero que sea fácil buscar todas las palabras de los dos primeros. (es decir, quiero algo así como el resultado de topDict[word1, word2].keys()).

El conjunto de datos actual con el que estoy jugando es la versión más reciente de Wikipedia For Schools. Los resultados de analizar las primeras mil páginas, por ejemplo, son algo así como 11 MB para un archivo de texto en el que cada línea es de tres palabras y se separa la pestaña de conteo total. Almacenar el texto en el formato de diccionario Ahora estoy usando tomas de alrededor de 185MB. Sé que habrá una sobrecarga adicional para los punteros y otras cosas, pero la diferencia parece excesiva.

Answer 1

Algunas medidas. Tomé 10MB de texto libre de e-book y frecuencias de trigram calculadas, produciendo un archivo de 24MB. Almacenarlo en diferentes estructuras de datos simples de Python tomó tanto espacio en kB, medido como RSS desde correr ps, donde d es un dict, keys y freqs son listas, y a, b, c, freq son los campos de un trigram record:

295760  S. Lott's answer 
237984  S. Lott's with keys interned before passing in 
203172 [*] d[(a,b,c)] = int(freq) 
203156  d[a][b][c] = int(freq) 
189132  keys.append((a,b,c)); freqs.append(int(freq)) 
146132  d[intern(a),intern(b)][intern(c)] = int(freq) 
145408  d[intern(a)][intern(b)][intern(c)] = int(freq) 
83888 [*] d[a+' '+b+' '+c] = int(freq) 
82776 [*] d[(intern(a),intern(b),intern(c))] = int(freq) 
68756  keys.append((intern(a),intern(b),intern(c))); freqs.append(int(freq)) 
60320  keys.append(a+' '+b+' '+c); freqs.append(int(freq)) 
50556  pair array 
48320  squeezed pair array 
33024  squeezed single array 

Las entradas marcadas con [*] no tienen una forma eficiente de buscar un par (a, b); están listados solo porque otros los han sugerido (o variantes de ellos). (Me molestó un poco hacer esto porque las respuestas mejor votadas no fueron útiles, como muestra la tabla.)

'Pair array' es el siguiente esquema en mi respuesta original ("Comenzaría con la matriz con las claves siendo las dos primeras palabras ... "), donde la tabla de valores para cada par es representada como una cadena única. 'Arreglo de pares comprimidos' es el mismo, omitiendo los valores de frecuencia que son iguales a 1 (el caso más común). 'Squeezed single array' es como una matriz de pares comprimidos, pero combina la clave y el valor juntos como una cadena (con un carácter de separación). El único código de matriz de exprimido:

import collections 

def build(file): 
    pairs = collections.defaultdict(list) 
    for line in file: # N.B. file assumed to be already sorted 
     a, b, c, freq = line.split() 
     key = ' '.join((a, b)) 
     pairs[key].append(c + ':' + freq if freq != '1' else c) 
    out = open('squeezedsinglearrayfile', 'w') 
    for key in sorted(pairs.keys()): 
     out.write('%s|%s\n' % (key, ' '.join(pairs[key]))) 

def load(): 
    return open('squeezedsinglearrayfile').readlines() 

if __name__ == '__main__': 
    build(open('freqs')) 

no he escrito el código para buscar valores de esta estructura (uso biseca, como se menciona más adelante), o implementado las estructuras más elegante comprimidos también se describen a continuación.

Respuesta original: Una simple ordenación ordenada de cadenas, cada cadena es una concatenación de palabras separada por espacios, buscada utilizando el módulo bisect, debería valer la pena intentarlo para empezar. Esto ahorra espacio en los punteros, etc. Todavía desperdicia espacio debido a la repetición de las palabras; hay un truco estándar para eliminar prefijos comunes, con otro nivel de índice para recuperarlos, pero eso es bastante más complejo y más lento. (La idea es almacenar trozos sucesivos de la matriz en una forma comprimida que debe escanearse secuencialmente, junto con un índice de acceso aleatorio para cada fragmento. Los trozos son lo suficientemente grandes como para comprimirlos, pero lo suficientemente pequeños para un tiempo de acceso razonable. esquema aplicable aquí: si las entradas sucesivas son 'hello george' y 'hello world', haga que la segunda entrada sea '6world' en su lugar. (6 es la longitud del prefijo en común.) ¿O tal vez podría salirse con la suya usando zlib? De todos modos, puedes encontrar más en este sentido buscando las estructuras de los diccionarios que se usan en la búsqueda de texto completo. Así que específicamente, comenzaría con la matriz con las dos primeras palabras, con una matriz paralela cuyas entradas enumeran la posible Terceras palabras y sus frecuencias. Sin embargo, todavía podría ser una mierda, creo que puede que no tenga suerte en cuanto a las baterías, incluidas las opciones de ahorro de memoria.

Además, las estructuras de árbol binario son no recomendadas para la eficiencia de la memoria aquí. Por ejemplo, this paper prueba una variedad de estructuras de datos sobre un problema similar (sin embargo, unigrams en lugar de trigramas) y encuentra una tabla hash para vencer a todas las estructuras de árbol con esa medida.

Debería haber mencionado, como lo hizo otra persona, que la matriz ordenada podría usarse solo para la lista de palabras, no para bigramas o trigramas; luego, para su estructura de datos "real", sea lo que sea, utiliza claves enteras en lugar de cadenas, índices en la lista de palabras. (Pero esto le impide explotar prefijos comunes excepto en la lista de palabras misma. Tal vez no debería sugerir esto después de todo.)

Answer 2

Puede intentar usar el mismo diccionario, solo un nivel de profundidad.

topDictionary[word1+delimiter+word2+delimiter+word3] 

delimitador podría ser simple "". (o use (word1, word2, word3))

Esto sería más fácil de implementar. Creo que va a ver una pequeña mejora, si no es suficiente ... ... Ya se me ocurrirá algo ...

Answer 3

Un par de intentos:

Calculo que estás haciendo algo similar a esto:

from __future__ import with_statement 

import time 
from collections import deque, defaultdict 

# Just used to generate some triples of words 
def triplegen(words="/usr/share/dict/words"): 
    d=deque() 
    with open(words) as f: 
     for i in range(3): 
      d.append(f.readline().strip()) 

     while d[-1] != '': 
      yield tuple(d) 
      d.popleft() 
      d.append(f.readline().strip()) 

if __name__ == '__main__': 
    class D(dict): 
     def __missing__(self, key): 
      self[key] = D() 
      return self[key] 
    h=D() 
    for a, b, c in triplegen(): 
     h[a][b][c] = 1 
    time.sleep(60) 

Eso me da ~ 88MB.

Cambiar el almacenamiento a

h[a, b, c] = 1 

toma ~ 25 MB

internar a, b, c y lo hace tomar alrededor de 31 MB. Mi caso es un poco especial porque mis palabras nunca se repiten en la entrada. Puede intentar algunas variaciones usted mismo y ver si alguno de estos le ayuda.

Answer 4

Puede poner todas las palabras en un diccionario. la clave sería word, y value es number (index).

continuación, se utiliza de esta manera:

Word1=indexDict[word1] 
Word2=indexDict[word2] 
Word3=indexDict[word3] 

topDictionary[Word1][Word2][Word3] 

Insertar en indexDict con:

if word not in indexDict: 
    indexDict[word]=len(indexDict) 

Answer 5

Use tuplas.
Las tuplas pueden ser claves para los diccionarios, por lo que no es necesario anidar diccionarios.

d = {} 
d[ word1, word2, word3 ] = 1 

también como un plus, podría utilizar defaultdict

• por lo que los elementos que no tienen entradas siempre devuelven 0
• y para que u puede decir d[w1,w2,w3] += 1 sin comprobar si la clave ya existe o no

ejemplo:

from collections import defaultdict 
d = defaultdict(int) 
d["first","word","tuple"] += 1 

Si usted necesita encontrar todas las palabras "word3" que se tupled con (palabra1, palabra2) a continuación, busque en dictionary.keys() usando listas por comprensión

si tiene una tupla, t, usted puede conseguir los dos primeros puntos se utilizan rangos de:

>>> a = (1,2,3) 
>>> a[:2] 
(1, 2) 

un pequeño ejemplo para la búsqueda de tuplas con listas por comprensión:

>>> b = [(1,2,3),(1,2,5),(3,4,6)] 
>>> search = (1,2) 
>>> [a[2] for a in b if a[:2] == search] 
[3, 5] 

aquí se puede apreciar, tenemos una lista de todos los elementos que aparecen como el tercer elemento de la tuplas que comience con (1,2)

Answer 6

Ok, por lo que básicamente está tratando de almacenar un espacio 3D escaso. El tipo de patrones de acceso que desea para este espacio es crucial para la elección del algoritmo y la estructura de datos. Teniendo en cuenta su fuente de datos, ¿desea alimentar esto a una grilla? Si no necesita acceso O (1):

Para obtener la eficacia de la memoria, desea subdividir ese espacio en subespacios con un número similar de entradas. (como un BTree). Por lo que una estructura de datos con:

• firstWordRange
• secondWordRange
• thirdWordRange
• numberOfEntries
• un bloque ordenada de entradas.
• bloques siguiente y anterior en las 3 dimensiones

Answer 7

En este caso, ZODB ¹ Btrees podrían ser útiles, ya que son mucho menos memoria hambre. Utilice un BTrees.OOBtree (Claves de objeto para valores de objeto) o BTrees.OIBTree (Claves de objeto para valores enteros), y use tuplas de 3 palabras como su clave.

Algo así como:

from BTrees.OOBTree import OOBTree as BTree 

La interfaz es, más o menos, dict-como, con la ventaja añadida (para ti) que .keys, .items, .iterkeys y .iteritems tienen dos min, max argumentos opcionales:

>>> t=BTree() 
>>> t['a', 'b', 'c']= 10 
>>> t['a', 'b', 'z']= 11 
>>> t['a', 'a', 'z']= 12 
>>> t['a', 'd', 'z']= 13 
>>> print list(t.keys(('a', 'b'), ('a', 'c'))) 
[('a', 'b', 'c'), ('a', 'b', 'z')] 

¹ Tenga en cuenta que si está en Windows y trabaja con Python> 2.4, sé que hay paquetes para versiones de Python más recientes, pero no puedo recordar dónde.

PS Existen en la generación de texto de Markov CheeseShop ☺

Answer 8

¿Está implementando?

Si sus cadenas asignan 2 palabras a las probabilidades del tercero, usaría un diccionario mapeando K-tuplas al histograma de 3ra palabra. Una forma trivial (pero hambrienta de memoria) de implementar el histograma sería usar una lista con repeticiones, y luego random.choice le da una palabra con la probabilidad adecuada.

Aquí es una implementación con el K-tupla como un parámetro:

import random 

# can change these functions to use a dict-based histogram 
# instead of a list with repeats 
def default_histogram():   return [] 
def add_to_histogram(item, hist): hist.append(item) 
def choose_from_histogram(hist): return random.choice(hist) 

K=2 # look 2 words back 
words = ... 
d = {} 

# build histograms 
for i in xrange(len(words)-K-1): 
    key = words[i:i+K] 
    word = words[i+K] 

    d.setdefault(key, default_histogram()) 
    add_to_histogram(word, d[key]) 

# generate text 
start = random.randrange(len(words)-K-1) 
key = words[start:start+K] 
for i in NUM_WORDS_TO_GENERATE: 
    word = choose_from_histogram(d[key]) 
    print word, 
    key = key[1:] + (word,) 

Answer 9

Si la memoria no es simplemente lo suficientemente grande, pybsddb puede ayudar a almacenar un mapa de disco persistente.

Answer 10

Puede usar una matriz nudosa multidimensional. Tendrá que usar números en lugar de cadenas para indexar en la matriz, pero eso se puede resolver usando una única dicción para asignar palabras a los números.

import numpy 
w = {'word1':1, 'word2':2, 'word3':3, 'word4':4} 
a = numpy.zeros((4,4,4)) 

Entonces para indexar en la matriz, que harías algo así como:

a[w[word1], w[word2], w[word3]] += 1 

que la sintaxis no es bello, pero matrices numpy son casi tan eficientes como cualquier cosa que es probable encontrar. Tenga en cuenta también que no he probado este código, por lo que puede estar apagado en algunos de los detalles. Solo voy de memoria aquí.

Answer 11

Aquí hay una estructura en árbol que usa la biblioteca bisecada para mantener una lista ordenada de palabras. Cada búsqueda en O (log2 (n)).

import bisect 

class WordList(object): 
    """Leaf-level is list of words and counts.""" 
    def __init__(self): 
     self.words= [ ('\xff-None-',0) ] 
    def count(self, wordTuple): 
     assert len(wordTuple)==1 
     word= wordTuple[0] 
     loc= bisect.bisect_left(self.words, word) 
     if self.words[loc][0] != word: 
      self.words.insert(loc, (word,0))   
     self.words[loc]= (word, self.words[loc][1]+1) 
    def getWords(self): 
     return self.words[:-1] 

class WordTree(object): 
    """Above non-leaf nodes are words and either trees or lists.""" 
    def __init__(self): 
     self.words= [ ('\xff-None-',None) ] 
    def count(self, wordTuple): 
     head, tail = wordTuple[0], wordTuple[1:] 
     loc= bisect.bisect_left(self.words, head) 
     if self.words[loc][0] != head: 
      if len(tail) == 1: 
       newList= WordList() 
      else: 
       newList= WordTree() 
      self.words.insert(loc, (head,newList)) 
     self.words[loc][1].count(tail) 
    def getWords(self): 
     return self.words[:-1] 

t = WordTree() 
for a in (('the','quick','brown'), ('the','quick','fox')): 
    t.count(a) 

for w1,wt1 in t.getWords(): 
    print w1 
    for w2,wt2 in wt1.getWords(): 
     print " ", w2 
     for w3 in wt2.getWords(): 
      print " ", w3 

Para simplificar, esto utiliza un valor ficticio en cada árbol y lista. Esto ahorra infinitas declaraciones if para determinar si la lista estaba realmente vacía antes de hacer una comparación. Solo está vacío una vez, por lo que las sentencias if se desperdician para todos n -1 otras palabras.

Answer 12

Scipy tiene matrices dispersas, lo que si puede hacer que las dos primeras palabras de una tupla, se puede hacer algo como esto:

import numpy as N 
from scipy import sparse 

word_index = {} 
count = sparse.lil_matrix((word_count*word_count, word_count), dtype=N.int) 

for word1, word2, word3 in triple_list: 
    w1 = word_index.setdefault(word1, len(word_index)) 
    w2 = word_index.setdefault(word2, len(word_index)) 
    w3 = word_index.setdefault(word3, len(word_index)) 
    w1_w2 = w1 * word_count + w2 
    count[w1_w2,w3] += 1