Эффективное построение набора уникальных строк в файле без сохранения фактических строк в наборе
Недавно я пытался решить следующую проблему:
У меня есть очень большой файл, содержащий длинные строки, и мне нужно найти и распечатать все уникальные строки в нем.
Я не хочу использовать карту или набор для хранения фактических строк, так как файл очень большой, а строки длинные, поэтому это приведет к сложности пространства O (N) с плохими константами (где N — количество строк ). Желательно, чтобы я сгенерировал набор, хранящий указатели на строки в файлах, которые являются уникальными. Ясно, что размер такого указателя (я полагаю, 8 байт на 64-битной машине), как правило, намного меньше размера строки (1 байт на символ, на мой взгляд) в памяти. Хотя сложность пространства все еще равна O (N), константы теперь намного лучше. Используя эту реализацию, файл никогда не должен быть полностью загружен в память.
Теперь, скажем, я буду проходить файл построчно, проверяя уникальность. Чтобы увидеть, есть ли оно уже в наборе, я мог бы сравнить все строки, указанные на данный момент, сравнивая символ за символом. Это дает сложность O (N ^ 2 * L), где L — средняя длина линии. Если не заботиться о сохранении полных строк в наборе, O (N * L) сложность может быть достигнута благодаря хешированию. Теперь, когда вместо этого используется набор указателей (чтобы уменьшить требования к пространству), как я все еще могу достичь этого? Есть ли хороший способ сделать это? Единственное, что я могу придумать, это такой подход:
- Хэш предложения. Сохраните значение хеша для отображения (или на самом деле: unordered_multimap неупорядочено, чтобы получить стиль хеш-карты, multi, так как двойные ключи могут быть вставлены в случае «ложных совпадений»).
- Для каждого нового предложения: проверьте, есть ли его хэш-значение уже на карте. Если нет, добавьте это. Если да, сравнивайте полные предложения (новое и одно в неупорядоченной карте с тем же хешем) посимвольно, чтобы убедиться, что нет «ложного соответствия». Если это «ложное совпадение», добавьте его.
Это правильный путь? Или есть лучший способ сделать это? Все предложения приветствуются!
И могу ли я использовать какой-нибудь умный «объект сравнения» (или что-то в этом роде, пока я об этом немного знаю), чтобы сделать эту проверку для уже существующих предложений полностью автоматизированной при каждом вызове unordered_map :: find ()?
Решение
Ваше решение выглядит хорошо для меня, так как вы храните O (уникальные строки) хэши, а не N, так что это нижняя граница.
Поскольку вы сканируете файл построчно, вы можете также отсортировать файл. Теперь повторяющиеся строки будут смежными, и вам нужно только проверить по хешу предыдущей строки. В этом подходе используется пространство O (1), но сначала нужно отсортировать файл.
Другие решения
Как говорится в ответе @ saadtaame, ваше пространство фактически равно O (уникальным строкам) — в зависимости от вашего варианта использования это может быть приемлемым или нет.
Хотя хэширование, безусловно, имеет свои достоинства, оно может иметь много проблем с коллизиями — и если у вас не может быть ложных срабатываний, то это не пуск, если вы фактически не держите содержимое строк для проверки.
Решение, которое вы описываете, состоит в том, чтобы поддерживать набор на основе хеша. Это, очевидно, самая простая вещь, которую нужно сделать, и да, это потребует сохранения всех уникальных строк в памяти. Это может или не может быть проблемой, хотя. Это решение также будет проще всего реализовать — то, что вы пытаетесь сделать, это именно то, что сделает любая реализация набора (на основе хеша). Вы можете просто использовать std::unordered_setи добавьте каждую строку в набор.
Поскольку мы разбрасываем идеи, вы также можете использовать Trie в качестве замены для набора. Возможно, вы сэкономите немного места, но это все равно будет O (уникальные строки).
Если в файле нет какой-то особой структуры, которую вы можете использовать, то определенно используйте хэширование строк. Это будет — на порядок — быстрее, чем фактически сравнивать каждую строку с каждой строкой в файле.
Если ваша фактическая реализация все еще слишком медленная, вы можете, например, ограничьте хеширование первой частью каждой строки. Это приведет к большему количеству ложных срабатываний, но при условии, что большинство строк будут отклоняться уже в первых нескольких словах, это значительно ускорит обработку файла (особенно, если вы ограничены вводом / выводом).