Python: ¿Establecer con solo verificación de existencia?

Question

Tengo un conjunto de grandes cadenas largas que quiero hacer búsquedas de existencia. No necesito que se guarde toda la cadena. Por lo que puedo decir, el set() en realidad almacenó la cadena que está consumiendo una gran cantidad de mi memoria.

¿Existe tal estructura de datos?

done = hash_only_set() 
while len(queue) > 0 : 
    item = queue.pop() 
    if item not in done : 
     process(item) 
     done.add(item) 

(Mi cola es constantemente ocupado por otros hilos así que no tengo manera de dedupping que al comienzo).

Answer 1

Es ciertamente posible para mantener un conjunto de sólo hashes:

done = set() 
while len(queue) > 0 : 
    item = queue.pop() 
    h = hash(item) 
    if h not in done : 
     process(item) 
     done.add(h) 

Tenga en cuenta que debido a las colisiones de condensación, existe la posibilidad de que se tiene en cuenta un elemento hecho a pesar de que no lo es.

Si no puede aceptar este riesgo, realmente necesita guardar todas las cadenas para poder saber si lo ha visto antes. Alternativamente: ¿quizás el procesamiento en sí mismo podría decirlo?

Sin embargo, alternativamente: si no puede mantener las cadenas en la memoria, guárdelas en una base de datos o cree archivos en un directorio con el mismo nombre que la cadena.

Answer 2

Puede usar una estructura de datos denominada Bloom Filter específicamente para este propósito. Se puede encontrar una implementación de Python here.

EDITAR: Notas importantes: positivos

1. falsos son posible en esta estructura de datos, es decir, una comprobación de la existencia de una cadena podría devolver un resultado positivo a pesar de que era no almacena .
2. No son posibles los falsos negativos (obtener un resultado negativo para una cadena que se almacenó).

Dicho esto, las posibilidades de que esto ocurra se pueden reducir al mínimo si se usan correctamente, por lo que considero que esta estructura de datos es muy útil.

Answer 3

Tendría que pensar en cómo hacer la búsqueda, ya que hay dos métodos que el conjunto necesita, __hash__ y __eq__.

El hash es una "pieza suelta" que puede llevarse, pero el __eq__ no es una pieza suelta que puede guardar; debes tener dos cadenas para la comparación.

Si solo necesita la confirmación negativa (este elemento no es parte del conjunto), puede completar una colección de conjuntos que implementó con sus cadenas, luego "finaliza" el conjunto quitando todas las cadenas, excepto aquellas con colisiones (se guardan para eq pruebas), y promete no agregar más objetos a su Conjunto. Ahora tiene una prueba exclusiva disponible ... puede ver si un objeto no es en su Conjunto. No puede estar seguro si "obj en Set == True" es un falso positivo o no.

Editar: Esto es básicamente un filtro de floración que fue hábilmente vinculado, pero un filtro de floración puede usar más de un hash por elemento que es realmente inteligente.

Edit2: Este es mi 3 minutos filtro Bloom:

class BloomFilter (object): 
    """ 
    Let's make a bloom filter 
    http://en.wikipedia.org/wiki/Bloom_filter 

    __contains__ has false positives, but never false negatives 
    """ 
    def __init__(self, hashes=(hash,)): 
     self.hashes = hashes 
     self.data = set() 
    def __contains__(self, obj): 
     return all((h(obj) in self.data) for h in self.hashes) 
    def add(self, obj): 
     self.data.update(h(obj) for h in self.hashes) 

Answer 4

lo que necesita saber toda la cadena de tener el 100% de certeza. Si tiene muchas cadenas con prefijos similares, puede ahorrar espacio usando un trie para almacenar las cadenas. Si sus cadenas son largas, también podría ahorrar espacio utilizando una función hash grande como SHA-1 para hacer que la posibilidad de colisiones hash sea tan remota que sea irrelevante.

Si puede hacer que la función process() sea idempotente, es decir, hacer que se llame dos veces en un elemento es solo un problema de rendimiento, entonces el problema es mucho más simple y puede usar estructuras de datos con pérdidas, como filtros de floración.

Answer 5

Si utiliza una función hash segura (como SHA-256, que se encuentra en el hashlib) para manipular las cadenas, es muy poco probable que encuentre duplicados (y si encuentra algunos, probablemente pueda ganar un premio como la mayoría de las funciones hash criptográficas).

El método __hash__() incorporado no garantiza que no tenga duplicados (y dado que solo usa 32 bits, es muy probable que encuentre algunos).

Answer 6

Como ya se ha insinuado, si las respuestas ofrecidas aquí (la mayoría de las cuales se rompen frente a las colisiones hash) no son aceptables, necesitaría usar una representación sin pérdida de las cadenas.

El módulo zlib de Python proporciona funciones integradas de compresión de cadenas y podría utilizarse para procesar previamente las cadenas antes de colocarlas en el conjunto. Sin embargo, tenga en cuenta que las cadenas tendrían que ser bastante largas (lo que usted insinúa que son) y tener una entropía mínima para ahorrar mucho espacio de memoria. Otras opciones de compresión pueden proporcionar un mejor ahorro de espacio y se pueden encontrar algunas implementaciones basadas en Python here