JPH0477967A - メモリ使用方式 - Google Patents
メモリ使用方式Info
- Publication number
- JPH0477967A JPH0477967A JP2191954A JP19195490A JPH0477967A JP H0477967 A JPH0477967 A JP H0477967A JP 2191954 A JP2191954 A JP 2191954A JP 19195490 A JP19195490 A JP 19195490A JP H0477967 A JPH0477967 A JP H0477967A
- Authority
- JP
- Japan
- Prior art keywords
- character string
- transition destination
- area
- memory
- storing
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 230000007704 transition Effects 0.000 claims abstract description 24
- 238000000034 method Methods 0.000 claims description 9
- 238000010586 diagram Methods 0.000 description 6
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明は、情報の検索水を、メモリを用いて実現するメ
モリ使用方式に関する。
モリ使用方式に関する。
レコード−意に識別する可変長文字列のヘッダを持つ複
数のレコードから成るファイルと、複数の検索キー（可
変長文字列）が与えられ、このファイルから検索キーと
同一の文字列をヘッダとするすべてのレコードを検索水
により選び出す処理がある。このような検索水を実現す
る場合、終端ノードまでの遷移状態はすべてポインタで
つないで実現している。
数のレコードから成るファイルと、複数の検索キー（可
変長文字列）が与えられ、このファイルから検索キーと
同一の文字列をヘッダとするすべてのレコードを検索水
により選び出す処理がある。このような検索水を実現す
る場合、終端ノードまでの遷移状態はすべてポインタで
つないで実現している。
このように検索水において、終端ノードまでの推移をす
べてポインタを用いて表す方法では、冗長なポインタが
存在し、検索水を実現するために無駄なメモリ空間が生
じる。
べてポインタを用いて表す方法では、冗長なポインタが
存在し、検索水を実現するために無駄なメモリ空間が生
じる。
本発明の目的は、このような欠点を除去し、使用メモリ
の節約ができるメモリ使用方式を提供することにある。
の節約ができるメモリ使用方式を提供することにある。
本発明は、所定のノードから終端のノードまで分岐せず
に遷移する文字列による検索を、メモリを用いて行うメ
モリ使用方式において、連続したメモリ領域に前記文字
列を格納することを特徴としている。
に遷移する文字列による検索を、メモリを用いて行うメ
モリ使用方式において、連続したメモリ領域に前記文字
列を格納することを特徴としている。
前述した本発明において、前記文字列を連続した別領域
のメモリに格納するのが好適である。
のメモリに格納するのが好適である。
また、前述した本発明において、格納先を示す情報に付
加された正または負の符号により、文字列が別領域のメ
モリに格納されていることを示すのが好適である。
加された正または負の符号により、文字列が別領域のメ
モリに格納されていることを示すのが好適である。
次に、本発明の実施例について図面を参照して説明する
。
。
第１図、第２図、第３回は、本発明を説明するための図
である。すなわち、第１図は、複数の検索キーの集合Ｋ
＝ （ａｂｃ、 ａｂ、 ａｃｃ）を状態遷移で表し
た説明図である。第２図は、各状態の遷移先をａ＋ ｂ
＋ Ｃの入力文字それぞれに関し記述した検索木の説明
図である。第３図は、分岐せずに終端ノードまで遷移す
る文字列を、連続した領域に格納した検索木の説明図で
ある。
である。すなわち、第１図は、複数の検索キーの集合Ｋ
＝ （ａｂｃ、 ａｂ、 ａｃｃ）を状態遷移で表し
た説明図である。第２図は、各状態の遷移先をａ＋ ｂ
＋ Ｃの入力文字それぞれに関し記述した検索木の説明
図である。第３図は、分岐せずに終端ノードまで遷移す
る文字列を、連続した領域に格納した検索木の説明図で
ある。
第１図において、検索キーとして、“’ａｂｃ”ａｂ″
ａｃｃ”を選んだときの状態遷移図が示されている
。ここで＄”は、文字列の終端を表す記号である。カッ
コ内の数字は、終端記号パ＄”および文字列を構成する
ａ”、ｂ“、Ｃ”の内部表現値であり、便宜上、それぞ
れ０，１，２．３に対応づけている。ＳＯは、文字列の
初期状態であり、第１番目の文字として“′ａ”が入力
されると８１に遷移する。第２番目の文字°“ｂ”が入
力されると、ＳｌはＳ２に遷移する。以下同様に、Ｓｉ
の遷移先Ｓｊは、次式より求まる。
ａｃｃ”を選んだときの状態遷移図が示されている
。ここで＄”は、文字列の終端を表す記号である。カッ
コ内の数字は、終端記号パ＄”および文字列を構成する
ａ”、ｂ“、Ｃ”の内部表現値であり、便宜上、それぞ
れ０，１，２．３に対応づけている。ＳＯは、文字列の
初期状態であり、第１番目の文字として“′ａ”が入力
されると８１に遷移する。第２番目の文字°“ｂ”が入
力されると、ＳｌはＳ２に遷移する。以下同様に、Ｓｉ
の遷移先Ｓｊは、次式より求まる。
ｊ＝ＡＤＲ３［ｉｌ ＋ｘｍ
ここで、ｘｍは第ｍ番目に入力された文字の内部表現値
である。
である。
第２図において、次の状態への遷移先を各状態ごとに格
納しておくことで検索木を実現している。
納しておくことで検索木を実現している。
ここで、Ｓ３． Ｓ４． Ｓ５． Ｓ６． Ｓ７． Ｓ
８は、遷移先を０または１つしか持たず、かつ後続する
状態で分岐するものはない。たとえば、Ｓ５においては
、遷移先がＯであり、Ｓ６においては、検索キー“Ｃ”
に対応して遷移先が８７となっている。このように、分
岐せずに終端まで到達するノードは、あらゆる入力記号
を想定して遷移先を格納する領域を確保しておく必要は
なく、第３図のストリング（ＳＴＲＩＮＧ）のように連
続した別領域に文字列を格納しておくことで、使用する
メモリ空間を節約することができる。ここで、ポインタ
の指すアドレスが、別領域か否かは、ポインタの正負で
判定する。すなわち、ポインタの値が正ならば従来通り
のアドレスを示し、負ならば別領域上のアドレスを示す
。たとえば、Ｓｌにおいて、検索キー“Ｃ”に対応して
−１のようになっている。これは、別領域上のアドレス
を示している。
８は、遷移先を０または１つしか持たず、かつ後続する
状態で分岐するものはない。たとえば、Ｓ５においては
、遷移先がＯであり、Ｓ６においては、検索キー“Ｃ”
に対応して遷移先が８７となっている。このように、分
岐せずに終端まで到達するノードは、あらゆる入力記号
を想定して遷移先を格納する領域を確保しておく必要は
なく、第３図のストリング（ＳＴＲＩＮＧ）のように連
続した別領域に文字列を格納しておくことで、使用する
メモリ空間を節約することができる。ここで、ポインタ
の指すアドレスが、別領域か否かは、ポインタの正負で
判定する。すなわち、ポインタの値が正ならば従来通り
のアドレスを示し、負ならば別領域上のアドレスを示す
。たとえば、Ｓｌにおいて、検索キー“Ｃ”に対応して
−１のようになっている。これは、別領域上のアドレス
を示している。
このように、本実施例において、複数個の繰り返しがな
い文字列の順序を持たない集合をリスト構造で表現し、
連続したメモリ領域に文字列を格納している。すなわち
、連続したメモリ領域に文字列を格納することにより、
冗長なポインタを廃し、使用メモリを節約できる。
い文字列の順序を持たない集合をリスト構造で表現し、
連続したメモリ領域に文字列を格納している。すなわち
、連続したメモリ領域に文字列を格納することにより、
冗長なポインタを廃し、使用メモリを節約できる。
以上説明したように本発明は、分岐せずに自ノードから
終端ノードまで遷移する文字列をリスト構造で記述する
代わりに、連続した領域に文字列を格納することにより
、使用メモリ空間を節約できるという効果がある。
終端ノードまで遷移する文字列をリスト構造で記述する
代わりに、連続した領域に文字列を格納することにより
、使用メモリ空間を節約できるという効果がある。
第１図、第２図、第３図は、本発明を説明するための図
である。 ５Ｏ−５８・・・遷移先 ＄・・・・・終端記号
である。 ５Ｏ−５８・・・遷移先 ＄・・・・・終端記号
Claims (2)
- （１）所定のノードから終端のノードまで分岐せずに遷
移する文字列による検索を、メモリを用いて行うメモリ
使用方式において、 連続したメモリ領域に前記文字列を格納することを特徴
とするメモリ使用方式。 - （２）前記文字列を連続した別領域のメモリに格納する
請求項１記載のメモリ使用方式。（３）格納先を示す情
報に付加された正または負の符号により、文字列が別領
域のメモリに格納されていることを示す請求項２記載の
メモリ使用方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2191954A JPH0477967A (ja) | 1990-07-20 | 1990-07-20 | メモリ使用方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2191954A JPH0477967A (ja) | 1990-07-20 | 1990-07-20 | メモリ使用方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0477967A true JPH0477967A (ja) | 1992-03-12 |
Family
ID=16283217
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2191954A Pending JPH0477967A (ja) | 1990-07-20 | 1990-07-20 | メモリ使用方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0477967A (ja) |
-
1990
- 1990-07-20 JP JP2191954A patent/JPH0477967A/ja active Pending
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6633953B2 (en) | Range content-addressable memory | |
| EP1485827A2 (en) | Efficient ipv4/ipv6 best matching prefix method and apparatus | |
| JP4995125B2 (ja) | 固定長データの検索方法 | |
| JPS60146346A (ja) | ハツシング装置 | |
| JPH02231675A (ja) | データを構成、管理又は検索するための方法及び装置 | |
| US6976025B2 (en) | Database and method for storing a searchable set of keywords | |
| JPH0477967A (ja) | メモリ使用方式 | |
| JPS60105040A (ja) | 文章検索方式 | |
| WO2003003250A1 (en) | Range content-addressable memory | |
| JPH10124356A5 (ja) | ||
| JPS62179083A (ja) | 文字列照合方法 | |
| JP2001520429A (ja) | Ｒａｍを使用してシフトレジスタをエミュレートする方法 | |
| JP2874810B2 (ja) | キーの記憶割り当て方法 | |
| JP3224159B2 (ja) | エキスパートシステム | |
| WO2004088486A1 (ja) | ルックアップテーブル装置及び信号変換方法 | |
| JPS60160444A (ja) | リスト処理方法 | |
| JP3092524B2 (ja) | ルーチングシステム | |
| JPS61105636A (ja) | 印字装置 | |
| JPS603035A (ja) | 記憶装置 | |
| JPS6319858Y2 (ja) | ||
| JPS60104373A (ja) | 文字処理装置 | |
| JPH07175695A (ja) | データベース制御方式 | |
| JPH04256210A (ja) | データ圧縮格納方式 | |
| JPS5897742A (ja) | 検索装置 | |
| JPH07210455A (ja) | 記憶装置 |