[科普中國]-代數(shù)格

基礎(chǔ)知識格論

格論論述次序及包含的性質(zhì)，是布爾代數(shù)的推廣，現(xiàn)已成為代數(shù)的重要組成部分，并在泛函分析、賦值論、幾何、邏輯、計(jì)算機(jī)科學(xué)、圖論等方面有廣泛的應(yīng)用。所謂格即指在集合L中定義兩個代數(shù)運(yùn)算∨和∧，這兩個代數(shù)運(yùn)算滿足：1

(1)a∨a = a ， a∧ a = a(冪等律);

(2)a ∨ b = b ∨ a，a ∧ b=b ∧ a(交換律);

(3)a ∨ (b ∨ c) = (a ∨ b) ∨c，a ∧ b(b ∧ c)=(a∧b) ∧ c(結(jié)合律);

(4)a ∨ (a ∧b)=a，a ∧ (a∨ b)=a(吸收律)，

記作(L，≤)。格論中最重要的概念是集合上的半序關(guān)系。格的種類有分配格、模格、完全格等。

格“格”一種特殊的偏序集。在許多數(shù)學(xué)對象中，所考慮的元素之間具有某種順序。

例如，一組實(shí)數(shù)間的大小順序；一個集合的諸子集（或某些子集）間按（被包含）所成的順序 ；一組命題間按蘊(yùn)涵所成的順序；等等。這種順序一般不是全序，即不是任意二元素間都能排列順序，而是在部分元素間的一種順序即偏序（半序）。偏序集和格就是研究順序的性質(zhì)及作用而產(chǎn)生的概念和理論。

格論在代數(shù)學(xué)、射影幾何學(xué)、集合論、數(shù)理邏輯、泛函分析以及概率論等許多數(shù)學(xué)分支中都有應(yīng)用。例如，在代數(shù)學(xué)中，對于一個群G與其子群格（G）之間關(guān) 系的研究。在數(shù)理邏輯中，關(guān)于不可解度的研究。

格的定義：設(shè)（L，≤）是偏序集，若L中任意兩個元素都存在上確界以及下確界，則稱（L，≤）是格（lattice），為了方便，這樣的格成為偏序格。

格h格 設(shè)(L，￡)是一個偏序集，如果對于"a,b?L，L的子集{a,b}在L中都有一個最大下界(記為inf{a,b})和一個最小上界(記為sup{a,b}),則稱(L，￡)是一個偏序格.

子集在L中有上確界和下確界的偏序集，就是格。

h代數(shù)格 在L定義二元運(yùn)算***和·**，滿足：對"a,b,c?L,有

(1) 交換律 a*b=b*a，a**·b=b·**a

(2)結(jié)合律(a*b)*c=a*(b*c) , (a**·b)·c=a·(b·**c)

(3) 吸收律 a*(a**·b)=a， a·**(a*b)=a

則稱(L，*，·)是代數(shù)格。

用代數(shù)的語言，格就是在非空集合上定義了兩個滿足結(jié)合律、交換律和吸收律的運(yùn)算。2

h對偶式 由1，0，和可以代表格中的任意元素的變量通過+，×運(yùn)算連結(jié)起來的式子，就是格中的表達(dá)式，記作f。將f中的0換成1，1換成0，+換成×，×換成+所得的表達(dá)式，就是表達(dá)式f的對偶式記作f。h

h對偶原理：若f為真，則f為真。3

備格備格亦稱完備格。又稱完全格。一類重要的格。它是伯克霍夫(Birkhoff，G.D.)于1933年引入的非代數(shù)概念。若格L的任意子集均有上確界及下確界，則L稱為備格。非空備格是有界的；備格的定義是自對偶的。任意集合A的集格P(A)、格L的合同格C(L)、群G的子群格、環(huán)的理想格、有限格等都是備格；但實(shí)數(shù)集R按通常數(shù)的大小關(guān)系構(gòu)成的格不是備格；若在R中填上±∞，則集R構(gòu)成備格。

合同格合同格是一類重要的格。指格的所有合同關(guān)系所構(gòu)成的格。設(shè)C(L)表示格L上的所有合同關(guān)系的集合，若θ，φ∈C(L)，定義θ≤φ當(dāng)且僅當(dāng)x≡y(θ)有x≡y(φ)，則C(L)關(guān)于上面定義的≤構(gòu)成一個格，稱為合同格。船山(Funayama，N.)和中山正(Nakayama，T.)于1942年證明了任意格的合同格是完全布勞威爾格，也是分配的代數(shù)格。合同格的性質(zhì)不僅在格論中，而且在格序代數(shù)、閉包代數(shù)、非結(jié)合格、多值邏輯等分支中都有廣泛的應(yīng)用。

代數(shù)格概念代數(shù)格(algebraic lattice)亦稱緊致生成格。是一種應(yīng)用廣泛的格。設(shè)L是備格，a∈L，若對XL，a≤∨X，存在X的有限子集X1，使得a≤∨X1，則稱a為L的緊致元。若備格L的任一元均為緊致元的并，則稱L為代數(shù)格。任意格的合同格是代數(shù)格。格L是代數(shù)格當(dāng)且僅當(dāng)L與某個含0的并半格的理想格同構(gòu)，這是代數(shù)格的一個很有用的性質(zhì)。代數(shù)格是伯克霍夫(Birkhoff，G.D.)于1967年引入的，但他并未假設(shè)完備性。代數(shù)格對合同格的刻畫、格的表示理論和無限維代數(shù)理論的研究均有重要作用。4

伯克霍夫簡介伯克霍夫是美國數(shù)學(xué)家。生于普林斯頓，早年在哈佛大學(xué)和英國劍橋大學(xué)就讀，1932年獲哈佛大學(xué)學(xué)士學(xué)位，后獲理學(xué)博士學(xué)位。1936年起，任教于哈佛大學(xué)，1938—1941年，為助理教授，1941—1946年，為副教授，1946—1982年，任數(shù)學(xué)教授，1982年退休。美國全國科學(xué)院、美國藝術(shù)與科學(xué)學(xué)院院士。1958年，任美國數(shù)學(xué)會副主席;1971—1972年，任美國數(shù)學(xué)協(xié)會副主席;1967—1968年，任美國工業(yè)與應(yīng)用數(shù)學(xué)會主席。.

伯克霍夫的工作涉及格論、近世代數(shù)、核反應(yīng)堆理論的流體動力學(xué)、聲學(xué)、偏微分方程的數(shù)值解，以及科學(xué)計(jì)算。他曾和菲力普斯(Phillips，R.S.)定義了取值于局部凸拓?fù)渚€性空間的函數(shù)的積分。他在1940年出版的《格論》，經(jīng)重新組織并增擴(kuò)內(nèi)容于1967年出版了第三版，除全面闡述了有關(guān)理論外，還介紹了格論在分析、集合論(包括拓?fù)浜蜏y度論)等方面的應(yīng)用，還涉及了有序系統(tǒng)及二進(jìn)制運(yùn)算等。他在把代數(shù)方法以及其他一些高水準(zhǔn)的數(shù)學(xué)方法應(yīng)用到別的科學(xué)領(lǐng)域方面有重要貢獻(xiàn)，并因此曾于1978年獲美國數(shù)學(xué)會G.D.伯克霍夫應(yīng)用數(shù)學(xué)獎。他一生發(fā)表學(xué)術(shù)論文近200篇，著有《流體動力學(xué)》(1950)、《橢圓方程的數(shù)值解》(1971)、《近世代數(shù)概論》(1941，與麥克萊恩(MacLane，S.)合著)和《代數(shù)》(1967)等專著。

代數(shù)格實(shí)現(xiàn)點(diǎn)數(shù)據(jù)索引近幾年來，基于內(nèi)容的多媒體信息檢索成為熱點(diǎn)研究課題，國外推出了多種基于內(nèi)容的圖像信息檢索系統(tǒng)。例如，IBM研制的QBIC系統(tǒng)采用顏色直方圖、紋理和形狀等特征檢索圖像，并用R*樹實(shí)現(xiàn)多維特征數(shù)據(jù)的索引； MIT媒體實(shí)驗(yàn)室研制的Photobook系統(tǒng)實(shí)現(xiàn)了形狀、紋理和人臉特征的抽取和檢索；Columbia大學(xué)研制的isualSEEk系統(tǒng)是視覺特征搜索引擎，而WebSEEk系統(tǒng)則是面向Web的文本/圖像搜索引擎。.從上述幾種圖像檢索系統(tǒng)來看，它們幾乎都是先從圖像中提取圖像特征，然后基于特征計(jì)算圖像之間的相似度,最終實(shí)現(xiàn)基于內(nèi)容和支持相似性查詢的圖像檢索系統(tǒng)。為了實(shí)現(xiàn)快速檢索，最常用的方法是對特征數(shù)據(jù)庫建立索引。多年來，人們陸續(xù)提出了多種索引技術(shù)，例如K-d樹、MB樹、R樹、R*樹、X樹、FastMap和VP樹等。這些索引技術(shù)可用于精確匹配查詢，也可以實(shí)現(xiàn)相似查詢。目前研究和使用較多的是R樹及其變種，它最早由Guttman提出，適合于對點(diǎn)數(shù)據(jù)和區(qū)域數(shù)據(jù)進(jìn)行索引。

提出一種新的用于點(diǎn)數(shù)據(jù)的組織、索引和快速檢索方法,它的主要特點(diǎn)是既利用了代數(shù)格的良好性質(zhì)，又利用了Hash高效查找能力。當(dāng)數(shù)據(jù)庫大小給定時，理論上講，本方法的檢索性能主要取決于點(diǎn)數(shù)據(jù)的維數(shù)、密度、所選用的代數(shù)格和Hash表的性能，但是在實(shí)際應(yīng)用中檢索性能可能還要取決于其它客觀因素，例如磁盤訪問速度等。能實(shí)現(xiàn)八維點(diǎn)數(shù)據(jù)的索引，得到了有參考價值的實(shí)驗(yàn)數(shù)據(jù)，我們開發(fā)基于其它代數(shù)格的、不同維數(shù)的索引結(jié)構(gòu)。5