Python: Установить только проверку наличия?

Question

У меня есть набор больших длинних строк, которые я хочу делать для поиска существования. Мне не нужна вся строка, которую нужно сохранить. Насколько я могу судить, set() фактически сохранил строку, которая поедает много моей памяти.

Существует ли такая структура данных?

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

(Моя очередь постоянно заполнена другими потоками, так что я не имею никакого способа dedupping его в начале).

Answer 1

Это, конечно, можно сохранить набор только хэшей:

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

Обратите внимание, что из-за хэш столкновения, есть шанс, что вы считаете пункт сделано, даже если это не так.

Если вы не можете принять этот риск, вам действительно нужно сохранить все строки, чтобы узнать, видели ли вы это раньше. Альтернативно: возможно, сама обработка могла бы сказать?

А альтернативно: если вы не можете принять, чтобы сохранить строки в памяти, сохранить их в базе данных или создать файлы в каталоге с тем же именем, что и строка.

Answer 2

Для этой цели можно использовать структуру данных Bloom Filter. Реализация Python может быть найдена here.

EDIT: Важные примечания:

1. Ложноположительные является возможными в этой структуре данных, то есть проверка на наличие строки может вернуть положительный результат, даже если он был не хранится ,
2. Ложные негативы (получение отрицательного результата для сохраненной строки) невозможны.

Таким образом, шансы на это могут быть сведены к минимуму при правильном использовании, и поэтому я считаю эту структуру данных очень полезной.

Answer 3

Вам нужно будет подумать о том, как выполнить поиск, поскольку для этого необходимы два метода, __hash__ и __eq__.

Хэш - это «свободная часть», которую можно отнять, но __eq__ не является свободной частью, которую вы можете сохранить; вы должны иметь две строки для сравнения.

Если вам нужно только отрицательное подтверждение (этот элемент не является частью набора), вы можете заполнить набор, который вы внедрили самими своими строками, затем вы «завершаете» набор, удалив все строки, кроме тех, которые имеют столкновений (они хранятся для экв тестов), и вы обещаете не добавлять в свой комплект больше объектов. Теперь у вас есть эксклюзивный тест. Вы можете узнать, не является ли объект не в вашем Комплекте. Вы не можете быть уверены, что «obj in Set == True» является ложным положительным или нет.

Редактировать: Это в основном фильтр цветения, который был утонченно связан, но фильтр цветения может использовать более одного хэша для каждого элемента, который действительно умный.

Edit2: Это мой 3-минутный цветение фильтр:

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

Вы должны знать всю строку, чтобы иметь 100% уверенность. Если у вас много строк со схожими префиксами, вы можете сэкономить место, используя trie для хранения строк. Если ваши строки длинны, вы также можете сэкономить место, используя большую хеш-функцию, такую ​​как SHA-1, чтобы сделать возможной хеш-коллизии настолько удаленной, чтобы быть неактуальной.

Если вы можете сделать функцию idempotent process() - то есть, если она дважды вызвана для элемента, это проблема только с производительностью, тогда проблема становится намного проще, и вы можете использовать потери данных, такие как фильтры цветения.

Answer 5

Если вы используете защищенный (например, SHA-256, найденный в модуле hashlib) хеш-функцию для хэш-строк, очень маловероятно, что вы нашли бы дубликат (и если вы найдете их, то вы, вероятно, можете выиграть приз, как с большинство криптографических хеш-функций).

Метод builtin __hash__() не гарантирует, что у вас не будет дубликатов (и поскольку он использует только 32 бита, очень вероятно, что вы найдете некоторые).

Answer 6

Как уже было намечено, если ответы, предлагаемые здесь (большинство из которых ломаются перед лицом хеш-коллизий), неприемлемы, вам нужно будет использовать представление строк без потерь.

Модуль zlib Python предоставляет встроенные возможности сжатия строк и может использоваться для предварительной обработки строк перед их помещением в ваш набор. Обратите внимание, однако, что строки должны быть довольно длинными (что вы намекаете на то, что они есть) и имеют минимальную энтропию, чтобы сэкономить много места в памяти. Другие варианты сжатия могут обеспечить лучшую экономию пространства, а некоторые версии на основе Python можно найти. here