Нольдық басу шешім диаграммасы (ZSDD) – жиындарды ықшам түрде көрсетуге арналған, реттелген бинарлық шешім диаграммасының (BDD) түрі. Сирек жиындарды тиімді қысуға көмектеседі.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Бинарлық шешім диаграммасының түрі
Kind of binary decision diagram
Нөлдік басқан шешім диаграммасы (ZSDD немесе ZDD) – бұл белгілі бір айнымалы ретімен бинарлық шешім диаграммасының (BDD) нақты түрі. Бұл дерек құрылымы жиындарды канондық түрде ықшам түрде ұсынады, әсіресе кейбір комбинаторлық мәселелер үшін тиімді. Реттелген бинарлық шешім диаграммасының (OBDD) қысқарту стратегиясын еске түсіріңіз, яғни егер екі шығу жиегі бір түйінге бағытталса, түйін өзінің бірінен кейін баласымен алмастырылады. Ал ZDD-де түйін, егер оның оң жиегі 0 терминалды түйінге нұсқаса, теріс баласымен алмастырылады. Бұл сирек жиындарды жақсырақ қысуға мүмкіндік беретін баламалы берік нормалық форманы ұсынады. Ол 1993 жылы Шин Ичи Минато ұсынған қысқарту ережесіне негізделген.
A zero suppressed decision diagram (ZSDD or ZDD) is a particular kind of binary decision diagram (BDD) with fixed variable ordering. This data structure provides a canonically compact representation of sets, particularly suitable for certain combinatorial problems. Recall the Ordered Binary Decision Diagram (OBDD) reduction strategy, i. e. a node is replaced with one of its children if both out edges point to the same node. In contrast, a node in a ZDD is replaced with its negative child if its positive edge points to the terminal node 0. This provides an alternative strong normal form, with improved compression of sparse sets. It is based on a reduction rule devised by Shin ichi Minato in 1993.
Өмірбаян
Бинарлық шешім диаграммасында Буль функциясы бірнеше шешім түйіндері мен терминалдық түйіндерден тұратын тамырланған, бағытталған, ациклді граф ретінде бейнелене алады. 1993 жылы Жапониядан Шин Ичи Минато Рэндал Брайанттың BDD-ін комбинаторлық мәселелерді шешу үшін модификациялады. Оның "Нөлдік басқан" BDD-лері бит векторларының сирек жиынтықтарын бейнелеуге және манипуляциялауға арналған. Егер мәселенің деректері ұзындығы n бит векторлары түрінде берілсе, онда векторлардың кез келген ішкі жиыны n айнымалыға арналған Буль функциясы арқылы көрсетіледі, егер айнымалыға сәйкес келетін вектор жиынтықта болса, ол 1-ді қайтарады. Брайанттың сөзіне сүйенсек, логикалық функциялардың түрлерін қосынды көбейтіндісі түріндегі мәселелерді көрсету үшін қолдануға болады. Мұндай формалар көбінесе "кубтар" жиынтығы ретінде бейнеленеді, олардың әрқайсысы 0, 1 және символдарынан тұратын жолмен белгіленеді. Мысалы, функциясын жиынтығы арқылы көрсетуге болады. 1, 0 және символдарын білдіру үшін 10, 01 және 00 биттерін пайдаланып, жоғарыдағы жиынтықты биттік векторлармен түрінде көрсетуге болады. Биттік векторлар жиынтығының сирек екенін атап өту керек, себебі векторлардың саны 2-ден кем, бұл биттік векторлардың максималды саны, және жиынтықта көптеген нөлге тең элементтер бар. Осы жағдайда, егер түйіннің айнымалысын 1-ге орнату функцияның 0-ді қайтаруына себеп болса, түйін қалдырылуы мүмкін. Бұл 1 біт позициясында вектор жиынтықта жоқ екенін білдіреді. Сирек жиынтықтар үшін бұл жағдай жиі кездеседі, сондықтан көптеген түйіндерді жоюға болады. Минато ZDD-нің комбинаторлық мәселелер үшін, мысалы, екі деңгейлі логикалық минимизацияның классикалық мәселелері, аттың жүрісі мәселесі, қателерді модельдеу, уақыттық талдау, N патшайым мәселесі, сондай-ақ нашар бөлу үшін ерекше қолайлы екенін дәлелдеді. ZDD-ді пайдалану арқылы n биттік векторлар жиынтығының OBDD-дегі бейнелеуінің мөлшерін ең көп дегенде n есеге азайтуға болады. Іс жүзінде, бұл оңтайландыру статистикалық тұрғыдан маңызды.
In a binary decision diagram, a Boolean function can be represented as a rooted, directed, acyclic graph, which consists of several decision nodes and terminal nodes. In 1993, Shin ichi Minato from Japan modified Randal Bryant's BDDs for solving combinatorial problems. His "Zero Suppressed" BDDs aim to represent and manipulate sparse sets of bit vectors. If the data for a problem are represented as bit vectors of length n, then any subset of the vectors can be represented by the Boolean function over n variables yielding 1 when the vector corresponding to the variable assignment is in the set. According to Bryant, it is possible to use forms of logic functions to express problems involving sum of products. Such forms are often represented as sets of "cubes", each denoted by a string containing symbols 0, 1, and For instance, the function can be illustrated by the set By using bits 10, 01, and 00 to denote symbols 1, 0, and – respectively, one can represent the above set with bit vectors in the form of Notice that the set of bit vectors is sparse, in that the number of vectors is fewer than 2, which is the maximum number of bit vectors, and the set contains many elements equal to zero. In this case, a node can be omitted if setting the node variable to 1 causes the function to yield 0. This is seen in the condition that a 1 at some bit position implies that the vector is not in the set. For sparse sets, this condition is common, and hence many node eliminations are possible. Minato has proved that ZDDs are especially suitable for combinatorial problems, such as the classical problems in two level logic minimization, knight's tour problem, fault simulation, timing analysis, the N queens problem, as well as weak division. By using ZDDs, one can reduce the size of the representation of a set of n bit vectors in OBDDs by at most a factor of n. In practice, the optimization is statistically significant.
Ерекшеліктері
ZDD-нің бір ерекшелігі – комбинация жиынтығы бірдей болғанда, форма кіріс айнымалыларының санына тәуелді емес. Графиктерді жасамас бұрын кіріс айнымалыларының санын анықтау қажет емес. ZDD-лер ешқашан комбинацияда кездеспейтін объектілерге қатысты айнымалыларды автоматты түрде жояды, осылайша сирек кездесетін комбинацияларды өңдеуде тиімділікке қол жеткізеді. ZDD-нің тағы бір артықшылығы – графиктегі 1-ге тең бағытталған жолдардың саны комбинация жиынтығындағы элементтер санымен дәл сәйкес келеді. Ал бастапқы BDD-лерде түйіндерді жою осы қасиетті бұзады. Сондықтан, ZDD-лер комбинация жиынтықтарын көрсету үшін қарапайым BDD-лерден артық. Дегенмен, 7-суретте көрсетілгендей, қарапайым Бульдық функцияларды көрсету үшін бастапқы BDD-лерді қолдану тиімдірек.
One feature of ZDDs is that the form does not depend on the number of input variables as long as the combination sets are the same. It is unnecessary to fix the number of input variables before generating graphs. ZDDs automatically suppress the variables for objects which never appear in combination, hence the efficiency for manipulating sparse combinations. Another advantage of ZDDs is that the number of 1 paths in the graph is exactly equal to the number of elements in the combination set. In original BDDs, the node elimination breaks this property. Therefore, ZDDs are better than simple BDDs to represent combination sets. It is, however, better to use the original BDDs when representing ordinary Boolean functions, as shown in Figure 7.
ZDD сөздіктер ретінде
ZDD-ді ағылшын тіліндегі бес әріпті сөздерді, мысалы, Стэнфорд ГрафБейсінен (Stanford GraphBase) алынған WORDS жиынтығын (көлемі 5757) көрсетуге болады. Мұны істеудің бір жолы – егер және тек қана егер бес сан , , , , ағылшын сөзінің әріптерін кодтаса, онда 1 деп анықталған функцияны қарастыру. Мысалы, 25 айнымалысы бар функцияның Z(f) = 6233 түйіні бар – бұл 5757 сөзді көрсету үшін тым нашар емес. Бинарлық ағаштармен, трилермен (tries) немесе хэш-кестелермен (hash tables) салыстырғанда, ZDD қарапайым іздеулерді орындау үшін ең жақсысы болмауы мүмкін, бірақ ол тек ішінара көрсетілген деректерді немесе кілтке шамамен сәйкес келуі керек деректерді алуда тиімді. Күрделі сұраныстарды оңай шешуге болады. Сонымен қатар, ZDD-де көп айнымалылар болмайды. Шын мәнінде, ZDD-ді пайдалану арқылы осы бес әріпті сөздерді 26 × 5 = 130 айнымалысы бар сиреп (sparse) функция ретінде көрсетуге болады, мысалы, айнымалы екінші әріптің "a" екенін анықтайды. "crazy" сөзін көрсету үшін F-ті шындыққа (true) айналдыру керек, егер және барлық басқа айнымалылар 0 болса. Осылайша, F 5757 жиынтықтан тұратын отбасы ретінде қарастырылуы мүмкін. Осы 130 айнымалымен ZDD өлшемі Z(F) 6233 орнына 5020-ға тең. Кнутқа (Knuth) сәйкес, BDD-ді пайдалану арқылы B(F)-тың эквиваленттік өлшемі 46,189 – Z(F)-тан әлдеқайда үлкен. Ұқсас теориялар мен алгоритмдерге ие болғанына қарамастан, ZDD-лер осы мәселеде BDD-ден айтарлықтай жақсы нәтижелер көрсетеді. Нәтижесінде, ZDD-лер бізге BDD-лер үшін тым қиын болатын кейбір сұраныстарды орындауға мүмкіндік береді. Субмножектердің (subset) күрделі отбасыларын элементар отбасылардан оңай құрастыруға болады. Белгілі бір үлгіні (pattern) қамтитын сөздерді іздеу үшін, ZDD-де отбасы алгебрасын (family algebra) пайдаланып, P үлгісін есептеуге болады, мысалы .
ZDDs can be used to represent the five letter words of English, the set WORDS (of size 5757) from the Stanford GraphBase for instance. One way to do this is to consider the function that is defined to be 1 if and only if the five numbers , , , encode the letters of an English word, where , , For example, The function of 25 variables has Z(f) = 6233 nodes – which is not too bad for representing 5757 words. Compared to binary trees, tries, or hash tables, a ZDD may not be the best to complete simple searches, yet it is efficient in retrieving data that is only partially specified, or data that is only supposed to match a key approximately. Complex queries can be handled with ease. Moreover, ZDDs do not involve as many variables. In fact, by using a ZDD, one can represent those five letter words as a sparse function that has 26×5 = 130 variables, where variable for example determines whether the second letter is "a". To represent the word "crazy", one can make F true when and all other variables are 0. Thus, F can be considered as a family consisting of the 5757 subsets , etc. With these 130 variables the ZDD size Z(F) is in fact 5020 instead of 6233. According to Knuth, the equivalent size of B(F) using a BDD is 46,189—significantly larger than Z(F). In spite of having similar theories and algorithms, ZDDs outperform BDDs for this problem with quite a large margin. Consequently, ZDDs allow us to perform certain queries that are too onerous for BDDs. Complex families of subset can readily be constructed from elementary families. To search words containing a certain pattern, one may use family algebra on ZDDs to compute where P is the pattern, e. g .
Жоғарғы жақтағы проблема
"Рыцарь" тур проблемасы тарихи маңызға ие. Рыцарь графигі шахмат тақтасының шаршыларын бейнелеу үшін n2 төбелік нүктелерді қамтиды. Қабырғалары рыцарьдың заңды қимылдарын көрсетеді. Рыцарь тақтаның әр шаршысын дәл бір рет басып өтуі мүмкін. Олаф Шрёер, М. Лёббинг және Инго Вегенер бұл мәселеге, атап айтқанда тақтада, графиктегі әр қабырғаға бульдік айнымалыларды тағайындау арқылы, барлық қабырғаларды белгілеу үшін барлығы 156 айнымалымен қарады. Мәселенің шешімі 156 биттік комбинациялық вектормен көрсетілуі мүмкін. Минатоның сөзіне сәйкес, барлық шешімдер үшін ZDD құрастыру тікелей шешу үшін тым үлкен. Бөліп-басқару әдісі тиімдірек. Мәселені тақтаның екі бөлігіне бөлу және кіші кеңістіктерде ZDD құрастыру арқылы, әр шешімі 64 қабырғадан тұратын "Рыцарь" тур проблемасын шешуге болады. Дегенмен, граф тығыз болғандықтан, ZDD пайдаланудың артықшылығы айқын емес.
The Knight's tour problem has a historical significance. The knight's graph contains n2 vertices to depict the squares of the chessboard. The edges illustrate the legal moves of a knight. The knight can visit each square of the board exactly once. Olaf Schröer, M. Löbbing, and Ingo Wegener approached this problem, namely on a board, by assigning Boolean variables for each edge on the graph, with a total of 156 variables to designate all the edges. A solution of the problem can be expressed by a 156 bit combination vector. According to Minato, the construction of a ZDD for all solutions is too large to solve directly. It is easier to divide and conquer. By dividing the problems into two parts of the board, and constructing ZDDs in subspaces, one can solve The Knight's tour problem with each solution containing 64 edges. However, since the graph is not very sparse, the advantage of using ZDDs is not so obvious.
Ақаулықтарды симуляциялау
Н. Такахаси және авторлар тобы OBDD-ді пайдаланып, бірнеше ақауды симуляциялау әдісін ұсынды. Бұл дедуктивті әдіс ақау жиынтығын бастапқы кірістерден бастапқы шығыстарға дейін таратады және бастапқы шығыстарда ақауларды анықтайды. Бұл әдіс бірмүшелік кубтар жиынымен жұмыс істейтіндіктен, ZDD тиімдірек болып табылады. Бірмүшелік кубтар жиыны есептеулерінде ZDD-нің оңтайландыру мүмкіндіктері, ZDD-нің VLSI CAD жүйелерін жасауда және көптеген басқа да қолданбаларда пайдалы екенін көрсетеді.
N. Takahashi et al suggested a fault simulation method given multiple faults by using OBDDs. This deductive method transmits the fault sets from primary inputs to primary outputs, and captures the faults at primary outputs. Since this method involves unate cube set expressions, ZDDs are more efficient. The optimizations from ZDDs in unate cube set calculations indicate that ZDDs could be useful in developing VLSI CAD systems and in a myriad of other applications.