сжатие огромного набора аналогичных строк

Вот простейшая вещь, о которой я могу думать, что это может сработать. Он «сжимает» данные, только сохраняя каждый уникальный путь каталога один раз в словаре. Все файлы в любом каталоге хранятся в list . Для целей тестирования примерный код ниже просто считывает входной файл, состоящий из одного полного пути к файлу на строку.

 from collections import defaultdict import os directories = defaultdict(list) with open('log_file_paths.txt') as inf: for path in (line.strip() for line in inf): dir_path, file_name = os.path.split(path) directories[dir_path].append(file_name) for path in directories: print path for file_name in directories[path]: print ' ', file_name 

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

Теперь обновленная версия теперь обладает тем свойством, что – в отличие от предыдущего – то, что создано, может быть маринованно, а это значит, что оно может быть сохранено и вернулось обратно в файл позже.

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

 import collections import cPickle as pickle # use C version for performance import operator import os class DefaultDict(collections.defaultdict): """ pickle-able defaultdict """ def __reduce__(self): args = (self.default_factory,) if self.default_factory else tuple() return type(self), args, None, None, self.iteritems() def Tree(): return DefaultDict(Tree) class Leaf(object): pass def print_tree(d, level=0, indent=' '*4): """ Tree structure pretty printer """ if not d: print indent * level + '<empty>' else: for key, value in sorted(d.iteritems()): print indent * level + str(key) if isinstance(value, dict): print_tree(value, level+1, indent) elif not isinstance(value, Leaf): print indent * (level+1) + str(value) # create Tree structure from paths tree = Tree() LEAF = Leaf() with open('log_file_paths.txt') as inf: for line in inf: path = line.strip().split(os.sep) reduce(operator.getitem, path[:-1], tree)[path[-1]] = LEAF print_tree(tree) # save tree to a file with open('file_tree.pk', 'wb') as outf: pickle.dump(tree, outf, pickle.HIGHEST_PROTOCOL) # try reading it back in del tree with open('file_tree.pk', 'rb') as inf: tree = pickle.load(inf) print_tree(tree) # display reconstituted tree 

Поэтому, если входной файл состоял из этих путей к файлу:

 tests/first/set1.log tests/first/set2.log tests/first/subfirst/set3.log tests/first/subfirst/set4.log tests/second/set5.log tests/second/subsecond/set6.log tests/second/subsecond/subsubsecond/set7.log tests/third/set8.log 

Следующая древовидная структура – это то, что создается в памяти и отображается (и позже написано, читается и перерисовывается), чтобы удерживать их:

 tests first set1.log set2.log subfirst set3.log set4.log second set5.log subsecond set6.log subsubsecond set7.log third set8.log 

Прямо сейчас у меня есть только Java-решение. Вы можете использовать его как отдельный сценарий. Измените значение в коде на пути к файлу и выполните его.

Вы можете изменить способ поиска в соответствии с вашими потребностями. В проекте также есть скрипт ant, который вы можете настроить, если это необходимо.

Например, если вы ищете имя файла:

sipproxy0-dc0-авто-узел известен, 10.20131021_213407_288.snapshot.log

Вы должны были бы предоставить полный путь, например:

C: \ ccview \ aglagole_2_cloudute \ tserver_ddpsf \ siptserver \ CloudUte \ UnitTest \ worker_log \ aglagole \ журналы \ sipproxy0-dc0-авто-узла известно, 10.20131021_213407_288.snapshot.log

Чтобы уменьшить использование памяти, я бы рекомендовал вам генерировать хэш для общей части в каждой строке (у Guava lib у Гува есть довольно хорошая реализация)

C: \ ccview \ aglagole_2_cloudute \ tserver_ddpsf \ siptserver \ CloudUte \ UnitTest \ worker_log \ aglagole \ журналы

Дайте мне знать, если вы столкнетесь с проблемами памяти.

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

Массивы суффикса являются современной заменой предлагаемых деревьев. Массивы суффикса могут использоваться для эффективного поиска подстроки. Однако сразу не ясно, как использовать их для моей проблемы. Обзор массивов суффиксов: Puglisi, SJ, Smyth, WF и Turpin, AH (2007). Таксономия алгоритмов построения массива суффикса. ACM Computing Surveys (CSUR), 39 (2), 4.

Это исследование напрямую применимо к моей проблеме: Brisaboa, NR, Cánovas, R., Claude, F., Martínez-Prieto, MA, & Navarro, G. (2011). Сжатые струнные словари. В экспериментальных алгоритмах (стр. 136-147). Спрингер Берлин Гейдельберг. К сожалению, никакой реализации для загрузки и повторного использования.

Грамматический анализатор: Larsson, NJ, & Moffat, A. (2000). Офлайн-сжатие на основе словаря. Труды IEEE, 88 (11), 1722-1732. Реализация доступна. Все строки должны быть в памяти, чтобы вычислить грамматику. Я могу собрать первые 1000 строк и вычислить грамматику; в качестве альтернативы я могу выполнить полный запуск (вплоть до сбоя памяти), записать все строки и вычислить грамматику. Возможная проблема: строки изменяются со временем (имена включают даты / время). Не оптимальная скорость сжатия; кроме того, неясно, что произойдет, если есть строка, которая не соответствует заранее вычисленной грамматике. Может быть, такая строка вообще не будет сжата. Это решение не так эффективно, как предыдущие исследования, и по-прежнему требует значительных усилий для кодирования и тестирования.