用於檢查和操作數據的存儲器引擎的製作方法

2023-09-21 17:59:10 1

專利名稱：用於檢查和操作數據的存儲器引擎的製作方法
技術領域：
本發明一般涉及用於檢查和操作數據的存儲器引擎，更具體地說，本發明涉及不僅用於快速檢索符號(字符或其類似物)串形式的數據的快速檢索，還根據須要用於在字符串內選擇地插入和刪除數據。
背景技術：
檢索由符號構成的緩衝器或其它存儲裝置，以便找到和給定的或預定的字符串匹配的字符串，是在許多應用中的一個基本的操作，例如但不限於資料庫、遺傳信息的處理、數據壓縮以及計算機語言的處理。通過在字符串中插入新的序列或從字符串中刪除序列來修改字符串，也是這些範圍的基本操作，並且由這些字符串操作佔據的時間直接地影響主程序的執行時間。
當進行串行計算時，即進行匹配操作時，為了在包含M個符號的緩衝器中找到存在的所有N個符號的字符串，所需的最大的步N*M。當須要在緩衝器內插入字符時，平均地說，在緩衝器中一半的符號必須向右或向左移動一個單元，以便為新的單元騰出位置。在這種情況下，平均須要N/2步。
提出了一系列用於改善這些操作的算法，它們基於若干技術，其中包括散列法，或者樹數據結構。當有關的字符串是固定長度的字時，使用散列法。在這種情況下，每個字和一個當所述字被存儲在字庫中時被用作索引的唯一的數相關。這種方法的缺點是，其只有當所述信息是靜止信息時才好用，並且在處理期間不改變位置。此外，產生所述的數是一種花費較高的操作，有時若干個字可以和同一個數相關，因而須要附加的操作查找要找的字。也可以利用後綴樹，後綴樹是一種樹結構，其中存儲在緩衝器中的所有的子字符串。當想要確定是否一個給定的字符串位於緩衝器中時，只需要下樹，每次下降查找的字符串的一個字符，直到所述字符串被找到或者找不到。在每種情況下，如果字符串含有M個符號，則最多須要M步來確定是否該字符串位於長度為L的緩衝器中。雖然這種檢索方法速度快，但是要建立一個後綴樹須要花費許多計算。
內容可尋址的存儲器，或者CAM，是一種利用一次存儲器訪問查找給定符號或字的位置的並行方案。這種方法對於固定長度的字好用，但是不容易擴展到可變長度的符號串。當在緩衝器中並行地進行檢索時，即當同時進行M個比較時，則步數被減少到N。已經提出了具有並行比較器和用於存儲和每個給定符號的比較結果的標記器的緩衝器，用於加速字符串的檢索。例如見Almy等人的美國專利4575818；Mayer的美國專利5319762；Eskandare-Gharnin等人的美國專利5602764；或者Satoh等人的美國專利5448733。這些已知的裝置一般使比較器與用於存儲最後進行的比較結果的一位標記器一起和緩衝器的每個單元關聯。所述比較器、存儲單元和標記器用這種方式操作，使得在緩衝器中的要被定位的字符串中的符號向緩衝器的所有的比較器傳播。然後，這些比較器比較給定的符號和在其相關的存儲單元中存儲的符號。比較結果存儲在和所述比較器以及存儲單元相關的標誌器中。
作為移位寄存器實現的緩衝器能夠使其內容和時鐘信號同步地並行地向左或向右移動。在這種情況下，緩衝器的整個內容只需要一步便可移動。不過，這些緩衝器，不僅提供其要被移動的內容的部分，而且提供全部的移動操作。此外，每個緩衝器單元集成單獨的比較器，這趨於增加作為一個整體的裝置的尺寸和複雜性，因而導致成本和使用的能量的增加。
因此，鑑於上述問題，本發明試圖利用一種能夠非常快地進行字符串檢索、插入和刪除的存儲裝置，其中使用被稱為Connex Memory(下文稱為CM)的新型存儲電路。

發明內容
本發明的目的在於使得能夠對數據進行快速的字符串檢索、插入和刪除操作。
本發明的另一個目的在於使得能夠對包括數據字符的字符串進行快速的字符串檢索、插入和刪除操作。
本發明的另一個目的在於使得能夠對包括數據字符的字符串快速地進行字符串檢索、插入和刪除操作，其中任何給定的數據字符的檢查和操作在一個時鐘周期內完成。
本發明的另一個目的在於使得能夠檢查在一個數據字符串內的可變尺寸的數據欄位。
本發明的另一個目的在於使得能夠標記在一個數據字符串內的可變尺寸的數據欄位。
本發明的另一個目的在於利用靜態的或動態的存儲單元暫時存儲和操作數據字符串。
本發明的另一個目的在於沿正向或反向的任何方向檢查存儲在存儲單元中的數據字符串。
按照本發明的一個實施例，一個存儲器引擎組合相聯的存儲器和隨機存取存儲器，用於使得能夠對數據快速地進行字符串檢索、插入和刪除操作，並且包括用於暫時存儲作為數據字符串的數據的存儲裝置。一個控制器被用於選擇地對所述存儲裝置輸出多個指令中的一個，並接收從其反饋的數據，所述存儲裝置按照由所述控制器輸出的指令檢查串中的數據字符。還利用一個時鐘裝置向所述存儲裝置和所述控制器輸出由每秒內一個預定數量的時鐘周期構成的時鐘信號，所述存儲裝置在一個時鐘周期內檢查並選擇地操作一個數據字符。
通過整體地考慮說明書、權利要求書和附圖，可以更加清楚地理解本發明的這些和其它的方面及其優選實施例。


圖1是表示按照本發明的一個實施例的存儲器引擎的一般結構的方塊圖，其中包括外部控制器和時鐘元件；圖2是表示和不同的總線相連的圖1的存儲器引擎的方塊圖，所述的總線使得能夠在存儲器引擎的構成元件之間交換信息。
圖3是表示圖1的存儲器引擎的基本操作的一個實施例的流程圖；圖4是表示圖1的存儲器引擎的基本操作的另一個實施例的流程圖；圖5是表示由圖1的存儲器引擎處理一個「c查找(find)」指令的流程圖；圖6是表示由圖1的存儲器引擎處理一個「讀(read)」指令的流程圖；圖7是表示由圖1的存儲器引擎處理一個「插入(insert)」指令的流程圖；圖8是表示由圖1的存儲器引擎處理一個「刪除(delete)」指令的流程圖；圖9是表示由圖1的存儲器引擎處理一個「下一個(next)」指令的流程圖；圖10是表示由圖1的存儲器引擎處理一個「跳躍」指令的流程圖；圖11是一個方塊圖，表示用於連接存儲器引擎的存儲裝置和其環境所需的以及用於把幾個存儲裝置連接在一起所需的輸入和輸出信號；圖12是表示存儲裝置的內部結構的一個實施例的一個方塊圖，其中使得兩維的靜態或動態存儲單元的陣列成為可以通過兩個代碼轉換器電路訪問的；圖13是用於連接動態存儲單元和其環境所需的輸入和輸出信號的方塊圖；圖14是表示按照本發明的一個實施例的存儲單元的內部體系結構的電路圖，所述存儲單元含有用於符號的存儲器及其相關的標誌器，通過所述存儲器，可以使符號及其相關的標記被存儲或讀出，或者和傳播的符號相比較。
圖15表示按照本發明的實施例的圖12所示的代碼轉換器電路的內部體系結構的電路圖，通過所示的電路，可以訪問兩維陣列的存儲單元，並且其使得能夠產生第一或最後被標記的單元的地址；圖16是表示作為隨機存取存儲器(RAM)和RAM控制器的組合的緩衝存儲器的內容的電路圖；圖17表示圖16所示的RAM控制器的內部結構的電路圖。
具體實施例方式
CM是一種對字串的物理支持，每個字從一個有限的存儲符號組中取值，每個字藉助於「設置」一個附加的位來增大，藉以用兩個狀態之一標記所述的字被標記的或未被標記的。術語「存儲符號」在這裡解釋為指一個連續比特的固定長度的集合，其長度和應用有關，並且不被事先地設置。
本發明的結構允許在一個時鐘周期內執行所有的CM指令，具有大約為在當前高速緩存技術中遇到的延遲的兩倍的延遲。這裡所述的結構是一種單片電路結構，其也可以被複製在更複雜的電路中。圖1表示按照本發明的一個實施例的存儲器引擎205的一般的體系結構，以及其和外部控制器255、同步時鐘電路256的操作關係。容易理解，外部控制器255和存儲器引擎的操作通過使用從時鐘電路256發出的公共時鐘信號協調。此外，本發明設想，外部控制器255可以具有任何數量的專用電路配置，而不脫離本發明的較寬的方面，只要外部控制器255能夠向存儲器引擎205發送指令並能夠接收來自存儲器引擎205的指令即可。
如圖2所示，CM206和作為一個緩衝器池組織的行存儲器隨機訪問裝置200相連，每個緩衝器具有和CM206相等的尺寸，並在存儲器引擎205的控制下，下文將存儲器引擎稱為Connex引擎(CE)。這些緩衝器也被稱為線緩衝器，其用途是使得能夠對比可以在CM206內容納的較長的字符串上進行檢索、插入和刪除操作，並且提供較低的實施成本和較低的功率消耗，如在後面詳細說明的。
圖3表示CE205的總的應用程式，從塊302開始，利用控制器255把事先選擇要進行檢查的字符串裝入相關的行存儲器206中。所述字符串由數據符號的集合構成，為了便於說明，所述數據符號被裝入行存儲器200中的一個或幾個緩衝器中，直到被完全地存儲在其中。用這種方式，在行存儲器200中的每個緩衝器含有字符串的不同的部分，每個部分具有和CM206的尺寸相等的尺寸，如前所述。
如圖3的塊304所示，CE205通過數據RAM總線100把要檢查的第一緩衝器的內容從行存儲器200裝入CM206中。然後，CM206按照從控制器255輸入的指令進行字符串的裝入的部分的所需的字符串操作或檢查，如塊306所示。然後，CM206在塊308確定是否應當在字符串的被檢查的部分中設置一個或幾個標記，以便在塊307選擇地設置這種標記，並在塊309復位所述的標記。容易理解，確定在被移動到CM206中的字符串的給定部分內是否應當設置一個或幾個數據標記和由控制器255輸入的特定指令有關，這在後面詳細說明。
在檢查CM206中的字符串的部分，並且如果須要，在其中設置一個或幾個標記之後，CE205把CM206的內容向回存儲到行存儲器200的第一緩衝器中，裝入第二緩衝器的內容，並進行相同的操作。CE205繼續把緩衝器的圖案裝入在CM206中，在CM206中進行字符串處理，並把CM206的內容向回存儲到緩衝器中，直到整個字符串被處理完畢。因為在被檢索的符號的字符串內存在的局部性的級別，被裝入CM206中的緩衝器的數量隨著檢索操作的數量的進展被快速減少，因而很快地把操作的數量限制於少量的緩衝器。
因此，本發明的一個重要方面在於，存儲在行存儲器200中的整個字符串不必響應由控制器255發出的指令被重複地檢查，因為設置的標記的存在(或者不存在)使得能夠使某些緩衝器免於後續的查看，如下所述。例如，如果由控制器255發出的指令命令對給定的一組數據元素進行檢索(如後詳述)，則CM206首先檢查行存儲器200中的每個緩衝器內的每個字符串，在其檢索第一個數據元素的合適的位置設置標記。此時在行存儲器200中的緩衝器的隨後的檢查將被限制於那些包括設置的標記的緩衝器，而排除沒有設置標記的那些。用這種方式，本發明的CM206不需要重複地檢索那些不可能包括要被檢索的數據元素的緩衝器，從而大大的且逐漸增多地消除大量數據的重複檢查，因而加快了響應時間。
本發明的另一個重要方面在於，CM206能夠在一個時鐘周期內並行地進行若干個操作。因此，就圖3而言，特別是塊306，307，308和309，CM206能夠在一個時鐘周期內並行地處理這些塊。因而容易理解，在圖3中包括的各個塊以及本發明的其它的方塊圖，都不得解釋為是按照其時間順序執行的，而是CM206能夠在一個時鐘周期內並行地處理許多塊，如上所述。
下面結合由控制器255發出的特定指令更加詳細地說明CM206的操作和CE205的操作。
CM206通過一般由控制器255發送的指令和數據進行操作。當指令要求一個數據操作符時，例如「查找(find)」指令，其確定給定符號、或在字符中的數據元素、或符號、當前在CM206中存儲的字符串所在的所有位置，所述指令和符號便被同時送入CM206中。CM206支持若干種的指令，所述指令主要被分成兩類正向指令和反向指令。每類又包括三種指令用於設置和復位和單元相關的標記的指令，用於訪問在設置有標記的單元中存儲的字的指令，以及用於修改在設置有標記的單元中存儲的字的指令。雖然本發明的設計支持和每個存儲字相關的一位標記，但是，不脫離本發明的較寬的方面，也可以使用幾個位來編碼每個字的狀態。
首先說明屬於正向指令類的指令。反向類的指令的行為方式是正向指令的鏡像，如後所述。在以下的說明中，符號這個術語表示由位構成的任何邏輯塊。對於某些應用程式，8位字節可能是最佳的實現。在其它的應用中，例如基因型字符串的生物學處理，符號可能是4位的實體。
正向指令對於字符串的檢索和插入操作，輸入字符串和指令一起每次一個符號(例如字符)地被輸入到CM206，當所述指令是檢索指令時，每個符號便同時和在CM206中當前存儲的所有符號比較。可以進行兩種比較，即有條件的比較和無條件的比較。字符串的第一個符號被無條件地檢索，而隨後的符號被有條件地檢索，其條件是，其前面一個符號在CM206中已被找到。
當所述操作是一個插入操作時，在CM206中在插入點右側的符號被向右移動一個位置，把新的符號在插入點插入。在本發明的一個實施例中，插入點是設置有標記的第一個符號的位置。
本發明的另一個重要目的在於，使檢索和插入操作兩者只在一個時鐘周期內進行，這是由於CE205系統的體系結構的高效率所致，如上所述。
關於字符串的刪除操作，連續的符號被從CM206中的刪除點讀出，並且在所述點的右側的所有符號被向左移動一個位置。這裡同樣，所述刪除點是具有設置的標記的第一個或最後一個存儲單元的位置。這個操作的讀出和移動部分被同時實現並且只用一個時鐘周期。
下面說明實現上述操作的指令。
查找和條件查找指令是訪問指令。如圖3和圖4的流程圖所示，查找指令可以通過控制器255和符號一起輸入到CM206中，CM206關聯地比較所述符號和在其M存儲單元包含的所有符號。這個指令的結果是，在其內容和給定符號匹配的單元之後的所有單元的標記被設置。所有的其它標記被復位。圖3的塊302-314概括地說明了這個操作。例如，假定本發明藉助於對符號加上括號表示該符號的標記被設置，並進一步假定字符串「RON AND ROBERT」當前被存儲在CM206中。對CM206發出「查找(R)」指令的結果使得其內容改變為「R[O]NAND R[O]BERT」。兩個符號O的標記被設置是因為它們跟隨著包含「R」的單元，R是要被查找的符號，如圖3的塊308所示。
用於進行「條件查找(condition find)」的條件查找指令的操作和查找指令的相似之處在於，符號也和指令一起輸入到CM206中，並且CM206進行這個符號的相關的檢索，不過在這種情況下，只有具有以前設置的標記的行存儲器200的單元或緩衝器在所述標比較中被涉及，如圖5塊322所示。其結果是，在發生匹配的單元後面的單元的標記被設置。所有其它的標記被復位。使用和上述相同的例子，並假定兩個「O」符號仍然設置有標記，則指令「條件查找(O)」將限於只對有標記的單元進行相關的比較。因為二者都含有「O」，故兩個比較是成功的，並且設置含有O的單元的右方的單元的標記「 RO[N]AND RO[B]ERT」。假定現在執行cfind(B)，則只有第二個被標記的單元得到成功的比較，因而E符號的標記被設置「RON ANDROB[E]RT」。這個處理繼續進行，直到所有的符號或數據元素都被檢索，從而向控制器255輸出成功的(或不成功的)匹配，如圖5的方塊324-326所示。
如上所述，容易理解，圖3說明本發明的基本功能，其一般可應用於所有的輸入指令。因此，例如結合塊302說明的「字符串」可以包含一個或幾個數據元素，和發出的指令的性質以及被操作或檢查的特定的數據無關。此外，雖然圖3假定裝入的字符串大於可以在CM206中容納的字符串，因而須要分片從行存儲器200移動到CM206進行檢查，但是並不總是這種情況。如圖4所示，另一種方法包括把其尺寸能夠被CM206容納的那些字符串直接裝入CM206中，如塊301所示。裝入CM206中的字符串的檢查將按照特定的指令在塊303中進行，同時塊305將合適地設置和復位標記。
容易理解，在CM206能夠容納要被檢查的數據情況下，通過選擇地旁路CE205和行存儲器200，可以相應地節省處理時間和消耗的能量。
另一個被提出的指令是讀-正向指令。讀-正向指令使得CM206返回在設置有標記的第一個即最左邊的一個單元中存儲的符號。在優選的方案中，按照公認的慣例，CM206的最左邊的符號地址是0，最右邊的地址是M-1，假定存儲容量是M個符號。
一進行讀操作，剛剛讀出的單元的標記便被復位，並且和剛剛讀出的單元相鄰的單元的標記被設置。再次假定CM含有「RO[N]ANDRO[B]ERT」，讀-正向指令的結果是，由CM輸出符號「N」，並且最左邊的標記改變為「RO N[] AND RO[B]ERT」。空格符號現在被標記。圖6表示作為塊330的這個處理，當發出讀-正向指令時，其操作可被包括在圖3的塊308中。
另一個被提出的指令是插入指令。插入指令和符號X一起提供給CM206。這個指令只影響CM206的第一個或者最左邊的被標記的單元。當符號X被插入時，在第一個被標記的單元的右邊的所有單元的內容和狀態，包括標記，都被向右移動一個位置，並把符號X存儲在第一個被標記的單元的先前的位置。剛剛收到新的符號的單元的標記被復位。作為例子，假如CM206含有「R[O]N AND R[O]B ERT」，則「插入(X)」使得CM206的內容變成「RX[O]N AND R[O]B ERT」。圖7作為塊332說明了這種處理。
另一個被提出的指令是刪除指令。刪除指令通過除去存儲在第一個被標記的單元中的符號並向左移動該單元的右邊的所有單元的內容而操作。假定CM含有「R O[N]AND R O[B]ERT」，則在刪除指令生效之後，CM含有「R[]N AND R[O]B ERT」。圖8作為塊334說明了這種處理。
另一個被提出的指令是next指令。Next指令沒有參數，其復位第一個或最左邊的一個被標記的單元的標記。用這種方式，當若干個標記被設置時，可以重複地使用這個指令，從而使得能夠訪問CM206的所有有標記的單元。例如，假定CM206含有「R[O]N AND R[O]BERT」，執行next指令將把CM206的內容改變成「R O N AND R[O]BERT」。圖9作為塊335說明這個處理。
暫且返回圖1，index的輸出13具有CM206中的第一個被標記的單元的線性地址。例如，如果CM206的第一個或最左邊的一個單元設置有標記，則index返回0。如果被標記的是第二個單元，則index返回1。假定CM206包含字符串「R O[N]AND R O[B]ERT」，並且字符串「RON」被存儲在CM206的最左邊的單元中，則index返回2，因為符號「N」被存儲在CM206的地址2中。
另一個被提出的指令是write-one指令。Write-one指令和符號S一起被提供給CM206，所述符號被寫入CM206的第一個或最左邊的被標記的單元。這個單元的標記被復位，並且線性地跟隨著所述單元的標記被置位。
另一個被提出的指令是write-all指令。該指令和符號S一起被提供給CM206，所述符號在一個時鐘周期內被同時寫入設置有標記的CM206的所有單元中。這些單元的標記被復位，並且在這些單元後面的單元的標記被置位。
另一個被提出的指令是write指令。該指令和地址A以及符號S一起被提供給CM206，所述符號被存儲在CM206的地址A的單元中。該指令類似於在隨機存取存儲器中的寫操作。和地址A的單元相關的標記被復位，並且線性地跟隨著的單元的標記被置位。
Read指令和地址A一起被提供給CM206，並使CM206輸出其處於地址A的單元的內容。這個指令類似於隨機存取存儲器的讀操作。由這個操作訪問的單元的標記不被改變。
另一個被提出的指令是jump指令，該指令被提供給CM206，用於處理在CM206中存儲有可變長度的字符串的情況，具有同樣的詞首和詞尾(即以相同序列開始兩個字符串，以相同序列結束兩個字符串)，而具有不同的中間部分，其可以具有不同的長度，此外，如果所有字符串的詞首的最後一個符號被標記，則CM206支持被稱為jump的操作，其取一個操作符，並且其行為最好通過例子進行說明。
假定CM206在其存儲器的不同部分中含有兩個字符串「AAA％BB％CCCC」和「AAA％DDD％CCCC」，其中％表示用作即將到來的特定應用的分隔符的唯一符號。此外，假定和在AAA詞首後面的％相關的標記已被設置，例如通過執行指令find(A)，cfind(A)，cfind(A)「AAA[％]BB％CCCC」和「AAA[％]DDD％CCCC」。Jump(s)指令的目的，其中s是一個符號，是要把標記從其當前位置移動到CCCC詞尾的開頭的未加標記的％符號，然後用s符號替換它們。
例如，在第一次執行指令jump($)之後，在上述例子CM206中的兩個字符串將改變為「AAA％[B]B％CCCC」和「AAA％[D]DD％CCCC」。在發出第二個指令jump($)之後，所述字符串成為「AAA％B[B]％CCCC」和「AAA％D[D]D％CCCC」。在第三個指令jump($)之後，所述字符串成為「AAA％BB$CCCC」和「AAA％DD[D]％CCC」。在第四個jump($)之後，為「AAA％BB$CCCC」和「AAA％DDD$CCCC」。因而響應jump指令，CM206執行以下操作所有設置有標記的單元都比較其符號和特定的分隔符號(在上面的例子中是％)。如果發現匹配，則用在指令中的符號s(上面的例子中的$)代替所述特定的分隔符號，並復位該單元的標記。否則，如果未找到匹配項，則復位該單元的標記，並設置相鄰的右方的單元的標記，結果，使標記向右移動一位。圖10作為塊336說明這種處理。
Jump指令在資料庫應用中是重要的，此時符號串含有欄位識別符或分隔符對以及數據值，其中識別符具有固定的長度，但是含有數據值的欄位沒有固定的長度。用這種方式，本發明有利地提供一種用於檢查字符串內的欄位的方法，每個欄位包含具有隨機的尺寸的數據值，同時標記字符串中的特定數據欄位而不管其內容。此外，因為在字符串中的被標記的單元的每次比較都在一個時鐘周期內完成，所以可以快速而高效地完成字符串的檢查。
本發明的另一個重要的方面在於，jump指令用一個預定的定位符號代替字符串中的分隔符。因此定位符號可用於標記特定數據欄位的結尾，而不管其長度，或者可用於標記跟隨被搜索的數據欄位的數據欄位。
如上所述，jump指令使得能夠並行地檢查在CM206中存儲的多個字符串，因此允許並行地識別在每個字符串中的分隔符，其中每個識別、選擇地替換，在一個時鐘周期內進行。
反向指令至此說明的檢索、插入和刪除指令總是應用於CM206的第一個標記的單元，並且，當其影響其它單元時，則影響在第一個被標記的單元的右側的單元。CM206還支持向後或反向查找、插入、刪除、下一個和標引操作，其中這些操作應用於CM206的最後被標記的單元。它們的行為是上述的正向查找、插入、刪除、下一個和標引操作的鏡像。
reverse-find指令是和符號s一起輸入到CM206中的指令，其設置含有符號s的單元的左方的單元的標記。所有其它標記被復位。如果CM206含有「JOHN AND JOHNNY」，則reverse-find(N)設置標記如下「JO[H]N[A]ND JO[H][N]NY」。
Reverse-cfind指令是一個反向條件查找指令，其和符號s一起輸入到CM206中，並且CM206隻相關地檢索被標記的單元。所有含有所述符號s的複製品的單元都使其左邊相鄰單元的標記被置位。所有其它的標記被復位。假定CM206含有「JO[H]N [A]NDJO[H][N]NY」，則Reverse-cfind(H)將標記改變如下「J[O]HN ANDJ[O]HNNY」。
Reverse-insert指令是一個和符號s一起輸入到CM206中的指令。最左邊的被標記的單元以及其線性右邊的所有單元的內容被右移一位，並把符號s存儲在最左邊的被標記的單元中。該單元的標記不變。例如在「JO[H]N AND JO[H]NNY」中反向插入X得到新的CM206的內容「JO[X]HN AND JO[H][N]NY」。
Reverse-delete是一個通過讀出或者除去最左邊單元中的符號並使所有左邊的單元的內容向右移動一位。最左邊被標記的單元的標記被復位，並設置其左邊的單元的標記。例如，如果在CM206中含有JO[H]N AND JO[H]NNY」，則Reverse-delete的結果是J[O]N ANDJO[H]NNY」。
Limited-Range指令如上所述，CM206還支持只影響其地址大於能夠由兩個附加的指令設置的某個數的單元的操作。其操作範圍被限制於具有大於所述限制的單元的指令被稱為被限制的指令。在這種情況下，檢索、插入和刪除操作的範圍不是CM206中的全部M個字，而是其中的一個較小的部分。在這種情況下，當進行find，cfind，insert，delete操作時，只影響CM206的鄰接的塊中的單元。單元的這個塊在左邊被一個特定的地址寄存器限制，該地址寄存器位於CM206的解碼部分的地址中，並延伸到最後，即CM206的最右邊的單元。
Set-limit是一個用於設置被限制的指令的較低限制地址為第一個或最左邊的被標記的單元的地址的指令。例如如果CM206含有字符串「RO[N]AND RO[B]ERT」，則set-limit指令設置限制地址為2，因為最左邊被標記的符號是N，在CM206中的地址2。
Set-limit-address是一個和地址A一起輸入到CM206的指令，並把這個地址存儲在保存限制地址的內存中。
Limited-find，limited-cfind，limited-reverse-find，以及limited-reverse-cfind是被限制的指令，其操作類似於find，cfind，reverse-find和reverse-cfind指令，但是只應用於其地址大於或等於限制地址的單元。
Limited-write-all指令和符號s一起輸入到CM206，其操作方式和write-all指令一致。其把符號s寫入其地址大於或等於限制地址的所有被標記的單元中。
CM206輸出若干個布爾信號，反映其被標記的單元的狀態。
1)如果在CM206中至少具有一個被標記的單元，則一個信號被CM206設置為1，否則便設置為0。
2)如果在整個CM206中只具有一個被標記的單元，則一個信號被CM206設置為1，否則便設置為0。
3)如果最後一個條件查找類型的指令(正向、反向或被限制的)未成功(未設置標記)，則一個信號被設置為1，並且CM206自動地反向到查找類型的操作，其可能設置一些標記。
4)如果一個或幾個具有預定的二進位圖案的字符被設置相關的標記，則一個信號被CM206設置為1。這些字符用於表示空的或無效的符號位置，並通過表示必須由外部控制器255尋址的特別條件的操作來設置其標記。
5)一個信號被CE設置為1，用於表示沒有緩衝器包含設置有標記的符號，或者表示RAM控制器已經加載CM中的所有緩衝器，並且沒有剩下緩衝器要被加載。
Connex引擎如上所述，圖2中示出了Connex引擎(CE)205。其是一個用於管理存儲在CM206中以及行存儲器200的緩衝器中的符號串的電路，行存儲器(line memory)200也叫做行(line)，其是由隨機存取存儲器實現的。每個行的容量等於CM206的容量，並含有(N+1)位的M個字。在外部實體例如計算機和處理器的控制下，CE205允許交換要被寫入到含有行或緩衝器的行存儲器200的內容或者從中讀出的內容。一個寫操作把行的內容存儲到CM206中。一個讀操作把把CM206的內容存儲到行中。兩種操作佔用一個周期。外部處理器可以使用insert或write指令在CM206中寫入信息，並通過data-in總線10輸入符號。符號可以通過兩個路徑從CE205讀出一個通過CM206，例如通過在command線14上發送read指令，並在data-out總線11上獲取符號。另一個路徑根據實現直接從LM200中讀出含有一個到幾個符號的字。在這種情況下，字的地址通過字地址總線203發送給CE205，並且從數據字總線204獲得所述的字。Data-ram總線100允許CM206的內容存儲在CM206的給定的行中或者從中被讀出。這個總線包含M*(N+1)根線，並允許整個的CM206在一個時鐘周期內被讀出或者寫入。
圖16表示構成LM的兩個元件的方塊圖。一個是隨機存取存儲器(RAM)130，其中行被存儲，另一個是RAM控制器120。RAM控制器的用途是快速地對CM206送入行，使得存儲在RAM中的行的集合內的符號串可被快速地處理。為此，RAM控制器通過RAM執行一個傳遞，此時其掃描其中存儲的行的集合，並向CM206發送一個選擇的子組進行處理。RAM控制器為RAM中的每個行保持兩個存儲的位。第一位表示和其相關的行是否應當在當前傳遞期間被發送給CM206。RAM控制器自動地以恆定的時間產生其第一位被設置為1的行的連續的地址，並允許行的內容存儲在CM206中進行處理，並從CM206中寫回。當剛剛被CM206處理過的行被向回存儲在RAM中時，no-flag信號15的值被存儲在由RAM控制器管理的所述行的第二位中。噹噹前的傳遞完成時，RAM控制器複製和所有行相關的所有第二位的值到其相關的第一位中。這個新的位的集合表示哪些行的標記已被設置，因而應當在下一個傳遞中被處理。
在RAM中的不是所有的行而僅僅是一小部分含有有效信息，其中所有的行被連續地存儲，並且在行地址0開始的情況下，可以對RAM控制器規定最後有效行的地址，以便限制其有效傳遞至有效行的組。這個地址藉助於外部處理裝置使用limit-address207信號輸入給RAM控制器。
LM200的L個行的集合可以在含有CM206的同一個矽晶片上實現，或者在矽晶片的外部使用非架上的存儲電路來實現。在兩種情況下，CE205被用於管理在L個行中存儲的信息，其把在行中存儲的信息傳遞到其中例如上述部分中所述的字符串指令被執行的CM206中，並把CM206的內容向回傳遞給行，使得能夠執行比CM206的M個符號存儲容量長得多的字符串的字符串操作。
當須要插入和刪除操作時，行不被填滿其整個容量，而只被部分地填充，從而允許在這些操作下在CM206中的符號串的擴大和縮小。在這種情況下，不含有有效符號的CM206的單元利用在被處理的串中未找到的預定的二進位圖案初始化。CM206產生作為被稱為interrupt(中斷)的在圖2中標號為101的外部處理實體的信號。當含有這個特定的二進位圖案的CM206的一個或幾個單元的標記被設置時，使該信號有效。
CM206及其外部連接連接被分成兩種類型。一種類型相當於CM206和其環境的互連，另一種類型相當於用於擴充電路所需的信號，即，如果多個CM206電路被連接在一起以便增加存儲量。
在下面的表達中假定最初的CM206塊可以存儲M個存儲器字，並且每個字的長度是N+1位，N位用於符號，1位用於標記。
如圖11所示的CM206的系統連接被列表如下。括號中的數字，當存在時，表示每個信號的位數。當使用對數功能時，則假定其是以3為底的對數。
.Data-in(M)N位字的數據輸入10，用於在CM206中輸入符號。
.Data-out(M)N位字的數據輸出11，用於從CM206讀出符號。
.Address(log(N))log(N)位的地址輸入12，其中log是以2為底的對數。
.Data-RamM*(N+1)位的雙向數據輸入100和輸出，允許一個存儲緩衝器的內容或行被寫入RAM200或從RAM200讀出。
.Index(log(M))根據最後進行的是正向操作或反向操作，保持第一個或最後一個被標記的單元的地址的log(M)位的輸出13。
.Interrupt(1)該信號由CM206產生，用於外部處理實體，並表示含有用於表示一個空的或無效條件預定的專用二進位配置的一個或幾個單元被設置標記。
.Command(5)用於表示要由CM206進行的操作的指令代碼的5位的輸入14。
.No-flag(1).二進位輸出信號15，表示CM206不含有被標記的單元。
No-eq(1)二進位輸出信號16，表示最後一個條件查找類指令(正向、反向或被限制的條件查找)未設置任標記。
.One-flag二進位輸出信號17，表示CM206隻包含一個被標記的單元。
.clock輸入信號14，作為時鐘信號，其控制CM206的操作。
信號data-in，addr，和com具有相對於有效的時鐘沿的相關的建立和保持時間。信號data-out，index，no-flag，no-eq，one-flag在和訪問存儲器相關的一個延遲之後成為穩定的。所述延遲相對於時鐘信號的有效沿被測量。當若干個CM206電路或模塊被連接在一起時，在擴展內部移位寄存器的一維陣列中，使用幾個信號把CM206模塊以線性方式連接在一起。這些信號示於圖1，現說明如下.Data-left-in(N+2)從前一個模塊接收的信號26，並具有一個符號(M位)、其相關的標記(1位)、以及和所述標記(1位)相關的比較器的輸出的二進位表示。
.Data-left-out(N+2)為前一模塊產生的信號25，並具有一個符號(M位)、其相關的標記(1位)、以及和所述標記相關的比較器的輸出的二進位表示。
.Data-right-in(N+2)從下一個模塊接收的信號19，並具有一個符號(M位)、其相關的標記(1位)、以及和所述標記相關的比較器的輸出的二進位表示。
.Data-right-out(N+2)為下一個模塊產生的信號18，並具有一個符號(M位)、其相關的標記(1位)、以及和所述標記相關的比較器的輸出的二進位表示。
.Line-in(2)從X變碼器電路接收的兩個信號23，被用於擴充所述結構。
.Line-out(1)為X變碼器電路產生的信號22。
.Column-in從Y變碼器電路接收的兩個信號20，被用於擴充所述結構。
.Column-out為Y變碼器電路產生的信號21。
在標題為內部結構的部分更加詳細限定了最後的4個信號組。如果這8個連接不用於擴充存儲器，則它們必須使用常規的技術被正確地連接與/或終止，以便能夠使CM206系統正確地操作。
CM206的內部結構圖12是表示包括CM206的單元30的兩維陣列的方塊圖、用於連接其和其它的CM206或CE205電路的信號、以及允許進行單元的選擇並報告關於被標記的單元的位置的狀態信息的電路。單元的陣列由一個兩維陣列的N+1位的M個單元構成。選擇兩維具有兩個理由。首先，為了最大地利用矽面積，其次，為了使和CM206中的信號傳播相關的延遲最小。代替使用在RAM電路中存在的典型的解碼器，CM206使用變碼器電路，這是因為地址須要被編碼、解碼和變碼，根據執行的指令而定。兩維方法須要使用兩個變碼器電路，每一維使用其中的一個。
容易理解，不脫離本發明的較寬的方面，CM206還可以作為一維的存儲單元陣列被構成。
圖12所示的CM206的內部結構包括以下的子系統.Symbol Cells用於符號的存儲器，或動態存儲器，其由M個單元的兩維陣列30構成，一個單元用於包含在存儲器中的一個符號(第一個單元位於第一行，並在兩維陣列的第一列)。為了便於表示，在表1中(下面)從底部向上以遞增的順序對行編號，同時從左向右以遞增的順序對列編號。
.Data-RamM*(N+1)位的雙向總線100，其允許M個符號及其相關的被存儲在此處假定位於符號單元區(30)中的存儲行中的標記被寫入外部數據存儲器或從中讀出。利用由X-transcoder電路39產生的line-select106信號進行在這個傳遞中涉及的行的選擇。
.Interrupt這個1位的信號由CM206中的一個或幾個單元產生，CM206包含預定的唯一的二進位圖案，用於表示空的單元或含有無效符號的單元，並使得這個或這些單元的相關標記被設置。
.X-transcoder電路39含有用於和Ytranscoder電路結合尋址和訪問CM206中的單元的邏輯。
.Y-transcoder電路40含有用於和X-transcoder電路39結合尋址和訪問單元的陣列中的信息。
.兩個輸入的AND gate門34接收由兩個變碼器產生的eq信號36和41，並產生信號one-flag 35。
.兩個變碼器電路把CM206的內容分割成3個區域位於第一被標記的單元之前的單元的集合，第一個被標記的單元，以及從第一個被標記的單元開始的單元的集合。
下面列出的信號對CM206電路的內部部分進行操作。因為含有M個單元的兩維陣列，並因為必須計算最低或最高地址的被標記的單元的地址，變碼器電路的操作依賴於幾個關鍵信號line-out，line-in，column-out以及column-in。
.line-outline-out信號42共有 個。每個和單元的兩維陣列的一行相關，並且如果該行含有被標記的單元，則該信號有效，否則無效。
.column-out類似地，column-out信號44，共有 個，它們相應於單元的兩維陣列的每個列。如果其相應的列在第一有效行上含有被標記的單元，則column-out類的信號是有效的，否則是無效的。
.line-in該信號43共有 個。兩維陣列的每行從X變碼器接收兩個信號，line-in[1]和line-in
，其表示以下條件是否該行是第一個含有被標記的單元的行，以及該行是否大於等於含有被標記的單元的第一行。
例如，假定具有8×8的具有下面所示的內容的兩維的單元陣列，其中括號包括被標記的單元中的符號。在頂行和第一列上的數字表示用於訪問CM206的行和列的編號系統，而不是在陣列中存儲的符號。
012345670 XXXXXXXX1 XXXXXXXX2 XXXXXXXX3 XXXXXXXX4 XX[X] XXX[X] X5 XXXXXXXX6 [X] XXX[X] XXX7 XXXXXXX[X]表1則按照行0，1，2，直到7的順序列出的信號42等於00001011。按照同樣順序列出的line-in信號43的line-in[1]是00001000，並且line-in信號43的line-in
是00001111。
.column-in 45Y變碼器電路的每一列和表示以下條件的兩個輸出信號column-in
以及column-in[1]相關該列是否含有兩維陣列的第一被標記的單元。
該列是否等於含有第一被標記的單元的列，或者是否其具有較高的地址。
使用上述8×8的兩維陣列的同一個例子，列出和從7遞減到0的列相關的信號，column-in信號45含有值00100000和00111111。
CM206的單元的外部結構除去已經提出的data-in，data-out，以及com信號之外，下面的信號使包含符號和標記的基本單元和其環境相連，如圖13和14所示。
.Data-left-outN+2位的信號25向前一個單元傳播的信息，並由N+1位的left-cell-out信號構成，其傳送存儲在單元中的符號及其相關的標記位。
.Left-eq-out(1)由比較器55在單元內部產生的輸出信號54。
.Data-right-out(N+2)N+2位的信號傳送向下一個單元傳播的信息，並由N+1位的right-cell-out信號構成，其傳送存儲在單元中的符號及其相關的標記位。
.Right-eq-out(1)在單元內部的比較器的輸出信號55。
.Data-left-in(N+2)N+2位的信號傳送從前一個單元接收的信息，並由N+1位的left-cell-in信號52構成，其傳送存儲在前一個單元中的符號及其相關的標記位，以及1位的信號left-eq-in，53，其傳送在前一個單元內部的比較器55的輸出。
.Data-right-in(N+2)這些N+2位的信號傳送從下一個單元接收的信息，並由N+1位的right-cell-in信號58構成，其傳送存儲在下一個單元中的符號及其相關的標記位，以及一位的信號right-eq-in 56，其是下一個單元內部的比較器55的輸出。
.Line-out(1)是一個產生標記的相反值的開路漏極(open drain)輸出。其和來自兩維陣列的相同行上的所有其它單元的所有line-out信號42並聯連接，並成為X變碼器電路39的輸入之一。
.Column-out(1)是一個一位的信號44，並是一個只在包含被標記的單元的第一行上產生標記的相反值的開路漏極輸出。其和兩維陣列的相同列中的單元的所有的column-out輸出並聯連接，並成為Y變碼器電路40的輸入之一。
.Line-in(2)line-in[1]和line-in
形成line-in信號43，其由X變碼器電路39產生，並表示以下條件line-in[1]單元屬於含有兩維陣列的第一被標記的單元的行。
Line-in單元屬於或者等於含有陣列的第一被標記的單元的行或者是具有較高地址的行。
.Colmn-in(2)column-in[1]和column-in
形成column-in信號45，並被Y變碼器電路40產生。它們表示以下條件column-in[1]單元屬於含有單元被標記的單元的列。
Column-in單元屬於從含有第一被標記的單元的列開始的列。
.No-eq當在本發明的綜述部分中所述的cfind型指令在單元中成功時，這個開路漏極輸出16是低態有效的。
.Symbol-data(N+1)這些雙向信號106允許單元的內容(N位符號加上一位標記)被寫入外部存儲器位置或從中被讀出。
.Interrupt 101如果標記被設置並且存儲的符號是一個預定的且唯一的表示無效符號的或者表示單元是空的二進位圖案，則這個信號被產生。這個信號由開路漏極驅動器產生，並且由陣列中的M個單元產生的所有M個中斷信號都進行「或」運算，以用於產生圖3中的中斷信號101。
單元的內部結構單元的內部結構如圖14所示，並含有以下的電路REG電路60是一個(N+1)位的含有單元中存儲的值的及其相關的標記位的值的寄存器。
MUX1電路61是N個4輸入多路傳輸器的集合，其根據被稱為c1 65和c2 66的選擇代碼允許幾個值中的一個被寫入REG中。對於多路傳輸器61的可能的選擇是出現在data-in信號10上的外部值，出現在sumbol-data信號106上的外部值，被left-cell-out信號51傳送的來自以前的單元的值，被right-cell-in信號58傳送的來自下一個的單元的值，或者存儲在REG 60中的值，其允許寄存器的動態實現。
MUX2電路62是一種4輸入多路傳輸器，其根據被稱為c3和c4的選擇代碼67和68允許4位中的一位存儲在REG的最高有效位中。對於多路傳輸器62的可能的選擇是由PLA 63產生的標記，出現在symbol-data 106信號106中的標記，由信號left-eq-in53傳送的來自前一個單元的標記，由信號right-eq-in 56傳送的來自下一個單元的標記，或存儲在REG 60中的標記，其允許這些位的動態實現。
COMP電路55是一個組合電路，只有當在data-in輸入信號10上存在的符號等於單元的N位內容時，在其一位的輸出上產生一個1，並且其通過信號right-cell-out 59傳送。
Symbol-data(N+1)這些信號106傳送來自給定行的單元的內容或者在REG中的CM206單元的內容到外部存儲實體。傳遞的方向被R/W信號112控制。
PLA電路63是一個組合電路，其可以利用可編程的邏輯陣列來實現，並且其產生被稱為c1，c2，c3，c4，c5，c6，c7和c8的指令位65，66，67，68，69，107，109，和111，它們被在單元的內部使用，以及no-eq信號16和的相反值，以及column-out信號44。開路漏極反相器20驅動信號no-eq 16。反相器70驅動column-out信號44。PLA 63接收幾個輸入信號Command信號14，其傳送要被CM206執行的指令(find，cfind，index等)的二進位表示，
寄存器REG 60的值，由left-eq-in 53信號傳送的在前一單元內的比較器55的輸出，由right-eq-in 56信號傳送的在下一個單元中的比較器55的輸出，信號no-eq 16，由X變碼器產生的line-in信號43和由Y變碼器電路產生的column-in信號45。
PLA 63產生interrupt信號15，當寄存器60含有用於標記未使用的或無效的單元的預定符號時，並且當和寄存器相關的標記被設置時，該信號有效。
表示在寄存器60中存儲的符號的寄存器60的N位輸出由被信號c5 69控制的N個三態反相驅動器71反相，它們成為信號data-out 11。開路漏極反相器64反相在寄存器REG 60存儲的標記位，並產生信號line-out 42。開路漏極反相器產生信號no-eq 16，其來自PLA 63。開路漏極反相器70產生信號column-out 44。在理論上，從兩維陣列中的不同的單元輸出的所有data-out 11和no-eq 16被連接在一起，屬於一個行的所有的line-out 42也被連接在一起，在相同列上的單元的所有column-out信號44也被連接在一起。
變碼器圖15表示兩個變碼器電路39和40的組織結構。X變碼器電路接收如下信號.line-outs含有 位這些信號的每一個來自兩維陣列的單元的每個行，用於表示在行上被標記的單元的存在。
.Address-high信號96含有log(N)/2位，並表示輸入到CM206的地址的上半個，並用於選擇兩維陣列中的 個行中的一個。
.5位的command信號14隻用於實現一些輔助指令set-limit，set-limit-address，limited-find，limited-cfind，limited-reverse-find，limited-reverse-cfind，limited-write-all，ram-read和ram-write。
Y-transcoder電路40接收以下信號 位的Column-outs信號44，每個來自單元的兩維陣列的每一列，表示在相關的列上被標記的單元的存在，這個被標記的單元是其所屬的行的第一個。
位的Address-low信號97，其表示用於選擇給定的行的地址的下半個。
.5位的Command信號，只用於實現以前列出的輔助指令。
兩個變碼器包含以下電路.解碼器DCD 83用於解碼在X變碼器39中的地址信號的上半個或在Y變碼器中的地址信號的下半個。
.多路傳輸器MUX-3電路82由 的兩維多路傳輸器構成，並且其使用c6信號92作為選擇信號。
.用於邏輯功能OR的前綴網絡PN-OR電路91。
.LATCH電路85，其鎖存PN-OR信號的輸出，並用於限定用於被限制的操作的CM206的有效部分。其使用c7信號93作為負載指令。
.MUX-4多路傳輸器電路87具有和MUX-3 82電路相同的結構，並使用c8信號94作為選擇信號。
個xor門的線性網絡XOR-1 86用於確定在由MUX-4電路87輸出的二進位配置中1的第一次出現。
.優先權編碼器PE 80，用於編碼在X變碼器中的line-out 42，或在Y變碼器中的column-outs信號44，產生索引欄位的上半個，即X變碼器中的index-high 38，或下半個，即Y變碼器中的index-low 46。
.RPE優先權編碼器81，接收和優先權編碼器80相同的輸入，但是順序相反，使得其可以產生上、下半個c索引欄位。
.PLA電路84是一個小的組合邏輯塊，其可以由可編程的邏輯陣列來實現，其解碼指令欄位14，從而產生c9位92，c10位93，c11位94，和c12位95，用於控制變碼器電路。
.XOR-2電路89產生p/2位的值，其被輸入到p/2輸入與門88，並且其產生eq信號36。所述eq信號是索引index-high 98的上半部分和由RPE電路81產生的反向索引的上部分內容在X變碼器39中比較的結果，或者是在Y變碼器40中索引index-low 99的下半部分和由RPE電路81產生的反向索引的下部分內容比較的結果。
RAM控制器圖16表示RAM控制器12的實現，而圖17是表示RAM控制器12的內部結構的電路圖。RAM控制器為在RAM中存儲的每行保持兩位存儲器。第一位被存儲在含有L位的寄存器AR 208中，一個用於RAM中的每一行。L位的內容被輸入到優先權編碼器P-ENC 210，其輸出被設置為1的最小加權的位的二進位表示。優先權編碼器210的輸出是line-address 201，並且是要被選擇供下一個CM 206進行讀或寫操作的RAM中的行的地址。例如，如果AR含有00101110，則P-ENC在line-address上輸出010，這是被設置為1的AR中的最低有效位的地址。Line-address 201也被輸入到多路傳輸器MUX-7 213的0輸入端，當被合適地選擇時，其把行地址信號的內容輸入到解碼器ADCD 214。這個解碼器具有L個輸出，1個有效的，L-1個無效的。有效的輸出具有和其權重或地址被P-ENC 210輸出的AR 208中的最低有效1位的相同的權重。例如，如果行地址是010，則ADCD 214產生00000010，其中被設置為1的位具有加權2。由ADCD 214輸出的L個信號和AR 208輸出的L位被L個異或門215異或，從而產生在AR中存儲的相同的二進位圖案，但是此時AR中的最低有效1位被設置為0。使用同一個的例子，如果AR含有00101110，則P-ENC輸出010，其被輸入給ADCD而成為00000010，其和00101110異或而產生00101100，黑體的0位表示在AR的內容和異或門215的輸出之間的差。異或門215的輸出通過多路傳輸器MUX-6 209被輸入到寄存器AR，當step-enable信號222有效時，在下一個時鐘周期被存儲到其中。該信號是信號202的com類的一部分，並且在用於控制CE 205的外部處理實體的控制下。
AR，P-ENC，MUX-7，ZDCD，L XOR門和MUX-6的組合形成一個電路，當以在AR中以二進位形式存儲的數K開始時，該電路在行地址上輸出連續的2的冪，其和等於K。此外，在階躍使能(step-enable)信號控制下，以恆定的時間產生每個2的冪。當所有的1位都從AR寄存器中消失時，優先權編碼器檢測到這個條件，並激活信號stop221，該信號作為在當前狀態下沒有須要被處理的行的標記被外部處理實體檢測。這個裝置以二進位數在一個循環中自動地產生所有被設置為1的位的連續的加權，每個加權的輸出只佔一個周期。
當在寄存器AR中這種1的連續的消除發生時，行在CM206中被處理，並進行字符串操作。在這些操作結束時，當CM206的內容被向回存儲在行中時，被反向的並和init信號224進行或運算的no-flag信號15的值被記錄在作為L個D型觸發器218之一的D型觸發器中。在L組中選擇的觸發器的地址和在RAM中的行的地址相同，並利用ADCD電路214的輸出進行觸發器的選擇，如下所述。這些L觸發器含有1和0的新的圖案，該圖案表示必須在下一個操作期間處理的下一組行。
RAM控制器的初始化須要在AR的位中用這種方式存儲1，即只有RAM中須要被處理的行的相關的AR位設置為1。這些有效行被存儲在鄰接的塊中的RAM的連續的地址中，並使得在塊中的最低地址是0。例如，如果在RAM中只有3個行是有效的，則AR寄存器的最低3位必須被設置為1，而所有其它的位被設置為0。在這種情況下，最高地址行的地址是2，因為有效行具有地址0，1和2。在這種情況下，控制外部實體在limit-address207信號上發送最高行的地址到RAM控制器，並激活init信號224。得到的操作是，在通過多路傳輸器MUX-7的limit-address信號上的log(L)地址被ADCD解碼成為L信號，除去一個具有等於limit-address內容的加權之外全部為0。
然後把MUX-7的輸出被輸入到前綴OR電路OR-PN216，其把值為0的並且加權小於在其輸入中的僅僅1位的加權的所有位轉換為1。例如，如果OR-PN電路接收00000100，其中1位的加權是2，則其輸出是00000111。然後使這些L個信號通過L個或門219，並被輸入到D觸發器218的D輸入端。L個D觸發器218分別由ADCD電路產生的、分別和init信號224進行或運算的L個信號使能。當每個1的輸出相應於RAM中的有效行時，通過激活控制多路傳輸器MUX-6209的啟動信號，這些L個觸發器的內容被加載到寄存器AR 208中。
雖然參照優選實施例對本發明進行了詳細說明，本領域的技術人員應當理解，不脫離本發明的基本範圍和構思，可以作出各種改變，其元件可以用等效元件替換。因此，本發明不限於這些特定的實施例，而是本發明包括落在所附權利要求範圍內的所有實施例。
權利要求
1.一種用於選擇地檢查和操作數據的存儲器引擎，所述存儲器引擎包括存儲裝置，用於暫時地存儲作為數據字符串的所述數據；控制器，其向所述存儲裝置選擇地輸出多個指令之一，並接收來自所述存儲裝置的反饋數據，所述存儲裝置按照由所述控制器輸出的所述指令檢查在所述字符串中的數據字符；以及時鐘裝置，用於向所述存儲裝置和所述控制器輸出由每秒預定的時鐘周期數構成的時鐘信號，其中所述存儲裝置在所述時鐘周期的一個內檢查和選擇地操作所述數據字符中的一個。
2.如權利要求1所述的用於選擇地檢查和操作數據的存儲器引擎，其中所述存儲裝置是一個相聯存儲裝置。
3.如權利要求2所述的用於選擇地檢查和操作數據的存儲器引擎，其中所述相聯存儲裝置和一個數據總線以及一個緩衝存儲裝置進行電通信。
4.如權利要求3所述的用於選擇地檢查和操作數據的存儲器引擎，其中所述緩衝存儲裝置包括多個緩衝器，每個所述緩衝器具有等於所述相聯存儲裝置的存儲容量。
5.如權利要求2所述的用於選擇地檢查和操作數據的存儲器引擎，其中所述相聯存儲裝置由作為動態和靜態存儲單元之一的兩維陣列被構成。
6.如權利要求1所述的用於選擇地檢查和操作數據的存儲器引擎，其中從所述控制器輸出的所述多個指令之一是「find」指令，藉以使所述數據字符串被檢查，從而確定是否任何所述數據字符和預定的符號匹配，所述預定的符號由所述控制器和所述「find」指令結合進行傳遞；以及所述存儲裝置進行操作用於標記所有和所述預定符號匹配的所述字符的右方的所有所述數據字符。
7.如權利要求1所述的用於選擇地檢查和操作數據的存儲器引擎，其中從所述控制器輸出的所述多個指令之一是「reverse-find」指令，藉以使所述數據字符串被檢查，從而確定是否任何所述數據字符和預定的符號匹配，所述預定的符號由所述控制器和所述「reverse-find」指令結合進行傳遞；以及所述存儲裝置進行操作用於標記所有和所述預定符號匹配的所述字符的左方的所有所述數據字符。
8.如權利要求4所述的用於選擇地檢查和操作數據的存儲器引擎，其中所述控制器進行操作用於把數據字符串加載到所述緩衝器的每個中；所述緩衝器利用所述數據總線按照順序傳遞所述數據字符串到所述相聯存儲裝置中；從所述控制器輸出的所述多個指令之一是「find」指令，藉以使佔據所述相聯存儲裝置的所述數據字符串被檢查，從而確定是否任何所述數據字符和所述控制器與所述「find」指令結合而傳遞的第一個預定符號匹配；所述相聯存儲裝置進行操作用於標記和所述第一預定符號匹配的所有的所述字符的右方的所有所述數據字符。
9.如權利要求4所述的用於選擇地檢查和操作數據的存儲器引擎，所述控制器進行操作用於把數據字符串加載到所述緩衝器的每個中；所述緩衝器利用所述數據總線按照順序傳遞所述數據字符串到所述相聯存儲裝置中；從所述控制器輸出的所述多個指令之一是「reverse-find」指令，藉以使所述數據字符串被檢查，從而確定是否任何所述數據字符和由所述控制器與所述「reverse-find」指令結合而傳遞的第一個預定符號匹配；所述相聯存儲裝置進行操作用於標記和所述第一預定符號匹配的所有的所述字符的左方的所有所述數據字符。
10.如權利要求8所述的用於選擇地檢查和操作數據的存儲器引擎，其中從所述控制器輸出的所述多個指令之一是「c-find」指令，藉以使只有包括被標記的數據字符的那些所述數據字符串再次被檢查，從而確定和所述控制器與所述「c-find」指令結合而傳遞的第二個預定符號匹配的數據字符的存在；以及所述相聯存儲裝置進行操作用於標記和所述第二預定符號匹配的所有所述字符右方的所有所述數據字符，所述相聯存儲裝置復位在所述數據字符中的所有其它標記。
11.如權利要求9所述的用於選擇地檢查和操作數據的存儲器引擎，其中從所述控制器輸出的所述多個指令之一是「reverse-cfind」指令，藉以使只有包括被標記的數據字符的那些所述數據字符串再次被檢查，從而確定和所述控制器與所述「reverse-cfind」指令結合而傳遞的第二個預定符號匹配的數據字符的存在；以及所述相聯存儲裝置進行操作用於標記在和所述第二預定符號匹配的所有所述字符左方的所有所述數據字符，所述相聯存儲裝置復位在所述數據字符中的所有其它標記。
12.如權利要求5所述的用於選擇地檢查和操作數據的存儲器引擎，其中所述相聯存儲裝置包括第一變碼器電路和第二變碼器電路，用於提供在所述兩維陣列中的所述存儲單元的線性地址；以及所述第一變碼器電路包括第一鎖存電路，所述第二變碼器電路包括第二鎖存電路，所述第一和第二鎖存電路包含位置信息，表示所述相聯存儲裝置內的所述存儲單元的哪一個包含被標記的數據字符。
13.如權利要求1所述的用於選擇地檢查和操作數據的存儲器引擎，其中從所述控制器輸出的所述多個指令之一是「delele」指令，藉以使首先出現的被標記的數據字符被刪除，所述被標記的數據字符的右方的所有其它的所述數據字符，包括其標記的狀態，被向左移動；以及所述數據字符串從所述數據字符的最左方開始被檢查。
14.如權利要求1所述的用於選擇地檢查和操作數據的存儲器引擎，其中從所述控制器輸出的所述多個指令之一是「reverse-delele」指令，藉以使最左方的被標記的數據字符被刪除，所述最左方的被標記的數據字符的右方的所有其它的所述數據字符被向左移動；以及所述存儲裝置標記在所述最左方的被標記的數據字符的左方的數據字符。
15.如權利要求1所述的用於選擇地檢查和操作數據的存儲器引擎，其中響應「insert」指令，所述存儲裝置確定被標記的數據字符的第一次出現，並把所述第一個被標記的數據字符的右方的所有所述數據字符的內容和標記狀態，包括所述第一個被標記的數據字符，向右移動；所述存儲裝置利用由所述控制器結合所述「insert」指令而傳遞的一個預定符號替換所述第一個被標記的數據字符的前一個位置；以及所述數據字符串從所述數據字符的最左方開始被檢查。
16.如權利要求1所述的用於選擇地檢查和操作數據的存儲器引擎，其中響應「reverse-insert」指令，所述存儲裝置確定被標記的數據字符的第一次出現，並把所述第一個被標記的數據字符的右方的所有所述數據字符的內容，包括所述第一個被標記的數據字符，向右移動；所述存儲裝置利用由所述控制器結合所述「reverse-insert」指令而傳遞的預定符號替換所述第一個被標記的數據字符的前一個位置；以及所述數據字符串從所述數據字符的最左方開始被檢查。
17.如權利要求1所述的用於選擇地檢查和操作數據的存儲器引擎，其中從所述控制器輸出的所述多個指令之一是「next」指令，藉以使第一個被標記的數據字符的標記被復位；以及所述數據字符串從所述數據字符的最左方開始被檢查。
18.如權利要求1所述的用於選擇地檢查和操作數據的存儲器引擎，其中從所述控制器輸出的所述多個指令之一是「write-one」指令，藉以使由所述控制器結合所述「write-one」指令而傳遞的一個預定符號被寫入第一次出現的被標記的數據字符；所述數據字符串從所述數據字符的最左方開始被檢查；以及所述存儲裝置復位所述第一個被標記的數據字符，並標記所述第一個被標記的數據字符的右方的一個數據字符。
19.如權利要求1所述的用於選擇地檢查和操作數據的存儲器引擎，其中從所述控制器輸出的所述多個指令之一是「write-all」指令，藉以使由所述控制器結合所述「write-one」指令而傳遞的一個預定符號被寫入所有出現的被標記的數據字符；所述數據字符串從所述數據字符的最左方開始被檢查；以及所述存儲裝置復位所有所述被標記的數據字符，並標記所有所述被標記的數據字符的右方的數據字符。
20.如權利要求1所述的用於選擇地檢查和操作數據的存儲器引擎，其中從所述控制器輸出的所述多個指令之一是「jump」指令，藉以使所述數據字符串被檢查，以便確定和一個預定的分隔符匹配的第一次出現的被標記的數據字符；以及所述數據字符串從所述數據字符的最左方開始被檢查。
21.如權利要求1所述的用於選擇地檢查和操作數據的存儲器引擎，其中從所述控制器輸出的所述多個指令之一是「jump」指令，藉以使所述數據字符串被檢查，以便確定和一個預定的分隔符匹配的所有出現的被標記的數據字符；以及所述數據字符串從所述數據字符的最左方開始被檢查。
22.如權利要求20所述的用於選擇地檢查和操作數據的存儲器引擎，其中所述存儲裝置利用由所述控制器結合所述「jump」指令而傳遞的一個預定的符號代替和所述預定的分隔符匹配的所述第一個被標記的數據字符；以及所述存儲裝置復位所述第一個被標記的數據字符；以及在所述被復位的數據字符的右方的、相鄰的一個數據字符上設置標記。
23.如權利要求1所述的用於選擇地檢查和操作數據的存儲器引擎，其中所述存儲裝置包括多個存儲單元；以及所述指令並行地被傳遞到所有所述存儲單元，藉以使得能夠在所述時鐘周期的一個內修改所有的所述存儲單元。
24.一種利用存儲裝置、控制器以及時鐘裝置檢查和修改數據的方法，所述存儲裝置用於存儲作為數據字符串的所述數據，所述控制器用於對所述存儲裝置選擇地輸出指令，所述時鐘裝置用於向所述控制器和所述存儲裝置輸出由每秒預定數量的時鐘周期構成的時鐘信號，所述方法包括以下步驟在所述存儲裝置中裝入所述數據；按照由所述控制器輸出的所述指令檢查所述被裝入的存儲器；以及按照由所述控制器輸出的所述指令選擇地操作所述數據，一個所述數據字符的所述檢查和操作在一個所述時鐘周期內完成。
25.按照權利要求24所述的用於檢查和操作數據的方法，還包括以下步驟具有所述靜態和動態存儲單元之一的兩維陣列構成所述存儲裝置，作為相聯存儲裝置。
26.按照權利要求24所述的用於檢查和操作數據的方法，還包括以下步驟檢查所述裝入的數據，確定是否任何所述數據字符和由所述控制器結合「find」指令傳遞的第一預定符號匹配；以及從所述裝入的數據字符的最左方開始所述檢查。
27.按照權利要求26所述的用於檢查和操作數據的方法，還包括以下步驟確定是否任何所述裝入的數據字符和所述第一預定符號匹配；在位於所述任何裝入的已被確定和所述第一預定符號匹配的數據字符的右方的所述數據字符串中的任何所述裝入的數據字符上設置一個標記；以及除去設置在所述裝入的位於已被確定和所述第一預定符號匹配的任何所述裝入的數據字符的右方的數據字符上的所述標記之外，復位在所述裝入的數據字符上的所有的標記。
28.按照權利要求26所述的用於檢查和操作數據的方法，還包括以下步驟設置一個和數據總線以及所述存儲裝置電通信的緩衝器裝置，所述緩衝器裝置包括多個緩衝器，其中每個所述緩衝器具有等於所述存儲裝置的存儲容量；通過所述數據總線從所述存儲裝置中除去所述被檢查的數據字符串；在一個所述緩衝器中存儲所述被除去的數據字符串；以及隨後裝入並檢查在所述緩衝器中存儲的其它數據字符串，直到所有的所述緩衝器被檢查過，每個所述其它數據字符串在完成其各自的檢查時被存儲在所述緩衝器中。
29.按照權利要求28所述的用於檢查和操作數據的方法，還包括以下步驟重新檢查包括被標記的數據字符的任何所述數據字符串，確定所述被重新檢查的數據字符串是否包括和所述控制器結合「c-find」指令傳遞的一個第二預定符號匹配的數據字符；以及標記位於和所述第二預定符號匹配的所述數據字符的右方的所有所述數據字符，同時復位所述數據字符中的所有其它的標記。
30.按照權利要求24所述的用於檢查和操作數據的方法，還包括以下步驟檢查所述裝入的數據，確定是否任何所述數據字符和所述控制器結合「reverse-find」指令傳遞的第一預定符號匹配；確定是否任何所述裝入的數據字符和所述第一預定符號匹配；在位於所述任何裝入的已被確定和所述第一預定符號匹配的數據字符的左方的所述數據字符串中的任何所述裝入的數據字符上設置一個標記；以及除去設置在所述裝入的位於已被確定和所述第一預定符號匹配的任何所述裝入的數據字符的左方的數據字符上的所述標記之外，復位在所述裝入的數據字符上的所有的標記。
31.按照權利要求28所述的用於檢查和操作數據的方法，還包括以下步驟重新檢查包括被標記的數據字符的任何所述數據字符串，以便確定所述被重新檢查的數據字符串是否包括和所述控制器結合「reverse-cfind」指令傳遞的一個第二預定符號匹配的數據字符；以及標記位於和所述第二預定符號匹配的所述數據字符的左方的所有所述數據字符，同時復位所述數據字符中的所有其它的標記。
32.按照權利要求30所述的用於檢查和操作數據的方法，還包括以下步驟設置一個和數據總線以及所述存儲裝置電通信的緩衝器裝置，所述緩衝器裝置包括多個緩衝器，其中每個所述緩衝器具有等於所述存儲裝置的存儲容量；通過所述數據總線從所述存儲裝置中除去所述被檢查的數據字符串；在一個所述緩衝器中存儲所述被除去的數據字符串；以及隨後裝入並檢查在所述緩衝器中存儲的後續數據字符串，直到所有的所述緩衝器被檢查過，每個所述其它的數據字符串在完成其各自的檢查時被存儲在所述緩衝器中。
33.按照權利要求24所述的用於檢查和操作數據的方法，還包括以下步驟響應「delete」指令刪除在所述裝入的數據中第一次出現的被標記的數據字符；向左移動在所述被標記的數據字符的右方的所有所述數據字符，包括它們的標記狀態；以及從所述裝入的數據字符的最左方開始所述檢查。
34.按照權利要求24所述的用於檢查和操作數據的方法，還包括以下步驟響應「reverse-delete」指令刪除在所述裝入的數據中第一次出現的被標記的數據字符；向左移動在所述被標記的數據字符的右方的所有所述數據字符，包括它們的標記狀態；標記和所述已被刪除的所述標記的數據字符相鄰的並位於其左方的數據字符；以及從所述裝入的數據字符的最左方開始所述檢查。
35.按照權利要求24所述的用於檢查和操作數據的方法，還包括以下步驟響應「insert」指令確定在所述裝入的數據中的被標記的數據字符的第一次出現；向右移動在所述被標記的數據字符的右方的所有所述數據字符的內容和標記狀態，包括所述第一個被標記的數據字符；利用由所述控制器結合所述「insert」指令傳遞的一個預定符號代替所述第一個被標記的數據字符的前一個位置；以及從所述裝入的數據字符的最左方開始所述檢查。
36.按照權利要求24所述的用於檢查和操作數據的方法，還包括以下步驟響應「reverse-insert」指令確定在所述裝入的數據中的被標記的數據字符的第一次出現；向右移動在所述被標記的數據字符的右方的所有所述數據字符的內容，包括所述第一個被標記的數據字符；插入由所述控制器結合所述「reverse-insert」指令傳遞的一個預定符號來代替所述第一個被標記的數據字符的前一個位置；標記所述插入的預定符號；以及從所述裝入的數據字符的最左方開始所述檢查。
37.按照權利要求24所述的用於檢查和操作數據的方法，還包括以下步驟響應「next」指令復位在所述裝入的數據中的第一個被標記的數據字符上的標記；以及從所述裝入的數據字符的最左方開始檢查。
38.按照權利要求24所述的用於檢查和操作數據的方法，還包括以下步驟在所述裝入的數據中向第一次出現的被標記的數據字符寫入通過「write-one」指令傳遞的一個預定符號；復位所述第一個被標記的數據字符，並標記位於所述第一個標記的數據字符的右方的數據字符；以及從所述裝入的數據字符的最左方開始檢查。
39.按照權利要求24所述的用於檢查和操作數據的方法，還包括以下步驟在所述裝入的數據中向所有出現的被標記的數據字符寫入通過「write-all」指令傳遞的一個預定符號；復位所有所述被標記的數據字符，並標記位於所有所述被標記的數據字符的右方的數據字符。
40.按照權利要求24所述的用於檢查和操作數據的方法，還包括以下步驟檢查所述裝入的數據，以便確定第一次出現的和所述控制器輸出的「jump」指令相關的一個預定的分隔符匹配的被標記的數據字符；以及從所述裝入的數據字符的最左方開始所述檢查。
41.按照權利要求40所述的用於檢查和操作數據的方法，還包括以下步驟利用與所述「jump」指令相關的由所述控制器傳遞的一個預定的符號代替和所述預定的分隔符匹配的所述第一個被標記的數據字符；復位所述第一個被標記的數據字符；以及在所述被復位的數據字符的右方的、相鄰的一個所述數據字符上設置標記。
42.一種用於選擇地檢查和操作數據的存儲器引擎，所述存儲器引擎包括相聯的存儲裝置，其具有選擇地移動的能力，用於暫時存儲作為數據字符串的所述數據；控制器，其選擇地對所述存儲裝置輸出多個指令中的一個，並從所述存儲裝置接收數據反饋，所述存儲裝置按照由所述控制器輸出的指令檢查所述字符串中的數據字符；以及所述相聯的存儲裝置選擇地響應由所述控制器發出的第一指令而移動所有所述數據字符，並且所述相聯的存儲裝置響應由所述控制器輸出的第二指令只移動所述數據字符的一部分。
43.按照權利要求42所述的用於選擇地檢查和操作數據的存儲器引擎，還包括時鐘裝置，用於向所述存儲裝置和所述控制器輸出由每秒預定數量的時鐘周期構成的時鐘信號，其中所述存儲裝置在一個所述的時鐘周期內檢查並選擇地操作所述數據字符。
全文摘要
一個存儲器引擎組合相聯的存儲器和隨機存取存儲器，用於使得能夠對數據快速地進行字符串檢索、插入和刪除操作，並且包括用於暫時存儲作為數據字符串的數據的存儲裝置。一個控制器被用於選擇地對所述存儲裝置輸出多個指令中的一個，並接收從其反饋的數據，所述存儲裝置按照由所述控制器輸出的指令檢查串中的數據字符。還利用一個時鐘裝置向所述存儲裝置和所述控制器輸出由每秒內一個預定數量的時鐘周期構成的時鐘信號，所述存儲裝置在一個時鐘周期內檢查並選擇地操作一個數據字符。
文檔編號G11C15/04GK1554048SQ02817663
公開日2004年12月8日 申請日期2002年8月7日 優先權日2001年8月10日
發明者格奧爾基·斯特凡, 多米尼克·蒂埃博, 克 蒂埃博, 格奧爾基 斯特凡 申請人:吉米塞公司