特許ウォッチ

公開番号2025006564
公報種別公開特許公報(A)
公開日2025-01-17
出願番号2023107443
出願日2023-06-29
発明の名称情報処理装置、情報処理方法及びプログラム
出願人キヤノン株式会社
代理人個人
主分類G06F 16/903 20190101AFI20250109BHJP(計算;計数)
要約【課題】検索に必要な記憶領域の容量を抑え、高速にデータを検索できるようにする。
【解決手段】情報処理装置は、一意に識別可能な検索キーに基づいて生成された第1のトライ構造を保持する保持手段と、保持手段に保持されている第1のトライ構造を参照して、検索キーから該検索キーに対応する属性値を検索する検索手段とを有し、第1のトライ構造は各ノードに属性値が関連付けられており、検索手段は、検索キーに基づいて第1のトライ構造に対する検索を行い、最も深く到達したノードに関連付けられた属性値を検索結果とする。
【選択図】図4
特許請求の範囲【請求項１】
一意に識別可能な検索キーに基づいて生成された第１のトライ構造を保持する保持手段と、
前記保持手段に保持されている前記第１のトライ構造を参照して、前記検索キーから該検索キーに対応する属性値を検索する検索手段とを有し、
前記第１のトライ構造は各ノードに前記属性値が関連付けられており、
前記検索手段は、前記検索キーに基づいて前記第１のトライ構造に対する検索を行い、最も深く到達したノードに関連付けられた前記属性値を検索結果とすることを特徴とする情報処理装置。
続きを表示（約 1,600 文字）【請求項２】
前記検索手段は、前記検索キーを構成するワード毎に順に前記第１のトライ構造に対して検索を行い、次のワードに対応するノードが前記第１のトライ構造にない場合に、現在のノードに関連付けられた前記属性値を検索結果とすることを特徴とする請求項１に記載の情報処理装置。
【請求項３】
新たな検索キー及び該検索キーに対応する属性値に基づいて前記第１のトライ構造を更新する登録処理を行う登録手段を有することを特徴とする請求項１に記載の情報処理装置。
【請求項４】
前記登録手段は、
前記新たな検索キーに対応する第１の属性値と、前記新たな検索キーに基づいて前記第１のトライ構造を検索して得られた第２の属性値とが異なる場合に、前記第１のトライ構造において、前記新たな検索キーでの検索で最も深く到達したノードから遷移する、前記第１の属性値を関連付けた前記新たな検索キーに対応するノードを作成することを特徴とする請求項３に記載の情報処理装置。
【請求項５】
前記登録手段は、
前記第１の属性値と前記第２の属性値とが異なる場合に、対応する属性値が前記第２の属性値である検索キーの各々について、該検索キーに基づいて前記第１のトライ構造を検索して第３の属性値を取得し、前記第２の属性値と前記第３の属性値とが異なる検索キー及び該検索キーに対応する属性値の登録処理を行うことを特徴とする請求項４に記載の情報処理装置。
【請求項６】
前記登録手段は、前記新たな検索キーに対応するノードを作成した場合に、前記第１のトライ構造におけるノード数を最小化するように、前記新たな検索キーでの検索で最も深く到達したノード及び該ノードから遷移するノードを再構築することを特徴とする請求項４に記載の情報処理装置。
【請求項７】
一意に識別可能なファイル名を有するファイルを木構造の保存場所で管理する階層型ファイルシステムを有しており、
ファイル名を前記検索キーとし、該ファイル名を有するファイルの保存場所を前記属性値とすることを特徴とする請求項１に記載の情報処理装置。
【請求項８】
一意に識別可能なファイル名を有するファイルを木構造の保存場所で管理する階層型ファイルシステムを有しており、
前記ファイル名及びデータサイズの少なくとも一方を入力として該ファイル名を有するファイルの保存場所を決定し、前記ファイル名及び決定した前記ファイルの保存場所を前記検索キー及び前記属性値として前記登録手段に入力する決定手段を有することを特徴とする請求項３に記載の情報処理装置。
【請求項９】
前記保持手段は、前記検索キーに基づいて生成された第２のトライ構造を保持し、
前記第２のトライ構造は各ノードに前記第１のトライ構造とは別の種類の属性値が関連付けられており、
前記第１のトライ構造と前記第２のトライ構造における同一の共通接頭辞を表すノードが１つのノードとして構成されていることを特徴とする請求項１に記載の情報処理装置。
【請求項１０】
情報処理装置が実行する情報処理方法であって、
一意に識別可能な検索キーに基づいて生成された第１のトライ構造を保持する保持工程と、
保持されている前記第１のトライ構造を参照して、前記検索キーから該検索キーに対応する属性値を検索する検索工程とを有し、
前記第１のトライ構造は各ノードに前記属性値が関連付けられており、
前記検索工程では、前記検索キーに基づいて前記第１のトライ構造に対する検索を行い、最も深く到達したノードに関連付けられた前記属性値を検索結果とすることを特徴とする情報処理方法。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法及びプログラムに関する。
続きを表示（約 2,400 文字）【背景技術】
【０００２】
画像データベース、ニュース記事サイト、機械学習用のデータ管理システム等のデータ名称からデータを取得するシステムにおいて、高速にデータを検索する技術の需要は高い。これらのシステムでは、経済的側面から、データをデータストレージに効率よく保存することが求められる。一方で、操作性の面から、データはデータ名称によって、意味的に分割され、データストレージに保存したいという要求もある。
【０００３】
機械学習用の画像データの一般的な保存状態の例を図２０に示す。ここでは、画像データはＰＮＧファイル形式で、階層的ツリー構造のファイルシステムに保存されるものとする。また、保存場所である「／Ｖｏｌｕｍｅ１／」と「／Ｖｏｌｕｍｅ２／」は物理的に異なるボリュームであるとする。図２０では、第１列の識別名を持つ画像ファイルが対応する第２列の保存場所のボリュームに保存されていることを表している。
【０００４】
この例では、識別名の接頭辞が「Ｐｈｏｔｏ＿Ｉｍｇ１＿００１」～「Ｐｈｏｔｏ＿Ｉｍｇ１＿５８０」である画像ファイルが「／Ｖｏｌｕｍｅ１／」に保存されている。識別名の接頭辞が「Ｐｈｏｔｏ＿Ｉｍｇ１＿５８３」～「Ｐｈｏｔｏ＿Ｉｍｇ１＿９９９」又は「Ｐｈｏｔｏ＿Ｉｍｇ２」である画像ファイルが「／Ｖｏｌｕｍｅ２／」に保存されている。また、識別名の接頭辞が「Ｐｈｏｔｏ＿Ｉｍｇ１＿５８１」と「Ｐｈｏｔｏ＿Ｉｍｇ１＿５８２」である２つの画像ファイルの保存先は変則的であり、その前後のファイルとは保存場所が異なっている。
【０００５】
このような識別名において接頭辞が共通で接尾部が僅かに異なっていることが多い場合に、識別名から保存場所を高速に検索するデータベース技術として、共通接頭辞検索に適したトライ（Ｔｒｉｅ）が知られている。識別名から保存場所を検索するには、Ｋｅｙ－Ｖａｌｕｅ型のデータベースを用いてもよいし、トライ技術を適用したデータベースを用いてもよい。しかしながら、いずれも検索のために必要となる、一次記憶（メモリ等）や二次記憶（ハードディスク等）の容量が大きいという課題があった。特許文献１には、トライを用いて高速な検索を実現しつつ、必要となる一次記憶（メモリ）の容量を削減する技術が提案されている。
【先行技術文献】
【特許文献】
【０００６】
特開２００８－１３４６８８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
特許文献１に記載の技術では、頻繁に検索される識別名については高速に検索できる一方で、まれに検索される識別名については検索に時間がかかるという課題があった。また、検索に必要な一次記憶（メモリ）の容量を削減することはできるが、その分を二次記憶（ハードディスク等）に保持しているため、検索に必要な記憶領域の総量が多いという課題があった。本発明は、このような事情に鑑みてなされたものであり、検索に必要な記憶領域の容量を抑え、高速にデータを検索できるようにすることを目的とする。
【課題を解決するための手段】
【０００８】
本発明に係る情報処理装置は、一意に識別可能な検索キーに基づいて生成された第１のトライ構造を保持する保持手段と、前記保持手段に保持されている前記第１のトライ構造を参照して、前記検索キーから該検索キーに対応する属性値を検索する検索手段とを有し、前記第１のトライ構造は各ノードに前記属性値が関連付けられており、前記検索手段は、前記検索キーに基づいて前記第１のトライ構造に対する検索を行い、最も深く到達したノードに関連付けられた前記属性値を検索結果とすることを特徴とする。
【発明の効果】
【０００９】
本発明によれば、検索に必要な記憶領域の容量を抑え、高速にデータを検索することが可能となる。
【図面の簡単な説明】
【００１０】
検索キーと属性値との対応関係の例を示す図である。
図１に示した例の検索を行うためのトライ構造を説明する図である。
本実施形態における情報処理装置のハードウェア構成例を示す図である。
第１の実施形態における情報処理装置の機能構成例を示す図である。
第１の実施形態におけるトライ構造を説明する図である。
第２の実施形態における情報処理装置の機能構成例を示す図である。
第２の実施形態におけるトライ構造を説明する図である。
第２の実施形態における登録処理の流れを説明する図である。
第２の実施形態におけるトライ構造を説明する図である。
第３の実施形態におけるトライ構造を説明する図である。
第３の実施形態における登録処理の流れを説明する図である。
第４の実施形態における情報処理装置を説明する図である。
第５の実施形態における情報処理装置の機能構成例を示す図である。
第５の実施形態における登録処理及び検索処理の流れを説明する図である。
第６の実施形態における登録処理の流れを説明する図である。
第６の実施形態における登録処理の流れを説明する図である。
第７の実施形態における決定処理の流れを説明する図である。
第８の実施形態における検索キーと複数の属性値の対応関係の例を示す図である。
第８の実施形態におけるトライ構造を説明する図である。
機械学習用の画像データの保存状態の例を示す図である。
【発明を実施するための形態】
（【００１１】以降は省略されています）

関連特許