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

Если у меня есть маска с нужным числом единиц, мне и сдвиг никакой тогда не нужен.
--- Добавлено ---

Видимо быстрее, чем двойку в степень возводить, будет только если уже со считанные маски в массив готовый записать, но для 64 бит больно много выходит.

 

Код (Text):

1.  
2. <?php
3. //это двойка
4. $i = 0b10;
5. $i2 = $i << 1;
6. //а тут мы ее сдигаем и получаем 100
7. echo decbin($i2);

Вычитания правильного не хватает.

Код (Text):

1.  
2. <?php
3. $i = 2;
4. $len = 7;
5. $mask = ($i << $len - 1) - 1;
6. echo decbin($mask);

Так работает. Засуну в бенчмарк, посмотрим что будет быстрее.

 

Спойлер: функция подсчета битов в числе

Код (PHP):

1. function bit_count_hard(int $v, int $length = null)
2. {
3.     if ($length > 0) {
4.         $v &= (2 << $length - 1) - 1;
5.     }
6.     $S = [1, 2, 4, 8, 16]; // Magic Binary Numbers
7.     $B = [0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF];
8.     $c = $v - (($v >> 1) & $B[0]);
9.     $c = (($c >> $S[1]) & $B[1]) + ($c & $B[1]);
10.     $c = (($c >> $S[2]) + $c) & $B[2];
11.     $c = (($c >> $S[3]) + $c) & $B[3];
12.     $c = (($c >> $S[4]) + $c) & $B[4];
13.     return $c;
14. }
15.  
16. function bit_count_hard2(int $v, int $length = null)
17. {
18.     if ($length > 0) {
19.         $v &= (2 << $length - 1) - 1;
20.     }
21.     $c = $v - (($v >> 1) & 0x55555555);
22.     $c = (($c >> 2) & 0x33333333) + ($c & 0x33333333);
23.     $c = (($c >> 4) + $c) & 0x0F0F0F0F;
24.     $c = (($c >> 8) + $c) & 0x00FF00FF;
25.     $c = (($c >> 16) + $c) & 0x0000FFFF;
26.     return $c;
27. }
28.  
29.  
30. function bit_count_pow(int $bmask, int $length = null)
31. {
32.     if ($length !== null) {
33.         $bmask &= pow(2, $length) - 1;
34.     }
35.     $cnt = 0;
36.     while ($bmask != 0) {
37.         $cnt++;
38.         $bmask &= $bmask - 1;
39.     }
40.     return $cnt;
41. }
42.  
43.  
44. function bit_count_shift(int $bmask, int $length = null)
45. {
46.     if ($length > 0) {
47.         $bmask &= (2 << $length - 1) - 1;
48.     }
49.     $cnt = 0;
50.     while ($bmask != 0) {
51.         $cnt++;
52.         $bmask &= $bmask - 1;
53.     }
54.     return $cnt;
55. }

Код (PHP):

1. $s = '1111111111111111111111111100';
2. $i = bindec($s);
3. $length = 30;
4. $times = 1000000;
5.  
6. $res['bit_count_pow'][] = bit_count_pow($i, $length);
7. $res['bit_count_shift'][] = bit_count_shift($i, $length);
8. $res['bit_count_hard'][] = bit_count_hard($i, $length);
9. $res['bit_count_hard2'][] = bit_count_hard2($i, $length);
10.  
11. $res['bit_count_pow'][] = bmark($times, 'bit_count_pow', $i, $length);
12. $res['bit_count_shift'][] = bmark($times, 'bit_count_shift', $i, $length);
13. $res['bit_count_hard'][] = bmark($times, 'bit_count_hard', $i, $length);
14. $res['bit_count_hard2'][] = bmark($times, 'bit_count_hard2', $i, $length);
15.  
16. print_r($res);

Результаты:

Код (PHP):

1. Array
2. (
3.     [bit_count_pow] => Array
4.         (
5.             [0] => 26
6.             [1] => 3.0027370452881
7.         )
8.  
9.     [bit_count_shift] => Array
10.         (
11.             [0] => 26
12.             [1] => 2.9123110771179
13.         )
14.  
15.     [bit_count_hard] => Array
16.         (
17.             [0] => 26
18.             [1] => 2.4514529705048
19.         )
20.  
21.     [bit_count_hard2] => Array
22.         (
23.             [0] => 26
24.             [1] => 2.3469979763031
25.         )
26.  
27. )

Получается, что замена pow() на сдвиг дает 3% прироста скорости, а если на такой большой маске (26 единиц) применить еще параллельный метод вместо метода Вейнера, то прирост скорости 21%.

 

Да, все что можно было сюда сделать - сделал и залил.

Сейчас пробуют по более сложной схеме сделать, но должно получится компактнее гораздо. Там по моим прикидкам в среднем 4 из 46 ссылок в узле используются. Получается на 3 млн. узлов потери 378 млн. байт, или 360мб.
В общем концепция такая:
Узлы и ссылки в отдельных блоках.
Узлы как и раньше постоянной длины, но теперь так:

Блок узлов:
6 байт маска
4 байт ссылка на блок в ссылках (смещение в байтах)

Блок ссылок:
Ссылки узла для поднятых битов в узле. 3 байта на ссылку

Принцип работы на примере добавления:
1. Делим слово по символу.
2. Берём 1 символ слова. По массиву индексов ищем id его узла.
2. Получаем узел, смотрим в нем бит второго символа слова.
2а) бит поднят, берём ссылку из узла на блок ссылок. Считаем кол-во битов до искомого бита 2 символа. К примеру этот символ будет буква 'в', у неё индекс 3. Считаем поднятые до третьего биты. Пусть у нас получился 1 бит поднят, не включая наш 3 бит. Первая ссылка значит с 0 по 3 байт, а наша ссылка с 3 по 6 байт. Считаем смещение 1 * 3байта. Читаем наши с 3 по 6 байты, делаем unpack и получаем Id следующего узла. Повторяем цикл.
2б) бит не поднят, значит следующего узла ещё нет. Создаём следующий узел. У нас теперь его id. Теперь читаем все ссылки с нашего узла. Для этого сначала считаем все поднятые биты. Так мы узнаем размер всех ссылок узла. Теперь считаем поднятые биты до нашего 3 бита буквы 'в'. У нас получилось 1 бит. Значит смещение нашей новой ссылки должно быть 1 * 3 байт т.е. 3
Сначала добавляем в существующий набор ссылок нашу новую ссылку на созданный узел. Таким образом у нас длина ссылок увеличилась на 3 байта и на старом месте она больше не уместится.
Размер и адрес старого места для ссылок узла добавляем в массив освободившегося места. Теперь пытаемся поискать в этом же массиве ранее освободившееся место большего размера. Если оно там есть, берём его адрес и убираем запись о нем из массива. Если в массиве подходящего места нет, то новым блок ссылок просто пишем в самый конец нашего блока.
Пишем ссылки и получаем их новый адрес.
Пишем в узел новый адрес смещения в блоке ссылок. Повторяем цикл.

Добавление новой ссылки на 4 байта прибавит словарю 11мб из расчёта 3 млн. узлов. Получится, что если каждый узел будет иметь по 4 ссылки, то 3млн. * (10байт + 12байт) = 63мб

 

Пробую писать параллельно с тестами. Еще не tdd, но уже ближе. Из плюсов можно отметить то, что тесты будут готовы вместе с рабочим кодом, а также то, что функции теперь сразу делаю как можно более элементарными, что упрощает их тестирование.

 

инкремент/декремент делать бессмысленно, потому что считать биты приходится единажды в 1 узле. Вернее дважды. 1 раз нужно посчитать все биты кроме 47, потому что 47 это не бит алфавита - это флаг того, что на данном узле заканчивается слово. Второй раз биты нужно посчитать до бита нужной буквы, чтобы понять место для ссылки этой буквы.

Там все очень просто. Вот схема блока узлов:




А вот схема блока ссылок:



На этой схеме видно, что у узла 0 (буква "А) есть 2 ссылки, значит в маске узла поднято 2 бита. В узле 1 поднято 5 бит и соответственно 5 ссылок записано в блоке памяти ссылок.

В строке содержимое видно какие именно числа там записаны. В самом узле есть маска 6 байт, и 4 байта смещение или адрес на соответствующий этому узлу участок памяти в блоке ссылок. В содержимом участков памяти блока ссылок записаны id узлов, на которые они ссылаются. Первая ссылка на 47 узел, вторая на 49 и т.д.

Предположим надо проверить наличие слова "АБ" в словаре. В узле 0, который к букве А относится у нас поднято 2 бита у буквы "А" и буквы "Б", т.е. 1 и второй биты. Сначала мы посчитали первые 46 бит и у нас получилось 2. Т.е. мы знаем теперь размер блока памяти выделенной ссылкам узла 0. Дальше надо понять какой именно из этого участка от 0 до 6 байт надо прочитать для того, чтобы получить ссылку буквы "Б". Считаем биты до бита буквы "Б" (второй бит).

Код (Text):

1. $bits = bit_count($mask, 1);

Теперь мы можем посчитать смещение. Все ссылки по 3 байта, поэтому 1 * 3 = 3. Смещение 3 и длина тоже 3. Делаем из строки ссылок

Код (Text):

1.  
2. $sub = substr($refs_block, 3, 3);
3. //теперь распаковываем и получаем число 49
4. $ref = unpack_24($sub);

Теперь снова считываем маску узла 49, поскольку мы ищем слово "АБ" это последняя буква - значит проверяем установлен ли 47 бит в маске этого 49 узла, если установлен - слово "АБ" есть в словаре, нет, значит - нет.

 

Сейчас вот так:

Код (Text):

1.  
2. private function bit_get(int $bitmap, int $bit)
3. {
4.     return (bool)(($bitmap >> $bit - 1) & 1);
5. }

Наверное как ты предложил получится быстрее.

 

Наконец-то закончил переделку. Все стало сложнее, прозрачность, если она вообще была, теперь практически исчезла. Но ожидаемая экономия действительно появилась. Словарь на 380 тыс. слов раньше занимал примерно 150 Мбайт в несжатом виде, теперь 13 Мбайт. Полный словарь всех словоформ словаря opencorpora.org (3.03 млн. слов) в несжатом виде теперь занимает 54 Мбайт.

 

Замер не могу сделать пока. Там есть загвоздка небольшая с сохранением словаря после создания.

 

Победа - приятно. Спасибо, очень помог. Но вылезла проблема, вернее суровая реальность. По деталям вся эта конструкция сделана из качественных деталей. Как если напиздить запчастей из гаража команды f1.
Но когда я собираю из них болид, чем более сложным я пытаюсь его сделать, тем хуже работает. Т.е. тут узким местом становится мой скил проектировщика.
Через неделю открою исходники и не смогу сам разобрать, что я там на..евертил.

 

Скорость упала примерно в 2 раза и теперь составляет 42.5 тыс. слов в секунду. Оформил изменения и пнул на гит версию 0.1.0

https://github.com/legale/yatrie

 

Размер словаря сократился на порядок, полный словарь на 3 млн. слов в несжатом виде теперь занимает 55 Мбайт, против ~600 Мбайт. Теперь надо рефакторить и запиливать в виде расширения для PHP на Си. Кто необходимый опыт имеет?

 

Попробую сделать загрузку словаря не с диска, а сразу из apcu. Но мой бенчмаркинг время загрузки вообще не учитывает. 42 тыс. Слов выходит только на работу функции поиска в словаре. Время загрузки словаря туда не входит.

 

Написание 2 функций далось мне очень сложно. Но мне удалось. Теперь либа умеет не только добавлять слова в словарь, а потом проверять есть ли они в словаре. Теперь можно получить все слова в словаре, или вытащить слова с определенной ветки дерева. Ура!

Вот то, что не давалось мне целых 2 дня.

PHP:

1. public function &trie_traverse_node(int $id, string $concat, array &$res = []): array {
2.     list($bits, $refs) = $this->node_get_children($id);
3.  
4.     //on the last node (leaf) save $concat to the res
5.     if(empty($refs)){
6.         $res[] = $concat;
7.         return $res;
8.     }
9.  
10.     //recurse call node traverse on each node_id and pass $concat arg by concatenating it a new char
11.     foreach($refs as $i=>$node_id){
12.         $string = $concat.$this->codepage_flip[$bits[$i]];
13.         $this->trie_traverse_node($node_id, $string, $res);
14.     }
15.  
16.     return $res;
17. }