基本介紹
- 中文名：代數格
- 外文名：algebraic lattice
- 領域：數學
- 別稱：緊緻生成格
- 提出者：伯克霍夫
- 實例：任意格的契約格
- 提出時間：1967年
基礎知識,格論,格,備格,契約格,代數格概念,伯克霍夫簡介,代數格實現點數據索引,
基礎知識
格論
格論論述次序及包含的性質，是布爾代數的推廣，現已成為代數的重要組成部分，並在泛函分析、賦值論、幾何、邏輯、計算機科學、圖論等方面有廣泛的套用。所謂格即指在集合L中定義兩個代數運算∨和∧，這兩個代數運算滿足：
(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(吸收循己捆設律)，
格
“格”一種特殊的偏序集。在許多數學對象中，所考慮的元素之間具有某種順序。
例如，一組實數間的大小順序；一個集合的諸端全永子集（或某些子集）間按（被包含）所成的順序 ；一組命題間按蘊涵所成的順序；等等。這種順序一般不是全序，即不是任意二元素間都能排列順序，而是在部分元素間的一種順序即偏序（半序）。偏序集和格就是研究順序的性質及作用而產生的概念和理論。
格論在代數學、射影幾何學、集合論、數理邏輯、泛函分析以及機率論等許多數學分支中都有套用。例如，在代數學中，對於一個群G與其子群格（G）之間關 系的研究。在數理邏輯中，關於不可解度的研究。
格的定義：設（L，≤）是偏序集，若L中任意兩個元素都存在上確界以及下確界，則稱（L，≤）是格（lattice），為了方便，這樣的格成為偏序格。
格h格 設(L，£)是一個偏序集，如果對於"a,bÎL，L的子集{a,b}在L中都有一個最大下界(記為inf{a,b})和一個最小上界(記為sup{a,b}),則稱(L，£)是一個偏序格.
子集在L中有上確界和下確界的偏序集，就是格。
h代數格 在L定義二元運算*和·，滿足：對"a,b,cÎL,有
(1) 交換律 a*b=b*a，a·b=b·a
(2)結合律(a*b)*c=a*(b*c) , (a·b)·c=a·(b·c)
(3) 吸收律 a*(a·b)=a， a·(a*b)=a
則稱(L，*，·)是代數格。
用代數的語言，格就是在非空集合上定義了兩個滿足結合律、交換律和吸收律的運算。
h對偶式 由1，0，和可以代表格中的任意元素的變數通過+，×運算連結起來的式子，就是格中的表達式，記作f。將f中的0換成1，1換成0，+換成×，×換成+所得的表達式，就是表達式f的對偶式記作f。h
h對偶原理：若f為真，則f為真。
備格
備格亦稱完備格。又稱完全格。一類重要的格。它是伯克霍夫(Birkhoff，G.D.)於1933年引入的非代數概念。若格L的任意子集均有上確界及下確界，則L稱為備格。非空備格是有界的；備格的定義是屑戰欠自對偶雅提槳嘗的。任意集合A的集格P(A)、格L的契約格C(L)、群G的子群格、環的理想格、有限格等都是備格；但實數集R按通常數的大小關係構成的格不是備格；若在R中填上±∞，則集R構成備格。
契約格
契約格是一類重要的格。講試指格的所有契約關係所構成的格。設C(L)表示格L上的所有契約關係的集合，若θ，φ∈C(L)，定義θ≤φ若且唯若x≡y(θ)有x≡y(φ)，則C(L)關於上面定義的≤構成一個格，稱為契約格。船山(Funayama，N.)和中山正(Nakayama，T.)於1942年證明了任意格的契約格是完全布勞威爾格，也是分配的代數格。契約格的性質不僅在格論中，而且在格序代數、閉包代數、非結合格、多值邏輯等分支中都有廣泛的套用。
代數格概念
代數格(algebraic lattice)亦稱緊緻生成格。是一種套用廣泛的格。設L是備格，a∈L，若對XL，a≤∨X，存在X的有限子集X1，使得a≤∨X1，則稱a為L的緊緻元。若備格L的任一元均為緊緻元的並，則稱L為代數格。任意格的契約格是代數格。格L是代數格若且唯若L與某個含0的並半格的理想格同構，這是代數格的一個很有用的性質。代數格是伯克霍夫(Birkhoff，G.D.)於1967年引入的，但他並未假設完備性。代數格對契約格的刻畫、格的表示理論乘備提和無限維代數理論的研究均有重要作用。
伯克霍夫簡介
伯克霍夫是美國數學家。生於普林斯頓，早年在哈佛大學和英國劍橋大學就讀，1932年獲哈佛大學學士學位，後獲理學博士學位。1936年起，任教於哈佛大學，1938—1941年，為助理教授，1941—1946年，為副教授，1946—1982年，任數學教授，1982年退休。美國全國科學院、美國藝術與科學學院院士。1958年，任美國數學會副主席;1971—1972年，任美國數學協會副主席;1967—1968年，任美國工業與套用數學會主席。.
伯克霍夫的工作涉及格論、近世代數、核反應堆理論的流體動力學、聲學、偏微分方程的數值解，以及科學計算。他曾和菲力普斯(Phillips，R.S.)定義了取值於局部凸拓撲線性空間的函式的積分。他在1940年出版的《格論》，經重新組織並增擴內容於1967年出版了第三版，除全面闡述了有關理論外，還介紹了格論在分析、集合論(包括拓撲和測度論)等方面的套用，還涉及了有序系統及二進制運算等。他在把代數方法以及其他一些高水準的數學方法套用到別的科學領域方面有重要貢獻，並因此曾於1978年獲美國數學會G.D.伯克霍夫套用數學獎。他一生髮表學術論文近200篇，著有《流體動力學》(1950)、《橢圓方程的數值解》(1971)、《近世代數概論》(1941，與麥克萊恩(MacLane，S.)合著)和《代數》(1967)等專著。
代數格實現點數據索引
近幾年來，基於內容的多媒體信息檢索成為熱點研究課題，國外推出了多種基於內容的圖像信息檢索系統。例如，IBM研製的QBIC系統採用顏色直方圖、紋理和形狀等特徵檢索圖像，並用R*樹實現多維特徵數據的索引； MIT媒體實驗室研製的Photobook系統實現了形狀、紋理和人臉特徵的抽取和檢索；Columbia大學研製的isualSEEk系統是視覺特徵搜尋引擎，而WebSEEk系統則是面向Web的文本/圖像搜尋引擎。.從上述幾種圖像檢索系統來看，它們幾乎都是先從圖像中提取圖像特徵，然後基於特徵計算圖像之間的相似度,最終實現基於內容和支持相似性查詢的圖像檢索系統。為了實現快速檢索，最常用的方法是對特徵資料庫建立索引。多年來，人們陸續提出了多種索引技術，例如K-d樹、MB樹、R樹、R*樹、X樹、FastMap和VP樹等。這些索引技術可用於精確匹配查詢，也可以實現相似查詢。目前研究和使用較多的是R樹及其變種，它最早由Guttman提出，適合於對點數據和區域數據進行索引。
提出一種新的用於點數據的組織、索引和快速檢索方法,它的主要特點是既利用了代數格的良好性質，又利用了Hash高效查找能力。當資料庫大小給定時，理論上講，本方法的檢索性能主要取決於點數據的維數、密度、所選用的代數格和Hash表的性能，但是在實際套用中檢索性能可能還要取決於其它客觀因素，例如磁碟訪問速度等。能實現八維點數據的索引，得到了有參考價值的實驗數據，我們開發基於其它代數格的、不同維數的索引結構。
h對偶式 由1，0，和可以代表格中的任意元素的變數通過+，×運算連結起來的式子，就是格中的表達式，記作f。將f中的0換成1，1換成0，+換成×，×換成+所得的表達式，就是表達式f的對偶式記作f。h
h對偶原理：若f為真，則f為真。
備格
備格亦稱完備格。又稱完全格。一類重要的格。它是伯克霍夫(Birkhoff，G.D.)於1933年引入的非代數概念。若格L的任意子集均有上確界及下確界，則L稱為備格。非空備格是有界的；備格的定義是自對偶的。任意集合A的集格P(A)、格L的契約格C(L)、群G的子群格、環的理想格、有限格等都是備格；但實數集R按通常數的大小關係構成的格不是備格；若在R中填上±∞，則集R構成備格。
契約格
契約格是一類重要的格。指格的所有契約關係所構成的格。設C(L)表示格L上的所有契約關係的集合，若θ，φ∈C(L)，定義θ≤φ若且唯若x≡y(θ)有x≡y(φ)，則C(L)關於上面定義的≤構成一個格，稱為契約格。船山(Funayama，N.)和中山正(Nakayama，T.)於1942年證明了任意格的契約格是完全布勞威爾格，也是分配的代數格。契約格的性質不僅在格論中，而且在格序代數、閉包代數、非結合格、多值邏輯等分支中都有廣泛的套用。
代數格概念
代數格(algebraic lattice)亦稱緊緻生成格。是一種套用廣泛的格。設L是備格，a∈L，若對XL，a≤∨X，存在X的有限子集X1，使得a≤∨X1，則稱a為L的緊緻元。若備格L的任一元均為緊緻元的並，則稱L為代數格。任意格的契約格是代數格。格L是代數格若且唯若L與某個含0的並半格的理想格同構，這是代數格的一個很有用的性質。代數格是伯克霍夫(Birkhoff，G.D.)於1967年引入的，但他並未假設完備性。代數格對契約格的刻畫、格的表示理論和無限維代數理論的研究均有重要作用。
伯克霍夫簡介
伯克霍夫是美國數學家。生於普林斯頓，早年在哈佛大學和英國劍橋大學就讀，1932年獲哈佛大學學士學位，後獲理學博士學位。1936年起，任教於哈佛大學，1938—1941年，為助理教授，1941—1946年，為副教授，1946—1982年，任數學教授，1982年退休。美國全國科學院、美國藝術與科學學院院士。1958年，任美國數學會副主席;1971—1972年，任美國數學協會副主席;1967—1968年，任美國工業與套用數學會主席。.
伯克霍夫的工作涉及格論、近世代數、核反應堆理論的流體動力學、聲學、偏微分方程的數值解，以及科學計算。他曾和菲力普斯(Phillips，R.S.)定義了取值於局部凸拓撲線性空間的函式的積分。他在1940年出版的《格論》，經重新組織並增擴內容於1967年出版了第三版，除全面闡述了有關理論外，還介紹了格論在分析、集合論(包括拓撲和測度論)等方面的套用，還涉及了有序系統及二進制運算等。他在把代數方法以及其他一些高水準的數學方法套用到別的科學領域方面有重要貢獻，並因此曾於1978年獲美國數學會G.D.伯克霍夫套用數學獎。他一生髮表學術論文近200篇，著有《流體動力學》(1950)、《橢圓方程的數值解》(1971)、《近世代數概論》(1941，與麥克萊恩(MacLane，S.)合著)和《代數》(1967)等專著。
代數格實現點數據索引
近幾年來，基於內容的多媒體信息檢索成為熱點研究課題，國外推出了多種基於內容的圖像信息檢索系統。例如，IBM研製的QBIC系統採用顏色直方圖、紋理和形狀等特徵檢索圖像，並用R*樹實現多維特徵數據的索引； MIT媒體實驗室研製的Photobook系統實現了形狀、紋理和人臉特徵的抽取和檢索；Columbia大學研製的isualSEEk系統是視覺特徵搜尋引擎，而WebSEEk系統則是面向Web的文本/圖像搜尋引擎。.從上述幾種圖像檢索系統來看，它們幾乎都是先從圖像中提取圖像特徵，然後基於特徵計算圖像之間的相似度,最終實現基於內容和支持相似性查詢的圖像檢索系統。為了實現快速檢索，最常用的方法是對特徵資料庫建立索引。多年來，人們陸續提出了多種索引技術，例如K-d樹、MB樹、R樹、R*樹、X樹、FastMap和VP樹等。這些索引技術可用於精確匹配查詢，也可以實現相似查詢。目前研究和使用較多的是R樹及其變種，它最早由Guttman提出，適合於對點數據和區域數據進行索引。
提出一種新的用於點數據的組織、索引和快速檢索方法,它的主要特點是既利用了代數格的良好性質，又利用了Hash高效查找能力。當資料庫大小給定時，理論上講，本方法的檢索性能主要取決於點數據的維數、密度、所選用的代數格和Hash表的性能，但是在實際套用中檢索性能可能還要取決於其它客觀因素，例如磁碟訪問速度等。能實現八維點數據的索引，得到了有參考價值的實驗數據，我們開發基於其它代數格的、不同維數的索引結構。
