Анатри - Anatree - Wikipedia

Анатри

An Анатри ^[1] это структура данных предназначен для решения анаграммы. Решение анаграммы - это проблема поиска слова из заданного списка букв. Эти проблемы часто встречаются в словесных играх, таких как Скраббл или в газете кроссворд загадки. Задача для колеса слов также состоит в том, что центральная буква появляется во всех словах, обрамленных данным набором. Некоторые другие условия могут быть введены относительно частоты (количества появлений) каждой из букв в данной входной строке. Эти проблемы классифицируются как Проблема удовлетворения ограничений в литературе по информатике.

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

Смешанный анатри

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

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

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

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

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

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

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

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

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

Поиск анаграмм

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

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

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

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

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

внешняя ссылка

• Чертовски крутые алгоритмы, часть 3 - деревья анаграммы
• Анаграмма на sourceforge

Рекомендации

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