著者

高橋 慎 吉原 潤 加藤 和彦

出版者

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

雑誌

情報処理学会研究報告データベースシステム(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.

著者

安積 裕樹 川副 真治 安部 潤一郎 有村 博紀 有川 節夫

出版者

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

雑誌

情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)

巻号頁・発行日

vol.42, no.14, pp.14-24, 2001-12-15

---

本稿では,分散記憶型並列計算機上での効率の良い全文索引構築法について考察する.接尾辞配列は,最近提案された高機能全文索引であり,情報検索や遺伝子情報などに広い応用を持つ.本稿では,分散記憶型並列計算機上での効率の良い接尾辞配列構築法を提案する.Baeza-Yates-Gonnet-Sinder(BGS )アルゴリズムは,最も広く使われている外部記憶上の構築アルゴリズムである.このBGSアルゴリズムを並列化し,効率の良い並列構築アルゴリズムを与える.このアルゴリズムは,並列計算機時間と通信量に関して,BGS の最適な並列化になっており,従来からあるBGS の並列版のRiberio-Kitajima-Ziviani (RKZ )アルゴリズムに比べてより高速である.In this paper,we study efficient parallel construction of full-text indexing structures for large text data.The suffix array is a compact full-text indexing structure that is useful in information retrieval and bio-informatics.We propose an efficient parallel algorithm for constructing suffix arrays on distributed memory parallel computers.This algorithm is a parallel implementation of the well-known external memory algorithm,called Baeza-Yates-Gonnet-Sinder (BGS)algorithm.By theoretical analysis,we show that our algorithm runs more efficiently than Riberio-Kitajima-Ziviani (RKZ) algorithm,another parallel implementation of the BGS algorithm,in terms of parallel time and communication complexities.

著者

内山 将夫 井佐原 均

出版者

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

雑誌

情報処理学会論文誌データベース(TOD) (ISSN:18827799)

巻号頁・発行日

vol.43, no.9, pp.1-14, 2002-09-15

---

近似文字列照合による全文検索では,入力パターンと一定以下の編集距離にある部分テキストすべてをテキストから検索する.近似文字列照合による全文検索は,テキストを接尾辞トライにより索引付けし,それを利用して検索することにより実現できる.しかし,接尾辞トライの占める空間領域は大きいため,接尾辞配列を索引として利用することもある.接尾辞配列を索引として利用する場合には,従来研究では,接尾辞トライ上での探索を接尾辞配列上での2分探索により模擬している.それに対して,本稿では,2分探索ではなく,補助的な配列を用いることにより,高速に,接尾辞トライ上での探索を模擬することができる手法を提案した.さらに,2分探索による方法を利用した場合と提案手法を利用した場合とにおける検索速度を実験的に測定し,提案手法の方が検索速度が速いことを示した.Given a text and an input pattern, the goal of full-text approximate string matching is to search for all parts of the text that match the pattern. Full-text approximate string matching can be performed using a suffix trie as an index of the text. A suffix trie, however, is relatively large. So, a suffix array, which is a compact representation of a suffix trie, is often used to simulate searches on a suffix trie. A binary search algorithm is used to search the array. A method is described in this paper that uses an auxiliary array to simulate searches on a suffix trie. The method does not use a binary search algorithm so that it can perform a faster simulation. Experiments showed that the proposed method is faster than one using a binary search algorithm.

著者

韓 永楷 定兼 邦彦 宋 永健

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.104, no.55, pp.1-7, 2004-05-13

---

文字列検索のためのデータ構造としては接尾辞本,接尾辞配列などが有名であるが,これらにはデータ構造の必要とする記他領域が大きいという欠点がある.近年GrossiとVitterによって提案された圧縮接尾辞配列は検索速度を落とすことなく接尾辞配列を圧縮したものであり,サイズは長さnの文字列に対してO(nlog|A|)ビット(Aはアルファベット)である.これは文字列のサイズの線形となっている.圧鎔接尾辞配列を構築するアルゴリズムとして,Honらの提案したO(nlog|A|)ビットの一時的な記他領域を使用するO(nloglogUI)時間アルゴリズムが存在する,これは領域に関しては最適だが時間に関しては最適ではない,本論文ではアルファベットサイズが小さいとき(log|A| = O((log log n)^<1-ε>))に0(n)時間で動くアルゴリズムを提案する.

著者

後藤 隆元 小野 廣隆 定兼 邦彦 山下 雅史

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.105, no.72, pp.1-8, 2005-05-13

---

計算機の性能の向上や, インターネットの普及により, 我々が扱うデータの量は急速に増加している.そしてそれに伴い, 大きなデータの中から必要なデータを探し出す機会も多くなっている.しかし, 扱うデータの量が増えるにつれて検索に必要な時間計算量や空間計算量も増加するため, より効率の良い検索アルゴリズムが求められている.一般に, 文字列検索を行う際にはあらかじめ対象となるファイルに対して索引付けを行って検索しやすくしている.そこで, 本研究では複数のファイルを格納した文書データベースに対して, 圧縮接尾辞配列を用いた索引付けを行うことにより, 時間的にも空間的にも効率が良く, 検索漏れが生じない文字列検索アルゴリズムを提案する.

著者

成澤 和志 稲永 俊介 坂内 英夫 竹田 正幸

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.107, no.24, pp.63-70, 2007-04-19

被引用文献数

1

---

本論文では,Blumerらによって提案された同値関係による同値類を計算する問題を考える.Blumerらはコンパクト有向無閉路文字列グラフ(CDAWG)と呼ばれる索引構造を定義するために同値類を利用した.同値類は本質的に等しく出現する冗長な部分文字列を集めた集合であるため,テキスト解析において有用である.本論文では,接尾辞配列を用いて同値類を計算するアルゴリズムを提案する.提案アルゴリズムでは,接尾辞木および接尾辞リンク木の巡回を模倣するため接尾辞配列の他に2つの補助配列を使用するが,これら以外のデータ構造を必要としない.このアルゴリズムは入力文字列に対して,線形時間および線形領域で動作する.本論文では,提案アルゴリズムと接尾辞木およびコンパクト有向無閉路文字列を用いたアルゴリズムとの計算時間・計算領域を計算機実験によって比較する.

著者

高橋 慎 加藤 和彦

出版者

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

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.44, no.11, pp.268-276, 2003-08-15

---

Suffix arrayはテキストの接尾辞のポインタを辞書順に並べ替えたもので,任意の部分文字列を高速に検索できるが,静的なデータ構造のため,更新時のオーバヘッドが大きい.我々は以前,この問題を解決するインクリメンタルな更新方式を提案したが,この方式が残す問題点の1つは,インクリメンタルに追加される情報を用いて作成した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 to solve this problem. One of the remaining problems is the overheads to integrate adding suffix array and existing large suffix array in update operation. Frequency of the integrate operation is reduced in the incremental updating scheme, but it still 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 integration overheads are reduced and throughput for the retrieval operations is increased. We show some experimental results conducted to evaluate the proposed scheme.

著者

秋川 雅史

出版者

文芸春秋

雑誌

週刊文春

巻号頁・発行日

vol.51, no.44, pp.94-97, 2009-11-19

著者

ブラウネル ジナン

出版者

阪急コミュニケーションズ

雑誌

ニューズウィーク (ISSN:09122001)

巻号頁・発行日

vol.24, no.45, 2009-11-25

著者

野中 美和 桜井 幸子 今井 伸恵 青砥 広幸 竹内 尚子 矢後 和夫

出版者

日本医療薬学会

雑誌

日本病院薬学会年会講演要旨集

巻号頁・発行日

vol.6, pp.168-169, 1996-08-21

著者

川本 治 宮崎 毅 中野 政詩

出版者

The Japanese Society of Irrigation, Drainage and Rural Engineering

雑誌

農業農村工学会論文集 (ISSN:18822789)

巻号頁・発行日

vol.77, no.4, pp.385-393, 2009-08-25

---

粘性土から成る農地斜面の長期安定問題における初生破壊解析を念頭に置いて,地すべり崩土の力学特性と変形の局所化に関する実測値を示した.不攪乱試料の圧密・排水三軸試験結果における中位のひずみ(軸ひずみ15%程度)では,せん断帯幅は微小亀裂に囲まれた粘土土塊の変形集中領域の幅として評価するのが適切であり,粒子径が重要な役割を果たす粒状体材料の場合とは異なる機構によってせん断帯が形成されると考えられた.この結果に基づいて田中による弾塑性有限要素モデルのパラメータ決定と三軸圧縮試験の有限要素解析を行った.浅層すべりの斜面中央部付近で採取された複数の試料の応力-ひずみ曲線は,過去の地すべり履歴を反映すると考えられる多様なパターンを示しており,有限要素解はこれらの供試体における平均的挙動を表現すると考えられた.

出版者

日経BP社

雑誌

日経コンストラクション (ISSN:09153470)

巻号頁・発行日

no.483, pp.66-67, 2009-11-13

著者

塚田 英晴 深澤 充 小迫 孝実 小針 大助 佐藤 衆介

出版者

日本草地学会

雑誌

日本草地学会誌 (ISSN:04475933)

巻号頁・発行日

vol.55, no.2, pp.166-169, 2009-07-15

---

飼料の国内自給率の向上や中山間地域の振興を図る一つの方策として、林地の畜産的利用が近年注目されている。一方、日本の森林は、多くの野生哺乳類の生息地として重要な役割を担っており、林地への放牧導入が林床植物の種構成や草冠構造への影響を通じて、野生哺乳類の生息環境の質や量にも変化をもたらすことも予想される。林地の野生哺乳類に対する牛による放牧の影響については報告例がほとんど認められないが、低木を含む放牧地での研究では、植生の被度、草高およびリターなどの減少を通じて小型哺乳類の個体数を減少させることが報告されている。また、牛以外の反芻動物による影響としては、シカ類の増加による森林植生の変化が、小型哺乳類相の貧弱化を招く可能性が英国の研究で指摘されている。したがって林地への牛の放牧導入を推進する上で、野生哺乳類と共存しうる林内放牧の適正水準に関する情報が重要となる。しかし、林内放牧が野生動物の生息に及ぼす影響に関する日本での研究報告はほとんどなされていない。本研究では、林地への乳牛の放牧を新たに導入した一農家の事例において、放牧が小型哺乳類に及ぼす影響に関し、捕獲数およびいくつかの環境指標をもとに評価したので報告する。

著者

廿楽 法 金子 信博

出版者

日本土壌動物学会

雑誌

Edaphologia (ISSN:03891445)

巻号頁・発行日

no.85, pp.7-12, 2009-08-31

著者

福田 栄紀 須山 哲男 澁谷 幸憲 八木 隆徳 目黒 良平

出版者

日本草地学会

雑誌

日本草地学会誌 (ISSN:04475933)

巻号頁・発行日

vol.55, no.2, pp.132-140, 2009-07-15

---

放牧牛がチシマザサ(以下、ササとする)優占植生中のスギ稚樹の生残に及ぼす影響を調べた。放牧共用林野内のスギ人工林に隣接するブナ林の空隙地に、禁牧区と放牧区を設定し、両区で放牧牛がササの生育、およびスギ稚樹の光環境、生残と樹高伸長に及ぼす影響を5年間比較した。禁牧区では、ササの被度と高さは急増して相対光量子束密度は低下し、スギ稚樹の生存率は禁牧3年目で急減した。一方、放牧区では、ササは採食されて生育が抑制されたため、良好な光環境が維持され、スギ稚樹の生存率と樹高伸長量は相対的に高く保たれた。放牧牛によるスギ稚樹の採食は稀で、踏圧や排糞による影響も軽微であった。放牧牛はササに対しては撹乱要因として作用したが、スギ稚樹に対しては作用しなかったため、ササに対する選択的生物撹乱要因と言える。スギの更新の成否は、ササが同所的に分布するブナ林床では、放牧牛の採食圧に強く依存する。

著者

桜井 幸子

出版者

公益社団法人日本数学教育学会

雑誌

日本数学教育学会誌. 臨時増刊, 総会特集号

巻号頁・発行日

vol.62, 1980-08-01

著者

桜井 幸子

出版者

公益社団法人日本数学教育学会

雑誌

日本数学教育学会誌. 臨時増刊, 総会特集号

巻号頁・発行日

vol.60, 1978-08-01

著者

櫻井 幸子 椎 崇 尾鳥 勝也 黒山 政一 矢後 和夫

出版者

日本医療薬学会

雑誌

日本病院薬学会年会講演要旨集

巻号頁・発行日

vol.7, 1997-08-15

著者

畑 友三郎 桜井 幸子 鈴木 越夫

出版者

公益社団法人日本数学教育学会

雑誌

日本数学教育学会誌 (ISSN:0021471X)

巻号頁・発行日

vol.60, no.6, pp.101-104, 1978-06-01