翻訳と辞書 Words near each other ・ Anatrachyntis pyrrhodes ・ Anatrachyntis rhizonympha ・ Anatrachyntis rileyi ・ Anatrachyntis risbeci ・ Anatrachyntis sesamivora ・ Anatrachyntis simplex ・ Anatrachyntis strangalota ・ Anatrachyntis tentoria ・ Anatrachyntis terminella ・ Anatrachyntis tripola ・ Anatrachyntis vanharteni ・ Anatrachyntis yunnanea ・ Anatragoides ・ Anatragus ・ Anatralata ・ Anatree ・ Anatrichis ・ Anatrisauropus ・ Anatropanthus ・ Anatrophon ・ Anatrophon sarmentosus ・ Anatropi ・ Anatropites ・ Anatrytone ・ Anatrytone logan ・ Anatsabites ・ Anatta ・ Anattalakkhana Sutta ・ Anatumomab mafenatox ・ Anatólio Falé Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Anatree ： ウィキペディア英語版 Anatree 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 wordwheel, scrabble or crossword puzzles that we find in newspapers. 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 $\backslash alpha\_1$, $\backslash alpha\_2$ ... $\backslash 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$ $\backslash alpha\_1$ s, $n\_2$ $\backslash 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. == Data Structures for solving Anagrams == A number of data structures have been proposed to solve anagrams in constant time. Two of the most commonly used data structures are the Alphabetic map and the Frequency map. The Alphabetic map maintains a hash table of all the possible words that can be in the language (this is referred to as the lexicon). For a given input sting, sort the letters in alphabetic order. This sorted string maps onto a word in the hash table. Hence finding the anagram requires sorting the letters and a looking up the word in the hash table. The sorting can be done in linear time by the counting sort and hash table look up can be done in constant time. For example for the word ANATREE, the alphabetic map would produce a mapping of $\backslash$. A Frequency map also stores the list of all possible words in the lexicon in a hash table. For a given input string, the frequency map maintains the frequencies (number of appearances) of all the letters and uses this count to perform a look up in the hash table. The worst case execution time is found to be linear in size of the lexicon. For example for the word ANATREE, the alphabetic map would produce a mapping of $f(A)->2,\; f(E)->2,\; f(N)->1,\; f(R)->1,\; f(T)->2$. The words that do not appear in the string are not written in the map. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Anatree」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.