代數(shù)格（應用于計算機科學等方面的格）

基礎知識

所謂格即指在集合L中定義兩個代數(shù)運算∨和∧，這兩個代數(shù)運算滿足：

(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(結合律);

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

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

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

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

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

格的定義

格（lattice）

格

偏序格

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

h代數(shù)格 在L定義二元運算

*

·

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

·

·

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

·

·

·

·

(3) 吸收律 a*(a

·

·

則稱(L，*，

·

代數(shù)格

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

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

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

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

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

代數(shù)格概念

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

伯克霍夫簡介

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

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

代數(shù)格實現(xiàn)點數(shù)據(jù)索引

近幾年來，基于內容的多媒體信息檢索成為熱點研究課題，國外推出了多種基于內容的圖像信息檢索系統(tǒng)。例如，IBM研制的QBIC系統(tǒng)采用顏色直方圖、紋理和形狀等特征檢索圖像，并用R*樹實現(xiàn)多維特征數(shù)據(jù)的索引； MIT媒體實驗室研制的Photobook系統(tǒng)實現(xiàn)了形狀、紋理和人臉特征的抽取和檢索；Columbia大學研制的isualSEEk系統(tǒng)是視覺特征搜索引擎，而WebSEEk系統(tǒng)則是面向Web的文本/圖像搜索引擎。

從上述幾種圖像檢索系統(tǒng)來看，它們幾乎都是先從圖像中提取圖像特征，然后基于特征計算圖像之間的相似度，最終實現(xiàn)基于內容和支持相似性查詢的圖像檢索系統(tǒng)。為了實現(xiàn)快速檢索，最常用的方法是對特征數(shù)據(jù)庫建立索引。多年來，人們陸續(xù)提出了多種索引技術，例如K-d樹、MB樹、R樹、R*樹、X樹、FastMap和VP樹等。這些索引技術可用于精確匹配查詢，也可以實現(xiàn)相似查詢。目前研究和使用較多的是R樹及其變種，它最早由Guttman提出，適合于對點數(shù)據(jù)和區(qū)域數(shù)據(jù)進行索引。

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