Как сжимают информацию без потери качества?

Answer 1

Всяко и разно. Есть довольно толстая пачка методов - семейство алгоритмов Лемпела-Зива, преобразование Бероуза-Уилера, код Хаффмана, кодирование длин серий, черт в ступе. Гуглите "lossless compression" - узнаете много интересного. .

Answer 2

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