Pull to refresh

Trie, или нагруженное дерево

Algorithms *
Sandbox
Здравствуй, Хабрахабр. Сегодня я хочу рассказать о такой замечательной структуре данных как словарь на нагруженном дереве, известной также как префиксное дерево, или trie.

Что это ?


Нагруженное дерево — структура данных реализующая интерфейс ассоциативного массива, то есть позволяющая хранить пары «ключ-значение». Сразу следует оговорится, что в большинстве случаев ключами выступают строки, однако в качестве ключей можно использовать любые типы данных, представимые как последовательность байт (то есть вообще любые).
Читать дальше →
Total votes 78: ↑73 and ↓5 +68
Views 90K
Comments 29

«Сделайте мне красиво!» Выпуск №26

Lumber room
Вашему вниманию очередной выпуск подкаста о веб-разработке «Сделайте мне красиво!»

Show notes:


Наши ссылки: RSS и лента на rpod.ru
Total votes 4: ↑3 and ↓1 +2
Views 479
Comments 0

«Сделайте мне красиво!» Выпуск №27

Lumber room
Вашему вниманию очередной выпуск подкаста о веб-разработке «Сделайте мне красиво!»

Show notes:


Наши ссылки: RSS и лента на rpod.ru
Total votes 9: ↑6 and ↓3 +3
Views 715
Comments 1

Префиксные деревья в Python

Python *
Доделал на днях питонью библиотеку datrie, реализующую префиксное дерево (см. википедию или хабр), спешу поделиться.

Если вкратце, то можно считать, что datrie.Trie — это замена стандартному питоньему dict, которая при определенных условиях (ключи — строки) занимает меньше памяти, имеет сравнимую скорость получения отдельного элемента и поддерживает дополнительные операции (получение всех префиксов данной строки, получение всех строк, начинающихся с данной строки и др.), которые работают примерно так же быстро, как и «словарные» операции.

Работает под Python 2.6-3.3, поддерживает юникод, лицензия LGPL.

Читать дальше →
Total votes 59: ↑58 and ↓1 +57
Views 11K
Comments 18

Сжатые префиксные деревья

Algorithms *
Tutorial
Тема префиксных деревьев поиска уже неколько раз поднималась на хабре. Здесь, например, кратко описывается, что такое префиксное дерево и зачем оно нужно, и рассматриваются основные операции над такими деревьями (поиск, вставка, удаление). К сожалению, ничего при этом не говорится про реализацию. В этом недавнем посте рассматривается «питонья библиотека datrie», являющаяся Cython-оберткой библиотеки libdatrie. По последней ссылке имеется хорошее описание реализации частично сжатых префиксных деревьев в виде детерминированных конечных автоматов (с использованием массивов). Я решил внести свои пять копеек в эту тему, рассмотрев реализацию на языке С++ префиксных деревьев с помощью указателей. Кроме того, была и еще одна цель — сравнить между собой поиск строк с помощью сбалансированного двоичного дерева поиска (АВЛ-дерево) и сжатого префиксного дерева.

Читать дальше →
Total votes 54: ↑52 and ↓2 +50
Views 58K
Comments 24

pymorphy2

Python *Algorithms *Natural Language Processing *
В далеком 2009 году на хабре уже была статья "Кузявые ли бутявки.." про pymorphy — морфологический анализатор для русского языка на Python (штуковину, которая умеет склонять слова, сообщать информацию о части речи, падеже и т.д.)

В 2012м я начал потихоньку делать pymorphy2 (github, bitbucket) — думаю, самое время представить эту библиотеку тут: pymorphy2 может работать в сотни раз быстрее, чем pymorphy (втч без использования C/C++ расширений) и при этом требовать меньше памяти; там лучше словари, лучше качество разбора, лучше поддержка буквы ё, проще установка и более «честный» API. Из негатива — не все возможности pymorphy сейчас реализованы в pymorphy2.

Эта статья о том, как pymorphy2 создавался (иногда с довольно скучными техническими подробностями), и сколько глупостей я при этом наделал; если хочется просто все попробовать, то можно почитать документацию.

Читать дальше →
Total votes 103: ↑100 and ↓3 +97
Views 74K
Comments 44

Максимальное XOR

Algorithms *
Здравствуй, Хабр. И сразу к делу.
Задача:
Есть два целых числа: L и R. Нужно найти максимальное значение A xor B на промежутке [L; R], где L ≤ A ≤ B ≤ R.
Казалось бы ничего сложного. Сразу напрашивается решение простым перебором.
Развернуть
public int BruteForce(int one, int two)
{
   int maxXor = 0;
   while (one < two)
   {
      int oneTemp = one + 1;
      while (oneTemp <= two)
      {
         int curXor = one ^ oneTemp;
         if (maxXor < curXor) maxXor = curXor;
         oneTemp++;
      }
      one++;
   }

   return maxXor;
}

Сложность этого решения O(n2).
А что, если в интервале будет 1000000 чисел. Возьмем L = 1, а R = 1000001. Сколько времени понадобится cреднестатистическому компьютеру для того, чтобы посчитать максимальное значение xor на этом интервале? Моему ноутбуку потребовалось 1699914 миллисекунд.
Существует решение, которое работает значительно быстрее, именно о нем и пойдет речь в этой статье.
image
Читать дальше →
Total votes 46: ↑34 and ↓12 +22
Views 23K
Comments 38

Алгоритм поиска наилучшего маршрута в linux

High performance *System Programming *Algorithms *Mathematics *
В настоящее время в компьютерных сетях практически повсеместно используется протокол IP. Для того, чтобы отправить IP-пакет каждый маршрутизатор ищет в свой таблице маршрутизации наилучший маршрут для адреса назначения пакета. В данной статье я хочу описать алгоритм поиска наилучшего маршрута, реализованного в ядре linux.
Читать дальше →
Total votes 19: ↑19 and ↓0 +19
Views 17K
Comments 1

Naive Spellchecking, или поиск ближайших слов из словаря по метрике Левенштейна на Scala

Search engines *Programming *Algorithms *Scala *Functional Programming *
Tutorial
Приветствую! В этой статье будет показан алгоритм поиска ближайших к заданному слов из корпуса в терминах метрики Левенштейна. Наивным spellchecking-ом назван потому, что не учитывает ни морфологии, ни контекста, ни вероятности появления скорректированного слова в предложении, однако в качестве первого приближения сойдет вполне. Также алгоритм может быть расширен на поиск ближайших последовательностей из любых других сравнимых объектов, нежели простой алфавит из Char-ов, и, после допиливания напильником, его можно приспособить и для учета вероятностей появления скорректированных слов. Но в данной статье сосредоточимся на базовом алгоритме для слов определенного алфавита, скажем, английского.

Код в статье будет на Scala.

Всех заинтересовавшихся прошу под кат.
Читать дальше →
Total votes 11: ↑11 and ↓0 +11
Views 2.9K
Comments 0

Самый быстрый Индиан: Key/Value контейнер на базе Trie

Algorithms *
image

«Может показаться, что я ничего не делаю. Но на самом деле, на клеточном уровне, я очень занят»
Автор неизвестен

В 21 веке построение программ все чаще напоминает конструктор Lego. Этот подход подразумевает, что многие «кубики» придуманы до нас. Собственно их элементарность обманчиво подсказывает, что ресурс улучшений за многие годы здесь практически исчерпан и нам остается использовать то, что есть. Но, как не странно, по аналогии с биологией, элементарные «клетки» порой скрывают самые сложные и продуманные алгоритмы и именно здесь заключены все самые интересные баталии. В этом смысле программисты по многогранности индустрии, чем-то напоминают медиков. Здесь есть свои терапевты, ветеринары, хирурги и есть вот те ребята, которые на несколько строк кода могут потратить несколько месяцев работы.

«В компании Google, прямо сейчас, пока я говорю, в нашем парке серверов, 1% всех CPU занимаются вычислениями внутри хештаблиц. Пока я говорю, более 8% всей оперативной памяти серверов занимают хештаблицы. И это только то, что относится к С++, я не знаю ситуации по Java»
Matt Kulukundis, CppCon 2017
Читать дальше →
Total votes 21: ↑20 and ↓1 +19
Views 6.1K
Comments 19

Низкоуровневая реализация префиксного дерева trie на PHP

PHP *Programming *Algorithms *

Предисловие


Описанная здесь реализация trie на PHP делает пока слишком жирный словарь, который соответственно довольно долго загружается в память, что нивелирует довольно неплохую скорость её работы. Скорость поиска составляет ~80 тыс. слов в секунду. Словарь сделан из списка лемм словаря opencorpora.org и включает в себя 389844 слова. В несжатом виде словарь весит ~150мб, а сжатый gzip ~6мб. Однако довольно неплохие результаты быстродействия доказывают, что на чистом PHP можно сделать вполне работоспособное префиксное дерево trie.
Читать дальше →
Total votes 22: ↑22 and ↓0 +22
Views 5.6K
Comments 26

Как сделать расширение на PHP7 сложнее, чем «hello, world», и не стать красноглазиком. Часть 2

PHP *C *
Tutorial

Краткое содержание первой части


В первой части я сделал болванку расширения, заставил ее правильно работать в IDE Clion, написал функцию-аналог my_array_fill() и проверил ее работоспособность в php.

Что теперь?


Теперь я запилю код библиотеки libtrie в наше расширение.

Немного расскажу как можно заставить работать старые php5 расширения в php7.
Дальше я сделаю несколько основных функций из этой библиотеки в php и проверю, что получилось.
Читать дальше →
Total votes 16: ↑16 and ↓0 +16
Views 4.8K
Comments 8

Поиск анаграмм и сабанаграмм во всех словах языка

Entertaining tasks Programming *Java *Algorithms *
Решение задач с анаграммами натолкнуло на мысль:
Сколько останется слов, если удалить все анаграммы и сабанграммы из словаря русского языка

В найденном словаре больше 1,5 млн слов в различных формах

Можно сравнить каждое слово с каждым, но для 1,5 млн записей это долго и неоптимально.
В мире с бесконечной памятью можно сгенерировать подстроки всех перестановок каждого слова и проверить наш словарь на них

Но есть ли решение получше?
Читать дальше →
Total votes 13: ↑13 and ↓0 +13
Views 7.4K
Comments 6

Выпуск#38: ITренировка — актуальные вопросы и задачи от ведущих компаний

Spice IT Recruitment corporate blog Entertaining tasks Programming *
Привет! Новая неделя — новый выпуск брейнтизиров. На этот раз, с собеседований в ИТ-компанию Accolite.

Кстати, ответы на задачки из прошлого выпуска уже опубликованы, проверяйте себя и свою смекалку.

Ну что, погнали!
Читать дальше →
Total votes 8: ↑7 and ↓1 +6
Views 1.9K
Comments 2

Immutable Trie: найди то, не знаю что, но быстро, и не мусори

Тензор corporate blog JavaScript *PostgreSQL *Programming *Algorithms *
Про префиксное дерево (Trie) написано немало, в том числе и на Хабре. Вот пример, как оно может выглядеть:


И даже реализаций в коде, в том числе на JavaScript, для него существует немало — от «каноничной» by John Resig и разных оптимизированных версий до серии модулей в NPM.

Зачем же нам понадобилось использовать его для сервиса по сбору и анализу планов PostgreSQL, да еще и «велосипедить» какую-то новую реализацию?..
Читать дальше →
Total votes 17: ↑16 and ↓1 +15
Views 4.8K
Comments 10

Подсчёт слов

C++ *Algorithms *
✏️ Technotext 2022

В статье рассказывается о решении задачки с собеса в одну российскую IT-контору.

В первые месяцы ковидной эры так случилось, что на моей текущей на тот момент работе всем уполовинили зарплату и я, недолго думая, пошёл на рынок труда. На собесе в одну известную российскую IT-компанию я получил эту задачу. Задачку нужно было просто решить: решить корректно, не "убив" при этом скорость "так, чтобы совсем ужас был".

Уже за рамками "вступительного испытания" ради спортивного интереса можно было посоревноваться с авторским решением в скорости. Спустя примерно год после упомянутых событий у меня появилось свободное время, пришли новые идеи и я попытался найти предельно быстрое решение, о чём и пойдёт речь в статье.

Читать далее
Total votes 39: ↑39 and ↓0 +39
Views 11K
Comments 19

Префиксное дерево (trie)

OTUS corporate blog Algorithms *
Translation

В этой статье обсудим такую структуру данных, как «префиксное дерево» (оно же нагруженное дерево, бор, trie, prefix tree). Кратко рассмотрим основы и реализуем наиболее важные операции: вставку, поиск по ключу и префиксный поиск.

Читать далее
Total votes 19: ↑14 and ↓5 +9
Views 8.7K
Comments 1

Префиксное дерево (trie) — вставка и поиск

OTUS corporate blog Algorithms *
Translation

Префиксное дерево (нагруженное дерево, trie) — структура данных для эффективного поиска. С его помощью сложность поиска можно довести до оптимального уровня — длины ключа. Вспомним, что в хорошо сбалансированном бинарном дереве поиска данные можно найти за время, пропорциональное M * log N, где M — максимальная длина строки, а N — количество ключей в дереве. В префиксном дереве — O(M), но увеличиваются требования к памяти. Подробнее о применении префиксных деревьев см. в этой статье.

Читать далее
Total votes 7: ↑5 and ↓2 +3
Views 2.4K
Comments 2