[其他]檢索關(guān)聯(lián)矩陣的方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 85105498
• 申請(qǐng)日: 1985-07-18
• 公開(kāi)（公告）號(hào): CN85105498A
• 公開(kāi)（公告）日: 1987-01-28
• 發(fā)明（設(shè)計(jì)）人: 魯文·愛(ài)德華·布魯克斯;羅薩林·卡姆·林·拉姆;約翰·米切爾·科頓
• 申請(qǐng)（專(zhuān)利權(quán)）人: 國(guó)際標(biāo)準(zhǔn)電氣公司
• 主分類(lèi)號(hào): G06F15/40
• 分類(lèi)號(hào): G06F15/40
• 代理公司: 中國(guó)國(guó)際貿(mào)易促進(jìn)委員會(huì)專(zhuān)利代理部
• 代理人: 姚珊

本發(fā)明基本上是涉及數(shù)據(jù)庫(kù)檢索的，更具體地說(shuō)，是涉及一種用于檢索關(guān)聯(lián)矩陣的方法。

大多數(shù)計(jì)算機(jī)的應(yīng)用都包括從一個(gè)數(shù)據(jù)集中檢索出具有特定特征的項(xiàng)目，例如，與一個(gè)特定的關(guān)鍵域相一致或具有一種特有的數(shù)據(jù)值模式。這類(lèi)操作的例子包括：檢索信用卡號(hào)碼的數(shù)據(jù)庫(kù)以獲得某一特定卡片的情況，檢索數(shù)字編碼圖象以找到與一種模式匹配的圖象元素，檢索一種電子器件中元件和連線(xiàn)的數(shù)據(jù)庫(kù)以確定在兩個(gè)元件之間是否有電路存在，以及檢索字處理文件以找到特定的文本字符串。因?yàn)闄z索是大多數(shù)計(jì)算機(jī)應(yīng)用中的一部分，所以它的速度對(duì)完成操作的快慢起著重要的作用。關(guān)聯(lián)矩陣是由結(jié)點(diǎn)和把結(jié)點(diǎn)連接在一起的鏈組成的數(shù)據(jù)結(jié)構(gòu)。鏈?zhǔn)菃畏较虻模珒蓚€(gè)結(jié)點(diǎn)之間可以有兩個(gè)方向相反的鏈。假設(shè)所有的鏈都具有同樣的價(jià)或權(quán)。關(guān)聯(lián)矩陣通常可以用于存貯事例之間或組元之間的相互關(guān)系，矩陣的軸代表預(yù)先確定的相互關(guān)系。這種關(guān)聯(lián)矩陣應(yīng)用的一個(gè)具體例子是數(shù)字電子器件中元件之間的連線(xiàn)。對(duì)于系統(tǒng)中各種類(lèi)型的信號(hào)使用不同的關(guān)聯(lián)矩陣。

關(guān)聯(lián)矩陣還能用來(lái)表示組元的層次，其中，一個(gè)組元由另外幾個(gè)組元組成，目標(biāo)計(jì)算機(jī)程序的目標(biāo)固有網(wǎng)絡(luò)和二維表示法簡(jiǎn)化了三維目標(biāo)，在三維目標(biāo)中，同一平面中目標(biāo)的所有部分都被認(rèn)為是連接在一起的。

對(duì)這些關(guān)聯(lián)矩陣經(jīng)常執(zhí)行的主要檢索操作是：

找出與給定組元相連的所有組元;

兩個(gè)組元之間是否存在通路;

從一個(gè)給定的組元經(jīng)過(guò)指定數(shù)目的鏈可達(dá)到哪些組元;

找出組成另一個(gè)組元的所有組元;

找出另一個(gè)組元是其一部分的所有組元。

在一般的結(jié)構(gòu)中，采用下列兩種方法中的一種來(lái)解決這個(gè)問(wèn)題。第一，連接給定結(jié)點(diǎn)的所有的鏈可以作為以該結(jié)點(diǎn)開(kāi)頭的鏈表而存貯起來(lái)。這樣便于找出與給定結(jié)點(diǎn)連接的所有結(jié)點(diǎn)，但如果互連的數(shù)目相對(duì)很大，則在存貯空間方面就要付出很高的代價(jià)。例如，如果1000個(gè)結(jié)點(diǎn)中的每一個(gè)都與另外100個(gè)結(jié)點(diǎn)相連，并且對(duì)于每一個(gè)連接都使用一個(gè)32位的指針，則互連需要3.2兆位的存貯量。另外，找出從一個(gè)給定的組元經(jīng)過(guò)指定數(shù)目的鏈可達(dá)到的所有組元這一操作是很慢的，需要經(jīng)常進(jìn)行堆棧操作。

第二，組元或結(jié)點(diǎn)之間的互連可以存貯在矩形矩陣的位中，其中矩陣的軸代表組元或結(jié)點(diǎn)，行/列交點(diǎn)的一位置“1”表示相應(yīng)的兩個(gè)結(jié)點(diǎn)或組元是相連的。這種方法對(duì)于存貯空間來(lái)說(shuō)是節(jié)約的，但是一般的處理機(jī)上往往速度很慢，因?yàn)閺囊粋€(gè)字中抽出或校驗(yàn)單獨(dú)的位常常需要幾條指令，而檢索矩陣需要許多這樣的操作。

本發(fā)明設(shè)想了一種使用相聯(lián)檢索技術(shù)檢索關(guān)聯(lián)矩陣的方法，以提高檢索速度。該方法適用于相聯(lián)陣列處理機(jī)，以下簡(jiǎn)稱(chēng)AAP，這種處理機(jī)允許矩陣中結(jié)點(diǎn)的并行檢索，因此提高了檢索速度。

該方法打算使用兩種類(lèi)型的數(shù)據(jù)結(jié)構(gòu)。第一種是用于定位矩陣中一個(gè)特定事例或組元的數(shù)據(jù)結(jié)構(gòu)，第二種是代表事例或組元間相互關(guān)系的關(guān)聯(lián)矩陣。連同AAP一起使用這些數(shù)據(jù)結(jié)構(gòu)，就能夠沿“鏈”結(jié)構(gòu)上下移動(dòng)，以定位矩陣中的任意節(jié)點(diǎn)。通過(guò)控制檢索機(jī)構(gòu)的掩碼的操作，可以在A(yíng)AP上快速而容易地完成從矩陣中抽取關(guān)系。

本發(fā)明的一個(gè)目的是提供一種提高檢索關(guān)聯(lián)矩陣速度的方法。

本發(fā)明的另一個(gè)目的是提供用于關(guān)聯(lián)矩陣的一種檢索方法，其中，利用一種相聯(lián)檢索機(jī)構(gòu)并行檢索矩陣的結(jié)點(diǎn)。

圖1用圖解法表示相聯(lián)陣列處理機(jī)。

圖2是相聯(lián)陣列處理機(jī)的框圖。

圖3表示陣列中的單元互連。

圖4表示一種索引文件的格式。

圖5表示在檢索中的一點(diǎn)上相聯(lián)陣列處理機(jī)的狀態(tài)。

圖6表示在檢索中的一點(diǎn)上相聯(lián)陣列處理機(jī)的狀態(tài)。

圖7表示一個(gè)簡(jiǎn)化的關(guān)聯(lián)矩陣。

圖8表示用于具有10頁(yè)目錄的16×16位陣列的目錄和關(guān)聯(lián)矩陣。

圖9、10、11a、11b、12、13、14a和14b表示進(jìn)行檢索的不同時(shí)刻相聯(lián)陣列處理機(jī)的不同狀態(tài)。