Привет. Я пытаюсь сделать низкоуровневую реализацию префиксного дерева trie. Мне нужно создать компактную бинарную структуру для хранения 3млн. слов. Вот так примерно выглядит структура дерева trie: Код (Text): root / \ \ t a b | | | h n y | | \ | e s y e / | | i r w | | | r e e | r Мы хотим получить значение для слова "абв" Будем считать, что словарь у нас уже загружен в переменную $dic. Читаем первые 5 байт нашего словаря это корень. PHP: $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?
У меня одно условие жесткое, мне надо а память 3 млн. слов плюс по 4 байта к каждому слову в виде данных, чтобы все в памяти уместилось. А trie просто единственная форма, которую как мне кажется я на достаточном уровне понял. Как можно без битмапа компактно сохранить данные о 40 сущностях? --- Добавлено --- Я морфологический анализатор делаю. Сейчас все работает на основе mysql хранилища, потолок скорости ~2000 слов в секунду. Хочу получить хотя бы 10тыс. слов в секунду.
Я морфологический анализатор делаю. Сейчас все работает на основе Саму по себе память не жалко. Чем больше памяти будет потреблять, тем дольше загрузка словаря. Если будет стоять выбор - скорость или размер памяти, конечно предпочтение скорости. Про различные способы организации данных много написано, но там уже на относительно высоком уровне, когда уже есть некие объекты, которых могут хранить данные. В общем буду рад любым предложениям по организации хранилища. Вот что потребуется хранить. Слова и соотв. им индексы более общих сущностей т.н. лемм. 3млн. слов. Лемм около 400 тыс. Если ничего не уменьшать то еще самый большой по кол-ву элементов объем - список форм в которые может трансформироваться лемма, тут около 8 млн. элементов. Сейчас в мускуле я это храню в таблице из 3 полей id леммы - id слова - список id грамматических свойств. Пример 28|34 - это единственное число именительный падеж. Работает со скоростью ~2000 слов в секунду. На всяких редисах и мемкешах еще медленнее, потому как там требуется больше операций IO. Совершенно точно PHP может лучше. --- Добавлено --- Мне тут подкинули материал на тему подсчета битов, но он на C++. Для меня эта тема и так покрыта туманом, мягко говоря, а еще на английском, а еще на незнакомом языке. Но материал очень хороший, видно даже не понимая всех деталей. https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive
PHP: function bitCnt($b) { $cnt=0; while ($b!=0) { $cnt++; $b &= $b-1; } return $cnt; } echo bitCnt(9); // 1001 => 2
Прикольно. Но достаточно долго работает и не решает вопрос подсчета битов после определенного. Вот что показывает тест: Спойлер Код (Text): <?php function bmark() { $args = func_get_args(); $len = count($args); if ($len < 3) { trigger_error("At least 3 args expected. Only $len given.", 256); return false; } $cnt = array_shift($args); $fun = array_shift($args); $start = microtime(true); $i = 0; $args = array_map(function($e){return var_export($e, true);},$args); $str = "$fun(" . implode(', ', $args) . ");"; while ($i < $cnt) { $i++; $res = eval($str); } $end = microtime(true) - $start; return $end; } function bitCnt($b) { $cnt=0; while ($b!=0) { $cnt++; $b &= $b-1; } return $cnt; } function bitCnt3($b) { for ($c = 0; $b; $b >>= 1) { $c += $b & 1; } return $c; } function bitCnt2($b) { return substr_count(base_convert($b,10,2),'1'); } //--------------------------------------- $i = 13423432; $j = 1000000; print "base_convert($i, 10,2): ".base_convert( $i, 10,2)."\n"; print "bitCnt($i): ".bitCnt($i)."\n"; print "bitCnt2($i): ".bitCnt2($i)."\n"; print "bitCnt3($i): ".bitCnt3($i)."\n"; print str_repeat('-',40)."\n"; $m1 = bmark($j, 'bitCnt', $i); $m2 = bmark($j, 'bitCnt2', $i); $m3 = bmark($j, 'bitCnt3', $i); print "measure time bitCnt($i) $j times: $m1\n"; print "measure time bitCnt2($i) $j times: $m2\n"; print "measure time bitCnt3($i) $j times: $m3\n"; print "diff: ". (1-min($m1,$m2,$m3)/max($m1,$m2,$m3))*100 ."%\n"; Код (Text): base_convert(13423432, 10,2): 110011001101001101001000 bitCnt(13423432): 11 bitCnt2(13423432): 11 bitCnt3(13423432): 11 ---------------------------------------- measure time bitCnt(13423432) 1000000 times: 2.2895648479462 measure time bitCnt2(13423432) 1000000 times: 2.711480140686 measure time bitCnt3(13423432) 1000000 times: 2.7266490459442 diff: 15.560331289504% bitCnt() - это от runcore; bitCnt2() - мой наивный вариант; bitCnt3() - наивный вариант Стэнфорда. Как говорится: "Почувствуй разницу".
Да, но все равно самый медленный. Кстати метод, который предложил ты это метод Питера Вегнера и впервые был опубликован аж в 1960 году. https://dl.acm.org/citation.cfm?doid=367236.367286&preflayout=flat Вот этот вариант из стэнфордских, который мне удалось повторить и который оказался быстрее. Не пойму как он работает и что надо сделать, чтобы он умел считать числа больше 32бит. Спойлер Counting bits set, in parallel unsigned int v; // count bits set in this (32-bit value) unsigned int c; // store the total here static const int S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers static const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF}; c = v - ((v >> 1) & B[0]); c = ((c >> S[1]) & B[1]) + (c & B[1]); c = ((c >> S[2]) + c) & B[2]; c = ((c >> S[3]) + c) & B[3]; c = ((c >> S[4]) + c) & B[4]; The B array, expressed as binary, is: B[0] = 0x55555555 = 01010101 01010101 01010101 01010101 B[1] = 0x33333333 = 00110011 00110011 00110011 00110011 B[2] = 0x0F0F0F0F = 00001111 00001111 00001111 00001111 B[3] = 0x00FF00FF = 00000000 11111111 00000000 11111111 B[4] = 0x0000FFFF = 00000000 00000000 11111111 11111111 We can adjust the method for larger integer sizes by continuing with the patterns for the Binary Magic Numbers, B and S. If there are k bits, then we need the arrays S and B to be ceil(lg(k)) elements long, and we must compute the same number of expressions for c as S or B are long. For a 32-bit v, 16 operations are used. Код (Text): function bitCnt4($v) { $S = array(1, 2, 4, 8, 16, 32); $B = array(0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF); $c = $v - (($v >> 1) & $B[0]); $c = (($c >> $S[1]) & $B[1]) + ($c & $B[1]); $c = (($c >> $S[2]) + $c) & $B[2]; $c = (($c >> $S[3]) + $c) & $B[3]; $c = (($c >> $S[4]) + $c) & $B[4]; return $c; } А вот про этот пишут, что он самый быстрый. Но его воспроизвести я не сумел. Спойлер A generalization of the best bit counting method to integers of bit-widths upto 128 (parameterized by type T) is this: v = v - ((v >> 1) & (T)~(T)0/3); // temp v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3); // temp v = (v + (v >> 4)) & (T)~(T)0/255*15; // temp c = (T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * CHAR_BIT; // count See Ian Ashdown's nice newsgroup post for more information on counting the number of bits set (also known as sideways addition). The best bit counting method was brought to my attention on October 5, 2005 by Andrew Shapira; he found it in pages 187-188 of Software Optimization Guide for AMD Athlon™ 64 and Opteron™ Processors. Charlie Gordon suggested a way to shave off one operation from the purely parallel version on December 14, 2005, and Don Clugston trimmed three more from it on December 30, 2005. I made a typo with Don's suggestion that Eric Cole spotted on January 8, 2006. Eric later suggested the arbitrary bit-width generalization to the best method on November 17, 2006. On April 5, 2007, Al Williams observed that I had a line of dead code at the top of the first method. [/quote]
PHP: $cnt = array_shift($args); $fun = array_shift($args); $start = microtime(true); $i = 0; $args = array_map(function($e){return var_export($e, true);},$args); $str = "$fun(" . implode(', ', $args) . ");"; while ($i < $cnt) { $i++; $res = eval($str); } $end = microtime(true) - $start; Тут нужно мерить без eval PHP: $cnt = array_shift($args); $fun = array_shift($args); $num = array_shift($args); $i = 0; $start = microtime(true); while ($i < $cnt) { $i++; $res = $fun($num); } $end = microtime(true) - $start;
Ну для сравнения eval не мешает, понятно что искажает время выполнения, но зато так функция универсальная, у меня раньше было через call_user_func_array(), но у нее недостаток, что она не позволяет запустить функцию var_export(), а я делал сравнение скорости функций сериализации. https://github.com/legale/serialize-bm
Мне же еще надо отсчитывать от заданного бита. У оксфордских ребят не нашел ничего похожего. Тут кстати на хабре видимо по мотивам этой страницы оксфордчан переработал и дополнил. https://habr.com/post/276957/ --- Добавлено --- Чувак скромняга запилил на хабр под видом своей статьи. Но даже не потрудился подобрать нормального русского слова для слова наивный. Но статья все равно хорошая.
Сделал функции для установки и снятия нужного бита, надеюсь завтра уже можно будет испытать. Код (Text): function bit_set($bitmap, $bit){ $bitmap |= 1 << $bit - 1 ; return $bitmap; } function bit_clear($bitmap, $bit){ $bitmap &= ~(1 << $bit - 1) ; return $bitmap; } function bit_check($bitmap, $bit ){ return (bool)(($bitmap >> $bit - 1) & 1); }
Заработало. Только у меня недо trie получилось. Если слово представить в виде башни, где каждая буква этаж. То у меня сейчас каждый этаж 48бит. Т.е. только 1 массив русских букв и цифр. А надо чтобы было в каждой букве, которая в ходу ещё 1 массив. Т.е. если делать по моему первому плану с фиксированной длиной, чтобы быстро можно было нужную часть брать не просматриваются остальные, тогда если грубо 64*64бит = 4096 бит на каждый этаж. Всего их будет примерно 30. Т.е.122880 бит или 15360 байт, что как-то очень мало.
Первая версия моего низкоуровневого префиксного дерева. Демонстрация работы: Спойлер Код (Text): <?php require(dirname(__FILE__).'/Trie2.txt'); $trie = new Yatrie(); $trie->trie_add('баба'); $trie->trie_add('абаб'); $trie->trie_add('ваба'); $trie->trie_add('ааааааббв'); $trie->trie_add('человек'); file_put_contents('dic_demo.txt',$trie->trie); //запишем словарь $trie = new Yatrie(file_get_contents('dic_demo.txt')); //заново создадим класс, но уже с сохраненным словарем print "Ожидаем true: "; var_dump( $trie->trie_check('баба')); print "Ожидаем true: "; var_dump( $trie->trie_check('человек')); print "Ожидаем true: "; var_dump( $trie->trie_remove('баба')); print "Ожидаем false: "; var_dump( $trie->trie_check('баба')); print "Ожидаем true: "; var_dump( $trie->trie_check('ааааааббв')); print "Ожидаем true: "; var_dump( $trie->trie_check('человек')); Принцип хранения двоичных данных словаря: 1 буква - слой 0 ----------- 6 байт - битовая маска кодовой таблицы 6 байт - битовая маска флагов "конец слова" ----------- 2 буква - слой 1 ----------- буква "а" 6 байт + 6 байт буква "б" 6 байт + 6 байт ... и т.д. --- Добавлено --- Размер словаря поражает воображение и вызывает сомнения. Словарь с максимальной длиной слов до 35 букв составляет всего 19кб. Где подвох?
Скорость поиска отличная получилась. 50 тыс. слов за 0.504 секунды. --- Добавлено --- Сейчас попробую свой гигантский словарь загнать. С такими размерами можно даже отказаться от оптимизации, которую я там использую. Дело в том, что функция pack конвертирует long long число в положенные 64 бита или 8 байт, у меня такие длинные числа не получаются, потому что кодовая таблица всего 6 первых байт использует, поэтому там у меня такой огород. Сначала pack('P', $data), а потом я substr отрезаю первые 6 байт и только потом сохраняю в словарь. Соответственно на чтении приходится читать по 6 байт, а потом дописывать их нулями через str_pad(), а только потом unpack('P', $bin).
Словарь гигантский добавился. Размер файла все те же 20кб. Слова из словаря ищет. Надо бы нормальные юнит тесты сделать, но мне лень тесты сочинять и писать их. Лучший тест - боевое применение. Надо приделать это к морфологическому анализатору. Еще не придумал как сделать красиво, дерево как и положено данных хранить не умеет, надо как-то придумать как я смогу от слова переходить к его словоформам.
Гит сделаю. Нашёл ошибку концептуальную, которая и была причиной того, что словарь независимо от кол-ва слов в нем занимал так немного памяти. --- Добавлено --- Видимо первоначальная задумка со слоями или узлами постоянной длины не выйдет. По крайней мере так просто, как это сделано сейчас.
Две новости - хорошая и плохая. 1. Переделал свое дерево. Теперь как по учебнику. 2. Скорость упала радикально, пожалуй раз в 10 упала. Наверняка можно улучшить, в общем запиливаю на гит, надеюсь кто-то заинтересуется.
Хорошая новость. Решил не выкладывать такую медленную версию. Ну очень долго операция добавления выполнялась. Прогнал профайлером и выяснилось, что самая долгая операция substr(), которая постоянно выполняется и при чтении и при записи. Поскольку довольно быстро размер бинарной строки становится несколько мегабайт, то время выполнения substr() становится запредельным. Я придумал следующий фокус. Я создал промежуточный метод для обращения к словарю, своебразный драйвер. Он принимает на вход id узла, по нехитрой схеме деления с округлением вниз определяет номер блока в словаре. и выдает в виде ссылки конкретных блок нужный блок словаря. Т.е. все функции практически остались без изменений, только теперь они открывают словарь не сразу обращаясь к переменной класса, а вызывая метод, который уже возвращает ссылку на блок словаря.
Той версии не осталось. Чтобы в этой версии увидеть как может медленно работать substr() можно увеличить размер блока. Т.е. сколько узлов может хранится в 1 строке. Там переменная класса $size_block. Если ставить даже 10000 - уже видно замедление, но если поставить 100 тыс. - будет видно отлично.