Темы

Алгоритмы сжатия данных

Data Compression Algorithms · 52 статей

  1. Кодирование Хаффмана: алгоритм сжатия данных

    Кодирование Хаффмана: эффективный алгоритм сжатия данных без потерь. Создание оптимальных префиксных кодов на основе частоты символов. 💻📚

    #3303 · 12 мин чтения

  2. Беспотерьное сжатие данных и методы восстановления исходной информации.

    Безопасное сжатие данных: полное восстановление оригинала без потерь. Узнайте о lossless-алгоритмах, статистической избыточности и ограничениях сжатия.

    #4401 · 13 мин чтения

  3. Поиск подстрок в строках

    Поиск подстрок: алгоритмы, методы и оптимизация. Обзор алгоритмов поиска шаблонов в тексте, влияние кодировки и применение в информатике и биоинформатике.

    #6932 · 3 мин чтения

  4. Библиотека сжатия данных zlib и алгоритм DEFLATE

    zlib и DEFLATE: библиотека для сжатия данных, форматы zlib и gzip. Алгоритм DEFLATE – комбинация LZ77 и кодирования Хаффмана. Эффективная компрессия!

    #8229 · 2 мин чтения

  5. Преобразование Бёрроуза — Уилера: Алгоритм сжатия данных

    Преобразование Бёрроуза-Уиллера (BWT): алгоритм для эффективной компрессии данных. Подготовка текста к сжатию, улучшение работы bzip2 и других методов.

    #8620 · 4 мин чтения

  6. bzip2: Алгоритм и особенности сжатия файлов

    bzip2 – бесплатная программа сжатия файлов с алгоритмом Burrows–Wheeler. Эффективнее LZW/Deflate, но медленнее. Не является архиватором!

    #15391 · 3 мин чтения

  7. Алгоритм сжатия данных без потерь Lempel–Ziv–Welch (LZW)

    LZW: универсальный алгоритм сжатия данных без потерь. Простота реализации, высокая скорость, используется в compress и GIF. История и принцип работы.

    #17217 · 6 мин чтения

  8. Алгоритмы сжатия данных без потерь LZ77 и LZ78

    Бесплатные алгоритмы сжатия данных LZ77 и LZ78 от Лемпеля и Зива: основы GIF, PNG, ZIP. Теория, варианты (LZW, LZMA) и применение.

    #17218 · 9 мин чтения

  9. Утилита diff: Сравнение файлов в UNIX-системах

    diff: утилита UNIX для сравнения файлов. Находит и отображает различия между файлами, используя минимальный набор вставок и удалений. Поддержка бинарных файлов.

    #17956 · 3 мин чтения

  10. Алгоритм поиска строк Ахо-Корасика

    Алгоритм Ахо-Корасика: быстрый поиск всех слов из словаря в тексте. Линейная сложность, эффективен для множественных совпадений. Компьютерные науки.

    #55303 · 2 мин чтения

  11. Программа сжатия compress на основе алгоритма LZW

    compress: утилита сжатия Unix на основе LZW. Медленнее gzip при сжатии, быстрее при распаковке, но с меньшей степенью сжатия. Восстановление с помощью uncompress.

    #59212 · 3 мин чтения

  12. Алгоритм Витерби: поиск наиболее вероятной последовательности скрытых состояний.

    Алгоритм Витерби: поиск наиболее вероятной последовательности скрытых состояний в HMM. Применение в связи, распознавании речи, лингвистике и биоинформатике.

    #63212 · 4 мин чтения

  13. Наибольшая общая подпоследовательность: алгоритмический подход

    Нахождение наибольшей общей подпоследовательности (LCS): алгоритм, применение в информатике, лингвистике, биоинформатике и системах контроля версий (Git).

    #64679 · 4 мин чтения

  14. Алгоритм Кнута-Морриса-Пратта: поиск подстроки за O(n)

    Алгоритм Кнута-Морриса-Пратта (KMP): поиск подстроки в тексте за O(n). Эффективный алгоритм, разработанный Моррисом, Кнутом и Матиясевичем для быстрого поиска строк.

    #67811 · 6 мин чтения

  15. Дельта-кодирование данных: методы и применение.

    Дельта-кодирование: эффективный метод хранения и передачи данных, основанный на фиксации различий. Снижает избыточность и экономит место.

    #78375 · 6 мин чтения

  16. Динамическое программирование временных рядов: алгоритм DTW для измерения сходства последовательностей.

    Динамическое временное искажение (DTW): алгоритм сравнения временных рядов, нечувствительный к скорости. Применение в анализе речи, сигнатур и данных.

    #82419 · 9 мин чтения

  17. Алгоритм сжатия данных без потерь LZMA и LZMA2

    LZMA: алгоритм сжатия данных без потерь. Высокая степень сжатия (лучше, чем bzip2), скорость, поддержка многопоточности и больших словарей (до 4 ГБ). 7-Zip.

    #85204 · 9 мин чтения

  18. Метрики сходства строк в информатике

    Расстояние редактирования: метрика схожести строк в компьютерной лингвистике. Применение в NLP, биоинформатике, автокоррекции. Леве́нштейна – самый популярный вид.

    #92659 · 4 мин чтения

  19. Алгоритм контрольной суммы Adler-32: Описание и особенности

    Adler-32: быстрый алгоритм проверки целостности данных, разработанный Марком Адлером. Используется в zlib и rsync. Альтернатива CRC, быстрее, но менее надежна.

    #94822 · 2 мин чтения

  20. Формат FASTA: структура, сжатие и манипуляции с последовательностями ДНК и белков

    Формат FASTA для ДНК и белков: расшифровка расширений файлов (.fa, .fna, .faa и др.). Простота, парсинг, обработка последовательностей. Сжатие FASTA.

    #103456 · 2 мин чтения

  21. Метод предсказания по частичному совпадению (PPM) и сжатие данных

    PPM: адаптивный алгоритм сжатия данных на основе статистического моделирования и предсказания. Используется для кластеризации и повышения эффективности сжатия.

    #112445 · 3 мин чтения

  22. Алгоритм поиска подстроки Рабина-Карпа

    Алгоритм Рабина-Карпа: быстрый поиск подстроки в тексте с использованием хеширования. Линейная сложность в среднем, эффективен для множественных образцов.

    #133846 · 3 мин чтения

  23. Алгоритм поиска подстроки Бойера-Мура и его модификации

    Алгоритм поиска строк Бойера-Мура: эффективный метод для быстрого поиска подстрок в тексте. История, принцип работы и оптимизация для высокой производительности.

    #133849 · 2 мин чтения

  24. Алгоритм сжатия LZX: история и применение

    LZX: алгоритм сжатия данных семейства LZ77, улучшенная версия DEFLATE. Создан Jonathan Forbes и Tomi Poutanen в 1990-х. Архиватор для Amiga.

    #139979 · 2 мин чтения

  25. Суффиксное дерево: структура и алгоритмы построения

    Суффиксное дерево: структура данных для быстрого поиска подстрок и решения задач со строками. Линейное время, но требует много памяти.

    #145893 · 3 мин чтения

  26. pngcrush: Оптимизация PNG изображений из командной строки

    pngcrush: бесплатная утилита для сжатия PNG без потерь качества. Оптимизация размера файлов, удаление лишних данных и манипуляции с PNG из командной строки.

    #146133 · 3 мин чтения

  27. Инкрементное кодирование: сжатие данных с использованием общих префиксов.

    Инкрементное кодирование (front compression) – алгоритм сжатия данных, эффективный для отсортированных списков. Уменьшает размер, сохраняя общие префиксы.

    #153273 · 1 мин чтения

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

    Словарное кодирование: алгоритмы сжатия данных без потерь, замена строк на ссылки в словаре. Статические и динамические словари, Huffword.

    #156600 · 2 мин чтения

  29. Rzip: Высокоэффективная компрессия данных с большим окном поиска

    rzip: мощная программа сжатия данных, использующая LZ77, Bzip2 и Huffman. Эффективно работает с большими файлами до 900 МБ, высокая степень компрессии.

    #156932 · 4 мин чтения

  30. FASTA: Пакет программ для выравнивания последовательностей ДНК и белков

    FASTA: программа для выравнивания ДНК и белков, разработанная в 1985 году. Формат FASTA – стандарт в биоинформатике. Поиск схожих последовательностей, анализ ДНК.

    #170416 · 6 мин чтения

  31. Преобразование "Перемещение в начало" (MTF): Принципы и применение.

    Преобразование MTF (Move-to-Front): эффективный метод кодирования данных для сжатия. Ускоряет энтропийное кодирование, впервые предложено Б. Рябко в 1980 году.

    #173983 · 3 мин чтения

  32. Адаптивное кодирование Хаффмана: FGK и алгоритм Виттера

    Адаптивное кодирование Хаффмана: сжатие данных в реальном времени без предварительного знания о распределении. FGK и алгоритм Виттера. Онлайн-кодирование.

    #175593 · 1 мин чтения

  33. wildmat: Библиотека сопоставления с образцом от Rich Salz

    wildmat: библиотека сопоставления с шаблонами от Rich Salz. Простой синтаксис, альтернатива регулярным выражениям для поиска по строкам. GitHub, public domain.

    #179332 · 3 мин чтения

  34. PAQ: Алгоритмы сжатия данных без потерь и их особенности.

    PAQ – мощный архиватор данных с высокой степенью сжатия (lossless). Бесплатное ПО, победитель Hutter Prize и Calgary Challenge. Теория и алгоритмы сжатия.

    #181903 · 9 мин чтения

  35. Битовые массивы: компактное хранение и применение

    Битовые массивы: компактное хранение данных в битах. Операции: длина, сравнение, конкатенация. Эффективный подсчет единиц (Hamming weight).

    #191653 · 8 мин чтения

  36. Алгоритм Sequitur: Построение иерархической грамматики из последовательности символов.

    Алгоритм Sequitur: сжатие данных и построение иерархической грамматики из последовательностей символов. Линейная сложность, эффективное применение в ПО.

    #196986 · 2 мин чтения

  37. Алгоритм Смита-Ватермана для локального выравнивания последовательностей

    Алгоритм Смита-Ватермана: поиск схожих участков в последовательностях ДНК и белков. Динамическое программирование, оптимальное локальное выравнивание.

    #233598 · 5 мин чтения

  38. Алгоритм поиска подстрок Хорспула: описание и анализ

    Алгоритм Бойера-Мура-Хорспула: быстрый поиск подстрок в тексте. Упрощение алгоритма Бойера-Мура, сложность O(n) в среднем, эффективен для длинных шаблонов.

    #248096 · 2 мин чтения

  39. Коррекция строк: алгоритмы и сложность вычислений

    Коррекция строк: вычисление минимальной стоимости преобразования одной строки в другую. Алгоритмы для определения расстояния между строками и кратчайшего пути.

    #262530 · 1 мин чтения

  40. Наибольшая общая подстрока: алгоритмы и применение

    Поиск самой длинной общей подстроки: алгоритмы, применение в дедупликации данных и обнаружении плагиата. Решение задачи и обобщение для k строк.

    #286761 · 2 мин чтения

  41. Алгоритм неточного поиска строк: Битап (Shift-Or)

    Алгоритм Битапа: быстрое неточное сопоставление строк. Поиск подстрок с учетом расстояния Левенштейна. Эффективен благодаря битовым операциям. Agrep.

    #293738 · 3 мин чтения

  42. Кратчайшая общая надпоследовательность: алгоритмы и сложность

    Кратчайшая общая надпоследовательность (SCS): определение, алгоритм поиска. Связь с проблемой наибольшей общей подпоследовательности. Информатика.

    #332262 · 1 мин чтения

  43. Кентерберийский корпус: набор данных для тестирования сжатия

    Корпус Кентербери – эталон для тестирования алгоритмов сжатия данных без потерь. 11 файлов, 2.8МБ. Замена Calgary Corpus. Тесты, бенчмарки, сжатие.

    #349639 · 1 мин чтения

  44. Беспотерянное сжатие данных на основе грамматик

    Бесcжатие данных без потерь: алгоритмы на основе грамматик (CFG). Эффективная компрессия, поиск минимальной грамматики, кодирование арифметикой.

    #364259 · 1 мин чтения

  45. Автомат Левенштейна для сравнения строк

    Автомат Левенштейна: мат. модель сравнения строк для поиска ошибок и автокоррекции. Быстрая проверка расстояния Левенштейна в словарях и триях.

    #378866 · 1 мин чтения

  46. Расстояние Дамерау-Левенштейна: метрика редактирования строк

    Расстояние Дамерау-Левенштейна: метрика для измерения разницы между строками. Учитывает вставки, удаления, замены и транспозиции символов. Поиск и исправление ошибок.

    #382956 · 2 мин чтения

  47. Приблизительное сопоставление строк

    Поиск неточного совпадения строк: алгоритмы, методы и типы (онлайн/оффлайн). Нечеткий поиск, приближенное сопоставление строк в тексте и словарях.

    #390490 · 2 мин чтения

  48. Сравнение файлов: методы, инструменты и применение.

    Сравнение файлов: инструменты diff, FileMerge, WinMerge и другие. Обнаружение изменений в коде и документах для повышения эффективности и избежания ошибок.

    #417265 · 3 мин чтения

  49. Алгоритм построения суффиксного дерева Укконена

    Алгоритм Укконена: построение суффиксного дерева за линейное время. Онлайн-алгоритм для эффективного анализа строк, предложенный Эско Укконеном.

    #422006 · 4 мин чтения

  50. Maximal unique match

    #506292 · 2 мин чтения

  51. List of sequence alignment software

    #509786 · 7 мин чтения

  52. Byte pair encoding

    #510997 · 2 мин чтения