Префиксное дерево trie низкоуровневая структура данных в PHP

Статус
В этой теме нельзя размещать новые ответы.

babahalki

Постоялец
Регистрация
6 Май 2016
Сообщения
247
Реакции
107
Привет. Я пытаюсь сделать низкоуровневую реализацию префиксного дерева trie. Мне нужно создать компактную бинарную структуру для
хранения 3млн. слов.

Вот так примерно выглядит структура дерева trie:
root
/ \ \
t a b
| | |
h n y
| | \ |
e s y e
/ | |
i r w
| | |
r e e
|
r



Мы хотим получить значение для слова "абв"
Будем считать, что словарь у нас уже загружен в переменную $dic.
Читаем первые 5 байт нашего словаря это корень.

Код:
$root = subsstr($dic, 0, 5);
//Там у нас такой битмап
//0000 0000 0000 0000 0000 0000 0000 0000 0000 0011
//Два последних бита - это буквы а и б, т.е. на первом уровне у нас есть
//2 узла а и б. Поскольку длина узла постоянная 4 байта, мы можем понять где у нас начинается следующий уровень 4 * 2
//5 байт корень, 4 байта узел буквы а и 4 байта узел буквы б.
$level2_offset = 5 + 4 * 2;
//читаем заголовок 2 уровня
$level2 = substr($level2_offset, 5);
//Там у нас такой битмап
//0000 0000 0000 0000 0000 0000 0000 0000 0000 0010
//Т.е. на уровне только 1 узел б
//Определяем смещение для уровня 3
$level3_offset = $level2_offset + 5 + 4;
//Читаем заголовок 3 уровня
$level3 = substr($dic, $level3_offset, 5);
//тут битмап такой
//0000 0000 0000 0000 0000 0001 0000 0001 0000 0110
//тут у нас 4 узла, нам нужен узел буквы "в" он третий и впереди него есть еще 1 узел буквы "б"
//значит смещение к нашему узлу у нас будет такое
$node_offset = $level3_offset + 5 + 4;
$node = substr($dic, $node_offset, 4);

Это концепция, но теперь проблема с реализацией. Зная количество узлов на уровне я легко с помощью умножения могу сосчитать смещение на следующий уровень.

1. Проблема в том, что у меня не получается легкой и быстрой функцией определить количество поднятых битов в битмапе уровня. Не считать же единицы в текстовой строке.
2. Как узнать количество поднятых битов младше искомого. Вот мне нужен 5 бит, и если впереди него все четыре подняты, то смещение 4*4, а если 0 поднято, то смещение 0.

Вот какой функцией можно из двоичного числа 1010 получить 2. или из числа 1000 получить 1?
 
1. Проблема в том, что у меня не получается легкой и быстрой функцией определить количество поднятых битов в битмапе уровня. Не считать же единицы в текстовой строке.
Вот Для просмотра ссылки Войди или Зарегистрируйсяот самого простого перебора до...

P.S. На С++, но, думаю, на PHP возможно переписать.
 
Последнее редактирование:
PHP:
n=0;
while (a!=0) {
   a=a&(a-1);
   n++;
}


Хорошие примеры пригодные для php Для просмотра ссылки Войди или Зарегистрируйся
Метод Питера Вегнера опубликован в 1960. Пока пользуюсь им, там есть побыстрее, мне удалось переписать на php, но он до 32 бит понимает. Самый быстрый из способов, который упомянут на сайте Оксфорда, завести не удалось.

Этот способ Питера Вегнера весьма неплох и универсален. Только мне к нему еще в комплекте нужен способ считать поднятые биты после определенного, т.е. к примеру считать только последние 8 из моих сорока. Для этого хорошо подходит мой крестьянский вариант, самый наивный из всех. Он по скорости ~15% проигрывает лидерам гонки, но зато в нем легко можно мою задачу решать.
PHP:
function bitCnt2($i, $offset = null, $length = 999999)
{
    return $offset ? substr_count(substr(decbin($i), $offset, $length), '1') : substr_count(decbin($i), '1');
}

Попробую запилить, всем спасибо.
 
Последнее редактирование модератором:
  • Нравится
Реакции: Nei
Статус
В этой теме нельзя размещать новые ответы.
Назад
Сверху