Анатри

Анатри ^[1] — это структура данных , предназначенная для решения анаграмм . Решение анаграммы – это задача найти слово из заданного списка букв. Эти проблемы обычно встречаются в словесных играх, таких как «Эрудит» , или в газетных кроссвордах . Задача для колеса слов также состоит в том, что центральная буква появляется во всех словах, обрамленных данным набором. Могут быть введены некоторые другие условия относительно частоты (количества появлений) каждой буквы в данной входной строке. эти проблемы классифицируются как проблема удовлетворения ограничений В литературе по информатике .

Анадерево представляется как ориентированное дерево , содержащее набор слов (W), закодированных в виде строк в некотором алфавите . Внутренние вершины помечены какой-либо буквой алфавита, а листья содержат слова. Ребра помечены неотрицательными целыми числами. Анадерево обладает тем свойством, что сумма меток ребер от корня до листа равна длине слова, хранящегося на листе. Если внутренние вершины помечены как $\alpha _{1}$ , $\alpha _{2}$ ... $\alpha _{l}$ , а метки ребер $n_{1}$ , $n_{2}$ ... $n_{l}$ , то путь от корня к листу по этим вершинам и ребрам представляет собой список слов, содержащих $n_{1}$ $\alpha _{1}$ с, $n_{2}$ $\alpha _{2}$ с и так далее. Anatrees предназначены для структур данных только для чтения со всеми словами, доступными во время создания.

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

Структуры данных

Для решения анаграмм за постоянное время был предложен ряд структур данных. Двумя наиболее часто используемыми структурами данных являются алфавитная карта и карта частот.

Алфавитная карта содержит хеш-таблицу всех возможных слов, которые могут быть в языке (это называется словарем ) . Для данной входной строки отсортируйте буквы в алфавитном порядке. Эта отсортированная строка отображается на слово в хеш-таблице. Следовательно, для поиска анаграммы необходимо сортировать буквы и искать слово в хеш-таблице. Сортировка может выполняться за линейное время с помощью сортировки подсчетом , а поиск в хэш-таблице может выполняться за постоянное время. Например, для слова ANATREE алфавитная карта создаст отображение $\{AAEENRT->\{''anatree''\}\}$ .

Карта частот также хранит список всех возможных слов в словаре в хеш-таблице. Для данной входной строки карта частот сохраняет частоты (количество появлений) всех букв и использует это количество для поиска в хеш-таблице. Время выполнения в худшем случае оказывается линейным по размеру словаря. Например, для слова ANATREE алфавитная карта создаст отображение $f(A)->2,f(E)->2,f(N)->1,f(R)->1,f(T)->1$ . Слова, которых нет в строке, не записываются на карте.

Строительство

Построение анадерева начинается с выбора метки для корня и разделения слов на основе метки, выбранной для корня. Этот процесс рекурсивно повторяется для всех меток дерева. Конструкция анадерева неканонична для данного набора слов, в зависимости от метки, выбранной для корня, анадерево будет соответственно различаться. На производительность анатри во многом влияет выбор этикеток.

Ниже приведены некоторые эвристики для выбора меток:

Начинайте обозначать вершины в алфавитном порядке от корня. Такой подход снижает накладные расходы на строительство.
Начните маркировать вершины на основе относительной частоты. Для присвоения меток вершинам используется вероятностный подход. Если $W_{n}^{\alpha }$ это совокупность слов, содержащих $n\alpha s$ , то мы помечаем вершину $\alpha$ если это максимизирует ожидаемое расстояние до листа. В этом подходе наиболее часто встречающиеся символы (например, E) отмечены в корне, а наименее часто встречающиеся символы — в конце. Следующее уравнение максимизируется $D_{\alpha }=\sum _{n}n{\frac {|W_{n}^{\alpha }|}{|W|}}$ . Этот подход предотвращает длинные последовательности ребер, помеченных нулями, поскольку они не добавляют буквы в слова, генерируемые анадеревом.

Нахождение анаграмм

Чтобы найти слово в анадереве, начните с корня, в зависимости от частоты метки в данной входной строке, следуйте по ребру, имеющему эту частоту, до листа. На листе есть нужное слово. Например, рассмотрите анатри на рисунке, чтобы найти слово $dog$ , данная строка может быть $ogd$ . Начните с корня и следуйте по краю, который имеет $1$ как этикетка. Мы следуем этой метке, поскольку данная входная строка имеет $1$ $d$ . Пройдите по этому краю, пока не встретите лист. Это дает необходимое слово.

Требования к пространству и времени

Лексикон, который хранит $w$ слова (каждое слово может быть $l$ символы длиной) в алфавите $O$ имеет следующие требования к пространству.

Структура данных	Требования к пространству
Алфавитная карта	$O(wl(log\|O\|)$
Карта частот	$O(w(\|O\|logl+llog\|O\|))$
Анатри	$O(w\|O\|(log\|O\|+l))$

Наихудшее время выполнения anatree составляет $O(|w|(l+w|O|^{2}))$

Ссылки

^ Римс, Чарльз (март 2012 г.). «Анатри: быстрая структура данных для анаграмм». Журнал экспериментальной алгоритмики . 17 (1): 2012. doi : 10.1145/2133803.2133804 .

Внешние ссылки

[1] Римс, Чарльз (март 2012 г.). «Анатри: быстрая структура данных для анаграмм». Журнал экспериментальной алгоритмики . 17 (1): 2012. doi : 10.1145/2133803.2133804 .

[1]