Простенький архиватор

Какое отношение архиватор имеет к «сжимал»?

размер файла сжимал

А как это прикрутить если бы у меня был текст например «windows new windows» чтоб слово «windows» заменил цифрой 2 а «new» оставил

Для начала уясните для себя, что вы хотите получить - архиватор или компрессор.

Возник вопрос как модифицировать вот этот вод код

Краткий ответ: никак. Просто нужно весь код удалить. И создать новый код, решающий твою новую задачу.

Если это лабораторка, то в jobs. Иначе потрудись сформулировать задачу.

Задача стоит так, есть файл с текстом, нужно скриптом составить словарь, исходя из количества повторяющихся слов, то что повторяется наибольшее количество раз заменить цифрой. Произвести замену слова на цифру. Поместить словарь вида: «слово:цифра» в начало полученного файла, считать его и произвести обратную замену

Ключевые слова для ввода в гугл:
1)Словарь
2)алгоритм Хаффмана
3)Разделимость словаря
Если ты слишком ленив, то:
1)Зив-Лемпел

разбить текст на слова, посчитать кол-во повторений каждого и присвоить словам уникальные id, потом произвести замену слов на id и дописать в конец(начало) маппинг id->слово.

Блин с реализацией туго у меня. Посчитать еще разберусь а присвоить уникальные ID каким образом можно?

L = ['a', 'b', 'cc', 'a'] # список слов
D = {} # словарь с id 
for w in L: D.setdefault(w, len(D)) # раздаем id

если нужно число повторов, то вот так

for w in L: D.setdefault(w, [len(D),0])[1] += 1

Развил немного вашу идею:

#!/usr/bin/python3

from itertools import groupby
import re

def compress(data):
    for k, g in groupby(data):
        yield len(list(g)), k
        
def decompress(data):
  m = re.findall('([0-9])([a-zA-Z])', data)
  return(''.join([int(d) * c for d, c in m]))

def test():
    result = compress('aaabbcdddd')
    compressed = ''.join('{}{}'.format(*r) for r in result)
    print(compressed)
    decompressed = decompress(compressed)
    print(decompressed)
    
test()

AleksJen

Если товарищ полноценное сжатие со словарём реализовывать будет, то ему надо будет учесть вероятность того, что в его тексте будут повторяющиеся длинные фрагменты, которые будут содержать в себе более короткие слова... В общем, словарь может получиться длинным, а сжатие - в несколько проходов...

Посчитать еще разберусь а присвоить уникальные ID каким образом можно?

уникальный id это просто 1,2,3, etc. Считать кол-во вхождений можно, например, через collections.defaultdict(int).

Решение влоб:

from collections import defaultdict

d = defaultdict(int)
with open("/tmp/testfile") as f:
  for l in f.readlines():
    for w in l.split():
      d[w] += 1

for id, (w, cnt) in enumerate(sorted(d.items(), key=lambda x: x[1], reverse=True)):
  print(id, w, cnt)

Я бы так взял модуль gzip;-)

Да это курсач, мне просто нужно чтоб хотяб немного сжалось)

может хотя бы алгоритм Хаффмана использовать?

from collections import defaultdict

d = defaultdict(int)
with open("C:/1.txt") as f:
    for l in f.readlines():
        for w in l.split():
            d[w] += 1

for id, (w, cnt) in enumerate(sorted(d.items(), key=lambda x: x[1], reverse=True)):
    if cnt>=100:
        D={id:w}

Вот я вот так попробовал, возник вопрос, а как вывести словарь вида «ID:слово» в начало файла, потом например @TEXT и далее сам замененный текст

а раз тебе нужно такое простое, то вот держи:

import Data.List
import Data.Maybe (fromJust)
import qualified Data.Map as M
import Control.Monad (forM_)
import Data.Function (on)
import System.Environment (getArgs)

main = do
    (a:_) <- getArgs
    case a of
        "-d" -> decode
        "-e" -> encode
        _ -> error "unsupported command"

encode = do
    -- считываем данные
    data_ <- getContents
    let  --разбиваем на слова
        w = words data_
        --добавиляем в Map считая кол-во повторений
        m = foldl' (\m v -> M.insertWith (+) v 1 m) M.empty w
        -- сортируем список по убыванию
        s = sortBy (flip compare `on` snd)  (M.toList m)
        -- нумеруем слова соответсвенно их порядку
        s' = map (\((w,_),i) -> (w,i)) (zip s [0..])
        -- создаем новую карту для быстрого поиска индекса
        m' = M.fromList s'
    -- выписываем список слов подряд
    forM_ s' (putStrLn . fst)
    putStrLn "---"            -- разделитель
    forM_ w $ \v -> case M.lookup v m' of
                        Nothing  -> error "impossible  happened"
                        Just idx -> putStr (show idx) >> putStr " "
    putStr "\n"

decode = do
  data_ <- fmap words getContents
  let go_pre :: M.Map Int String -> Int -> [String] -> String
      go_pre m _ ("---":ws) = go m ws
      go_pre m idx (w:ws) = go_pre (M.insert idx w m) (idx+1) ws
      go :: M.Map Int String -> [String] -> String
      go m ws = unwords $ map (\v -> fromJust (M.lookup (read v) m)) ws
  putStrLn (go_pre M.empty 0 data_)

qnikst@localhost ~/tmp/lor/arch $ echo 'windows is so windows' | ./arch -e
windows
is
so
---
0 1 2 0

qnikst@localhost ~/tmp/lor/arch $ echo 'windows is so windows' | ./arch -e | ./arch -d
windows is so windows

Бесплатная версия:

• будет жрать оперативку
• не бинарная
• использует неэффективный алгоритм кодирования
• ломает переносы строк
• будет работать заведомо хуже известных алгоритмов

за платной версией обращаться в jobs.

Нее мне самому нужно написать, причем так чтоб код был попримитивнее, вот и пытаюсь с вашей помощью разобраться как это реализовать.Еще вопрос, почему такая замена не работает

from collections import defaultdict

d = defaultdict(int)
with open("C:/1.txt") as f:
    for l in f.readlines():
        for w in l.split():
            d[w] += 1

for id, (w, cnt) in enumerate(sorted(d.items(), key=lambda x: x[1], reverse=True)):
    if cnt>=100:
        D={id:w}
        with open("C:/1.txt") as y:
            for text in y:
                for key in D.keys():
                    text = text.replace(key, str(D[key]))
                    print text

ну выше пример примитивный (т.е. сделанный по принципу прямого переложения описания алгоритма на язык), вопрос только в переложении того кода на питон.

Вопросы по питону лучше адресовать не мне из меня питонер чуть лучше, чем из AIv хацкелист.

P.S.

with open(«C:/1.txt») as y:

linux.org.ru

ай-ай-ай

а как вывести словарь вида «ID:слово» в начало файла, потом например @TEXT и далее сам замененный текст

Для начала надо прочитать какую нить хорошую и не очень толстую книжку по питону.

Проблема в том что нет времени(

Блин, и правда ваш хацкель многословный... на питоне это будет в неск раз короче.

Могу только посочуйтсвовать. Но как преподаватель, считаю некорректным делать за студентов их курсовые. Полгода Вы валяли дурака а теперь у Вас нет времени?;-)

половина строк это комментарии и представление в таком виде, чтобы ТС понял, или несколько это 1.1? =)

архиватор

man архиватор, компрессор

Чтобы в начало файла помещался словарь типа: «слово:цифра» ну и соответственно это все заменялось туда и обратно, буду рад любому совету.

man адаптивный алгоритм Хаффмена

Да не совсем, я просто не пойму как именно это реализовать, при этом 2 курсовые товарищам я помог написать) ну да ладно)

O_o... какой вуз и специальность, если не секрет?

Проходите по словарю в цикле и выводите что нужно, потом печатаете @ТЕХТ... я не пойму, что Вы не можете тут понять;-)

У тебя rle а делал словарный по принципу
* нади все подстроки длинной от 1 символа повторяющиейся более 1 раза
* найди все свободные буквы в тексте т.е. те что еще в влезают в 1 байт но в тексте не встречаются
* отсортируй по профиту замены подстроки на свободную букву - формат - буква + подстрока + буква + текст_с_заменной_подстрокой_на_букву
* разжатие по принципу a = text[1:].split(text[0]); text = a[1:].join(a[0])
* если следующая буква \x00 то закончить сжатие - я сжимал только текст. Можно изменить формат на тот что \x00 поддерживает
* внимание. сжимать надо только по 1 самой профитной подстроке. И дальше снова искать все подстроки потому что после замены часть подстрок пропала а часть профитов изменилась.
* Процесс сжатия довольно медленный если не знать как эффектновно искать нужные подстроки. Это домашнее задание
Алгоритм хорошо подходит для сжатия исходных кодов программ

или несколько это 1.1? =)

Несколько - это несколько, после выбрасывания коммментариве и приведения к нормальному представлению;-)

Да зачем, просто реализовать метод Ньютона чтобы с помощью него вычислить нелинейное уравнение для меня легче было чем вот это( Да я знаю что читать книги надо(

несколько подразумевает >=2, ты точно уверен?

Навскидку, по кр. мере около 2 (мб и больше). Я правда ХЗ что есть по твоему нормальное представление;-)

если будет лишнее время скинь на мыло, раз уж в этом треде решать за студента задачку не хочется, нормальное представление у меня будет минимум без явного создания промежуточных вычислений, по стандартным haskell coding style. Без использования неэффективных функций из Prelude, которые могут немного сократить место.

Мой тезис в том, что на данной задаче в разница будет меньше, чем в 2 раза (без учета импортов).

Без учета импорта (который у меня один, и тот нужен только для того что бы stdin и argv получить - можно и без этого), без учета #! для баша, вывода справки и пустых строк для «ясности» у меня 10 строк (а все вместе 15 строк, 515 байт). Если я начну экономить строки... ну в 5 строк без учета импорта лягу (я не к тому что все в одну строку, просто там можно будет циклы кой какие убрать, заюзать ФП и пр) - но читаемость кода упадет.

ЗЫ переносы строк я оставляю, а вот лишние пробелы и табы убираю - между словами один пробел.

В общем 4 содержательных строчки, это наверное минимум. При этом ни одной ";", т.е. в каждой строке лишь один операнд;-)

А как это прикрутить если бы у меня был текст например «windows new windows» чтоб слово «windows» заменил цифрой 2 а «new» оставил

«2 new 2»

Этот пример похож на бред без дополнительного описания точного формата входных данных. Раз, у тебя не получается всё враз сделать, то разбивай всё на подзадачи. И выполняй их все от простых к сложным. Как я тебе ранее писал, сначала выкинь весь код ранее написанный (надеюсь тобой). Потом нужно определиться с подзадачами.

1. Формальное описание всех требований: к входному потоку, к сжатому потоку, к разжатому потоку, к словарю; к скорости работы программы, степени интеллектуальности/инновационности использованных алгоритмов, количеству строк и т.д. При этом определить какие требования реализовать в первую очередь, а какие можно опустить (на словах проговорить при сдаче работы).
2. Подзадачи:
   1. Провести анализ входного потока и создать словарь.
   2. Сформировать сжатый поток данных, применив словарь для преобразования входного потока.
   3. Сформировать разжатый поток данных, применив словарь для преобразования сжатого потока.

От простого к сложному: 1, 2.3, 2.2, 2.1.

Для того, чтобы можно было каждую подзадачу решать независимо от других, словарь необходимо разместить в отдельный файл, который будет постоянно находиться на диске. Сначала определись с форматом словаря. В твоем случае, самый простой — нечётные строки хранят id, чётные хранят слова.

$ cat словарь 
0
windows
1
 
2
new

В сжатом потоке хранятся индексы через пробел

$ cat входной\ поток 
windows new windows

$ cat сжатый\ поток 
0 1 2 1 0

$ cat разжатый\ поток 
windows new windows

Тогда новые потоки будут выглядеть так

$ cat словарь 
0
windows
1
 
2
new
4
is
5
so

$ cat входной\ поток 
windows new windows
windows is so windows

$ cat сжатый\ поток 
0 1 2 1 0 3 0 1 4 1 5 1 0

$ cat разжатый\ поток 
windows new windows
windows is so windows

$ ls -aln
итого 24
drwxrwxr-x 2 500 500 4096 июня   8 18:46 .
drwxrwxr-x 3 500 500 4096 июня   8 18:13 ..
-rw-rw-r-- 1 500 500   41 июня   8 18:45 входной поток
-rw-rw-r-- 1 500 500   41 июня   8 18:46 разжатый поток
-rw-rw-r-- 1 500 500   25 июня   8 18:49 сжатый поток
-rw-rw-r-- 1 500 500   29 июня   8 18:44 словарь

на кодирование и декодирование и вывод?

Чтобы сжатый поток занимал меньше места, его удобнее хранить плотным потоком без пробелов. Только вначале нужно указать какое количество цифр содержиться в индексе. В данном примере размерность словаря = «1».

$ cat сжатый\ поток 
0 1 2 1 0 3 0 1 4 1 5 1 0
$ cat сжатый\ поток\ без\ пробелов 
1 0121030141510

$ ls -aln сжатый*
-rw-rw-r-- 1 500 500 25 июня   8 18:49 сжатый поток
-rw-rw-r-- 1 500 500 15 июня   8 20:43 сжатый поток без пробелов

Да. В варианте с минимальным числом строк первым операндом читаем файл (как список списков слов, 36 символов), вторым делаем словарь преобразования в зависимости от режима (154 символа, и там есть небольшое читерство), третьим в случае запаковки выводим заголовок (92 символа), четвертым конвертируем и выводим данные (52 символа).

Да, я знаю про ПЕП8, и я по некоторым пунктам с ним не согласен - у меня на ноуте ширина окна 166 символов, и я не понимаю нафига я должен резать строки и отдавать правую половину монитора под пустоту (со своим кодом работаю в основном я сам).

Ну а обычный вариант, который на 10 содержательных строк, настолько скучный что о нем и говорить неинтересно;-)

ЗЫ какой нить руби будет небось еще лаконичней;-)

только не «операнд» а «оператор» - совсем уработался;-((((

Ладно, я это тут оставлю - м.б. ТС-а оно сподвигнет на подвиги;-)

#!/usr/bin/python
import sys

if len(sys.argv)!=2 or not sys.argv[1] in ('-p', '-u'): print 'usage: ./arch.py -p (pack)|-u (unpack)'; sys.exit()

L, D = [ l.split() for l in sys.stdin ], {}
if sys.argv[1]=='-u': D = dict([ (str(i),w) for i, w in enumerate(L.pop(0)) ])
else: print ' '.join([ w for w in sum(L, []) if not w in D and D.setdefault(w, len(D))+1 ])
for l in L: print ' '.join([ str(D[i]) for i in l ])

читер, у тебя формат файла другой. в целом круто, вариант с аналогичным форматом в котором алгоритмическая часть < чем на 8 строк попробую привести как будет время за компом нормально посидеть.

Это самый простой формат позволяющий учитывать переносы строк.

ох тыж блин :) у меня ж ещё как в хафмане кол-во вхождений слов считается и тем кто больше выдается меньший номер :) что формально можно в дальшейшем переводить в битовое представление одной доп функцией.

О да... у меня на это уйдет еще одна строчка;-)

main = getargs >>= \(x:_) -> putstrln =<< fmap (case x of "-d" -> go true ; "-e" -> go false ; _ -> error "usage foobar") getcontents
        
go tp d = unlines $ map (unwords . map (fromjust . (`m.lookup` m)) . words) t
  where (m,h,t) | tp =
          let (_,l,m) = foldl' (\(i,l,m) v -> case m.lookup v m of nothing -> (i+1,v:l, m.insert v (show i) m) ; _ -> (i,l,m)) (0,[],m.empty) (words d)
          in (m,l,lines d)                                                              
                | otherwise = (\(a,b) -> (a,[],b)) $ ((m.fromlist . (zip [show x | x <- [0..]]) . words . head) &&& tail)  (lines d)

6 строк :) нормально, с учетом разделения чистых и не-чистых вычислений.

Впрочем, логично, что скриптового языка меньше, но термин «многословый» минимум не в тему.

Не, ну по байтикам - у меня 268, у тебя 618;-) Дык и задача ж простая.

Наш Гуру, который последний год играется с хаскелем и даже под ГПГПУ на нем пишет, говорил что ЯП оч. прикольный с оч. интересными идеями, но код примерно вдвое длинней аналогичного питоньего.

Я со временем наверное хочу его попристальней поглядеть - не для использования, а для получения новых идей.