(57)【要約】【課題】索引サイズが圧縮され、記号列データの検索に必要なメモリ使用量を減らすことができるようにする。【解決手段】マップマッチング部４４によって、移動体の経度緯度情報の時系列と、道路地図上の各道路の道路ＩＤとに基づいて、移動体の経度緯度情報の時系列を、移動体の移動履歴を表す道路ＩＤの列である記号列データに変換する。索引圧縮部５０によって、移動体の移動履歴を表す道路ＩＤの列における道路ＩＤの遷移が、隣接する道路ＩＤに限定されることを利用した符号化方法を用いて、記号列データの圧縮索引を生成する。データ検索部５４によって、記号列データに対して、クエリとして与えられた道路ＩＤの列である記号列データと一致する部分を検索する。【選択図】図５
2018013924.tif 000002
【特許請求の範囲】
【請求項１】
移動体の経度緯度情報の時系列と、道路地図上の各道路の道路ＩＤとに基づいて、移動体の経度緯度情報の時系列を、移動体の移動履歴を表す道路ＩＤの列である記号列データに変換するマップマッチング部と、
移動体の移動履歴を表す道路ＩＤの列における道路ＩＤの遷移が、隣接する道路ＩＤに限定されることを利用した符号化方法を用いて圧縮された、前記記号列データに対して、クエリとして与えられた道路ＩＤの列である記号列データと一致する部分を検索するデータ検索部と、
を含む移動体経路検索装置。
【請求項２】
連結部を更に含み、
前記マップマッチング部は、複数の移動体の経度緯度情報の時系列の各々について、前記記号列データに変換し、
前記連結部は、前記マップマッチング部により変換された複数の前記記号列データを連結することにより、一つの記号列データを生成し、
前記データ検索部は、前記連結部によって生成された前記一つの記号列データに対して、前記クエリとして与えられた道路ＩＤの列である記号列データと一致する部分を検索する請求項１記載の移動体経路検索装置。
【請求項３】
与えられた記号列をバローズ・ホィーラー変換した記号列を出力するＢＷ変換部と、
前記与えられた記号列に含まれる記号間の遷移関係を表すグラフ構造を生成するグラフ構造解析部と、
前記グラフ構造解析部によって生成された前記グラフ構造を用いて、前記ＢＷ変換部によって出力された前記バローズ・ホィーラー変換した記号列を、記号の種類数を削減した記号列に変換する符号化部と、
前記符号化部によって変換された前記記号列を表す圧縮索引を生成する索引化部と、
前記グラフ構造解析部によって生成された前記グラフ構造、及び前記索引化部によって生成された前記圧縮索引に基づいて、クエリとして与えられた記号列に対応する、前記ＢＷ変換部によって出力された前記バローズ・ホィーラー変換した記号列の接尾辞の範囲を計算するデータ検索部と、
を含む記号列検索装置。
【請求項４】
前記グラフ構造解析部は、前記グラフ構造として、前記与えられた記号列に含まれる各記号を頂点とし、記号間の遷移関係を辺として表現する有向グラフを生成し、
前記符号化部は、前記有向グラフを用いて、現在の頂点及び次の記号を表す符号が既知の場合に、次の頂点が一意的に確定することを利用した符号化方法により、前記バローズ・ホィーラー変換した記号列を、記号の種類数を削減した記号列に変換する請求項３記載の記号列検索装置。
【請求項５】
前記データ検索部は、前記接尾辞の範囲を計算する際に、クエリとして与えられた記号列の各記号ｗについて、記号の種類数を削減した記号列Ｑと、前記有向グラフと、前記記号ｗの次の記号とに基づいて、前記バローズ・ホィーラー変換した記号列Ｒの最初の要素からｊ番目の要素の中で、前記記号ｗが出現する回数を計算する請求項４記載の記号列検索装置。
【請求項６】
前記グラフ構造解析部は、前記有向グラフの各頂点に、前記頂点を表す記号ｗよりも辞書順が小さな記号が、与えられた記号列の中で発生した回数を付与し、
前記データ検索部は、前記接尾辞の範囲を計算する際に、クエリとして与えられた記号列の各記号ｗについて、記号の種類数を削減した記号列Ｑと、前記有向グラフの各頂点に付与された前記回数と、前記記号ｗの次の記号とに基づいて、前記バローズ・ホィーラー変換した記号列Ｒの最初の要素からｊ番目の要素の中で、前記記号ｗが出現する回数を計算する請求項５記載の記号列検索装置。
【請求項７】
前記データ検索部は、前記バローズ・ホィーラー変換した記号列Ｒの最初の要素からｊ番目の要素の中で、前記記号ｗが出現する回数Ｒａｎｋ（Ｒ、ｗ、ｊ）を、以下の式に従って計算する請求項６記載の記号列検索装置。
【数１】
2018013924.tif 000004
ただし、φ(ｗ’→ｗ)は記号ｗ’から記号ｗに遷移した場合の符号化であり、Ｃ［ｗ］は、前記有向グラフにおいて記号ｗを表す頂点に付与された前記回数である。
【請求項８】
コンピュータを、
移動体の経度緯度情報の時系列と、道路地図上の各道路の道路ＩＤとに基づいて、移動体の経度緯度情報の時系列を、移動体の移動履歴を表す道路ＩＤの列である記号列データに変換するマップマッチング部、及び
移動体の移動履歴を表す道路ＩＤの列における道路ＩＤの遷移が、隣接する道路ＩＤに限定されることを利用した符号化方法を用いて圧縮された、前記記号列データに対して、クエリとして与えられた道路ＩＤの列である記号列データと一致する部分を検索するデータ検索部
として機能させるためのプログラム。
【請求項９】
コンピュータを、
与えられた記号列をバローズ・ホィーラー変換した記号列を出力するＢＷ変換部、
前記与えられた記号列に含まれる記号間の遷移関係を表すグラフ構造を生成するグラフ構造解析部、
前記グラフ構造解析部によって生成された前記グラフ構造を用いて、前記ＢＷ変換部によって出力された前記バローズ・ホィーラー変換した記号列を、記号の種類数を削減した記号列に変換する符号化部、
前記符号化部によって変換された前記記号列を表す圧縮索引を生成する索引化部、及び
前記グラフ構造解析部によって生成された前記グラフ構造、及び前記索引化部によって生成された前記圧縮索引に基づいて、クエリとして与えられた記号列に対応する、前記ＢＷ変換部によって出力された前記バローズ・ホィーラー変換した記号列の接尾辞の範囲を計算するデータ検索部
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、移動体経路検索装置、記号列検索装置、及びプログラムに係り、特に、与えられた記号列から、クエリの記号列と一致する部分を検索する移動体経路検索装置、記号列検索装置、及びプログラムに関する。
【背景技術】
【０００２】
従来より、バローズ・ホィーラー変換に基づき文字列の検索を行うための方法が知られている（非特許文献１）。
【０００３】
また、内部で用いられる簡潔ビットベクトルを圧縮することで、索引全体のサイズを圧縮する方法（非特許文献２）や、バローズ・ホィーラー変換された文字列を、固定長のブロックに分割し、ブロックごとに圧縮する方法が知られている（非特許文献３）。
【０００４】
また、バローズ・ホィーラー変換された配列に対するランク計算を高速化するために必要な補助情報を圧縮するための文字列検索システムが知られている（特許文献１）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００９−２４４９９６号公報
【非特許文献】
【０００６】
【非特許文献１】P. Ferragina and  G. Manzini, Opportunistic Data Structures with Applications, 2003.
【非特許文献２】V. Makinen, and G. Navarro, Implicit Compression Boosting with Applications to Self-Indexing, 2007.
【非特許文献３】Juha Karkkainen and S. Puglisi, Fixed Block Compression Boosting in FM-Indexes, 2011.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記非特許文献１では、バローズ・ホィーラー変換に基づく文字列の検索方法が示されているが、データを圧縮せずにメモリに格納するため、大規模な文字列に対する検索が行えないなどの問題がある。
【０００８】
そこで、上記非特許文献２ではバローズ・ホィーラー変換された文字列を圧縮することで、メモリ使用量が大きく削減できることを示している。しかしながらこの方法では異なる文字は異なる文字として取り扱う。異なる文字をある条件のもとで同じ文字（符号）として表現することができれば、全体の文字種類数が減少し、さらなる圧縮効果が期待できるが、そのようなアイデアは見られない。
【０００９】
上記非特許文献３では、上記非特許文献２と異なりバローズ・ホィーラー変換をブロック分割し、各ブロックに対して圧縮を行う。この方法では各ブロックごとにランク情報を格納する。しかし、各ブロックごとにランク情報を記号種類数だけ格納する必要があり、記号種類数が巨大な値の場合にはこれにかかるデータサイズがオーバヘッドとなり、圧縮率が低下する問題がある。また、ブロックサイズを調整するとサイズが変化する。最適なサイズを求めるためには繰り返し索引を構築しサイズを確認する必要があるため、構築にきわめて大きな時間がかかってしまうことも問題点である。
【００１０】
上記特許文献１に記載の方法は、ランク計算のための補助情報を圧縮するための方法である。この方法を上記非特許文献３に記載の方法と組み合わせることでランク情報を圧縮できる可能性もあるが、その場合でも、上記非特許文献３の問題点である最適なブロックサイズを求めるための計算量の問題は解決しない。
【００１１】
本発明は、上記の事情を鑑みてなされたもので、索引サイズが圧縮され、記号列データの検索に必要なメモリ使用量を減らすことができる移動体経路検索装置、記号列検索装置、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記の目的を達成するために第１の発明に係る移動体経路検索装置は、移動体の経度緯度情報の時系列と、道路地図上の各道路の道路ＩＤとに基づいて、移動体の経度緯度情報の時系列を、移動体の移動履歴を表す道路ＩＤの列である記号列データに変換するマップマッチング部と、移動体の移動履歴を表す道路ＩＤの列における道路ＩＤの遷移が、隣接する道路ＩＤに限定されることを利用した符号化方法を用いて圧縮された、前記記号列データに対して、クエリとして与えられた道路ＩＤの列である記号列データと一致する部分を検索するデータ検索部と、を含んで構成されている。
【００１３】
第２の発明に係るプログラムは、コンピュータを、移動体の経度緯度情報の時系列と、道路地図上の各道路の道路ＩＤとに基づいて、移動体の経度緯度情報の時系列を、移動体の移動履歴を表す道路ＩＤの列である記号列データに変換するマップマッチング部、及び移動体の移動履歴を表す道路ＩＤの列における道路ＩＤの遷移が、隣接する道路ＩＤに限定されることを利用した符号化方法を用いて圧縮された、前記記号列データに対して、クエリとして与えられた道路ＩＤの列である記号列データと一致する部分を検索するデータ検索部として機能させるためのプログラムである。
【００１４】
第１の発明及び第２の発明によれば、マップマッチング部によって、移動体の経度緯度情報の時系列と、道路地図上の各道路の道路ＩＤとに基づいて、移動体の経度緯度情報の時系列を、移動体の移動履歴を表す道路ＩＤの列である記号列データに変換する。そして、データ検索部によって、移動体の移動履歴を表す道路ＩＤの列における道路ＩＤの遷移が、隣接する道路ＩＤに限定されることを利用した符号化方法を用いて圧縮された、前記記号列データに対して、クエリとして与えられた道路ＩＤの列である記号列データと一致する部分を検索する。
【００１５】
このように、移動体の移動履歴を表す道路ＩＤの列である記号列データに変換し、道路ＩＤの遷移が、隣接する道路ＩＤに限定されることを利用した符号化方法を用いて圧縮された記号列データに対して、クエリとして与えられた道路ＩＤの列である記号列データと一致する部分を検索することにより、索引サイズが圧縮され、移動体の移動履歴を表す記号列データの検索に必要なメモリ使用量を減らすことができる。
【００１６】
第３の発明に係る記号列検索装置は、与えられた記号列をバローズ・ホィーラー変換した記号列を出力するＢＷ変換部と、前記与えられた記号列に含まれる記号間の遷移関係を表すグラフ構造を生成するグラフ構造解析部と、前記グラフ構造解析部によって生成された前記グラフ構造を用いて、前記ＢＷ変換部によって出力された前記バローズ・ホィーラー変換した記号列を、記号の種類数を削減した記号列に変換する符号化部と、前記符号化部によって変換された前記記号列を表す圧縮索引を生成する索引化部と、前記グラフ構造解析部によって生成された前記グラフ構造、及び前記索引化部によって生成された前記圧縮索引に基づいて、クエリとして与えられた記号列に対応する、前記ＢＷ変換部によって出力された前記バローズ・ホィーラー変換した記号列の接尾辞の範囲を計算するデータ検索部と、を含んで構成されている。
【００１７】
第４の発明に係るプログラムは、コンピュータを、与えられた記号列をバローズ・ホィーラー変換した記号列を出力するＢＷ変換部、前記与えられた記号列に含まれる記号間の遷移関係を表すグラフ構造を生成するグラフ構造解析部、前記グラフ構造解析部によって生成された前記グラフ構造を用いて、前記ＢＷ変換部によって出力された前記バローズ・ホィーラー変換した記号列を、記号の種類数を削減した記号列に変換する符号化部、前記符号化部によって変換された前記記号列を表す圧縮索引を生成する索引化部、及び前記グラフ構造解析部によって生成された前記グラフ構造、及び前記索引化部によって生成された前記圧縮索引に基づいて、クエリとして与えられた記号列に対応する、前記ＢＷ変換部によって出力された前記バローズ・ホィーラー変換した記号列の接尾辞の範囲を計算するデータ検索部として機能させるためのプログラムである。
【００１８】
第３の発明及び第４の発明によれば、ＢＷ変換部によって、与えられた記号列をバローズ・ホィーラー変換した記号列を出力する。グラフ構造解析部によって、前記与えられた記号列に含まれる記号間の遷移関係を表すグラフ構造を生成する。そして、符号化部によって、前記グラフ構造解析部によって生成された前記グラフ構造を用いて、前記ＢＷ変換部によって出力された前記バローズ・ホィーラー変換した記号列を、記号の種類数を削減した記号列に変換する。また、索引化部によって、前記符号化部によって変換された前記記号列を表す圧縮索引を生成する。データ検索部によって、前記グラフ構造解析部によって生成された前記グラフ構造、及び前記索引化部によって生成された前記圧縮索引に基づいて、クエリとして与えられた記号列に対応する、前記ＢＷ変換部によって出力された前記バローズ・ホィーラー変換した記号列の接尾辞の範囲を計算する。
【００１９】
このように、与えられた記号列に含まれる記号間の遷移関係を表すグラフ構造を生成し、バローズ・ホィーラー変換した記号列を、記号の種類数を削減した記号列に変換し、クエリとして与えられた記号列に対応する、バローズ・ホィーラー変換した記号列の接尾辞の範囲を計算することにより、索引サイズが圧縮され、記号列データの検索に必要なメモリ使用量を減らすことができる。
【発明の効果】
【００２０】
以上説明したように、本発明の移動体経路検索装置及びプログラムによれば、移動体の移動履歴を表す道路ＩＤの列である記号列データに変換し、道路ＩＤの遷移が、隣接する道路ＩＤに限定されることを利用した符号化方法を用いて圧縮された記号列データに対して、クエリとして与えられた道路ＩＤの列である記号列データと一致する部分を検索することにより、索引サイズが圧縮され、移動体の移動履歴を表す記号列データの検索に必要なメモリ使用量を減らすことができる、という効果が得られる。
【００２１】
また、本発明の記号列検索装置及びプログラムによれば、与えられた記号列に含まれる記号間の遷移関係を表すグラフ構造を生成し、バローズ・ホィーラー変換した記号列を、記号の種類数を削減した記号列に変換し、クエリとして与えられた記号列に対応する、バローズ・ホィーラー変換した記号列の接尾辞の範囲を計算することにより、索引サイズが圧縮され、記号列データの検索に必要なメモリ使用量を減らすことができる、という効果が得られる。
【図面の簡単な説明】
【００２２】
【図１】本発明の実施の形態に係る経路パターン検索装置の全体処理を示す図である。
【図２】本発明の実施の形態に係る経路パターン検索装置の経路データを検索する処理を示す図である。
【図３】検索結果の例を示す図である。
【図４】本発明の実施の形態に係る経路パターン検索装置を示すブロック図である。
【図５】本発明の実施の形態に係る経路パターン検索装置を示す機能ブロック図である。
【図６】本発明の実施の形態に係る経路パターン検索装置の索引圧縮部を示す機能ブロック図である。
【図７】有向グラフの例を示す図である。
【図８】（Ａ）記号列の例を示す図、（Ｂ）バローズ・ホィーラー変換した記号列の例を示す図、及び（Ｃ）符号化した記号列の例を示す図である。
【図９】符号化した記号列のハフマン符号を説明するための図である。
【図１０】符号化した記号列の圧縮ウェーブレット木の例を示す図である。
【図１１】本発明の実施の形態に係る経路パターン検索装置のデータ検索部を示す機能ブロック図である。
【図１２】疑似ランク計算部のアルゴリズムを示す図である。
【図１３】接尾辞範囲計算部のアルゴリズムを示す図である。
【図１４】従来技術における接尾辞範囲の計算アルゴリズムを示す図である。
【図１５】本発明の実施の形態に係る経路パターン検索装置の索引圧縮処理ルーチンの内容を示すフローチャートである。
【図１６】本発明の実施の形態に係る経路パターン検索装置の経路パターン検索処理ルーチンの内容を示すフローチャートである。
【発明を実施するための形態】
【００２３】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２４】
＜本実施の形態の概要＞
多数の車両（移動体）から、移動体位置が緯度経度情報の時系列（軌跡）として収集される状況を考える。まず、これらの軌跡はマップマッチング部に入力され、マップマッチング部により、道路地図との照合を行い、移動体が移動した道路の道路ＩＤの列に変換する。この変換処理は自動車の場合、典型的にはカーナビ側で行うことになるが、緯度経度情報のみがサーバに送信された場合はサーバ側で処理することもあり得る。
【００２５】
このような処理によって、移動体の軌跡の集合は移動体の経路データ（記号列データ）の集合へと変換されることになる。
【００２６】
この記号列データの集合はパターン検索部へ入力され、検索可能になるよう、索引化される。
【００２７】
パターン検索部の中にある符号化部では移動体の移動履歴における道路ＩＤの遷移が物理的に隣接する道路ＩＤに限定されることを利用した符号化方法を用いて記号あたりに必要なビット数を減らすことでデータの圧縮を行ったうえで索引化することを特徴としている。
【００２８】
なお、以降のパターン検索部では複数の記号列ではなく、ひとつの巨大な記号列Ｔが索引化されるものと想定している（図１ではＮ＝１）。複数の記号列をひとつの記号列として取り扱うためには、新しい記号＄を区切り文字として用いて、マップマッチング部から出力された複数の記号列を連結すればよい。
【００２９】
また、図２はパターン検索部の全体概要を表している。
【００３０】
まず、索引化したい記号列Ｔ(一般的には巨大なサイズ)を索引圧縮部に渡す。索引圧縮部は、後述する方法に従い、圧縮した索引を構築する。この際、同時にＴを解析することで得られる遷移グラフも出力する。
【００３１】
データ検索部では複数のクエリとなる記号列Ｐ１,Ｐ２,…に対して、圧縮された索引及び遷移グラフを用いて検索結果Ｒ１,Ｒ２,…を返す。
【００３２】
検索結果としては記号列Ｔの接尾辞の範囲を返す。
【００３３】
図３に記号列ＡＤＡＮＡＣ＄に対する検索の例を示す。
【００３４】
まず、ｉ番目の接尾辞は元の記号列のｉ番目から最後の文字までの部分文字列を表す。つまり、０番目の接尾辞はＡＤＡＮＡＣ＄であり、３番目の接尾辞はＮＡＣ＄である。次にこのようにして得られた接尾辞を辞書順にソートする。これにより、各接尾辞の先頭部分では同じパターンが連続するようになる。この例ではＡに対応する範囲は［１，４）である（４は含まない）。また、ＡＤに対応する範囲は［２,３）である（同様に３は含まない）。
【００３５】
＜経路パターン検索装置の構成＞
図４に示すように、本実施の形態に係る経路パターン検索装置１０は、ＣＰＵ１２、ＲＯＭ１４、ＲＡＭ１６、ＨＤＤ１８、通信インタフェース２０、及びこれらを相互に接続するためのバス２２を備えている。
【００３６】
ＣＰＵ１２は、各種プログラムを実行する。ＲＯＭ１４には、各種プログラムやパラメータ等が記憶されている。ＲＡＭ１６は、ＣＰＵ１２による各種プログラムの実行時におけるワークエリア等として用いられる。記憶媒体としてのＨＤＤ１８には、後述する索引圧縮処理ルーチン及び経路パターン検索処理ルーチンを実行するためのプログラムを含む各種プログラムや各種データが記憶されている。
【００３７】
本実施の形態における経路パターン検索装置１０を、索引圧縮処理ルーチン及び経路パターン検索処理ルーチンを実行するためのプログラムに沿って、機能ブロックで表すと、図５に示すようになる。経路パターン検索装置１０は、入力部３０、演算部４０、及び出力部８０を備えている。
【００３８】
入力部３０は、複数の車両から収集された緯度経度情報の時系列である軌跡データの集合を受け付ける。また、入力部３０は、クエリとしての道路ＩＤの列である記号列データを受け付ける。
【００３９】
演算部４０は、道路地図データベース４２、マップマッチング部４４、連結部４６、及びパターン検索部４８を備えている。
【００４０】
道路地図データベース４２には、道路地図上の各道路を表す道路ＩＤが、経路緯度情報と対応付けられて格納されている。
【００４１】
マップマッチング部４４は、入力部３０により受け付けた軌跡データの集合に含まれる軌跡データの各々について、道路地図データベース４２に格納されている各道路ＩＤの経路緯度情報と照合することにより、当該軌跡データを、道路ＩＤの列である記号列データに変換する。
【００４２】
連結部４６は、マップマッチング部４４により得られた記号列データの各々を連結して一つの記号列データを生成する。このとき、新しい記号＄を区切り文字として用いて連結する。
【００４３】
パターン検索部４８は、連結部４６により生成された記号列データから、入力部３０によりクエリとして受け付けた記号列データと一致する部分を検索する。
【００４４】
パターン検索部４８は、索引圧縮部５０、圧縮索引記憶部５２、及びデータ検索部５４を備えている。
【００４５】
索引圧縮部５０は、連結部４６により生成された記号列データについて、圧縮された索引を生成し、圧縮索引記憶部５２に格納する。
【００４６】
索引圧縮部５０は、図６に示すように、グラフ構造解析部６０、ＢＷ変換部６２、符号化部６４、及び索引化部６６を備えている。
【００４７】
グラフ構造解析部６０は、連結部４６により生成された記号列データＴに基づいて、以下に説明するように、記号列データＴの記号間の遷移関係を解析し、遷移関係を表す有向グラフＧを生成する。ここでは、入力された記号列データＴの例として「ＣＡＮＡＤＡ」を用いた場合について説明する。この記号列にはＡ,Ｃ,Ｄ,Ｎの四文字が使われている。
【００４８】
まず、記号列データＴから有向グラフＧを以下のように構成する。
【００４９】
記号列データＴに出現する各記号 (例では Ａ,Ｃ,Ｄ,Ｎ)に対応する頂点を生成する。また、記号列データＴの内部で記号ｗから別の記号ｗ’への直接の遷移（例ではＣ→Ａなど）が一度でも出現した場合、辺ｗ’→ｗを設定する。
【００５０】
さらに、各頂点ｗに自然数Ｃ[ｗ]を付与する。ただし、Ｃ[ｗ]は記号ｗよりも辞書順が小さな記号が記号列データＴの中で発生した回数である。
【００５１】
上記の処理により有向グラフＧが構成される。
【００５２】
次に、構成された有向グラフＧに対して符号化関数を計算する。図７の例では四種類の文字（記号）を二種類の色（符号）に符号化している。
【００５３】
この符号化の要件としては、現在の頂点及び次の記号を表す符号（色）が既知の場合に次の頂点が一意的に確定するような符号化である必要がある。このような符号化は様々なものがあり得るが、ここでの目的が圧縮であることを考えれば、なるべく少ない色数で頂点を塗り分けるというようなものが望ましい。
【００５４】
以降では現在の頂点（記号）ｗ’から次の頂点（記号）ｗへ遷移した際のｗの符号化関数をφ(ｗ’→ｗ)と表記することにする。
【００５５】
なお、例では符号の値を色で示したが、符号のとる値は一般には自然数であるとしてよい。
【００５６】
具体的には以下のステップ１〜ステップ３により色数の少ない符号化を得ることができる。
【００５７】
ステップ１では、有向グラフＧのＮ個の各頂点ｗに対して、それぞれ異なる符号の値（自然数）１,２,・・・,Ｎを割り当てる（これは符号化の要件を満たしている）。
【００５８】
ステップ２では、有向グラフＧのひとつの頂点ｗに対して、ｗを始点とする有向辺の終点の頂点の符号の集合をＵとする（したがってＵは自然数の部分集合になる）。頂点ｗに、集合Ｕに含まれない自然数のなかで最小の値をもつものをｗの符号として割り当てる。  上記ステップ２を、有向グラフＧのすべての頂点ｗに対して繰り返す。
【００５９】
上記図７の例ではＡ,Ｃ,Ｄには青色、Ｎには黄色、という符号が割り当てられる。この符号が符号化の要件を満たしていることは図７より容易に確認できる。たとえば、現在の頂点がＡの場合、次の符号が黄色であれば、次の頂点はＮであり、次の符号が青色であれば、次の頂点はＤである。
【００６０】
なお、この例では各頂点に一つ符号を割り当てたが、要件さえ満たせば、ひとつの頂点に複数の符号語が割り当てられるような符号化でもよい。
【００６１】
入力された記号列データＴが、道路ＩＤの列の場合、記号列データＴのなかでｗ’→ｗという遷移はある道路IDから別の道路IDへの遷移を意味するが、車両の移動は物理的には隣接している道路IDに限定されているため、ｗから遷移する可能性のある記号ｗ’は高々数種類程度である。
【００６２】
これは上記のステップ２において、集合Ｕのサイズが小さくなることを意味し、したがってｗの符号として小さな自然数を割り当てることができることを意味している。また、全体で使われる色数を小さくすることができ、高い圧縮率を実現することができる。例えば、「ＣＡＮＡＤＡ」は、記号が４種類であるため、２ビットであるが、符号化により、青・青・黄・青・青・青に変換されるため、記号あたり１ビットとなる。
【００６３】
ＢＷ変換部６２は、連結部４６により生成された記号列データＴに基づいて、以下に説明するように、記号列データＴをバローズ・ホィーラー変換した記号列Ｒに変換し、符号化部６４へ渡す。
【００６４】
ＢＷ変換部６２ではまず記号列データＴを反転させ、末尾に＄という特殊記号を付与する（図８（Ａ）参照）。この記号＄の辞書順序は 記号列データＴ内のどの記号よりも小さいものとする。この記号列をＳとする。例ではＳ＝ＡＤＡＮＡＣ＄となる。
【００６５】
次に記号列Ｓをバローズ・ホィーラー変換し、得られた記号列をＲとする。例では記号列ＲがＣＮ＄ＤＡＡＡである（図８（Ｂ）参照）。この記号列Ｒを符号化部６４に渡す。
【００６６】
符号化部６４は、ＢＷ変換部６２から受け取った記号列Ｒ、及びグラフ構造解析部６０から受け取った有向グラフＧの符号化関数φをもとに、記号列Ｒを符号化し、符号化された記号列Ｑを得る（図８（Ｃ）参照）。
【００６７】
ただし、「＄」には他のどれとも異なる符号を割り当てるものとする。例では記号列Ｒに対応したＢＹ＄ＢＢＢＢという、符号化された記号列Ｑが得られている（Ｂは青色、Ｙは黄色を示す）。この記号列Ｑは、記号列Ｒよりも記号種類数が少なく、圧縮しやすいものになっている。
【００６８】
索引化部６６は、符号化部６４で得られた記号列Ｑを圧縮ウェーブレット木へ格納することで圧縮を行う。上記非特許文献２との最大の違いは有向グラフＧを用いた符号化を行うかどうかである。符号化部６４で得られた記号列Ｑは記号列Ｒよりも記号種類数が少ないので、記号列Ｒよりも記号列Ｑのサイズは小さくなる。
【００６９】
ここで得られた圧縮ウェーブレット木が、圧縮索引記憶部５２に格納される。
【００７０】
図９、図１０に、記号列Ｑに対する圧縮ウェーブレット木の例を示す。この例ではまず、図９に示すように、記号列Ｑに対するハフマン符号化を行い、ハフマン符号化された記号列Ｑ’を求める。次に、図１０に示すように、各記号の一番左側のビットを並べたビット列を作る。これがウェーブレット木における根ノードである。次に、一ビット目が０の記号だけを集めて、それらの二ビット目を左側の子ノードに対応するビット列に格納する。例では一ビット目が０の記号はＹ及び＄であるので、左側の子ノードに対応するビット列には、これらの順番を保持したまま、これらの文字の２ビット目である０、１が格納されている。一ビット目が１の記号についても同様に、右側の子ノードに対応するビット列に格納するが、この例では一ビット目が１の記号はＢのみであるため、右側の子ノードを作る必要はない。ウェーブレット木の各ノードに対応するビット列は、上記非特許文献２でも用いられている、圧縮簡潔ビットベクトルを用いる。
【００７１】
データ検索部５４は、入力部３０が受け付けたクエリとしての記号列データＰを受け取り、検索結果として、記号列データＰに対応する、記号列データＴの接尾辞の範囲を返す。データ検索部５４は、図１１に示すように、接尾辞範囲計算部７０及び疑似ランク計算部７２を備えている。
【００７２】
上記では、記号列Ｒ＝ＣＮ＄ＤＡＡＡを符号化し、記号列Ｑ＝ＢＹ＄ＢＢＢＢを得た。ここではＡ,Ｃ,Ｄが同じ符号に割り当てられているため、従来技術では可能であった検索が一見すると不可能であるように見えるが、本実施の形態では疑似ランク計算部７２によるランク計算により、符号化された記号列Ｑであっても従来と同様に検索を行うことが可能となる。
【００７３】
疑似ランク計算部７２は、符号化された記号列Ｑに対して、記号列Ｒを用いずに、記号列Ｒ、記号ｗ、位置ｊに対するＲａｎｋ（Ｒ,ｗ,ｊ）を計算する。ここで、Ｒａｎｋ（Ｒ,ｗ,ｊ）の値は、Ｒの最初の要素（0番目）からｊ−１番目の要素の中で、記号ｗが何回出現したかを表すカウント値として定義される。
【００７４】
バローズ・ホィーラー変換された記号列Ｒから接尾辞の範囲を計算するための従来手法（図１２）では記号列Ｒに対するランク計算を必要する。符号化された記号列Ｑに対して、記号列Ｒを用いずにＲａｎｋ（Ｒ, ｗ,ｊ）を計算することができれば、接尾辞の範囲を計算することができる。これは、Ｃ［ｗ’］＜＝ｊ＜Ｃ［ｗ’＋１］ となるような記号ｗ’を用いて以下のように計算することができる。Ｃ［ｗ］の定義よりこのような記号ｗ’は一つに決まる。ただし、Ｃ［ｗ’＋１］は、辞書順で記号ｗ’の次の記号に対応する頂点に付与された自然数である。
【００７５】
【数１】
2018013924.tif 000003
【００７６】
ここで、φ(ｗ’→ｗ)は記号ｗ’から記号ｗに遷移した場合の符号化である。この第二式ではＲａｎｋ（Ｒ,ｗ,Ｃ［ｗ’］）のようにＲを使っているが、これが必要になるのは有向グラフＧの中の辺の数だけなので、索引圧縮部５０の処理の直後にＺｗ’→ｗを事前に計算しておき、有向グラフＧの辺にＺｗ’→ｗを格納しておくことで、検索時においては再計算する必要がない。したがって、疑似ランク計算部７２は、第一式を用いてＲａｎｋ（Ｑ,φ（ｗ’→ｗ）,ｊ）−Ｚｗ’→ｗから、所望のＲａｎｋ(Ｒ,ｗ,ｊ)を得る。
【００７７】
図１２に、疑似ランク計算部７２によるアルゴリズムを示す。
【００７８】
なお、 記号ｗと Ｃ［ｗ’］＜＝ ｊ ＜Ｃ［ｗ’＋１］となる記号ｗ’の遷移が有向グラフＧに含まれない場合、上式は Ｒａｎｋ（Ｒ, ｗ, ｊ）と一致することが保証されない。しかしながら、ｗ’→ｗの遷移が有向グラフに含まれないことは記号列データＴ 内でもｗ’→ｗの遷移がない、ということであり、この場合は、上記図１２でも示すように、クエリの記号列データが、記号列データＴ内に存在しないことを意味するので、即座にＮｏｔＦｏｕｎｄを返すことで正しい検索結果となる。
【００７９】
接尾辞範囲計算部７０は、圧縮ウェーブレット木で圧縮された記号列Ｑ、及びクエリとしての記号列Ｐ、 及び有向グラフＧを用いて、記号列データＴの、クエリ記号列Ｐに対応する接尾辞の範囲を計算する。具体的には、記号列Ｑ、記号列Ｐ、有向グラフＧを受け取り、図１３に示すアルゴリズムに従って、接尾辞の範囲を返す。結果的にこのアルゴリズムは、図１４に示す従来手法（非特許文献１）のアルゴリズムにおけるランク計算を、疑似ランク計算部７２による計算に置き換えたものになっており、従来手法と結果が一致することが保証されている。
【００８０】
上記図１３のアルゴリズムは、上記図３の例を用いると、クエリの記号列データＰ＝“Ａ”に対しては[ｓｔ,ｅｄ）＝[１,４）を返し、Ｐ＝“ＡＤ”に対しては[ｓｔ,ｅｄ）＝[２,３）を返す。さらに記号列データＴ中に存在しない記号列データＰ＝“ＡＡ”に対してはＮｏｔＦｏｕｎｄを返す。
【００８１】
なお、接尾辞範囲計算部７０は、結果の接尾辞範囲[ｓｔ,ｅｄ）に対して、ｅｄ−ｓｔを計算することで、クエリの記号列データＰが記号列データＴの中で出現する回数を計算するようにしてもよい。また、接尾辞範囲計算部７０は、従来手法と同様に記号列データＰが記号列データＴ内で出現する位置なども計算するようにしてもよい。
【００８２】
接尾辞範囲計算部７０によって接尾辞範囲[ｓｔ,ｅｄ）又はＮｏｔＦｏｕｎｄが、出力部８０により出力される。
【００８３】
＜経路パターン検索装置の作用＞
次に、本発明の実施の形態に係る経路パターン検索装置１０の動作について説明する。
【００８４】
入力部３０により、複数の車両から収集された緯度経度情報の時系列である軌跡データの集合を受け付けると、経路パターン検索装置１０によって、図１５に示す索引圧縮処理ルーチンが実行される。
【００８５】
まず、ステップＳ１００において、入力部３０により受け付けた軌跡データの集合に含まれる軌跡データの各々について、道路地図データベース４２に格納されている各道路ＩＤの経路緯度情報と照合することにより、当該軌跡データを、道路ＩＤの列である記号列データに変換する。
【００８６】
ステップＳ１０２では、上記ステップＳ１００により得られた記号列データの各々を連結して一つの記号列データを生成する。
【００８７】
ステップＳ１０４では、上記ステップＳ１０２により生成された記号列データＴに基づいて、記号列データＴの記号間の遷移関係を解析し、遷移関係を表す有向グラフＧを生成すると共に、各頂点ｗに自然数Ｃ[ｗ]を付与し、有向グラフＧに対して符号化関数を計算する。
【００８８】
そして、ステップＳ１０６では、上記ステップＳ１０２で生成された記号列データＴに基づいて、記号列データＴをバローズ・ホィーラー変換した記号列Ｒに変換する。
【００８９】
ステップＳ１０８では、上記ステップＳ１０６で得られた、バローズ・ホィーラー変換した記号列Ｒ、及び上記ステップＳ１０４で得られた有向グラフＧの符号化関数φをもとに、記号列Ｒを符号化し、符号化された記号列Ｑを得る。
【００９０】
そして、ステップＳ１１０では、上記ステップＳ１０８で得られた記号列Ｑを圧縮ウェーブレット木へ格納することで圧縮を行い、ここで得られた圧縮ウェーブレット木を、圧縮索引記憶部５２に格納し、索引圧縮処理ルーチンを終了する。
【００９１】
そして、入力部３０により、クエリとしての記号列データＰを受け付けると、経路パターン検索装置１０によって、図１６に示す経路パターン検索処理ルーチンが実行される。
【００９２】
まず、ステップＳ１２０において、クエリとしての記号列データＰにおけるターゲット記号ｗ、接尾辞範囲の開始位置ｓｔ及び終了位置ｅｄを初期化する（上記図１３の１行目〜３行目参照）。
【００９３】
そして、ステップＳ１２２において、前回のターゲット記号ｗを、ｗ’として保持すると共に、クエリとしての記号列データＰにおけるターゲット記号を、一つ前の記号に更新する（上記図１３の５行目、６行目参照）。
【００９４】
ステップＳ１２４では、符号化された記号列Ｑと、有向グラフＧとに基づいて、接尾辞範囲の開始位置ｓｔ及び終了位置ｅｄのそれぞれについて、疑似ランク計算部７２による疑似ランクの計算を行う（上記図１３の７行目、８行目参照）。
【００９５】
ステップＳ１２６では、上記ステップＳ１２４による計算結果と、有向グラフＧとに基づいて、接尾辞範囲の開始位置ｓｔ及び終了位置ｅｄのそれぞれを更新する（上記図１３の９行目、１０行目参照）。
【００９６】
ステップＳ１２８では、接尾辞範囲の開始位置ｓｔ又は終了位置ｅｄについての計算結果が、ＮｏｔＦｏｕｎｄであるか、又は接尾辞範囲の開始位置ｓｔが、終了位置ｅｄ以降になったかを判定する（上記図１３の１１行目参照）。接尾辞範囲の開始位置ｓｔ又は終了位置ｅｄについての計算結果が、ＮｏｔＦｏｕｎｄである場合、又は接尾辞範囲の開始位置ｓｔが、終了位置ｅｄ以降になった場合には、ステップＳ１３０において、クエリとしての記号列データＰが、記号列データＴから検索されなかったことを示すメッセージを出力部８０により出力して、経路パターン検索処理ルーチンを終了する（上記図１３の１２行目参照）。
【００９７】
一方、接尾辞範囲の開始位置ｓｔ及び終了位置ｅｄについての計算結果の何れもが、ＮｏｔＦｏｕｎｄではなく、かつ、接尾辞範囲の開始位置ｓｔが、終了位置ｅｄより前である場合には、ステップＳ１３２へ移行する。
【００９８】
ステップＳ１３２では、クエリとしての記号列データＰの全ての記号について、上記ステップＳ１２２〜ステップＳ１２８の処理を実行したか否かを判定する（上記図１３の４行目参照）。上記ステップＳ１２２〜ステップＳ１２８の処理を実行していない記号が存在する場合には、上記ステップＳ１２２へ戻り、当該記号を、ターゲット記号とする。
【００９９】
一方、クエリとしての記号列データＰの全ての記号について、上記ステップＳ１２２〜ステップＳ１２８の処理を実行した場合には、ステップＳ１３４において、最終的に得られた接尾辞範囲の開始位置ｓｔ及び終了位置ｅｄを用いて、検索結果を出力部８０により出力して、経路パターン検索処理ルーチンを終了する（上記図１３の１５行目参照）。
【０１００】
以上説明したように、本実施の形態に係る経路パターン検索装置によれば、マップマッチングにより、移動体の移動履歴を表す道路ＩＤの列である記号列データに変換し、道路ＩＤの遷移が、隣接する道路ＩＤに限定されることを利用した符号化方法を用いて圧縮された記号列データに対して、クエリとして与えられた道路ＩＤの列である記号列データと一致する部分を検索することにより、索引サイズが圧縮され、移動体の移動履歴を表す記号列データの検索に必要なメモリ使用量を減らすことができる。
【０１０１】
また、与えられた記号列に含まれる記号間の遷移関係を表すグラフ構造を生成し、バローズ・ホィーラー変換した記号列を、記号の種類数を削減した記号列に変換し、クエリとして与えられた記号列に対応する、バローズ・ホィーラー変換した記号列の接尾辞の範囲を計算することにより、索引サイズが圧縮され、記号列データの検索に必要なメモリ使用量を減らすことができる。
【０１０２】
また、グラフ構造に記号間の遷移の情報を持たせることで、記号列データの各記号を格納するに必要なビット数が削減される。なぜならば、たとえ、２20種類の記号がある場合でも、各記号から遷移する可能性のある記号が４種類しかない場合、記号間の遷移の情報を別途グラフ構造として保持することで、一記号あたりのビット数がlog2４＝２ビットで表現できるためである。記号間の遷移の情報を保持しなければlog2２20＝２０ビットとなるため、10倍の違いがある。特に、数百万〜数千万の道路リンクをもつ道路ネットワークの場合、ある道路リンクを走行する車両が次に移動可能（＝遷移可能）な道路リンクは典型的には４つ以下（十字路）であるため、車両の移動履歴を表す道路ＩＤの列である記号列データの各記号を格納するに必要なビット数が削減される。
【０１０３】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１０４】
例えば、記号列データが、道路ＩＤの列を表す記号列データであり、クエリの記号列データと同じ経路パターンを検索する場合を例に説明したが、これに限定されるものではない。道路ＩＤの列以外のものを表す記号列データを入力としてもよい。
【０１０５】
また、道路ＩＤの列を表す複数の記号列データを連結して１つの記号列データを生成する場合を例に説明したが、これに限定されるものではない。例えば、道路ＩＤの列を表す複数の記号列データの各々について、符号化方法を用いて圧縮し圧縮索引を生成し、記号列データの各々について、クエリとしての記号列データと一致する部分を検索するようにしてもよい。
【０１０６】
例えば、本発明のプログラムは、記憶媒体に格納して提供するようにしてもよい。
【符号の説明】
【０１０７】
１０   経路パターン検索装置
３０   入力部
４０   演算部
４２   道路地図データベース
４４   マップマッチング部
４６   連結部
４８   パターン検索部
５０   索引圧縮部
５２   圧縮索引記憶部
５４   データ検索部
６０   グラフ構造解析部
６２   ＢＷ変換部
６４   符号化部
６６   索引化部
７０   接尾辞範囲計算部
７２   疑似ランク計算部
８０   出力部
【図１】
2018013924.tif 000005
【図２】
2018013924.tif 000006
【図３】
2018013924.tif 000007
【図４】
2018013924.tif 000008
【図５】
2018013924.tif 000009
【図６】
2018013924.tif 000010
【図７】
2018013924.tif 000011
【図８】
2018013924.tif 000012
【図９】
2018013924.tif 000013
【図１０】
2018013924.tif 000014
【図１１】
2018013924.tif 000015
【図１２】
2018013924.tif 000016
【図１３】
2018013924.tif 000017
【図１４】
2018013924.tif 000018
【図１５】
2018013924.tif 000019
【図１６】
2018013924.tif 000020