Алгоритм декодирования PHP Хаффмана
Я недавно устроился на работу и получил хакерранкский экзамен с парой вопросов. Одним из них был алгоритм декодирования Хаффмана. Доступна похожая проблема Вот что объясняет форматирование намного лучше, чем я могу.
Фактическая задача состояла в том, чтобы взять два аргумента и вернуть декодированную строку.
Первый аргумент — это коды, которые представляют собой строковый массив, например:
[
"a 00",
"b 101",
"c 0111",
"[newline] 1001"]
Что похоже: один символ, две вкладки, код Хаффмана.
Новая строка была указана в этом формате из-за способа установки ранга хакера.
Второй аргумент — это строка для декодирования с использованием кодов. Например:
101000111 = bac
Это мое решение:
function decode($codes, $encoded) {
$returnString = '';
$codeArray = array();
foreach($codes as $code) {
sscanf($code, "%s\t\t%s", $letter, $code);
if ($letter == "[newline]")
$letter = "\n";
$codeArray[$code] = $letter;
}
print_r($codeArray);
$numbers = str_split($encoded);
$searchCode = '';
foreach ($numbers as $number) {
$searchCode .= $number;
if (isset($codeArray[$searchCode])) {
$returnString .= $codeArray[$searchCode];
$searchCode = '';
}
}
return $returnString;
}
Он прошел два начальных теста, но было еще пять скрытых тестов, которые он не прошел и не дал обратной связи.
Я понимаю, что это решение не прошло бы, если бы символ был пробелом, поэтому я попробовал менее оптимальное решение, которое использовало substr, чтобы получить первый символ, и соответствие регулярному выражению, чтобы получить число, но оно все равно прошло первые два и провалило скрытую пятерку. Я попробовал функционировать на платформе хакерского ранга с пробелами в качестве входных данных, и среда с песочницей не могла справиться с этим в любом случае, поэтому я вернулась к вышеупомянутому решению, так как оно было более элегантным.
Я пробовал код со специальными символами, символами других языков, кодами различных размеров, и он всегда возвращал желаемое решение.
Я просто разочарован тем, что не смог найти случаи, которые привели к сбою, так как я нашел это элегантным решением. Я хотел бы получить отзывы о том, почему это может не сработать, учитывая отсутствие пробелов, а также любые отзывы об увеличении производительности.
Решение
Ваш основной подход — это звук. Поскольку код Хаффмана является префиксным кодом, т. Е. Ни один код не является префиксом другого, то, если ваш поиск находит совпадение, то это должен быть код. Вторая половина вашего кода будет работать с любым правильным кодом Хаффмана и любым сообщением, закодированным с его использованием.
Некоторые комментарии. Во-первых, приведенный вами пример не является кодом Хаффмана, так как префиксы 010, 0110, 1000, а также 11 нет Коды Хаффмана полны, а код префикса — нет.
Это поднимает вторую проблему, которая заключается в том, что вы не обнаруживаете эту ошибку. Вы должны проверить, если $searchCode пусто после окончания вашего цикла. Если это не так, то код не был завершен или код закончился посередине. В любом случае, сообщение повреждено относительно предоставленного префиксного кода. Уточнил ли вопрос, что делать с ошибками?
Единственная реальная проблема, которую я ожидал с этим кодом, заключается в том, что вы не достаточно расшифровали описание кода. В вопросе говорилось, что всегда было две вкладки, или вы пришли к выводу, что? Возможно, это было просто любое количество места и вкладок. Там, где нужно преобразовать другие кодировки символов, например [newline]? Я полагаю, что вам действительно нужно преобразовать их, если один из примеров работал. Сделал это? В противном случае, возможно, вы не должны были конвертировать.
Другие решения
У меня был такой же вопрос для Coding Challenge. с некоторой модификацией в качестве входных данных был список с (a 111101, b 110010, [newline] 111111 ….)
Я использовал другой подход, чтобы решить эту проблему, используя hashmap, но все же у меня тоже было пройдено всего 2 примера теста.
ниже мой код:
public static String decode(List<String> codes, String encoded) {
// Write your code here
String result = "";
String buildvalue ="";
HashMap <String,String> codeMap= new HashMap<String,String>();
for(int i=0;i<codes.size();i++){
String S= codes.get(i);
String[] splitedData = S.split("\\s+");
String value=splitedData[0];
String key=(splitedData[1].trim());
codeMap.put(key, value);
}
for(int j=0;j<encoded.length();j++){
buildvalue+=Character.toString(encoded.charAt(j));
if(codeMap.containsKey(buildvalue)){
if(codeMap.get(buildvalue).contains("[newline]")){
result+="\n";
buildvalue="";
}
else{
result+=codeMap.get(buildvalue);
buildvalue="";
}
}
}
return result.toString();
}
}