Сжатие текста с использованием рекурсивных N-грамм - PullRequest
Новая
       29

Сжатие текста с использованием рекурсивных N-грамм

2 голосов
/ 04 января 2012

Я просто разбирался с идеей разбить большую группу текста на одно целое с помощью рекурсивного 2-граммового хранилища, пока не останется только одно значение. 

table pair
{
    id
    first_parent_id (points to -> this.id)
    second_parent_id (points to -> this.id)
}

Например, вВ следующем коде у меня есть предложение из 11 слов (двенадцать с точкой).Я мог бы сохранить каждую пару слов в базе данных («this» + «is» = ID # 1), а затем сохранить каждый набор из двух пар слов в базе данных (1 + 2 = ID # 7) и повторять до тех пор, пока я не доберусь доосталось только одно слово - это будет идентификатор 12. 

This is my group of words which I plan to compress.
---1---|--2-----|--3-----|-----4-|----5--|-------6-
-------7--------|--------8-------|-------9---------
----------------10---------------11----------------
------------------------12-------------------------

Затем, используя число "12", мы можем работать в обратном направлении (если у нас один и тот же набор данных) 

------------------------12-------------------------
----------------10---------------11----------------
-------7--------|--------8-------|-------9---------
---1---|--2-----|--3-----|-----4-|----5--|-------6-
This is my group of words which I plan to compress.

Покадля сжатия / распаковки каждой строки потребовалось бы огромное количество работы - кажется, что она может найти применение в какой-либо архивной работе, где необходимо хранить содержимое, - но никогда не читается, за исключением редких случаев, когда процесс распаковки не выполняется.это не проблема.

Правильно ли я думаю об этом?Будет ли возможное количество последовательностей слов слишком велико, чтобы их хранить таким образом?(Представьте себе документ из 500 слов).

Ответы [ 2 ]

2 голосов
/ 08 января 2012

Зачем вам нужны "слова диграммы", чтобы добиться сжатия? Если это не является строго обязательным требованием, существуют различные способы сжатия текстовых данных с разными сценариями. В основном это называется предварительной обработкой словаря. Вот список, который можно применить в вашем случае:

  1. Подсчитывать вхождения слов и сортировать их по частотам в порядке убывания. Вы можете использовать верхние N слов с вашим пользовательским методом кодирования, где N может быть настроено пользователем. Вы даже можете оптимизировать N с помощью динамического программирования или чего-то подобного. При фактическом кодировании кодировать флаг, чтобы указать следующий символ, является ли это словарное слово или непосредственно закодированное слово.

  2. Построение гистограммы комбинаций символов биграммы или триграммы (включая пробелы, знаки пунктуации и т. Д.). Затем используйте неиспользуемые значения байтов для кодирования тех биграмм или триграмм, которые часто видны. Вы даже можете использовать рекурсивные методы, чтобы сканировать снова и снова, чтобы уменьшить исходный файл.

В вашем случае, это неэффективно, если вы рассмотрите вышеописанные методы. Потому что, кажется, вы не учли, что вам нужны действительно большие данные для декодирования ваших закодированных данных. Чтобы понять большинство идей сжатия, лучше написать очень простую тестовую программу для анализа ее результатов. В итоге вы получите более сильные и стабильные алгоритмы.

Вот некоторые словарные препроцессоры, которые приходят мне в голову, чтобы просто дать вам ссылку:

  1. XWRT : один из современных препроцессоров словаря.
  2. DICT : Препроцессор высокопроизводительного FreeArc архиватора (с открытым исходным кодом). Об этом есть статья . К сожалению, это на русском языке.
  3. KWC : Простой препроцессор тестового словаря, который заменяет 6-граммовые коды на словарные коды. Смотрите здесь для обсуждения.
  4. bpe2 V3 : основано на замене n-грамм. Другие версии: V1 , V2 . Также есть обсуждение об этом.
1 голос
/ 04 января 2012

Короче говоря, да, возможное количество последовательностей, вероятно, будет слишком велико, чтобы сделать это эффективно.Большая проблема заключается в том, что эти отображения слов и n-граммы, следующие за каждым из этих отображений, должны где-то храниться, что значительно перевесит любую экономию фактического «сжатия».

...