реализация Патриция Три в Яве
Я пытаюсь переписать c ++ patricia trie в Java.
Код C ++ из Вот
Я немного застрял.
Итак, вот мое понимание:
#define ZEROTAB_SIZE 256
head->key = (char*)calloc(ZEROTAB_SIZE, 1);
мы создаем массив из 256 битов для ключа, поэтому мы можем иметь строку длиной не более 32 символов, и каждый символ представлен 8 битами. Могу ли я реализовать это с массивом символов в Java?
template <class T>
int PatriciaTrie<T>::bit_get(PatriciaTrieKey bit_stream, int n) {
if (n < 0) return 2; // "pseudo-bit" with a value of 2.
int k = (n & 0x7);
return ( (*(bit_stream + (n >> 3))) >> k) & 0x1;
}
k получает последние 7 бит из n, мы переходим к n / 8 символу строки (не совсем n / 8, поскольку смещение вправо приведет к удалению всего, что меньше 8 до нуля), затем мы сдвигаем значение bit_stream [n> > 3] на к, и тогда мы получаем последний бит. если я использую массивы в Java, я мог бы переписать это как
return (bit_stream[n>>3] >> k) & 0x1;
?
template <class T>
int PatriciaTrie<T>::bit_first_different(PatriciaTrieKey k1, PatriciaTrieKey k2) {
if (!k1 || !k2)
return 0; // First bit is different!
int n = 0;
int d = 0;
while ( (k1[n] == k2[n]) &&
(k1[n] != 0) &&
(k2[n] != 0) )
n++;
while (bit_get(&k1[n], d) == bit_get(&k2[n], d))
d++;
return ((n << 3) + d);
}
теперь это сбивает с толку, первая часть до второго цикла while выглядит достаточно ясно, зацикливается и проверяет, сколько бит равно и не равно нулю, но я не уверен, что делает второй цикл, мы берем адрес из двух ключей и проверьте первые биты, если они равны, и если они равны, мы проверяем снова, пока мы не найдем неравные биты?
Главным образом я не уверен, как здесь используется адрес ключа, но я мог бы быть смущен и сдвигом битов в классе bit_get.
Я хочу сделать сравнение между этим trie в c ++ и java для моего класса java, и я хочу, чтобы реализации были как можно более похожими.
Решение
Я не знаком с этой структурой данных, но есть некоторые проблемы с вашим пониманием этого кода.
Первый, calloc выделяет 256 байтов, а не бит. new byte[256] Было бы сопоставимо в Java.
Во-вторых, n & 0x7 получает три бита nне семь. Более понятный способ написать это n/8 а также n%8 вместо n>>3 а также n & 7, но побитовые операции могут быть немного быстрее, если ваш компилятор глуп.
Вы правы в том, что (bit_stream[n>>3]>>k) & 1 та же.
Теперь первый цикл в bit_first_different циклы над байтами, а не битами. Проверка на 0 состоит в том, чтобы предотвратить утечку ключей. Как только этот цикл заканчивается, n относится к первому отличающемуся байту. Затем второй цикл ищет, какой бит отличается.
Обратите внимание, что если два ключа не различаются, то второй цикл может выйти за пределы конца ключей, что может вызвать ошибку сегментации.
Теперь & принимает адрес k1[n] поскольку bit_get функция ожидает указатель на символ … это проходит в nэлемент битового потока. После цикла d смещение первого разного бита k[n],
Наконец код объединяет n (какой байт?) с d (какой бит в этом байте?), чтобы дать бит. Опять я бы выступил 8*n+d для ясности, но это вопрос вкуса.
Другие решения
Могу ли я реализовать это с массивом символов в Java?
Моя ява немного ржавая но я верю char подписано в Java, что означает, что >> не будет делать то, что вы ожидаете. Это потому, что смещение числа со знаком не сместит бит знака, так что вы действительно хотите >>> оператор или просто использовать byte тип, который без знака. У меня такое чувство, что это все неправильно, поэтому, пожалуйста, перепроверьте.
возврат (bit_stream [n >> 3] >> k) & 0x1;
В C или C ++, *(array + k) это просто еще один способ написать array[k] так что ваш перевод выглядит правильно. Что касается интерпретации, bit_stream[n>>3] по сути, выбирает байт, в котором находится нужный бит. >> k Перемещает нужный бит в позицию младшего разряда. Наконец, мы удаляем все интересующие нас фрагменты, маскируя их & 0x1, Это оставляет нам значение 0 или 1 в зависимости от того, был установлен бит или нет.
Последняя функция выполняет сравнение 2-битных строк и возвращает битовую позицию, в которой эти 2 строки сначала различаются. Первый цикл, по сути, является оптимизированной версией второго цикла, где вместо того, чтобы выполнять побитовое сравнение, вместо этого он проверяет целые байты.
Другими словами, он сначала перебирает все байты и находит первые 2, которые отличаются. Затем он берет эти 2 разных байта и проходит по ним, пока не найдет первые 2 бита, которые отличаются. Обратите внимание, что bit_get Функция никогда не получит больше n в этом сценарии, потому что мы знаем, что где-то в байте есть разница. Окончательная позиция бита затем строится из результата обоих циклов следующим образом: (number_of_equal_bytes * 8) + number_of_equal_bits),