【手続補正書】
【提出日】平成17年1月18日(2005.1.18)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】発明の名称
【補正方法】変更
【補正の内容】
【発明の名称】文字列に対するハッシュ値の計算方法およびその方法を実現するプログラムを記録した機械可読な記録媒体、文字列に対するハッシュ値の計算装置ならびに情報管理装置
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ＣＰＵとメモリを備えるコンピュータを用いた、処理対象の文字列に対するハッシュ値の計算方法であって、
１つ以上の特定の文字列それぞれを、より短い長さの変換後文字列と一意に対応付けるための機械可読なテーブルを準備するステップと、
前記ＣＰＵを用いて、処理対象文字列中に出現する文字列を、前記テーブルを参照して対応の変換後文字列に変換するステップと、
前記ＣＰＵを用いて、変換後文字列を含む前記処理対象文字列に基づいてハッシュ値を計算するステップとを含む、文字列に対するハッシュ値の計算方法。
【請求項２】
前記テーブルを準備する前記ステップは、
過去に出現した処理対象文字列を前記メモリに準備するステップと、
前記過去に出現した処理対象文字列の部分文字列の各々の、出現回数と文字列長とを、前記ＣＰＵを用いて集計するステップと、
前記ＣＰＵを用いて、前記集計された出現回数と文字列長とに基づき、前記過去に出現した処理対象文字列の部分文字列のうち、所定文字に置換したときに前記過去に出現した処理対象文字列を最も効率的に圧縮することが可能な部分文字列を選択し、選択された前記部分文字列を前記特定の文字列として前記テーブルに追加するステップとを含む、請求項１に記載の、文字列に対するハッシュ値の計算方法。
【請求項３】
前記テーブルを準備する前記ステップは、
前記ＣＰＵを用いて、前記選択された部分文字列を考慮して前記出現回数を再計算し、さらに、前記追加するステップを所定の条件が成立するまで繰返すステップを含む、請求項２に記載の、文字列に対するハッシュ値の計算方法。
【請求項４】
前記変換後文字列を含む処理対象文字列は、前記テーブルの当該変換後文字列に対応の文字列を用いて変換前の処理対象文字列に復元されることを特徴とする、請求項１に記載の、文字列に対するハッシュ値の計算方法。
【請求項５】
変換前の処理対象文字列に使用される文字セットに含まれない文字を、前記変換後文字列の文字として用いることを特徴とする、請求項１に記載の、文字列に対するハッシュ値の計算方法。
【請求項６】
前記テーブルは、複数のユーザに共通に使用される共通テーブルと、ユーザ毎に使用されるユーザ毎テーブルを含む、請求項１に記載の、文字列に対するハッシュ値の計算方法。
【請求項７】
前記ユーザ毎テーブルの前記変換後文字列には、前記共通テーブルの前記変換後文字列に用いられない文字が含まれる、請求項６に記載の、文字列に対するハッシュ値の計算方法。
【請求項８】
前記共通テーブルの前記変換後文字列それぞれは１バイトの異なる文字コードを示し、かつ前記１バイトの異なる文字コードはＡＳＣＩＩコードの所定のコード群のうちのいずれかのコードを示し、
前記ユーザ毎テーブルの前記変換後文字列のそれぞれは複数バイトの異なる文字コードを示し、かつ前記複数バイトのうち先頭の１バイトはＡＳＣＩＩコード中の前記所定のコード群を除いた所定コードを示す、請求項７に記載の、文字列に対するハッシュ値の計算方法。
【請求項９】
変換前の前記処理対象文字列は、ＵＲＬを示す文字列である、請求項１に記載の、文字列に対するハッシュ値の計算方法。
【請求項１０】
請求項１に記載の、文字列に対するハッシュ値の計算方法により計算された前記ハッシュ値を用いて情報を管理する情報管理装置であって、
前記処理対象文字列を用いて参照されるファイルを記憶する記憶部と、
ハッシュ領域と、
計算された前記ハッシュ値が指示する前記ハッシュ領域のアドレスに、前記処理対象文字列を用いて参照される前記ファイルの前記記憶部における記憶アドレスと、変換後の前記処理対象文字列とを対応付けて格納する手段とを備える、情報管理装置。
【請求項１１】
請求項１に記載の、文字列に対するハッシュ値の計算方法により計算された前記ハッシュ値に従う前記ハッシュ領域のアドレスをアクセスし、当該アドレスに格納された前記変換後の処理対象文字列と対応付けて格納された前記記憶アドレスを読出す手段と、
前記読出された前記記憶アドレスに基づき前記記憶部を検索する手段とをさらに備える、請求項１０に記載の情報管理装置。
【請求項１２】
変換前の前記処理対象文字列はＵＲＬを示す文字列である、請求項１０に記載の情報管理装置。
【請求項１３】
ＣＰＵとメモリを備えるコンピュータを用いて、処理対象の文字列に対するハッシュ値の計算方法を実現するプログラムを記録した機械可読な記録媒体であって、前記プログラムは、
１つ以上の特定の文字列それぞれを、より短い長さの変換後文字列と一意に対応付けるための機械可読なテーブルを準備するステップと、
前記ＣＰＵを用いて、処理対象文字列中に出現する文字列を、前記テーブルを参照して対応の変換後文字列に変換するステップと、
前記ＣＰＵを用いて、変換後文字列を含む前記処理対象文字列に基づいてハッシュ値を計算するステップとを含む、文字列に対するハッシュ値の計算方法を実現するプログラムを記録した機械可読な記録媒体。
【請求項１４】
前記テーブルを準備する前記ステップは、
過去に出現した処理対象文字列を前記メモリに準備するステップと、
前記過去に出現した処理対象文字列の部分文字列の各々の、出現回数と文字列長とを、前記ＣＰＵを用いて集計するステップと、
前記ＣＰＵを用いて、前記集計された出現回数と文字列長とに基づき、前記過去に出現した処理対象文字列の部分文字列のうち、所定文字に置換したときに前記過去に出現した処理対象文字列を最も効率的に圧縮することが可能な部分文字列を選択し、選択された前記部分文字列を前記特定の文字列として前記テーブルに追加するステップとを含む、請求項１３に記載の、文字列に対するハッシュ値の計算方法を実現するプログラムを記録した機械可読な記録媒体。
【請求項１５】
処理対象の文字列に対するハッシュ値の計算装置であって、
前記計算装置はＣＰＵとメモリとを含み、
１つ以上の特定の文字列それぞれを、より短い長さの変換後文字列と一意に対応付けるための機械可読なテーブルを準備する手段と、
前記ＣＰＵを用いて、処理対象文字列中に出現する文字列を、前記テーブルを参照して対応の変換後文字列に変換する手段と、
前記ＣＰＵを用いて、変換後文字列を含む前記処理対象文字列に基づいてハッシュ値を計算する手段とを含む、文字列に対するハッシュ値の計算装置。
【請求項１６】
前記テーブルを準備する手段は、
過去に出現した処理対象文字列を前記メモリに準備する手段と、
前記ＣＰＵを用いて、前記過去に出現した処理対象文字列の部分文字列の各々の、出現回数と文字列長とを、集計する手段と、
前記ＣＰＵを用いて、前記集計された出現回数と文字列長とに基づき、前記過去に出現した処理対象文字列の部分文字列のうち、所定文字に置換したときに前記過去に出現した処理対象文字列を最も効率的に圧縮することが可能な部分文字列を選択し、選択された前記部分文字列を前記特定の文字列として前記テーブルに追加する手段とを含む、請求項１５に記載の、文字列に対するハッシュ値の計算装置。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２３
【補正方法】変更
【補正の内容】
【００２３】
それゆえにこの発明の目的は、ＵＲＬのように、文字の並びの出現頻度に偏りがあるような文字列に対して効率的にハッシングが行なえる、文字列に対するハッシュ値の計算方法およびその方法を実現するプログラムを記録した機械可読な記録媒体、文字列に対するハッシュ値の計算装置ならびに情報管理装置を提供することである。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００２４
【補正方法】変更
【補正の内容】
【００２４】
【課題を解決するための手段】
この発明のある局面に従うと、方法は、偏った頻度で文字の並びが出現する処理対象の文字列に対するハッシュ値の計算方法であって、特定の文字列を、より短い長さの変換後文字列と一意に関連付けるための機械可読なテーブルを準備するステップと、コンピュータを用いて、処理対象文字列中に出現する文字列を、テーブルを参照して対応の変換後文字列に変換するステップと、コンピュータを用いて、変換後文字列を含む処理対象文字列に基づいてハッシュ値を計算するステップとを含む。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】変更
【補正の内容】
【００２６】
好ましくは、テーブルを準備するステップは、過去に出現した処理対象文字列をコンピュータ中に準備するステップと、過去に出現した処理対象文字列の部分文字列の各々の、出現回数と文字列長とを、コンピュータを用いて集計するステップと、集計された出現回数と文字列長とに基づき、過去に出現した処理対象文字列の部分文字列のうち、所定文字に置換したときに過去に出現した処理対象文字列を最も効率的に圧縮することが可能な部分文字列を選択しテーブルに追加するステップと、選択された部分文字列を考慮して出現回数を再計算し、さらに、追加するステップを所定の条件が成立するまで繰返すステップとを含む。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００２８
【補正方法】変更
【補正の内容】
【００２８】
この発明の他の局面に従うと、記録媒体は、偏った頻度で文字の並びが出現する処理対象の文字列に対するハッシュ値の計算方法を実現するプログラムを記録した機械可読な記録媒体であって、プログラムは、特定の文字列を、より短い長さの変換後文字列と一意に関連付けるための機械可読なテーブルを準備するステップと、処理対象文字列中に出現する文字列を、テーブルを参照して対応の変換後文字列に変換するステップと、変換後文字列を含む処理対象文字列に基づいてハッシュ値を計算するステップとを含む。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００３０
【補正方法】変更
【補正の内容】
【００３０】
好ましくは、テーブルを準備するステップは、過去に出現した処理対象文字列を準備するステップと、過去に出現した処理対象文字列の部分文字列の各々の、出現回数と文字列長とを集計するステップと、集計された出現回数と文字列長とに基づき、過去に出現した処理対象文字列の部分文字列のうち、所定文字に置換したときに過去に出現した処理対象文字列を最も効率的に圧縮することが可能な部分文字列を選択しテーブルに追加するステップと、選択された部分文字列を考慮して出現回数を再計算し、さらに、追加するステップを所定の条件が成立するまで繰返すステップとを含む。