Сопоставление сжатого шаблона
В информатике ) — сопоставление сжатых данных (сокращенно CPM это процесс поиска шаблонов в сжатых данных с небольшой декомпрессией или без нее. Поиск в сжатой строке выполняется быстрее, чем поиск в несжатой строке, и требует меньше места.
Проблема сжатого соответствия
[ редактировать ]Если в сжатом файле используется кодировка переменной ширины, это может стать проблемой: например, пусть «100» будет кодовым словом для a , а «110100» — кодовым словом для b . Если мы ищем вхождение a в тексте, мы можем получить в результате также вхождение внутри кодового слова b : мы называем это событие ложным совпадением . Поэтому нам нужно проверить, эффективно ли обнаруженное вхождение выровнено по границе кодового слова. Однако мы всегда могли бы декодировать весь текст, а затем применить классический алгоритм сопоставления строк , но это обычно требует больше места и времени и часто невозможно, например, если сжатый файл размещен в Интернете. Эта проблема проверки совпадения, возвращаемого алгоритмом сопоставления сжатого шаблона, является ли оно истинным или ложным совпадением, а также невозможность декодирования всего текста называется проблемой сопоставления сжатого образца . [1]
Стратегии
[ редактировать ]Существует множество стратегий для нахождения границ кодовых слов и предотвращения полной распаковки текста, например:
- Список индексов первого бита каждого кодового слова, к которому мы можем применить двоичный поиск;
- Список индексов первого бита каждого кодового слова с дифференциальным кодированием, чтобы мы могли занимать меньше места в файле;
- Маска бита , где бит 1 отмечает начальный бит каждого кодового слова;
- Разделение на блоки для частичной и целенаправленной декомпрессии.
Были предложены алгоритмы, обеспечивающие время работы, которое логарифмически растет с увеличением длины строки и шаблона. [2]
Ссылки
[ редактировать ]- ^ Джоэл Грус (2019). Наука о данных с нуля. Первые принципы работы с Python . О'Рейли Медиа. ISBN 9781491901427 . Архивировано из оригинала 17 августа 2021 г. Проверено 26 августа 2021 г.
- ^ Артур Еж (25 июня 2013 г.). «Более быстрое сопоставление полностью сжатых образов путем повторного сжатия». arXiv : 1111.3244 [ cs.DS ].
- Шмуэль Т. Кляйн и Дана Шапира СООТВЕТСТВИЕ ОБРАЗЦА В ТЕКСТАХ, ЗАКОДИРОВАННЫХ ХАФФМАНОМ (2003)
- Марек Карпински, Войцех Риттер и Аюми Шинохара. ЭФФЕКТИВНЫЙ АЛГОРИТМ СООТВЕТСТВИЯ ШАБЛОНУ ДЛЯ СТРОК С КРАТКИМИ ОПИСАНИЯМИ. Северный журнал вычислений 4 (2): стр. 172–168 (1997).
Внешние ссылки
[ редактировать ]- «Почти оптимальное сопоставление с образцом, полностью сжатым LZW». 1999: 316–325. CiteSeerX 10.1.1.44.5521 .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - Алгоритм сопоставления сжатого шаблона на основе словаря (PDF) , заархивировано из оригинала (PDF) 13 марта 2003 г.
- «Объединяющая структура для сопоставления сжатых шаблонов». 1999: 89–96. CiteSeerX 10.1.1.50.1745 .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - «Ускорение сопоставления строковых шаблонов за счет сжатия текста: начало новой эры» (PDF) . Архивировано из оригинала (PDF) 8 августа 2007 г. Проверено 22 марта 2009 г.
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - «Сдвиг-и подход к сопоставлению с образцом в сжатом тексте LZW». 1999: 1–13. CiteSeerX 10.1.1.15.4609 .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - «Алгоритм LZW» (PDF) .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь )