Информационный портал
«SoftTime-INFO»
|
| Задачи | 22. Кодирование и декодирование данных (11.06.2007). 22. Кодирование и декодирование данных (11.06.2007). Автор - Trianon
Категория - 3
Имеется некий набор строк, содержащие произвольные символы. Набор предназначен для передачи через транспортный канал, который способен транслировать только определенный алфавит.
Одним из решений такой поблемы (например в почтовых стандартах) является применение методики кодирования base64, при которой алфавитом из 64 символов передаются любые бинарные (т.е. из байтов со значениями 0..255) данные. Строки при этом, как известно вырастают на величину (log(256)/log(64)-1)*100% = 33% по стравнению с исходной длиной.
Основное требование Заказчика не устраивают накладные расходы в 33%. Он предлагает использовать алфавит из 85 символов текста, и согласен на рост в (соответственно (log(256)/log(85)-1)*100% ) 25% от исходной длины. И ни байтом больше.
Требуется разработать такие функции $text = user_encode($data, $abc) и $data = user_decode($text, $abc), которые бы кодировали и декодировали указанные данные ($data) в текст ($text) символами из строки с предложенным алфавитом ($abc), и укладывались в 25% overhead.
Дополнительные требования a) кодированные строки заказчик собирается не только пересылать, но и хранить. И ему было бы крайне удобно если результаты строкового сравнения на больше меньше равно оригинальных данных и кодированных строк были равнозначными. То есть если данные1< данные2 то и код1< код2 .
б) поскольку часть интерфейсов, работающих с таким представлением данных, позже вероятно будет реализована на других языках, а возможно даже в микроконтроллере, заказчику бы не хотелось, чтобы в реализации user_encode и user_decode применялись какие-либо нестандартные функции, отличные от ord, chr, substr, strpos и intval, и крайне желательно, чтобы было исключено применение операций с плавающей точкой.
Логическую сторону решения можно оценить при помощи следующего скрипта, который начисляет штрафные баллы за невыполненные требования.
<form method=post action = ?>
Алфавит:
<input size=100 name=abc value="abcdefghijklmnopqrstuvwxyzABCDEFGHI JKLMNOPQRSTUVWXYZ0123456789!@$^*()[],./_+-=~:|?{}'">
Строки данных:
<textarea cols=100 rows=10 name=list >
A
Quicks
brown
fox
jumps
over
lazy
dog
!!
</textarea>
<input type=submit value=Go />
</form>
<hr>
<?php
include 'user.php';
// function user_encode($data, $abc)
// {
// ...
// }
// function user_decode($text, $abc)
// {
// ...
// }
//function user_encode($x, $abc) {return base64_encode($x); }
//function user_decode($x, $abc) {return base64_decode($x); }
if(!isset($_POST['list'])|| @strlen($_POST['abc'])<2) exit;
$list = get_magic_quotes_gpc()? stripslashes($_POST['list']):$_POST['list'];
$abc = get_magic_quotes_gpc()? stripslashes($_POST['abc']):$_POST['abc'];
$list = explode("\r\n", $list);
echo "<table border=1>";
$maxres = 0;
foreach($list as $msg)
{
if(isset($dm)) { $dm0 = $dm; $em0 = $em; }
if(strlen($msg) > 0 && $msg[0] == ' ')
$msg = base64_decode($msg);
$em = user_encode($msg, $abc);
$dm = user_decode($em, $abc);
$res = '';
if($msg !== $dm) $res = '64 - данные не декодировались';
else
{
$abc0 = count_chars($abc,1);
$abc1 = count_chars($em,1);
$extra = '';
foreach($abc1 as $key =>$val)
if(!isset($abc0[$key]))
$extra .= sprintf(" %02X", $key);
if(strlen($extra))
$res = "32 - применены символы не из алфавита, с кодами $extra";
else
{
$l1 = strlen($dm);
$l2 = strlen($em);
$max = floor(($l1*8 * 1.33 + 7)/8);
if($l2 > $max)
$res = "16 - код длинее оптимального на ".($l2 - $max)." байт";
else if(isset($dm0))
{
$cmp = ($dm0 < $dm) !== ($em0 < $em);
if($cmp)
$res = "8 - сравнение кодов не соответствует сравнению данных";
}
}
}
$maxres |= intval($res);
echo "<tr>"
."<td>".htmlspecialchars($msg)."</td>"
."<td>".htmlspecialchars($em)."</td>"
."<td>".htmlspecialchars($dm)."</td>"
."<td>. $res</td></tr>";
}
echo "</table> Штрафных баллов : ".$maxres;
?>
Решение и обсуждение задачи доступно по ссылкам
http://www.softtime.ru/forum/read.php?id_forum=7&id_theme=38855
http://www.softtime.ru/forum/read.php?id_forum=7&id_theme=39219
http://www.softtime.ru/forum/read.php?id_forum=7&id_theme=39444
http://www.softtime.ru/forum/read.php?id_forum=7&id_theme=39445
http://www.softtime.ru/forum/read.php?id_forum=7&id_theme=39446
|
|
