Построение множества уникальных строк в файле эффективно, без сохранения фактических строк в наборе

Question

Недавно я пытался решить следующую проблему:

У меня есть очень большой файл, содержащий длинные строки, и мне нужно найти и распечатать все уникальные строки в нем.

Я не хочу использовать карту или задавать сохранение фактических строк, так как файл очень большой и длинные строки, поэтому это приведет к сложности пространства O (N) с плохими константами (где N количество строк). Предпочтительно, я предпочел бы генерировать набор, сохраняющий указатели на строки в уникальных файлах. Очевидно, что размер такого указателя (8 байт на 64-битной машине, который, как я полагаю), обычно намного меньше размера строки (1 байт на символ, который, как мне кажется) в памяти. Хотя пространственная сложность все еще O (N), константы теперь намного лучше. Используя эту реализацию, файл никогда не должен полностью загружаться в память.

Теперь, допустим, я просмотрю файл по строкам, проверяя уникальность. Чтобы узнать, уже ли он в наборе, я мог бы сравнить со всеми строками, указанными в наборе, сравнивая символ по символу. Это дает сложность O (N^2 * L), при этом L - средняя длина линии. Когда вы не заботитесь о сохранении полных строк в наборе, сложность O (N * L) может быть достигнута благодаря хешированию. Теперь, когда вместо этого используется набор указателей (чтобы уменьшить требования к пространству), как я могу достичь этого? Есть ли опрятный способ сделать это? Единственное, что я могу придумать, это такой подход:

1. Хеш-предложение. Сохраните хеш-значение для сопоставления (или на самом деле: unordered_multimap unordered, чтобы получить стиль hashmap, multi, поскольку двойные ключи могут быть вставлены в случае «ложных совпадений»).
2. Для каждого нового предложения: проверьте, находится ли его хэш-значение на карте. Если нет, добавьте его. Если да, сравните полные предложения (новый и один в неупорядоченной карте с одинаковым хэшем) по символу, чтобы убедиться, что нет «ложного совпадения». Если это «ложное совпадение», добавьте его еще.

Это правильный путь? Или вы можете сделать это лучше? Все предложения приветствуются!

И могу ли я использовать какой-то умный «объект сравнения» (или что-то в этом роде, о котором я пока мало знаю), чтобы эта проверка для уже существующих предложений была полностью автоматизирована при каждом вызове unordered_map :: find()?

Answer 1

Ваше решение отлично выглядит для меня, так как вы храните O (уникальные строки) хэши не N, так что это нижняя граница.

Поскольку вы сканируете файл по строкам, вы можете также отсортировать файл. Теперь повторяющиеся строки будут смежными, и вам нужно только проверить хэш предыдущей строки. Этот подход использует O (1) пространство, но вы должны сначала отсортировать файл.

Answer 2

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

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

Answer 3

Как сказано в ответе saadtaame, ваше пространство на самом деле O (уникальные линии) - в зависимости от вашего варианта использования это может быть приемлемым или нет.

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

Решение, которое вы описываете, состоит в том, чтобы поддерживать хэш-набор. Это, очевидно, самая простая вещь, и да, это потребует сохранения всех уникальных линий в памяти. Это может быть или не быть проблемой. Это решение также было бы самым простым в реализации - то, что вы пытаетесь сделать, - это то, что сделает любая реализация набора (hash-based). Вы можете просто использовать std::unordered_set и добавить каждую строку в набор.

Поскольку мы бросаем идеи, вы также можете использовать trie в качестве замены для набора. Вы могли бы сэкономить некоторое пространство, но это все равно будет O (уникальные строки).