Есть ли способ для генерации одного ключа, который запоминает все строки, с которыми мы сталкивались?

Question

Я имею дело с сотнями тысяч файлов,

Я должен обработать эти файлы 1 на 1, При этом мне нужно запомнить файлы, которые уже обработаны.

Все, что я могу придумать, это сильный путь к файлу каждого файла в массиве lo ---- ong, а затем проверка его каждый раз на предмет дублирования.

Но я думаю, что должен быть какой-то лучший способ,

Можно ли мне сгенерировать КЛЮЧ (который является числом) или что-то, что просто запоминает все файлы, которые были обработаны?

Answer 1

Вы можете использовать какую-то хеш-функцию (MD5, SHA1).

псевдокод:

for each F in filelist
    hash = md5(F name)

    if not hash in storage
        process file F
        store hash in storage to remember

см. http://tools.ietf.org/html/rfc1321 для реализации C MD5

Answer 2

Фильтр Блума может решить вашу проблему.Идея фильтра Блума проста.Он начинается с пустого массива некоторой длины, причем все его члены имеют нулевое значение.У нас будет K число хеш-функций.Когда нам нужно вставить элемент в фильтр Блума, у нас есть элемент со всеми K хэш-функциями.Эти хеш-функции будут получать K индексов для фильтра Блума.Для этих индексов нам нужно изменить значение члена на 1. Чтобы проверить, существует ли элемент в фильтре Блума, просто хешируйте его со всеми K хэшами и проверьте соответствующие индексы массива.Если все они равны 1, элемент присутствует в фильтре Блума.

Обратите внимание, что фильтр Блума может давать ложноположительные результаты.Но это никогда не дало бы ложных отрицательных результатов.Вам нужно настроить алгоритм фильтра Блума, чтобы устранить эти ложноположительные случаи.

Answer 3

Если я правильно понимаю ваш вопрос, вы хотите создать ОДИН ключ, который должен принимать определенное значение, и из этого значения вы сможете определить, какие файлы уже были обработаны?Я не знаю, сможете ли вы сделать это, просто с той точки зрения, что ваше пространство достаточно велико, а генерация уникальных ключевых презентаций в таком огромном пространстве требует много памяти.

Как уже упоминалось, что вы можете сделать, это просто сохранить каждый URL-адрес пути в HashSet.Помещение в набор сотен тысяч записей не так уж и плохо, а время поиска амортизируется постоянным временем O (1), поэтому оно будет довольно быстрым.

Answer 4

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

Answer 5

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

У выбранного языка программирования, вероятно, уже есть такая, поэтому вам не нужнонапиши один сам.C ++ имеет std::set.Java имеет Set реализации TreeSet и HashSet.Python имеет Set.Все они позволяют добавлять элементы и очень быстро проверять наличие элемента (O (1) для наборов на основе хеш-таблиц, O (log (n)) для наборов на основе деревьев).Помимо них, существует множество бесплатных реализаций множеств, а также бинарных деревьев поиска общего назначения и хеш-таблиц, которые вы можете использовать.