特許
J-GLOBAL ID：200903087345633050
配列探索システムおよび探索プログラム
発明者：
,
,
出願人/特許権者：
代理人 (1件)：
吉田 聡
公報種別：公開公報
出願番号（国際出願番号）：特願2003-431970
公開番号（公開出願番号）：特開2005-190248
出願日： 2003年12月26日
公開日（公表日）： 2005年07月14日
要約：
【課題】 配列の類似部分を探索するときの時間計算量および空間計算量を改善する。 【解決手段】 配列探索システムは、配列を構成する部分列中、第1の配列中の各要素から延びる部分列の出現位置を格納する第1のテーブルと、第2の配列中の各要素から延びる部分列に対応する、第1のテーブル中の、第1の配列の部分列に関する出現位置を取得する出現位置取得手段と、第2の配列の部分列および第1の配列の部分列に関する出現位置に基づく構造体を、それぞれの出現位置の間の差異にしたがってヒープに投入し、形成されたヒープの根に、差異が同一の構造体が所定回数表れるときに、構造体を取り出して、その情報を記憶装置に記憶するヒープ形成手段と、取り出された、差異が同一の構造体の第1の配列の部分列および第2の配列の部分列に関する出現位置から、所定の長さ以上、第1の配列および第2の配列とが一致する位置を特定する類似位置特定手段とを備える。【選択図】 図1
請求項（抜粋）：
第1の配列から、第2の配列と類似する位置を探索する配列探索システムであって、
配列を構成する所定の長さの部分列中、第1の配列中の各要素から延びる当該所定の長さの部分列の出現位置を格納する第1のテーブルと、
第2の配列中の各要素から延びる当該所定の長さの部分列に対応する、前記第1のテーブル中の、前記第1の配列の部分列に関する出現位置を取得する出現位置取得手段と、
前記第2の配列の部分列に関する出現位置および第1の配列の部分列に関する出現位置に基づく構造体を、前記第2の配列の部分列に関する出現位置と、第1の配列の部分列に関する出現位置との間の差異にしたがってヒープに投入することにより、ヒープを形成するヒープ形成手段であって、前記形成されたヒープの根に、前記差異が同一の構造体が所定回数表れるときに、当該構造体を取り出して、その情報を記憶装置に記憶するヒープ形成手段と、
前記取り出された、差異が同一の構造体の第1の配列の部分列に関する出現位置と、前記第2の配列の部分列に関する出現位置とから、少なくとも所定の長さ以上、第1の配列および第2の配列とが一致する位置を特定する類似位置特定手段とを備えたことを特徴とする配列探索システム。
IPC (1件)：
FI (1件)：
引用特許：
前のページに戻る
