Сжатое сопоставление с образцом - Compressed pattern matching

В Информатика, сжатое сопоставление с образцом (сокращенно Цена за тысячу показов) - это процесс поиска шаблонов в сжатых данных с небольшой декомпрессией или без нее. Поиск в сжатой строке выполняется быстрее, чем поиск в несжатой строке, и требует меньше места.

Сжатая проблема сопоставления

Если сжатый файл использует кодирование переменной ширины это может быть проблемой: например, пусть «100» будет кодовое слово за а и пусть «110100» будет кодовым словом для б. Если мы ищем появление а в тексте мы могли бы получить в результате также вхождение в кодовое слово б: мы называем это событие ложное совпадение. Таким образом, мы должны проверить, эффективно ли выровнено обнаруженное вхождение на границе кодового слова. Однако мы всегда могли декодировать весь текст, а затем применить классический алгоритм сопоставления строк, но это обычно требует больше места и времени и часто невозможно, например, если сжатый файл размещен в сети. Эта проблема проверки соответствия, возвращаемого сжатым алгоритмом сопоставления с образцом, является истинным или ложным совпадением вместе с невозможностью декодирования всего текста, называется сжатая проблема сопоставления.

Стратегии

Существует множество стратегий для поиска границ кодовых слов и предотвращения полной декомпрессии текста, например:

• Список индексов первого бита каждого кодового слова, где мы можем применить двоичный поиск;
• Список индексов первого бита каждого кодового слова с дифференциальным кодированием, чтобы мы могли занимать меньше места в файле;
• Маска бита, где бит 1 отмечает начальный бит каждого кодового слова;
• Разделение на блоки для частичной и прицельной декомпрессии.

Рекомендации

• Шмуэль Т. Кляйн и Дана Шапира СООТВЕТСТВИЕ ОБРАЗОВАНИЙ В ЗАКОДИРОВАННЫХ ТЕКСТАХ (2003)
• Марек Карпински, Войцех Риттер и Аюми Шинохара. ЭФФЕКТИВНЫЙ АЛГОРИТМ ПОДБОРА ШАБЛОНА ДЛЯ СТРОК С КОРОТКИМИ ОПИСАНИЯМИ. Nordic Journal of Computing 4 (2): стр 172-168 (1997).

внешняя ссылка

• «Почти оптимальное соответствие с образцом, полностью сжатым LZW». CiteSeerX  10.1.1.44.5521.
• Алгоритм сопоставления сжатых шаблонов на основе словаря (PDF), заархивировано из оригинал (PDF) 13 марта 2003 г.
• «Объединяющая структура для сжатого сопоставления с образцом». CiteSeerX  10.1.1.50.1745.
• «Ускорение сопоставления строковых шаблонов с помощью сжатия текста: рассвет новой эры» (PDF). Архивировано из оригинал (PDF) на 2008-08-08. Получено 2009-03-22.
• "Shift-and-подход к сопоставлению с образцом в сжатом LZW тексте". CiteSeerX  10.1.1.15.4609.
• «Алгоритм LZW» (PDF).