Реферат: Новый способ архивирования данных передаем фильм с помощью sms

НОВЫЙ СПОСОБ АРХИВИРОВАНИЯ ДАННЫХ

Передаем фильм с помощью SMS.


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


Принцип алгоритма очень простой (основан на моем принципе создания вселенной), легко проверить работу вручную.


Разрешаю бесплатно пользоваться алгоритмом для разработки любых программ и чипов которые идут на благо людям и природе (особенно запрещаю использование алгоритма в устройствах которые возможно будут вживляться, воздействовать на человека и живые существа).

Данному алгоритму нет аналогов в мире, что подтверждено протоколом Российского комитета по регистрации рекордов планеты «Интерстронг» 7 ноября 2008 г. «Самый эффективный алгоритм сжатия информации в мире».




Впервые алгоритм был представлен на научной конференции «Научное программное обеспечение в образовании и научных исследованиях» в Санкт-Петербурге 30 января 2008 года.


Представьте безразмерные флешки, вечные цифровые фотоаппарты камеры, передача данных в космосе, и.т.п.


^ Принцип работы алгоритма сжатия данных:


Для примера представим часть набора двоичного кода, который был взят из архива (сжатого ZIP архиватором).


00110100100101101010001001101111001010100110000010


Способ преобразования двоичного кода

00 – 0

01 – 1

10 – 01

11 – 10

Если в конце остается 1 бит, то оставляем без преобразования


Распишем преобразование данных:


Исходный код:

00 11 01 00 10 01 01 10 10 10 00 10 01 10 11 11 00 10 10 10 01 10 00 00 10 (50 бит 100%)

После 1-го преобразования:

01 01 00 11 10 10 10 10 01 10 11 01 00 01 01 01 10 10 00 1 (39 бит 78%)

После 2-го преобразования:

11 01 00 10 10 10 11 01 10 10 11 10 10 10 1 (29 бит 58%)

После 3-го преобразования:

10 10 01 01 01 10 10 10 11 00 10 10 11 (26 бит 52%)

После 4-го преобразования:

01 01 11 10 10 10 11 00 01 01 10 (22 бита 44%)

После 5-го преобразования:

11 10 01 01 01 10 01 10 1 (17 бит 34%)

После 6-го преобразования:

10 01 11 10 11 01 1 (13 бит 26%)

После 7-го преобразования:

01 11 00 11 01 1 (11 бит 22%)

После 8-го преобразования:

11 00 10 11 (8 бит 16%)

После 9-го преобразования:

10 00 11 0 (7 бит 14%)

После 10-го преобразования:

01 01 00 (6 бит 12%)

После 11-го преобразования:

11 0 (3 бита 6%)

После 12-го преобразования:

10 0 (3 бита 6%)

После 13-го преобразования:

01 0 (3 бита 6%)

После 14-го преобразования:

10 (2 бита 4%)

После 15-го преобразования:

01 (2 бита 4%)

После 16-го преобразования:

1 (1 бит 2%)


Итого из приведенного выше примера получаем: 6.125% средний процент сжатия информации за 1 шаг преобразования.


Способ распаковки архива:


Берем преобразованную цепочку к примеру:

01 01 00 11 10 10 10 10 01 10 11 01 00 01 01 01 10 10 00 1

строим дерево всех возможных вариантов распаковки и сравниваем с исходным:

00 11 01 00 10 01 01 10 10 10 00 10 01 10 11 11 00 10 10 10 01 10 00 00 10


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


Можно сжать примерно до 45 байт (фильм в SMS) служебной информации.


Рекомендации по написанию архиватора.

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


Жмем пакетами, чем больше получится сжать, тем лучше, подбирается оптимальный размер скорость/быстродействие.


Я строил граф по 3 цепочкам

Берм преобразованный кусок:


01 01 00


00 01 00 01 00 00 – первая цепочка преобразуем 0 ->00 1->01

(вариант самой оптимальной распаковки)

-- 10 -- -- (вторая цепочка -вариант распаковки по 2 битам – 01 –> 10 10 –> 11 - 00 и 11 не прописываем в графе)

11 0 (третья цепочка -вариант распаковки по 2 битам со смещением на 1 бит 01 – >10 10 –> 11 - 00 и 11 не прописываем в графе).

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


Потом принцип распаковки очень простой берем сжатый пакет, строим все варианты распаковки и берем путь в графе с нужным номером и.т.д.


Перешлите алгоритм знакомым программистам.


С уважением,

Кириченко Олег Юрьевич

infosave@mail.ru


Пример программы на php

<? 
global $mas_all,$str_arc,$str_out,$count,$offset; 

function tree($n_mas,$len) 
{  
global $str_arc,$str_out; 
global $mas_all; 
global $count; 
global $offset,$len_doarc,$len_arc; 
if($len==0) $len++; 
for($i=0;$i<$len;$i++)  
{ 
//отслеживаем длинну те что уже длинее положенного удаляем 
if($len_arc-$mas_all[$n_mas-$i]['num']>0) 
if(strlen($mas_all[$n_mas-$i]['str'])-$mas_all[$n_mas-$i]['num']<=$len_doarc-$len_arc) 
{ 
$count++; //создаю новый элемент массива 
$mas_all[$count]['str']=''; 
$mas_all[$count]['num']=1;  
$mas_all[$count]['str'].=$mas_all[$n_mas-$i]['str'].'0'.$str_arc[$mas_all[$n_mas-$i]['num']]; //складываю массивы 
$mas_all[$count]['num']=$mas_all[$count]['num']+$mas_all[$n_mas-$i]['num']; 
} 
if($len_arc-$mas_all[$n_mas-$i]['num']>1) 
if(strlen($mas_all[$n_mas-$i]['str'])-$mas_all[$n_mas-$i]['num']<=$len_doarc-$len_arc) 
if($str_arc[$mas_all[$n_mas-$i]['num']].$str_arc[$mas_all[$n_mas-$i]['num']+1]!='11'&&$str_arc[$mas_all[$n_mas-$i]['num']].$str_arc[$mas_all[$n_mas-$i]['num']+1]!='00')   
{ 
$count++; 
$mas_all[$count]['str']=''; 
$mas_all[$count]['num']=0; 
if($str_arc[$mas_all[$n_mas-$i]['num']].$str_arc[$mas_all[$n_mas-$i]['num']+1]=='10') 
{ $mas_all[$count]['str'].=$mas_all[$n_mas-$i]['str'].'11';  $mas_all[$count]['num']=$mas_all[$n_mas-$i]['num']+2;  
//echo '№'.$count.' --- '.$n_mas.' '.$i.' --- '.$mas_all[$n_mas-$i]['num'].'
'; 
} 
if($str_arc[$mas_all[$n_mas-$i]['num']].$str_arc[$mas_all[$n_mas-$i]['num']+1]=='01') 
{ $mas_all[$count]['str'].=$mas_all[$n_mas-$i]['str'].'10';  $mas_all[$count]['num']=$mas_all[$n_mas-$i]['num']+2;  
//echo '№'.$count.' --- '.$n_mas.' '.$i.' --- '.$mas_all[$n_mas-$i]['num'].'
';  
} 
} 


} 
for($i=0;$i<$len;$i++) {unset($mas_all[$n_mas-$i]);} 

if ($mas_all[$count]['num']<$len_arc) tree($count,$count-$n_mas); 

} 

$filename='c:/1.txt'; 
$fd=fopen($filename,"r"); 
//$dataf = fread ($fd, filesize ($filename)); 
$dataf = fread ($fd,8); // Указываем количество байт с файла 
fclose ($fd); 
    $str_gz=$dataf; 
    $len=strlen($dataf); 
    echo 'Длинна пакета '.$len.' байт
'; 
    $i=0; 
    $str_out=''; 
    $str_anpac=''; 
    while($i<$len) 
    {    
        $byte_in=decbin(ord($str_gz[$i])); 
        while(strlen($byte_in)<8) $byte_in='0'.$byte_in;     
        $str_out.=$byte_in; 
        $i++; 
    } 
$len_out=strlen($str_out); 
$i=0; 
$str_arc=''; 
    while($i<$len_out) 
    {    
if ($str_out[$i].$str_out[$i+1]=='00') { $str_arc.='0'; $str_anpac.='1';} 
if ($str_out[$i].$str_out[$i+1]=='01') { $str_arc.='1'; $str_anpac.='1';} 
if ($str_out[$i].$str_out[$i+1]=='10') { $str_arc.='01'; $str_anpac.='00';} 
if ($str_out[$i].$str_out[$i+1]=='11') { $str_arc.='10'; $str_anpac.='00';} 
$i++; 
$i++; 
    } 
echo $str_arc.'
'; 
echo 'До сжатия(бит)'.strlen($str_out).' После сжатия(бит)'.strlen($str_arc).' в '.strlen($str_out)/strlen($str_arc); 

$len_out=strlen($str_arc); 

//строим дерево комбинаций 

$byte_arc=''; 
$byte_unpac=''; 
$i=0; 
        $offset=8-(($len_out/8)-floor($len_out/8))*8;  
        if($offset<8&&$offset>0) { echo 'Offset='.$offset;  
        } 

echo '
'.$str_out.'
'; 
echo $str_arc.'
'; 

echo 'Все варианты распаковки'." "; 
$len_doarc=strlen($str_out); 
$len_arc=strlen($str_arc); 
$count=0; 
$cn=0; 
$mas_all[0]['num']=0; 
$mas_all[0]['str']=''; 
tree(0,0);     
foreach ($mas_all as $key => $value) { 
if($mas_all[$key]['num']<$len_arc) unset($mas_all[$key]); else { 
     
$mas_out[$cn]=$mas_all[$key]['str']; 
if($mas_all[$key]['str']==$str_out) $num_array=$cn; 
$cn++; 
} 

 } 
print_r($mas_out); 
echo '
 Всего вариантов распаковки '.count($mas_out); 
echo '
 Номер варианта '.$num_array; 

unset($mas_all); 
unset($mas_out); 
?>