#haskell #compression #bitstring
Вопрос:
Учитывая тип битовых нитей в Хаскелле:
data Bits = O Bits | I Bits | Nil
Существуют ли алгоритмы сжатия, которые дают удовлетворительные результаты (особенно когда речь идет о повторяющихся подстроках), которые очень малы и просты в реализации в виде идиоматических рекурсивных функций Хаскелла? В идеале алгоритм должен работать с битовыми строками, а не со списками символов; таким образом, он должен идентифицировать повторяющиеся подстроки произвольной длины и позиции. Я прошу ссылки (т. Е. Имена/цитаты); нет необходимости публиковать полный код.
Комментарии:
1. Тем, кто проголосовал за закрытие: обратите внимание, что я не прошу рекомендаций по программному обеспечению или библиотекам, я прошу назвать алгоритмы. Это противоречит руководящим принципам?
2. Я думаю, что вопрос немного основан на мнении: что значит, чтобы алгоритм был «простым» и «идиоматичным», и каковы «удовлетворительные результаты»?
3. Кроме того, вы имеете в виду последовательные повторения или дублированные подстроки в целом?
4. @Noughtmare Я имею в виду алгоритм, который, возможно, может быть реализован в нескольких рекурсивных функциях без множества зависимостей, используя в основном сопоставление шаблонов. Но как еще я могу это определить? Если бы я просто попросил алгоритм сжатия в целом, есть много таких, которые я легко могу найти в Google, так что этот вопрос не понадобился бы. Но мне действительно нужен тот, который может быть реализован в нескольких строках обычного Хаскелла. И я имею в виду дублированные подстроки в целом, в основном я хочу, чтобы он мог обнаруживать повторяющиеся слова и сжимать их.
5. Кодировка длины выполнения очень проста в определении и хорошо работает, если у вас есть длинные повторяющиеся строки. ( en.wikipedia.org/wiki/Run-length_encoding )