Префиксное кодирование, иногда называемое фронтальным кодированием, является еще одним алгоритмом, который пытается удалить дублированные данные, чтобы уменьшить их размер. Его принципы просты, однако этот алгоритм трудно реализовать. Чтобы понять почему, сначала давайте взглянем на его природу.
Посмотрите на следующий словарь.
использовать
используемую
полезную
полезность
uselss
бесполезно
бесполезность
Вместо того чтобы хранить все эти слова в виде простого текста или передавать их по сети, мы можем сжимать (кодировать) их с помощью префиксного кодирования.
Понятно, что каждое из этих слов начинается с префикса «use», который также является первым словом в списке. Таким образом, мы можем легко сжать их в следующий массив.
$data = array( 0 => 'use', 1 => '0d', 2 => '0ful', 3 => '0fully', 4 => '0less', 5 => '0lessly', 6 => '0lessness', );
Понятно, что это не лучшее сжатие, и мы можем пойти еще дальше, используя не только первое слово в качестве префикса.
$data = array( 0 => 'use', 1 => '0d', 2 => '0ful', 3 => '2ly', 4 => '0less', 5 => '4ly', 6 => '4ness', );
Теперь сжатие стало лучше, и хорошая новость в том, что декомпрессия — довольно простой процесс. Однако самой сложной частью является само сжатие. Проблема в том, что довольно сложно выбрать подходящий префикс. В нашем первом примере это просто, но на практике большую часть времени мы будем иметь более разнородные данные. Действительно, процесс сжатия может быть очень сложным для случайно сгенерированных данных, и алгоритм будет не только медленным, но и сложным в реализации.
Хорошо, что этот алгоритм можно использовать во многих случаях, если мы заранее знаем формат данных. Итак, давайте рассмотрим три примера, где этот алгоритм может быть очень удобным.
заявка
Вот три примера префиксного кодирования. Как я уже говорил выше, процесс сжатия может быть очень сложным для случайных данных, поэтому рекомендуется использовать его, только если вы заранее знаете формат входных данных.
Дата и время префиксы
Мы, люди, часто пропускаем первые две цифры года, поэтому, например, мы не всегда пишем 1995 или 1996, но мы используем более короткие — ’95 и ’96. Таким образом, годы могут быть закодированы с помощью более коротких строк.
входные данные: (1991, 1992, 1993, 1994, 1995, 1996 годы;
выходные данные: (91, 92, 93, 94, 95, 96)
Проблема в том, что при небольших изменениях входного потока мы можем перепутать декодер. Таким образом, если мы добавим годы 21-го века, мы потеряем уникальность данных.
входные данные: (1998, 1992, 1999, 2011, 2012)
выходные данные: (98, 92, 99, 11, 12)
Теперь декодер может декодировать два последних значения как (1911, 1912), так как «19» считается префиксом. Поэтому мы должны заранее знать, что наш префикс абсолютно равен для каждого из значений. Если нет, формат кодирования должен быть другим. Например, мы также можем закодировать префикс с помощью специального маркера.
ввод: (1998, 1992, 1932, 1924, 2001, 2012)
вывод: (№ 19, 98, 92, 32, 24, № 20, 01, 12)
Как только декодер прочитает символ #, он будет знать, как декодировать следующий номер в качестве префикса.
Это может быть использовано на практике для форматов даты и времени. Допустим, у нас есть некоторые значения даты и времени, но мы знаем, что все они находятся в одном и том же дне.
2012-01-31 15:33:45
2012-01-31 16:12:11
2012-01-31 17:32:35
2012-01-31 18:54:34
Очевидно, что мы можем опустить часть даты этих строк и отправить (сохранить) только время. Еще раз, мы должны быть абсолютно уверены, что все эти значения находятся в одном дне. Если нет, мы можем использовать стратегию кодирования предыдущего примера.
Телефонные номера
Телефонные номера являются типичным случаем кодирования префикса. Не только международный код, но и операторы мобильной связи используют префиксы для своих телефонных номеров. Таким образом, если нам нужно перевести телефонные номера, скажем, из Великобритании , мы можем заменить ведущий «+44» на что-то более короткое.
Если вам случится кодировать телефонную книгу для мобильного устройства, вы можете сэкономить место, сжимая данные с использованием префиксного кодирования, и, таким образом, у пользователя будет больше места и он будет хранить больше телефонных номеров на своем мобильном устройстве.
Префиксы телефонных номеров также можно использовать для нормализации базы данных. Таким образом, вы можете хранить их в отдельной таблице БД и оставлять только уникальные номера из телефонной книги.
Гео координаты
Используя тот же пример из моего предыдущего поста, мы можем отправить координаты GEO, удалив общий префикс для больших уровней масштабирования. Действительно, когда вам нужно отправить много маркеров в ваше картографическое приложение, вы можете ожидать, что все эти маркеры будут достаточно близко друг к другу при большом уровне масштабирования.
При больших уровнях масштабирования мы можем ожидать, что маркеры будут иметь одинаковый префикс.
Теперь координаты этих точек могут иметь общий префикс, как в примере ниже со станциями метро.
LatLon (40.762959, -73.985989)
LatLon (40.761886, -73.983629)
LatLon (40.762861, -73.981612)
LatLon (40.764616, -73.98056)
Мы видим, что все эти точки GEO имеют одинаковый префикс (40,76x, -73,98x), поэтому мы можем отправить префикс только один раз.
Префикс: (40,76, -73,98)
Данные:
LatLon (2959,5989)
LatLon (1886,3629)
LatLon (2861,1612)
LatLon (4616,056)
Это только три примера кодирования префикса, и этот алгоритм очень полезен при передаче однородных данных.
Суффикс Кодировка
Суффиксное кодирование является практически тем же алгоритмом, что и префиксное кодирование, с той небольшой разницей, которую мы используем для кодирования дублирующих суффиксов. Как и в приведенных ниже примерах, суффиксное кодирование может быть полезно при замене повторяющихся суффиксов фамилии.
Джонсон
Кларк
Джексон
Или названия компаний.
Apple Inc.
Google Inc.
Yahoo! Inc.
Здесь мы можем заменить «Inc.» с чем-то еще, но короче.
Похожие сообщения:
- Компьютерные алгоритмы: сжатие данных с относительным кодированием
- Компьютерные алгоритмы: сжатие данных с использованием кодирования длин серий
- Компьютерные алгоритмы: сжатие данных с кодированием диаграмм и подстановкой шаблонов
Источник: http://www.stoimen.com/blog/2012/02/06/computer-algorithms-data-compression-with-prefix-encoding/