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

Тема в разделе "PHP", создана пользователем babahalki, 20 июн 2018.

Статус темы:
Закрыта.
Модераторы: latteo
  1. babahalki

    babahalki

    Регистр.:
    6 май 2016
    Сообщения:
    246
    Симпатии:
    98
    Привет. Я пытаюсь сделать низкоуровневую реализацию префиксного дерева 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?
     
  2. Nei

    Nei Nosce te ipsum

    Регистр.:
    5 сен 2009
    Сообщения:
    670
    Симпатии:
    521
    Вот всякие разные способы от самого простого перебора до...

    P.S. На С++, но, думаю, на PHP возможно переписать.
     
    latteo и babahalki нравится это.
  3. babahalki

    babahalki

    Регистр.:
    6 май 2016
    Сообщения:
    246
    Симпатии:
    98
    Спасибо, кажется в самую точку. Осталось с СИ++ разобраться. :)
     
  4. boffin

    boffin Писатель

    Регистр.:
    30 сен 2012
    Сообщения:
    3
    Симпатии:
    4
    PHP:
    n=0;
    while (
    a!=0) {
       
    a=a&(a-1);
       
    n++;
    }
    Хорошие примеры пригодные для php https://habr.com/post/276957/
     
    Последнее редактирование: 20 июн 2018
    babahalki нравится это.
  5. babahalki

    babahalki

    Регистр.:
    6 май 2016
    Сообщения:
    246
    Симпатии:
    98
    Метод Питера Вегнера опубликован в 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');
    }
    Попробую запилить, всем спасибо.
     
    Последнее редактирование модератором: 29 июн 2018
    Nei нравится это.
Статус темы:
Закрыта.