Низкоуровневая реализация префиксного дерева trie на PHP
Предисловие
Описанная здесь реализация trie на PHP делает пока слишком жирный словарь, который соответственно довольно долго загружается в память, что нивелирует довольно неплохую скорость её работы. Скорость поиска составляет ~80 тыс. слов в секунду. Словарь сделан из списка лемм словаря opencorpora.org и включает в себя 389844 слова. В несжатом виде словарь весит ~150 мб, а сжатый gzip ~6 мб. Однако довольно неплохие результаты быстродействия доказывают, что на чистом PHP можно сделать вполне работоспособное префиксное дерево trie.
Заранее прошу программистов с задатками литературных критиков не писать злобных комментариев. Эта статья должна быть интересна новичкам, как и я сам. Кому лень читать можно сразу посмотреть код на github.
Как все началось
Уже довольно давно я вынашиваю идею написания морфологического анализатора для своих PHP проектов, который сможет быстро проводить морфологический разбор заданных слов, а также трансформацию слов в нужную морфологическую форму.
На PHP уже есть подобная библиотека, которая называется phpmorhy. Работает довольно быстро и я бы использовал её и ничего бы не выдумывал, но компилятор словаря в ней сделан в виде отдельного не PHP приложения, что для меня делает невозможным использование этой библиотеки. Сама библиотека построена на базе уже давно не обновляемого словаря AOT, что еще больше снижает её полезность.
Шли недели и месяцы, я прочитал статью хабровчанина, потом статью И. Сегаловича о быстром морфологическом алгоритме для поисковика, потом еще кучу разных статей.
Мало-помалу я созрел для написания собственного лунапарка с блекджеком и шмарами морфологического анализатора. Думаю:»Ну прогресс шагнул вперед, на PHP уже геном человека парсить можно! ».
Взял словарь opencorpora.org, положил в mysql и получил скорость поиска 2 тыс. слов в секунду. Надо загружать словарь в память, думаю я. И тут оказывается, что для того чтобы доступными в PHP штатными структурами данных вроде массива или объекта, хранить словарь на 3 млн. нужно примерно 2Гб оперативной памяти. Все реализации trie на php, которые мне попадались, годились только как учебное пособие демонстрации логики работы, поскольку сами строились на нативных PHP структурах по хранению данных.
Устройство хранения словаря и принцип работы
Везде, где мне удалось почитать, послушать или посмотреть про префиксное дерево trie не объясняется как именно данных будут хранится в памяти. Вот у нас узел, а вот его наследники, а вот флаг окончания слова, что под капотом не показывают. Поэтому способ хранения мне пришлось выдумывать самому.
Как известно префиксное дерево trie состоит из узлов. Узел хранит в себе префикс, ссылки на последующие узлы (потомков) и указатель на то, что этот префикс является последним в цепочке. Довольно доходчиво про trie рассказывает индус вот тут.
Узлы в моей реализации trie представляют собой блоки данных фиксированной длины 154 байта. Первые 6 байт (48 бит) содержат в себе битовую маску наследников. 46 первых бит — русский алфавит, цифры, кавычка, дефис и апостроф. Апостроф добавлен потому что в словаре opencorpora.org есть слово «кот-д«ивуар», в котором используется именно знак апостроф. 47-й бит служит для хранения флага окончания слова. Следующие после битовой маски 148 байт используются для хранения ссылок на наследников узла. По 3 байта на каждый знак (46×3 = 148).
Узлы хранятся в виде двоичных данных в строке. Доступ к нужному участку осуществляется с помощью функции substr () и последующей распаковкой unpack ().
Использование узлов фиксированной длины позволяет упростить процесс адресации. Для переключения на нужный узел достаточно знать его порядковый номер (id) и длину узла. Умножаем порядковый номер на длину и узнаем смещение относительно начала строки — все очень просто.
рис. 1 Схема хранения
Недостатки
Используемая схема хранения упрощает адресацию, но прямо-таки пожирает место. Для хранения 380 тыс. слов требуется чуть более миллиона узлов. 154 байта * 1 000 000 узлов = 146.86 мегабайт. Т.е. примерно 400 байт на 1 слово. Если записывать слова в простой текстовый файл в кодировке utf8, то эти же 380 тыс. слов можно уместить в 16 мегабайт.
Планы
Чтобы использовать память более рационально я хочу перейти к переменной длине узлов, тогда в качестве ссылки придется записывать не id узла, а его местоположение в байтах. Определение места хранения ссылки на нужный узел будет происходить следующим образом. На примере слова «абв».
Буква «а» первая в алфавите поэтому узел у неё тоже первый, соответственно смещение 0. Читаем 6 байт, начиная от 0.
$str = substr($dic, 0, 6);
Распаковываем строку:
$mask = (ord($str[5]) << 40) + (ord($str[4]) << 32) + (ord($str[3]) << 24) + (ord($str[2]) << 16) + (ord($str[1]) << 8) + ord($str[0]);
Смотрим в маске 2-й бит (буква «б»)
bit_get($mask, 2);
Бит установлен, теперь считаем кол-во поднятых бит в маске до 2. Допустим у нашего узла бит буквы «а» тоже поднят, значит наш бит буквы «б» будет вторым поднятым битом. Считаем смещение, чтобы прочитать ссылку
$offset = 6 + 3;
6 байт маска + 3 байта, которые занимает первая ссылка, получается 9 байт. Читаем нужный кусок строки.
$str = substr($dic, $offset, 3);
Распаковываем ссылку:
$ref = (ord($str[2]) << 16) + (ord($str[1]) << 8) + ord($str[0]);
Переходим к следующему узлу и все повторяем снова. В последней букве проверяем наличие 47 бита в маске, если он установлен — в нашем trie есть искомое слово.
Надеюсь, что удастся сохранить скорость не ниже 50 тыс. слов в секунду.
Благодарности
Хочу поблагодарить участников форума nulled.cc и php.ru за помощь с побитовыми функциями.
