babahalki
Постоялец
- Регистрация
- 6 Май 2016
- Сообщения
- 247
- Реакции
- 107
- Автор темы
- #1
Привет. Я пытаюсь сделать низкоуровневую реализацию префиксного дерева trie. Мне нужно создать компактную бинарную структуру для
хранения 3млн. слов.
Вот так примерно выглядит структура дерева trie:
root
/ \ \
t a b
| | |
h n y
| | \ |
e s y e
/ | |
i r w
| | |
r e e
|
r
Мы хотим получить значение для слова "абв"
Будем считать, что словарь у нас уже загружен в переменную $dic.
Читаем первые 5 байт нашего словаря это корень.
Это концепция, но теперь проблема с реализацией. Зная количество узлов на уровне я легко с помощью умножения могу сосчитать смещение на следующий уровень.
1. Проблема в том, что у меня не получается легкой и быстрой функцией определить количество поднятых битов в битмапе уровня. Не считать же единицы в текстовой строке.
2. Как узнать количество поднятых битов младше искомого. Вот мне нужен 5 бит, и если впереди него все четыре подняты, то смещение 4*4, а если 0 поднято, то смещение 0.
Вот какой функцией можно из двоичного числа 1010 получить 2. или из числа 1000 получить 1?
хранения 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?