用于确定搜索起点的装置和方法

摘要

本发明的目的是从待搜索对象之中有效地检测更长的字符串，从而具有相同部分的不同长度的多个字符串存在于其中。本发明包括：重复数据搜索电路(21)，其以某个字符为起点评估在已经输入的字符数据与CAM单元阵列(26)内的字符数据之间的连续匹配以便输出指示存在或者不存在连续匹配的OFRB‑0和指示连续匹配的地址的MADR‑0；以及跟踪电路100₁，...，100_K，其评估以已经移位一个字符的字符各自为起点来评价连续匹配以便输出指示存在或者不存在连续匹配的OFRB‑1、...、OFRB‑K和指示连续匹配的地址的MADR‑1、...、MADR‑K。然后标识已经输出在OFRB‑0、...、OFRB‑K之中为最长连续匹配的信号的电路，并且使用由该电路输出的在MADR‑1、...、MADR‑K之中的地址作为最长匹配字符串的地址。

主权项

一种通过将数据元序列的第一部分数据元序列替换为关于所述数据元序列的第二部分数据元序列的位置和长度的信息来压缩所述数据元序列的装置，包括：内容可寻址存储器，被配置用于将形成所述数据元序列的至少一部分的多个数据元中的每个数据元存储在与所述数据元在所述数据元序列中的位置相对应的地址处，并且在给出搜索数据元时，在与所述搜索数据元相匹配的匹配数据元被作为所述多个数据元之一存储的情况下，输出存储所述匹配数据元的所述地址；主生成电路，被配置用于在向所述内容可寻址存储器给出所述搜索数据元、并且将所述匹配数据元的序列存储在所述内容可寻址存储器中，其中所述匹配数据元的序列与开始于所述搜索数据元的序列中的参考数据元的序列是相匹配的情况下，基于从所述内容可寻址存储器输出的所述地址生成第一行存在信息和第一行地址信息，所述第一行存在信息指示所述匹配数据元的序列被存储，并且所述第一行地址信息指示存储所述匹配数据元的序列的所述地址；K个扩展生成电路，所述K个扩展生成电路中的第J个扩展生成电路(K代表自然数，并且J代表等于或者小于K的自然数)被配置用于在向所述内容可寻址存储器给出所述搜索数据元、并且将所述匹配数据元的序列存储在所述内容可寻址存储器中，其中所述匹配数据元的序列与开始于所述搜索数据元的序列中的从所述参考数据元起的第J个数据的序列是相匹配的情况下，基于从所述内容可寻址存储器输出的所述地址生成第一行存在信息和第一行地址信息，所述第一行存在信息指示所述匹配数据元的序列被存储，并且所述第一行地址信息指示存储所述匹配数据元的序列的所述地址；第一输出电路，被配置用于在向所述内容可寻址存储器给出所述搜索数据元、并且所述主生成电路和所述K个扩展生成电路中的任何生成电路生成所述第一行存在信息的情况下，输出第二行存在信息，所述第二行存在信息指示将所述匹配数据元的序列存储在所述内容可寻址存储器中，其中所述匹配数据元的序列与开始于所述搜索数据元的序列中的所述参考数据元之后的任何数据元的序列是相匹配的；第二输出电路，被配置用于在向所述内容可寻址存储器给出所述搜索数据元的情况下，输出由所述主生成电路和所述K个扩展生成电路中生成所述第一行存在信息的至少一个生成电路生成的所述第一行地址信息作为第二行地址信息；以及确定部，被配置用于向所述内容可寻址存储器连续给出形成所述第一部分数据元序列的所述数据元作为所述搜索数据元，基于紧接于所述第一输出电路不再输出所述第二行存在信息之前从所述第二输出电路输出的所述第二行地址信息来确定所述第二部分数据元序列的所述位置，以及基于来自所述第一输出电路的所述第二行存在信息的连续输出的数量来确定所述第二部分数据元序列的所述长度。