Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Сжатое префиксное дерево

Из Википедии — свободной энциклопедии

Базисное дерево
Тип дерево
Год изобретения 1968
Автор Дональд Р. Моррисон
Сложность в О-символике
В худшем случае
Поиск
Вставка
Удаление
Логотип Викисклада Медиафайлы на Викискладе
Пример базисного дерева для русского языка
Пример базисного дерева для русского языка

Базисное дерево (также компактное префиксное дерево, основное дерево, дерево остатков[1]) — это структура данных, представляющая собой оптимизированную по памяти реализацию префиксного дерева. В базисном дереве узел , являющийся единственным потомком узла , сливается с узлом .

Временная сложность операций поиска, добавления и удаления элемента из базисного дерева оценивается как , где  — длина обрабатываемого элемента. Время работы не зависит от количества элементов в дереве.

В отличие от обычных префиксных деревьев, узел базисного дерева может быть помечен как одним элементом (символом, битом и т. д.), так и последовательностью элементов. Это делает базисное дерево более эффективным для небольших наборов строк (особенно если сами строки достаточно длинные), и также для наборов, имеющих небольшое количество длинных префиксов.

Применение

  • Базисное дерево используется, в частности, для синтаксического анализа естественных языков[2].
  • Базисное дерево является одной из структур данных ядра Linux[3].

Примечания

  1. Структура Radix Tree для сжатия данных https://habrahabr.ru/post/141145/
  2. Pymorphy 2 https://m.habrahabr.ru/post/176575/
  3. Robert Love. Linux Kernel Development. Third Edition. 2010 https://docs.google.com/file/d/0B1iyZaHiAMfFZE9aXzNBOXR0OGM/edit?pli=1 Архивная копия от 15 декабря 2015 на Wayback Machine

Ссылки

Эта страница в последний раз была отредактирована 1 марта 2020 в 16:14.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).