著者

竹本 卓 竹中 康晴 皆川 勉 小泉 友弘 牛島 康之 柳田 直昭 小原 靖生 田中 幸一 藤田 康彦

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告システムLSI設計技術(SLDM) (ISSN:09196072)

巻号頁・発行日

vol.2004, no.102, pp.75-80, 2004-10-22

被引用文献数

2

---

3.5Mpolygon/secの3DCGエンジン、15fps@QVGAのMPEG4 codecエンジン、最大2MpixelのJPEGエンジン、カメラI/F、SDカードI/F、LCD I/F、および20MbitのDRAMを1chipに集積した携帯機器向けメディアプロセッサT4Gの開発について述べる。3DCGエンジンは東芝のコンフィギュアラブルプロセッサMePを応用することにより実現されている。DRAMを内蔵したことにより、3Dエンジンとメモリ間のバンド幅は2GByte/secに達する。このチップでは、0.13um CMOS DRAM混載プロセスを使用し、20Mtransistorのロジックと20MbitのDRAMを集積した。3DCG処理時の最大消費電力は170mWである。A media processor named T4G is described. T4G integrates 3.5M polygon/sec 3D Graphic engine, 15fps@QVGA MPEG4 engine, 2M pixel JPEG engine and 20Mbit DRAM into a single chip. It also provides several peripheral interfaces such as Camera I/F and LCDC. The 3D graphics engine was designed based on a Toshiba's configurable processor MeP (Media embedded Processor). Using eDRAM, the bandwidth between the 3D engine and the frame buffer reaches 2GByte/sec. This chip is fabricated using 0.13um CMOS technology and consumes maximum 170mW during 3D graphics operation.

著者

松延 直美 水森 龍太 蔡東生

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告グラフィクスとCAD(CG) (ISSN:09196072)

巻号頁・発行日

vol.2003, no.86, pp.59-64, 2003-08-18

被引用文献数

2

---

CGで群れの振る舞いを作成する代表的な方法としてBoidアルゴリズムが知られている.しかし,このアルゴリズムは確率的要素を持たない為,一度安定した状態になると経路の設定が単調になってしまうという問題がある.そこで,本研究では群れを生成する代表的生物であり生物学の分野でも研究されている魚類に注目し,魚類の特徴をBoidアルゴリズムに加え,さらに自然界によく見られる自己組織化理論を用いてゆらぎを加えることにより,群れの動きをより写実的に表現する手法を提案する.また,群れが敵に襲われた際の個体間の情報伝達や逃避行動の表現に関しても,自己組織化理論を用いて試みる.Boid algorithm is a typical technique of creating behavior of a group by CG. However, since this algorithm does not have a probable factor, when a group is stabilized, the routes of objects becomes monotonous. So, We propose the technique of creating behavior of a group with reality by adding the feature of self-organization criticality system to Boid algorithm. Self-organization criticality system is one of the features of nature. Then, We propose also the technique of the communication between the objects and expression of escape action when a group is attacked by the enemy by self-organization criticality system.

著者

江口 悠利 中川 智尋 太田 賢 竹下 敦

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告システムLSI設計技術(SLDM) (ISSN:09196072)

巻号頁・発行日

vol.2008, no.32, pp.215-220, 2008-03-28

---

携帯電話の高機能化と共に最近ではPCのようにユーザが自由にネイティブコードのアプリを追加して端末をカスタマイズ可能なオープン端末(スマートフォンと呼ぶ)も増加している.一方で,そのオープン性の代償としてスマートフォンには情報漏洩等の懸念があり,通常の携帯電話と同等の安全性を保つことは難しい.オープン性と安全性を両立する手段として,マルチOS技術があるが,本稿では性能面に優れ,既存OSの修正インパクトが少ない,OSのサスペンド機能を利用したOS切り替え方式に着目する.この方式は,一方のOSが実行状態の際には,他方のOSは全て休止状態となる特徴がある.休止状態のOSはメール着信,電話着信不能であるため,携帯電話に適用する際には,実行中のOSと協調して着信を処理する機構,OS間の通信機構が必要となる.しかし,従来のOS間通信方式はOSの並行動作を想定しているため,OS切り替え環境には適用できないOS切り替え環境に対応したOS間通信方式を設計,評価ボードに実装した.遅延・スループットの評価の結果,提案方式は着信通知等の少量データ転送に適用可能であること,インタラクティブな通信には不適であることを確認した.Cellular equipment gets high-performance, and smartphone gets attention in customizations to add-on native code applications like a PC. Unlike cell phone, it is difficult to avoid threats of compromising smartphone. We use multiple-OS technology to combine open environment like smartphone and secure environment like cell phone. As a result of comparison of several technologies in terms of performance, development cost and power consumption, we select OS Switching that uses Suspend/Resume function. This has a restriction that whenever an OS executed, any other OSes are suspended. Suspend OS cannot receive any mails and phone calls. Cellular equipment must be able to receive mails and phone calls to redirect them from application in executing OS to application in suspend OS by using Inter-OS Communication. However, existing Inter-OS communication method is not suitable for OS switching. Therefore, we propose an Inter-OS communication method to cooperate with application programs in OS Switching. As a result of experimentation, our method is not suitable interactive communication, but suitable for a small mount of data communication without switching OS to notificate incoming mails.

著者

繁在家 学 鷲崎 弘宜

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告ソフトウェア工学(SE) (ISSN:09196072)

巻号頁・発行日

vol.2008, no.55, pp.33-40, 2008-06-12

---

ソフトウェア中心システムの開発における品質要求は,要求分析の段階で明確に識別し,さらにはソフトウェアのアーキテクチャ分析・設計において明示的に扱うことではじめて実現される.また,属人性の排除,トレーサビリティを考慮したアーキテクチャ分析・設計は,ソフトウェア工学の手法を適用する必要がある.しかし,各工程に対して複数の手法を適応する場合,手法間の整合性を考慮する必要があり,手法を適用する阻害要因となっている.上述の背景を踏まえ,本稿では,簡単な WEB システムの開発を事例として,複数の手法を用いた品質要求駆動型のアーキテクチャ分析・設計手法を提案する.具体的には,要求分析手法である KAOS,アーキテクチャ設計手法である品質特性駆動型設計(Attribute-Driven Design)の整合性を考慮し,独自拡張を加えたアーキテクチャ分析・設計手法を提案する.さらに,提案手法は,品質要求を考慮したアーキテクチャ分析・設計を達成する中で,アスペクト指向型アーキテクチャを抽出する技法を取り扱う.Quality requirements for a development of a software centered system should be recognized in a process of requirements analysis and also those requirements are realized by dealt with explicitly in a software architecture analysis and design process. A method of software engineering should be used in the software architecture analysis and design process to clear individual techniques and realize traceability. However, if several methods are used in each process, consistency between methods should be considered. This is a disincentive to adapt methods into the development. With the background above, in this paper, we propose a quality requirement driven method of the architecture analysis and design process with several methods using a example of a simple web system development. Specifically, we propose it with unique expansion and considering consistency between KAOS, which is a method of requirements analysis, and ADD, which is a method of attribute-driven design. Furthermore, this method we propose includes a technique of picking up aspect oriented architecture during the architecture analysis and design process with satisfaction of quality requirements.

著者

水戸 将弥 藤田 聡

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告ヒューマンコンピュータインタラクション(HCI) (ISSN:09196072)

巻号頁・発行日

vol.2001, no.108, pp.101-108, 2001-11-15

---

近年の情報処理技術の飛躍的な進歩に伴い、コンピュータを介した人間同士のコミュニケーションが 日常生活の様々な局面で用いられ始めている。本稿では、ユーザとシステムとの間の知的なインタフェースを実現するためのひとつのアプローチとして、ユーザからの非明示的な要求を自動的に獲得するための手法の提案をおこなう。要求の獲得は、ユーザとの対話の中で得られる選択の系列をもとにおこなわれる。また提案手法の応用例として勤務表作成問題をとりあげ、労働者の出勤パターンに関する嗜好の自動獲得を試みる。In this paper, we propose a method for acquiring inexplicit requirements from users via the interaction between users and the computer system. The proposed method is applied to the shift scheduling problem, that is the problem of assigning shift to each labor in such a way that as many requirements are satisfied as possible. An outline of the prototype system that is presently under construction is also given.

著者

惣宇利卓寛 紫合 治

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告ソフトウェア工学(SE) (ISSN:09196072)

巻号頁・発行日

vol.2007, no.97, pp.15-22, 2007-09-27

---

本論文では、既存の Web アプリケーションに HTML タグの属性を付加することによって、求める Web サービスを簡単に構築する方式について提案する。この方式は、従来の Web ラッパー方式に比べて、Web アプリケーション自身に手を加えることが必要という問題I土あるが、頻繁に行われる Web ページの改訂に対しても確実に誤りなくデータ抽出できるため、より実用性が高いといえる。また、複数の Web ページにまたがるデータ抽出も容易にできる。この方式による Web サービス変換システムを開発し、既存の Web サイトから Web サービスが容易に構築できることを確認した。This paper proposes a new method and a system to obtain required Web services by converting existing Web applications into Web services using new HTML tag attributes. This method extracts requested data from Web pages correctly and precisely when the original Web application is modified, while existing Web page wrapping method frequently requires the rule changes. Also the proposed method can treat multi-paged data extraction effectively. We have developed the Web service conversion system based on the proposed method, and recognized that the method successfully converts existing Web applications into required Web services.

著者

山本 泰則 中川 隆

出版者

情報処理学会

雑誌

情報処理学会研究報告人文科学とコンピュータ(CH) (ISSN:09196072)

巻号頁・発行日

vol.2005, no.76, pp.47-54, 2005-07-29

被引用文献数

6

---

人文科学系のデータベースを構造のちがいを越えて、また分野横断的に検索するために、すべてのデータをDublin Coreメタデータで記述するという方法をとってきた。しかし、Dublin Coreは博物館の標本資料のような物理的な実態を記述するには、必ずしも適しているわけではない。本稿では、国立民族学博物館の民族標本資料を例に、その情報をDublin Coreへ変換方法を提案し、その有効性と課題について議論する。We are investigating the cross-domain retrieval system for studies in humanities where the cross-database search is realized by converting the fields of each databases to the Dublin Core metadata elements. But the Dublin Core is not necessarily suitable to describe the physical objects like in the museum. This report proposes an example to map the information of ethnographic objects in the National Museum of Ethnology to the Dublin Core, and discusses the feasibility of the mapping for cross-database search in humanities.

著者

高久 雅生 江草 由佳 宇陀 則彦 石塚 英弘

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告情報学基礎(FI) (ISSN:09196072)

巻号頁・発行日

vol.1999, no.102, pp.119-128, 1999-11-30

---

Z39.50は情報検索のための国際標準プロトコルで、現在各国で実装が進められつつある。筆者らはこのZ39.50プロトコルを通じてDublin Core Matadata Element Setを共通スキーマとして検索・返戻できる書誌データ検索システムを構築した。今回、対象としたデータはJAPAN/MARCの日本語書誌データで、これをDublin Coreに変換した。本稿ではこのZ39.50検索システムについて報告する。This paper describes a Z39.50-based information retrieval system which can search bibliographic data through the Dublin Core Metadata Element Set as a common schema. The system consists of a metadata conversion module, a Z39.50 server, and a database module. The metadata conversion module converts from JAPAN/MARC records to Dublin Core metadata represented by RDF. The Z39.50 server searches through Dublin Core access point. The database module parses Dublin Core metadata written in XML, and makes index of metadata.

著者

神田 直之 駒谷 和範 中野 幹生 中臺 一博 辻野 広司 尾形 哲也 奥乃 博

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告音声言語情報処理(SLP) (ISSN:09196072)

巻号頁・発行日

vol.2006, no.12, pp.55-60, 2006-02-04

被引用文献数

4

---

複数のドメインを扱う音声対話システムにおいて,対話の文脈や進行に関する特徴量を導入してより精度よくドメイン選択を行う手法を開発したので報告する.本稿ではドメイン選択問題を,応答すべきドメインが,(I)ひとつ前の応答を行ったドメイン,(II)音声認識結果に対する最尤のドメイン,(III)それ以外のいずれかのドメイン,のどれに該当するかを判別する問題と捉える.ドメイン選択の正解を与えた対話データから,対話の文脈や進行に関する特徴量を用いて上記を判別する決定木を学習することにより,ドメイン選択器を構成した.5ドメインのマルチドメイン音声対話システムを用いた10名の被験者による評価実験の結果,音声認識尤度に基づく従来のドメイン選択手法に比べ,ドメイン選択誤りが11.6%削減された.We have developed a robust domain selection method using dialogue history in multi-domain spoken dialogue systems. We define domain selection as classifying problem among (I) the domain in the previous turn, (II) the domain in which N-best speech recognition results can be accepted with the highest recognition score, (III) other domains. We constructed a classifier by decision tree learning with dialogue corpus. The experimental result using 10 subjects shows that our method could reduced 11.6% domain selection error, compared with a conventional method using speech recognition likelihoods only.

著者

水野 智士 高木 浩吉 小暮 悟 伊藤 敏彦 甲斐 充彦 小西 達裕 伊東 幸宏

出版者

情報処理学会

雑誌

情報処理学会研究報告音声言語情報処理(SLP) (ISSN:09196072)

巻号頁・発行日

vol.2005, no.12, pp.77-82, 2005-02-05

被引用文献数

5

---

近年の音声認識、言語理解技術、及びコンピュータ性能の向上によって、音声を用いるインタフェースやタスク指向型の対話システムが利用されるようになってきた。そんな中で、より一般的にシステムが利用されるようになるには、より頑健な言語理解が必要となる。本稿では、より頑健な意味理解を実現するために、音声認識信頼と対話履歴を利用して、ユーザ発話意図の推定を行う手法について記述する。本研究では、言語理解の頑健さを向上させるために、対話履歴において、県名や市町村名など、どのカテゴリについての発話がされたのかを識別する。その識別結果と、認識結果のn-bestを利用して言語理解結果を生成する。これを実現する場合、カテゴリ識別の精度がそのまま言語理解精度に影響する。そこで、ユーザの発話意図を推定することで、カテゴリ識別精度の向上を図り言語理解精度向上を目指した。評価実験を行い、音声認識の1-bestをそのまま利用する言語理解手法よりも提案手法のほうが、言語理解精度が高くなることを示した。The spoken dialogue interface and the task oriented dialogue system has come to be used by improving the speech recognition, the language understanding technologies, and the computer performance. We need a more robust language understanding for the system to come to be used more generally. Our paper deals with speech intent presumption method using the confidence score of speech recognition and dialogue history for robust meaning understanding. This language understanding results are generated by using the speech recognition results (n-best) and the identification results. Thus, the accuracy of the category identification influences the language understanding accuracy. Then, we used the presumption of user's speech intention in order to improve the language understanding accuracy. As the result of evaluation experiment, we show that the language understanding performance used our proposed method is higher than the language understanding method which simply gives priority to the first hypothesis of a n-best.

著者

山村 周史 青木 孝 安藤寿茂

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告計算機アーキテクチャ(ARC) (ISSN:09196072)

巻号頁・発行日

vol.2007, no.79, pp.61-66, 2007-08-01

被引用文献数

2

---

我々は,ペタスケールシステム向けのプロセッサアーキテクチャの検討を行っている.ペタスケール規模の科学技術計算アプリケーションを高速に実行するためには,大量の浮動小数点演算を高効率で処理できなければならない.これを実現するために,我々は,既存のスカラプロセッサに対して, SIMD 演算ユニットを拡張装備するアーキテクチャを提案する. HPL および PHASE の主要計算ルーチンを対象として,シミュレーションにより本アーキテクチャの性能評価を行い,その有効性について述べる.A processor for a peta-scale supercomputer requires achieving high floating point performance with high energy efficiency. To meet these requirements, we propose an architecture with the combination of a high performance superscalar processor core and wide SIMD processing elements. In this paper, we evaluate its performance and effectiveness with an architecture simulator using math kernels of HPL and PHASE.

著者

西野 順二

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告ゲーム情報学(GI) (ISSN:09196072)

巻号頁・発行日

vol.2007, no.20, pp.33-39, 2007-03-05

被引用文献数

6

---

日本固有のカードゲーム大貧民の戦略について考察した。不完全情報多人数ゲームであり、必勝アルゴリズムの導出は難しい。自動プレイヤの終盤データベースの構築を目指し、10枚2人および10枚3人について、1枚プレイに限定して探索した。効率的な探索のため、大貧民の特性に基づいた手の同相性を定義して、パターン数の縮約を行った。パタンの縮約を行い、2人については5 741通り、3人については1 428 867通りに縮約した。探索の結果2人では3 518通り、3人では621 368通りの必勝パタンがあることが明らかになった。We introduce a reduction algorithm using hand structure under DAIHIMIN game rule. 10 cards with 2 players distribution and 10 cards with 3 players distribution are solved and shown. 2 players reduced pattern is 5,714 and 3 players reduced pattern is 1,428,867. As a searching result, the winning distributions are 5,741 patterns for 2 players and, 621,368 patterns for 3 players.

著者

中野 鐵兵 佐々木 浩 藤江 真也 小林 哲則

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告音声言語情報処理(SLP) (ISSN:09196072)

巻号頁・発行日

vol.2008, no.46, pp.77-84, 2008-05-15

被引用文献数

5

---

音声・言語アプリケーションにおける従来の語彙情報作成手法の問題点を解決するため,集合知を利用した語彙情報の収集・共有・管理システムを提案する.具体的には,語彙情報を集中管理するためのオンラインデータベースシステムを構築し,それを利用者に公開する.提案システムでは,Web 資源からの語彙情報の自動収集の枠組みを備え,データの集約を図る.また,アプリケーション用語彙の新規作成から,その継続的な更新まで包括的な解法を提供し,これまで各々の開発者がアプリケーション毎に用意していた語彙定義のプロセスの一元化を図る.さらに,インタフェースを広く公開し,アプリケーション間の語彙定義の共有や,アプリケーションで使用する語彙の自動更新のサポートを図る.本稿では,実際に提案システムの実装として開発されたプロトタイプシステムと,提案システムによって実際に有効な語彙リストの生成が可能である事を示した評価実験について述べる.In order to solve the problems of the conventional approach of designing lexicons, we propose a new approach: using a lexical data collection, sharing, and management system using collective intelligence. In particular, we construct and operate a new online database system for lexical informations. The proposed system is designed as a data intensive system so that it can collect lexical information from all web-based resources. Also, the system provides the comprehensive solution of designing lexicons so that the designing processes of lexicons can be standardized. Besides, the system interface is published so that lexical informations are shared by many applications. In this paper, the prototype system developed based on the proposed approach and the feasibility test for designing lexicons are described. The assessment result showed that the proper lexicons can be generated from the proposed system.

著者

後藤崇行 常松 祐一 渡辺 裕

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告オーディオビジュアル複合情報処理(AVM) (ISSN:09196072)

巻号頁・発行日

vol.2005, no.66, pp.31-36, 2005-07-08

---

フィルムグレインは、フィルムで撮影したコンテンツ特有の模様である。一般に雑音成分として捉えられがちだが、フィルムグレインによってフィルムコンテンツの質感を表現することができるため、質感を表現したい場合、除去されないことが望ましい。しかし、フィルムグレインを含んだ画像に圧縮符号化を施すと符号化による影響を受け失われてしまう。特に近年標準化された動画像符号化方式H.264/AVCにおいては、デブロッキングフィルタや4x4整数変換により、フィルムグレインが失われやすくなっている。H.264/AVCの拡張方式FRExt(Fidelity Range Extensions) では、映画コンテンツなどフィルムグレインを含む高解像度画像において画質改善を行う様々な符号化ツールが追加された。そこで筆者らは、更なるフィルムグレインの再現性を考慮したH.264/AVC符号化方式について検討してきた。本稿では、符号化モード決定のコスト値について考察し、フィルムグレインの再現性を更に向上させる手法の検討を行う。Film grain is a specific texture of film conttents. Though it generally tends to be recognized as a noise,it is preferable for film grain not to be removed to express the feeling of quality of film contents. However,film grain is influenced and lost easily by encoding. Especially,in H.264/AVC which is the state-of-the-art video coding standard,it is more easier for film grain to be lost by performing de-blocking filter and 4x4 integer-transform. In FRExt(Fidelity Range Extensions) which extended the conventional H.264/AVC,various coding tools were added to improve the quality of high definition size images such as movies containing film grain. We have been studying the H.264/AVC encoding method considering the fidelity of film grain. In this paper we consider the method to improve the fidelity of the film grain further by changing the cost value of the encoding mode decision.

著者

宇田 隆哉 伊藤 雅仁 淡谷 浩平 重野 寛 松下 温

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告コンピュータセキュリティ(CSEC) (ISSN:09196072)

巻号頁・発行日

vol.2002, no.12, pp.133-138, 2002-02-14

被引用文献数

1

---

本論文は携帯型端末向け電子チケットシステムの提案である。本提案のシステムは商用に耐えうる強固なセキュリティを持ち、既存の携帯電話端末に特別なハードウェアを加えることなく、携帯型端末の機種を問わず電子チケットの発行から使用までを安全に管理できる。利用者は、携帯型端末からチケット発行サーバにアクセスし希望するチケットを購入した後、その携帯型端末画面上に電子チケットを表示し入場ゲートを通過する。本論文では、三次元パターン通信を用いることにより、電子チケットに付加した公開鍵暗号署名を任意の画面解像度を持つ端末上で扱うことを可能にした。本提案のシステムは、イベント会場の入場券や鉄道の切符などに幅広く利用可能である。A digital ticket system for cellular phones is described in this paper. The system has strong security for commercial use and has flexibility to support any cellular phone and PDA. A user can deal with everything related with a ticket such as issue, payment and showing with his cellular phone. He accesses to the ticket issuing server to get a ticket and shows that ticket holding his cellular phone to the ticket reader at an entrance gate. 3-D pattern is used in order to show a ticket, and no adding hardware module is needed. This system can be used for concert ticket, train ticket, etc.

著者

吉原 潤 加藤 和彦 奈良崎 清彦

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告データベースシステム(DBS) (ISSN:09196072)

巻号頁・発行日

vol.2000, no.69, pp.41-48, 2000-07-26

---

suffix arrayはテキストの接尾辞のポインタを接尾辞の辞書順に並べたもので,任意の部分文字列検索を高速に行うことができるが,更新のオーバーヘッドが大きい.本論文ではsuffix arrayを効率的に更新する方式として,我々が以前提案したインクリメンタルな更新方式を分散並列化をした方式を提案する.この方式ではsuffix arrayに含まれる接尾辞を辞書順のある範囲で分割し,各ノードに担当区間を割り当てる.繰り返される更新に伴い各ノードの担当区間のサイズの不均衡が生じるため,動的に担当区間の変更を行ない更新処理の負荷を均等化する.また,単純に均等なサイズに分割して連続した区間をノードに割り当てた場合に検索要求の分布に偏りが生じることを示し,検索要求の偏りを軽減する分割方法を提案した.A suffix array is a full-text index data structure which is efficient for retrieving any substring of text, but requires a lot of overhead for updating it. In this paper, we propose an efficient updating scheme of suffix arrays. In this scheme, a suffix array is split into some sections and each section is assigned to a node. When updating, the incremental updating scheme which we already proposed runs in parallel on each node. To balance the sizes of sections after repeated updating, boundaries of sections are changed dynamically. Furthremore we propose the spliting scheme of suffix arrays to balance the retrieval prosessing load.

著者

定兼 邦彦

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2000, no.84, pp.73-80, 2000-09-21

---

全文検索のための索引である接尾辞配列は,他の全文検索索引と比較すると省スペースであるが,転置ファイルのような単語索引と比較するとサイズが大きい.この問題を解決するために圧縮接尾辞配列が提案されたが,検索にはテキスト自身も必要であるため,索引サイズはテキストよりも小さくならない.本稿では圧縮接尾辞配列を用いた検索アルゴリズムを,テキスト自身が不要になるように変更する.また,テキスト全体やその一部を圧縮接尾辞配列から復元するアルゴリズムを提案する.これにより,テキストの圧縮と高速な検索の両立が可能となる.A compressed text database based on the compressed suffix array is proposed. The compressed suffix array of Grossi and Vitter occupies only O(n) bits for a text of length n; however it also uses the text itself that occupies O(n log|Σ|) bits for the alphabet Σ. On the other hand, our data structure does not use the text itself, and supports important operations for text databases: inverse, search and decompress. Our algorithms can find occ occurrences of any substring P of the text in O(|P|log n + occ log^ε n) time and decompress a part of the text of length l in O(l+log^ε n) time for any fixed 1 > ε > 0. Our data structure occupies only 1/εnH_0 + n(6+3logH_0)<log^εn>/<log^εn-1>+2n+|Σ|log|Σ|+o(n) bits where H_0〓log|Σ| is the order-0 entropy of the text.

著者

高橋 慎 吉原 潤 加藤 和彦

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告データベースシステム(DBS) (ISSN:09196072)

巻号頁・発行日

vol.2001, no.70, pp.53-60, 2001-07-17

---

suffix arrayはテキストの接尾辞のポインタを辞書順に並べかえたもので,任意の部分文字列を高速に検索できるが,静的なデータ構造のため,更新のオーバーヘッドが大きい.我々は以前,インクリメンタルな更新方式を提案したが,この方式が残す問題の一つは,差分情報を用いて作成したsuffix arrayを一つにまとめる再構成処理のオーバーヘッドが大きいことである.本論文ではsuffix arrayを分散配置することでsuffix arrayのサイズを小さくし,再構成処理の高速化を図る分散並列処理方式について述べる.実装を用いた実験結果により,再構成処理の高速化と検索時の性能の向上についての評価を行なう.Suffix array is a full-text index structure efficient to retrieve any substring of the indexed text, but requires significant overheads to update. Previously we proposed an incremental updating scheme for suffix arrays. One of the remaining problems is the overheads to reconstruct large suffix arrays. Frequency of the reconstruction operation is reduced in the incremental updating scheme, but requires considerable overheads. This paper presents a scheme to incorporate parallel and distributed processing into the incremental updating scheme. In the scheme, decomposed suffix arrays are distributed to several machines, so that the reconstruction overheads are reduced and throughput for the retrieval operations is increased. We show some experimental results performed to evaluate the proposed scheme.

著者

定兼 邦彦 宋永健 姚兆明 林徳華

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2001, no.115, pp.19-26, 2001-11-27

---

文字列検索のための索引として接尾辞配列が有名であるが,そのサイズが問題となっている.圧縮接尾辞配列はそれを圧縮したもので,通常は元の文字列よりもサイズが小さくなる.ただし圧縮接尾辞配列を構成するアルゴリズムとしては一旦接尾辞配列を構成するものしか存在しないため,一時的だが大量のメモリが必要となる.本研究では長さ n の文字列に対し,$O(n)$ ビットの一時記憶を用いる O(n|Σ|log n)$ 時間 (|Σ|はアルファベットサイズ)のアルゴリズムを提案する.このアルゴリズムは短い文字列に対する圧縮接尾辞配列から長い文字列に対するものを徐々に作成するものになっており,データの追加を容易に行える点も利点である.Though the suffix array is now famous as an index for string matching, it has a problem of its size. The compressed suffix array is a compressed version of the suffix array whose size is usually smaller than the size of the string. However all known algorithms construct the compressed suffix arrays via uncompressed suffix arrays, which temporarily occupy huge amount of memory. This paper proposes an O(n|Σ| log n) time algorithm to construct a compressed suffix array of a string of length n on alphabet Σ using only O(n) bits temporal space. This is an incremental algorithm, which construct the compressed suffix array of a concatenation of a character and a string from that of the string. Therefore this algorithm also has the merit of appending data quickly.

著者

中嶋 将太 福井 正博

出版者

一般社団法人情報処理学会

雑誌

研究報告システムLSI設計技術(SLDM) (ISSN:09196072)

巻号頁・発行日

vol.2009, no.7, pp.129-134, 2009-01-22

---

近年, LSI の微細化,高性能化に伴い,設計時間の短期化や高性能を維持したままでの低消費電力化といったことが求められるようになった.これらの要求をかなえるために,デザインプロセスにおいて,高いレベルですばやく電力や遅延時間を見積もるということが非常に重要である.本稿では RTL における遅延マクロモデルの提案を行っている.このモデルはVdd, Vt のばらつきに対してトランジスタレベル並みの精度を目標としている.モデル化の手法,及び寄生容量の考慮などに関する検討内容と実験結果について示す.Recent, due to the rapid progress of LSI technology, efficient and low-power designs have been highly required to keep high performance. To satisfy these requests, it is very important to be able to explore the value of power and delay at a high-level early in the design process. This paper proposes a new efficient RTL delay macro-model to address these recent problems. The goal is to provide transistor-level accuracy at the RTL with Vt and Vdd variability. The Modeling algorithm that considers parasitic capacitances and experimental results are discussed.