В алготитмах проскачила задачка о Сворачивание повторяющихся последовательностей строк

Автор: ArtemGorikov
Дата: 03.03.08

:

Есть поток повторяющихся строк на входе. Нужно распознавать если какая-то строка (или пачка строк) повторяется, и заменять их на число вхождений + тело строки.

Автору не подходят стандартные алгоритмы компрессии, т.к. он хочет сохранить читабельность лога.
Я предложил такое решение

Автор: Tonal-
Дата: 04.03.08

:

1. Дочитываем буфер до максимума (100 строк)
   
2. Делим напаполам — сравниваем первую половину со второй.
   
3. Если равны — свёртываем, сдвигаем остаток в буфере в начало буфера и идём в начало алгоритма.
   
4. Если не равны — отступаем 2 строки от конца буфера — это остаток.
   Если получили пустой буфер выводим его первую строку и идём в начало.
   Если буфер не пуст — идём в п.2

Ну и рекурсивно по сворачиваемому.

Вот что получилось на haskell:

-- данные свёртки будут в дереве
data CompressBlock n s = Empty 
                       | BlockStr s 
                       | BlockBlk n [CompressBlock n s] 
                       deriving (Eq, Show)

-- Половина длинны
half_len xs = length xs `div` 2

-- Поиск половин и выдача дерева свёртки
first_fold []  = (Empty,      [])
first_fold [s] = (BlockStr s, [])
first_fold xs  = first_fold' xs (half_len xs) []

first_fold' []  _ rest    = (Empty, rest)
first_fold' [s] _ rest    = (BlockStr s, rest)
first_fold' (s:xs) 0 rest = (BlockStr s, xs ++ rest)

first_fold' xs half rest 
  | take half xs == take half (drop half xs) 
    = (
      simplify $ BlockBlk 2 (second_fold $ take half xs), 
      drop (half * 2) xs ++ rest)
  | otherwise = first_fold' xs (half - 1) rest

-- рекурсивный проход по сворачиваемому
second_fold []  = []
second_fold [s] = [BlockStr s]
second_fold xs  = simp_list (fld : second_fold rest)
  where
   (fld, rest) = first_fold' xs (half_len xs) []
   
-- Преобразование дерева свёртки в более простой и менее глубокий вид
simplify (BlockBlk _ []) = Empty
simplify (BlockBlk 0 _)  = Empty
simplify (BlockBlk 1 [BlockStr s]) = BlockStr s

simplify (BlockBlk n [BlockBlk m xs]) 
  = simplify $ BlockBlk (n * m) (simp_list xs)

simplify (BlockBlk n (BlockBlk m xs:ys)) | xs == ys 
  = simplify $ BlockBlk (n * (m + 1)) (simp_list xs)

simplify xs = xs

simp_list xs = aggr [ x | x <- map simplify xs, x /= Empty ]

aggr [] = []
aggr (x:y:xs) | x == y = aggr (BlockBlk 2 [x] : xs)
aggr (BlockBlk m x:xs) 
  | x == take len_x xs
    = aggr (BlockBlk (m + 1) x : drop len_x xs)
  where
    len_x = length x
aggr (x:xs) = x : aggr xs

-- Длинна окна
win_len :: Int
win_len = 100

-- Собственно компрессия данных в список свёрток
compact [] = []
compact [s] = [BlockStr s]

compact xs | length xs < win_len 
  = aggr $second_fold xs

compact xs = blks : compact (rest ++ drop win_len xs)
  where
    (blks, rest) = first_fold $ take win_len xs

-- Распечатка свёртки
to_strs Empty = []
to_strs (BlockStr s) = [s]
to_strs (BlockBlk 1 xs) = concat $ map to_strs xs
to_strs (BlockBlk n xs) = (pref_n ++ y) : map (pref ++) ys
  where
    pref_n = "[" ++ show n ++ "] "
    pref   = take (length pref_n) $ cycle " "
    y:ys   = concat $ map to_strs xs

main = do
  file_strs <- getContents
  putStr $ unlines $ to_strs $ BlockBlk 1 $ compact $ lines file_strs

Если у кого-нибудь есть соображения по поводу улучшения кода — будет здорово.

Да в алгоритме есть небольшой косяк — если некоторая последовательность строк повторяется нечётное число раз, то последняя группа в свёртку не попадает. Просто решить эту проблемку как-то не получилось...

Здравствуйте, Tonal-, Вы писали:

T>В алготитмах проскачила задачка о Сворачивание повторяющихся последовательностей строк

Автор: ArtemGorikov
Дата: 03.03.08

:
T>

T>Есть поток повторяющихся строк на входе. Нужно распознавать если какая-то строка (или пачка строк) повторяется, и заменять их на число вхождений + тело строки.

T>Автору не подходят стандартные алгоритмы компрессии, т.к. он хочет сохранить читабельность лога.
T>Я предложил такое решение

Автор: Tonal-
Дата: 04.03.08

:
T>[list=1]
T>

Дочитываем буфер до максимума (100 строк)
T>

Делим напаполам — сравниваем первую половину со второй.
от простого Эрлангиста — А если не напополам, а отсечением головы, там классический вариант с протягиванием по списку, только вместо сортировки компрессия, тогда может и нижний косяк связанный с четностью разрешится?



T>Да в алгоритме есть небольшой косяк — если некоторая последовательность строк повторяется нечётное число раз, то последняя группа в свёртку не попадает. Просто решить эту проблемку как-то не получилось...

Здравствуйте, sergesokolov, Вы писали:
T>>

Делим напаполам — сравниваем первую половину со второй.
S>от простого Эрлангиста — А если не напополам, а отсечением головы, там классический вариант с протягиванием по списку, только вместо сортировки компрессия, тогда может и нижний косяк связанный с четностью разрешится?
Это RLE получается, если я правильно тебя понял.
Тут другой косяк — если у нас повторяются не строки а блоки строк (например чередуются), то RLE ничего не сожмёт.
Например в логе, на котором я отлаживался, логический блок состоит из 3х или 4х строк.
Для того, чтобы применить RLE, нужно об этом знать и предварительно разбивать весь поток на такие логические блоки, а предложенный алгоритм самостоятельно находит повторения.

... << RSDN@Home 1.2.0 alpha 2 rev. 867>>

Здравствуйте, Tonal-, Вы писали:

T>Здравствуйте, sergesokolov, Вы писали:
T>>>

Делим напаполам — сравниваем первую половину со второй.
S>>от простого Эрлангиста — А если не напополам, а отсечением головы, там классический вариант с протягиванием по списку, только вместо сортировки компрессия, тогда может и нижний косяк связанный с четностью разрешится?
T>Это RLE получается, если я правильно тебя понял.
T>Тут другой косяк — если у нас повторяются не строки а блоки строк (например чередуются), то RLE ничего не сожмёт.
T>Например в логе, на котором я отлаживался, логический блок состоит из 3х или 4х строк.
ну я и думал, что не все так просто, я же не знаю что ты сжимаешь просто предложил самое простое.
T>Для того, чтобы применить RLE, нужно об этом знать и предварительно разбивать весь поток на такие логические блоки, а предложенный алгоритм самостоятельно находит повторения.
а если не разбивать а пошагово с каждым новым циклом увеличивать отсекаемую голову на одну строку? и так до твоей половины?

Здравствуйте, sergesokolov, Вы писали:
S>ну я и думал, что не все так просто, я же не знаю что ты сжимаешь просто предложил самое простое.
Ну и прочитай внимательно моё первое сообщение — там вродь все условия чётко изложены — что сжимается, зачем сжимается.

T>>Для того, чтобы применить RLE, нужно об этом знать и предварительно разбивать весь поток на такие логические блоки, а предложенный алгоритм самостоятельно находит повторения.
S>а если не разбивать а пошагово с каждым новым циклом увеличивать отсекаемую голову на одну строку? и так до твоей половины?
И чем это будет лучше предложенного?
Может я чего не понимаю.
Опиши алгоритм полностью, можно псевдокодом или на любимом языке — будет понятней.

Здравствуйте, Tonal-, Вы писали:

T>Здравствуйте, sergesokolov, Вы писали:
S>>ну я и думал, что не все так просто, я же не знаю что ты сжимаешь просто предложил самое простое.
T>Ну и прочитай внимательно моё первое сообщение — там вродь все условия чётко изложены — что сжимается, зачем сжимается.
пардон как обычно читал наискось

T>>>Для того, чтобы применить RLE, нужно об этом знать и предварительно разбивать весь поток на такие логические блоки, а предложенный алгоритм самостоятельно находит повторения.
S>>а если не разбивать а пошагово с каждым новым циклом увеличивать отсекаемую голову на одну строку? и так до твоей половины?
T>И чем это будет лучше предложенного?
Это просто разные стратегии ап и даун, один отчаянный програмист даже уверял, что Шатлл разбился из-за того что его собирали дауном, что мол всегда дает больше ошибок как и все я ему не верю.
T>Может я чего не понимаю.
T>Опиши алгоритм полностью, можно псевдокодом или на любимом языке — будет понятней.
ну попробую, если время будет...