Можно ли сгенерировать все возможные термины, которые можно найти в троичном дереве поиска? - PullRequest
Новая
       27

Можно ли сгенерировать все возможные термины, которые можно найти в троичном дереве поиска?

2 голосов
/ 16 ноября 2011

Из того, что я понимаю о троичных поисковых деревьях, они являются обратными детерминированными в элементах, которые могут быть найдены и найдены (не уверены в правильных терминах). Что я имею в виду, если вы создаете троичное дерево для кошка , велосипед , ось , и вы даете кому-то троичное дерево, он должен иметь возможность вычесть эти три слов из него.

Это правильно?

Я спрашиваю, потому что у меня есть троичная древовидная структура, которая содержит такие слова, как ISMAP, SELECTED и COMPACT (действительно, атрибуты HTML 4), и мне интересно, смогу ли я получить полный список элементов, хранящихся в этом дереве (оригинальная документация пропала). Структура выглядит так: 

internal static byte [] htmlAttributes = {
   72,5,77,0, 82,0,0,0, 69,0,0,0, 70,0,0,0, 0,0,0,1, 67,12,40,0, 79,7,0,0,
   77,31,0,0, 80,0,0,0, 65,0,0,0, 67,0,0,0, 84,0,0,0, 0,0,0,2, 73,11,18,0,
   84,0,0,0, 69,0,0,0, 0,0,0,1, 65,0,0,0, 67,0,0,0, 84,0,0,0, 73,0,0,0,
   79,0,0,0, 78,0,0,0, 0,0,0,1, 72,0,0,0, 69,0,0,0, 67,0,0,0, 75,0,0,0,
   69,0,0,0, 68,0,0,0, 0,0,0,2, 76,0,0,0, 65,0,0,0, 83,0,0,0, 83,0,0,0,
   73,0,0,0, 68,0,0,0, 0,0,0,1, 68,0,0,0, 69,0,0,0, 66,0,0,0, 65,0,0,0,
   83,0,0,0, 69,0,0,0, 0,0,0,1, 68,0,28,0, 69,7,15,0, 67,0,22,0, 76,0,0,0,
   65,0,0,0, 82,0,0,0, 69,0,0,0, 0,0,0,2, 65,0,0,0, 84,0,0,0, 65,0,0,0,
   0,0,1,1, 83,0,0,0, 82,0,0,0, 67,0,0,0, 0,0,0,1, 73,0,0,0, 83,0,0,0,
   65,0,0,0, 66,0,0,0, 76,0,0,0, 69,0,0,0, 68,0,0,0, 0,0,0,2, 70,0,0,0,
   69,0,0,0, 82,0,0,0, 0,0,0,2, 70,0,0,0, 79,0,0,0, 82,0,0,0, 0,0,0,1,
   78,8,48,0, 79,36,0,0, 83,30,55,0, 72,0,0,0, 65,0,0,0, 68,0,0,0, 69,0,0,0,
   0,0,0,2, 77,9,0,0, 85,0,0,0, 76,0,0,0, 84,0,0,0, 73,0,0,0, 80,0,0,0,
   76,0,0,0, 69,0,0,0, 0,0,0,2, 73,0,6,0, 83,0,0,0, 77,0,0,0, 65,0,0,0,
   80,0,0,0, 0,0,0,2, 76,0,0,0, 79,0,0,0, 78,0,0,0, 71,0,0,0, 68,0,0,0,
   69,0,0,0, 83,0,0,0, 67,0,0,0, 0,0,0,1, 72,0,9,0, 82,0,0,0, 69,0,0,0,
   70,0,0,0, 0,0,0,2, 65,0,0,0, 77,0,0,0, 69,0,0,0, 0,0,0,1, 82,0,0,0,
   69,0,0,0, 83,0,0,0, 73,0,0,0, 90,0,0,0, 69,0,0,0, 0,0,0,2, 82,14,22,0,
   69,0,0,0, 65,0,0,0, 68,0,0,0, 79,0,0,0, 78,0,0,0, 76,0,0,0, 89,0,0,0,
   0,0,0,2, 87,0,0,0, 82,0,0,0, 65,0,0,0, 80,0,0,0, 0,0,0,2, 80,0,0,0,
   82,0,0,0, 79,0,0,0, 70,0,0,0, 73,0,0,0, 76,0,0,0, 69,0,0,0, 0,0,0,1,
   83,0,12,0, 82,3,0,0, 67,0,0,0, 0,0,0,1, 69,0,0,0, 76,0,0,0, 69,0,0,0,
   67,0,0,0, 84,0,0,0, 69,0,0,0, 68,0,0,0, 0,0,0,2, 85,0,0,0, 83,0,0,0,
   69,0,0,0, 77,0,0,0, 65,0,0,0, 80,0,0,0, 0,0,0,1, 
};

Ответы [ 2 ]

2 голосов
/ 16 ноября 2011

Структура данных не является точно троичным деревом, поскольку третья ветвь неявна (, т.е. , следующая запись после текущей записи). Это похоже на trie , реализованный в бинарной древовидной структуре. Каждые 4 числа соответствуют структуре, подобной struct { char letter, Loff, Roff, flag}. Например, запись 0 = 72,5,77,0 - это буква «H», смещение влево 5, смещение вправо 77, флаг 0 (возможно, это не терминал). После левого смещения, через 5 записей после # 0 мы имеем 67,12,40,0, что составляет C, 12, 40, 0; 12 записей после # 5, 65,0,0,0 - A,0,0,0. Это и следующие 5 записей (с 65,67,84,73,79,78), очевидно, соответствуют строке ACTION. После правого смещения, 77 записей после # 0, мы имеем 78,8,48,0, 79,36,0,0, 83,30,55,0, 72,0,0,0, 65,... или N, O и S записей с ветвями, за которыми следуют записи H, A, D, E без явных ветвей, чтобы сделать NOSHADE.

Когда вы следуете по дереву к листьям, добавляйте буквы в текущую строку (как при обходе по дереву) и, возвращаясь вверх (от листьев), сбрасывайте буквы с конца текущей строки.

2 голосов
/ 16 ноября 2011

Я думаю, что алгоритм выглядит примерно так 

printOutWords(root, wordSoFar)
     if (!root.hasMiddle)
        print wordSoFar + root.char

     if (root.hasMiddle)
        printOutWords(root.middle, wordSoFar + root.char)
     if (root.hasLeft)
        printOutWords(root.left, wordSoFar)
     if (root.hasRight)
        printOutWords(root.right, wordSoFar)

Затем начните с 

printOutWords(ternaryTree, "")

Я не знаю, как декодировать ваш массив, но если вы можете реализовать эти операции, я думаю, что-то вроде этого.

Хорошо, вот код C #, который работает на основе простого представления массива. Я использовал дерево из этой статьи в Википедии

http://en.wikipedia.org/wiki/Ternary_search_tree

Я представлял его в виде массива, где корнем является элемент 0, а потом его дочерние элементы равны 1, 2, 3. Детям 1, 4,5,6 и так далее. «\ 0» используется для обозначения того, что ребенка больше нет. Алгоритм такой же, как и выше. 

using System;
using System.Text;

namespace TreeDecode
{
    class Program
    {
        // http://en.wikipedia.org/wiki/Ternary_search_tree
        //The figure below shows a ternary search tree with the strings "as", "at", "cup", "cute", "he", "i" and "us":
        internal static char[] searchTree = {
                                                                               'c', 
                              'a',                                             'u',                                               'h', 
               '\0',          't',          '\0',            '\0',             't',           '\0',              '\0',            'e',            'u',
         '\0','\0','\0', 's','\0','\0','\0','\0','\0',  '\0','\0','\0',  'p','e','\0',   '\0','\0','\0',    '\0','\0','\0', '\0','\0','\0',   'i','s','\0',
        };

       static void printOutWords(char[] tree, int root, string wordSoFar) {
          if (!HasMiddle(tree, root))
              Console.WriteLine(wordSoFar + CharAt(tree, root));

          if (HasMiddle(tree, root))
              printOutWords(tree, MiddleKid(root), wordSoFar + CharAt(tree, root));
          if (HasLeft(tree, root))
              printOutWords(tree, LeftKid(root), wordSoFar);
          if (HasRight(tree, root))
              printOutWords(tree, RightKid(root), wordSoFar);

        }    

        private static int RightKid(int root)
        {
            return root * 3 + 3;            
        }

        private static bool HasRight(char[] tree, int root)
        {
            int rightIndex = RightKid(root);
            return (rightIndex < tree.Length && tree[rightIndex] != 0);
        }

        private static int LeftKid(int root)
        {
            return root * 3 + 1;
        }

        private static bool HasLeft(char[] tree, int root)
        {
            int leftIndex = LeftKid(root);
            return (leftIndex < tree.Length && tree[leftIndex] != 0);
        }

        private static int MiddleKid(int root)
        {
            return root * 3 + 2;
        }

        private static bool HasMiddle(char[] tree, int root)
        {
            int middleIndex = MiddleKid(root);
            return (middleIndex < tree.Length && tree[middleIndex] != 0);
        }

        private static int NumKids(char[] tree, int root)
        {
            return (HasMiddle(tree, root) ? 1 : 0) + (HasRight(tree, root) ? 1 : 0) + (HasLeft(tree, root) ? 1 : 0);
        }


        private static string CharAt(char[] tree, int root)
        {
            return new String(tree[root], 1);
        }


        static void Main(string[] args)
        {
            printOutWords(searchTree, 0, "");
        }
    }
}

Это печатает 

cute
cup
at
as
he
us
i
...