JP2002049645A - ハッシュ値算出方法、ハッシュ値算出装置、検索方法、検索装置、記録媒体 - Google Patents
ハッシュ値算出方法、ハッシュ値算出装置、検索方法、検索装置、記録媒体Info
- Publication number
- JP2002049645A JP2002049645A JP2000234735A JP2000234735A JP2002049645A JP 2002049645 A JP2002049645 A JP 2002049645A JP 2000234735 A JP2000234735 A JP 2000234735A JP 2000234735 A JP2000234735 A JP 2000234735A JP 2002049645 A JP2002049645 A JP 2002049645A
- Authority
- JP
- Japan
- Prior art keywords
- hash value
- character string
- hash
- character
- storage device
- 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
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】
【課題】 ハッシュ値が偏るためシノニムが多くなり、
シノニム内からの検索に時間がかかるため、類似した文
字列の多いデータに対して検索速度が落ちる。 【解決手段】 記憶装置４はハッシュテーブル部４１
と、文字列記憶部４２とを備える。データ処理装置２は
ハッシュ値算出手段２１と、テーブル検索手段２２とを
備える。ハッシュ値算出手段２１は、入力装置１から与
えられた文字列の各文字の文字コードと係数記憶装置３
の数列の各要素との積を取り、その総和を求めてハッシ
ュ値とする。テーブル検索手段２２はハッシュ値算出手
段２１の求めたハッシュ値に対応するハッシュテーブル
部４１を探索し、与えられた文字列に該当するデータを
文字列記憶部４２から検索する。
シノニム内からの検索に時間がかかるため、類似した文
字列の多いデータに対して検索速度が落ちる。 【解決手段】 記憶装置４はハッシュテーブル部４１
と、文字列記憶部４２とを備える。データ処理装置２は
ハッシュ値算出手段２１と、テーブル検索手段２２とを
備える。ハッシュ値算出手段２１は、入力装置１から与
えられた文字列の各文字の文字コードと係数記憶装置３
の数列の各要素との積を取り、その総和を求めてハッシ
ュ値とする。テーブル検索手段２２はハッシュ値算出手
段２１の求めたハッシュ値に対応するハッシュテーブル
部４１を探索し、与えられた文字列に該当するデータを
文字列記憶部４２から検索する。
Description
【０００１】
【発明の属する技術分野】本発明はハッシュテーブルを
用いた検索方法に関し、特に、類似した文字列の多い、
特に固定長文字列のデータを高速に検索するためのハッ
シュテーブル用ハッシュ値算出方法に関する。
用いた検索方法に関し、特に、類似した文字列の多い、
特に固定長文字列のデータを高速に検索するためのハッ
シュテーブル用ハッシュ値算出方法に関する。
【０００２】
【従来の技術】従来、大量の文字列データを高速に検索
する手段としてハッシュテーブルが用いられている。
する手段としてハッシュテーブルが用いられている。
【０００３】特開平５ー１４３６４８号公報「情報登録
検索装置」には、ハッシュ値によりハッシュテーブルの
エントリを検索し、ハッシュ値が同じでキー名が異なる
場合にはキーテーブルにより通常のシノニムチェインを
作ってデータを登録し、またハッシュ値及びキー名が同
じ場合には対応するキーテーブルからデータテーブルに
より同名チェインを作ってデータを登録する技術が開示
されている。
検索装置」には、ハッシュ値によりハッシュテーブルの
エントリを検索し、ハッシュ値が同じでキー名が異なる
場合にはキーテーブルにより通常のシノニムチェインを
作ってデータを登録し、またハッシュ値及びキー名が同
じ場合には対応するキーテーブルからデータテーブルに
より同名チェインを作ってデータを登録する技術が開示
されている。
【０００４】
【発明が解決しようとする課題】従来技術には次のよう
な問題点があった。第１の問題点は、類似した文字列の
多いデータに対して検索速度が落ちやすい事である。そ
の理由は、ハッシュ値が偏りやすいためシノニムが多く
なり、シノニム内からの検索に時間がかかるためであ
る。第２の問題点は、類似した文字列の多いデータに対
してメモリ使用効率が落ちやすい事である。その理由
は、ハッシュ値が偏りやすく、使用されないエントリが
多くなりやすいためである。
な問題点があった。第１の問題点は、類似した文字列の
多いデータに対して検索速度が落ちやすい事である。そ
の理由は、ハッシュ値が偏りやすいためシノニムが多く
なり、シノニム内からの検索に時間がかかるためであ
る。第２の問題点は、類似した文字列の多いデータに対
してメモリ使用効率が落ちやすい事である。その理由
は、ハッシュ値が偏りやすく、使用されないエントリが
多くなりやすいためである。
【０００５】特開平５ー１４３６４８号公報「情報登録
検索装置」は、ハッシュ値の偏りを減らすことについて
は開示されていない。
検索装置」は、ハッシュ値の偏りを減らすことについて
は開示されていない。
【０００６】本発明は、以上の問題を解決するハッシュ
テーブル用ハッシュ値算出方法、装置を提供する。
テーブル用ハッシュ値算出方法、装置を提供する。
【０００７】
【課題を解決するための手段】本発明のハッシュ値算出
装置は、ハッシュ値算出のための係数をあらかじめ記憶
する係数記憶装置と、ハッシュテーブル部と文字列記憶
部を記憶する記憶装置と、ハッシュ値算出手段を有し、
前記ハッシュ値算出手段が入力装置から与えられた文字
列の各文字の文字コードを数値とした値と前記係数記憶
装置の数列の各要素との積を取り、前記積の総和を求め
てハッシュ値とするデータ処理装置とを有する。
装置は、ハッシュ値算出のための係数をあらかじめ記憶
する係数記憶装置と、ハッシュテーブル部と文字列記憶
部を記憶する記憶装置と、ハッシュ値算出手段を有し、
前記ハッシュ値算出手段が入力装置から与えられた文字
列の各文字の文字コードを数値とした値と前記係数記憶
装置の数列の各要素との積を取り、前記積の総和を求め
てハッシュ値とするデータ処理装置とを有する。
【０００８】本発明の検索装置は、ハッシュ値算出のた
めの係数をあらかじめ記憶する係数記憶装置と、ハッシ
ュテーブル部と、文字列記憶部を記憶する記憶装置と、
前記入力装置から与えられた文字列の各文字の文字コー
ドを数値とした値と前記係数記憶装置の数列の各要素と
の積を取り、前記積の総和を求めてハッシュ値とする前
記ハッシュ値算出手段と、前記ハッシュ値算出手段の求
めた前記ハッシュ値に対応する前記ハッシュテーブル部
を探索し、与えられた前記文字列を文字列記憶部から検
索するテーブル検索手段から構成されるデータ処理装置
とを有する。
めの係数をあらかじめ記憶する係数記憶装置と、ハッシ
ュテーブル部と、文字列記憶部を記憶する記憶装置と、
前記入力装置から与えられた文字列の各文字の文字コー
ドを数値とした値と前記係数記憶装置の数列の各要素と
の積を取り、前記積の総和を求めてハッシュ値とする前
記ハッシュ値算出手段と、前記ハッシュ値算出手段の求
めた前記ハッシュ値に対応する前記ハッシュテーブル部
を探索し、与えられた前記文字列を文字列記憶部から検
索するテーブル検索手段から構成されるデータ処理装置
とを有する。
【０００９】本発明のハッシュ値算出方法は、文字列か
らハッシュ値を算出する方法であって、ハッシュ値算出
のための複数の係数をあらかじめ計数テーブルに記憶す
る第一の処理と、与えられた文字列の各文字の文字コー
ドを数値とした値と前記計数テーブル内に格納されてい
る計数との積を取る第二の処理と、前記積の総和を求め
てハッシュ値とする第三の処理から構成される。
らハッシュ値を算出する方法であって、ハッシュ値算出
のための複数の係数をあらかじめ計数テーブルに記憶す
る第一の処理と、与えられた文字列の各文字の文字コー
ドを数値とした値と前記計数テーブル内に格納されてい
る計数との積を取る第二の処理と、前記積の総和を求め
てハッシュ値とする第三の処理から構成される。
【００１０】本発明の検索方法は、複数の文字からなる
文字列を文字列記憶部から検索する検索方法であって、
ハッシュ値算出のための複数の係数をあらかじめ計数テ
ーブルに記憶する第一の処理と、前記文字列のそれぞれ
の前記文字の文字コードを数値とした値と前記計数テー
ブル内に格納されている計数との積を取る第二の処理
と、前記積の総和を求めてハッシュ値とする第三の処理
と前記ハッシュ値に対応する前記ハッシュテーブル部を
探索し、前記文字列を前記文字列記憶部から検索する第
四の処理から構成される。
文字列を文字列記憶部から検索する検索方法であって、
ハッシュ値算出のための複数の係数をあらかじめ計数テ
ーブルに記憶する第一の処理と、前記文字列のそれぞれ
の前記文字の文字コードを数値とした値と前記計数テー
ブル内に格納されている計数との積を取る第二の処理
と、前記積の総和を求めてハッシュ値とする第三の処理
と前記ハッシュ値に対応する前記ハッシュテーブル部を
探索し、前記文字列を前記文字列記憶部から検索する第
四の処理から構成される。
【００１１】本発明第一の記録媒体は、本発明のハッシ
ュ値算出方法の各処理をコンピュータに実行させるプロ
グラムを記録した。
ュ値算出方法の各処理をコンピュータに実行させるプロ
グラムを記録した。
【００１２】本発明第二の記録媒体は、本発明の検索方
法の各処理をコンピュータに実行させるプログラムを記
録した。
法の各処理をコンピュータに実行させるプログラムを記
録した。
【００１３】
【発明の実施の形態】次に、本発明の実施の形態につい
て図面を参照して詳細に説明する。
て図面を参照して詳細に説明する。
【００１４】図１は、本発明実施の形態のハッシュ値算
出装置の構成を示すブロック図である。図１を参照する
と、本発明のハッシュ値算出装置は、入力装置１と、デ
ータ処理装置２と、係数記憶装置３と、文字列情報を記
憶する記憶装置４とから構成される。係数記憶装置３は
ハッシュ値算出のための係数をあらかじめ記憶してい
る。この計数は経験的に最適な数値を選択している。
出装置の構成を示すブロック図である。図１を参照する
と、本発明のハッシュ値算出装置は、入力装置１と、デ
ータ処理装置２と、係数記憶装置３と、文字列情報を記
憶する記憶装置４とから構成される。係数記憶装置３は
ハッシュ値算出のための係数をあらかじめ記憶してい
る。この計数は経験的に最適な数値を選択している。
【００１５】記憶装置４は、ハッシュテーブル部４１
と、文字列記憶部４２とを記憶している。データ処理装
置２はハッシュ値算出手段２１と、テーブル検索手段２
２とを備える。ハッシュ値算出手段２１は、入力装置１
から与えられた文字列の各文字の文字コードを数値とし
た値と係数記憶装置３の数列の各要素との積を取り、そ
の総和を求めてハッシュ値とする。テーブル検索手段２
２はハッシュ値算出手段２１の求めたハッシュ値に対応
するハッシュテーブル部４１を探索し、与えられた文字
列に該当するデータを文字列記憶部４２から検索する。
と、文字列記憶部４２とを記憶している。データ処理装
置２はハッシュ値算出手段２１と、テーブル検索手段２
２とを備える。ハッシュ値算出手段２１は、入力装置１
から与えられた文字列の各文字の文字コードを数値とし
た値と係数記憶装置３の数列の各要素との積を取り、そ
の総和を求めてハッシュ値とする。テーブル検索手段２
２はハッシュ値算出手段２１の求めたハッシュ値に対応
するハッシュテーブル部４１を探索し、与えられた文字
列に該当するデータを文字列記憶部４２から検索する。
【００１６】次に、図１及び図２を参照して本実施例の
動作について詳細に説明する。図２は、本発明第一の実
施の形態のハッシュ値算出方法を用いた検索方法の動作
を示すフローチャートである。以下の式によりハッシュ
値を求める。
動作について詳細に説明する。図２は、本発明第一の実
施の形態のハッシュ値算出方法を用いた検索方法の動作
を示すフローチャートである。以下の式によりハッシュ
値を求める。
【００１７】H(s[]) = s[1] × k[1] + s[2] × k[2] +
... + s[n] × k[n]。
... + s[n] × k[n]。
【００１８】H() : ハッシュ値。（十進数） s[i] : 入力装置１から与えられた文字列のi番目の文字
の文字コードを十進数にした値。
の文字コードを十進数にした値。
【００１９】k[] : 係数記憶装置３に記憶されている
係数数列のi番目の要素（十進数）。
係数数列のi番目の要素（十進数）。
【００２０】まず、入力装置１から与えられた入力文字
列は、ハッシュ値算出手段２１に供給される（ステップ
Ａ−１）。総和を計算するための返却値を０にする（ス
テップＡ−２）。ハッシュ値算出手段２１は、係数記憶
装置３の数列の各要素を求め（ステップＡ−４）と入力
装置１から与えられた文字列の各文字の文字コードを数
値とした値との積を取り（ステップＡ−５）、その総和
を求めてハッシュ値とする（ステップＡ−３）。このよ
うにする事で、与えられた文字列から以下の式に対応す
るハッシュ値が得られる。テーブル検索手段２２はハッ
シュ値算出手段２１の求めたハッシュ値に対応するハッ
シュテーブル部４１を探索し、入力装置１から与えられ
た文字列を文字列記憶部４２から検索する（ステップＡ
−６）。
列は、ハッシュ値算出手段２１に供給される（ステップ
Ａ−１）。総和を計算するための返却値を０にする（ス
テップＡ−２）。ハッシュ値算出手段２１は、係数記憶
装置３の数列の各要素を求め（ステップＡ−４）と入力
装置１から与えられた文字列の各文字の文字コードを数
値とした値との積を取り（ステップＡ−５）、その総和
を求めてハッシュ値とする（ステップＡ−３）。このよ
うにする事で、与えられた文字列から以下の式に対応す
るハッシュ値が得られる。テーブル検索手段２２はハッ
シュ値算出手段２１の求めたハッシュ値に対応するハッ
シュテーブル部４１を探索し、入力装置１から与えられ
た文字列を文字列記憶部４２から検索する（ステップＡ
−６）。
【００２１】次に、図３と４に示す具体例を用いて本実
施例の動作を説明する。図３は、本発明第一の実施の形
態のハッシュ値算出方法において、実際の文字列とハッ
シュテーブルの内容を示す図である。図４は、本発明第
一の実施の形態のハッシュ値算出方法において、実際の
文字列とハッシュ値とインデックスの内容を示す図であ
る。
施例の動作を説明する。図３は、本発明第一の実施の形
態のハッシュ値算出方法において、実際の文字列とハッ
シュテーブルの内容を示す図である。図４は、本発明第
一の実施の形態のハッシュ値算出方法において、実際の
文字列とハッシュ値とインデックスの内容を示す図であ
る。
【００２２】図３に示すように、例えば、係数記憶装置
３には以下の数列が記憶されている。{ 31, 117, 111,
43, 3, 25, 17, 101, 59, 125, 49, 7, 97,
19,45, 23, 57, 63, 13, 41, 73, 55, 85,
35, 11, 115, 103, 1,29, 5, 91, 79 }。
３には以下の数列が記憶されている。{ 31, 117, 111,
43, 3, 25, 17, 101, 59, 125, 49, 7, 97,
19,45, 23, 57, 63, 13, 41, 73, 55, 85,
35, 11, 115, 103, 1,29, 5, 91, 79 }。
【００２３】入力文字列として、"TABLE001△△△△△
△△△△△△△△△△△△△△△△△△△"が与えられ
たする。ハッシュ値算出手段２１は各文字の文字コード
を数値とした値と係数記憶装置３の係数との積を順次計
算し、その総和を算出する（Ａ３及びＡ４）。この計算
を文字列の長さ分繰り返し（Ａ２）、ハッシュ値 68935
を得る。計算方法は、( 'T' × 31 + 'A' × 117 + 'B'
× 111 + ... + '△'× 79 = 68935 )である。ここ
で、 'A' は、ＡＳＣＩＩコードで４１（１６進数）で
あるから、十進数で６５である。 'B' は、ＡＳＣＩＩ
コードで４２（１６進数）であるから、十進数で６６で
ある。'△'ＡＳＣＩＩコードで２０（１６進数）である
から、十進数で３２である。
△△△△△△△△△△△△△△△△△△△"が与えられ
たする。ハッシュ値算出手段２１は各文字の文字コード
を数値とした値と係数記憶装置３の係数との積を順次計
算し、その総和を算出する（Ａ３及びＡ４）。この計算
を文字列の長さ分繰り返し（Ａ２）、ハッシュ値 68935
を得る。計算方法は、( 'T' × 31 + 'A' × 117 + 'B'
× 111 + ... + '△'× 79 = 68935 )である。ここ
で、 'A' は、ＡＳＣＩＩコードで４１（１６進数）で
あるから、十進数で６５である。 'B' は、ＡＳＣＩＩ
コードで４２（１６進数）であるから、十進数で６６で
ある。'△'ＡＳＣＩＩコードで２０（１６進数）である
から、十進数で３２である。
【００２４】テーブル検索手段２２はハッシュ値をハッ
シュテーブルサイズ（例えば128、十進数）で割った余
りを計算し、ハッシュテーブルのインデックス値 71
（十進数）を得る。テーブル検索手段２２はハッシュテ
ーブル部４１のインデックス値71 内を探索し、入力さ
れた文字列を検索する。同様に以下の様な文字列が与え
られた場合、ハッシュ値算出手段２１はそれぞれの文字
列についてハッシュ値を求め、テーブル検索手段２２は
それぞれのハッシュ値に対応するハッシュテーブルのイ
ンデックスを探索する。
シュテーブルサイズ（例えば128、十進数）で割った余
りを計算し、ハッシュテーブルのインデックス値 71
（十進数）を得る。テーブル検索手段２２はハッシュテ
ーブル部４１のインデックス値71 内を探索し、入力さ
れた文字列を検索する。同様に以下の様な文字列が与え
られた場合、ハッシュ値算出手段２１はそれぞれの文字
列についてハッシュ値を求め、テーブル検索手段２２は
それぞれのハッシュ値に対応するハッシュテーブルのイ
ンデックスを探索する。
【００２５】次に、本発明第二の実施例について図面を
参照して詳細に説明する。図５は、本発明第二の実施の
形態のハッシュ値算出方法を用いた検索方法の動作を示
すフローチャートである。図５を参照すると、本実施例
は、ハッシュ値算出手段２１が、図２に示された実施例
におけるハッシュ値算出手段２１に対し、係数記憶装置
３の数列の長さを超える文字列に対してハッシュ値を求
める機能を有する点で異なる。
参照して詳細に説明する。図５は、本発明第二の実施の
形態のハッシュ値算出方法を用いた検索方法の動作を示
すフローチャートである。図５を参照すると、本実施例
は、ハッシュ値算出手段２１が、図２に示された実施例
におけるハッシュ値算出手段２１に対し、係数記憶装置
３の数列の長さを超える文字列に対してハッシュ値を求
める機能を有する点で異なる。
【００２６】まず、入力装置１から与えられた入力文字
列は、ハッシュ値算出手段２１に供給される（ステップ
Ｂ−１）。総和を計算するための返却値を０にする（ス
テップＢ−２）。ハッシュ値算出手段２１は、係数記憶
装置３の数列の各要素を求め（ステップＢ−５）と入力
装置１から与えられた文字列の各文字の文字コードを数
値とした値との積を取る（ステップＢ−６）。ハッシュ
値算出手段２１は、係数記憶装置３の最後の係数を使う
と、次からはもう一度最初の係数から使い始める（図４
のＢ３及びＢ７）。このようにする事で可変長文字列に
対してもハッシュ値を得られるようにしている。返却値
の総和を求めてハッシュ値とする（ステップＢ−４）。
このようにする事で、与えられた文字列から以下の式に
対応するハッシュ値が得られる。テーブル検索手段２２
はハッシュ値算出手段２１の求めたハッシュ値に対応す
るハッシュテーブル部４１を探索し、入力装置１から与
えられた文字列を文字列記憶部４２から検索する（ステ
ップＢ−８）。
列は、ハッシュ値算出手段２１に供給される（ステップ
Ｂ−１）。総和を計算するための返却値を０にする（ス
テップＢ−２）。ハッシュ値算出手段２１は、係数記憶
装置３の数列の各要素を求め（ステップＢ−５）と入力
装置１から与えられた文字列の各文字の文字コードを数
値とした値との積を取る（ステップＢ−６）。ハッシュ
値算出手段２１は、係数記憶装置３の最後の係数を使う
と、次からはもう一度最初の係数から使い始める（図４
のＢ３及びＢ７）。このようにする事で可変長文字列に
対してもハッシュ値を得られるようにしている。返却値
の総和を求めてハッシュ値とする（ステップＢ−４）。
このようにする事で、与えられた文字列から以下の式に
対応するハッシュ値が得られる。テーブル検索手段２２
はハッシュ値算出手段２１の求めたハッシュ値に対応す
るハッシュテーブル部４１を探索し、入力装置１から与
えられた文字列を文字列記憶部４２から検索する（ステ
ップＢ−８）。
【００２７】次に、具体例について図６を用いて説明す
る。図６は、本発明第二の実施の形態のハッシュ値算出
方法において、実際の文字列とハッシュ値とインデック
スの内容を示す図である。
る。図６は、本発明第二の実施の形態のハッシュ値算出
方法において、実際の文字列とハッシュ値とインデック
スの内容を示す図である。
【００２８】図３の例では、"TABLE000000000000000000
0000000001"という文字列は係数記憶装置３に記憶され
ている係数の数よりも文字列の方が長いため処理できな
い。図５のシステムは係数記憶装置３の全（すべ）ての
係数を使った後は、最初の係数から使い始める。このた
め、最後の文字"1"を処理する時は、数列の最初の数字
31 を使用する。計算方法は、( 'T' × 31 + 'A' × 11
7 + 'B' × 111 + ... + '1' × 31 = 89314 )である。
この方法によりハッシュ値及びインデックス値を求める
と図６の様になる。
0000000001"という文字列は係数記憶装置３に記憶され
ている係数の数よりも文字列の方が長いため処理できな
い。図５のシステムは係数記憶装置３の全（すべ）ての
係数を使った後は、最初の係数から使い始める。このた
め、最後の文字"1"を処理する時は、数列の最初の数字
31 を使用する。計算方法は、( 'T' × 31 + 'A' × 11
7 + 'B' × 111 + ... + '1' × 31 = 89314 )である。
この方法によりハッシュ値及びインデックス値を求める
と図６の様になる。
【００２９】上述の各ステップは、コンピュータ６０と
そのコンピュータ６０上で走行するのプログラムを用い
た処理により実現することが可能である。図７は、本発
明実施の形態のハッシュ値算出方法をコンピュータ６０
に実行させるプログラムを記録した記録媒体６１とコン
ピュータ６０を示す図である。
そのコンピュータ６０上で走行するのプログラムを用い
た処理により実現することが可能である。図７は、本発
明実施の形態のハッシュ値算出方法をコンピュータ６０
に実行させるプログラムを記録した記録媒体６１とコン
ピュータ６０を示す図である。
【００３０】
【発明の効果】本発明の効果は、類似した文字列の多い
データに対して検索効率・メモリ使用効率の良いハッシ
ュテーブルを作成する事により、検索速度、及びメモリ
使用率を向上させられる事である。その理由は、類似し
た文字列の多いデータに対しても偏りの少ないハッシュ
値を得られるためである。
データに対して検索効率・メモリ使用効率の良いハッシ
ュテーブルを作成する事により、検索速度、及びメモリ
使用率を向上させられる事である。その理由は、類似し
た文字列の多いデータに対しても偏りの少ないハッシュ
値を得られるためである。
【図１】本発明実施の形態のハッシュ値算出装置の構成
を示すブロック図である。
を示すブロック図である。
【図２】本発明第一の実施の形態のハッシュ値算出方法
を用いた検索方法の動作を示すフローチャートである。
を用いた検索方法の動作を示すフローチャートである。
【図３】本発明第一の実施の形態のハッシュ値算出方法
において、実際の文字列とハッシュテーブルの内容を示
す図である。
において、実際の文字列とハッシュテーブルの内容を示
す図である。
【図４】本発明第一の実施の形態のハッシュ値算出方法
において、実際の文字列とハッシュ値とインデックスの
内容を示す図である。
において、実際の文字列とハッシュ値とインデックスの
内容を示す図である。
【図５】本発明第二の実施の形態のハッシュ値算出方法
を用いた検索方法の動作を示すフローチャートである。
を用いた検索方法の動作を示すフローチャートである。
【図６】本発明第二の実施の形態のハッシュ値算出方法
において、実際の文字列とハッシュ値とインデックスの
内容を示す図である。
において、実際の文字列とハッシュ値とインデックスの
内容を示す図である。
【図７】本発明実施の形態のハッシュ値算出方法をコン
ピュータ６０に実行させるプログラムを記録した記録媒
体６１とコンピュータ６０を示す図である。
ピュータ６０に実行させるプログラムを記録した記録媒
体６１とコンピュータ６０を示す図である。
１ 入力装置 ２ データ処理装置 ３ 係数記憶装置 ４ 記憶装置 ２１ ハッシュ値算出手段 ２２ テーブル検索手段 ４１ ハッシュテーブル部 ４２ 文字列記憶部 ６０ コンピュータ ６１ 記録媒体
Claims (6)
- 【請求項１】 ハッシュ値算出のための係数をあらかじ
め記憶する係数記憶装置と、ハッシュテーブル部と文字
列記憶部を記憶する記憶装置と、ハッシュ値算出手段を
有し、前記ハッシュ値算出手段が入力装置から与えられ
た文字列の各文字の文字コードを数値とした値と前記係
数記憶装置の数列の各要素との積を取り、前記積の総和
を求めてハッシュ値とするデータ処理装置とを有するこ
とを特徴とするハッシュ値算出装置。 - 【請求項２】 ハッシュ値算出のための係数をあらかじ
め記憶する係数記憶装置と、ハッシュテーブル部と、文
字列記憶部を記憶する記憶装置と、前記入力装置から与
えられた文字列の各文字の文字コードを数値とした値と
前記係数記憶装置の数列の各要素との積を取り、前記積
の総和を求めてハッシュ値とする前記ハッシュ値算出手
段と、前記ハッシュ値算出手段の求めた前記ハッシュ値
に対応する前記ハッシュテーブル部を探索し、与えられ
た前記文字列を文字列記憶部から検索するテーブル検索
手段から構成されるデータ処理装置とを有することを特
徴とする検索装置。 - 【請求項３】 文字列からハッシュ値を算出する方法で
あって、ハッシュ値算出のための複数の係数をあらかじ
め計数テーブルに記憶する第一の処理と、与えられた文
字列の各文字の文字コードを数値とした値と前記計数テ
ーブル内に格納されている計数との積を取る第二の処理
と、前記積の総和を求めてハッシュ値とする第三の処理
から構成されることを特徴とするハッシュ値算出方法。 - 【請求項４】 複数の文字からなる文字列を文字列記憶
部から検索する検索方法であって、 ハッシュ値算出のための複数の係数をあらかじめ計数テ
ーブルに記憶する第一の処理と、前記文字列のそれぞれ
の前記文字の文字コードを数値とした値と前記計数テー
ブル内に格納されている計数との積を取る第二の処理
と、前記積の総和を求めてハッシュ値とする第三の処理
と前記ハッシュ値に対応する前記ハッシュテーブル部を
探索し、前記文字列を前記文字列記憶部から検索する第
四の処理から構成されることを特徴とする検索方法。 - 【請求項５】 請求項３記載のハッシュ値算出方法の各
処理をコンピュータに実行させるプログラムを記録した
記録媒体。 - 【請求項６】 請求項４記載の検索方法の各処理をコン
ピュータに実行させるプログラムを記録した記録媒体。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000234735A JP2002049645A (ja) | 2000-08-02 | 2000-08-02 | ハッシュ値算出方法、ハッシュ値算出装置、検索方法、検索装置、記録媒体 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000234735A JP2002049645A (ja) | 2000-08-02 | 2000-08-02 | ハッシュ値算出方法、ハッシュ値算出装置、検索方法、検索装置、記録媒体 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JP2002049645A true JP2002049645A (ja) | 2002-02-15 |
Family
ID=18727069
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2000234735A Pending JP2002049645A (ja) | 2000-08-02 | 2000-08-02 | ハッシュ値算出方法、ハッシュ値算出装置、検索方法、検索装置、記録媒体 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP2002049645A (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2008283703A (ja) * | 2002-09-19 | 2008-11-20 | Research In Motion Ltd | 通信デバイス上で連絡情報にアクセスするシステムおよび方法 |
| US8095526B2 (en) | 2003-12-02 | 2012-01-10 | Nec Corporation | Efficient retrieval of variable-length character string data |
| JP4944266B1 (ja) * | 2011-06-08 | 2012-05-30 | 義尚 神山 | ２分割文字検索ソフトウェア |
-
2000
- 2000-08-02 JP JP2000234735A patent/JP2002049645A/ja active Pending
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2008283703A (ja) * | 2002-09-19 | 2008-11-20 | Research In Motion Ltd | 通信デバイス上で連絡情報にアクセスするシステムおよび方法 |
| US8095526B2 (en) | 2003-12-02 | 2012-01-10 | Nec Corporation | Efficient retrieval of variable-length character string data |
| US8200646B2 (en) | 2003-12-02 | 2012-06-12 | Nec Corporation | Efficient retrieval of variable-length character string data |
| JP4944266B1 (ja) * | 2011-06-08 | 2012-05-30 | 義尚 神山 | ２分割文字検索ソフトウェア |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3554459B2 (ja) | テキストデータ登録検索方法 | |
| JPH05189490A (ja) | 関数結果をセーブし検索する方法と装置 | |
| CN109828789A (zh) | 加速压缩方法以及加速压缩装置 | |
| JP2002049645A (ja) | ハッシュ値算出方法、ハッシュ値算出装置、検索方法、検索装置、記録媒体 | |
| JP3360693B2 (ja) | 顧客情報検索方式 | |
| CN109802685A (zh) | 加速压缩方法以及加速压缩装置 | |
| CN113495901B (zh) | 一种面向可变长数据块的快速检索方法 | |
| JP3558267B2 (ja) | 文書検索装置 | |
| JP3534471B2 (ja) | マージソート方法及びマージソート装置 | |
| CN109802686A (zh) | 加速压缩方法以及加速压缩装置 | |
| CN109857463A (zh) | 加速压缩方法以及加速压缩装置 | |
| JPH0773187A (ja) | 検索システム | |
| JPH09245045A (ja) | 鍵検索方法および装置 | |
| JPS642970B2 (ja) | ||
| JP2004206631A (ja) | 検索チューニング方法および情報検索システム | |
| JPS61141036A (ja) | デ−タ検索方式 | |
| JP3040114B2 (ja) | レコード検索装置 | |
| JP3564952B2 (ja) | 高速文書登録検索方法および装置 | |
| JPS6373422A (ja) | 情報検索装置 | |
| JPH06162096A (ja) | レコード検索方法 | |
| JPH01259418A (ja) | 文字列検索装置 | |
| JPH07319888A (ja) | 索引検索方式 | |
| JPH0546663A (ja) | キーワード検索方式 | |
| JP3224159B2 (ja) | エキスパートシステム | |
| JPH04205173A (ja) | 情報検索システム |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20040727 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20041124 |