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

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

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

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

Стратегии

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

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

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

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

  • «Почти оптимальное соответствие с образцом, полностью сжатым 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). Цитировать журнал требует | журнал = (помощь)