2

三分探索木について私が理解していることから、それらは探して見つけることができるアイテムで逆決定論的です（正しい用語についてはわかりません）。つまり、 cat、bicycle、axisの三分木を作成し、その三分木を誰かに渡せば、その人はそこからこれらの 3 つの単語を差し引くことができるはずです。

これは正しいです？

ISMAP、SELECTED、COMPACT (実際、HTML 4 の属性) などの単語を含む 3 項ツリー構造があり、そのツリーに格納されている項目の完全なリストを取得できるかどうか疑問に思っているためです (元のドキュメントなくなっている）。構造は次のようになります。

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, 
};
4

2 に答える 2

2

アルゴリズムはこのようなものだと思います

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
于 2011-11-15T21:53:25.223 に答える
2

3 番目の分岐が暗黙的であるため (つまり、現在のエントリの次のエントリ)、データ構造は厳密には三分木ではありません。これは、バイナリ ツリー構造内に実装されたトライのようなものです。4 つの各数値は、 のような構造体に対応しstruct { char letter, Loff, Roff, flag}ます。たとえば、エントリ 0 =72,5,77,0は文字 'H'、左オフセット 5、右オフセット 77、フラグ 0 (おそらくターミナルではないことを意味します) です。左オフセットに続いて、#0 の後に 5 つのエントリが67,12,40,0ありC, 12, 40, 0ます。#5 の後の 12 エントリ65,0,0,0は ですA,0,0,0。それと次の 5 つのエントリ (65、67、84、73、79、78) は明らかに string に対応しますACTION。右側のオフセットに続いて、#0 の後の 77 エントリ、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.

葉に向かってツリーをたどると、現在の文字列に文字が追加され (トライ内をトラバースする場合と同様)、上に戻ると (葉から離れて) 現在の文字列の末尾から文字が削除されます。

于 2011-11-15T22:53:47.237 に答える