特許ウォッチ

公開番号2025140960
公報種別公開特許公報(A)
公開日2025-09-29
出願番号2024040635
出願日2024-03-15
発明の名称検索装置、検索方法、及びプログラム
出願人個人
代理人個人
主分類G06F 16/901 20190101AFI20250919BHJP(計算;計数)
要約【課題】効率よく文字列を検索することが可能な検索装置、検索方法、及びプログラムを提供する。
【解決手段】検索装置100は、可変長の登録文字列112と、複数のノード200から構成されるデータツリー111とを格納するデータベース110を備える。ノード200は、登録文字列112の少なくとも一部の文字列を示す直列文字列と、当該ノード200の下位の遷移先に関するブランチ情報とを含む。検索装置100は、ノード200の直列文字列及びブランチ情報に基づいて、検索文字列を含む登録文字列112を検索する検索部130を備える。直列文字列は、直列文字列が示す文字列と終端同士が一致する登録文字列112が存在する場合、登録文字列112の実体を保持し、直列文字列が示す文字列と終端同士が一致する登録文字列112が存在しない場合、当該ノード200のブランチ情報が示す遷移先の登録文字列112を共用参照する。
【選択図】図3
特許請求の範囲【請求項１】
可変長の登録文字列と、複数のノードから構成されるデータツリーとを格納する格納部であって、前記ノードは、前記登録文字列の少なくとも一部の文字列を示す直列文字列情報と、当該ノードの下位の遷移先に関するブランチ情報とを含む、格納部と、
前記ノードの前記直列文字列情報及び前記ブランチ情報に基づいて、検索文字列を含む前記登録文字列を検索する検索部と、
を備え、
前記直列文字列情報は、前記直列文字列情報が示す文字列と終端同士が一致する前記登録文字列が存在する場合、前記登録文字列の実体を保持し、前記直列文字列情報が示す文字列と終端同士が一致する前記登録文字列が存在しない場合、当該ノードの前記ブランチ情報が示す遷移先の前記登録文字列を共用参照する、
検索装置。
続きを表示（約 960 文字）【請求項２】
前記ノードは、前記直列文字列情報が実体を保持するか否かを示す実体フラグを含む、
請求項１に記載の検索装置。
【請求項３】
前記検索部は、前記ノードに含まれる前記直列文字列情報が示す文字列及び前記検索文字列の比較結果と、前記ノードに含まれる前記実体フラグとに基づいて、前記検索を行う、
請求項２に記載の検索装置。
【請求項４】
前記検索部は、前記ノードに含まれる前記直列文字列情報が示す文字列と前記検索文字列とを、並列処理可能なデータ単位で比較する、
請求項１乃至３のいずれか一項に記載の検索装置。
【請求項５】
前記検索部は、前記ノードに含まれる前記直列文字列情報が示す文字列と前記検索文字列とを、ＳＩＭＤ（ＳｉｎｇｌｅＩｎｓｔｒｕｃｔｉｏｎ／ＭｕｌｔｉｐｌｅＤａｔａ）命令により比較する、
請求項４に記載の検索装置。
【請求項６】
前記ブランチ情報は、前記直列文字列情報が示す文字列に続く複数のブランチ文字と、前記複数のブランチ文字のそれぞれに対応する遷移先情報と、を含む、
請求項１乃至３のいずれか一項に記載の検索装置。
【請求項７】
前記遷移先情報は、前記複数のブランチ文字の後に連続して格納される、
請求項６に記載の検索装置。
【請求項８】
前記検索部は、前記ノードに含まれる前記複数のブランチ文字と前記検索文字列における前記ブランチ文字の位置に対応する文字とを、並列処理可能なデータ単位で比較する、
請求項６に記載の検索装置。
【請求項９】
前記検索部は、前記ノードに含まれる前記複数のブランチ文字と前記検索文字列における前記ブランチ文字の位置に対応する文字とを、ＳＩＭＤ命令により比較する、
請求項８に記載の検索装置。
【請求項１０】
新たに登録する前記登録文字列に基づいて前記ノードを割り当て、前記割り当てたノードに前記直列文字列情報及び前記ブランチ情報を設定する登録部を備える、
請求項１乃至３のいずれか一項に記載の検索装置。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明は、検索装置、検索方法、及びプログラムに関する。
続きを表示（約 3,100 文字）【背景技術】
【０００２】
近年のＩＴ（Information Technology）技術の発達及び世界的な普及に伴い、コンピュータにおけるデータ処理は、企業の競争力をも左右する最も重要な要素に成っている。特にＩｏＴ（Intern et of Things）の推進や５Ｇの普及等により、全世界のデータ量はさらに爆発的に増加すると予測されている。このため、データ処理技術の飛躍的な向上が望まれている。
【０００３】
データ処理技術として、例えば、データ検索に関連する技術として、特許文献１、非特許文献１～４が知られている。特許文献１には、Ｐａｔｒｉｃｉａ－Ｔｒｅｅを用いた情報検索方法が記載されている。非特許文献１には、Ｔｒｉｅ（Ｐｒｅｆｉｘ-Ｔｒｅｅ)による効率的なインデックス作成方法が記載されている。非特許文献２には、ＶＡＳＴ木を用いたＳＩＭＤ命令（ＳｉｎｇｌｅＩｎｓｔｒｕｃｔｉｏｎ／ＭｕｌｔｉｐｌｅＤａｔａ）による大規模データ探索方法が記載されている。非特許文献３には、Ｔｒｉｅの高さを最適化する方法が記載されている。非特許文献４には、ＳＩＭＤ命令を使用してツリーベースのインデックス構造の処理を高速化する方法が記載されている。
【先行技術文献】
【特許文献】
【０００４】
特開２００１－３５７０７０号公報
【非特許文献】
【０００５】
Matthias Boehm, Benjamin Schlegel, Peter Benjamin Volk, Ulrike Fischer, Dirk Habich, Wolfgang Lehner, "Efficient In-Memory Indexing with Generalized Prefix Trees", Datenbanksysteme fur Business, Technologie und Web (BTW), pp. 227-246, 2011年3月, [令和５年１２月１８日検索], インターネット<URL:https://dl.gi.de/bitstreams/4acd192a-e10b-4fa5-bb29-af8907b0a1ae/download>
山室健, 鬼塚真, 日高東潮, 山室雅司, "VAST木: 木構造索引の圧縮を用いたSIMD命令による大規模データ探索の高速化", 情報処理学会論文誌データベース, Vol.8，No.2，pp.30-42, 2015年6月, [令和５年１２月１８日検索], インターネット<URL:https://db-event.jpn.org/deim2011/proceedings/pdf/e2-1.pdf>
Robert Binna, Eva Zangerle, Martin Pichl, Gunther Specht, Viktor Leis, "HOT: A Height Optimized Trie Index for Main-Memory Database Systems", SIGMOD '18: Proceedings of the 2018 International Conference on Management of Data, 2018年5月, pp.521-534, [令和５年１２月１８日検索], インターネット<URL:https://15721.courses.cs.cmu.edu/spring2020/papers/07-oltpindexes2/p521-binna.pdf>
Steffen Zeuch, Frank Huber, Johann-Christoph Freytag, "Adapting Tree Structures for Processing with SIMD Instructions", 17th International Conference on Extending Database Technology(EDBT), p.97-108, 2014年3月, [令和５年１２月１８日検索], インターネット<URL:https://openproceedings.org/2014/conf/edbt/ZeuchFH14.pdf>
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記のような関連する技術では、可変長の文字列を検索することが考慮されていないため、効率よく検索することができない場合がある。
【０００７】
本発明は、このような事情に鑑みてなされたものであって、効率よく文字列を検索することが可能な検索装置、検索方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明に係る検索装置は、可変長の登録文字列と、複数のノードから構成されるデータツリーとを格納する格納部であって、前記ノードは、前記登録文字列の少なくとも一部の文字列を示す直列文字列情報と、当該ノードの下位の遷移先に関するブランチ情報とを含む、格納部と、前記ノードの前記直列文字列情報及び前記ブランチ情報に基づいて、検索文字列を含む前記登録文字列を検索する検索部と、を備え、前記直列文字列情報は、前記直列文字列情報が示す文字列と終端同士が一致する前記登録文字列が存在する場合、前記登録文字列の実体を保持し、前記直列文字列情報が示す文字列と終端同士が一致する前記登録文字列が存在しない場合、当該ノードの前記ブランチ情報が示す遷移先の前記登録文字列を共用参照するものである。
【０００９】
本発明に係る検索方法は、可変長の登録文字列と、複数のノードから構成されるデータツリーとを格納し、前記ノードは、前記登録文字列の少なくとも一部の文字列を示す直列文字列情報と、当該ノードの下位の遷移先に関するブランチ情報とを含み、前記ノードの前記直列文字列情報及び前記ブランチ情報に基づいて、検索文字列を含む前記登録文字列を検索し、前記直列文字列情報は、前記直列文字列情報が示す文字列と終端同士が一致する前記登録文字列が存在する場合、前記登録文字列の実体を保持し、前記直列文字列情報が示す文字列と終端同士が一致する前記登録文字列が存在しない場合、当該ノードの前記ブランチ情報が示す遷移先の前記登録文字列を共用参照するものである。
【００１０】
本発明に係るプログラムは、可変長の登録文字列と、複数のノードから構成されるデータツリーとを格納し、前記ノードは、前記登録文字列の少なくとも一部の文字列を示す直列文字列情報と、当該ノードの下位の遷移先に関するブランチ情報とを含み、前記ノードの前記直列文字列情報及び前記ブランチ情報に基づいて、検索文字列を含む前記登録文字列を検索し、前記直列文字列情報は、前記直列文字列情報が示す文字列と終端同士が一致する前記登録文字列が存在する場合、前記登録文字列の実体を保持し、前記直列文字列情報が示す文字列と終端同士が一致する前記登録文字列が存在しない場合、当該ノードの前記ブランチ情報が示す遷移先の前記登録文字列を共用参照する、処理をコンピュータに実行させるためのプログラムである。
【発明の効果】
（【００１１】以降は省略されています）

関連特許