Изменится ли хеш текстового файла если добавить в него пустую строку

Обновлено: 15.01.2025

Текстовые файлы. Примеры решения задач на модификацию текстовых файлов

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

Содержание

1. Как определить, что данные в текстовом файле закончились?
2. Как прочитать строки из текстового файла, если их количество неизвестно? Способы определения количества строк в файле
3. Замена строки в текстовом файле. Пример
4. Удаление строки из файла по ее индексу. Пример
5. Вставка строки в указанную позицию файла. Пример
6. Обмен местами двух строк в файле. Пример
7. Реверсирование строк файла (перестановка строк файла в обратном порядке). Пример
8. Сортировка строк файла. Метод сортировки выбором. Пример
9. Объединение двух файлов. Пример

Поиск на других ресурсах:

1. Как определить, что данные в текстовом файле закончились?

Пример.

2. Как прочитать строки из текстового файла, если их количество неизвестно? Способы определения количества строк в файле

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

прочитать строки файла методом readlines() . Результатом будет список. Затем с помощью метода len() определить количество строк;
реализовать цикл чтения строк методом readline() до тех пор, пока не будет пустая строка. Метод readline() возвращает пустую строку в случае, когда достигнут конец файла.

Пример. В примере приводятся 3 способа определения количества строк в файле.

3. Замена строки в текстовом файле. Пример

Чтобы заменить строку в текстовом файле нужно выполнить следующие действия:

считать файл в список;
изменить строку в списке;
записать список в файл.

4. Удаление строки из файла по ее индексу. Пример

По примеру п. 3 выполняется удаление строки по ее индексу.

5. Вставка строки в указанную позицию файла. Пример

В данном примере осуществляется вставка строки в указанную позицию файла. Если указать позицию, которая размещена за последней строкой файла, то осуществляется дописывание строки в конец файла.

6. Обмен местами двух строк в файле. Пример

7. Реверсирование строк файла (перестановка строк файла в обратном порядке). Пример

8. Сортировка строк файла. Метод сортировки выбором. Пример

Приводится пример сортировки строк файла. Используется метод сортировки выбором.

Хэш — это какая-то функция, сопоставляющая объектам какого-то множества числовые значения из ограниченного промежутка.

Быстро считается — за линейное от размера объекта время;
Имеет не очень большие значения — влезающие в 64 бита;
«Детерминированно-случайная» — если хэш может принимать \(n\) различных значений, то вероятность того, что хэши от двух случайных объектов совпадут, равна примерно \(\frac\) .

Обычно хэш-функция не является взаимно однозначной: одному хэшу может соответствовать много объектов. Такие функции называют сюръективными.

Для некоторых задач удобнее работать с хэшами, чем с самими объектами. Пусть даны \(n\) строк длины \(m\) , и нас просят \(q\) раз проверять произвольные две на равенство. Вместо наивной проверки за \(O(q \cdot n \cdot m)\) , мы можем посчитать хэши всех строк, сохранить, и во время ответа на запрос сравнивать два числа, а не две строки.

Применения в реальной жизни

Чек-суммы. Простой и быстрый способ проверить целостность большого передаваемого файла — посчитать хэш-функцию на стороне отправителя и на стороне получателя и сравнить.
Хэш-таблица. Класс unordered_set из STL можно реализовать так: заведём \(n\) изначально пустых односвязных списков. Возьмем какую-нибудь хэш-функцию \(f\) с областью значений \([0, n)\) . При обработке .insert(x) мы будем добавлять элемент \(x\) в \(f(x)\) -тый список. При ответе на .find(x) мы будем проверять, лежит ли \(x\) -тый элемент в \(f(x)\) -том списке. Благодаря «равномерности» хэш-функции, после \(k\) добавлений ожидаемое количество сравнений будет равно \(\frac\) = \(O(1)\) при правильном выборе \(n\) .
Мемоизация. В динамическом программировании нам иногда надо работать с состояниями, которые непонятно как кодировать, чтобы «разгладить» в массив. Пример: шахматные позиции. В таком случае нужно писать динамику рекурсивно и хранить подсчитанные значения в хэш-таблице, а для идентификации состояния использовать его хэш.
Проверка на изоморфизм. Если нам нужно проверить, что какие-нибудь сложные структуры (например, деревья) совпадают, то мы можем придумать для них хэш-функцию и сравнивать их хэши аналогично примеру со строками.
Криптография. Правильнее и безопаснее хранить хэши паролей в базе данных вместо самих паролей — хэш-функцию нельзя однозначно восстановить.
Поиск в многомерных пространствах. Детерминированный поиск ближайшей точки среди \(m\) точек в \(n\) -мерном пространстве быстро не решается. Однако можно придумать хэш-функцию, присваивающую лежащим рядом элементам одинаковые хэши, и делать поиск только среди элементов с тем же хэшом, что у запроса.

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

Сегодня же мы остановимся на строках.

Полиномиальное хэширование

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

Будем считать, что строка — это последовательность чисел от \(1\) до \(m\) (размер алфавита). В C++ char это на самом деле тоже число, поэтому можно вычитать из символов минимальный код и кастовать в число: int x = (int) (c - 'a' + 1) .

Определим прямой полиномиальный хэш строки как значение следующего многочлена:

\[ h_f = (s_0 + s_1 k + s_2 k^2 + \ldots + s_n k^n) \mod p \]

Здесь \(k\) — произвольное число больше размера алфавита, а \(p\) — достаточно большой модуль, вообще говоря, не обязательно простой.

Его можно посчитать за линейное время, поддерживая переменную, равную нужной в данный момент степени \(k\) :

Можем ещё определить обратный полиномиальный хэш:

\[ h_b = (s_0 k^n + s_1 k^ + \ldots + s_n) \mod p \]

Его преимущество в том, что можно написать на одну строчку кода меньше:

Автору проще думать об обычных многочленах, поэтому он будет везде использовать прямой полиномиальный хэш и обозначать его просто буквой \(h\) .

Зачем это нужно?

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

Например, если нужно посчитать хэш от конкатенации строк \(a\) и \(b\) (т. е. \(b\) приписали в конец строки \(a\) ), то можно просто хэш \(b\) домножить на \(k^<|a|>\) и сложить с хэшом \(a\) :

Удалить префикс строки можно так:

А суффикс — ещё проще:

В задачах нам часто понадобится домножать \(k\) в какой-то степени, поэтому имеет смысл предпосчитать все нужные степени и сохранить в массиве:

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

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

Деление по модулю возможно делать только при некоторых k и mod (а именно — при взаимно простых). В любом случае, писать его долго, и мы это делать не хотим.

Для нашей задачи не важно получать именно полиномиальный хэш — главное, чтобы наша функция возвращала одинаковый многочлен от одинаковых подстрок. Вместо приведения к нулевой степени приведём многочлен к какой-нибудь достаточно большой — например, к \(n\) -ной. Так проще — нужно будет домножать, а не делить.

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

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

Лайфхак. Если взять обратный полиномиальный хэш короткой строки на небольшом алфавите с \(k=10\) , то числовое значение хэша строки будет наглядно соотноситься с самой строкой:

Этим удобно пользоваться при дебаге.

Примеры задач

Количество разных подстрок. Посчитаем хэши от всех подстрок за \(O(n^2)\) и добавим их все в std::set . Чтобы получить ответ, просто вызовем set.size() .

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

Сравнение строк (больше-меньше, а не только равенство). У любых двух строк есть какой-то общий префикс (возможно, пустой). Сделаем бинпоиск по его длине, а дальше сравним два символа, идущие за ним.

Палиндромность подстроки. Можно посчитать два массива — обратные хэши и прямые. Проверка на палиндром будет заключаться в сравнении значений hash_substring() на первом массиве и на втором.

Количество палиндромов. Можно перебрать центр палиндрома, а для каждого центра — бинпоиском его размер. Проверять подстроку на палиндромность мы уже умеем. Как и всегда в задачах на палиндромы, случаи четных и нечетных палиндромов нужно обрабатывать отдельно.

Хранение строк в декартовом дереве

Если для вас всё вышеперечисленное тривиально: можно делать много клёвых вещей, если «оборачивать» строки в декартово дерево. В вершине дерева можно хранить символ, а также хэш подстроки, соответствующей её поддереву. Чтобы поддерживать хэш, нужно просто добавить в upd() пересчёт хэша от конкатенации трёх строк — левого сына, своего собственного символа и правого сына.

Имея такое дерево, мы можем обрабатывать запросы, связанные с изменением строки: удаление и вставка символа, перемещение и переворот подстрок, а если дерево персистентное — то и копирование подстрок. При запросе хэша подстроки нам, как обычно, нужно просто вырезать нужную подстроку и взять хэш, который будет лежать в вершине-корне.

Если нам не нужно обрабатывать запросы вставки и удаления символов, а, например, только изменения, то можно использовать и дерево отрезков вместо декартова.

Вероятность ошибки и почему это всё вообще работает

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

Событие, когда два хэша совпали, а не должны, называется коллизией. Пусть мы решаем задачу определения количества различных подстрок — мы добавляем в set \(O(n^2)\) различных случайных значений в промежутке \([0, m)\) . Понятно, что если произойдет коллизия, то мы какую-то строку не учтем и получим WA. Насколько большим следует делать \(m\) , чтобы не бояться такого?

Выбор констант

Практическое правило: если вам нужно хранить \(n\) различных хэшей, то безопасный модуль — это число порядка \(10 \cdot n^2\) . Обоснование — см. парадокс дней рождений.

Не всегда такой можно выбрать один — если он будет слишком большой, будут происходить переполнения. Вместо этого можно брать два или даже три модуля и считать много хэшей параллельно.

Можно также брать модуль \(2^\) . У него есть несколько преимуществ:

Он большой — второй модуль точно не понадобится.
С ним ни о каких переполнениях заботиться не нужно — если все хранить в unsigned long long , процессор сам автоматически сделает эти взятия остатков при переполнении.
С ним хэширование будет быстрее — раз переполнение происходит на уровне процессора, можно не выполнять долгую операцию % .

Всё с этим модулем было прекрасно, пока не придумали тест против него. Однако, его добавляют далеко не на все контесты — имейте это в виду.

В выборе же \(k\) ограничения не такие серьезные:

Она должна быть чуть больше размера словаря — иначе можно изменить две соседние буквы и получить коллизию.
Она должна быть взаимно проста с модулем — иначе в какой-то момент всё может занулиться.

Главное — чтобы значения \(k\) и модуля не знал человек, который генерирует тесты.

Парадокс дней рождений

В группе, состоящей из 23 или более человек, вероятность совпадения дней рождения хотя бы у двух людей превышает 50%.

Более общее утверждение: в мультимножество нужно добавить \(\Theta(\sqrt)\) случайных чисел от 1 до n, чтобы какие-то два совпали.

Первое доказательство (для любителей матана). Пусть \(f(n, d)\) это вероятность того, что в группе из \(n\) человек ни у кого не совпали дни рождения. Будем считать, что дни рождения распределены независимо и равномерно в промежутке от \(1\) до \(d\) .

\[ f(n, d) = (1-\frac) \times (1-\frac) \times . \times (1-\frac) \]

Попытаемся оценить \(f\) :

Из последнего выражения более-менее понятно, что вероятность \(\frac\) достигается при \(n \approx \sqrt\) и в этой точке изменяется очень быстро.

Второе доказательство (для любителей теорвера). Введем \(\frac\) индикаторов — по одному для каждой пары людей \((i, j)\) — каждый будет равен единице, если дни рождения совпали. Ожидание и вероятность каждого индикатора равна \(\frac\) .

Обозначим за \(X\) число совпавших дней рождений. Его ожидание равно сумме ожиданий этих индикаторов, то есть \(\frac \cdot \frac\) .

Отсюда понятно, что если \(d = \Theta(n^2)\) , то ожидание равно константе, а если \(d\) асимптотически больше или меньше, то \(X\) стремится нулю или бесконечности соответственно.

Примечание: формально, из этого явно не следует, что вероятности тоже стремятся к 0 и 1.

Бонус: «мета-задача»

Дана произвольная строка, по которой известным только авторам задачи способом генерируется ответ yes/no. В задаче 100 тестов. У вас есть 20 попыток отослать решение. В качестве фидбэка вам доступны вердикты на каждом тесте. Вердиктов всего два: OK (ответ совпал) и WA. Попытки поделить на ноль, выделить терабайт памяти и подобное тоже считаются как WA.

Цель работы: изучить построение функции хеширования и алгоритмов хеширования данных и научиться разрабатывать алгоритмы открытого и закрытого хеширования при решении задач на языке C++.

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

Теоретические сведения.

Ознакомьтесь с материалом лекции 38.

Задания к лабораторной работе.

Выполните приведенные ниже задания.

Составьте хеш-таблицу, содержащую буквы и количество их вхождений во введенной строке. Вывести таблицу на экран. Осуществить поиск введенной буквы в хеш-таблице.
Постройте хеш-таблицу из слов произвольного текстового файла, задав ее размерность с экрана. Выведите построенную таблицу слов на экран. Осуществите поиск введенного слова. Выполните программу для различных размерностей таблицы и сравните количество сравнений. Удалите все слова, начинающиеся на указанную букву, выведите таблицу.
Постройте хеш-таблицу для зарезервированных слов, используемого языка программирования (не менее 20 слов), содержащую HELP для каждого слова. Выдайте на экран подсказку по введенному слову. Добавьте подсказку по вновь введенному слову, используя при необходимости реструктуризацию таблицы. Сравните эффективность добавления ключа в таблицу или ее реструктуризацию для различной степени заполненности таблицы.
В текстовом файле содержатся целые числа. Постройте хеш-таблицу из чисел файла. Осуществите поиск введенного целого числа в хеш-таблице. Сравните результаты количества сравнений при различном наборе данных в файле.

Указания к выполнению работы.

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

Следует реализовать каждое задание в соответствии с приведенными этапами:

На данный момент могу получить хеш только одного файла данным скриптом:

12.1k 12 12 золотых знаков 37 37 серебряных знаков 68 68 бронзовых знаков

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

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

который принимает параметром имя и возвращает объект, содержащий информацию. Метод объекта

возвращает true, если объект является файлом

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

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

В итоге получается следующий код

в результате работы которого в файле hash будут содержаться хеши всех файлов в текущей директории. Каждый файл будет представлен отдельной строкой в формате

Читайте также: