Структура данных Бор (Цифровое дерево)

Термины   18 января 2013  Автор статьи:  
geekbrains.ru/

Бор — структура данных, которая хранит информацию о наборе строк и например позволяет проверять вхождения заданной строки t в заданной набор строк за длину t. Здесь под вхождением понимается проверка того, что строка совпадает с элементом набора.
Бор — это такое дерево на ребрах которого написаны символы, тогда путь до каждого из листьев произноситься как некоторая строка из набора, а каждая подстрока произносится как некий путь от корня. Обычно вершины в которых заканчивается строка помечаются. Для проверки строки t на принадлежность набору надо спускать по дереву и если:

  • удалось спуститься произнеся строку t целиком
  • спуск завершился в помеченной вершине, то строка t является элементом набора

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

Сжатый бор

В сжатом боре хранятся не ребра, а три числа:

  • Номер строки
  • Левая граница
  • Правая граница

— подстрокой какой строки набора и с какими левыми и правыми элементами данное ребро является.
В сжатом боре не ветвящиеся пути сжимаются в одно ребро. Во время поиска по сжатому бору позиция поиска в наборе определяется ребром и смещением в нем. Проверки на совпадения соответствующих символов лучше попадают в кеш процессора, а также есть возможность использовании операции memcmp. Таким образом зачастую сжатый бор требует меньше памяти и поиск в нем эффективней работает. Развитие идеи использования бора приводит к обобщению префикс функции для набора строк, а это в свою очередь используется в алгоритме Ахо — Корасика поиска в тексте набора образцов: «Задан текст t и набор образцов S1 и так далее Sn требуется найти вхождения хотя бы одного образца в текст».

Научиться программировать

  • на Delphi

  • на Java

  • на C++

geekbrains.ru/
geekbrains.ru/