Здравствуй, Хабрахабр. Сегодня я хочу рассказать о такой замечательной структуре данных как словарь на нагруженном дереве, известной также как префиксное дерево, или trie.
Что это ?
Нагруженное дерево — структура данных реализующая интерфейс ассоциативного массива, то есть позволяющая хранить пары «ключ-значение». Сразу следует оговорится, что в большинстве случаев ключами выступают строки, однако в качестве ключей можно использовать любые типы данных, представимые как последовательность байт (то есть вообще любые).
Екатерина Малахова, редактор-фрилансер, специально для блога Нетологии адаптировала статью Beau Carnes об основных типах структур данных.
«Плохие программисты думают о коде. Хорошие программисты думают о структурах данных и их взаимосвязях», — Линус Торвальдс, создатель Linux.
Структуры данных играют важную роль в процессе разработки ПО, а еще по ним часто задают вопросы на собеседованиях для разработчиков. Хорошая новость в том, что по сути они представляют собой всего лишь специальные форматы для организации и хранения данных.
В этой статье я покажу вам 10 самых распространенных структур данных.
Когда мы пытаемся определить какому оператору принадлежит номер телефона, то обычно смотрим на его DEF код. Например, если номер начинается на 916, то это МТС, на 968 – Билайн, 926 – Мегафон (все зависит от вашего региона). Но этот метод очень условный и совершенно не подходит когда нужны точные данные. В реальности все сложнее: DEF коды часто делят между собой несколько операторов, и совсем необязательно, что искомый номер относится к операторам большой четверки. Ну и наконец, номер можно просто портировать.
В статье я расскажу о том, как по номеру телефона достоверно определить мобильного оператора который его обслуживает, а также получить дополнительную, «бесплатную» информацию – домашний регион абонента. Использовать эти данные можно как угодно, начиная от предзаполнения адреса в анкете пользователя и перенаправления на региональную версию вашего сервиса, до использования этих данных в процессинге и статистике. В конце статьи будет ссылка на github с исходниками.
Сразу оговорюсь, что домашний регион абонента, по большому счету, никак не связан с текущим месторасположением пользователя, т.е. определяемый регион отвечает на вопрос «Откуда номер?», а не «Где пользователь?».
Сколько останется слов, если удалить все анаграммы и сабанграммы из словаря русского языка
В найденном словаре больше 1,5 млн слов в различных формах
Можно сравнить каждое слово с каждым, но для 1,5 млн записей это долго и неоптимально.
В мире с бесконечной памятью можно сгенерировать подстроки всех перестановок каждого слова и проверить наш словарь на них
Привет, меня зовут Петр и я работаю в Badoo в команде биллинга. В этой статье я хочу поделиться своим опытом работы над пет-проектом по созданию хранилища фотографий с возможностью поиска дубликатов. Я расскажу, с каким багажом я вошел в этот проект, в чем заключалась задача и как её решал. В конце поделюсь результатами и почему я считаю, что это один из лучших проектов, которым я занимался.
Однажды мои знакомые попросили сделать им хранилище изображений для их проекта по модерации внешних ресурсов. Условия: срок хранения до трех лет, фотографии при этом присылаются неравномерно, в среднем поток — 150.000 картинок в сутки.
Казалось бы, достаточно банальная задача. Если бы не еще одно условие: хорошо бы сопоставлять фотографии с уже имеющимися: искать дубликаты и помечать их.
В этой статье обсудим такую структуру данных, как «префиксное дерево» (оно же нагруженное дерево, бор, trie, prefix tree). Кратко рассмотрим основы и реализуем наиболее важные операции: вставку, поиск по ключу и префиксный поиск.
Префиксное дерево (нагруженное дерево, trie) — структура данных для эффективного поиска. С его помощью сложность поиска можно довести до оптимального уровня — длины ключа. Вспомним, что в хорошо сбалансированном бинарном дереве поиска данные можно найти за время, пропорциональное M * log N, где M — максимальная длина строки, а N — количество ключей в дереве. В префиксном дереве — O(M), но увеличиваются требования к памяти. Подробнее о применении префиксных деревьев см. в этой статье.
