Anatree

Anatree to struktura danych przeznaczona do rozwiązywania anagramów . Rozwiązanie anagramu polega na znalezieniu słowa z podanej listy liter. Problemy te są często spotykane w grach słownych, takich jak Scrabble lub w krzyżówkach w gazetach . Problem z kołem słów ma również warunek, że środkowa litera pojawia się we wszystkich słowach obramowanych danym zestawem. Można wprowadzić inne warunki dotyczące częstotliwości (liczby wystąpień) każdej z liter w danym ciągu wejściowym. Problemy te są klasyfikowane jako problem spełnienia ograniczeń w literaturze informatycznej.

Anatree jest reprezentowane jako ukierunkowane drzewo , które zawiera zestaw słów (W) zakodowanych jako ciągi znaków w jakimś alfabecie . Wewnętrzne wierzchołki są oznaczone jakąś literą alfabetu, a liście zawierają słowa. Krawędzie są oznaczone nieujemnymi liczbami całkowitymi. Anatree ma tę właściwość, że suma etykiet krawędzi od korzenia do liścia jest długością słowa przechowywanego w liściu. Jeśli wewnętrzne wierzchołki są oznaczone jako , $...$ ${\ Displaystyle \ alpha _ {2}}$ α $}}$ Displaystyle \ alpha _ etykiety krawędzi $to$ a $tych$ $korzenia$ od do a krawędzie to lista słów, które zawierają ${\ displaystyle n_ {1}}$ ${\ displaystyle \ alpha _ {1}}$ s, ${\ displaystyle n_ {2}}$ ${\ displaystyle \ alpha _{2}}$ s i tak dalej. Anatrees mają być strukturami danych tylko do odczytu ze wszystkimi słowami dostępnymi w czasie budowy.

Mieszany anatree

Mieszane anatree to anatree, w którym wewnętrzne wierzchołki przechowują również słowa. Mieszane anatree może zawierać słowa o różnej długości, podczas gdy w zwykłym anatree wszystkie słowa mają tę samą długość.

Struktury danych

Zaproponowano szereg struktur danych do rozwiązywania anagramów w stałym czasie. Dwie najczęściej używane struktury danych to mapa alfabetyczna i mapa częstotliwości.

Mapa alfabetyczna zawiera tablicę mieszającą wszystkich możliwych słów, które mogą występować w języku (nazywa się to leksykonem ) . Dla podanego ciągu wejściowego posortuj litery w porządku alfabetycznym. Ten posortowany ciąg jest odwzorowywany na słowo w tablicy skrótów. Stąd znalezienie anagramu wymaga posortowania liter i wyszukania słowa w tablicy skrótów. Sortowanie może odbywać się w czasie liniowym z sortowaniem liczącym, a przeglądanie tablicy mieszającej może odbywać się w stałym czasie. Na przykład, biorąc pod uwagę słowo ANATREE, mapa alfabetyczna dawałaby odwzorowanie $\ {AAEENRT-> \ {'' anatree''\}\}}$ .

Mapa częstotliwości przechowuje również listę wszystkich możliwych słów w leksykonie w tablicy mieszającej. Dla danego ciągu wejściowego mapa częstotliwości zachowuje częstotliwości (liczbę wystąpień) wszystkich liter i wykorzystuje tę liczbę do wykonania wyszukiwania w tablicy skrótów. Stwierdzono, że czas wykonania najgorszego przypadku ma liniowy rozmiar leksykonu. Na przykład, biorąc pod uwagę słowo ANATREE, mapa alfabetyczna dałaby odwzorowanie ${\ Displaystyle f (A) -> 2, f (E) -> 2, f (N) -> 1, f (R) -> 1, f (T) -> 1}$ . Słowa, które nie pojawiają się w łańcuchu, nie są zapisywane na mapie.

Budowa

Budowa drzewa anatree rozpoczyna się od wybrania etykiety dla korzenia i podziału słów na podstawie etykiety wybranej dla korzenia. Ten proces jest powtarzany rekurencyjnie dla wszystkich etykiet drzewa. Konstrukcja Anatree jest niekanoniczna dla danego zestawu słów, w zależności od etykiety wybranej dla rdzenia, anatree będzie się odpowiednio różnić. Wybór etykiet ma duży wpływ na wydajność anatree.

Poniżej przedstawiono niektóre heurystyki służące do wybierania etykiet:

Rozpocznij oznaczanie wierzchołków w porządku alfabetycznym od korzenia. Takie podejście zmniejsza koszty budowy
Rozpocznij etykietowanie wierzchołków w oparciu o częstotliwość względną. Do przypisywania etykiet do wierzchołków stosuje się podejście probabilistyczne. Jeśli $,$ zbiorem słów, które zawierają ${\ Displaystyle n \ alpha s}$ oznaczamy wierzchołek za pomocą $\ displaystyle \ alpha$ jeśli maksymalizuje oczekiwaną odległość do liścia. To podejście ma najczęściej pojawiające się znaki (takie jak E) oznaczone u nasady i najrzadziej pojawiające się znaki oznaczone na liściach. Następujące równanie jest zmaksymalizowane ${\ Displaystyle D _ {\ alfa} = \ suma _ {n} n {\ Frac {| W_ {n} ^ {\ alfa} |} {| W|}}$ } Takie podejście zapobiega powstawaniu długich sekwencji krawędzi oznaczonych zerem, ponieważ nie dodają one liter do słów generowanych przez anatree.

Znajdowanie anagramów

Aby znaleźć słowo w anatree, zacznij od korzenia, w zależności od częstotliwości etykiety w danym ciągu wejściowym, podążaj za krawędzią, która ma tę częstotliwość, aż do liścia. Liść zawiera wymagane słowo. Rozważmy na przykład anatree na rysunku, aby znaleźć słowo $.$ ciąg może być o $displaystyle ogd}$ Zacznij od nasady i podążaj za krawędzią, która $etykietę$ . Podążamy za tą etykietą, ponieważ dany ciąg wejściowy ma ${\ displaystyle 1}$ ${\ displaystyle d}$ . Przemierzaj tę krawędź, aż napotkasz liść. To daje wymagane słowo.

Wymagania przestrzenne i czasowe

Leksykon przechowujący $miejsca$ $( każde$ może mieć $.$ znaków) w alfabecie ma następujące wymagania dotyczące

Struktura danych	Wymagania dotyczące miejsca
Mapa alfabetyczna	${\ Displaystyle O (wl (log \| O \|)}$
Mapa częstotliwości	${\ Displaystyle O (w (\| O \| logl + llog \| O \|))}$
Anatree	${\ Displaystyle O (w \| O \| (log \| O \| + l)}}$

W najgorszym przypadku czas wykonania anatree to ${\ Displaystyle O (| w | (l + w | O | ^ {2}))}$

Linki zewnętrzne