Pat
J-GLOBAL ID：200903087345633050
配列探索システムおよび探索プログラム
Inventor：
,
,
Applicant, Patent owner：
Agent (1)：
吉田 聡
Gazette classification：公開公報
Application number (International application number)：2003431970
Publication number (International publication number)：2005190248
Application date： Dec. 26, 2003
Publication date： Jul. 14, 2005
Summary：
【課題】 配列の類似部分を探索するときの時間計算量および空間計算量を改善する。 【解決手段】 配列探索システムは、配列を構成する部分列中、第1の配列中の各要素から延びる部分列の出現位置を格納する第1のテーブルと、第2の配列中の各要素から延びる部分列に対応する、第1のテーブル中の、第1の配列の部分列に関する出現位置を取得する出現位置取得手段と、第2の配列の部分列および第1の配列の部分列に関する出現位置に基づく構造体を、それぞれの出現位置の間の差異にしたがってヒープに投入し、形成されたヒープの根に、差異が同一の構造体が所定回数表れるときに、構造体を取り出して、その情報を記憶装置に記憶するヒープ形成手段と、取り出された、差異が同一の構造体の第1の配列の部分列および第2の配列の部分列に関する出現位置から、所定の長さ以上、第1の配列および第2の配列とが一致する位置を特定する類似位置特定手段とを備える。【選択図】 図1
Claim (excerpt)：
第1の配列から、第2の配列と類似する位置を探索する配列探索システムであって、
配列を構成する所定の長さの部分列中、第1の配列中の各要素から延びる当該所定の長さの部分列の出現位置を格納する第1のテーブルと、
第2の配列中の各要素から延びる当該所定の長さの部分列に対応する、前記第1のテーブル中の、前記第1の配列の部分列に関する出現位置を取得する出現位置取得手段と、
前記第2の配列の部分列に関する出現位置および第1の配列の部分列に関する出現位置に基づく構造体を、前記第2の配列の部分列に関する出現位置と、第1の配列の部分列に関する出現位置との間の差異にしたがってヒープに投入することにより、ヒープを形成するヒープ形成手段であって、前記形成されたヒープの根に、前記差異が同一の構造体が所定回数表れるときに、当該構造体を取り出して、その情報を記憶装置に記憶するヒープ形成手段と、
前記取り出された、差異が同一の構造体の第1の配列の部分列に関する出現位置と、前記第2の配列の部分列に関する出現位置とから、少なくとも所定の長さ以上、第1の配列および第2の配列とが一致する位置を特定する類似位置特定手段とを備えたことを特徴とする配列探索システム。
IPC (1)：
FI (1)：
Patent cited by the Patent：
Return to Previous Page
