Anatree

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

An anatree is a data structure designed to solve anagrams. Solving an anagram is the problem of finding a word from a given list of letters. These problems are commonly encountered in word games like Scrabble or in newspaper crossword puzzles. The problem for the wordwheel also has the condition that the central letter appear in all the words framed with the given set. Some other conditions may be introduced regarding the frequency (number of appearances) of each of the letters in the given input string.

These problems are classified as Constraint satisfaction problem in computer science literature. An anatree is represented as a directed tree which contains a set of words (W) encoded as strings in some alphabet. The internal vertices are labelled with some letter in the alphabet and the leaves contain words. The edges are labelled with non-negative integers. An anatree has the property that the sum of the edge labels from the root to the leaf is the length of the word stored at the leaf.

If the internal vertices are labelled as \alpha_1 , \alpha_2 ... \alpha_l , and the edge labels are n_1 , n_2 ... n_l , then the path from the root to the leaf along these vertices and edges are a list of words that contain n_1 \alpha_1 s, n_2 \alpha_2 s and so on. Anatrees are intended to be read only data structures with all the words available at construction time.…

An anatree is a data structure designed to solve anagrams. Solving an anagram is the problem of finding a word from a given list of letters. These problems are commonly encountered in word games like Scrabble or in newspaper crossword puzzles. The problem for the wordwheel also has the condition that the central letter appear in all the words framed with the given set. Some other conditions may be introduced regarding the frequency (number of appearances) of each of the letters in the given input string.

These problems are classified as Constraint satisfaction problem in computer science literature. An anatree is represented as a directed tree which contains a set of words (W) encoded as strings in some alphabet. The internal vertices are labelled with some letter in the alphabet and the leaves contain words. The edges are labelled with non-negative integers. An anatree has the property that the sum of the edge labels from the root to the leaf is the length of the word stored at the leaf.

If the internal vertices are labelled as \alpha_1 , \alpha_2 ... \alpha_l , and the edge labels are n_1 , n_2 ... n_l , then the path from the root to the leaf along these vertices and edges are a list of words that contain n_1 \alpha_1 s, n_2 \alpha_2 s and so on. Anatrees are intended to be read only data structures with all the words available at construction time. A mixed anatree is an anatree where the internal vertices also store words.

A mixed anatree can have words of varying lengths, where as in a regular anatree, all words are of the same length. Start labeling vertices based on the relative frequency. A probabilistic approach is used to assign labels to vertices. If W_n^\alpha is the set of words that contain n \alpha s , then we label the vertex with \alpha if it maximizes the expected distance to the leaf. This approach has the most frequently appearing characters (like E) labeled at the root and the least frequently appearing characters labeled at the leaves.

The following equation is maximized D_\alpha = \sum_n n \frac . This approach prevents long sequences of zero labeled edges since they do not contribute letters to the words generated by the anatree.

References

External links

Damn Cool Algorithms Part 3 - Anagram Trees Anagram at sourceforge

Text derived from https://en.wikipedia.org/w/index.php?oldid=1373805514 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.