著者

惣宇利卓寛 紫合 治

出版者

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

雑誌

情報処理学会研究報告ソフトウェア工学(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.

著者

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

出版者

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

雑誌

情報処理学会研究報告情報学基礎(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.

著者

飯塚 肇

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.13, no.7, pp.467-473, 1972-07-15

著者

湯浅 敬

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.44, no.4, pp.432-433, 2003-04-15

---

1999年春から1年間,イギリスのブリストル研究所に出向し,2002年秋から現在のパロアルト研究所に移籍となりました.アメリカに来てまだ間もないのですが,これからシリコンバレーの情報を中心にお伝えしていく予定ですので,よろしくお願いします.

著者

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

出版者

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

雑誌

情報処理学会研究報告音声言語情報処理(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.

著者

山村 周史 青木 孝 安藤寿茂

出版者

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

雑誌

情報処理学会研究報告計算機アーキテクチャ(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.

著者

浅川 秀治 Erik Selberg

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.46, no.9, pp.1008-1015, 2005-09-15

被引用文献数

1

---

本稿では,2005年に新しくサービス開始されたMicrosoft社の独自開発MSN Search Engine について概要を述べる.まず,アーキテクチャの上位レベルの説明を行い,続いて基本的な設計目標について説明する.次に,ドキュメントのインデックス化とランク付けに使用した技術について述べる.特に,今回MSN Search Engineをスクラッチから開発したことで学んだことや,明らかになった問題点にサービス面,技術面の両方の観点から焦点を当て,最後にMicrosoft社の考える今後の検索エンジンの方向性について述べる.Webにおいて最も重要なサービスが検索エンジンであることから,本論分が今後の日本における検索エンジンの開発に役立つことを期待している.

著者

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

出版者

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

雑誌

情報処理学会研究報告音声言語情報処理(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.

著者

伊東 秀夫

出版者

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

雑誌

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

巻号頁・発行日

vol.41, no.1, pp.31-39, 2000-02-15

被引用文献数

3

---

Suffix arrayは文字列索引の一種であり,suffix treeに比べ単純でコンパクトなデータ構造を用いて実装できる.文字列処理に対して多くの優れた性質を持つsuffix arrayだが,特に大規模なテキストに対しては索引構築に多大な記憶量と計算コストを必要とし実用上の問題になっている.我々は,高速かつコンパクトなsuffix array構築法を提案する.そのキーとなるアイデアは,任意のsuffix間の関係ではなく,隣接するsuffix間の関係のみを利用する点にある.このアルゴリズムを二段階ソート法と呼ぶ.514MBの毎日新聞記事を含む様々なデータセットを用いた評価実験により,我々のアルゴリズムはQuicksortの約6倍拘束であり,また,今まで最も高速なアルゴリズムとして知られているSadakaneの方法に対し2?3倍高速であることを示す.The Suffix array is a string indexing structure and a memory efficient alternative of the suffix tree. It has myriad virtues on string processing. However, it requires large memory and computation to build suffix arrays for large texts. We propose an efficient algorithm for sorting suffixes. One of the key ideas is to use specific relationships between an adjacent suffix pair. We call this algorithm the Two-Stage Suffix Sort. Our experiments on several text data sets (including 514MB japanese newspapers) demonstrate that our algorithm is about 6 times faster than the popular sorting algorithm Quicksort, and 2 to 3 times faster than Sadakane's algorithm which is known as the fastest one.

著者

伊東 秀夫

出版者

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

雑誌

情報処理学会研究報告自然言語処理(NL)

巻号頁・発行日

vol.1999, no.2, pp.27-34, 1999-01-20

---

Suffix arrayは文字列索引の一種であり、suffix treeに比べ単純でコンパクトなデータ構造で実装できる。文字列処理に対して多くの優れた性質を持つsuffix arrayだが、特に大規模なテキストに対しては索引構築に多大な記憶量と計算コストを必要とし実用上の問題なっている。我々は、高速かつコンパクトなsuffix array構築法を提案する。そのキーとなるアイデアは、任意のsuffix間の関係ではなく、隣接するsuffix間の関係のみを利用する点にある。このアルゴリズムを二段階ソート法と呼ぶ。514MBの毎日新聞記事を含む様々なデータセットを用いた評価実験により、我々のアルゴリズムはQuicksortの4.5?6.9倍高速であり、また、今までで最も高速なアルゴリズムとして知られているSadakaneの方法に対し2.5?3.6倍高速であることが示される。The Suffix array is a string indexing structure and a memory efficient alternative of the Suffix tree. It has myriad virtues on string processing. However, it requires large memory and computation to build suffix arrays for large texts. We propose an efficient algorithm for sorting suffixes. One of the key ideas is to use specific relationships between an adjacent suffix pair. We call this algorithm the Two-Stage Suffix Sort. Our experiments on several text data sets (including 514MB japanese newspapers) demonstrate that our algorithm is 4.5 to 6.9 times faster than the popular sorting algorithm Quicksort, and 2.5 to 3.6 times faster than Sadakane's algorithms which is known as the fastest one.

著者

定兼 邦彦

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(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.

著者

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

出版者

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

雑誌

情報処理学会論文誌数理モデル化と応用(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.

著者

高橋 慎 加藤 和彦

出版者

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

雑誌

情報処理学会論文誌コンピューティングシステム(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.